optimization/10520: induction variable analysis not used to eliminate comparisons

optimization/10520: induction variable analysis not used to eliminate comparisons

[bsamwel]

>Number:         10520
>Category:       optimization
>Synopsis:       induction variable analysis not used to eliminate comparisons
>Confidential:   no
>Severity:       non-critical
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          pessimizes-code
>Submitter-Id:   net
>Arrival-Date:   Mon Apr 28 13:06:01 UTC 2003
>Closed-Date:
>Last-Modified:
>Originator:     Bart Samwel
>Release:        gcc-3.2.3
>Organization:
>Environment:
Debian unstable as of 28/04/03
>Description:
When I compile the following loop (please don't mind the excess of casts etcetera - this is generated code):

unsigned int _tmp0= /* ... */;

int* buf_fast= /* ... */;

unsigned int n_in=0;
unsigned int n_out=0;
unsigned int n_in1=1;
unsigned int n_out1=1;
for(0;((n_in < _tmp0  && n_out < _tmp0) && n_in1 < _tmp0) && n_out1 < _tmp0;(((((n_in +=4,n_out +=2)),n_in1 +=4)),n_out1 +=2)){
  buf_fast[(int)n_out]=buf_fast[(int)n_in];
  buf_fast[(int)n_out1]=buf_fast[(int)n_in1];
}

The assembler output for arch=pentium4 is:

.L27:
	movl	-72(%ebp), %eax
	movl	(%edi,%eax,4), %eax
	movl	%eax, (%edi,%ecx,4)
	movl	(%edi,%esi,4), %eax
	addl	$4, -72(%ebp)
	movl	%eax, (%edi,%edx,4)
	addl	$2, %ecx
	addl	$4, %esi
	addl	$2, %edx
	cmpl	%ebx, -72(%ebp)
	jae	.L23
	cmpl	%ebx, %ecx
	jae	.L23
	cmpl	%ebx, %esi
	jae	.L23
	cmpl	%ebx, %edx
	jb	.L27

This loop contains a LOT of compares, which means that GCC doesn't induce that during the loop, the following things hold (with n = the iteration number):

n_in = 0 + 4 * n
n_in1 = 1 + 4 * n
n_out = 0 + 2 * n
n_out1 = 1 + 4 * n

and therefore:

n_in < n_in1
n_out <= n_in
n_out1 <= n_in1

Because of these relations, it would be possible for GCC to induce that if n_in1 <  _tmp0, then also n_in < _tmp0, n_out < _tmp0 and n_out1 < _tmp0. However, GCC doesn't seem to see the relationships between the variables.

Oh, before you ask: no, I can't remove the unnecessary loop conditions. :( These are part of the compiled Cyclone code and are required by the Cyclone compiler so that it can optimize away the bounds checks on the array accesses. Optimizing away these inefficiencies is a back-end job, which is why I'm reporting this to GCC.
>How-To-Repeat:

>Fix:

>Release-Note:
>Audit-Trail:
>Unformatted: