re PR rtl-optimization/51933 (wrong code due to -free)

	PR rtl-optimization/51933
	* ree.c (transform_ifelse): Return true right away if dstreg is
	already wider or equal to cand->mode.
	(enum ext_modified_kind, struct ext_modified, ext_state): New types.
	(make_defs_and_copies_lists): Remove defs_list and copies_list
	arguments, add state argument, just truncate state->work_list
	instead of always allocating and freeing the vector.  Assert that
	get_defs succeeds instead of returning 2.  Changed return type to
	bool.
	(merge_def_and_ext): Add state argument.  If SET_DEST doesn't
	have ext_src_mode, see if it has been modified already with the
	right kind of extension and has been extended before from the
	ext_src_mode.  If SET_DEST is already wider or equal to cand->mode,
	just return true.  Remember the original mode in state->modified
	array.
	(combine_reaching_defs): Add state argument.  Don't allocate and
	free here def_list, copied_list and vec vectors, instead just
	VEC_truncate the vectors in *state.  Don't handle outcome == 2
	here.
	(find_and_remove_re): Set DF_DEFER_INSN_RESCAN df flag.
	Add state variable, clear vectors in it, initialize state.modified
	if needed.  Free all the vectors at the end and state.modified too.
	Don't skip a candidate if the extension expression has been modified.

	* gcc.c-torture/execute/pr51933.c: New test.

From-SVN: r183416

4 files changed, 210 insertions, 83 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index c65dcc3..80f124a 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,29 @@
+2012-01-23  Jakub Jelinek  <jakub@redhat.com>
+
+	PR rtl-optimization/51933
+	* ree.c (transform_ifelse): Return true right away if dstreg is
+	already wider or equal to cand->mode.
+	(enum ext_modified_kind, struct ext_modified, ext_state): New types.
+	(make_defs_and_copies_lists): Remove defs_list and copies_list
+	arguments, add state argument, just truncate state->work_list
+	instead of always allocating and freeing the vector.  Assert that
+	get_defs succeeds instead of returning 2.  Changed return type to
+	bool.
+	(merge_def_and_ext): Add state argument.  If SET_DEST doesn't
+	have ext_src_mode, see if it has been modified already with the
+	right kind of extension and has been extended before from the
+	ext_src_mode.  If SET_DEST is already wider or equal to cand->mode,
+	just return true.  Remember the original mode in state->modified
+	array.
+	(combine_reaching_defs): Add state argument.  Don't allocate and
+	free here def_list, copied_list and vec vectors, instead just
+	VEC_truncate the vectors in *state.  Don't handle outcome == 2
+	here.
+	(find_and_remove_re): Set DF_DEFER_INSN_RESCAN df flag.
+	Add state variable, clear vectors in it, initialize state.modified
+	if needed.  Free all the vectors at the end and state.modified too.
+	Don't skip a candidate if the extension expression has been modified.
+
 2012-01-22  Douglas B Rupp  <rupp@gnat.com>
 
 	PR target/47096
diff --git a/gcc/ree.c b/gcc/ree.c
index 4cab20e..3f67091 100644
--- a/gcc/ree.c
+++ b/gcc/ree.c
@@ -1,5 +1,5 @@
 /* Redundant Extension Elimination pass for the GNU compiler.
-   Copyright (C) 2010, 2011 Free Software Foundation, Inc.
+   Copyright (C) 2010, 2011, 2012 Free Software Foundation, Inc.
    Contributed by Ilya Enkovich (ilya.enkovich@intel.com)
 
    Based on the Redundant Zero-extension elimination pass contributed by
@@ -380,6 +380,11 @@ transform_ifelse (ext_cand *cand, rtx def_insn)
   dstreg = SET_DEST (set_insn);
   srcreg = XEXP (SET_SRC (set_insn), 1);
   srcreg2 = XEXP (SET_SRC (set_insn), 2);
+  /* If the conditional move already has the right or wider mode,
+     there is nothing to do.  */
+  if (GET_MODE_SIZE (GET_MODE (dstreg)) >= GET_MODE_SIZE (cand->mode))
+    return true;
+
   map_srcreg = gen_rtx_REG (cand->mode, REGNO (srcreg));
   map_srcreg2 = gen_rtx_REG (cand->mode, REGNO (srcreg2));
   map_dstreg = gen_rtx_REG (cand->mode, REGNO (dstreg));
