]>
Commit | Line | Data |
---|---|---|
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. |