re PR tree-optimization/67975 (Failure to optimise equality between two call sequences)

2015-10-19  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/67975
	* tree-cfg.h (extract_true_false_controlled_edges): Declare.
	* tree-cfg.c (extract_true_false_controlled_edges): Split out
	core worker from ...
	* tree-ssa-loop-im.c (extract_true_false_args_from_phi): ... here.
	* tree-ssa-sccvn.c (vn_phi_compute_hash): Hash number of args
	instead of block number for PHIs with two or one args.
	(vn_phi_eq): Compare edge predicates of PHIs that are in different
	blocks.

	* gcc.dg/tree-ssa/ssa-fre-50.c: New testcase.

From-SVN: r228971

7 files changed, 196 insertions, 64 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index ed0f4ce..89a42c1 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,17 @@
 2015-10-19  Richard Biener  <rguenther@suse.de>
 
+	PR tree-optimization/67975
+	* tree-cfg.h (extract_true_false_controlled_edges): Declare.
+	* tree-cfg.c (extract_true_false_controlled_edges): Split out
+	core worker from ...
+	* tree-ssa-loop-im.c (extract_true_false_args_from_phi): ... here.
+	* tree-ssa-sccvn.c (vn_phi_compute_hash): Hash number of args
+	instead of block number for PHIs with two or one args.
+	(vn_phi_eq): Compare edge predicates of PHIs that are in different
+	blocks.
+
+2015-10-19  Richard Biener  <rguenther@suse.de>
+
 	* gimple-fold.c (gimple_phi_nonnegative_warnv_p): New function.
 	(gimple_stmt_nonnegative_warnv_p): Use it.
 	* match.pd (CPROJ): New operator list.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index a5c3aa6..c4e96a7 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,10 @@
 2015-10-19  Richard Biener  <rguenther@suse.de>
 
+	PR tree-optimization/67975
+	* gcc.dg/tree-ssa/ssa-fre-50.c: New testcase.
+
+2015-10-19  Richard Biener  <rguenther@suse.de>
+
 	* gcc.dg/torture/builtin-cproj-1.c: Skip for -O0.
 
 2015-10-19  H.J. Lu  <hongjiu.lu@intel.com>
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-50.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-50.c
new file mode 100644
index 0000000..9155f8c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-50.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O -ffinite-math-only -fdump-tree-fre1" } */
+
+extern double cos (double);
+extern double tan (double);
+
+int
+f1 (double x, double y)
+{
+  double z1 = cos(y<10 ? x : tan(x<20 ? x : y));
+  double z2 = cos(y<10 ? x : tan(x<20 ? x : y));
+  return z1 == z2;
+}
+
+/* { dg-final { scan-tree-dump "return 1;" "fre1" } } */
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index 735ac46..5bf546e 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -8532,6 +8532,75 @@ extract_true_false_edges_from_block (basic_block b,
     }
 }
 
