Re: Executing code at compilation time

Fernando wrote:


> GCC does a pretty good job at optimizing a program like this one
> below:
>
> #include <stdio.h>
>
> int main(int argc, char** argv) {
> int i = 0;
> int sum = 0;
> for (; i < 10; i++) {
> sum += i;
> }
> printf("The sum is %d\n", sum);
> }
>
> GCC -O1 produces an assembly that simply prints the answer, 45. It
> completely resolves the loop.
>
> I would like to know what kind of optimizations are used to be able to
> completely resolve the loop. Could you give me some source? E.g,
> chapter in textbook, or paper?


Basic algebra gives us several power rules, including
(Sigma i : i=0,n) = (n^2 - n)/2, or in English,


"If n is a natural number, then when you subtract n from its
square and divide the difference by two, you get the sum of all
natural numbers less than n."


The for loop above gives us i taking on all positive integer values
less than ten. The sum is going to be (100 - 10)/2 = 45. The assignment
of sum to 45 can be lifted out of the loop, and someone on the gcc
team has noticed the common pattern and implemented the corresponding
optimization. Once that's done, the loop body is empty, and empty
loops can be eliminated in a separate optimization as dead code.


> Additionally, GCC does not resolve the loop in the program below:
>
> #include <stdio.h>
>
> int main(int argc, char **argv) {
> int i, j, k, t = 0;
> for(i = 0; i < 1000; i++)
> for(j = 0; j < 1000; j++)
> for(k = 0; k < 1000; k++)
> if(i * i + j * j + k * k % 7 == 0)
> t++;
> printf("%d\n", t);
> return 0;
> }
>
> But it is "solvable" at compilation time. Is there any sort of non-
> standard optimization that does the job, in this case?


This isn't a common pattern, so just implementing (or even
composing) those standard algebraic identities and power rules
out of the back of your highschool algebra book won't provide a
closed form for it. What you can do that would catch this (and
within limits many compilers including gcc do this) is partial
evaluation.


Partial evaluation means that the compiler executes the code, insofar
as it can, at compile time. In this case where the result depends
on nothing but constants, that can turn into complete evaluation.


The Problem (and I used that capital P on purpose) with partial
evaluation is The Halting Problem. You'd like to guarantee that
your compiler will produce reasonably timely results, and that
puts you in the position of needing to prove that your partial
evaluation will halt. While you can do that in some particular
cases, there is not, and can never be, a general solution.


In practice, partial evaluation has to be limited to some finite
amount of compute time or interpreter steps, and if that limit
is exceeded the compiler or interpreter gives up. It is not at
all surprising that gcc gives up before it gets a billion
iterations through the inner loop above.


                                                                Bear

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