search for: dominate

Hi Tobias, 1) Daniel and Chandler have for a long time been talking about computing > dominance and post-dominance in one shot to reduce the cost of > post-dominance and make it (freely) available everywhere. Is this > covered by your current (or planned) work? I'm not sure what you exactly mean by one shot; I'll ask around tomorrow. I wanted to play a little bit with your

>> all the zero paths from entry to %a pass by %b. > > > That is a graph-wise definition, sure. > So, this is an interesting definition, and maybe this is part of the source > of the problem. > > For SSA, at least GCC requires that both "definition block dominates use > block" (which would be true here), *and* > that "definition appears before use in block" (IE definition locally > dominates use). > > IE it has to pass both DT->dominates(block(%b), block(%a)) and > DT->dominates(%b, %a). > > LLVM special cases &q...

...BB10 (malloc) / \ BB11 BB12 ... / \ / \ ... \ / \ / \ / BB13 BB14 BB15 | ... | / BB16 The block BB10 dominates BB11, BB12 and BB14. The dominance frontier of BB10 contains BB13, BB15 and BB16. So if the predecessors of the dominance frontier contains BB11, BB12 and BB14. If a call to free is inserted into BB11, BB12, and BB14, double free would occur. The problem boils down to this: how can we ensure exact...

...alloc(), we will end up in one of the blocks in the dominance frontier (kind of). These blocks must have multiple predecessors, else it would not be in the dominance frontier. If a predecessors of these blocks has only one successor, then that successor is the block in the dominance frontier and it dominates nobody. If it has multiple successors, then a critical edge will be placed between this predecessor and the block in the dominance frontier. Thus, the predecessor will now be a block that also dominates nobody. This means that we cannot reach another block where a call to free() was inserted witho...

...libLLVMCore.a(Dominators.cpp.o) duplicate symbol llvm::DominatorTreeBase<llvm::BasicBlock, true>::DominatorTreeBase() in: ../../lib/libLLVMAnalysis.a(PostDominators.cpp.o) ../../lib/libLLVMCore.a(Dominators.cpp.o) duplicate symbol llvm::DominatorTreeBase<llvm::BasicBlock, true>::dominates(llvm::DomTreeNodeBase<llvm::BasicBlock> const*, llvm::DomTreeNodeBase<llvm::BasicBlock> const*) const in: ../../lib/libLLVMAnalysis.a(PostDominators.cpp.o) ../../lib/libLLVMCore.a(Dominators.cpp.o) duplicate symbol llvm::DominatorTreeBase<llvm::BasicBlock, true>::properly...

Like I said, i'm nearly positive there is a much faster way, as the sets are mostly shared except in the cyclic case, and in all reducible cyclic cases, removal of back-arcs does not affect dominance (because in any reducible flowgraph, v dominates u whenever u,v is a back-arc) On Tue, Apr 25, 2017 at 7:38 PM, Hongbin Zheng <etherzhhb at gmail.com> wrote: > Hi Daniel, > > Thanks a lot for all these explanation, I will try it out. > > Hongbin > > On Tue, Apr 25, 2017 at 7:04 PM, Daniel Berlin <dberlin at dberl...

...<dberlin at dberlin.org> >> wrote: >> >>> >>> >>> On Tue, Apr 25, 2017 at 6:17 PM, Hongbin Zheng <etherzhhb at gmail.com> >>> wrote: >>> >>>> Hi Daniel, >>>> >>>> I mean "*As a set*, B + C dominate D". >>>> >>>> On Tue, Apr 25, 2017 at 5:42 PM, Daniel Berlin <dberlin at dberlin.org> >>>> wrote: >>>> >>>>> When you say collectively, you mean "would dominate it if considered a >>>>> single block togeth...

