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