Re: Executing code at compilation time

Hi Fernando,


On 16/03/2010, at 12:53 PM, 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?


The optimisation you're looking for (or rather, a whole family of
optimisations) is "partial evaluation". In a nutshell, partial
evaluation identifies precisely those bits of your program which
depend only on static data known to the compiler and evaluate them at
the time of translation, in the manner you've observed above. In your
examples, this is easy, but there's many, many more interesting
applications of partial evaluation. Perhaps the most famous is
Futamura's attempt [1] to define an entire compiler by applying
partial evaluation to an invocation of an interpreter for the source
language (see bottom of email for references.)


You can find a good introduction to partial evaluation in Consel and
Danvy [2]. There's also plenty of books written on the topic, but I
haven't read any of them so I'll leave it between you and google to
sort out the details.


Having said all that, to the best of my knowledge, neither GCC nor any
other C compiler out there implements a true partial evaluator. The
optimisation is most readily applicable to functional languages
although it's been recently applied to imperative scenarios such as C,
too (see [2] for more pointers.) Instead, the effect you've observed
was probably caused by some other optimisation getting rid of the loop
(most likely loop unrolling, but certain forms of strength reduction
could also do the trick here), then constant folding reducing the
resulting basic block into a single assignment "sum := 45", after
which constant propagation (Wegman and Zadeck [3]) can easily complete
the process. This is why your second example could not be optimised:
it was simply to big to unroll in the first place!


Another issue to bear in mind is that, contrary to folklore knowledge,
partial evaluation does not always improve the generated code. In
certain settings, an aggressive form of partial evaluation can
specialise the program to the point where other optimisations (notably
common expression elimination) cannot operate efficiently, resulting
in a net degradation of the ultimate compiler output. Because it
generally specialises procedures for different constant input values,
if you attempt to indiscriminately evaluate everything that can be
evaluated at the time of compilation, you may also easily end up
increasing your program's size to the point when caching kills any
performance benefits you've gained, since doing a bunch of simple
operations such as sums is almost certainly cheaper than loading even
one or two extra words from uncached memory! This is why, oh so often,
gcc -O3 can give you a program that runs twice as slow as gcc -O1.


Finally, you must also remain vigilant to the possibility that
evaluating your "constant-input" loops could lead to exponential-time
compilation, or even non-terminating compilation if the loop itself
does not terminate.


And, last but not least, you should remember that it's easy to apply
partial evaluation aggressively to a point where it increases the very
algorithmic complexity of the program, i.e., makes a linear program
run in exponential time. For example, if you're not careful,
partially-evaluating a statement such as "x = foo(); sum = x + x", can
result in two copies of partially-evaluated calls to "foo" in your
program, which, if either "foo" itself or the surrounding procedure is
recursive (or appears in a loop), will lead to an exponential run time
in the ultimate executable.


Hope that helps,


Patryk Zadarnowski.




[1] Futamura, Yoshihiko, "Partial evaluation of computation process 
an approach to a compiler-compiler" in Systems, Computers, Controls
2(5), pages 4550, 1971; also in Higher-Order and Symbolic Computation
12(4), pages 381391, 1999"


[2] Consel, Charles and Danvy, Olivier, "Tutorial notes on partial
evaluation" in POPL '93: Proceedings of the Twentieth Annual ACM
Symposium on Principles of Programming Languages, pages 493501, 1993.


[3] Wegman, Mark N. and Zadeck, Frank Kenneth, "Constant propagation
with conditional branches",
in POPL '85: Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on
Principles of programming languages, pages 291-299, 1985.

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