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? Ciao! Steven
PR54146_lcssa.diff
Description: Binary data
