gccint: Scalar evolutions

1 
1 16.5 Scalar evolutions
1 ======================
1 
1 Scalar evolutions (SCEV) are used to represent results of induction
1 variable analysis on GIMPLE.  They enable us to represent variables with
1 complicated behavior in a simple and consistent way (we only use it to
1 express values of polynomial induction variables, but it is possible to
1 extend it).  The interfaces to SCEV analysis are declared in
1 'tree-scalar-evolution.h'.  To use scalar evolutions analysis,
1 'scev_initialize' must be used.  To stop using SCEV, 'scev_finalize'
1 should be used.  SCEV analysis caches results in order to save time and
1 memory.  This cache however is made invalid by most of the loop
1 transformations, including removal of code.  If such a transformation is
1 performed, 'scev_reset' must be called to clean the caches.
1 
1  Given an SSA name, its behavior in loops can be analyzed using the
1 'analyze_scalar_evolution' function.  The returned SCEV however does not
1 have to be fully analyzed and it may contain references to other SSA
1 names defined in the loop.  To resolve these (potentially recursive)
1 references, 'instantiate_parameters' or 'resolve_mixers' functions must
1 be used.  'instantiate_parameters' is useful when you use the results of
1 SCEV only for some analysis, and when you work with whole nest of loops
1 at once.  It will try replacing all SSA names by their SCEV in all
1 loops, including the super-loops of the current loop, thus providing a
1 complete information about the behavior of the variable in the loop
1 nest.  'resolve_mixers' is useful if you work with only one loop at a
1 time, and if you possibly need to create code based on the value of the
1 induction variable.  It will only resolve the SSA names defined in the
1 current loop, leaving the SSA names defined outside unchanged, even if
1 their evolution in the outer loops is known.
1 
1  The SCEV is a normal tree expression, except for the fact that it may
1 contain several special tree nodes.  One of them is 'SCEV_NOT_KNOWN',
1 used for SSA names whose value cannot be expressed.  The other one is
1 'POLYNOMIAL_CHREC'.  Polynomial chrec has three arguments - base, step
1 and loop (both base and step may contain further polynomial chrecs).
1 Type of the expression and of base and step must be the same.  A
1 variable has evolution 'POLYNOMIAL_CHREC(base, step, loop)' if it is (in
1 the specified loop) equivalent to 'x_1' in the following example
1 
1      while (...)
1        {
1          x_1 = phi (base, x_2);
1          x_2 = x_1 + step;
1        }
1 
1  Note that this includes the language restrictions on the operations.
1 For example, if we compile C code and 'x' has signed type, then the
1 overflow in addition would cause undefined behavior, and we may assume
1 that this does not happen.  Hence, the value with this SCEV cannot
1 overflow (which restricts the number of iterations of such a loop).
1 
1  In many cases, one wants to restrict the attention just to affine
1 induction variables.  In this case, the extra expressive power of SCEV
1 is not useful, and may complicate the optimizations.  In this case,
1 'simple_iv' function may be used to analyze a value - the result is a
1 loop-invariant base and step.
1