search for: postdom

...hat will never change. > > Nobody is looking to change that necessarily, or at least i'm not, only to make the impact not "correctness requires N^2 algorithms or other things that *already* are slowing down the compiler" > - LLVM made the decision/tradeoff not to maintain a postdom tree > throughout most of the pass pipeline > > Well, actually, this one is likely to change. The only issue here is keeping it updated, and i have a solution for that. > - Fundamentally, you don’t really lose anything. > This i'm going to disagree with :) This is basically a...

Hi Daniel, Daniel Berlin wrote: > /* Add fake edges to the function exit for any non constant and non > noreturn calls (or noreturn calls with EH/abnormal edges), > volatile inline assembly in the bitmap of blocks specified by > BLOCKS > or to the whole CFG if BLOCKS is zero. > ... > > The goal is to expose cases in

...sic Blocks. I searched the Programming Guide (http://llvm.org/docs/ProgrammersManual.html#common), it mentioned briefly that such details will be covered in the future. So, I am tuning to the list and ask. Say, I have BasicBlock * a, *b, and need to know whether a DOM b, (a DOMi b, a DOMp b, a PostDOM b), etc. How can these be expressed? Similar things, how can I find all BasicBlocks that a dominates, (DOM, DOMp, PostDOM, ...) Browsing the source code, I seem to find things like DominatorFrontier, DominatorTree, etc. But I have no clue how they can be used. Can somebody leverage some more de...

...ance trees. I implemented dotty printing for dominance trees and introduced these new flags: -dot-dom : Print dominance tree of function to 'dot' file -dot-dom-only : Print dominance tree of function to 'dot' file (with no function bodies) -dot-postdom : Print postdominance tree of function to 'dot' file -dot-postdom-only : Print postdominance tree of function to 'dot' file (with no function bodies) -view-dom : View dominance tree of function -view-dom-only : View dominance tree of functio...

...: Re: [llvm-dev] DCE in the presence of control flow. The post dominators computation costs more on llvm than GCC because of how the respective cfgs work under the covers. Even for GCC, when we implemented cd-dce, it only catches 1-2% more cases. It's not really worth the cost in llvm unless postdom comes free On Wed, Jan 27, 2016, 1:56 PM David Callahan via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote: I have been looking at some internal codes looking for differences between Clang (specifically 3.7.1) and gcc (typically 4.8.1 but sometimes later...

Hi Guys, I am using the Postdom pass and I would like to get the root of the tree. However, everytime I try to get the root, I get a segfault. I don't know why the environment can't find DominatorTreeBase. Below is the code that generates the Segfault. In my .h file I include Dominators.h PDT.getRootNode(); //PDT is a...

...I think it is completely healthy for the project to reevaluate these kinds of decisions. We now have many years of experience, bug reports, and we should have a good ability to evaluate the compile-time impact of a potential change. -Hal > - LLVM made the decision/tradeoff not to maintain a postdom tree > throughout most of the pass pipeline > - Fundamentally, you don’t really lose anything. It’s an easy > analysis to find the exit points and mark blocks. Doing a CFG walk > instead of a PostDom walk is typically not such a big deal. > The fundamental problem relevant to Preci...

I have been looking at some internal codes looking for differences between Clang (specifically 3.7.1) and gcc (typically 4.8.1 but sometimes later). One area where I bumped into was dead code elimination in the presence of complex control flow. I note that the “aggressive dead code elimination” (ADCE.cpp) treats all branch operations as live (isa<TerminatorInst>(I)). Doing more requires

...de/llvm/**Support/CFG.h:105: llvm::SuccIterator<Term_, BB_>::SuccIterator(Term_) [with Term_ = llvm::TerminatorInst*, BB_ = llvm::BasicBlock]: Assertion `T && "getTerminator returned null!"' failed. 0 opt 0x0848e569 Stack dump: 0. Program arguments: opt -dot-cfg -dot-postdom -dot-dom -load /home/llvm/src/Release/lib/**parallel.so -parallel obj.o -o out.o 1. Running pass 'Function Pass Manager' on module 'obj.o'. 2. Running pass 'Loop Pass Manager' on function '@main' Aborted (core dumped)* I do not know why this error occurred.Wh...

...the presence of control flow. > > The post dominators computation costs more on llvm than GCC because of how > the respective cfgs work under the covers. Even for GCC, when we > implemented cd-dce, it only catches 1-2% more cases. It's not really worth > the cost in llvm unless postdom comes free > > > A 1-2% reduction in code size seems like it might well be worth a post-dom > calculation. > 1-2% more cases != 1-2% reduction in code size. In particular, it assumes nothing else will catch those cases :) The cases are mostly caught by SimplifyCFG/etc anyway In an...

...: Re: [llvm-dev] DCE in the presence of control flow. The post dominators computation costs more on llvm than GCC because of how the respective cfgs work under the covers. Even for GCC, when we implemented cd-dce, it only catches 1-2% more cases. It's not really worth the cost in llvm unless postdom comes free A 1-2% reduction in code size seems like it might well be worth a post-dom calculation. 1-2% more cases != 1-2% reduction in code size. In particular, it assumes nothing else will catch those cases :) Fair enough. The cases are mostly caught by SimplifyCFG/etc anyway In any case, her...

After running through bugpoint, I get this reduced function You can reproduce the problem with: opt bugpoint-reduced-function.bc -break-crit-edges -adce -verify Bugpoint is currently trying to narrow down which block breaks this, but is so far failing. It seems to be running out of memory rather than failing on a particular block. This is on freebsd 5.4, X86, llvm is compiled with gcc 3.4.2

...: Re: [llvm-dev] DCE in the presence of control flow. The post dominators computation costs more on llvm than GCC because of how the respective cfgs work under the covers. Even for GCC, when we implemented cd-dce, it only catches 1-2% more cases. It's not really worth the cost in llvm unless postdom comes free A 1-2% reduction in code size seems like it might well be worth a post-dom calculation. 1-2% more cases != 1-2% reduction in code size. In particular, it assumes nothing else will catch those cases :) Fair enough. The cases are mostly caught by SimplifyCFG/etc anyway In any case, her...

...rol flow. >> >> The post dominators computation costs more on llvm than GCC because of >> how the respective cfgs work under the covers. Even for GCC, when we >> implemented cd-dce, it only catches 1-2% more cases. It's not really worth >> the cost in llvm unless postdom comes free >> >> >> A 1-2% reduction in code size seems like it might well be worth a >> post-dom calculation. >> > > 1-2% more cases != 1-2% reduction in code size. In particular, it assumes > nothing else will catch those cases :) > > Fair enough. >...

...: Re: [llvm-dev] DCE in the presence of control flow. The post dominators computation costs more on llvm than GCC because of how the respective cfgs work under the covers. Even for GCC, when we implemented cd-dce, it only catches 1-2% more cases. It's not really worth the cost in llvm unless postdom comes free A 1-2% reduction in code size seems like it might well be worth a post-dom calculation. 1-2% more cases != 1-2% reduction in code size. In particular, it assumes nothing else will catch those cases :) Fair enough. The cases are mostly caught by SimplifyCFG/etc anyway In any case, her...

...ix that too), so it should not be *that* bad. We can make it calculate subgraphs like you do as well. 3. While i think the way you compute CD for the subset is cool, it is a bunch of code, and probably hard for the vast majority of people to understand and debug :) So if we can make IDF (assuming postdom) within a few percent of what you are doing, we should just do it, IMHO. If not, well, it's the old "compile time cost vs actual runtime performance improvement vs any reduced maintenance burden/stuff we can make architecturally more sound" game. On Mon, Apr 4, 2016 at 9:46 AM, Dav...

On Mon, Apr 4, 2016 at 11:49 AM, David Callahan <dcallahan at fb.com> wrote: > > I may have not correctly used the IDFCalculator. I passed in the > PostDominator tree and then changed the loop over successor blocks to also > be able to iterate over predecessors. I did not see anything in the > interface that would let that happen but perhaps I don’t understand the API > so I modified it to explicitly iterate over predecessors under a flag. &g...

Hi, I'm trying to solve a problem from StructurizeCFG not actually handling regions with multiple exits. Sample IR attached. StructurizeCFG doesn't touch this function, exiting early on the isTopLevelRegion check. SIAnnotateControlFlow then gets confused and ends up inserting an if into one of the blocks, and the matching end.cf into one of the return/unreachable blocks. The input to

...is obviously non-linear as it uses the DominanceFrontier analysis. However, for me it works surprisingly well. > When I committed it I tested it on the LLVM test suite, polyhedron.com and the SPEC 2006 benchmarks [1]. I got the following timings (in seconds): > > Name DomTree PostDomTree DomFrontier RegionTree > SPEC 2006 1.109 0.911 0.525 0.662 > Polyhedron.com 0.034 0.029 0.016 0.022 > > On these examples DomFrontier and RegionTree calculation is very fast. Also, I used RegionInfo for over two years in my daily Polly work. A...

On Fri, Mar 25, 2016 at 3:52 PM, Hal Finkel <hfinkel at anl.gov> wrote: > > ------------------------------ > > *From: *"Mehdi Amini via llvm-dev" <llvm-dev at lists.llvm.org> > *To: *"Daniel Berlin" <dberlin at dberlin.org> > *Cc: *"David Callahan via llvm-dev" <llvm-dev at lists.llvm.org> > *Sent: *Friday, March 25, 2016