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 ...? Thanks, Preston -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111223/4f383bb8/attachment.html>
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 structure and there are usually better ways to do things. What are you trying to do? SSA construction? -Chris
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 ...?It depends on what you need. - PromoteMemoryToRegister.cpp is used for initial SSA construction. - SSAUpdater.h can be used to update SSA form after duplicating code. It works both for LLVM IR and the CodeGen MI representation. - LiveRangeCalc.cpp is used by the register allocator to recompute liveness and SSA form after splitting live ranges. These functions all compute what they need from the dominator tree. /jakob
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 shall I redo the calculation for myself, or ...? > > We're hoping to remove them, because they're inherently an N^2 data structure and there are usually better ways to do things. > What are you trying to do? SSA construction? > > -ChrisTo do dependence analysis efficiently, we want to avoid testing all memory references against each other (another O(N^2) proposition). So we build FUD chains for memory references, guided by the Alias Sets analysis. 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'm surprised they cause you a space problem. In my experience (admittedly, long ago), we never noticed a problem. We certainly had much less memory available at the time. Perhaps we could profitably re-visit how they are represented? Preston
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 Computing Static Single Assignment Form and ...* Cytron, Ferrante, Rosen, Wegman During the calculation, represent the current frontier, DF(X), as suggested in *An Efficient Representation for Sparse Sets* Briggs, Torczon This lets us add members and clear the set in constant time and allows us to enumerate the members in time proportional to the number of members. O(n) space. Then, having computed the DF for a single block, allocate a vector of the appropriate length and copy the members of the set into the vector. This requires time and space proportional to the actual size of the DF, typically much smaller than O(n) per block. When you're done computing DFs, throw away the big sparse set (you only need one as a workspace) and retain the dense vectors. When placing phi nodes, Figure 11 of Cytron, et al., the only use of the DF is to walk over the members in a for loop, and the dense vector is perfect for the occasion. More general representations waste space. So, the only real trick is to change the set representation between the time the DFs are computed and the time they are used. Some people object to numbering the basic blocks, but I've never understood this objection. I did it often, whenever I needed it; it's not some expensive property that you need to maintain across many phases. Preston 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 shall I redo the > calculation for myself, or ...? > > We're hoping to remove them, because they're inherently an N^2 data > structure and there are usually better ways to do things. What are you > trying to do? SSA construction? > > -Chris >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111224/28f6464d/attachment.html>