+
+/* From a controlling predicate in the immediate dominator DOM of
+   PHIBLOCK determine the edges into PHIBLOCK that are chosen if the
+   predicate evaluates to true and false and store them to
+   *TRUE_CONTROLLED_EDGE and *FALSE_CONTROLLED_EDGE if
+   they are non-NULL.  Returns true if the edges can be determined,
+   else return false.  */
+
+bool
+extract_true_false_controlled_edges (basic_block dom, basic_block phiblock,
+				     edge *true_controlled_edge,
+				     edge *false_controlled_edge)
+{
+  basic_block bb = phiblock;
+  edge true_edge, false_edge, tem;
+  edge e0 = NULL, e1 = NULL;
+
+  /* We have to verify that one edge into the PHI node is dominated
+     by the true edge of the predicate block and the other edge
+     dominated by the false edge.  This ensures that the PHI argument
+     we are going to take is completely determined by the path we
+     take from the predicate block.
+     We can only use BB dominance checks below if the destination of
+     the true/false edges are dominated by their edge, thus only
+     have a single predecessor.  */
+  extract_true_false_edges_from_block (dom, &true_edge, &false_edge);
+  tem = EDGE_PRED (bb, 0);
+  if (tem == true_edge
+      || (single_pred_p (true_edge->dest)
+	  && (tem->src == true_edge->dest
+	      || dominated_by_p (CDI_DOMINATORS,
+				 tem->src, true_edge->dest))))
+    e0 = tem;
+  else if (tem == false_edge
+	   || (single_pred_p (false_edge->dest)
+	       && (tem->src == false_edge->dest
+		   || dominated_by_p (CDI_DOMINATORS,
+				      tem->src, false_edge->dest))))
+    e1 = tem;
+  else
+    return false;
+  tem = EDGE_PRED (bb, 1);
+  if (tem == true_edge
+      || (single_pred_p (true_edge->dest)
+	  && (tem->src == true_edge->dest
+	      || dominated_by_p (CDI_DOMINATORS,
+				 tem->src, true_edge->dest))))
+    e0 = tem;
+  else if (tem == false_edge
+	   || (single_pred_p (false_edge->dest)
+	       && (tem->src == false_edge->dest
+		   || dominated_by_p (CDI_DOMINATORS,
+				      tem->src, false_edge->dest))))
+    e1 = tem;
+  else
+    return false;
+  if (!e0 || !e1)
+    return false;
+
+  if (true_controlled_edge)
+    *true_controlled_edge = e0;
+  if (false_controlled_edge)
+    *false_controlled_edge = e1;
+
+  return true;
+}
+
+
+
 /* Emit return warnings.  */
 
 namespace {
diff --git a/gcc/tree-cfg.h b/gcc/tree-cfg.h
index 855077a..1bfa5c4 100644
--- a/gcc/tree-cfg.h
+++ b/gcc/tree-cfg.h
@@ -105,5 +105,7 @@ extern unsigned int execute_fixup_cfg (void);
 extern unsigned int split_critical_edges (void);
 extern basic_block insert_cond_bb (basic_block, gimple *, gimple *);
 extern bool gimple_find_sub_bbs (gimple_seq, gimple_stmt_iterator *);
+extern bool extract_true_false_controlled_edges (basic_block, basic_block,
+						 edge *, edge *);
 
 #endif /* _TREE_CFG_H  */
diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
index 603e6d4..0598c18 100644
--- a/gcc/tree-ssa-loop-im.c
+++ b/gcc/tree-ssa-loop-im.c
@@ -619,56 +619,15 @@ static bool
 extract_true_false_args_from_phi (basic_block dom, gphi *phi,
 				  tree *true_arg_p, tree *false_arg_p)
 {
-  basic_block bb = gimple_bb (phi);
-  edge true_edge, false_edge, tem;
-  tree arg0 = NULL_TREE, arg1 = NULL_TREE;
-
-  /* We have to verify that one edge into the PHI node is dominated
-     by the true edge of the predicate block and the other edge
-     dominated by the false edge.  This ensures that the PHI argument
-     we are going to take is completely determined by the path we
-     take from the predicate block.
-     We can only use BB dominance checks below if the destination of
-     the true/false edges are dominated by their edge, thus only
-     have a single predecessor.  */
-  extract_true_false_edges_from_block (dom, &true_edge, &false_edge);
-  tem = EDGE_PRED (bb, 0);
-  if (tem == true_edge
-      || (single_pred_p (true_edge->dest)
-	  && (tem->src == true_edge->dest
-	      || dominated_by_p (CDI_DOMINATORS,
-				 tem->src, true_edge->dest))))
-    arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
-  else if (tem == false_edge
-	   || (single_pred_p (false_edge->dest)
-	       && (tem->src == false_edge->dest
-		   || dominated_by_p (CDI_DOMINATORS,
-				      tem->src, false_edge->dest))))
-    arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
-  else
-    return false;
-  tem = EDGE_PRED (bb, 1);
-  if (tem == true_edge
-      || (single_pred_p (true_edge->dest)
-	  && (tem->src == true_edge->dest
-	      || dominated_by_p (CDI_DOMINATORS,
-				 tem->src, true_edge->dest))))
-    arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
-  else if (tem == false_edge
-	   || (single_pred_p (false_edge->dest)
-	       && (tem->src == false_edge->dest
-		   || dominated_by_p (CDI_DOMINATORS,
-				      tem->src, false_edge->dest))))
-    arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
-  else
-    return false;
-  if (!arg0 || !arg1)
+  edge te, fe;
+  if (! extract_true_false_controlled_edges (dom, gimple_bb (phi),
+					     &te, &fe))
     return false;
 
   if (true_arg_p)
-    *true_arg_p = arg0;
+    *true_arg_p = PHI_ARG_DEF (phi, te->dest_idx);
   if (false_arg_p)
-    *false_arg_p = arg1;
+    *false_arg_p = PHI_ARG_DEF (phi, fe->dest_idx);
 
   return true;
 }
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index f2eb213..c57fb25 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -2658,7 +2658,8 @@ vn_nary_op_insert_stmt (gimple *stmt, tree result)
 static inline hashval_t
 vn_phi_compute_hash (vn_phi_t vp1)
 {
-  inchash::hash hstate (vp1->block->index);
+  inchash::hash hstate (vp1->phiargs.length () > 2
+			? vp1->block->index : vp1->phiargs.length ());
   tree phi1op;
   tree type;
   edge e;
@@ -2685,6 +2686,7 @@ vn_phi_compute_hash (vn_phi_t vp1)
   return hstate.end ();
 }
 
+
 /* Compare two phi entries for equality, ignoring VN_TOP arguments.  */
 
 static int
@@ -2693,29 +2695,97 @@ vn_phi_eq (const_vn_phi_t const vp1, const_vn_phi_t const vp2)
   if (vp1->hashcode != vp2->hashcode)
     return false;
 
-  if (vp1->block == vp2->block)
+  if (vp1->block != vp2->block)
     {
-      int i;
-      tree phi1op;
-
-      /* If the PHI nodes do not have compatible types
-	 they are not the same.  */
-      if (!types_compatible_p (vp1->type, vp2->type))
+      if (vp1->phiargs.length () != vp2->phiargs.length ())
 	return false;
 
-      /* Any phi in the same block will have it's arguments in the
-	 same edge order, because of how we store phi nodes.  */
-      FOR_EACH_VEC_ELT (vp1->phiargs, i, phi1op)
+      switch (vp1->phiargs.length ())
 	{
-	  tree phi2op = vp2->phiargs[i];
-	  if (phi1op == VN_TOP || phi2op == VN_TOP)
-	    continue;
-	  if (!expressions_equal_p (phi1op, phi2op))
-	    return false;
+	case 1:
+	  /* Single-arg PHIs are just copies.  */
+	  break;
+
+	case 2:
+	  {
+	    /* Rule out backedges into the PHI.  */
+	    if (vp1->block->loop_father->header == vp1->block
+		|| vp2->block->loop_father->header == vp2->block)
+	      return false;
+
+	    /* If the PHI nodes do not have compatible types
+	       they are not the same.  */
+	    if (!types_compatible_p (vp1->type, vp2->type))
+	      return false;
+
+	    basic_block idom1
+	      = get_immediate_dominator (CDI_DOMINATORS, vp1->block);
+	    basic_block idom2
+	      = get_immediate_dominator (CDI_DOMINATORS, vp2->block);
+	    /* If the immediate dominator end in switch stmts multiple
+	       values may end up in the same PHI arg via intermediate
+	       CFG merges.  */
+	    if (EDGE_COUNT (idom1->succs) != 2
+		|| EDGE_COUNT (idom2->succs) != 2)
+	      return false;
+
+	    /* Verify the controlling stmt is the same.  */
+	    gimple *last1 = last_stmt (idom1);
+	    gimple *last2 = last_stmt (idom2);
+	    if (gimple_code (last1) != GIMPLE_COND
+		|| gimple_code (last2) != GIMPLE_COND)
+	      return false;
+	    gcond *cond1 = as_a <gcond *> (last1);
+	    gcond *cond2 = as_a <gcond *> (last2);
+	    if (gimple_cond_code (cond1) != gimple_cond_code (cond2)
+		|| ! expressions_equal_p (gimple_cond_lhs (cond1),
+				       gimple_cond_lhs (cond2))
+		|| ! expressions_equal_p (gimple_cond_rhs (cond1),
+					  gimple_cond_rhs (cond2)))
+	      return false;
+
+	    /* Get at true/false controlled edges into the PHI.  */
+	    edge te1, te2, fe1, fe2;
+	    if (! extract_true_false_controlled_edges (idom1, vp1->block,
+						       &te1, &fe1)
+		|| ! extract_true_false_controlled_edges (idom2, vp2->block,
+							  &te2, &fe2))
+	      return false;
+
+	    /* ???  Handle VN_TOP specially.  */
+	    if (! expressions_equal_p (vp1->phiargs[te1->dest_idx],
+				       vp2->phiargs[te2->dest_idx])
+		|| ! expressions_equal_p (vp1->phiargs[fe1->dest_idx],
+					  vp2->phiargs[fe2->dest_idx]))
+	      return false;
+
+	    return true;
+	  }
+
+	default:
+	  return false;
 	}
-      return true;
     }
-  return false;
+
+  /* If the PHI nodes do not have compatible types
+     they are not the same.  */
+  if (!types_compatible_p (vp1->type, vp2->type))
+    return false;
+
+  /* Any phi in the same block will have it's arguments in the
+     same edge order, because of how we store phi nodes.  */
+  int i;
+  tree phi1op;
+  FOR_EACH_VEC_ELT (vp1->phiargs, i, phi1op)
+    {
+      tree phi2op = vp2->phiargs[i];
+      if (phi1op == VN_TOP || phi2op == VN_TOP)
+	continue;
+      if (!expressions_equal_p (phi1op, phi2op))
+	return false;
+    }
+
+  return true;
 }
 
 static vec<tree> shared_lookup_phiargs;