re PR tree-optimization/42142 (DCE miscompiles a certain quicksort implementation when optimizing with -O1 or higher)

2009-11-24  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/42142
	* tree-ssa-dce.c (mark_aliased_reaching_defs_necessary_1):
	Handle iv-dependent (non-)kills properly.
	(mark_aliased_reaching_defs_necessary): Pass the basic-block
	of the reference statement to mark_aliased_reaching_defs_necessary_1.

	* gcc.c-torture/execute/pr42142.c: New testcase.

From-SVN: r154494

4 files changed, 49 insertions, 4 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d05e456..e13a3b2 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@
+2009-11-24  Richard Guenther  <rguenther@suse.de>
+
+	PR tree-optimization/42142
+	* tree-ssa-dce.c (mark_aliased_reaching_defs_necessary_1):
+	Handle iv-dependent (non-)kills properly.
+	(mark_aliased_reaching_defs_necessary): Pass the basic-block
+	of the reference statement to mark_aliased_reaching_defs_necessary_1.
+
 2009-11-24  Martin Jambor  <mjambor@suse.cz>
 
 	PR tree-optimization/42154
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 7ad8ae9..9e1ff85 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2009-11-24  Richard Guenther  <rguenther@suse.de>
+
+	PR tree-optimization/42142
+	* gcc.c-torture/execute/pr42142.c: New testcase.
+
 2009-11-24  Martin Jambor  <mjambor@suse.cz>
 
 	PR tree-optimization/42154
diff --git a/gcc/testsuite/gcc.c-torture/execute/pr42142.c b/gcc/testsuite/gcc.c-torture/execute/pr42142.c
new file mode 100644
index 0000000..43cf57e
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr42142.c
@@ -0,0 +1,26 @@
+int __attribute__((noinline,noclone))
+sort(int L)
+{
+  int end[2] = { 10, 10, }, i=0, R;
+  while (i<2)
+    {
+      R = end[i];
+      if (L<R)
+        {
+          end[i+1] = 1;
+          end[i] = 10;
+          ++i;
+        }
+      else
+        break;
+    }
+  return i;
+}
+extern void abort (void);
+int main()
+{
+  if (sort (5) != 1)
+    abort ();
+  return 0;
+}
+
diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c
index f0135a9..056b7b5 100644
--- a/gcc/tree-ssa-dce.c
+++ b/gcc/tree-ssa-dce.c
@@ -495,11 +495,11 @@ static bool chain_ovfl = false;
    which is based on a non-aliased decl, necessary.  It returns
    true whenever the defining statement of the current VDEF is
    a kill for REF, as no dominating may-defs are necessary for REF
-   anymore.  DATA points to cached get_ref_base_and_extent data for REF.  */
+   anymore.  DATA points to the basic-block that contains the
+   stmt that refers to REF.  */
 
 static bool
-mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef,
-					void *data ATTRIBUTE_UNUSED)
+mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data)
 {
   gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
 
@@ -529,6 +529,12 @@ mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef,
 	    }
 	  /* Or they need to be exactly the same.  */
 	  else if (ref->ref
+		   /* Make sure there is no induction variable involved
+		      in the references (gcc.c-torture/execute/pr42142.c).
+		      The simplest way is to check if the kill dominates
+		      the use.  */
+		   && dominated_by_p (CDI_DOMINATORS, (basic_block) data,
+				      gimple_bb (def_stmt))
 		   && operand_equal_p (ref->ref, lhs, 0))
 	    return true;
 	}
@@ -547,7 +553,7 @@ mark_aliased_reaching_defs_necessary (gimple stmt, tree ref)
   ao_ref_init (&refd, ref);
   chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
 			      mark_aliased_reaching_defs_necessary_1,
-			      NULL, NULL);
+			      gimple_bb (stmt), NULL);
   if (chain > longest_chain)
     longest_chain = chain;
   total_chain += chain;