similar to: [LLVMdev] post dominance frontier fix

On Fri, 20 Apr 2007, Ryan M. Lefever wrote: > Please advise on how I should proceed. Even though, as I mentioned, the > code does not follow the LLVM coding standards and does not adhere to > the llvm::PostDominanceFrontier interface, I figured it would be better > to a working PDF than to not have it. Perhaps if you don't want to > insert it into the regular LLVM code base,

On Sat, Jan 7, 2012 at 12:14 AM, Cameron Zwarich <zwarich at apple.com> wrote: > On Jan 6, 2012, at 8:27 PM, Daniel Berlin wrote: > > Note: GCC takes exactly the same approach as LLVM here, for exactly > the reason chris specifies. > In fact, until we started local SSA updating (which is now many years > ago, but ...), dominance frontier calculation for ssa updating was in

In the literature (see below for a reference), when a dominance frontier is computed, it is computed from a CFG that contains a dummy entry node and dummy exit node. Further, those dummy nodes are potential members of the (post-)dominance frontier for a given basic block. In LLVM, I could not figure out a way to determine if the dummy entry node is a member of the post-dominance frontier of

On Thu, 9 Nov 2006, Ryan M. Lefever wrote: Sorry I never responded to this: > In the literature (see below for a reference), when a dominance frontier > is computed, it is computed from a CFG that contains a dummy entry node > and dummy exit node. Further, those dummy nodes are potential members > of the (post-)dominance frontier for a given basic block. In LLVM, I > could not

On Jan 6, 2012, at 8:27 PM, Daniel Berlin wrote: > Note: GCC takes exactly the same approach as LLVM here, for exactly > the reason chris specifies. > In fact, until we started local SSA updating (which is now many years > ago, but ...), dominance frontier calculation for ssa updating was in > the top 10 profile functions for GCC compiles of large source files. > I had tried a

Is there a reason this is better than the modified algorithm created by Ferrante? It looks like yours has as bad a worst case time bound in reality. That is, the algorithm runs in O(sum of the size of all the dominance frontiers). http://www.cs.rice.edu/~keith/Embed/dom.pdf See figure 5. It will only touch nodes actually in the dominance frontier. This is what GCC uses. There are actually real

On 4/12/13 3:19 PM, Arsen wrote: > Thank you John. > Actually the opt tool (from LLVM 3.2 version) can generate the needed graphs > (with pass "-domfrontier"). > But I just want to surely know is there some pass or builder which can be > integrated somehow so it will be possible directly to generate CDG? Yes and no. There's isn't a control dependence pass in LLVM

Hi, I'm not able to answer your question. I'm wondering if you can create your own if it is just your own hobby project, or a project that you don't have to commit to the main repository. Creating DominatorFrontier seems to be expensive. However, if you are using bit-vector to represent a basic-block-set, I guess it can be done in linear time in practice. Following is the

Hi all, Does anyone know how to recreate the DominanceFronter and PostDominanceFrontier structures using the API of the latest release? To my knowledge, these are needed to implement a PRE pass (as done in the past<https://llvm.org/svn/llvm-project/llvm/tags/RELEASE_13/lib/Transforms/Scalar/PRE.cpp>), but they were removed a while ago for efficiency reasons. Is there a better way to

On Jan 6, 2012, at 5:08 PM, Chris Lattner wrote: >>> >>> It's very like SSA construction, but must make provision >>> testing anti dependences. I had planned to use dominance frontiers to >>> guide placement of phi nodes, as usual. >> >> Ok, in that case, please check out include/llvm/Transforms/Utils/SSAUpdater.h, >> which is the

Hi, I found that LLVM 3.1 says Dominance frontier is deprecated. Can anyone please tell me, if there is any replacement for Dominance frontier & Postdominance frontier in LLVM? What are the options if we need to use them? Thanks, Swarup. -------------- next part -------------- An HTML attachment was scrubbed... URL:

On Fri, Jan 6, 2012 at 8:17 PM, Chris Lattner <clattner at apple.com> wrote: > > On Jan 6, 2012, at 5:08 PM, Chris Lattner wrote: > >>>> >>>> It's very like SSA construction, but must make provision >>>> testing anti dependences.  I had planned to use dominance frontiers to >>>> guide placement of phi nodes, as usual. >>>

I just finished upgrading our LLVM to 2.4 and I immediately ran into a problem with dominance frontier calculation: llvm/lib/VMCore/PassManager.cpp:714: void llvm::PMDataManager::verifyDomInfo(llvm::Pass&, llvm::Function&): Assertion `0 && "Invalid dominator info"' failed. Strangely enough, the Pass running when the assert triggers is Dominance Frontier

On Feb 18, 2009, at 8:00 AM, David Greene wrote: > I just finished upgrading our LLVM to 2.4 and I immediately ran into > a problem > with dominance frontier calculation: > > llvm/lib/VMCore/PassManager.cpp:714: void > llvm::PMDataManager::verifyDomInfo(llvm::Pass&, llvm::Function&): > Assertion > `0 && "Invalid dominator info"' failed.

On Wednesday 18 February 2009 10:35, Devang Patel wrote: > On Feb 18, 2009, at 8:00 AM, David Greene wrote: > > I just finished upgrading our LLVM to 2.4 and I immediately ran into > > a problem > > with dominance frontier calculation: > > > > llvm/lib/VMCore/PassManager.cpp:714: void > > llvm::PMDataManager::verifyDomInfo(llvm::Pass&,

On Sun, Nov 3, 2013 at 1:02 AM, Daniel Berlin <dberlin at dberlin.org> wrote: > Is there a reason this is better than the modified algorithm created > by Ferrante? > It looks like yours has as bad a worst case time bound in reality. > That is, the algorithm runs in O(sum of the size of all the dominance > frontiers). > > http://www.cs.rice.edu/~keith/Embed/dom.pdf >

On Dec 31, 2011, at 11:04 AM, Preston Briggs wrote: > Hi Chris, > > I wish we could talk about this at a white board, over a period of > weeks, but email will have to do… That would be nice :) > I don't entirely understand your position about dominance frontiers. > In my experience, they were trivial to compute, requiring very little > time, space, or code. Rereading

On Dec 24, 2011, at 7:48 AM, Preston Briggs wrote: > Here's how I did things, back when I got to write my own infrastructure. It's still O(n^2) in the worst case, but much quicker in the expected case. > > Number all the basic blocks, 0 to n-1 and build a vector mapping from integer to block. Requires O(n) time and space. > > For each block, compute the set containing

Hi, Chris I get a new PostDominanceFrontier class by combinating the code of PostDominanceSet/PostDominanceTree/PostDominanceFrontier FunctionPasses. It works very well. BTW: Why the PostDominanceFrontier FunctionPasses does not use the formal argument in runOnFunction(Function &)? Does it gets the Function from PassManager? Thank you. Xia >On Thu, 9 Sep 2004, xia_yimin wrote: >

When analysing a function "fn", my FunctionPass needs some PostDominanceFrontier information of functions which are called by function "fn". getAnalysis<PostDominanceFrontier>() cannot give the information, because it only gives the PostDominanceFrontier information of "fn", not the PostDominanceFrontier information of functions called by "fn".