Bug 20126 - [3.4 Regression] Inlined memcmp makes one argument null on entry
Summary: [3.4 Regression] Inlined memcmp makes one argument null on entry
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: target (show other bugs)
Version: 4.0.0
: P2 normal
Target Milestone: 3.4.6
Assignee: Alexandre Oliva
URL:
Keywords: wrong-code
Depends on: 22425
Blocks: 22239
  Show dependency treegraph
 
Reported: 2005-02-21 21:44 UTC by Javier Kohen
Modified: 2006-02-20 18:37 UTC (History)
6 users (show)

See Also:
Host: x86_64-linux
Target: x86_64-linux
Build: x86_64-linux
Known to work: 3.2.3
Known to fail: 3.3.3 3.4.0
Last reconfirmed: 2006-01-07 01:53:16


Attachments
The program that causes the failure (5.12 KB, application/octet-stream)
2005-02-21 21:47 UTC, Javier Kohen
Details
A slightly modified version that does work. (5.10 KB, application/octet-stream)
2005-02-21 21:48 UTC, Javier Kohen
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Javier Kohen 2005-02-21 21:44:34 UTC
Hi, I found out a compiler bug triggered by compiling Python 2.3 with GCC 4.0
"pre5." I've been able to track it down to a small fragment which I'll attach
below. The bug is a regression as GCC 3.4.4 20050203 produces a working application.

This is the compiler's output and compilation command-line:
Using built-in specs.
Configured with: ../src/configure -v --enable-languages=c,c++,java,f95,objc,ada
--prefix=/usr --libexecdir=/usr/lib --enable-shared --with-system-zlib
--enable-nls --enable-threads=posix --without-included-gettext
--program-suffix=-4.0 --enable-__cxa_atexit --enable-libstdcxx-allocator=mt
--enable-clocale=gnu --enable-libstdcxx-debug --enable-java-gc=boehm
--enable-java-awt=gtk --enable-mpfr x86_64-linux
Thread model: posix
gcc version 4.0.0 20050125 (experimental) (Debian 4.0-0pre5.0.0.1.gcc4)
 /usr/lib/gcc/x86_64-linux/4.0.0/cc1 -E -quiet -v ptest.c -mtune=k8 -Wall
-Wstrict-prototypes -O3 -fpch-preprocess -o ptest.i
ignoring nonexistent directory
"/usr/lib/gcc/x86_64-linux/4.0.0/../../../../x86_64-linux/include"
#include "..." search starts here:
#include <...> search starts here:
 /usr/local/include
 /usr/lib/gcc/x86_64-linux/4.0.0/include
 /usr/include
End of search list.
 /usr/lib/gcc/x86_64-linux/4.0.0/cc1 -fpreprocessed ptest.i -quiet -dumpbase
ptest.c -mtune=k8 -auxbase ptest -O3 -Wall -Wstrict-prototypes -version -o ptest.s
GNU C version 4.0.0 20050125 (experimental) (Debian 4.0-0pre5.0.0.1.gcc4)
(x86_64-linux)
        compiled by GNU C version 4.0.0 20050125 (experimental) (Debian
4.0-0pre5.0.0.1.gcc4).
GGC heuristics: --param ggc-min-expand=30 --param ggc-min-heapsize=4096
 as -V -Qy --64 -o ptest.o ptest.s
GNU ensamblador versión 2.15 (x86_64-linux) utilizando BFD versión 2.15
 /usr/lib/gcc/x86_64-linux/4.0.0/collect2 --eh-frame-hdr -m elf_x86_64
-dynamic-linker /lib/ld-linux-x86-64.so.2 -o ptest
/usr/lib/gcc/x86_64-linux/4.0.0/../../../../lib64/crt1.o
/usr/lib/gcc/x86_64-linux/4.0.0/../../../../lib64/crti.o
/usr/lib/gcc/x86_64-linux/4.0.0/crtbegin.o -L/usr/lib/gcc/x86_64-linux/4.0.0
-L/usr/lib/gcc/x86_64-linux/4.0.0
-L/usr/lib/gcc/x86_64-linux/4.0.0/../../../../lib64
-L/usr/lib/gcc/x86_64-linux/4.0.0/../../.. -L/lib/../lib64 -L/usr/lib/../lib64
ptest.o -lgcc --as-needed -lgcc_s --no-as-needed -lc -lgcc --as-needed -lgcc_s
--no-as-needed /usr/lib/gcc/x86_64-linux/4.0.0/crtend.o
/usr/lib/gcc/x86_64-linux/4.0.0/../../../../lib64/crtn.o

In case the information is ambiguous, the compiler is a 64-bit binary generating
64-bit binaries.

Please check http://lists.debian.org/debian-amd64/2005/02/msg00505.html for some
comments I wrote on the relevant assembly output.
Comment 1 Javier Kohen 2005-02-21 21:47:13 UTC
Created attachment 8246 [details]
The program that causes the failure

I use Python's data structures, that's the explanation for the weird
structures.
Comment 2 Javier Kohen 2005-02-21 21:48:48 UTC
Created attachment 8247 [details]
A slightly modified version that does work.

I'm sorry if it's irrelevant, but here's a slightly different version that
works correctly. I was trying to make the fragment small by removing some
duplicate code, but that change makes it work. You can diff this against
ptest.i and see the few differences pretty clearly.
Comment 3 Andrew Pinski 2005-02-21 22:15:25 UTC
Reduced testcase (and shows that this is also a 3.3/3.4/4.0 Regression too):
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
typedef struct {
    struct _object *_ob_next;
    struct _object *_ob_prev;
    int ob_refcnt;
    struct _typeobject *ob_type;
    int ob_size;
    long ob_shash;
    int ob_sstate;
    char ob_sval[1];
} strobject;
static int
string_contains(strobject *a, strobject *el)
{
 const char *lhs, *rhs, *end;
 int size;

 size = (((el))->ob_size);
 rhs = (((el))->ob_sval);
 lhs = (((a))->ob_sval);

 if (size == 1)
  return memchr(lhs, *rhs, (((a))->ob_size)) != ((void *)0);

 end = lhs + ((((a))->ob_size) - size);
 while (lhs <= end) {
  const char *t = lhs+1;
  if (memcmp(lhs, rhs, size) == 0)
   return 1;
  lhs = t;
 }
 return 0;
}
int
main(void)
{
 char* s1 = "aa";
 char* s2 = "aa";
 strobject *obj1;
 strobject *obj2;
 obj1 = calloc(1, sizeof (*obj1) + 64);
 obj2 = calloc(1, sizeof (*obj2) + 64);
 obj1->ob_size = strlen(s1);
 obj2->ob_size = strlen(s2);
 memcpy(&obj1->ob_sval[0], s1, obj1->ob_size);
 memcpy(&obj2->ob_sval[0], s2, obj2->ob_size);
 printf("'%*s' in '%*s' = %d\n",
        obj2->ob_size, obj2->ob_sval,
        obj1->ob_size, obj1->ob_sval,
        string_contains(obj1, obj2));
 return 0;
}
Comment 4 Jakub Jelinek 2005-02-22 10:25:17 UTC
Looks like a strength reduction bug.
Smaller self-contained testcase:
extern void abort (void);

typedef struct { int a; char b[3]; } S;
S c = { 2, "aa" }, d = { 2, "aa" };

void *
bar (const void *x, int y, int z)
{
  return (void *) 0;
}

int
foo (S *x, S *y)
{
  const char *e, *f, *g;
  int h;

  h = y->a;
  f = y->b;
  e = x->b;

  if (h == 1)
    return bar (e, *f, x->a) != 0;

  g = e + x->a - h;
  while (e <= g)
    {
      const char *t = e + 1;
      if (__builtin_memcmp (e, f, h) == 0)
        return 1;
      e = t;
    }
  return 0;
}

int
main (void)
{
  if (foo (&c, &d) != 1)
    abort ();
  return 0;
}

Fails on both i386 and x86_64.
Comment 5 Jakub Jelinek 2005-02-22 11:32:27 UTC
I think the bug is in loop_giv_rescan assumes validate_change in:
      if (v->giv_type == DEST_ADDR)
        /* Store reduced reg as the address in the memref where we found
           this giv.  */
        validate_change (v->insn, v->location, v->new_reg, 0);

can't fail, but it indeed fails when replacing (reg/v/f:DI 67 [ lhs ])
with v->new_reg (plus:DI (reg:DI 90) (const_int -1)), as
(insn 66 65 67 (parallel [
            (set (reg:CC 17 flags)
                (if_then_else:CC (ne (reg:DI 62 [ pretmp.25 ])
                        (const_int 0 [0x0]))
                    (compare:CC (mem:BLK (plus:DI (reg:DI 90)
                                (const_int -1 [0xffffffffffffffff])) [0 A8])
                        (mem:BLK (reg/v/f:DI 66 [ rhs ]) [0 A8]))
                    (const_int 0 [0x0])))
            (use (const_int 1 [0x1]))
            (use (reg:CC 17 flags))
            (use (reg:SI 19 dirflag))
        ]) -1 (nil)
    (nil))
is not valid x86_64 insn - cmpstrqi_rex_1 requires (mem:BLK (match_operand:DI 4
"register_operand" "0")).