@@ -466,43 +471,77 @@ is_cond_copy_insn (rtx insn, rtx *reg1, rtx *reg2)
   return false;
 }
 
+enum ext_modified_kind
+{
+  /* The insn hasn't been modified by ree pass yet.  */
+  EXT_MODIFIED_NONE,
+  /* Changed into zero extension.  */
+  EXT_MODIFIED_ZEXT,
+  /* Changed into sign extension.  */
+  EXT_MODIFIED_SEXT
+};
+
+struct ext_modified
+{
+  /* Mode from which ree has zero or sign extended the destination.  */
+  ENUM_BITFIELD(machine_mode) mode : 8;
+
+  /* Kind of modification of the insn.  */
+  ENUM_BITFIELD(ext_modified_kind) kind : 2;
+
+  /* True if the insn is scheduled to be deleted.  */
+  unsigned int deleted : 1;
+};
+
+/* Vectors used by combine_reaching_defs and its helpers.  */
+typedef struct ext_state
+{
+  /* In order to avoid constant VEC_alloc/VEC_free, we keep these
+     4 vectors live through the entire find_and_remove_re and just
+     VEC_truncate them each time.  */
+  VEC (rtx, heap) *defs_list;
+  VEC (rtx, heap) *copies_list;
+  VEC (rtx, heap) *modified_list;
+  VEC (rtx, heap) *work_list;
+
+  /* For instructions that have been successfully modified, this is
+     the original mode from which the insn is extending and
+     kind of extension.  */
+  struct ext_modified *modified;
+} ext_state;
+
 /* Reaching Definitions of the extended register could be conditional copies
    or regular definitions.  This function separates the two types into two
-   lists, DEFS_LIST and COPIES_LIST.  This is necessary because, if a reaching
-   definition is a conditional copy, merging the extension with this definition
-   is wrong.  Conditional copies are merged by transitively merging their
-   definitions.  The defs_list is populated with all the reaching definitions
-   of the extension instruction (EXTEND_INSN) which must be merged with an
-   extension.  The copies_list contains all the conditional moves that will
-   later be extended into a wider mode conditional move if all the merges are
-   successful.  The function returns 0 upon failure, 1 upon success and 2 when
-   all definitions of the EXTEND_INSN have been previously merged.  */
-
-static int
+   lists, STATE->DEFS_LIST and STATE->COPIES_LIST.  This is necessary because,
+   if a reaching definition is a conditional copy, merging the extension with
+   this definition is wrong.  Conditional copies are merged by transitively
+   merging their definitions.  The defs_list is populated with all the reaching
+   definitions of the extension instruction (EXTEND_INSN) which must be merged
+   with an extension.  The copies_list contains all the conditional moves that
+   will later be extended into a wider mode conditional move if all the merges
+   are successful.  The function returns false upon failure, true upon
+   success.  */
+
+static bool
 make_defs_and_copies_lists (rtx extend_insn, rtx set_pat,
-                            VEC (rtx,heap) **defs_list,
-                            VEC (rtx,heap) **copies_list)
+			    ext_state *state)
 {
-  VEC (rtx,heap) *work_list = VEC_alloc (rtx, heap, 8);
   rtx src_reg = XEXP (SET_SRC (set_pat), 0);
   bool *is_insn_visited;
-  int ret = 1;
+  bool ret = true;
+
+  VEC_truncate (rtx, state->work_list, 0);
 
   /* Initialize the work list.  */
-  if (!get_defs (extend_insn, src_reg, &work_list))
-    {
-      VEC_free (rtx, heap, work_list);
-      /* The number of defs being equal to zero can only mean that all the
-         definitions have been previously merged.  */
-      return 2;
-    }
+  if (!get_defs (extend_insn, src_reg, &state->work_list))
+    gcc_unreachable ();
 
   is_insn_visited = XCNEWVEC (bool, max_insn_uid);
 
   /* Perform transitive closure for conditional copies.  */
-  while (!VEC_empty (rtx, work_list))
+  while (!VEC_empty (rtx, state->work_list))
     {
-      rtx def_insn = VEC_pop (rtx, work_list);
+      rtx def_insn = VEC_pop (rtx, state->work_list);
       rtx reg1, reg2;
 
       gcc_assert (INSN_UID (def_insn) < max_insn_uid);
@@ -514,22 +553,21 @@ make_defs_and_copies_lists (rtx extend_insn, rtx set_pat,
       if (is_cond_copy_insn (def_insn, &reg1, &reg2))
 	{
 	  /* Push it onto the copy list first.  */
-	  VEC_safe_push (rtx, heap, *copies_list, def_insn);
+	  VEC_safe_push (rtx, heap, state->copies_list, def_insn);
 
 	  /* Now perform the transitive closure.  */
-	  if (!get_defs (def_insn, reg1, &work_list)
-	      || !get_defs (def_insn, reg2, &work_list))
+	  if (!get_defs (def_insn, reg1, &state->work_list)
+	      || !get_defs (def_insn, reg2, &state->work_list))
 	    {
-	      ret = 0;
+	      ret = false;
 	      break;
 	    }
         }
       else
-	VEC_safe_push (rtx, heap, *defs_list, def_insn);
+	VEC_safe_push (rtx, heap, state->defs_list, def_insn);
     }
 
   XDELETEVEC (is_insn_visited);
-  VEC_free (rtx, heap, work_list);
 
   return ret;
 }
@@ -538,7 +576,7 @@ make_defs_and_copies_lists (rtx extend_insn, rtx set_pat,
    on the SET pattern.  */
 
 static bool
-merge_def_and_ext (ext_cand *cand, rtx def_insn)
+merge_def_and_ext (ext_cand *cand, rtx def_insn, ext_state *state)
 {
   enum machine_mode ext_src_mode;
   enum rtx_code code;
@@ -577,10 +615,27 @@ merge_def_and_ext (ext_cand *cand, rtx def_insn)
 
   gcc_assert (sub_rtx != NULL);
 
-  if (GET_CODE (SET_DEST (*sub_rtx)) == REG
-      && GET_MODE (SET_DEST (*sub_rtx)) == ext_src_mode)
+  if (REG_P (SET_DEST (*sub_rtx))
+      && (GET_MODE (SET_DEST (*sub_rtx)) == ext_src_mode
+	  || ((state->modified[INSN_UID (def_insn)].kind
+	       == (cand->code == ZERO_EXTEND
+		   ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT))
+	      && state->modified[INSN_UID (def_insn)].mode
+		 == ext_src_mode)))
     {
-      return combine_set_extension (cand, def_insn, sub_rtx);
+      if (GET_MODE_SIZE (GET_MODE (SET_DEST (*sub_rtx)))
+	  >= GET_MODE_SIZE (cand->mode))
+	return true;
+      /* If def_insn is already scheduled to be deleted, don't attempt
+	 to modify it.  */
+      if (state->modified[INSN_UID (def_insn)].deleted)
+	return false;
+      if (combine_set_extension (cand, def_insn, sub_rtx))
+	{
+	  if (state->modified[INSN_UID (def_insn)].kind == EXT_MODIFIED_NONE)
+	    state->modified[INSN_UID (def_insn)].mode = ext_src_mode;
+	  return true;
+	}
     }
 
   return false;
@@ -596,48 +651,31 @@ merge_def_and_ext (ext_cand *cand, rtx def_insn)
    and false upon failure.  */
 
 static bool
-combine_reaching_defs (ext_cand *cand, rtx set_pat)
+combine_reaching_defs (ext_cand *cand, rtx set_pat, ext_state *state)
 {
   rtx def_insn;
   bool merge_successful = true;
   int i;
   int defs_ix;
-  int outcome;
-  VEC (rtx, heap) *defs_list, *copies_list, *vec;
-
-  defs_list = VEC_alloc (rtx, heap, 8);
-  copies_list = VEC_alloc (rtx, heap, 8);
+  bool outcome;
 
-  outcome = make_defs_and_copies_lists (cand->insn,
-                                        set_pat, &defs_list, &copies_list);
+  VEC_truncate (rtx, state->defs_list, 0);
+  VEC_truncate (rtx, state->copies_list, 0);
 
-  /* outcome == 2 means that all the definitions for this extension have been
-     previously merged when handling other extensions.  */
-  if (outcome == 2)
-    {
-      VEC_free (rtx, heap, defs_list);
-      VEC_free (rtx, heap, copies_list);
-      if (dump_file)
-        fprintf (dump_file, "All definitions have been previously merged.\n");
-      return true;
-    }
+  outcome = make_defs_and_copies_lists (cand->insn, set_pat, state);
 
-  if (outcome == 0)
-    {
-      VEC_free (rtx, heap, defs_list);
-      VEC_free (rtx, heap, copies_list);
-      return false;
-    }
+  if (!outcome)
+    return false;
 
   merge_successful = true;
 
   /* Go through the defs vector and try to merge all the definitions
      in this vector.  */
-  vec = VEC_alloc (rtx, heap, 8);
-  FOR_EACH_VEC_ELT (rtx, defs_list, defs_ix, def_insn)
+  VEC_truncate (rtx, state->modified_list, 0);
+  FOR_EACH_VEC_ELT (rtx, state->defs_list, defs_ix, def_insn)
     {
-      if (merge_def_and_ext (cand, def_insn))
-        VEC_safe_push (rtx, heap, vec, def_insn);
+      if (merge_def_and_ext (cand, def_insn, state))
+	VEC_safe_push (rtx, heap, state->modified_list, def_insn);
       else
         {
           merge_successful = false;
@@ -649,12 +687,10 @@ combine_reaching_defs (ext_cand *cand, rtx set_pat)
      the copies in this vector.  */
   if (merge_successful)
     {
-      FOR_EACH_VEC_ELT (rtx, copies_list, i, def_insn)
+      FOR_EACH_VEC_ELT (rtx, state->copies_list, i, def_insn)
         {
           if (transform_ifelse (cand, def_insn))
-            {
-              VEC_safe_push (rtx, heap, vec, def_insn);
-            }
+	    VEC_safe_push (rtx, heap, state->modified_list, def_insn);
           else
             {
               merge_successful = false;
@@ -675,9 +711,12 @@ combine_reaching_defs (ext_cand *cand, rtx set_pat)
           if (dump_file)
             fprintf (dump_file, "All merges were successful.\n");
 
-          VEC_free (rtx, heap, vec);
-          VEC_free (rtx, heap, defs_list);
-          VEC_free (rtx, heap, copies_list);
+	  FOR_EACH_VEC_ELT (rtx, state->modified_list, i, def_insn)
+	    if (state->modified[INSN_UID (def_insn)].kind == EXT_MODIFIED_NONE)
+	      state->modified[INSN_UID (def_insn)].kind
+		= (cand->code == ZERO_EXTEND
+		   ? EXT_MODIFIED_ZEXT : EXT_MODIFIED_SEXT);
+
           return true;
         }
       else
@@ -689,7 +728,7 @@ combine_reaching_defs (ext_cand *cand, rtx set_pat)
             {
 	      fprintf (dump_file,
 		       "Merge cancelled, non-mergeable definitions:\n");
-	      FOR_EACH_VEC_ELT (rtx, vec, i, def_insn)
+	      FOR_EACH_VEC_ELT (rtx, state->modified_list, i, def_insn)
 	        print_rtl_single (dump_file, def_insn);
             }
         }
@@ -700,10 +739,6 @@ combine_reaching_defs (ext_cand *cand, rtx set_pat)
       cancel_changes (0);
     }
 
-  VEC_free (rtx, heap, vec);
-  VEC_free (rtx, heap, defs_list);
-  VEC_free (rtx, heap, copies_list);
-
   return false;
 }
 
@@ -829,26 +864,30 @@ find_and_remove_re (void)
   int num_re_opportunities = 0, num_realized = 0, i;
   VEC (ext_cand, heap) *reinsn_list;
   VEC (rtx, heap) *reinsn_del_list;
+  ext_state state;
 
   /* Construct DU chain to get all reaching definitions of each
      extension instruction.  */
   df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN);
   df_analyze ();
+  df_set_flags (DF_DEFER_INSN_RESCAN);
 
   max_insn_uid = get_max_uid ();
-  reinsn_del_list = VEC_alloc (rtx, heap, 4);
+  reinsn_del_list = NULL;
   reinsn_list = find_removable_extensions ();
+  state.defs_list = NULL;
+  state.copies_list = NULL;
+  state.modified_list = NULL;
+  state.work_list = NULL;
+  if (VEC_empty (ext_cand, reinsn_list))
+    state.modified = NULL;
+  else
+    state.modified = XCNEWVEC (struct ext_modified, max_insn_uid);
 
   FOR_EACH_VEC_ELT (ext_cand, reinsn_list, i, curr_cand)
     {
       num_re_opportunities++;
 
-      /* If the candidate insn is itself a definition insn for another
-         candidate, it may have been modified and the UD chain broken.
-         FIXME: the handling of successive extensions can be improved.  */
-      if (!reg_mentioned_p (curr_cand->expr, PATTERN (curr_cand->insn)))
-	continue;
-
       /* Try to combine the extension with the definition.  */
       if (dump_file)
         {
@@ -856,12 +895,13 @@ find_and_remove_re (void)
           print_rtl_single (dump_file, curr_cand->insn);
         }
 
-      if (combine_reaching_defs (curr_cand, PATTERN (curr_cand->insn)))
+      if (combine_reaching_defs (curr_cand, PATTERN (curr_cand->insn), &state))
         {
           if (dump_file)
             fprintf (dump_file, "Eliminated the extension.\n");
           num_realized++;
           VEC_safe_push (rtx, heap, reinsn_del_list, curr_cand->insn);
+	  state.modified[INSN_UID (curr_cand->insn)].deleted = 1;
         }
     }
 
@@ -871,6 +911,11 @@ find_and_remove_re (void)
 
   VEC_free (ext_cand, heap, reinsn_list);
   VEC_free (rtx, heap, reinsn_del_list);
+  VEC_free (rtx, heap, state.defs_list);
+  VEC_free (rtx, heap, state.copies_list);
+  VEC_free (rtx, heap, state.modified_list);
+  VEC_free (rtx, heap, state.work_list);
+  XDELETEVEC (state.modified);
 
   if (dump_file && num_re_opportunities > 0)
     fprintf (dump_file, "Elimination opportunities = %d realized = %d\n",
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 65bea77..dee2c0d 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2012-01-23  Jakub Jelinek  <jakub@redhat.com>
+
+	PR rtl-optimization/51933
+	* gcc.c-torture/execute/pr51933.c: New test.
+
 2012-01-22  Douglas B Rupp  <rupp@gnat.com>
 
 	* gcc.dg/builtins-config.h (HAVE_C99_RUNTIME):
diff --git a/gcc/testsuite/gcc.c-torture/execute/pr51933.c b/gcc/testsuite/gcc.c-torture/execute/pr51933.c
new file mode 100644
index 0000000..a6556c9
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr51933.c
@@ -0,0 +1,51 @@
+/* PR rtl-optimization/51933 */
+
+static signed char v1;
+static unsigned char v2[256], v3[256];
+
+__attribute__((noclone, noinline)) void
+foo (void)
+{
+  asm volatile ("" : : "g" (&v1), "g" (&v2[0]), "g" (&v3[0]) : "memory");
+}
+
+__attribute__((noclone, noinline)) int
+bar (const int x, const unsigned short *y, char *z)
+{
+  int i;
+  unsigned short u;
+  if (!v1)
+    foo ();
+  for (i = 0; i < x; i++)
+    {
+      u = y[i];
+      z[i] = u < 0x0100 ? v2[u] : v3[u & 0xff];
+    }
+  z[x] = '\0';
+  return x;
+}
+
+int
+main (void)
+{
+  char buf[18];
+  unsigned short s[18];
+  unsigned char c[18] = "abcdefghijklmnopq";
+  int i;
+  for (i = 0; i < 256; i++)
+    {
+      v2[i] = i;
+      v3[i] = i + 1;
+    }
+  for (i = 0; i < 18; i++)
+    s[i] = c[i];
+  s[5] |= 0x600;
+  s[6] |= 0x500;
+  s[11] |= 0x2000;
+  s[15] |= 0x500;
+  foo ();
+  if (bar (17, s, buf) != 17
+      || __builtin_memcmp (buf, "abcdeghhijkmmnoqq", 18) != 0)
+    __builtin_abort ();
+  return 0;
+}