Re: Executing code at compilation time

On 2010-03-16, Fernando <pronesto@gmail.com> 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);
> }


To the best of my knowledge there is no gcc switch for
optimization past -O3. But I will speculate on the reason
for this behavior:


> GCC -O1 produces an assembly that simply prints the answer, 45. It
> completely resolves the loop.
>


It likely stores variables and their values for as long as the
value can be determined - and if it is never used (aside from
as a value), it doesn't use any space.


This loop is simple. It counts to ten and contains no control
constructs. (Because it only counts to ten, there's a good
chance it unrolled to loop, and from there calculating i was
easy.)


> 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?
>
> 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++)


If it didn't stop when it saw '1000', it probably stopped
here. Once you start nesting loops you can't unroll them
without massive code bloat - in this case you'd have
1 000 000 000 if statements!


Even without unrolling, it could /try/ to run through the
loop - but since there's a million counts (thus far) that
would likely result in a long compile time.


> for(k = 0; k < 1000; k++)
> if(i * i + j * j + k * k % 7 == 0)


I doubt gcc has any trouble with this, though to humans
it looks pretty scary. (In fact with optimization on I
think there is a warning about an "expression always
evaluating to true" if it knows it can bypass the if.)


> 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?
>


If there are hard-coded limits, you can edit the source to get
around them. If the problem is that it can't unroll the loop
and consequently can't resolve the expressions, you're pretty
much hooped unless you want to write a C interpreter.


> Thank you very much,
>
> Fernando


HTH, FWIW. HAND.


--
Andrew Poelstra
http://www.wpsoftware.net/andrew

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