Re: Executing code at compilation time

Fernando <pronesto@gmail.com> writes:


> GCC does a pretty good job at optimizing a program like this one
> below:
>
> 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?


I suspect it is a combination of loop unrolling and constant folding: If
the loop is completely unrolled, constant folding can eliminate all
calculations and reduce the program to one that just prints the answer.


> Additionally, GCC does not resolve the loop in the program below:
>
> 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.


I suspect GCC has a limit on the size of loops it will unroll. In the
first program, the loop is only 10 iterations, which apparently is below
the limit, but 1000 iterations is apparently over the limit. If the
loop is not unrolled, constant folding does not apply, so the only
optimisation likely to happen is moving loop invariant computations
outside the loop:




  int main(int argc, char **argv) {
      int i, i2, j, j2, k, t = 0;
      for(i = 0; i < 1000; i++) {
          i2 = i*i;
          for(j = 0; j < 1000; j++) {
              j2 = i2+j*j;
              for(k = 0; k < 1000; k++)
                  if(j2 + k * k % 7 == 0)
                      t++;
          }
      }
      printf("%d\n", t);
      return 0;
  }


> Is there any sort of non- standard optimization that does the job, in
> this case?


Aggressive compile-time calculation can be done by partial evaluation
(http://www.itu.dk/people/sestoft/pebook/).


A partial evaluator for C is C-mix, which you can get at
(http://diku.dk/Forskning/toppsredir/?obvius_proxy_url=http%3A%2F%2Fwww.diku.dk%2FOLD%2Fforskning%2Ftopps%2Factivities%2Fcmix%2F).
It can require a bit of work to get optimal results with C-mix, but when
you do, the results can be quite impressive.


Torben

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