Re: Executing code at compilation time

Dear Fernando,


On 17/03/2010, at 11:37 AM, Fernando Magno Quintao Pereira wrote:


> If you allow me a last question, why the loop:


>
> for (; i < 32767; i++) {
> sum += i;
> }
>
> fully resolved, whereas:
>
> for (; i < 32767; i++) {
> sum -= i; // see the minus
> }
>
> is not?


This one's easy. As you're rightly observed, constant folding and
propagation alone is not able to optimise either of these loops, since
it only deals with individual variables that retain the same value
across all possible execution path, and none of the variables in the
above code ("i" and "sum") have the property (in particular, both
"sum" and "i" will assume 32767 different values through the execution
of the loop!)


However, if you decrease the limit sufficiently (say 10 rather than
32767), both loops will get fully unrolled into 10 individual
assignments. Under the SSA representation of the program [1], this
basically means that both "sum" and "i" get replaced by 10 different
variables: sum0, sum1 ... sum9 and i0, i1 .. i9. Each of these
variables will, individually, retain a constant value through
execution, so the whole program can be folded and propagated away.


Alternatively, if a compiler is smart enough, then it may notice that
a simple loop such as the one above is simply a sum of an arithmetic
series and replace it by a standard textbook formula that computes
that sum in constant time, so that, once again, constant propagation
can take care of the rest. This optimisation is known as "strength
reduction". Most textbooks on program optimisations have a chapter on
strength reduction, but you can also check out the work of Wolfe et
al. [2, 3] for interesting and powerful applications of this
technique.


One problem with strength reduction is that you can only ever make
it so smart, since it requires the compiler to be equipped with a
whole pile of mathematical identities. Including more identities
will result in a more powerful optimiser, but also in longer
compilation times, so that, at some point, the compiler writer
must make a judgement call and decide when to stop, and which
identities are of most value to "typical" input programs. From
your investigation, it seems that GCC authors simply didn't make
their strength reduction algorithm smart enough to notice the
pattern in the second example, which is probably fair enough
since the first example is far, far more common in practice
and likely to result in more interesting programs getting
optimised.


Cheers,
Patryk.


[1] Cytron, Ron and Ferrante, Jeanne and Rosen, Barry K. and
Wegman, Mark N. and Zadeck, F. Kenneth, "Efficiently computing
static single assignment form and the control dependence graph",
in ACM Transactions on Programming Languages and Systems (TOPLAS)
13(4), pages 451-490, 1991.


[2] Wolfe, Michael, "Beyond induction variables", in PLDI '92:
Proceedings of the ACM SIGPLAN 1992 conference on Programming
language design and implementation, pages 162-174, 1992.


[3] Gerlek, Michael P. and Stoltz, Eric and Wolfe, Michael,
"Beyond induction variables: detecting and classifying sequences
using a demand-driven SSA form" in ACM Transactions on Programming
Languages and Systems (TOPLAS), 17(1), pages 85-122, 1995.

Return to the comp.compilers page.
Search the comp.compilers archives again.