gcc/doc/gccint/analysis-and-representation-of-loops/scalar-evolutions.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:: Scalar evolutions, IV analysis on GIMPLE
   7
   8 .. _scalar-evolutions:
   9
  10 Scalar evolutions
  11 *****************
  12
  13 Scalar evolutions (SCEV) are used to represent results of induction
  14 variable analysis on GIMPLE.  They enable us to represent variables with
  15 complicated behavior in a simple and consistent way (we only use it to
  16 express values of polynomial induction variables, but it is possible to
  17 extend it).  The interfaces to SCEV analysis are declared in
  18 :samp:`tree-scalar-evolution.h`.  To use scalar evolutions analysis,
  19 ``scev_initialize`` must be used.  To stop using SCEV,
  20 ``scev_finalize`` should be used.  SCEV analysis caches results in
  21 order to save time and memory.  This cache however is made invalid by
  22 most of the loop transformations, including removal of code.  If such a
  23 transformation is performed, ``scev_reset`` must be called to clean
  24 the caches.
  25
  26 Given an SSA name, its behavior in loops can be analyzed using the
  27 ``analyze_scalar_evolution`` function.  The returned SCEV however
  28 does not have to be fully analyzed and it may contain references to
  29 other SSA names defined in the loop.  To resolve these (potentially
  30 recursive) references, ``instantiate_parameters`` or
  31 ``resolve_mixers`` functions must be used.
  32 ``instantiate_parameters`` is useful when you use the results of SCEV
  33 only for some analysis, and when you work with whole nest of loops at
  34 once.  It will try replacing all SSA names by their SCEV in all loops,
  35 including the super-loops of the current loop, thus providing a complete
  36 information about the behavior of the variable in the loop nest.
  37 ``resolve_mixers`` is useful if you work with only one loop at a
  38 time, and if you possibly need to create code based on the value of the
  39 induction variable.  It will only resolve the SSA names defined in the
  40 current loop, leaving the SSA names defined outside unchanged, even if
  41 their evolution in the outer loops is known.
  42
  43 The SCEV is a normal tree expression, except for the fact that it may
  44 contain several special tree nodes.  One of them is
  45 ``SCEV_NOT_KNOWN``, used for SSA names whose value cannot be
  46 expressed.  The other one is ``POLYNOMIAL_CHREC``.  Polynomial chrec
  47 has three arguments -- base, step and loop (both base and step may
  48 contain further polynomial chrecs).  Type of the expression and of base
  49 and step must be the same.  A variable has evolution
  50 ``POLYNOMIAL_CHREC(base, step, loop)`` if it is (in the specified
  51 loop) equivalent to ``x_1`` in the following example
  52
  53 .. code-block:: c++
  54
  55   while (...)
  56     {
  57       x_1 = phi (base, x_2);
  58       x_2 = x_1 + step;
  59     }
  60
  61 Note that this includes the language restrictions on the operations.
  62 For example, if we compile C code and ``x`` has signed type, then the
  63 overflow in addition would cause undefined behavior, and we may assume
  64 that this does not happen.  Hence, the value with this SCEV cannot
  65 overflow (which restricts the number of iterations of such a loop).
  66
  67 In many cases, one wants to restrict the attention just to affine
  68 induction variables.  In this case, the extra expressive power of SCEV
  69 is not useful, and may complicate the optimizations.  In this case,
  70 ``simple_iv`` function may be used to analyze a value -- the result
  71 is a loop-invariant base and step.