This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

PATCH for bogus loop optimization



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).


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]