loop.texi

理解和实践操作系统的一本好书

@item @code{flow_loop_tree_node_add}: Adds a node to the tree.
@item @code{flow_loop_tree_node_remove}: Removes a node from the tree.
@item @code{add_bb_to_loop}: Adds a basic block to a loop.
@item @code{remove_bb_from_loops}: Removes a basic block from loops.
@end itemize

Most low-level CFG functions update loops automatically.  The following
functions handle some more complicated cases of CFG manipulations:

@itemize
@item @code{remove_path}: Removes an edge and all blocks it dominates.
@item @code{split_loop_exit_edge}: Splits exit edge of the loop,
ensuring that PHI node arguments remain in the loop (this ensures that
loop-closed SSA form is preserved).  Only useful on GIMPLE.
@end itemize

Finally, there are some higher-level loop transformations implemented.
While some of them are written so that they should work on non-innermost
loops, they are mostly untested in that case, and at the moment, they
are only reliable for the innermost loops:

@itemize
@item @code{create_iv}: Creates a new induction variable.  Only works on
GIMPLE@.  @code{standard_iv_increment_position} can be used to find a
suitable place for the iv increment.
@item @code{duplicate_loop_to_header_edge},
@code{tree_duplicate_loop_to_header_edge}: These functions (on RTL and
on GIMPLE) duplicate the body of the loop prescribed number of times on
one of the edges entering loop header, thus performing either loop
unrolling or loop peeling.  @code{can_duplicate_loop_p}
(@code{can_unroll_loop_p} on GIMPLE) must be true for the duplicated
loop.
@item @code{loop_version}, @code{tree_ssa_loop_version}: These function
create a copy of a loop, and a branch before them that selects one of
them depending on the prescribed condition.  This is useful for
optimizations that need to verify some assumptions in runtime (one of
the copies of the loop is usually left unchanged, while the other one is
transformed in some way).
@item @code{tree_unroll_loop}: Unrolls the loop, including peeling the
extra iterations to make the number of iterations divisible by unroll
factor, updating the exit condition, and removing the exits that now
cannot be taken.  Works only on GIMPLE.
@end itemize

@node LCSSA
@section Loop-closed SSA form
@cindex LCSSA
@cindex Loop-closed SSA form

Throughout the loop optimizations on tree level, one extra condition is
enforced on the SSA form:  No SSA name is used outside of the loop in
that it is defined.  The SSA form satisfying this condition is called
``loop-closed SSA form'' -- LCSSA@.  To enforce LCSSA, PHI nodes must be
created at the exits of the loops for the SSA names that are used
outside of them.  Only the real operands (not virtual SSA names) are
held in LCSSA, in order to save memory.

There are various benefits of LCSSA:

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

However, it also means LCSSA must be updated.  This is usually
straightforward, unless you create a new value in loop and use it
outside, or unless you manipulate loop exit edges (functions are
provided to make these manipulations simple).
@code{rewrite_into_loop_closed_ssa} is used to rewrite SSA form to
LCSSA, and @code{verify_loop_closed_ssa} to check that the invariant of
LCSSA is preserved.

@node Scalar evolutions
@section Scalar evolutions
@cindex Scalar evolutions
@cindex IV analysis on GIMPLE

Scalar evolutions (SCEV) are used to represent results of induction
variable analysis on GIMPLE@.  They enable us to represent variables with
complicated behavior in a simple and consistent way (we only use it to
express values of polynomial induction variables, but it is possible to
extend it).  The interfaces to SCEV analysis are declared in
@file{tree-scalar-evolution.h}.  To use scalar evolutions analysis,
@code{scev_initialize} must be used.  To stop using SCEV,
@code{scev_finalize} should be used.  SCEV analysis caches results in
order to save time and memory.  This cache however is made invalid by
most of the loop transformations, including removal of code.  If such a
transformation is performed, @code{scev_reset} must be called to clean
the caches.

Given an SSA name, its behavior in loops can be analyzed using the
@code{analyze_scalar_evolution} function.  The returned SCEV however
does not have to be fully analyzed and it may contain references to
other SSA names defined in the loop.  To resolve these (potentially
recursive) references, @code{instantiate_parameters} or
@code{resolve_mixers} functions must be used.
@code{instantiate_parameters} is useful when you use the results of SCEV
only for some analysis, and when you work with whole nest of loops at
once.  It will try replacing all SSA names by their SCEV in all loops,
including the super-loops of the current loop, thus providing a complete
information about the behavior of the variable in the loop nest.
@code{resolve_mixers} is useful if you work with only one loop at a
time, and if you possibly need to create code based on the value of the
induction variable.  It will only resolve the SSA names defined in the
current loop, leaving the SSA names defined outside unchanged, even if
their evolution in the outer loops is known.

