On Wed, Aug 15, 2012 at 6:26 PM, Steven Bosscher <stevenb....@gmail.com> wrote: > Hello, > > This patch rewrites the rewriting part of > rewrite_into_loop_closed_ssa. This function took ~300s on the > simplified test case for PR54146, walking around the many thousands of > loops in the >400,000 basic blocks in the CFG, in > compute_global_livein. > > For rewriting into LC-SSA, we can do better than that if we use the > knowledge that we're actually computing livein for an SSA name "DEF", > therefore its uses must all be dominated by the basic block where DEF > is assigned a value. But walking up the dominator tree doesn't work > here because we want to traverse and mark the edges in the CFG where > DEF is live, and we may not see those edges if we walk up the > dominator tree from a USE to DEF. We do know, however, that when we > walk up the CFG then: > > 1. if we enter any loop nested in the same loop as the basic block > containing DEF (let's call it DEF_LOOP) then we can stop walking > because the only way in is through one of the edges we're interested > in. > > 2. if we enter a loop is not in the nesting stack of DEF_LOOP, then we > can skin straight to the header of the loop and continue looking up > from there. > > 3. if we reach a basic block X as a predecessor of Y and Y dominates X > then we don't have to look at X or any of its predecessors. > > Putting this all together, you end up with what looks like a poor > man's form of structural analysis where the control tree only contains > loop nodes, non-loop basic blocks, and irreducible regions. (Honza: > maybe re-surrect > http://gcc.gnu.org/ml/gcc-patches/2003-06/msg01669.html? Now that we > can maintain the loop tree, perhaps it's also feasible to maintain the > complete control tree and use it in places where we want to analyze > only a sub-CFG?) > > The effect is that the time spent in rewrite_into_loop_closed_ssa > drops to less than one second. > > Bootstrapped&tested on powerpc64-unknown-linux-gnu. OK for trunk?
Ok! It recently occured to me that the only reason we do not have virtual operands in loop-closed-SSA form (and thus jump through hoops dealing with them in cfgloopmainp and elsewhere) was that we'd have so many of them. Today we just have a single one, so maybe we can simplify things here (the into-lc-SSA code just skips vops, not doing that should provide lc-SSA form even for virtuals). Many thanks for all these speed-ups! Richard. > Ciao! > Steven
