similar to: [LLVMdev] dominance frontiers

On Dec 23, 2011, at 1:35 PM, Preston Briggs wrote: > Reading the comments in Analysis/DominanceFrontier.h, I see a note that the structure is deprecated and we're not to use it for anything new. > > Has it been replaced with something equally useful, or shall I redo the calculation for myself, or ...? We're hoping to remove them, because they're inherently an N^2 data

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 it's dominance frontier, based on Figure 10 of * * *Efficiently

On Fri, Dec 23, 2011 at 3:53 PM, Chris Lattner <clattner at apple.com> wrote: > > > On Dec 23, 2011, at 1:35 PM, Preston Briggs wrote: > > > Reading the comments in Analysis/DominanceFrontier.h, I see a note that the structure is deprecated and > > we're not to use it for anything new. > > > > Has it been replaced with something equally useful, or

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

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 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

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

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. >>>

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

Reading the LLVM Programmer's Manual, the description of DenseSet mentions: *Note that DenseSet has the same requirements for the value type that DenseMap <http://llvm.org/docs/ProgrammersManual.html#dss_densemap> has.* But when I read about DenseMap, I don't really see any requirements for the values, just a warning about space. On the other hand, the *keys* have special

My problem was that the constructor for DenseMap has an undocumented constraint. explicit DenseMap(unsigned NumInitBuckets = 0) { init(NumInitBuckets); } if given an explicit argument, requires that the argument be a power of 2. It's checked by an assert in init(), but for some reason my code didn't trip the assertion. Is there a special way I must make to enable asserts? Thanks,

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

Hi Alexandru, On 25/01/13 10:23, Alexandru Ionut Diaconescu wrote: > Thank you a lot for your response. I will try to use your approach with chasing > back along def-use chains to find instructions that define the registers used in > the load. Can you tell me please what class/methods/existing path are good for > this? I assume that I must have a method with arguments like the

Hello Duncan, I compiled LLVM without optimizations (because maybe I have to look to memory accesses in the future). Maybe some of these optimizations I can enable when I am running my pass with opt ? It is still one thing that I don't understand. If the memory accesses will be eliminated, and I have the following situation: %i = alloca i32, align 4 %j = alloca i32, align 4 ..... %2 = load

Hi Guys, I saw in the API that DominanceFrontier has been deprecated. Is this for real? I have read the computational issues but shouldn't that be left to the users of llvm? My concern is I am writing a Control Dependence module that uses Dominance-Frontier information. Getting rid of Dominance Frontiers will put me in a tight spot. George -------------- next part -------------- An HTML

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 George, > I saw in the API that DominanceFrontier has been deprecated. Is this for real? > I have read the computational issues but shouldn't that be left to the users of > llvm? > My concern is I am writing a Control Dependence module that uses > Dominance-Frontier information. > Getting rid of Dominance Frontiers will put me in a tight spot. if the dominancefrontier

I think y'all underestimate how important documentation can be. There are, after all, documents out there that purport to be guides to writing a back end for LLVM. I know of 2 other experienced & motivated compiler writers who read the available documentation, wrote some code, foundered, gave up, and wrote their own back end from scratch. So there's three of us that I know about, and I

On 25 September 2013 22:13, Preston Briggs <preston.briggs at gmail.com> wrote: > A lot of my difficulty in reading other examples is that it's not clear > what matters and what doesn't. It's what I hope to get by sitting next to > someone and asking questions. Some of this could be addressed in a guide. > I'd start with a chapter on planning. > Another

On Thu, Sep 26, 2013 at 12:22 PM, Preston Briggs <preston.briggs at gmail.com>wrote: > I think y'all underestimate how important documentation can be. > I'm a strong proponent for good documentation, and whenever I get a solid understanding of a specific part of LLVM I will usually write documentation for it. (I'm pretty clueless about backend stuff, which is why I