Re: Executing code at compilation time

Fernando Magno Quintao Pereira wrote:
> If
> you allow me a last question, why the loop:
>
> for (; i < 32767; i++) {
> sum += i;
> }
>
> is fully resolved,


The assignment to sum in the first is caught by a power rule and
lifted out of the loop. The form is converted into


int sum = 0;
sum += ((32766 * 32766) + 32766)/2;
      for (; i < 32767; i++) {
      }


constant folding converts that into


int sum = 0;
sum += 53821761;
      for (; i < 32767; i++) {
      }


dead code elimination removes the loop because nothing now happens
in it, so you get:


int sum = 0;
sum += 53821761;


Then flow analysis notices nothing depends on the value of sum between
the initialization and the addition and folds the (constant) addition
into the initialization and combines them;


int sum = 53821761;


And that's about as far as that can be resolved given that you're printing
the value of sum after the "loop."


Note that if you weren't printing the value of sum, nothing would depend
on the variable or the initialization, so even that would probably be
removed.


> whereas:
>
> for (; i < 32767; i++) {
> sum -= i; // see the minus
> }
>
> is not?


gcc (at least at -O1) applies this summation rule with factor
+1 but doesn't notice the same rule with a factor -1.


Loop unrolling which can resolve shorter iterations doesn't
try to unroll something 32767 iterations long. And with no
summation rule having lifted the addition out of the loop, the
loop itself can't be eliminated because the addition still
depends on it.


Maybe gcc at -O2 or higher looks for factors other than +1
to use with its summation rules. If not, it might be a good
addition for a future version. But factor +1 is common relative
to all other factors, so even if they implement more general
rules, it's not surprising to see the factor +1 being the
only one they look for at the lower optimization levels.


If you're interested in the set of summation identities
useful for lifting iterative addends of various functions
out of loops, most of them can be found at
http://en.wikipedia.org/wiki/Summation in the section
"Identities."


Programmers tend to be pretty empirical, and mostly think
nothing of using loops to calculate something like your sum
above when they don't know the closed forms for it (or, sadly,
even when they do know the closed form but fear someone else
won't be able to understand what their code did and why). So
if it recognizes and optimizes these calculation patterns (and
compositions and multiples of them) the compiler can do quite
a lot of numerical heavy lifting, reducing runtime in some
problems by orders of magnitude, and reducing the number of
operations that can introduce roundoff errors in some problems
by the same amount.


                                                                Bear

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