2017-10-23 Richard Biener <rguenther@suse.de>

	PR tree-optimization/82129
	* tree-ssa-pre.c (bitmap_set_and): Remove.
	(compute_antic_aux): Compute ANTIC_OUT intersection in a way
	canonicalizing expressions in the set to those with lowest
	ID rather than taking that from the first edge.

	* gcc.dg/torture/pr82129.c: New testcase.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@253998 138bc75d-0d04-0410-961f-82ee72b054a4

4 files changed, 104 insertions, 33 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 6caddb801b7..28052db569f 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@
+2017-10-23  Richard Biener  <rguenther@suse.de>
+
+	PR tree-optimization/82129
+	* tree-ssa-pre.c (bitmap_set_and): Remove.
+	(compute_antic_aux): Compute ANTIC_OUT intersection in a way
+	canonicalizing expressions in the set to those with lowest
+	ID rather than taking that from the first edge.
+
 2017-10-23  Richard Sandiford  <richard.sandiford@linaro.org>
 
 	* combine.c (rtx_equal_for_field_assignment_p): Use
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index f14930b6e11..9ca1131a65b 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2017-10-23  Richard Biener  <rguenther@suse.de>
+
+	PR tree-optimization/82129
+	* gcc.dg/torture/pr82129.c: New testcase.
+
 2017-10-22  Uros Bizjak  <ubizjak@gmail.com>
 
 	PR target/52451
diff --git a/gcc/testsuite/gcc.dg/torture/pr82129.c b/gcc/testsuite/gcc.dg/torture/pr82129.c
new file mode 100644
index 00000000000..b1161491fe6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr82129.c
@@ -0,0 +1,52 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-ftree-pre" } */
+
+int pj;
+
+void
+g4 (unsigned long int *bc, unsigned long int *h5)
+{
+  if (pj != 0)
+    {
+      int ib = 0;
+
+      while (bc != 0)
+	{
+m6:
+	  for (pj = 0; pj < 2; ++pj)
+	    pj = 0;
+
+	  while (pj != 0)
+	    {
+	      for (;;)
+		{
+		}
+
+	      while (ib != 0)
+		{
+		  unsigned long int tv = *bc;
+		  unsigned long int n7;
+
+		  *bc = 1;
+		  while (*bc != 0)
+		    {
+		    }
+
+ut:
+		  if (pj == 0)
+		    n7 = *h5 > 0;
+		  else
+		    {
+		      *h5 = tv;
+		      n7 = *h5;
+		    }
+		  ib += n7;
+		}
+	    }
+	}
+
+      goto ut;
+    }
+
+  goto m6;
+}
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 5eb47a9d6d5..4861a4c231f 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -537,7 +537,6 @@ static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int);
 static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
 static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
-static void bitmap_set_and (bitmap_set_t, bitmap_set_t);
 static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
 static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
 static bitmap_set_t bitmap_set_new (void);
@@ -800,36 +799,6 @@ sorted_array_from_bitmap_set (bitmap_set_t set)
   return result;
 }
 
-/* Perform bitmapped set operation DEST &= ORIG.  */
-
-static void
-bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
-{
-  bitmap_iterator bi;
-  unsigned int i;
-
-  if (dest != orig)
-    {
-      bitmap_and_into (&dest->values, &orig->values);
-
-      unsigned int to_clear = -1U;
-      FOR_EACH_EXPR_ID_IN_SET (dest, i, bi)
-	{
-	  if (to_clear != -1U)
-	    {
-	      bitmap_clear_bit (&dest->expressions, to_clear);
-	      to_clear = -1U;
-	    }
-	  pre_expr expr = expression_for_id (i);
-	  unsigned int value_id = get_expr_value_id (expr);
-	  if (!bitmap_bit_p (&dest->values, value_id))
-	    to_clear = i;
-	}
-      if (to_clear != -1U)
-	bitmap_clear_bit (&dest->expressions, to_clear);
-    }
-}
-
 /* Subtract all expressions contained in ORIG from DEST.  */
 
 static bitmap_set_t
@@ -2182,17 +2151,54 @@ compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
 
       phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
 
+      /* If we have multiple successors we need to intersect the ANTIC_OUT
+         sets.  For values that's a simple intersection but for
+	 expressions it is a union.  Given we want to have a single
+	 expression per value in our sets we have to canonicalize.
+	 Avoid randomness and running into cycles like for PR82129 and
+	 canonicalize the expression we choose to the one with the
+	 lowest id.  This requires we actually compute the union first.  */
       FOR_EACH_VEC_ELT (worklist, i, bprime)
 	{
 	  if (!gimple_seq_empty_p (phi_nodes (bprime)))
 	    {
 	      bitmap_set_t tmp = bitmap_set_new ();
 	      phi_translate_set (tmp, ANTIC_IN (bprime), block, bprime);
-	      bitmap_set_and (ANTIC_OUT, tmp);
+	      bitmap_and_into (&ANTIC_OUT->values, &tmp->values);
+	      bitmap_ior_into (&ANTIC_OUT->expressions, &tmp->expressions);
 	      bitmap_set_free (tmp);
 	    }
 	  else
-	    bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
+	    {
+	      bitmap_and_into (&ANTIC_OUT->values, &ANTIC_IN (bprime)->values);
+	      bitmap_ior_into (&ANTIC_OUT->expressions,
+			       &ANTIC_IN (bprime)->expressions);
+	    }
+	}
+      if (! worklist.is_empty ())
+	{
+	  /* Prune expressions not in the value set, canonicalizing to
+	     expression with lowest ID.  */
+	  bitmap_iterator bi;
+	  unsigned int i;
+	  unsigned int to_clear = -1U;
+	  bitmap seen_value = BITMAP_ALLOC (NULL);
+	  FOR_EACH_EXPR_ID_IN_SET (ANTIC_OUT, i, bi)
+	    {
+	      if (to_clear != -1U)
+		{
+		  bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
+		  to_clear = -1U;
+		}
+	      pre_expr expr = expression_for_id (i);
+	      unsigned int value_id = get_expr_value_id (expr);
+	      if (!bitmap_bit_p (&ANTIC_OUT->values, value_id)
+		  || !bitmap_set_bit (seen_value, value_id))
+		to_clear = i;
+	    }
+	  if (to_clear != -1U)
+	    bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
+	  BITMAP_FREE (seen_value);
 	}
     }