Movatterモバイル変換

Next:Scalar evolutions, Previous:Loop manipulation, Up:Analysis and Representation of Loops [Contents][Index]

15.4 Loop-closed SSA form ¶

Throughout the loop optimizations on tree level, one extra condition isenforced on the SSA form: No SSA name is used outside of the loop inthat it is defined. The SSA form satisfying this condition is called“loop-closed SSA form” – LCSSA. To enforce LCSSA, PHI nodes must becreated at the exits of the loops for the SSA names that are usedoutside of them. Only the real operands (not virtual SSA names) areheld in LCSSA, in order to save memory.

There are various benefits of LCSSA:

Many optimizations (value range analysis, final valuereplacement) are interested in the values that are defined in the loopand used outside of it, i.e., exactly those for that we create new PHInodes.
In induction variable analysis, it is not necessary to specify theloop in that the analysis should be performed – the scalar evolutionanalysis always returns the results with respect to the loop in that theSSA name is defined.
It makes updating of SSA form during loop transformations simpler.Without LCSSA, operations like loop unrolling may force creation of PHInodes arbitrarily far from the loop, while in LCSSA, the SSA form can beupdated locally. However, since we only keep real operands in LCSSA, wecannot use this advantage (we could have local updating of realoperands, but it is not much more efficient than to use generic SSA formupdating for it as well; the amount of changes to SSA is the same).

However, it also means LCSSA must be updated. This is usuallystraightforward, unless you create a new value in loop and use itoutside, or unless you manipulate loop exit edges (functions areprovided to make these manipulations simple).rewrite_into_loop_closed_ssa is used to rewrite SSA form toLCSSA, andverify_loop_closed_ssa to check that the invariant ofLCSSA is preserved.