The SCEV is a normal tree expression, except for the fact that it may
contain several special tree nodes.  One of them is
@code{SCEV_NOT_KNOWN}, used for SSA names whose value cannot be
expressed.  The other one is @code{POLYNOMIAL_CHREC}.  Polynomial chrec
has three arguments -- base, step and loop (both base and step may
contain further polynomial chrecs).  Type of the expression and of base
and step must be the same.  A variable has evolution
@code{POLYNOMIAL_CHREC(base, step, loop)} if it is (in the specified
loop) equivalent to @code{x_1} in the following example

@smallexample
while (@dots{})
  @{
    x_1 = phi (base, x_2);
    x_2 = x_1 + step;
  @}
@end smallexample

Note that this includes the language restrictions on the operations.
For example, if we compile C code and @code{x} has signed type, then the
overflow in addition would cause undefined behavior, and we may assume
that this does not happen.  Hence, the value with this SCEV cannot
overflow (which restricts the number of iterations of such a loop).

In many cases, one wants to restrict the attention just to affine
induction variables.  In this case, the extra expressive power of SCEV
is not useful, and may complicate the optimizations.  In this case,
@code{simple_iv} function may be used to analyze a value -- the result
is a loop-invariant base and step.

@node loop-iv
@section IV analysis on RTL
@cindex IV analysis on RTL

The induction variable on RTL is simple and only allows analysis of
affine induction variables, and only in one loop at once.  The interface
is declared in @file{cfgloop.h}.  Before analyzing induction variables
in a loop L, @code{iv_analysis_loop_init} function must be called on L.
After the analysis (possibly calling @code{iv_analysis_loop_init} for
several loops) is finished, @code{iv_analysis_done} should be called.
The following functions can be used to access the results of the
analysis:

@itemize
@item @code{iv_analyze}: Analyzes a single register used in the given
insn.  If no use of the register in this insn is found, the following
insns are scanned, so that this function can be called on the insn
returned by get_condition.
@item @code{iv_analyze_result}: Analyzes result of the assignment in the
given insn.
@item @code{iv_analyze_expr}: Analyzes a more complicated expression.
All its operands are analyzed by @code{iv_analyze}, and hence they must
be used in the specified insn or one of the following insns.
@end itemize

The description of the induction variable is provided in @code{struct
rtx_iv}.  In order to handle subregs, the representation is a bit
complicated; if the value of the @code{extend} field is not
@code{UNKNOWN}, the value of the induction variable in the i-th
iteration is

@smallexample
delta + mult * extend_@{extend_mode@} (subreg_@{mode@} (base + i * step)),
@end smallexample

with the following exception:  if @code{first_special} is true, then the
value in the first iteration (when @code{i} is zero) is @code{delta +
mult * base}.  However, if @code{extend} is equal to @code{UNKNOWN},
then @code{first_special} must be false, @code{delta} 0, @code{mult} 1
and the value in the i-th iteration is

@smallexample
subreg_@{mode@} (base + i * step)
@end smallexample

The function @code{get_iv_value} can be used to perform these
calculations.

@node Number of iterations
@section Number of iterations analysis
@cindex Number of iterations analysis

Both on GIMPLE and on RTL, there are functions available to determine
the number of iterations of a loop, with a similar interface.  The
number of iterations of a loop in GCC is defined as the number of
executions of the loop latch.  In many cases, it is not possible to
determine the number of iterations unconditionally -- the determined
number is correct only if some assumptions are satisfied.  The analysis
tries to verify these conditions using the information contained in the
program; if it fails, the conditions are returned together with the
result.  The following information and conditions are provided by the
analysis:

@itemize
@item @code{assumptions}: If this condition is false, the rest of
the information is invalid.
@item @code{noloop_assumptions} on RTL, @code{may_be_zero} on GIMPLE: If
this condition is true, the loop exits in the first iteration.
@item @code{infinite}: If this condition is true, the loop is infinite.