Re: Executing code at compilation time

torbenm@diku.dk (Torben Ęgidius Mogensen)
Tue, 16 Mar 2010 11:25:21 +0100

          From comp.compilers

Related articles
Executing code at compilation time pronesto@gmail.com (Fernando) (2010-03-15)
Re: Executing code at compilation time gah@ugcs.caltech.edu (glen herrmannsfeldt) (2010-03-16)
Re: Executing code at compilation time torbenm@diku.dk (2010-03-16)
Re: Executing code at compilation time dnovillo@acm.org (Diego Novillo) (2010-03-16)
Re: Executing code at compilation time bartc@freeuk.com (Bartc) (2010-03-16)
Re: Executing code at compilation time quinn_jackson2004@yahoo.ca (Quinn Tyler Jackson) (2010-03-16)
Re: Executing code at compilation time apoelstra@localhost.localdomain (Andrew Poelstra) (2010-03-16)
Re: Executing code at compilation time bear@sonic.net (Ray) (2010-03-16)
Re: Executing code at compilation time pat@jantar.org (Patryk Zadarnowski) (2010-03-17)
[11 later articles]
| List of all articles for this month |

From: torbenm@diku.dk (Torben Ęgidius Mogensen)
Newsgroups: comp.compilers
Date: Tue, 16 Mar 2010 11:25:21 +0100
Organization: UNI-C
References: 10-03-038
Keywords: optimize
Posted-Date: 16 Mar 2010 23:34:47 EDT

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



Post a followup to this message

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