tree-optimization/117123 - missed PHI equivalence in VN

Value-numbering can use its set of equivalences to prove that
a PHI node with args <a_1, 5, 10> is equal to a_1 iff on the
edges with the constants a_1 == 5 and a_1 == 10 hold.  This
breaks down when the order of PHI args is <5, 10, a_1> as then
we drop to VARYING early.  The following mitigates this by
shuffling a copy of the edge vector to always process a SSA name
argument first.  Which should also handle the special-case of
a two argument <5, a_1> we already had.

	PR tree-optimization/117123
	* tree-ssa-sccvn.cc (visit_phi): First process a non-constant
	argument edge to handle more equivalences.  Remove the
	two-arg special case.

	* g++.dg/tree-ssa/pr117123.C: New testcase.

2 files changed, 77 insertions, 25 deletions

diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr117123.C b/gcc/testsuite/g++.dg/tree-ssa/pr117123.C
new file mode 100644
index 0000000..2aa2810
--- /dev/null
+++ b/gcc/testsuite/g++.dg/tree-ssa/pr117123.C
@@ -0,0 +1,52 @@
+// { dg-do compile }
+// { dg-options "-Os -fdump-tree-optimized" }
+
+struct Potato {
+  int size;
+  bool isMashed;
+};
+
+int dont_be_here();
+
+int patatino(int a) {
+  if (a > 5 && a % 2 == 0 && a != 10) {
+    return a * 2;
+  } else {
+    Potato spud;
+    spud.size = a;
+    spud.isMashed = false;
+
+    for (int i = 0; i < 10; i++) {
+      if (i > 10 && i < 5 && a == -1) {
+        for (int j = 0; j < 5; j++) {
+          spud.size += j;
+        }
+      }
+    }
+
+    for (int k = 0; k < 10 && a == -100 && spud.size > 1000; k++) {
+      for (int l = 0; l < 5; l++) {
+        spud.size += l * k;
+      }
+    }
+
+    for (int m = 0; m < 10 && a == -1000 && spud.size < -1000; m++) {
+      dont_be_here();
+    }
+
+    if (a > 10000 && spud.size < -10000) {
+      spud.size *= 2;
+    }
+
+    for (int n = 0; n < 10 && a == -2000 && spud.size > 2000; n++) {
+      for (int o = 0; o < 5; o++) {
+        spud.size -= o * n;
+      }
+    }
+
+    return spud.size;
+  }
+}
+
+// { dg-final { scan-tree-dump-not "dont_be_here" "optimized" } }
+// { dg-final { scan-tree-dump-times "if " 3 "optimized" } }
diff --git a/gcc/tree-ssa-sccvn.cc b/gcc/tree-ssa-sccvn.cc
index abf7d38..84a0c37 100644
--- a/gcc/tree-ssa-sccvn.cc
+++ b/gcc/tree-ssa-sccvn.cc
@@ -5948,8 +5948,7 @@ visit_phi (gimple *phi, bool *inserted, bool backedges_varying_p)
   tree sameval_base = NULL_TREE;
   poly_int64 soff, doff;
   unsigned n_executable = 0;
-  edge_iterator ei;
-  edge e, sameval_e = NULL;
+  edge sameval_e = NULL;
 
   /* TODO: We could check for this in initialization, and replace this
      with a gcc_assert.  */
@@ -5962,10 +5961,32 @@ visit_phi (gimple *phi, bool *inserted, bool backedges_varying_p)
   if (!inserted)
     gimple_set_plf (phi, GF_PLF_1, false);
 
+  basic_block bb = gimple_bb (phi);
+
+  /* For the equivalence handling below make sure to first process an
+     edge with a non-constant.  */
+  auto_vec<edge, 2> preds;
+  preds.reserve_exact (EDGE_COUNT (bb->preds));
+  bool seen_nonconstant = false;
+  for (unsigned i = 0; i < EDGE_COUNT (bb->preds); ++i)
+    {
+      edge e = EDGE_PRED (bb, i);
+      preds.quick_push (e);
+      if (!seen_nonconstant)
+	{
+	  tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
+	  if (TREE_CODE (def) == SSA_NAME)
+	    {
+	      seen_nonconstant = true;
+	      if (i != 0)
+		std::swap (preds[0], preds[i]);
+	    }
+	}
+    }
+
   /* See if all non-TOP arguments have the same value.  TOP is
      equivalent to everything, so we can ignore it.  */
-  basic_block bb = gimple_bb (phi);
-  FOR_EACH_EDGE (e, ei, bb->preds)
+  for (edge e : preds)
     if (e->flags & EDGE_EXECUTABLE)
       {
 	tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
@@ -6065,27 +6086,6 @@ visit_phi (gimple *phi, bool *inserted, bool backedges_varying_p)
 			  }
 			continue;
 		      }
-		    /* If on all previous edges the value was equal to def
-		       we can change sameval to def.  */
-		    if (EDGE_COUNT (bb->preds) == 2
-			&& (val = vn_nary_op_get_predicated_value
-				    (vnresult, EDGE_PRED (bb, 0)))
-			&& integer_truep (val)
-			&& !(e->flags & EDGE_DFS_BACK))
-		      {
-			if (dump_file && (dump_flags & TDF_DETAILS))
-			  {
-			    fprintf (dump_file, "Predication says ");
-			    print_generic_expr (dump_file, def, TDF_NONE);
-			    fprintf (dump_file, " and ");
-			    print_generic_expr (dump_file, sameval, TDF_NONE);
-			    fprintf (dump_file, " are equal on edge %d -> %d\n",
-				     EDGE_PRED (bb, 0)->src->index,
-				     EDGE_PRED (bb, 0)->dest->index);
-			  }
-			sameval = def;
-			continue;
-		      }
 		  }
 	      }
 	    sameval = NULL_TREE;