gccint: LCSSA
1
1 16.4 Loop-closed SSA form
1 =========================
1
1 Throughout the loop optimizations on tree level, one extra condition is
1 enforced on the SSA form: No SSA name is used outside of the loop in
1 that it is defined. The SSA form satisfying this condition is called
1 "loop-closed SSA form" - LCSSA. To enforce LCSSA, PHI nodes must be
1 created at the exits of the loops for the SSA names that are used
1 outside of them. Only the real operands (not virtual SSA names) are
1 held in LCSSA, in order to save memory.
1
1 There are various benefits of LCSSA:
1
1 * Many optimizations (value range analysis, final value replacement)
1 are interested in the values that are defined in the loop and used
1 outside of it, i.e., exactly those for that we create new PHI
1 nodes.
1 * In induction variable analysis, it is not necessary to specify the
1 loop in that the analysis should be performed - the scalar
1 evolution analysis always returns the results with respect to the
1 loop in that the SSA name is defined.
1 * It makes updating of SSA form during loop transformations simpler.
1 Without LCSSA, operations like loop unrolling may force creation of
1 PHI nodes arbitrarily far from the loop, while in LCSSA, the SSA
1 form can be updated locally. However, since we only keep real
1 operands in LCSSA, we cannot use this advantage (we could have
1 local updating of real operands, but it is not much more efficient
1 than to use generic SSA form updating for it as well; the amount of
1 changes to SSA is the same).
1
1 However, it also means LCSSA must be updated. This is usually
1 straightforward, unless you create a new value in loop and use it
1 outside, or unless you manipulate loop exit edges (functions are
1 provided to make these manipulations simple).
1 'rewrite_into_loop_closed_ssa' is used to rewrite SSA form to LCSSA, and
1 'verify_loop_closed_ssa' to check that the invariant of LCSSA is
1 preserved.
1