Re: [patch] PR54146 - rewrite rewrite_into_loop_closed_ssa

[Richard Guenther <richard dot guenther at gmail dot com>]

On Wed, Aug 15, 2012 at 6:26 PM, Steven Bosscher <stevenb.gcc@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