...ge from START to END). In contrast, it seems that the current LLVM post-dominator analysis only operates in a mode in which it generates a forest of post-dominator trees, with one rooted at each exit node. The problem this can cause is that, by nature, these trees omit some nodes which are not post-dominated by any one exit. This invalidates analyses which build on a traversal of the post-dominator tree. (In my case, I'm implementing Pingali & Bilardi's optimal control dependence algorithms: http://doi.acm.org/10.1145/256167.256217.) Consider, for example, a simple function with a single...

When looking into https://llvm.org/bugs/show_bug.cgi?id=24866, I discovered that the root cause of the crash is that I was expecting every basic block to have a corresponding Node in the dominator tree. Apparently, the "while.end" basic block in the example does not have a Node in the Dominator Tree. Can anyone tell me if this is expected? If so, under what circumstances?

Hi, In browsing through the LLVM source, I don't currently see an implementation for a control dependence graph builder. Am I overlooking something? It doesn't look like LLVM currently provides a way to build the post-dominance frontier of the reverse CFG, either. Dominators.h mentions forward dominators, but I believe all this is referring to is dominators as opposed to post-dominators,

...t;> >> >> but accepting >> >> >> >> %a = getelementptr inbounds i8* %b, i64 1 >> >> %b = getelementptr inbounds i8* %a, i64 1 >> >> >> > >> > Does the verifier accept the latter right now? >> >> Yes. %a dominates %b and %b dominates %a, so it is valid. >> > > So i'm confused. > > How does %b dominate %a? all the zero paths from entry to %a pass by %b. Cheers, Rafael

Btw, here is another interesting paper about post-dominators and control dependence: https://pdfs.semanticscholar.org/cbb2/9a0e4895025bd9df24f9263217df12f1ed1e.pdf I think a great outcome of your internship would be some precise documentation regarding the guarantees the LLVM dominators give -- possibly also considering classic and weak control dependence and the difference between

Hi I run into an issue as part of splitting a critical edge during LICM. When a new basic block is created and needs to be added into the dominator tree, the block is already in the dominator tree. I print the dominator tree and I see it is added into the tree as child of node it is supposed to dominate. How do I debug to find out why/when its getting added into the tree. ? Tips/suggestions on how to debug to find out how the densemap involved is getting updated will be great. thanks Shrey -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/p...

There is PostDominatorTree for determining post-dominance. Even if A post-dominates B and B is executed, that doesn't guarantee that A will be executed. For example, there could be an infinite loop in-between. Strong post-dominance makes the stronger guarantee that there will be no infinite loop from B to A. Do we have anything in LLVM for determining strong post-dominance an...

On Tue, Apr 25, 2017 at 6:32 PM, Daniel Berlin <dberlin at dberlin.org> wrote: > > > On Tue, Apr 25, 2017 at 6:17 PM, Hongbin Zheng <etherzhhb at gmail.com> > wrote: > >> Hi Daniel, >> >> I mean "*As a set*, B + C dominate D". >> >> On Tue, Apr 25, 2017 at 5:42 PM, Daniel Berlin <dberlin at dberlin.org> >> wrote: >> >>> When you say collectively, you mean "would dominate it if considered a >>> single block together? >>> >>> IE >>> &g...

...013 at 9:13 PM, Henrique Santos < henrique.nazare.santos at gmail.com> wrote: > PRE normally uses a latest placement algorithm to do something of the sort. > I don't know about GVN/PRE, but older version of PRE might have it. > Just placing the calls to free at the predecessors (dominated by BB12) of > the dominance frontier of BB12 seems to work, however. Is there anything > wrong with this? > It seems that placing the calls to free at the predecessors of dominance frontier is inadequate. It is possible that there are exit blocks that are dominated by BB12 (calls to mallo...

> > It seems that placing the calls to free at the predecessors of dominance > frontier is inadequate. It is possible that there are exit blocks that are > dominated by BB12 (calls to malloc). I guess we can also insert calls to > free at these exit blocks too. That crossed my mind a few minutes later. : ) If you're interested, PRE.cpp existed last at r25315. It calculates the "availability frontier" which is probably what you're looking...

Hi, Is there any way to quickly test if a set of basic block collectively dominate another basic block? Thanks Hongbin -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170425/b9336a6d/attachment.html>

Hi folks, This summer I'm working on improving dominators during my internship at Google. Below is an RFC on switching to dynamic dominators, which you can also read as a Google Doc <https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing> if you prefer so. Please let us know what you think. ~Kuba

...). In contrast, it > seems that the current LLVM post-dominator analysis only operates in a > mode in which it generates a forest of post-dominator trees, with one > rooted at each exit node. The problem this can cause is that, by > nature, these trees omit some nodes which are not post-dominated by > any one exit. This invalidates analyses which build on a traversal of > the post-dominator tree. > > (In my case, I'm implementing Pingali & Bilardi's optimal control > dependence algorithms: http://doi.acm.org/10.1145/256167.256217.) > > Consider, for example...