Re: Loop unrolling

[Scott A Crosby <crosby at qwes dot math dot cmu dot edu>]

On Fri, 18 Sep 1998, Joern Rennecke wrote:

> > 2) Determining whether a loop is empty or not needs some kind of
> >    register lifetime information.  Last I looked, this was not
> >    reliable at the time of loop unrolling.  If this is no longer true,
> >    then I can resurrect some code to do this.
> 
> As long as the end value o the loop counter can be calculated, this is
> no problem.
> 

There are cases where a loop may be not empty or the iteration count
isn't known at compile time. 

You can have multiply-nested loops where the innermost one is empty, and
the others just wrap around around another loop who's final effect is
do-nothing. For example, case 'x2' below. (Does this happen with >1d
arrays of objects with do-nothing constructors, or constructors that are
proven to do nothing?)

I am not good at reading assembly code on x86, so I can't tell if/when
this happens, but there are several different cases of empty loops that
can/should be eliminated. What code is generated for the 7 constructions
below?

I have a feeling that the multidimensional case causes nested empty loops,
given that the compiler produces empty loops for the 1d case. Actually,
removing the latter 4 loops may be a much bigger win than the first 3 in
many templated instances. For loops that you can prove will terminate, you
don't necessarily have to know the end-value of the loop at compile time,
you just need to know that it is constant throughout the lifetime of the
loop.

class A { 
   int i ; 
public:
   A() {};
}


foo ( int a, int b, int c) {
   // These should only reserve a static amount of 
   //   space on the stack frame, and do nothing else. (no looping)
   A x1 [10];
   A x2 [10][10];
   A x3 [10][10][10];

   // These should only calculate and reserve a static amount of space 
   //   on the stack frame, and do nothing else. (no looping)
   A y1 [a];
   A y2 [a][10];
   A y3 [a][b];
   A y4 [a][10][b][10][c];

}

Scott



--
This sig is the answer to the ultimate question of life, the universe, and
everything else.