search for: regioninfo

Hi Tobias, My RegionSimplify pass adds new exit node for refined regions to convert them into simple region. However, the RegionInfo pass does not seem to recognize those changes. For example, in the attached file, bb4.region is supposed to be in the first region. My RegionExtractor pass required the extracted region to be simple. Should we modify RegionInfo or is their away to preserve the RegionInfo from RegionSimplify and pa...

Tobias, Thanks for taking the time to summarize all this. It's a great writeup. I'm moving the thread to llvm-dev. My responses below. On May 21, 2012, at 5:06 AM, Tobias Grosser <tobias at grosser.es> wrote: > First of all some information about the RegionInfo pass: > > ======================================================================= > The very first paper I was looking at, when implementing it was "The Program Structure Tree: Computing Control Regions in Linear Time (1994)". Nadav already mentioned this and it is also mentione...

Hi fellows, I am writing to ask what is the algorithm implemented in LLVM's RegionInfo.h/cpp. In the header file "RegionInfo.h", it says "Calculates a program structure tree built out of single entry single exit regions (defined in a 1994 paper called "The Program Structure Tree"). ... ... The algorithm to calculate these data structures however is COMPLETELY...

...         [5] for.cond => return             [6] if.end62 => if.end69             [6] if.end69 => if.end75             [6] for.end => if.end81             [6] for.cond88 => return               [7] for.end143 => return End region tree opt: /home/towelie/Tools/LLVM/llvm/lib/Analysis/RegionInfo.cpp:86: bool llvm::Region::contains(const llvm::BasicBlock *) const: Assertion `DT->getNode(BB) && "BB not part of the dominance tree"' failed. 0  opt             0x0000000000bc715e 1  opt             0x0000000000bc765a 2  libpthread.so.0 0x00007fe7ed96d420 3  libc.so.6    ...

...o serialize the work-items in a work-group (e.g., insert nested loops around REGIONs in between barriers). At this point, I thought I should implement a full-featured structural analysis, but some one in my team suggested to first explore what was already in the LLVM. That's what lead me to the RegionInfo class. If it's not much trouble, could you send the draft to my forum email? Also, are you aware of any plan on having the interval/structural analysis supported in LLVM. Thanks again. P.S. One thing I need to find out from reading the implementation is why a sequence of basic blocks do not ge...

...> [6] if.end62 => if.end69 > [6] if.end69 => if.end75 > [6] for.end => if.end81 > [6] for.cond88 => return > [7] for.end143 => return > End region tree > opt: /home/towelie/Tools/LLVM/llvm/lib/Analysis/RegionInfo.cpp:86: bool > llvm::Region::contains(const llvm::BasicBlock *) const: Assertion > `DT->getNode(BB) && "BB not part of the dominance tree"' failed. > 0 opt 0x0000000000bc715e > 1 opt 0x0000000000bc765a > 2 libpthread.so.0 0x00007fe7...

...asking for an mathematical proof really. It sounds to me like there should be a theorem or two in the graph theory endorsing it. Or do you mean, the implementation is solely based on empirical observation instead of theory. The reason I am interested in the formalization is that I find the current RegionInfo implementation very helpful in defining regions in between barriers in the OpenCL implementation on CPU. I haven't found a test case that breaks it. I got the right intuition, just could not figure out a way to formally prove it, neither did I find one in your regioninfo draft. Thanks, Paul...

Hi Tobi, I have one additional question about the RegionInfo::isRegion function. In the second case (i.e. Entry dominates Exit), why is checking the following two conditions are equivalent to checking it's a refined region: For any BB in DF(exit), 1) BB should be in DF(entry) 2) BB reachable only from entry through...

Hi Fellows, I notice an unexpected behavior in RegionInfo's block_iterator. Consider the following situation: a user creates her own region containing just a single basic block TheBB, then tries to have the block_iterator to print a DFS traversal of the region. The expected behavior should be that only the single basic block TheBB will be printed, but...

...obias, Thanks so much for the quick response. Your approach fixes the issue. On a bigger context, would it make more sense to make the region exit part of the region? For example, a while loop gets lowered down to LLVM IR contains while.cond, while.body and while.end. If one tries to use RegionInfo as a substitute for structural analysis, she might think while.end should belong to the region/structure ... is it necessary to exclude the exit from being part of the region or both ways are equally correct in terms of uniquely representing regions? Best, Paul [image: Inline image 1] On Fri,...

...r approach fixes the >> issue. >> On a bigger context, would it make more sense to make the region >> exit >> part of the region? For example, a while loop gets lowered down to LLVM IR >> contains while.cond, while.body and while.end. If one tries to use >> RegionInfo as a substitute for structural analysis, she might think >> while.end should belong to the region/structure ... is it necessary to >> exclude the exit from being part of the region or both ways are equally >> correct in terms of uniquely representing regions? >> > > Th...

...w.informatics.sussex.ac.uk/users/js231/img/sa-controltree.pdf > > Does this make it any clearer? I'm happy to explain it in more detail. Hi James, this is very close to what ether and me have implemented. However you have got the nicer graphics, they look great. If you want to try the RegionInfo pass call: opt -regions -analyze somefile.ll This will print you a tree that is not as nice as your graphics, but should have the same semantics. The algorithm I used is probably different, however the results are the same. The main difference I see between our approaches is that you classify...

Last time I asked here about superblocks (which we were using in the first version of ThreadSanitizer instrumentation) Tobias Grosser has suggested to use RegionInfo: did you have a look at the RegionInfo pass? It currently detects some kind of refinded SESE regions. I use them in Polly and as far as I know the Intel OpenCL SDK also uses them in some way. It is not SEME, but it may either fit your needs or we may think about extending it. If yo...

On Wed, 08 Dec 2010 12:09:27 -0600 greened at obbligato.org (David A. Greene) wrote: > Török Edwin <edwintorok at gmail.com> writes: > > > What are we left with then? Only 4.2 and 4.3? > > On SLES 10.1 at least. I think it is highly platform dependent. Also keep in mind that llvm-gcc uses the 4.2 unwinder, so if you are seeing EH failures maybe the EH info generated by

Török Edwin <edwintorok at gmail.com> writes: > What are we left with then? Only 4.2 and 4.3? On SLES 10.1 at least. I think it is highly platform dependent. > I only use 4.4 since a while, and it works fairly well. On what platform? > Are you sure it is not a bug in the regression tests themselves > (strict-aliasing bugs, etc.)? No, I'm not sure. > Which

...: note: possible intended match here [x86_64-off-dbg]: NoModRef: Ptr: i8* @B <-> call void @llvm.memset.p0i8.i64(i8* @A, i8 0, i64 1, i32 1, i1 false) [x86_64-off-dbg]: ^ [x86_64-off-dbg]: -- [x86_64-off-dbg]: [x86_64-off-dbg]: ******************** [x86_64-off-dbg]: FAIL: LLVM :: Analysis/RegionInfo/mix_1.ll (2791 of 8402) [x86_64-off-dbg]: ******************** TEST 'LLVM :: Analysis/RegionInfo/mix_1.ll' FAILED ******************** [x86_64-off-dbg]: Script: [x86_64-off-dbg]: -- [x86_64-off-dbg]: opt -regions -analyze < /ptmp/dag/llvm-project.official/llvm/trunk/test/Analysis/RegionI...

...h; however, this is not always the case. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120215/03c7d484/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: RegionInfo_loop Type: application/octet-stream Size: 3169 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120215/03c7d484/attachment.obj>

Hi folks, A few months back I finished writing and testing a pass which implements "structural analysis" as described originally by Sharir in 1980 ("Structural analysis: A new approach to flow analysis in optimizing compilers") and more recently by Muchnick in Advanced Compiler Design and Implementation. It analyses the CFG and recognises specific region schema, such as

...olly.grosser.es/example_load_Polly_into_clang.html > error: unable to load plugin > '/Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib': > 'dlopen(/Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib, > 9): Symbol not found: __ZN4llvm10RegionInfo2IDE > Referenced from: > /Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib > Expected in: flat namespace > in /Users/Kariddi/Documents/Sviluppo/Tesi/git-prefix/lib//LLVMPolly.dylib' > clang (LLVM option parsing): Unknown command line argument > ...

...1 BB2 > \ / > PhiBB > | > BB > And extract BB1, BB2 and PhiBB. > If you have any ideas or if you think this will not work, please let me > know. > Thanks. > Vu Hi Vu, I believe this is the right approach. If I am right and you work on the RegionInfo pass I believe what you want is only to extract so called simpleRegions that have just a single entry and exit edge. Have a look at the email from Andreas Simbuerger two weeks ago: [llvm-commits] [PATCH] Add SeSeRegionInfo transform pass This should contain the functions needed to transform a r...