gcc/doc/gccint/analysis-and-representation-of-loops/loop-closed-ssa-form.rst

   1 ..
   2   Copyright 1988-2022 Free Software Foundation, Inc.
   3   This is part of the GCC manual.
   4   For copying conditions, see the copyright.rst file.
   5
   6 .. index:: LCSSA, Loop-closed SSA form
   7
   8 .. _lcssa:
   9
  10 Loop-closed SSA form
  11 ********************
  12
  13 Throughout the loop optimizations on tree level, one extra condition is
  14 enforced on the SSA form:  No SSA name is used outside of the loop in
  15 that it is defined.  The SSA form satisfying this condition is called
  16 'loop-closed SSA form' -- LCSSA.  To enforce LCSSA, PHI nodes must be
  17 created at the exits of the loops for the SSA names that are used
  18 outside of them.  Only the real operands (not virtual SSA names) are
  19 held in LCSSA, in order to save memory.
  20
  21 There are various benefits of LCSSA:
  22
  23 * Many optimizations (value range analysis, final value
  24   replacement) are interested in the values that are defined in the loop
  25   and used outside of it, i.e., exactly those for that we create new PHI
  26   nodes.
  27
  28 * In induction variable analysis, it is not necessary to specify the
  29   loop in that the analysis should be performed -- the scalar evolution
  30   analysis always returns the results with respect to the loop in that the
  31   SSA name is defined.
  32
  33 * It makes updating of SSA form during loop transformations simpler.
  34   Without LCSSA, operations like loop unrolling may force creation of PHI
  35   nodes arbitrarily far from the loop, while in LCSSA, the SSA form can be
  36   updated locally.  However, since we only keep real operands in LCSSA, we
  37   cannot use this advantage (we could have local updating of real
  38   operands, but it is not much more efficient than to use generic SSA form
  39   updating for it as well; the amount of changes to SSA is the same).
  40
  41 However, it also means LCSSA must be updated.  This is usually
  42 straightforward, unless you create a new value in loop and use it
  43 outside, or unless you manipulate loop exit edges (functions are
  44 provided to make these manipulations simple).
  45 ``rewrite_into_loop_closed_ssa`` is used to rewrite SSA form to
  46 LCSSA, and ``verify_loop_closed_ssa`` to check that the invariant of
  47 LCSSA is preserved.