Re-run of loop pass

[Michael Hayes]

Toon Moene writes:
 > I do not completely understand this remark.  The sequence is:
 > 
 > first-pass-through-loop; second-pass-through-loop;  
 > pass-through-unroll; bct-optimisations.
 > 
 > How can the elimination of a BIV be so important then ?  It can  
 > either happen in the first or the second pass through loop, but that  
 > shouldn't matter.

 > Do you have an example of this at hand ?  I fail to see how this  
 > could be happening.

OK, here's a simple example

void fcopy1(float *a, float *b)
{
    int i;
    
    for (i = 0; i < 4; i++)
	a[i] = b[i];
}

The loop on the first pass gets converted to

 for (p = a, q = b, r = a + 4; p < r; )
    *p++ = *q++;

The second pass then gives up trying to calculate the number of loop
iterations since the initial value of p is not a constant.  Now some
algebra could be applied to determine the number of loop iterations
but this would involve tracking register values. 

While it would be desirable to directly determine the number of loop
iterations of such a modified loop, the easiest solution might be to
cache the iteration counts computed on the first pass.

As I mentioned previously, the problem appears with machine having
autoincrement addressing modes.  For example, compiling for the m68k
generates (gcc -O2 -funroll-loops):


	.file	"fcopy1.c"
	.version	"01.01"
gcc2_compiled.:
.text
	.align 	2
.globl fcopy1
	.type	 fcopy1,@function
fcopy1:
	link.w %a6,#0
	movm.l #0x3030,-(%sp)
	move.l 8(%a6),%a2
	move.l 12(%a6),%a3
	moveq.l #12,%d2
	add.l %a2,%d2
	moveq.l #13,%d0
	add.l %a2,%d0
	moveq.l #13,%d1
	cmp.l %a2,%d0
	jble .L9
	tst.l %d1
	jbeq .L5
	moveq.l #4,%d3
	cmp.l %d1,%d3
	jbge .L9
	moveq.l #8,%d3
	cmp.l %d1,%d3
	jbge .L10
	cmp.l %d1,%d1
	jble .L5
	move.l (%a3)+,(%a2)+
.L10:
	move.l (%a3)+,(%a2)+
.L9:
	move.l (%a3)+,(%a2)+
	cmp.l %a2,%d2
	jblt .L7
	.align 	2
.L5:
	move.l %a2,%a1
	move.l %a3,%a0
	move.l (%a0)+,(%a1)+
	move.l (%a0),(%a1)
	move.l 8(%a3),8(%a2)
	move.l 12(%a3),12(%a2)
	lea (16,%a3),%a3
	lea (16,%a2),%a2
	cmp.l %a2,%d2
	jbge .L5
.L7:
	movm.l (%sp)+,#0xc0c
	unlk %a6
	rts
.Lfe1:
	.size	 fcopy1,.Lfe1-fcopy1
	.ident	"GCC: (GNU) egcs-2.92.15 19981018 (gcc2 ss-980609 experimental)"