Not sure if it is not too late though, maybe_eliminate_biv already said it can
be eliminated.
Comment 6 Alexandre Oliva 2005-03-03 07:04:09 UTC
Oops, didn't mean to pick this one up, at least for now.
Comment 7 Alexandre Oliva 2005-03-03 07:07:03 UTC
Doh, nevermind, too many open tabs, I guess :-(
Comment 8 Alexandre Oliva 2005-03-07 21:57:43 UTC
Subject: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

loop attempts to eliminate a biv represented by a pseudo in favor of a
giv represented by (plus (reg) (const_int -1)).  Unfortunately, the
biv pseudo appears in an insn that doesn't accept anything but a
register, so validate_change fails and the error goes unnoticed.

The patch below fixes the problem and passed bootstrap on
x86_64-linux-gnu (testing still pending), but I'm not very comfortable
with the use of location for the assignment.  Is this a safe change?
Any loop experts around willing to take a second look on this?  Thanks
in advance,

Index: gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	PR target/20126
	* loop.c (loop_givs_rescan): If replacement of DEST_ADDR failed,
	set the original address pseudo to the correct value before the
	original insn and leave the insn alone.

Index: gcc/loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.522
diff -u -p -r1.522 loop.c
--- gcc/loop.c 17 Jan 2005 08:46:15 -0000 1.522
+++ gcc/loop.c 7 Mar 2005 21:37:43 -0000
@@ -5470,9 +5470,16 @@ loop_givs_rescan (struct loop *loop, str
 	mark_reg_pointer (v->new_reg, 0);
 
       if (v->giv_type == DEST_ADDR)
-	/* Store reduced reg as the address in the memref where we found
-	   this giv.  */
-	validate_change (v->insn, v->location, v->new_reg, 0);
+	{
+	  /* Store reduced reg as the address in the memref where we found
+	     this giv.  */
+	  if (! validate_change (v->insn, v->location, v->new_reg, 0))
+	    /* Not replaceable; emit an insn to set the original giv reg from
+	       the reduced giv.  */
+	    v->insn = loop_insn_emit_before (loop, 0, v->insn,
+					     gen_move_insn (*v->location,
+							    v->new_reg));
+	}
       else if (v->replaceable)
 	{
 	  reg_map[REGNO (v->dest_reg)] = v->new_reg;

-- 
Alexandre Oliva             http://www.ic.unicamp.br/~oliva/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}
Comment 9 Jakub Jelinek 2005-03-09 01:47:27 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Mon, Mar 07, 2005 at 06:56:19PM -0300, Alexandre Oliva wrote:
> loop attempts to eliminate a biv represented by a pseudo in favor of a
> giv represented by (plus (reg) (const_int -1)).  Unfortunately, the
> biv pseudo appears in an insn that doesn't accept anything but a
> register, so validate_change fails and the error goes unnoticed.
> 
> The patch below fixes the problem and passed bootstrap on
> x86_64-linux-gnu (testing still pending), but I'm not very comfortable
> with the use of location for the assignment.  Is this a safe change?
> Any loop experts around willing to take a second look on this?  Thanks
> in advance,

Unfortunately, it seems to break ada bootstrap on at least x86-64 and i386:
../../gcc/ada/ali.adb: In function 'ALI.SCAN_ALI':
../../gcc/ada/ali.adb:2070: error: unrecognizable insn:
(insn:HI 5987 1558 1560 230 ../../gcc/ada/ali.adb:996 (set (plus:SI (reg:SI 2074)
            (symbol_ref:SI ("ali__cumulative_restrictions") [flags 0x2] <var_decl 0xb7e2b360 ali__cumulative_restrictions>))
        (plus:SI (reg:SI 2074)
            (symbol_ref:SI ("ali__cumulative_restrictions") [flags 0x2] <var_decl 0xb7e2b360 ali__cumulative_restrictions>))) -1 (nil)
    (nil))

../../gcc/ada/ali.adb: In function 'ALI.SCAN_ALI':
../../gcc/ada/ali.adb:2070: error: unrecognizable insn:
(insn:HI 6040 1461 1463 230 ../../gcc/ada/ali.adb:992 (set (plus:DI (plus:DI (reg:DI 2096)
                (reg/f:DI 726))
            (const_int 12 [0xc]))
        (plus:DI (reg:DI 2096)
            (const:DI (plus:DI (symbol_ref:DI ("ali__cumulative_restrictions") [flags 0x2] <var_decl 0x2a96136ea0 ali__cumulative_restrictions>)
                    (const_int 92 [0x5c]))))) -1 (nil)
    (nil))

	Jakub
Comment 10 Alexandre Oliva 2005-03-09 04:02:23 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Mar  8, 2005, Jakub Jelinek <jakub@redhat.com> wrote:

> Unfortunately, it seems to break ada bootstrap on at least x86-64 and i386:

Odd...  It surely completed bootstrap for me with default build flags.

Hmm...  FORTIFY_SOURCE?

Comment 11 Jakub Jelinek 2005-03-09 08:51:13 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Wed, Mar 09, 2005 at 01:02:08AM -0300, Alexandre Oliva wrote:
> On Mar  8, 2005, Jakub Jelinek <jakub@redhat.com> wrote:
> 
> > Unfortunately, it seems to break ada bootstrap on at least x86-64 and i386:
> 
> Odd...  It surely completed bootstrap for me with default build flags.
> 
> Hmm...  FORTIFY_SOURCE?

This is Ada,
stage1/xgcc -Bstage1/ -B/usr/i386-redhat-linux/bin/ -c -O2 -Wall -g -pipe \
-march=i386 -mtune=pentium4 -fprofile-generate      -gnatpg -gnata -I- -I. \
-Iada -I../../gcc/ada ../../gcc/ada/ali.adb -o ada/ali.o
in particular, so -D_FORTIFY_SOURCE=2 definitely isn't in the game.
Were you bootstrapping with Ada (which is not on by default)?

	Jakub
Comment 12 Jakub Jelinek 2005-03-09 09:23:52 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Wed, Mar 09, 2005 at 01:02:08AM -0300, Alexandre Oliva wrote:
> On Mar  8, 2005, Jakub Jelinek <jakub@redhat.com> wrote:
> 
> > Unfortunately, it seems to break ada bootstrap on at least x86-64 and i386:
> 
> Odd...  It surely completed bootstrap for me with default build flags.

Your code hits just once on ali.adb
stage1/gnat1 -I- -I. -Iada -I../../gcc/ada -quiet -dumpbase ali.adb -O2 -gnatpg \
  -gnata -gnatO ada/ali.o ../../gcc/ada/ali.adb -o foo.s

(gdb) p debug_rtx(v->insn)
(insn 1571 1568 1573 (set (mem/s/v/j:QI (plus:SI (reg:SI 349 [ D.4388 ])
                (symbol_ref:SI ("ali__cumulative_restrictions") [flags 0x2] <var_decl 0xb7c0ea8c ali__cumulative_restrictions>)) [5 ali__cumulative_restrictions.set S1 A8])
        (const_int 1 [0x1])) -1 (nil)
    (nil))
(gdb) p debug_rtx(*v->location)
(plus:SI (reg:SI 349 [ D.4388 ])
    (symbol_ref:SI ("ali__cumulative_restrictions") [flags 0x2] <var_decl 0xb7c0ea8c ali__cumulative_restrictions>))
(gdb) p debug_rtx(v->new_reg)
(plus:SI (reg:SI 1953)
    (symbol_ref:SI ("ali__cumulative_restrictions") [flags 0x2] <var_decl 0xb7c0ea8c ali__cumulative_restrictions>))

Note that recog_memoized (v->insn) is -1 even without the change, not sure what would
fix that up.  But it certainly shows that *v->location doesn't have to be
a simple pseudo, so gen_move_insn might not work.

	Jakub
Comment 13 Alexandre Oliva 2005-03-10 11:44:18 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Mar  9, 2005, Jakub Jelinek <jakub@redhat.com> wrote:

> On Wed, Mar 09, 2005 at 01:02:08AM -0300, Alexandre Oliva wrote:
>> On Mar  8, 2005, Jakub Jelinek <jakub@redhat.com> wrote:
>> 
>> > Unfortunately, it seems to break ada bootstrap on at least x86-64 and i386:
>> 
>> Odd...  It surely completed bootstrap for me with default build flags.

> Your code hits just once on ali.adb

Rats, I didn't realize I needed --enable-languages=all,ada to pick
that up.  Fixed now.

> Note that recog_memoized (v->insn) is -1 even without the change,
> not sure what would fix that up.

Problem is that the insn has a volatile memory access, and loop runs
with volatile_ok = 0.

I'm not entirely sure why that is; presumably to avoid introducing or
removing volatile memory accesses.  I can see how this prevents
introducing them, but it appears to me that it still can remove them.

Anyhow, I've come up with a solution for this.  This patch introduces
a new function that is like validate_change, but if validate_change
fails and the original insn fails to be recognized with !volatile_ok
but passes with volatile_ok, then try the change and recog with
volatile_ok.

> But it certainly shows that *v->location doesn't have to be
> a simple pseudo, so gen_move_insn might not work.

Indeed.  I've introduced a new pseudo to hold the computed value now,
for the case in which *v->location isn't a reg.


Passed bootstrap and regtest on x86_64-linux-gnu on mainline, as well
as bootstrap on gcc-4_0-rhl-branch, both with Ada enabled.  Ok to
install?

Index: gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	PR target/20126
	* loop.c (loop_givs_rescan): If replacement of DEST_ADDR failed,
	set the original address pseudo to the correct value before the
	original insn, if possible, and leave the insn alone, otherwise
	create a new pseudo, set it and replace it in the insn.
	* recog.c (validate_change_maybe_volatile): New.
	* recog.h (validate_change_maybe_volatile): Declare.

Index: gcc/loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.522
diff -u -p -r1.522 loop.c
--- gcc/loop.c 17 Jan 2005 08:46:15 -0000 1.522
+++ gcc/loop.c 10 Mar 2005 11:23:59 -0000
@@ -5470,9 +5470,31 @@ loop_givs_rescan (struct loop *loop, str
 	mark_reg_pointer (v->new_reg, 0);
 
       if (v->giv_type == DEST_ADDR)
-	/* Store reduced reg as the address in the memref where we found
-	   this giv.  */
-	validate_change (v->insn, v->location, v->new_reg, 0);
+	{
+	  /* Store reduced reg as the address in the memref where we found
+	     this giv.  */
+	  if (validate_change_maybe_volatile (v->insn, v->location,
+					      v->new_reg))
+	    /* Yay, it worked!  */;
+	  /* Not replaceable; emit an insn to set the original
+	     giv reg from the reduced giv.  */
+	  else if (REG_P (*v->location))
+	    loop_insn_emit_before (loop, 0, v->insn,
+				   gen_move_insn (*v->location,
+						  v->new_reg));
+	  else
+	    {
+	      /* If it wasn't a reg, create a pseudo and use that.  */
+	      rtx reg, seq;
+	      start_sequence ();
+	      reg = force_reg (v->mode, *v->location);
+	      seq = get_insns ();
+	      end_sequence ();
+	      loop_insn_emit_before (loop, 0, v->insn, seq);
+	      gcc_assert (validate_change_maybe_volatile (v->insn, v->location,
+							  reg));
+	    }
+	}
       else if (v->replaceable)
 	{
 	  reg_map[REGNO (v->dest_reg)] = v->new_reg;
Index: gcc/recog.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/recog.c,v
retrieving revision 1.221
diff -u -p -r1.221 recog.c
--- gcc/recog.c 7 Mar 2005 13:52:08 -0000 1.221
+++ gcc/recog.c 10 Mar 2005 11:24:01 -0000
@@ -235,6 +235,34 @@ validate_change (rtx object, rtx *loc, r
     return apply_change_group ();
 }
 
+/* Same as validate_change, but doesn't support groups, and it accepts
+   volatile mems if they're already present in the original insn.
+
+   ??? Should this should search new for new volatile MEMs and reject
+   them?  */
+
+int
+validate_change_maybe_volatile (rtx object, rtx *loc, rtx new)
+{
+  int result;
+
+  if (validate_change (object, loc, new, 0))
+    return 1;
+
+  if (volatile_ok || ! insn_invalid_p (object))
+    return 0;
+
+  volatile_ok = 1;
+
+  gcc_assert (! insn_invalid_p (object));
+
+  result = validate_change (object, loc, new, 0);
+
+  volatile_ok = 0;
+
+  return result;
+}
+
 /* This subroutine of apply_change_group verifies whether the changes to INSN
    were valid; i.e. whether INSN can still be recognized.  */
 
Index: gcc/recog.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/recog.h,v
retrieving revision 1.55
diff -u -p -r1.55 recog.h
--- gcc/recog.h 7 Mar 2005 13:52:09 -0000 1.55
+++ gcc/recog.h 10 Mar 2005 11:24:01 -0000
@@ -74,6 +74,7 @@ extern void init_recog_no_volatile (void
 extern int check_asm_operands (rtx);
 extern int asm_operand_ok (rtx, const char *);
 extern int validate_change (rtx, rtx *, rtx, int);
+extern int validate_change_maybe_volatile (rtx, rtx *, rtx);
 extern int insn_invalid_p (rtx);
 extern void confirm_change_group (void);
 extern int apply_change_group (void);
Index: gcc/testsuite/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	* gcc.dg/pr20126.c: New.

Index: gcc/testsuite/gcc.dg/pr20126.c
===================================================================
RCS file: gcc/testsuite/gcc.dg/pr20126.c
diff -N gcc/testsuite/gcc.dg/pr20126.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/gcc.dg/pr20126.c 10 Mar 2005 11:24:16 -0000
@@ -0,0 +1,50 @@
+/* dg-do run */
+/* dg-options "-O2" */
+
+/* PR target/20126 was not really target-specific, but rather a loop's
+   failure to take into account the possibility that a DEST_ADDR giv
+   replacement might fail, such as when you attempt to replace a REG
+   with a PLUS in one of the register_operands of cmpstrqi_rex_1.  */
+
+extern void abort (void);
+
+typedef struct { int a; char b[3]; } S;
+S c = { 2, "aa" }, d = { 2, "aa" };
+
+void *
+bar (const void *x, int y, int z)
+{
+  return (void *) 0;
+}
+
+int
+foo (S *x, S *y)
+{
+  const char *e, *f, *g;
+  int h;
+
+  h = y->a;
+  f = y->b;
+  e = x->b;
+
+  if (h == 1)
+    return bar (e, *f, x->a) != 0;
+
+  g = e + x->a - h;
+  while (e <= g)
+    {
+      const char *t = e + 1;
+      if (__builtin_memcmp (e, f, h) == 0)
+        return 1;
+      e = t;
+    }
+  return 0;
+}
+
+int
+main (void)
+{
+  if (foo (&c, &d) != 1)
+    abort ();
+  return 0;
+}

-- 
Alexandre Oliva             http://www.ic.unicamp.br/~oliva/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}
Comment 14 Alexandre Oliva 2005-03-11 14:29:56 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Mar 10, 2005, Alexandre Oliva <aoliva@redhat.com> wrote:

> +   ??? Should this should search new for new volatile MEMs and reject
> +   them?  */

Here's a stricter version that does test for this.

Index: gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	PR target/20126
	* loop.c (loop_givs_rescan): If replacement of DEST_ADDR failed,
	set the original address pseudo to the correct value before the
	original insn, if possible, and leave the insn alone, otherwise
	create a new pseudo, set it and replace it in the insn.
	* recog.c (validate_change_maybe_volatile): New.
	* recog.h (validate_change_maybe_volatile): Declare.

Index: gcc/loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.522
diff -u -p -r1.522 loop.c
--- gcc/loop.c 17 Jan 2005 08:46:15 -0000 1.522
+++ gcc/loop.c 11 Mar 2005 14:17:20 -0000
@@ -5470,9 +5470,31 @@ loop_givs_rescan (struct loop *loop, str
 	mark_reg_pointer (v->new_reg, 0);
 
       if (v->giv_type == DEST_ADDR)
-	/* Store reduced reg as the address in the memref where we found
-	   this giv.  */
-	validate_change (v->insn, v->location, v->new_reg, 0);
+	{
+	  /* Store reduced reg as the address in the memref where we found
+	     this giv.  */
+	  if (validate_change_maybe_volatile (v->insn, v->location,
+					      v->new_reg))
+	    /* Yay, it worked!  */;
+	  /* Not replaceable; emit an insn to set the original
+	     giv reg from the reduced giv.  */
+	  else if (REG_P (*v->location))
+	    loop_insn_emit_before (loop, 0, v->insn,
+				   gen_move_insn (*v->location,
+						  v->new_reg));
+	  else
+	    {
+	      /* If it wasn't a reg, create a pseudo and use that.  */
+	      rtx reg, seq;
+	      start_sequence ();
+	      reg = force_reg (v->mode, *v->location);
+	      seq = get_insns ();
+	      end_sequence ();
+	      loop_insn_emit_before (loop, 0, v->insn, seq);
+	      gcc_assert (validate_change_maybe_volatile (v->insn, v->location,
+							  reg));
+	    }
+	}
       else if (v->replaceable)
 	{
 	  reg_map[REGNO (v->dest_reg)] = v->new_reg;
Index: gcc/recog.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/recog.c,v
retrieving revision 1.221
diff -u -p -r1.221 recog.c
--- gcc/recog.c 7 Mar 2005 13:52:08 -0000 1.221
+++ gcc/recog.c 11 Mar 2005 14:17:22 -0000
@@ -235,6 +235,45 @@ validate_change (rtx object, rtx *loc, r
     return apply_change_group ();
 }
 
+
+/* Function to be passed to for_each_rtx to test whether a piece of
+   RTL contains any mem/v.  */
+static int
+volatile_mem_p (rtx *x, void *data ATTRIBUTE_UNUSED)
+{
+  return (MEM_P (*x) && MEM_VOLATILE_P (*x));
+}
+
+/* Same as validate_change, but doesn't support groups, and it accepts
+   volatile mems if they're already present in the original insn.  */
+
+int
+validate_change_maybe_volatile (rtx object, rtx *loc, rtx new)
+{
+  int result;
+
+  if (validate_change (object, loc, new, 0))
+    return 1;
+
+  if (volatile_ok || ! insn_invalid_p (object))
+    return 0;
+
+  /* Make sure we're not adding or removing volatile MEMs.  */
+  if (for_each_rtx (loc, volatile_mem_p, 0)
+      || for_each_rtx (&new, volatile_mem_p, 0))
+    return 0;
+
+  volatile_ok = 1;
+
+  gcc_assert (! insn_invalid_p (object));
+
+  result = validate_change (object, loc, new, 0);
+
+  volatile_ok = 0;
+
+  return result;
+}
+
 /* This subroutine of apply_change_group verifies whether the changes to INSN
    were valid; i.e. whether INSN can still be recognized.  */
 
Index: gcc/recog.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/recog.h,v
retrieving revision 1.55
diff -u -p -r1.55 recog.h
--- gcc/recog.h 7 Mar 2005 13:52:09 -0000 1.55
+++ gcc/recog.h 11 Mar 2005 14:17:22 -0000
@@ -74,6 +74,7 @@ extern void init_recog_no_volatile (void
 extern int check_asm_operands (rtx);
 extern int asm_operand_ok (rtx, const char *);
 extern int validate_change (rtx, rtx *, rtx, int);
+extern int validate_change_maybe_volatile (rtx, rtx *, rtx);
 extern int insn_invalid_p (rtx);
 extern void confirm_change_group (void);
 extern int apply_change_group (void);
Index: gcc/testsuite/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	* gcc.dg/pr20126.c: New.

Index: gcc/testsuite/gcc.dg/pr20126.c
===================================================================
RCS file: gcc/testsuite/gcc.dg/pr20126.c
diff -N gcc/testsuite/gcc.dg/pr20126.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/gcc.dg/pr20126.c 11 Mar 2005 14:17:36 -0000
@@ -0,0 +1,50 @@
+/* dg-do run */
+/* dg-options "-O2" */
+
+/* PR target/20126 was not really target-specific, but rather a loop's
+   failure to take into account the possibility that a DEST_ADDR giv
+   replacement might fail, such as when you attempt to replace a REG
+   with a PLUS in one of the register_operands of cmpstrqi_rex_1.  */
+
+extern void abort (void);
+
+typedef struct { int a; char b[3]; } S;
+S c = { 2, "aa" }, d = { 2, "aa" };
+
+void *
+bar (const void *x, int y, int z)
+{
+  return (void *) 0;
+}
+
+int
+foo (S *x, S *y)
+{
+  const char *e, *f, *g;
+  int h;
+
+  h = y->a;
+  f = y->b;
+  e = x->b;
+
+  if (h == 1)
+    return bar (e, *f, x->a) != 0;
+
+  g = e + x->a - h;
+  while (e <= g)
+    {
+      const char *t = e + 1;
+      if (__builtin_memcmp (e, f, h) == 0)
+        return 1;
+      e = t;
+    }
+  return 0;
+}
+
+int
+main (void)
+{
+  if (foo (&c, &d) != 1)
+    abort ();
+  return 0;
+}

-- 
Alexandre Oliva             http://www.ic.unicamp.br/~oliva/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}
Comment 15 Alexandre Oliva 2005-04-02 17:22:33 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Mar 11, 2005, Alexandre Oliva <aoliva@redhat.com> wrote:

> On Mar 10, 2005, Alexandre Oliva <aoliva@redhat.com> wrote:
>> +   ??? Should this should search new for new volatile MEMs and reject
>> +   them?  */

> Here's a stricter version that does test for this.

> Index: gcc/ChangeLog
> from  Alexandre Oliva  <aoliva@redhat.com>

> 	PR target/20126
> 	* loop.c (loop_givs_rescan): If replacement of DEST_ADDR failed,
> 	set the original address pseudo to the correct value before the
> 	original insn, if possible, and leave the insn alone, otherwise
> 	create a new pseudo, set it and replace it in the insn.
> 	* recog.c (validate_change_maybe_volatile): New.
> 	* recog.h (validate_change_maybe_volatile): Declare.

Ping?

http://gcc.gnu.org/PR20126

Comment 16 roger 2005-04-05 04:22:07 UTC
The stricter version is mostly OK, except for one correction and one suggestion.
The correction is that in the case where the replacement wasn't a register, you
shouldn't be calling validate_change_maybe_volatile inside a gcc_assert.  When
ENABLE_ASSERT_CHECKING is disabled, the side-effects of this statement will be
lost (i.e. the replacement attempt using the new pseudo).  You should instead
try "if (!validate_change_maybe_volatile (...)) gcc_unreachable();" or
alternatively use a temporary variable.

The minor suggestion is that any potential performance impact of this change
can be reduced further by  tweaking validate_change_maybe_volatile to check
whether "object" contains any volatile mem references before attempting all
of the fallback/retry logic.

Something like:

int
validate_change_maybe_volatile (rtx object, rtx *loc, rtx new)
{
  if (validate_change (object, loc, new, 0))
    return 1;

  if (volatile_ok
+     || !for_each_rtx (&object, volatile_mem_p, 0)
      || !insn_invalid_p (object))
    return 0;

  ...

This has the "fail fast" advantage that if the original instruction
didn't contain any volatile memory references (the typical case), we
don't bother to attempt instruction recognitions with (and without)
volatile_ok set.  Admittedly, this new function is only called in
one place which probably isn't on any critical path, but the above
tweak should improve things (the for_each_rtx should typically be faster
than the insn_invalid_p call, and certainly better than two calls to
insn_invalid_p and one to validate_change when there's usually no need.)

p.s. I completely agree with your decision to implement a stricter test
to avoid inserting/replacing/modifying volatile memory references.

Please could you bootstrap and regression test with the above changes and
repost to gcc-patches?  I'm prepared to approve with those changes, once
testing confirms no unexpected interactions.  Or if you disagree with the
above comments, let me/someone know.  Thanks in advance,

Roger
-- 
Comment 17 Alexandre Oliva 2005-04-08 16:34:04 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Mar 11, 2005, Alexandre Oliva <aoliva@redhat.com> wrote:

> On Mar 10, 2005, Alexandre Oliva <aoliva@redhat.com> wrote:
>> +   ??? Should this should search new for new volatile MEMs and reject
>> +   them?  */

> Here's a stricter version that does test for this.

Roger suggested some changes in the patch.  I've finally completed
bootstrap and test with and without the patch on amd64-linux-gnu, and
posted the results to the test-results list.  No regressions.  Ok to
install?

Index: gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	PR target/20126
	* loop.c (loop_givs_rescan): If replacement of DEST_ADDR failed,
	set the original address pseudo to the correct value before the
	original insn, if possible, and leave the insn alone, otherwise
	create a new pseudo, set it and replace it in the insn.
	* recog.c (validate_change_maybe_volatile): New.
	* recog.h (validate_change_maybe_volatile): Declare.

Index: gcc/loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.525
diff -u -p -r1.525 loop.c
--- gcc/loop.c 2 Apr 2005 16:53:38 -0000 1.525
+++ gcc/loop.c 5 Apr 2005 19:22:41 -0000
@@ -5476,9 +5476,31 @@ loop_givs_rescan (struct loop *loop, str
 	mark_reg_pointer (v->new_reg, 0);
 
       if (v->giv_type == DEST_ADDR)
-	/* Store reduced reg as the address in the memref where we found
-	   this giv.  */
-	validate_change (v->insn, v->location, v->new_reg, 0);
+	{
+	  /* Store reduced reg as the address in the memref where we found
+	     this giv.  */
+	  if (validate_change_maybe_volatile (v->insn, v->location,
+					      v->new_reg))
+	    /* Yay, it worked!  */;
+	  /* Not replaceable; emit an insn to set the original
+	     giv reg from the reduced giv.  */
+	  else if (REG_P (*v->location))
+	    loop_insn_emit_before (loop, 0, v->insn,
+				   gen_move_insn (*v->location,
+						  v->new_reg));
+	  else
+	    {
+	      /* If it wasn't a reg, create a pseudo and use that.  */
+	      rtx reg, seq;
+	      start_sequence ();
+	      reg = force_reg (v->mode, *v->location);
+	      seq = get_insns ();
+	      end_sequence ();
+	      loop_insn_emit_before (loop, 0, v->insn, seq);
+	      gcc_assert (validate_change_maybe_volatile (v->insn, v->location,
+							  reg));
+	    }
+	}
       else if (v->replaceable)
 	{
 	  reg_map[REGNO (v->dest_reg)] = v->new_reg;
Index: gcc/recog.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/recog.c,v
retrieving revision 1.221
diff -u -p -r1.221 recog.c
--- gcc/recog.c 7 Mar 2005 13:52:08 -0000 1.221
+++ gcc/recog.c 5 Apr 2005 19:22:43 -0000
@@ -235,6 +235,45 @@ validate_change (rtx object, rtx *loc, r
     return apply_change_group ();
 }
 
+
+/* Function to be passed to for_each_rtx to test whether a piece of
+   RTL contains any mem/v.  */
+static int
+volatile_mem_p (rtx *x, void *data ATTRIBUTE_UNUSED)
+{
+  return (MEM_P (*x) && MEM_VOLATILE_P (*x));
+}
+
+/* Same as validate_change, but doesn't support groups, and it accepts
+   volatile mems if they're already present in the original insn.  */
+
+int
+validate_change_maybe_volatile (rtx object, rtx *loc, rtx new)
+{
+  int result;
+
+  if (validate_change (object, loc, new, 0))
+    return 1;
+
+  if (volatile_ok
+      /* Make sure we're not adding or removing volatile MEMs.  */
+      || for_each_rtx (loc, volatile_mem_p, 0)
+      || for_each_rtx (&new, volatile_mem_p, 0)
+      || ! insn_invalid_p (object))
+    return 0;
+
+  volatile_ok = 1;
+
+  if (insn_invalid_p (object))
+    gcc_unreachable ();
+
+  result = validate_change (object, loc, new, 0);
+
+  volatile_ok = 0;
+
+  return result;
+}
+
 /* This subroutine of apply_change_group verifies whether the changes to INSN
    were valid; i.e. whether INSN can still be recognized.  */
 
Index: gcc/recog.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/recog.h,v
retrieving revision 1.55
diff -u -p -r1.55 recog.h
--- gcc/recog.h 7 Mar 2005 13:52:09 -0000 1.55
+++ gcc/recog.h 5 Apr 2005 19:22:43 -0000
@@ -74,6 +74,7 @@ extern void init_recog_no_volatile (void
 extern int check_asm_operands (rtx);
 extern int asm_operand_ok (rtx, const char *);
 extern int validate_change (rtx, rtx *, rtx, int);
+extern int validate_change_maybe_volatile (rtx, rtx *, rtx);
 extern int insn_invalid_p (rtx);
 extern void confirm_change_group (void);
 extern int apply_change_group (void);
Index: gcc/testsuite/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	* gcc.dg/pr20126.c: New.

Index: gcc/testsuite/gcc.dg/pr20126.c
===================================================================
RCS file: gcc/testsuite/gcc.dg/pr20126.c
diff -N gcc/testsuite/gcc.dg/pr20126.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/gcc.dg/pr20126.c 5 Apr 2005 19:22:59 -0000
@@ -0,0 +1,50 @@
+/* dg-do run */
+/* dg-options "-O2" */
+
+/* PR target/20126 was not really target-specific, but rather a loop's
+   failure to take into account the possibility that a DEST_ADDR giv
+   replacement might fail, such as when you attempt to replace a REG
+   with a PLUS in one of the register_operands of cmpstrqi_rex_1.  */
+
+extern void abort (void);
+
+typedef struct { int a; char b[3]; } S;
+S c = { 2, "aa" }, d = { 2, "aa" };
+
+void *
+bar (const void *x, int y, int z)
+{
+  return (void *) 0;
+}
+
+int
+foo (S *x, S *y)
+{
+  const char *e, *f, *g;
+  int h;
+
+  h = y->a;
+  f = y->b;
+  e = x->b;
+
+  if (h == 1)
+    return bar (e, *f, x->a) != 0;
+
+  g = e + x->a - h;
+  while (e <= g)
+    {
+      const char *t = e + 1;
+      if (__builtin_memcmp (e, f, h) == 0)
+        return 1;
+      e = t;
+    }
+  return 0;
+}
+
+int
+main (void)
+{
+  if (foo (&c, &d) != 1)
+    abort ();
+  return 0;
+}

-- 
Alexandre Oliva             http://www.ic.unicamp.br/~oliva/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}
Comment 18 roger 2005-04-08 17:03:21 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail


Hi Alex,

On 8 Apr 2005, Alexandre Oliva wrote:
> Roger suggested some changes in the patch.  I've finally completed
> bootstrap and test with and without the patch on amd64-linux-gnu, and
> posted the results to the test-results list.  No regressions.  Ok to
> install?

Hmm.  It looks like you misunderstood some of the comments in my
review (comment #16 in the bugzilla PR)...

+  gcc_assert (validate_change_maybe_volatile (v->insn, v->location,
+					       reg));

This is still unsafe.  If you look in system.h, you'll see that when
ENABLE_ASSERT_CHECKING is undefined, the gcc_assert macro gets defined
as:

#define gcc_assert(EXPR) ((void)(0 && (EXPR)))

which means that EXPR will not get executed.  Hence you can't put
side-effecting statements (especially those whose changes you depend
upon) naked inside a gcc_assert.  Ahh, I now see the misunderstanding;
you changed/fixed the other "safe" gcc_assert statement, and missed
the important one that I was worried about.  Sorry for the confusion.


Secondly:

+  if (volatile_ok
+      /* Make sure we're not adding or removing volatile MEMs.  */
+      || for_each_rtx (loc, volatile_mem_p, 0)
+      || for_each_rtx (&new, volatile_mem_p, 0)
+      || ! insn_invalid_p (object))
+    return 0;

The suggestion wasn't just to reorder the existing for_each_rtx to
move these tests earlier, it was to confirm that the original "whole"
instruction had a volatile memory reference in it, i.e. that this is
a problematic case, before doing any more work.  Something like:

+  if (volatile_ok
++     /* If there isn't a volatile MEM, there's nothing we can do.  */
++     || !for_each_rtx (&object, volatile_mem_p, 0)
+!     /* But make sure we're not adding or removing volatile MEMs.  */
+      || for_each_rtx (loc, volatile_mem_p, 0)
+      || for_each_rtx (&new, volatile_mem_p, 0)
+      || ! insn_invalid_p (object))
+    return 0;

This second change was just a micro-optimization, and I'd have approved
your patch without it, but the use of gcc_assert in loop_givs_rescan is
a real correctness issue.

Sorry again for the inconvenience,

Roger
--

Comment 19 Alexandre Oliva 2005-04-08 20:51:25 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Apr  8, 2005, Roger Sayle <roger@eyesopen.com> wrote:

> Ahh, I now see the misunderstanding; you changed/fixed the other
> "safe" gcc_assert statement, and missed the important one that I was
> worried about.  Sorry for the confusion.

Yep.  Doh!

> Secondly:

> +  if (volatile_ok
> +      /* Make sure we're not adding or removing volatile MEMs.  */
> +      || for_each_rtx (loc, volatile_mem_p, 0)
> +      || for_each_rtx (&new, volatile_mem_p, 0)
> +      || ! insn_invalid_p (object))
> +    return 0;

> The suggestion wasn't just to reorder the existing for_each_rtx to
> move these tests earlier, it was to confirm that the original "whole"
> instruction had a volatile memory reference in it, i.e. that this is
> a problematic case, before doing any more work.

Aaah.  Clearly, I wasn't thinking right when I made the change.  I'll
test your suggested change along with the gcc_assert fix.

> Sorry again for the inconvenience,

No worries.  I shouldn't have rushed to making the changes and
starting a bootstrap before going to bed on a night when I was so
tired :-/

I'll post the patch when testing is complete.

Comment 20 Alexandre Oliva 2005-04-10 02:43:36 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Apr  8, 2005, Roger Sayle <roger@eyesopen.com> wrote:

> ++     /* If there isn't a volatile MEM, there's nothing we can do.  */
> ++     || !for_each_rtx (&object, volatile_mem_p, 0)

This actually caused crashes.  We don't want to scan the entire insn
(it might contain NULLs), only the insn pattern.  Here's the patch
that bootstrapped and passed regression testing on amd64-linux-gnu.
Ok?

Index: gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	PR target/20126
	* loop.c (loop_givs_rescan): If replacement of DEST_ADDR failed,
	set the original address pseudo to the correct value before the
	original insn, if possible, and leave the insn alone, otherwise
	create a new pseudo, set it and replace it in the insn.
	* recog.c (validate_change_maybe_volatile): New.
	* recog.h (validate_change_maybe_volatile): Declare.

Index: gcc/loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.525
diff -u -p -r1.525 loop.c
--- gcc/loop.c 2 Apr 2005 16:53:38 -0000 1.525
+++ gcc/loop.c 10 Apr 2005 00:13:56 -0000
@@ -5476,9 +5476,31 @@ loop_givs_rescan (struct loop *loop, str
 	mark_reg_pointer (v->new_reg, 0);
 
       if (v->giv_type == DEST_ADDR)
-	/* Store reduced reg as the address in the memref where we found
-	   this giv.  */
-	validate_change (v->insn, v->location, v->new_reg, 0);
+	{
+	  /* Store reduced reg as the address in the memref where we found
+	     this giv.  */
+	  if (validate_change_maybe_volatile (v->insn, v->location,
+					      v->new_reg))
+	    /* Yay, it worked!  */;
+	  /* Not replaceable; emit an insn to set the original
+	     giv reg from the reduced giv.  */
+	  else if (REG_P (*v->location))
+	    loop_insn_emit_before (loop, 0, v->insn,
+				   gen_move_insn (*v->location,
+						  v->new_reg));
+	  else
+	    {
+	      /* If it wasn't a reg, create a pseudo and use that.  */
+	      rtx reg, seq;
+	      start_sequence ();
+	      reg = force_reg (v->mode, *v->location);
+	      seq = get_insns ();
+	      end_sequence ();
+	      loop_insn_emit_before (loop, 0, v->insn, seq);
+	      if (!validate_change_maybe_volatile (v->insn, v->location, reg))
+		gcc_unreachable ();
+	    }
+	}
       else if (v->replaceable)
 	{
 	  reg_map[REGNO (v->dest_reg)] = v->new_reg;
Index: gcc/recog.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/recog.c,v
retrieving revision 1.221
diff -u -p -r1.221 recog.c
--- gcc/recog.c 7 Mar 2005 13:52:08 -0000 1.221
+++ gcc/recog.c 10 Apr 2005 00:13:57 -0000
@@ -235,6 +235,46 @@ validate_change (rtx object, rtx *loc, r
     return apply_change_group ();
 }
 
+
+/* Function to be passed to for_each_rtx to test whether a piece of
+   RTL contains any mem/v.  */
+static int
+volatile_mem_p (rtx *x, void *data ATTRIBUTE_UNUSED)
+{
+  return (MEM_P (*x) && MEM_VOLATILE_P (*x));
+}
+
+/* Same as validate_change, but doesn't support groups, and it accepts
+   volatile mems if they're already present in the original insn.  */
+
+int
+validate_change_maybe_volatile (rtx object, rtx *loc, rtx new)
+{
+  int result;
+
+  if (validate_change (object, loc, new, 0))
+    return 1;
+
+  if (volatile_ok
+      /* If there isn't a volatile MEM, there's nothing we can do.  */
+      || !for_each_rtx (&PATTERN (object), volatile_mem_p, 0)
+      /* Make sure we're not adding or removing volatile MEMs.  */
+      || for_each_rtx (loc, volatile_mem_p, 0)
+      || for_each_rtx (&new, volatile_mem_p, 0)
+      || !insn_invalid_p (object))
+    return 0;
+
+  volatile_ok = 1;
+
+  gcc_assert (!insn_invalid_p (object));
+
+  result = validate_change (object, loc, new, 0);
+
+  volatile_ok = 0;
+
+  return result;
+}
+
 /* This subroutine of apply_change_group verifies whether the changes to INSN
    were valid; i.e. whether INSN can still be recognized.  */
 
Index: gcc/recog.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/recog.h,v
retrieving revision 1.55
diff -u -p -r1.55 recog.h
--- gcc/recog.h 7 Mar 2005 13:52:09 -0000 1.55
+++ gcc/recog.h 10 Apr 2005 00:13:57 -0000
@@ -74,6 +74,7 @@ extern void init_recog_no_volatile (void
 extern int check_asm_operands (rtx);
 extern int asm_operand_ok (rtx, const char *);
 extern int validate_change (rtx, rtx *, rtx, int);
+extern int validate_change_maybe_volatile (rtx, rtx *, rtx);
 extern int insn_invalid_p (rtx);
 extern void confirm_change_group (void);
 extern int apply_change_group (void);
Index: gcc/testsuite/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	* gcc.dg/pr20126.c: New.

Index: gcc/testsuite/gcc.dg/pr20126.c
===================================================================
RCS file: gcc/testsuite/gcc.dg/pr20126.c
diff -N gcc/testsuite/gcc.dg/pr20126.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/gcc.dg/pr20126.c 10 Apr 2005 00:14:15 -0000
@@ -0,0 +1,50 @@
+/* dg-do run */
+/* dg-options "-O2" */
+
+/* PR target/20126 was not really target-specific, but rather a loop's
+   failure to take into account the possibility that a DEST_ADDR giv
+   replacement might fail, such as when you attempt to replace a REG
+   with a PLUS in one of the register_operands of cmpstrqi_rex_1.  */
+
+extern void abort (void);
+
+typedef struct { int a; char b[3]; } S;
+S c = { 2, "aa" }, d = { 2, "aa" };
+
+void *
+bar (const void *x, int y, int z)
+{
+  return (void *) 0;
+}
+
+int
+foo (S *x, S *y)
+{
+  const char *e, *f, *g;
+  int h;
+
+  h = y->a;
+  f = y->b;
+  e = x->b;
+
+  if (h == 1)
+    return bar (e, *f, x->a) != 0;
+
+  g = e + x->a - h;
+  while (e <= g)
+    {
+      const char *t = e + 1;
+      if (__builtin_memcmp (e, f, h) == 0)
+        return 1;
+      e = t;
+    }
+  return 0;
+}
+
+int
+main (void)
+{
+  if (foo (&c, &d) != 1)
+    abort ();
+  return 0;
+}

-- 
Alexandre Oliva             http://www.ic.unicamp.br/~oliva/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}
Comment 21 roger 2005-04-10 03:18:40 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail


On 9 Apr 2005, Alexandre Oliva wrote:
> On Apr  8, 2005, Roger Sayle <roger@eyesopen.com> wrote:
>
> > ++     /* If there isn't a volatile MEM, there's nothing we can do.  */
> > ++     || !for_each_rtx (&object, volatile_mem_p, 0)
>
> This actually caused crashes.  We don't want to scan the entire insn
> (it might contain NULLs), only the insn pattern.

Argh! Indeed, my mistake/oversight.  Thanks.


>	PR target/20126
>	* loop.c (loop_givs_rescan): If replacement of DEST_ADDR failed,
>	set the original address pseudo to the correct value before the
>	original insn, if possible, and leave the insn alone, otherwise
>	create a new pseudo, set it and replace it in the insn.
>	* recog.c (validate_change_maybe_volatile): New.
>	* recog.h (validate_change_maybe_volatile): Declare.

This is OK for mainline, thanks.  Now that 4.0 is frozen for release
candidate one, Mark needs to decide whether this patch can make it
into 4.0.0 or will have to wait for 4.0.1.  I also think we should
wait for that decision before considering a backport for 3.4.x (or
we'll have a strange temporal regression).

I'd recommend commiting this patch to mainline ASAP, so it can have
a few days of testing before Mark has to make his decision.

Thanks again for your patience,

Roger
--

Comment 22 GCC Commits 2005-04-10 04:01:06 UTC
Subject: Bug 20126

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	aoliva@gcc.gnu.org	2005-04-10 04:00:54

Modified files:
	gcc            : ChangeLog loop.c recog.c recog.h 
	gcc/testsuite  : ChangeLog 
Added files:
	gcc/testsuite/gcc.dg: pr20126.c 

Log message:
	gcc/ChangeLog:
	PR target/20126
	* loop.c (loop_givs_rescan): If replacement of DEST_ADDR failed,
	set the original address pseudo to the correct value before the
	original insn, if possible, and leave the insn alone, otherwise
	create a new pseudo, set it and replace it in the insn.
	* recog.c (validate_change_maybe_volatile): New.
	* recog.h (validate_change_maybe_volatile): Declare.
	gcc/testsuite/ChangeLog:
	* gcc.dg/pr20126.c: New.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.8217&r2=2.8218
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/loop.c.diff?cvsroot=gcc&r1=1.525&r2=1.526
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/recog.c.diff?cvsroot=gcc&r1=1.221&r2=1.222
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/recog.h.diff?cvsroot=gcc&r1=1.55&r2=1.56
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&r1=1.5318&r2=1.5319
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/pr20126.c.diff?cvsroot=gcc&r1=NONE&r2=1.1

Comment 23 Mark Mitchell 2005-04-10 18:44:35 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

Roger Sayle wrote:
> On 9 Apr 2005, Alexandre Oliva wrote:
> 
>>On Apr  8, 2005, Roger Sayle <roger@eyesopen.com> wrote:
>>
>>
>>>++     /* If there isn't a volatile MEM, there's nothing we can do.  */
>>>++     || !for_each_rtx (&object, volatile_mem_p, 0)
>>
>>This actually caused crashes.  We don't want to scan the entire insn
>>(it might contain NULLs), only the insn pattern.
> 
> 
> Argh! Indeed, my mistake/oversight.  Thanks.
> 
> 
> 
>>	PR target/20126
>>	* loop.c (loop_givs_rescan): If replacement of DEST_ADDR failed,
>>	set the original address pseudo to the correct value before the
>>	original insn, if possible, and leave the insn alone, otherwise
>>	create a new pseudo, set it and replace it in the insn.
>>	* recog.c (validate_change_maybe_volatile): New.
>>	* recog.h (validate_change_maybe_volatile): Declare.
> 
> 
> This is OK for mainline, thanks.  Now that 4.0 is frozen for release
> candidate one, Mark needs to decide whether this patch can make it
> into 4.0.0 or will have to wait for 4.0.1.  I also think we should
> wait for that decision before considering a backport for 3.4.x (or
> we'll have a strange temporal regression).

Thanks for alerting me to this one; it does look relatively serious. 
I've added it to:

http://gcc.gnu.org/wiki/Last-Minute%20Requests%20for%204.0.0

and will consider whether it merits a second release-candidate.

Comment 24 Andrew Pinski 2005-04-10 21:00:20 UTC
Fixed at least on the mainline.
Comment 25 Alexandre Oliva 2005-04-11 03:51:29 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Apr 10, 2005, Mark Mitchell <mark@codesourcery.com> wrote:

> Thanks for alerting me to this one; it does look relatively
> serious. I've added it to:

> http://gcc.gnu.org/wiki/Last-Minute%20Requests%20for%204.0.0

> and will consider whether it merits a second release-candidate.

FWIW, I've bootstrapped and regtested it on amd64-linux-gnu on 4.0
branch as well.  The same patch applies cleanly.

Comment 26 Joshua Conner 2005-04-11 21:10:59 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail


On Apr 10, 2005, at 8:50 PM, Alexandre Oliva wrote:

> On Apr 10, 2005, Mark Mitchell <mark@codesourcery.com> wrote:
>
>> Thanks for alerting me to this one; it does look relatively
>> serious. I've added it to:
>
>> http://gcc.gnu.org/wiki/Last-Minute%20Requests%20for%204.0.0
>
>> and will consider whether it merits a second release-candidate.
>
> FWIW, I've bootstrapped and regtested it on amd64-linux-gnu on 4.0
> branch as well.  The same patch applies cleanly.
>
> --  
> Alexandre Oliva             http://www.ic.unicamp.br/~oliva/
> Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
> Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}
>

I'm now getting a ICE building the mainline (please ignore the "3.4.3"  
in the
directory structure, it's a holdover from the build scripts I'm using)  
that appears
to be related to this patch.  Here's the output:

...
/Volumes/Home/Users/josh/work/SameOld-mainline-elf/ToolsSrc/build-gcc 
-3.4.3-arm-elf-full/./gcc/xgcc  
-B/Volumes/Home/Users/josh/work/SameOld-mainline-elf/ToolsSrc/build- 
gcc-3.4.3-arm-elf-full/./gcc/  -c -DHAVE_CONFIG_H -O2 -g -O2  -I.  
-I/Volumes/Home/Users/josh/work/SameOld-mainline-elf/ToolsSrc/gcc/ 
libiberty/../include  -W -Wall -pedantic -Wwrite-strings  
-Wstrict-prototypes  
/Volumes/Home/Users/josh/work/SameOld-mainline-elf/ToolsSrc/gcc/ 
libiberty/cp-demangle.c -o cp-demangle.o
In file included from  
/Volumes/Home/Users/josh/work/SameOld-mainline-elf/ToolsSrc/gcc/ 
libiberty/cp-demangle.c:99:
/Volumes/Home/Users/josh/work/SameOld-mainline-elf/ToolsSrc/gcc/ 
libiberty/../include/libiberty.h:80: warning: function declaration  
isn't a prototype
/Volumes/Home/Users/josh/work/SameOld-mainline-elf/ToolsSrc/gcc/ 
libiberty/cp-demangle.c: In function 'd_print_comp':
/Volumes/Home/Users/josh/work/SameOld-mainline-elf/ToolsSrc/gcc/ 
libiberty/cp-demangle.c:3324: internal compiler error: in  
loop_givs_rescan, at loop.c:5501
Please submit a full bug report,
with preprocessed source if appropriate.
See <URL:http://gcc.gnu.org/bugs.html> for instructions.
make[1]: *** [cp-demangle.o] Error 1
make: *** [all-target-libiberty] Error 2

And my configuration:

TOPLEVEL_CONFIGURE_ARGUMENTS=/Volumes/Home/Users/josh/work/SameOld- 
mainline-elf/ToolsSrc/gcc/configure  
--prefix=/Volumes/Home/Users/josh/work/SameOld-mainline-elf/ToolsSrc/ 
gcc/../../ToolChains/darwin-ppc/gcc-3.4.3/ --target=arm-unknown-elf  
--program-prefix=arm-elf- --disable-nls --enable-languages=c,c++  
--with-newlib --enable-multilib --disable-shared

FWIW, the mainline built successfully for me on 5 April.

I'd be glad to enter a bug report, if it's appropriate -- I wasn't sure  
about
proper behavior for a recently fixed bug.  Otherwise, I'm also glad to  
provide
any additional information that may help track down the issue.

- Josh
~~~~~~
Josh Conner
Apple Computer

Comment 27 Alexandre Oliva 2005-04-12 03:35:37 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Apr 11, 2005, Josh Conner <jconner@apple.com> wrote:

> I'm now getting a ICE building the mainline (please ignore the
> "3.4.3" in the directory structure, it's a holdover from the build
> scripts I'm using) that appears to be related to this patch.

That sounds possible.  The patch might indeed have the effect of
turning previously-silent miscompilations into ICEs.  I didn't expect
we'd get any, but you may be proving me wrong.  Would you please send
me the preprocessed testcase in private, or just confirm that you're
using newlib as the C library?  I'll then try to duplicate the problem
on one of the platforms at my disposal.

Comment 28 Alexandre Oliva 2005-04-12 06:58:57 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Apr 12, 2005, Alexandre Oliva <aoliva@redhat.com> wrote:

> On Apr 11, 2005, Josh Conner <jconner@apple.com> wrote:
>> I'm now getting a ICE building the mainline (please ignore the
>> "3.4.3" in the directory structure, it's a holdover from the build
>> scripts I'm using) that appears to be related to this patch.

> That sounds possible.  The patch might indeed have the effect of
> turning previously-silent miscompilations into ICEs.  I didn't expect
> we'd get any, but you may be proving me wrong.  Would you please send
> me the preprocessed testcase in private, or just confirm that you're
> using newlib as the C library?  I'll then try to duplicate the problem
> on one of the platforms at my disposal.

I went ahead and tried to build an arm-elf toolchain out of uberbaum,
and got the problem.

The problem was an stmia instruction in a loop, whose base address
pseudo loop wanted to replace with another pseudo plus a constant.
Since there's a requirement that all of the base addresses match, when
we started replacing the address expressions of any of the
destinations other than the first, that didn't have an offset, the
insn failed to match, and none of the work arounds I introduced for
such a replacement failure succeeded.

The only relatively simple way to overcome this error I could think of
was to introduce yet another work around, to enable us to handle not
only REGs, but also PLUS involving a REG and a constant (very likely
a literal immediate, but I didn't introduce such a requirement).

This has enabled the testcase to compile successfully and correctly,
although we generate a total of 4 assignments to the pseudo in
response to the 4 givs detected involving it in the 4-register stmia
instruction.  Not a big deal, since they end up being optimized away.

The bad news is that this is a regression.  The code before my patch
would still work: for some reason I still don't understand, the
assignment of the base pseudo isn't removed, so with my new work
around patch below, we end up introducing unnecessary assignments to
the giv.  They are optimized away, but if I can figure out what the
conditions are in which we don't need to introduce assignments to the
giv, we could simply avoid all the messy new code, that assumes we
absolutely must replace the expression with something else.

Anyhow, here's the patch with the workaround for the problem you ran
into.  I'll submit it formally when it completes testing.

Index: gcc/loop.c
===================================================================
RCS file: /cvs/uberbaum/gcc/loop.c,v
retrieving revision 1.526
diff -u -p -r1.526 loop.c
--- gcc/loop.c 10 Apr 2005 04:00:45 -0000 1.526
+++ gcc/loop.c 12 Apr 2005 06:35:26 -0000
@@ -5488,6 +5488,15 @@ loop_givs_rescan (struct loop *loop, str
 	    loop_insn_emit_before (loop, 0, v->insn,
 				   gen_move_insn (*v->location,
 						  v->new_reg));
+	  else if (GET_CODE (*v->location) == PLUS
+		   && REG_P (XEXP (*v->location, 0))
+		   && CONSTANT_P (XEXP (*v->location, 1)))
+	    loop_insn_emit_before (loop, 0, v->insn,
+				   gen_move_insn (XEXP (*v->location, 0),
+						  gen_rtx_MINUS
+						  (GET_MODE (*v->location),
+						   v->new_reg,
+						   XEXP (*v->location, 1))));
 	  else
 	    {
 	      /* If it wasn't a reg, create a pseudo and use that.  */

-- 
Alexandre Oliva             http://www.ic.unicamp.br/~oliva/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}
Comment 29 Alexandre Oliva 2005-04-12 08:19:22 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Apr 12, 2005, Alexandre Oliva <aoliva@redhat.com> wrote:

> They are optimized away, but if I can figure out what the
> conditions are in which we don't need to introduce assignments to the
> giv, we could simply avoid all the messy new code, that assumes we
> absolutely must replace the expression with something else.

It appears that the only case in which we could do away with adding
the assignment is if giv->same is biv, and we mark the bl with
all_reduced=0.  It appears to me that, in any other case, the
assignment we're relying on might have been dropped or hoisted.

I'd love to be wrong, though.  If I am, we could get your problem, as
well as the original bug report, fixed by simply reverting my patch
and setting bl->all_reduced=0 if validate_change failed.  This
actually works for the testcases I've tried, but I'm not convinced it
works in the general case.  Does any expert in rtl loop care to chime
in?

Thanks,

Comment 30 roger 2005-04-12 14:38:36 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail


Hi Alexandre,

On 12 Apr 2005, Alexandre Oliva wrote:
> Does any expert in rtl loop care to chime in?

I'm not sure I qualify for the title "rtl loop" expert, but setting
bl->all_reduced to zero after we fail to validate a change to the
RTL looks to be a reasonable failure mode.

I still like your fallbacks, that by trying harder we perform better
optimization, but as shown by the ARM's "stmia" instruction I suspect
there will always be cases were we can't reduce IV expressions in
some backend instructions.

Previously, we didn't even detect these cases and potentially generated
bad code.  I think the ICE was an improvement over the "potentially" bad
code, but what we really need is a more graceful failure/degradation.


As you propose, I'd recommend something like (for your final clause):

	/* If it wasn't a reg, create a pseudo and use that.  */
	rtx reg, seq;
	start_sequence ();
	reg = force_reg (v->mode, *v->location);
!	if (validate_change_maybe_volatile (v->insn, v->location, reg))
!	  {
!	    seq = get_insns ();
!	    end_sequence ();
!	    loop_insn_emit_before (loop, 0, v->insn, seq);
!	  }
!	else
!	  {
!	    end_sequence ();
!	    if (loop_dump_stream)
!	      fprintf (loop_dump_stream,
!		       "unable to reduce iv to register in insn %d\n",
!		       INSN_UID (v->insn));
!	    bl->all_reduced = 0;
!	    v->ignore = 1;
!	    continue;
!	  }


I think its worthwhile keeping the validate_change_maybe_volatile
calls/changes on mainline.  But then for gcc 4.0.0 or 4.0.1
we can use the much simpler:


      if (v->giv_type == DEST_ADDR)
        /* Store reduced reg as the address in the memref where we found
           this giv.  */
!	{
!	  if (!validate_change (v->insn, v->location, v->new_reg, 0))
!	    {
!             if (loop_dump_stream)
!               fprintf (loop_dump_stream,
!                        "unable to reduce iv to register in insn %d\n",
!                        INSN_UID (v->insn));
!             bl->all_reduced = 0;
!             v->ignore = 1;
!             continue;
!	    }
!	}


A much less intrusive regression fix than previously proposed fix for
4.0.  But perhaps one of the real "rtl loop" experts would like to
comment?

Roger
--

Comment 31 Mark Mitchell 2005-04-12 17:54:55 UTC
I like the simpler approach.  If someone would test that for 4.0, I'd be ecstatic.
Comment 32 Jakub Jelinek 2005-04-13 09:46:44 UTC
Subject: Re:  [3.3/3.4/4.0 Regression] Inlined memcmp makes one argument null on entry

On Tue, Apr 12, 2005 at 05:54:58PM -0000, mmitchel at gcc dot gnu dot org wrote:
> 
> ------- Additional Comments From mmitchel at gcc dot gnu dot org  2005-04-12 17:54 -------
> I like the simpler approach.  If someone would test that for 4.0, I'd be ecstatic.

Here is what I have bootstrapped/regtested on
{i386,x86_64,ia64,ppc,ppc64,s390,s390x}-linux.

2005-04-13  Alexandre Oliva  <aoliva@redhat.com>
	    Roger Sayle  <roger@eyesopen.com>

	PR target/20126
	* loop.c (loop_givs_rescan): If replacement of DEST_ADDR failed,
	set the original address pseudo to the correct value before the
	original insn, if possible, and leave the insn alone, otherwise
	create a new pseudo, set it and replace it in the insn.
	* recog.c (validate_change_maybe_volatile): New.
	* recog.h (validate_change_maybe_volatile): Declare.

	* gcc.dg/pr20126.c: New.

--- gcc/loop.c.jj	2005-04-03 10:33:24.000000000 +0200
+++ gcc/loop.c	2005-04-12 23:22:06.000000000 +0200
@@ -5478,9 +5478,20 @@ loop_givs_rescan (struct loop *loop, str
 	mark_reg_pointer (v->new_reg, 0);
 
       if (v->giv_type == DEST_ADDR)
-	/* Store reduced reg as the address in the memref where we found
-	   this giv.  */
-	validate_change (v->insn, v->location, v->new_reg, 0);
+	{
+	  /* Store reduced reg as the address in the memref where we found
+	     this giv.  */
+	  if (!validate_change (v->insn, v->location, v->new_reg, 0))
+	    {
+	      if (loop_dump_stream)
+		fprintf (loop_dump_stream,
+			 "unable to reduce iv to register in insn %d\n",
+			 INSN_UID (v->insn));
+	      bl->all_reduced = 0;
+	      v->ignore = 1;
+	      continue;
+	    }
+	}
       else if (v->replaceable)
 	{
 	  reg_map[REGNO (v->dest_reg)] = v->new_reg;
--- gcc/testsuite/gcc.dg/pr20126.c	1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/gcc.dg/pr20126.c 10 Mar 2005 11:24:16 -0000
@@ -0,0 +1,50 @@
+/* dg-do run */
+/* dg-options "-O2" */
+
+/* PR target/20126 was not really target-specific, but rather a loop's
+   failure to take into account the possibility that a DEST_ADDR giv
+   replacement might fail, such as when you attempt to replace a REG
+   with a PLUS in one of the register_operands of cmpstrqi_rex_1.  */
+
+extern void abort (void);
+
+typedef struct { int a; char b[3]; } S;
+S c = { 2, "aa" }, d = { 2, "aa" };
+
+void *
+bar (const void *x, int y, int z)
+{
+  return (void *) 0;
+}
+
+int
+foo (S *x, S *y)
+{
+  const char *e, *f, *g;
+  int h;
+
+  h = y->a;
+  f = y->b;
+  e = x->b;
+
+  if (h == 1)
+    return bar (e, *f, x->a) != 0;
+
+  g = e + x->a - h;
+  while (e <= g)
+    {
+      const char *t = e + 1;
+      if (__builtin_memcmp (e, f, h) == 0)
+	return 1;
+      e = t;
+    }
+  return 0;
+}
+
+int
+main (void)
+{
+  if (foo (&c, &d) != 1)
+    abort ();
+  return 0;
+}


	Jakub
Comment 33 Bernd Schmidt 2005-04-13 10:08:40 UTC
Subject: Re:  [3.3/3.4/4.0 Regression] Inlined memcmp makes
 one argument null on entry

Jakub Jelinek wrote:
> 	PR target/20126
> 	* loop.c (loop_givs_rescan): If replacement of DEST_ADDR failed,
> 	set the original address pseudo to the correct value before the
> 	original insn, if possible, and leave the insn alone, otherwise
> 	create a new pseudo, set it and replace it in the insn.
> 	* recog.c (validate_change_maybe_volatile): New.
> 	* recog.h (validate_change_maybe_volatile): Declare.
> 
This doesn't appear to match the patch you posted.


Bernd
Comment 34 Jakub Jelinek 2005-04-13 11:38:23 UTC
Subject: Re:  [3.3/3.4/4.0 Regression] Inlined memcmp makes one argument null on entry

On Wed, Apr 13, 2005 at 12:05:35PM +0200, Bernd Schmidt wrote:
> Jakub Jelinek wrote:
> >	PR target/20126
> >	* loop.c (loop_givs_rescan): If replacement of DEST_ADDR failed,
> >	set the original address pseudo to the correct value before the
> >	original insn, if possible, and leave the insn alone, otherwise
> >	create a new pseudo, set it and replace it in the insn.
> >	* recog.c (validate_change_maybe_volatile): New.
> >	* recog.h (validate_change_maybe_volatile): Declare.
> >
> This doesn't appear to match the patch you posted.

Oops.  Is:
2005-04-13  Alexandre Oliva  <aoliva@redhat.com>
	    Roger Sayle  <roger@eyesopen.com>

	PR target/20126
	* loop.c (loop_givs_rescan): If replacement of DEST_ADDR failed,
	signal that all GIVs couldn't be reduced.

	* gcc.dg/pr20126.c: New.
better?

	Jakub
Comment 35 jsm-csl@polyomino.org.uk 2005-04-13 21:01:47 UTC
Subject: Re:  [3.3/3.4/4.0 Regression] Inlined memcmp makes
 one argument null on entry

On Wed, 13 Apr 2005, jakub at redhat dot com wrote:

> +/* dg-do run */
> +/* dg-options "-O2" */

Not valid gcc.dg markings (missing surrounding { }).  All tests which are 
portable, test only successful compilation or execution (not warnings) and 
whose options are among those tested in gcc.c-torture should go there, 
i.e. in this case gcc.c-torture/execute, instead of gcc.dg.  (It is indeed 
the case that several tests are wrongly in gcc.dg and should move.)

Comment 36 Mark Mitchell 2005-04-14 06:02:32 UTC
Subject: Re:  [3.3/3.4/4.0 Regression] Inlined memcmp makes
 one argument null on entry

Jakub Jelinek wrote:
> On Tue, Apr 12, 2005 at 05:54:58PM -0000, mmitchel at gcc dot gnu dot org wrote:
> 
>>------- Additional Comments From mmitchel at gcc dot gnu dot org  2005-04-12 17:54 -------
>>I like the simpler approach.  If someone would test that for 4.0, I'd be ecstatic.
> 
> 
> Here is what I have bootstrapped/regtested on
> {i386,x86_64,ia64,ppc,ppc64,s390,s390x}-linux.

Please apply this to the 4.0 branch forthwith.  Thanks for taking the 
initiative; Alexandre, Roger, thanks for working on this as well.

Comment 37 GCC Commits 2005-04-14 06:14:51 UTC
Subject: Bug 20126

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	gcc-4_0-branch
Changes by:	jakub@gcc.gnu.org	2005-04-14 06:14:41

Modified files:
	gcc            : ChangeLog loop.c 
	gcc/testsuite  : ChangeLog 
Added files:
	gcc/testsuite/gcc.c-torture/execute: 20050414-1.c 

Log message:
	2005-04-14  Alexandre Oliva  <aoliva@redhat.com>
	Roger Sayle  <roger@eyesopen.com>
	
	PR target/20126
	* loop.c (loop_givs_rescan): If replacement of DEST_ADDR failed,
	signal that all GIVs couldn't be reduced.
	
	* gcc.c-torture/execute/20050414-1.c: New.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.7592.2.151&r2=2.7592.2.152
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/loop.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=1.522.8.1&r2=1.522.8.2
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=1.5084.2.123&r2=1.5084.2.124
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.c-torture/execute/20050414-1.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=NONE&r2=1.1.2.1

Comment 38 Alexandre Oliva 2005-04-14 17:21:42 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Apr 12, 2005, Roger Sayle <roger@eyesopen.com> wrote:

> !             v->ignore = 1;

What's the point of the statement above?  If we actually know the giv
reg has the right value, why not use it for other purposes as well?

Comment 39 roger 2005-04-14 17:37:58 UTC
You'll notice in loop.c that everywhere that we currently set all_reduced to
zero, we also set ignore to true.  This change is to avoid wasting CPU cycles,
if we know that an IV can't be eliminated, there's no point in trying to
modify any more instructions that use it.  At best, this incurs wasted
CPU cycles, at worst we'll end up substituting in some places and not others,
which will result in requiring both the original IV *and* the replacement IV
which will increase register pressure in the loop.

As your (Alex's) testing showed, I'm not sure that its strictly required for
correctness, it's mainly to preserve consistency with the exisiting all_reduced
invariants by using the same idiom as used elsewhere, but also as a potential
compile-time/run-time micro-optimization.  However for 4.0, I thought it best
to reuse/copy the existing idiom, rather than risk clearing all_reduced without
setting ignore (which may have potentially exposed code paths not seen before).

We still need the 4.1 variant to be tested/committed to mainline.
Comment 40 Alexandre Oliva 2005-04-15 03:31:18 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Apr 12, 2005, Roger Sayle <roger@eyesopen.com> wrote:

> I still like your fallbacks, that by trying harder we perform better
> optimization,

The more I think about this, the more I have the impression that
perhaps the fallbacks are not necessary.  My gut feeling (that has
been wrong before, so take that with a grain of salt) is that, if we
mark the giv as ignored, its assignment within the loop won't be
removed (if they ever are, I'm not entirely sure), so if we introduce
a new assignment, we're wasting cpu cycles either in the compiler, if
it has to remove the redundant set, or at run-time, if it can't figure
that out.

My feeling stems from the fact that we've never had (AFAIK) a
situation in which the failure to make the change caused a
miscompilation, except in the case of a biv whose final assignment was
hoisted before the loop.  I can't quite figure out why this would ever
make sense; it appears to me that computing its final value after the
loop is always profitable is always better because it would reduce
register pressure, but I may be way off here.  In the two other cases
that were exposed by attempts to report failures in the substitution
(namely, the Ada bootstrap error that Jakub reported against an
earlier version of the patch, and the arm-elf build failure that Josh
reported), the value was there, and, since the code actually refrained
from checking the result of validate_change, perhaps it really didn't
matter whether the substitution worked.  At least until we started
swimming bivs to before the loop...

So I'm wondering if taking out all of the workarounds and going back
to something like what is now in the 4.0 branch, except for the use of
validate_change_maybe_volatile, wouldn't get us exactly what we want.

Unfortunately, cases in which the substitution fails are quite rare,
and the loop code isn't exactly trivial, so it's hard to decide
whether we've just been lucky, or the code was already mostly correct.

Anyhow, in the meantime, could I check in the patch to fix Josh's
asm-elf build failure?  I haven't been able to bootstrap the tree
lately because of PR21029, but I know it would bootstrap successfully
on amd64-linux-gnu (it would never hit the point that I changed :-),
and I know it fixes the arm-elf problem.

It would be nice to keep the hard failure in place for a bit longer,
such that we stood a better chance of finding other situations that
might require work arounds.

Comment 41 roger 2005-04-15 14:52:32 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail


On 15 Apr 2005, Alexandre Oliva wrote:
> On Apr 12, 2005, Roger Sayle <roger@eyesopen.com> wrote:
> > I still like your fallbacks, that by trying harder we perform
> > better optimization,
>
> The more I think about this, the more I have the impression that
> perhaps the fallbacks are not necessary.
> ...
> So I'm wondering if taking out all of the workarounds and going back
> to something like what is now in the 4.0 branch, except for the use of
> validate_change_maybe_volatile, wouldn't get us exactly what we want.
> ...
> Anyhow, in the meantime, could I check in the patch to fix Josh's
> asm-elf build failure?
> ...
> It would be nice to keep the hard failure in place for a bit longer,
> such that we stood a better chance of finding other situations that
> might require work arounds.

Sure.   Your patch in comment #28 of bugzilla PR20126 is OK for mainline
to resolve Josh's bootstrap failure.  Sounds like you've already done
the necessary testing, and I'll trust you on a suitable ChangeLog entry.

I agree with your proposed game plan of keeping the hard failure in
place temporarily, to discover whether there are any other "fallback"
strategies that would be useful.  Ultimately though, I don't think we
should close PR20126 until a "soft failure" is implemented on mainline,
like we've (Jakub has) done on the gcc-4_0-branch (such as the
mainline code proposed in comment #30).

Roger
--

Comment 42 Richard Earnshaw 2005-04-16 17:50:50 UTC
(In reply to comment #41)
> Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

> Sure.   Your patch in comment #28 of bugzilla PR20126 is OK for mainline
> to resolve Josh's bootstrap failure.  Sounds like you've already done
> the necessary testing, and I'll trust you on a suitable ChangeLog entry.
>

I'm not convinced.

1) It produces non-canonical RTL: (MINUS (REG) (const))
2) It doesn't validate that insn, which is necessary in case 'const' or some
modified version of it is not valid.

R.
Comment 43 GCC Commits 2005-04-16 21:42:32 UTC
Subject: Bug 20126

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	aoliva@gcc.gnu.org	2005-04-16 21:42:27

Modified files:
	gcc            : ChangeLog loop.c 

Log message:
	PR target/20126
	* loop.c (loop_givs_rescan): Handle non-replaceable (plus (reg)
	(const)).

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.8324&r2=2.8325
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/loop.c.diff?cvsroot=gcc&r1=1.526&r2=1.527

Comment 44 Alexandre Oliva 2005-04-16 21:48:51 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Apr 15, 2005, Roger Sayle <roger@eyesopen.com> wrote:

> Sure.   Your patch in comment #28 of bugzilla PR20126 is OK for mainline
> to resolve Josh's bootstrap failure.  Sounds like you've already done
> the necessary testing, and I'll trust you on a suitable ChangeLog entry.

Thanks, here's what I've just checked in.

Index: gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>
	PR target/20126
	* loop.c (loop_givs_rescan): Handle non-replaceable (plus (reg)
	(const)).

Index: gcc/loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.526
diff -u -p -r1.526 loop.c
--- gcc/loop.c 10 Apr 2005 04:00:45 -0000 1.526
+++ gcc/loop.c 16 Apr 2005 21:40:02 -0000
@@ -5488,6 +5488,15 @@ loop_givs_rescan (struct loop *loop, str
 	    loop_insn_emit_before (loop, 0, v->insn,
 				   gen_move_insn (*v->location,
 						  v->new_reg));
+	  else if (GET_CODE (*v->location) == PLUS
+		   && REG_P (XEXP (*v->location, 0))
+		   && CONSTANT_P (XEXP (*v->location, 1)))
+	    loop_insn_emit_before (loop, 0, v->insn,
+				   gen_move_insn (XEXP (*v->location, 0),
+						  gen_rtx_MINUS
+						  (GET_MODE (*v->location),
+						   v->new_reg,
+						   XEXP (*v->location, 1))));
 	  else
 	    {
 	      /* If it wasn't a reg, create a pseudo and use that.  */

-- 
Alexandre Oliva             http://www.ic.unicamp.br/~oliva/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}
Comment 45 Alexandre Oliva 2005-04-16 21:58:03 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Apr 15, 2005, Roger Sayle <roger@eyesopen.com> wrote:

> I agree with your proposed game plan of keeping the hard failure in
> place temporarily, to discover whether there are any other "fallback"
> strategies that would be useful.  Ultimately though, I don't think we
> should close PR20126 until a "soft failure" is implemented on mainline,
> like we've (Jakub has) done on the gcc-4_0-branch (such as the
> mainline code proposed in comment #30).

But see, the problem with the soft failure mode is that, if it is ever
legitimate to leave the giv alone and not make sure we set whatever
register appears in it to the right value, then can't we always do it,
removing all of the (thus useless) workarounds?

And if there's any case in which it is not legitimate to do so, then
the soft failure mode would be a disservice to the user, that would
silently get a miscompiled program.  We should probably at least warn
in this case.

Anyhow, here's a patch that was tested with bootstrap and regtest on
amd64-linux-gnu on mainline, that brings in the soft failure mode from
the 4.0 branch to mainline, without removing the potentially-useless
workarounds.

Index: gcc/loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.526
diff -u -p -r1.526 loop.c
--- gcc/loop.c 10 Apr 2005 04:00:45 -0000 1.526
+++ gcc/loop.c 16 Apr 2005 21:37:45 -0000
@@ -5494,11 +5494,23 @@ loop_givs_rescan (struct loop *loop, str
 	      rtx reg, seq;
 	      start_sequence ();
 	      reg = force_reg (v->mode, *v->location);
-	      seq = get_insns ();
-	      end_sequence ();
-	      loop_insn_emit_before (loop, 0, v->insn, seq);
-	      if (!validate_change_maybe_volatile (v->insn, v->location, reg))
-		gcc_unreachable ();
+	      if (validate_change_maybe_volatile (v->insn, v->location, reg))
+		{
+		  seq = get_insns ();
+		  end_sequence ();
+		  loop_insn_emit_before (loop, 0, v->insn, seq);
+		}
+	      else
+		{
+		  end_sequence ();
+		  if (loop_dump_stream)
+		    fprintf (loop_dump_stream,
+			     "unable to reduce iv in insn %d\n",
+			     INSN_UID (v->insn));
+		  bl->all_reduced = 0;
+		  v->ignore = 1;
+		  continue;
+		}
 	    }
 	}
       else if (v->replaceable)

-- 
Alexandre Oliva             http://www.ic.unicamp.br/~oliva/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}
Comment 46 roger 2005-04-17 00:21:58 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail


Hi Alex,

On 16 Apr 2005, Alexandre Oliva wrote:
> On Apr 15, 2005, Roger Sayle <roger@eyesopen.com> wrote:
> > I agree with your proposed game plan of keeping the hard failure in
> > place temporarily, to discover whether there are any other "fallback"
> > strategies that would be useful.  Ultimately though, I don't think we
> > should close PR20126 until a "soft failure" is implemented on mainline,
> > like we've (Jakub has) done on the gcc-4_0-branch (such as the
> > mainline code proposed in comment #30).
>
> But see, the problem with the soft failure mode is that, if it is ever
> legitimate to leave the giv alone and not make sure we set whatever
> register appears in it to the right value, then can't we always do it,
> removing all of the (thus useless) workarounds?
>
> And if there's any case in which it is not legitimate to do so, then
> the soft failure mode would be a disservice to the user, that would
> silently get a miscompiled program.  We should probably at least warn
> in this case.

I don't believe there are any cases in which it is not legitimate
to leave the GIV alone, so we'll never silently miscompile anything.

My understanding is that it's always possible to leave the giv
alone (provided that we set all_reduced to false).  The "workarounds"
as we've got used to calling them are not required for correctness,
but for aggressive optimization.  There's clearly a benefit to
strength reducing GIVs, and the harder we try to replace them, the
better the code we generate.  Yes, they are (useless/not necessary)
from a purely correctness point of view; we don't even have to call
validate_change we could just always give-up and punt using clearing
all_reduced (technicaly we don't have to perform any loop optimizations
for correctness), but we'd generate pretty poor code.

The patch you proposed provides the soft failure mode we want (and
now have on the release branch).  We could, as you say remove all
of the current workarounds, and the only thing that would suffer is
the quality of the code we generate.  Needless to say, I'd prefer
to keep these optimizations (for example your recent one for Josh
to allow us to strength reduce the ARM's stim instruction).  It's
not unreasonable to try three or four approaches before giving up,
and forcing the optimizers to preserve the original GIV.


Does this clear things up?  Do you agree?

Roger
--

Comment 47 Alexandre Oliva 2005-04-17 02:37:52 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail

On Apr 16, 2005, Roger Sayle <roger@eyesopen.com> wrote:

> Does this clear things up?  Do you agree?

Yup, for both questions.  Thanks for the clarification.  It wasn't
clear to me that the assignments played any useful role, as soon as I
found out the givs could be assumed to hold the correct value.  It
all makes sense to me now.

Comment 48 Mark Mitchell 2005-04-17 02:46:53 UTC
Jakub, thank you for applying this patch to the 4.0 branch.

If you've confirmed that the bug has been fixed, would you please remove 4.0
from the summary here, and from the known-to-fail list?

Thanks,

-- Mark
Comment 49 roger 2005-04-17 03:06:37 UTC
Subject: Re: [PR target/20126, RFC] loop DEST_ADDR biv replacement may fail


On 16 Apr 2005, Alexandre Oliva wrote:
> On Apr 16, 2005, Roger Sayle <roger@eyesopen.com> wrote:
>
> > Does this clear things up?  Do you agree?
>
> Yup, for both questions.  Thanks for the clarification.  It wasn't
> clear to me that the assignments played any useful role, as soon as I
> found out the givs could be assumed to hold the correct value.  It
> all makes sense to me now.

Your patch (in comment #45) is OK for mainline, with a suitable
ChangeLog entry.  Hurray, we can close the PR.

Roger
--

Comment 50 Ulrich Weigand 2005-07-07 19:20:36 UTC
(In reply to comment #49)
> Your patch (in comment #45) is OK for mainline, with a suitable
> ChangeLog entry.  Hurray, we can close the PR.

Is there any reason why the patch wasn't checked in?

I'm now getting bootstrap failure on s390 because the gcc_unreachable
is triggered ...   With the patch from comment #45, bootstrap succeeds.
Comment 51 Alexandre Oliva 2005-07-08 12:23:31 UTC
I don't know whether I just forgot about it, or figured we'd be better off
leaving it as it was for a bit longer, so as to expose more cases we could
handle especially.
Comment 52 Ulrich Weigand 2005-07-08 15:48:15 UTC
(In reply to comment #51)
> I don't know whether I just forgot about it, or figured we'd be better off
> leaving it as it was for a bit longer, so as to expose more cases we could
> handle especially.

Well, in my case the problem is that the pattern has two memory operands 
whose addresses need to agree, and loop is trying to change one of them
--> the insn predicate rejects.

I don't see how this can be fixed easily, and don't think much effort
should be put into the old loop code -- but we need a safe fall-back
to avoid the ICE.
Comment 53 GCC Commits 2005-07-11 03:56:20 UTC
Subject: Bug 20126

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	danglin@gcc.gnu.org	2005-07-11 03:56:14

Modified files:
	gcc            : ChangeLog loop.c 

Log message:
	PR middle-end/22239
	PR target/20126
	* loop.c (loop_givs_rescan): Use expand_simple_binop instead of
	gen_rtx_MINUS to handle non-replaceable (plus ((x) (const)).

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.9401&r2=2.9402
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/loop.c.diff?cvsroot=gcc&r1=1.535&r2=1.536

Comment 54 Ulrich Weigand 2005-07-13 22:28:18 UTC
Bootstrap on s390-ibm-linux is still broken because of this issue.  Can we just check in the patch from comment #45?  
Comment 55 Alexandre Oliva 2005-07-14 18:32:15 UTC
I'd say go for it.  It's approved, after all.  'fraid I don't have a ChangeLog
entry handy.
Comment 56 GCC Commits 2005-07-14 21:11:45 UTC
Subject: Bug 20126

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	uweigand@gcc.gnu.org	2005-07-14 21:11:41

Modified files:
	gcc            : ChangeLog loop.c 

Log message:
	2005-07-14  Alexandre Oliva  <aoliva@redhat.com>
	Ulrich Weigand  <uweigand@de.ibm.com>
	
	PR target/20126
	* loop.c (loop_givs_rescan): Do not ICE if unable to reduce an IV
	in some insn.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.9445&r2=2.9446
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/loop.c.diff?cvsroot=gcc&r1=1.536&r2=1.537

Comment 57 Alexandre Oliva 2006-02-20 18:37:33 UTC
This should have long been closed.