CSE bug (PR27363)

[Paul Brook <paul at codesourcery dot com>]

I've been looking at PR27363, which is an arm-linux kernel miscompilation.

The code is a structure copy, followed be a use of the first element of that
structure. 

Slightly simplified, we have:

(reg 101) and (reg 102) are the source and destination addresses
for that structure copy. (reg 104) is the value used after the copy.


#1: (set (reg 103) (reg 101))

#2: (parallel
   (set (reg 103) (plus (reg 103) (const_int 8)))
   (set (reg 0) (mem (reg 103)))
   (set (reg 1) (mem (plus (reg 103) (const_int 4)))))

#3: (parallel
   (set (reg 102) (plus (reg 102) (const_int 8)))
   (set (mem (reg 102)) (reg 0))
   (set (mem (plus (reg 102) (const_int 4))) (reg 1)))

#4: (set (reg 104) (mem (reg 101)))

The miscompilation occurs in the first CSE pass.

After insn #2 cse has correctly determined that (reg 0) is equivalent to (mem 
(reg 101)).

When processing insn #3 cse_insn identifies that (reg 0) is equivalent to (mem 
(reg 101)), ok so far.

Then it invalidates all equivalences involving registers set by this insn, ie. 
anything involving (reg 102). Also ok.

As its last act it adds an equivalence for the set destination ie. between 
(mem (reg 102)) and (mem (reg 101)). AFAICS there's no code to notice that 
the destination of the set is invalidated by one of the other sets in the 
parallel.

The attached patch fixes this in a similar way to how source operands are 
handled. Destination addresses are added to the hash table, then we check to 
see if they have been removed after invalidating the set destinations.
I originally did the checks manually, then Richard Sandiford suggested the 
current solution.

The testcase is from the PR. It isn't a particularly good testcase (I'd expect 
SRA to be able to eliminate it entirely before long), but I couldn't come up 
with a better one.

Tested with cross to arm-none-eabi and bootstrapped on i686-linux.
I can't tell if this is a regression (it fails at least as far back as 3.4), 
however it is a wrong-code bug compiling the linux kernel.
Ok?

Paul

2006-07-19  Paul Brook  <paul@codesourcery.com>

	gcc/
	* cse.c (cse_insn): Add destination addresses to hash table. Check if
	they are invalidated by this instruction.

	gcc/testsuite/
	* gcc.dg/pr27363.c: New test.

Index: gcc/cse.c
===================================================================
--- gcc/cse.c	(revision 115597)
+++ gcc/cse.c	(working copy)
@@ -4739,6 +4739,8 @@ struct set
   unsigned src_const_hash;
   /* Table entry for constant equivalent for SET_SRC, if any.  */
   struct table_elt *src_const_elt;
+  /* Table entry for the destination address.  */
+  struct table_elt *dest_addr_elt;
 };
 
 static void
@@ -5970,6 +5972,40 @@ cse_insn (rtx insn, rtx libcall_insn)
 	 so that the destination goes into that class.  */
       sets[i].src_elt = src_eqv_elt;
 
+  /* Record destination addresses in the hash table.  This allows us to
+     check if they are invalidated by other sets.  */
+  for (i = 0; i < n_sets; i++)
+    {
+      if (sets[i].rtl)
+	{
+	  rtx x = SET_DEST (sets[i].rtl);
+	  struct table_elt *elt;
+	  enum machine_mode mode;
+	  unsigned hash;
+
+	  if (MEM_P (x))
+	    {
+	      x = XEXP (x, 0);
+	      mode = GET_MODE (x);
+	      hash = HASH (x, mode);
+	      elt = lookup (x, hash, mode);
+	      if (!elt)
+		{
+		  if (insert_regs (x, NULL, 0))
+		    {
+		      rehash_using_reg (x);
+		      hash = HASH (x, mode);
+		    }
+		  elt = insert (x, NULL, hash, mode);
+		}
+
+	      sets[i].dest_addr_elt = elt;
+	    }
+	  else
+	    sets[i].dest_addr_elt = NULL;
+	}
+    }
+
   invalidate_from_clobbers (x);
 
   /* Some registers are invalidated by subroutine calls.  Memory is
@@ -6062,12 +6098,20 @@ cse_insn (rtx insn, rtx libcall_insn)
     }
 
   /* We may have just removed some of the src_elt's from the hash table.
-     So replace each one with the current head of the same class.  */
+     So replace each one with the current head of the same class.
+     Also check if destination addresses have been removed.  */
 
   for (i = 0; i < n_sets; i++)
     if (sets[i].rtl)
       {
-	if (sets[i].src_elt && sets[i].src_elt->first_same_value == 0)
+	if (sets[i].dest_addr_elt
+	    && sets[i].dest_addr_elt->first_same_value == 0)
+	  {
+	    /* The elt was removed, which means this destination s not
+	       valid after this instruction.  */
+	    sets[i].rtl = NULL_RTX;
+	  }
+	else if (sets[i].src_elt && sets[i].src_elt->first_same_value == 0)
 	  /* If elt was removed, find current head of same class,
 	     or 0 if nothing remains of that class.  */
 	  {
Index: gcc/testsuite/gcc.dg/pr27363.c
===================================================================
--- gcc/testsuite/gcc.dg/pr27363.c	(revision 0)
+++ gcc/testsuite/gcc.dg/pr27363.c	(revision 0)
@@ -0,0 +1,39 @@
+/* PR27363.  CSE was breaking on the arm store multiple insn used for
+   structure copies.  */
+/* { dg-do run } */
+/* { dg-options "-Os" } */
+extern void abort (void);
+
+struct snd_mask {
+    unsigned int bits[6];
+};
+
+static int __attribute__((noinline))
+snd_mask_refine(struct snd_mask *mask)
+{
+  struct snd_mask old;
+
+  old = *mask;
+  if (mask->bits[0]==0 && mask->bits[1]==0)
+    return 1;
+
+  return old.bits[0] != mask->bits[0];
+}
+
+int main(int argc, char *argv[])
+{
+  struct snd_mask mask;
+
+
+  mask.bits[0] = 23;
+  mask.bits[1] = 42;
+  mask.bits[2] = 0;
+  mask.bits[3] = 0;
+  mask.bits[4] = 0; 
+  mask.bits[5] = 0;
+
+
+  if (snd_mask_refine(&mask))
+    abort();
+  return 0;
+}