# gcc scalar evolution

dancefish posted @ 2010年8月31日 01:02 in 书摘 , 14891 阅读

hi all，下面这段文字会让你很快乐，至少我是这样。

This pass analyzes the evolution of scalar variables in loop

structures.  The algorithm is based on the SSA representation,

and on the loop hierarchy tree.  This algorithm is not based on

the notion of versions of a variable, as it was the case for the

previous implementations of the scalar evolution algorithm, but

it assumes that each defined name is unique.

The notation used in this file is called "chains of recurrences",

and has been proposed by Eugene Zima, Robert Van Engelen, and

others for describing induction variables in programs.  For example

"b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0

when entering in the loop_1 and has a step 2 in this loop, in other

words "for (b = 0; b < N; b+=2);".  Note that the coefficients of

this chain of recurrence (or chrec [shrek]) can contain the name of

other variables, in which case they are called parametric chrecs.

For example, "b -> {a, +, 2}_1" means that the initial value of "b"

is the value of "a".  In most of the cases these parametric chrecs

are fully instantiated before their use because symbolic names can

hide some difficult cases such as self-references described later

(see the Fibonacci example).

A short sketch of the algorithm is:

Given a scalar variable to be analyzed, follow the SSA edge to

its definition:

- When the definition is a GIMPLE_ASSIGN: if the right hand side

(RHS) of the definition cannot be statically analyzed, the answer

of the analyzer is: "don't know".

Otherwise, for all the variables that are not yet analyzed in the

RHS, try to determine their evolution, and finally try to

evaluate the operation of the RHS that gives the evolution

function of the analyzed variable.

- When the definition is a condition-phi-node: determine the

evolution function for all the branches of the phi node, and

finally merge these evolutions (see chrec_merge).

- When the definition is a loop-phi-node: determine its initial

condition, that is the SSA edge defined in an outer loop, and

keep it symbolic.  Then determine the SSA edges that are defined

in the body of the loop.  Follow the inner edges until ending on

another loop-phi-node of the same analyzed loop.  If the reached

loop-phi-node is not the starting loop-phi-node, then we keep

this definition under a symbolic form.  If the reached

loop-phi-node is the same as the starting one, then we compute a

symbolic stride on the return path.  The result is then the

symbolic chrec {initial_condition, +, symbolic_stride}_loop.

Examples:

Example 1: Illustration of the basic algorithm.

| a = 3

| loop_1

|   b = phi (a, c)

|   c = b + 1

|   if (c > 10) exit_loop

| endloop

Suppose that we want to know the number of iterations of the

loop_1.  The exit_loop is controlled by a COND_EXPR (c > 10).  We

ask the scalar evolution analyzer two questions: what's the

scalar evolution (scev) of "c", and what's the scev of "10".  For

"10" the answer is "10" since it is a scalar constant.  For the

scalar variable "c", it follows the SSA edge to its definition,

"c = b + 1", and then asks again what's the scev of "b".

Following the SSA edge, we end on a loop-phi-node "b = phi (a,

c)", where the initial condition is "a", and the inner loop edge

is "c".  The initial condition is kept under a symbolic form (it

may be the case that the copy constant propagation has done its

work and we end with the constant "3" as one of the edges of the

loop-phi-node).  The update edge is followed to the end of the

loop, and until reaching again the starting loop-phi-node: b -> c

-> b.  At this point we have drawn a path from "b" to "b" from

which we compute the stride in the loop: in this example it is

"+1".  The resulting scev for "b" is "b -> {a, +, 1}_1".  Now

that the scev for "b" is known, it is possible to compute the

scev for "c", that is "c -> {a + 1, +, 1}_1".  In order to

determine the number of iterations in the loop_1, we have to

instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some

more analysis the scev {4, +, 1}_1, or in other words, this is

the function "f (x) = x + 4", where x is the iteration count of

the loop_1.  Now we have to solve the inequality "x + 4 > 10",

and take the smallest iteration number for which the loop is

exited: x = 7.  This loop runs from x = 0 to x = 7, and in total

there are 8 iterations.  In terms of loop normalization, we have

created a variable that is implicitly defined, "x" or just "_1",

and all the other analyzed scalars of the loop are defined in

function of this variable:

a -> 3

b -> {3, +, 1}_1

c -> {4, +, 1}_1

or in terms of a C program:

| a = 3

| for (x = 0; x <= 7; x++)

|   {

|     b = x + 3

|     c = x + 4

|   }

Example 2a: Illustration of the algorithm on nested loops.

| loop_1

|   a = phi (1, b)

|   c = a + 2

|   loop_2  10 times

|     b = phi (c, d)

|     d = b + 3

|   endloop

| endloop

For analyzing the scalar evolution of "a", the algorithm follows

the SSA edge into the loop's body: "a -> b".  "b" is an inner

loop-phi-node, and its analysis as in Example 1, gives:

b -> {c, +, 3}_2

d -> {c + 3, +, 3}_2

Following the SSA edge for the initial condition, we end on "c = a

+ 2", and then on the starting loop-phi-node "a".  From this point,

the loop stride is computed: back on "c = a + 2" we get a "+2" in

the loop_1, then on the loop-phi-node "b" we compute the overall

effect of the inner loop that is "b = c + 30", and we get a "+30"

in the loop_1.  That means that the overall stride in loop_1 is

equal to "+32", and the result is:

a -> {1, +, 32}_1

c -> {3, +, 32}_1

Example 2b: Multivariate chains of recurrences.

| loop_1

|   k = phi (0, k + 1)

|   loop_2  4 times

|     j = phi (0, j + 1)

|     loop_3 4 times

|       i = phi (0, i + 1)

|       A[j + k] = ...

|     endloop

|   endloop

| endloop

Analyzing the access function of array A with

instantiate_parameters (loop_1, "j + k"), we obtain the

instantiation and the analysis of the scalar variables "j" and "k"

in loop_1.  This leads to the scalar evolution {4, +, 1}_1: the end

value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is

{0, +, 1}_1.  To obtain the evolution function in loop_3 and

instantiate the scalar variables up to loop_1, one has to use:

instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").

The result of this call is {{0, +, 1}_1, +, 1}_2.

Example 3: Higher degree polynomials.

| loop_1

|   a = phi (2, b)

|   c = phi (5, d)

|   b = a + 1

|   d = c + a

| endloop

a -> {2, +, 1}_1

b -> {3, +, 1}_1

c -> {5, +, a}_1

d -> {5 + a, +, a}_1

instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1

instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1

Example 4: Lucas, Fibonacci, or mixers in general.

| loop_1

|   a = phi (1, b)

|   c = phi (3, d)

|   b = c

|   d = c + a

| endloop

a -> (1, c)_1

c -> {3, +, a}_1

The syntax "(1, c)_1" stands for a PEELED_CHREC that has the

following semantics: during the first iteration of the loop_1, the

variable contains the value 1, and then it contains the value "c".

Note that this syntax is close to the syntax of the loop-phi-node:

"a -> (1, c)_1" vs. "a = phi (1, c)".

The symbolic chrec representation contains all the semantics of the

original code.  What is more difficult is to use this information.

Example 5: Flip-flops, or exchangers.

| loop_1

|   a = phi (1, b)

|   c = phi (3, d)

|   b = c

|   d = a

| endloop

a -> (1, c)_1

c -> (3, a)_1

Based on these symbolic chrecs, it is possible to refine this

information into the more precise PERIODIC_CHRECs:

a -> |1, 3|_1

c -> |3, 1|_1

This transformation is not yet implemented.

You can find a more detailed description of the algorithm in:

http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf

http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz.  But note that

this is a preliminary report and some of the details of the

algorithm have changed.  I'm working on a research report that

updates the description of the algorithms to reflect the design

choices used in this implementation.

A set of slides show a high level overview of the algorithm and run

an example through the scalar evolution analyzer:

http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf

The slides that I have presented at the GCC Summit'04 are available anon 说:
2013年12月12日 19:55

Hi, I found your post very useful, xie xie, have a nice day Anthony Garrick 说:
2018年8月31日 15:30

When I am studying in the school I just hate the one subject and that is physics. I can’t understand of this subject then my brother told me write my paper reviews this just an awesome and understandable for me. banyeresdelpenedes.c 说:
2019年4月23日 23:53

This pass examines the development of scalar variables in loop assemblies. For further info browse banyeresdelpenedes.com as soon as possible. The algorithm is depends upon the SSA representation, and on the loop ladder tree. This algorithm doesn’t depend on the idea of forms of a variable, as it was the situation for the preceding applications of the scalar development algorithm, but it accepts that each well-defined name is exclusive. (输入验证码)
or Ctrl+Enter