This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
PATCH for bogus loop optimization
- To: egcs-patches at cygnus dot com
- Subject: PATCH for bogus loop optimization
- From: Mark Mitchell <mark at markmitchell dot com>
- Date: Thu, 16 Jul 1998 10:35:03 -0700
- Cc: Jeff Law <law at cygnus dot com>
- Reply-to: mark at markmitchell dot com
I've been working on some improvements to loop. In particular, I've
got code that I'll submit soon that puts memory references into
pseudos for the duration of the loop. This makes lots of loops go
faster.
Unfortunately, my "improvements" broke loop-2f. However, the problem
lies not in my code but in code presently in GCC. I've attached a
patch. I believe that this patch should go not only on the mainline
but also on the 1.1 branch.
You can reproduce the problem by changing this test in loop-2f.c
i >= 0 && &p[i] < &p[40]
to
&p[i] < &p[40] && i >= 0
(One of my changes to loop optimization removes the difference between
these two orderings, which is a good thing, and thereby triggered the
bug.)
In particular, lets look at this function:
void g(int n, char*s)
{
int i;
for (i = n; &s[i] < &s[40] && i >= 0; i++)
s[i] = 3;
}
On the x86, the code generated looks like:
g:
pushl %ebp
movl %esp,%ebp
pushl %ebx
movl 12(%ebp),%ebx # EBX = s
movl 8(%ebp),%eax # EAX = n
leal (%eax,%ebx),%ecx # ECX = &s[n]
leal 40(%ebx),%edx # EDX = &s[40]
cmpl %edx,%ecx # if (&s[i] >= &s[40])
jae .L3 # goto L3
testl %eax,%eax # if (n == 0)
jl .L3 # goto L3
movl %ecx,%eax # EAX = &s[i]
.p2align 4,,7
.L5:
movb $3,(%eax) # s[i] = 3
incl %eax # EAX = &s[i+1]
cmpl %edx,%eax # if (&s[i] >= &s[40])
jae .L3 # break;
cmpl %ebx,%eax # if (&s[i] >= (signed!) &s[0])
jge .L5 # continue;
.L3:
Note the signed comparison of the two addresses on the penultimate
line. The patch consists mostly of a large comments explaining what's
going wrong, so I'll omit that here.
Jeff, may I check this in on the mainline and on the 1.1 branch?
--
Mark Mitchell mark@markmitchell.com
Mark Mitchell Consulting http://www.markmitchell.com
Thu Jul 16 10:31:23 1998 Mark Mitchell <mark@markmitchell.com>
* loop.c (maybe_eliminate_biv_1): Avoid signed/unsigned comparison
confusion when setting cc0.
Index: loop.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/loop.c,v
retrieving revision 1.56
diff -c -p -r1.56 loop.c
*** loop.c 1998/06/21 17:33:00 1.56
--- loop.c 1998/07/16 17:19:52
*************** maybe_eliminate_biv_1 (x, insn, bl, elim
*** 6534,6540 ****
return 1;
#ifdef HAVE_cc0
! if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
{
/* Can replace with any giv that was reduced and
that has (MULT_VAL != 0) and (ADD_VAL == 0).
--- 6643,6684 ----
return 1;
#ifdef HAVE_cc0
! /* The idea here is to replace the SET of cc0 by a REG with
! a comparison involving related induction variables.
! Unfortunately, however, such a replacement does not work
! correctly if the REG is being used as signed and the
! replacement value is unsigned, or vice versa. For
! example, in:
!
! for (int i = n; i >= 0; --i)
! s[i] = 3;
!
! `s' is an address (an unsigned quantity), while `i' is a
! signed quantity. The exit test for the loop might look
! something like:
!
! (SET cc0 i)
! (JUMP (SET (PC) (IF_THEN_ELSE (LT (CC0) (CONST_INT 0))
! (LABEL_REF L) (PC))))
!
! If we replace the SET of cc0 with a comparison of the
! induction variable for `s + i' and the original value of `s',
! however, we should be change the comparison in the
! IF_THEN_ELSE to be unsigned. Otherwise, an array the spans
! the boundary between "negative" and "positive" addresses will
! confuse us.
!
! There are related problems with overflow. If an induction
! variable "wraps around" but the original value doest not, we
! can get confused when doing the comparison.
!
! Pointers can't wrap around, or overflow, in a conformant
! program. Therefore, it's safe to do these optimizations if
! both the original REG and the values in the replacement are
! pointers. For now, though, we just disable these
! optimizations. */
!
! if (0 && SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
{
/* Can replace with any giv that was reduced and
that has (MULT_VAL != 0) and (ADD_VAL == 0).