similar to: [LLVMdev] Is structural analysis pass available?

On 03/16/2010 05:02 PM, James Stanier wrote: > > Hi Trevor, > > I just studied your diagrams -- I *think* that the "control tree" of > structural analysis is not same as the "control flow tree" from your own > Java work. However, as you understand your work more than I do, I present > you with some fancy coloured diagrams that I drew that might help you

On 03/13/2010 08:54 PM, James Stanier wrote: > > Hi folks, Hi James, I have also been working on such a pass for the last couple of month. The pass itself is finished and ether has written some further LLVM support implementing a RegionPass class, that can be used to implement region passes that work like the existing LoopPasses today, but use a region instead of a loop or function as

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

Why not use the "standard" algorithm for detecting SESE-regions and building a program structure tree? It should handle everything you want. It also becomes much simpler to specify a connected SESE-region by entry/exit edges, while a disconnected region is specified by entry/exit blocks. Only defining regions on blocks is not enough to be able to quickly determine how to replace/move a

On 03/15/2010 05:51 PM, James Stanier wrote: > > Hi Tobias, Hi, > > Thanks for getting back to me. I have just had a peek at the documentation > for your region pass, and it looks really cool, and thanks also for the > pointers to the literature. > > If you want an overview of how structural analysis works, some of the pages > from Muchnick's textbook are available

Hi Trevor, I just studied your diagrams -- I *think* that the "control tree" of structural analysis is not same as the "control flow tree" from your own Java work. However, as you understand your work more than I do, I present you with some fancy coloured diagrams that I drew that might help you (and others!) understand what structural analysis does a bit better than the

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

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

The other repliers have been right that you probably want to use Value*s rather than string names in constructing your dependency graph, but I wanted to clear up a second possible point of confusion. When you see %2 in the assembly, that's an indication that the instruction's name is empty. That is, value->getName() == "". As far as I know, llvm-dis just generates numbers in

Hi, Is the structural analysis pass discussed in http://comments.gmane.org/gmane.comp.compilers.llvm.devel/30213 still available to download? Thanks. -- Jianzhou

hi, On Tue, Jul 27, 2010 at 3:32 PM, Tobias Grosser <grosser at fim.uni-passau.de> wrote: > On 07/27/10 09:24, Evan Cheng wrote: >> Any chance you could templatify this so someone can add a MachineRegionInfo later? It would be useful for region based register allocation, etc. >> >> Thanks, >> >> Evan > > Hi Evan, > > ether did once a templated

On Mar 13, 2010, at 11:54 AM, James Stanier wrote: > It > analyses the CFG and recognises specific region schema, such as if- > then, > if-then-else, while-loop, etc., and builds a "control tree" which > represents > the hierarchical structure of the input program. I am not sure if my definition of a control flow tree is the same as yours, but if it is, I am very

You can achieve the 'standalone tools' effect using LLVM bitcode, which is a binary IR format. Then you can have: source code -> [llvm-gcc frontend] -> bc bc -> [your tool using llvm bitcode reader writer library, doing whatever mutations to the IR you want and spitting out bc again] -> bc bc -> [llvm backend (llc)/llvm-as/...] -> native code. Doesn't that meet your

On Fri, Mar 27, 2009 at 11:18 PM, jstanier <j.stanier at sussex.ac.uk> wrote: > > Hi again everyone... > > After following the "Writing an LLVM Pass" tutorial using LLVM 2.5, there > is > a part that states that: > > "This makefile specifies that all of the .cpp files in the current > directory > are to be compiled and linked together into a

Hi Tobias, If the PHI node at exit block of region R has multiple inputs from the R, I split the exit block into 2. The first block contains all PHI nodes whose input are all from the region. The second is the new exit node. All branches (outside R) to the old exit now point the new exit. All regions whose exit is the old exit are also updated with the new exit node. It works like a charm.

On 01/26/2011 07:50 PM, Vu Le wrote: > I guess I didn't have a clear question. > > Suppose we have BB1 and BB2 both point to BB3. > BB1 has variable x. BB2 also as variable x. > BB3 will have PHINode for x with 2 value from BB1 and BB2. > BB1 BB2 > \ / > BB3 > > Now if BB1 and BB2 is extracted into a function > (using ExtractCodeRegion), they

Hi, I want to write a pass that pulls single-entry a single-exit (SESE) region into a function. The idea is similar to extracting a loop in LoopExtractor.cpp. Basically, for each region that meet our criteria, 1. Find all basic blocks in that regions 2. Call llvm::ExtractCodeRegion() to replace that region by a call to the extracted function. 3. Delete the region from the RegionPassManager queue

Hi Tobias, Thanks a lot for the detailed reply. I am working on several new optimizations for OpenCL kernels for a DSP architecture. The project itself has an NDA associated with it, so I cannot go into more details, but the source will be open to public after completion. One of the first steps is to serialize the work-items in a work-group (e.g., insert nested loops around REGIONs in

On 01/08/10 14:20, ether wrote: > sorry that i forgot to change the subjuect > > > hi all, Hi ether, now a kind of more complete answer. > On 2010-1-7 0:11, John Mosby wrote: >> In LLVM we could add support for generalized CFG regions and >> RegionPasses. A region is a part of the CFG. The only information we >> have is, that it has one entry and one exit, this

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 a path passing exit.