tree-ssa-sccvn.c: Include tree-cfg.h and domwalk.h.

2014-05-16  Richard Biener  <rguenther@suse.de>

	* tree-ssa-sccvn.c: Include tree-cfg.h and domwalk.h.
	(set_ssa_val_to): Handle unexpected sets to VN_TOP.
	(visit_phi): Ignore edges marked as not executable.
	(class cond_dom_walker): New.
	(cond_dom_walker::before_dom_children): Value-number
	control statements and mark successor edges as not
	executable if possible.
	(run_scc_vn): First walk all control statements in
	dominator order, marking edges as not executable.
	* tree-inline.c (copy_edges_for_bb): Be not confused
	about random edge flags.

	* gcc.dg/tree-ssa/ssa-fre-39.c: New testcase.
	* gcc.dg/tree-ssa/ssa-fre-40.c: Likewise.
	* gcc.dg/tree-ssa/ssa-pre-8.c: One more elimination.
	* gcc.dg/tree-ssa/struct-aliasing-2.c: Scan cddce1 dump.

From-SVN: r210492

8 files changed, 230 insertions, 35 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 3df0bb4..cc0d973 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,19 @@
 2014-05-16  Richard Biener  <rguenther@suse.de>
 
+	* tree-ssa-sccvn.c: Include tree-cfg.h and domwalk.h.
+	(set_ssa_val_to): Handle unexpected sets to VN_TOP.
+	(visit_phi): Ignore edges marked as not executable.
+	(class cond_dom_walker): New.
+	(cond_dom_walker::before_dom_children): Value-number
+	control statements and mark successor edges as not
+	executable if possible.
+	(run_scc_vn): First walk all control statements in
+	dominator order, marking edges as not executable.
+	* tree-inline.c (copy_edges_for_bb): Be not confused
+	about random edge flags.
+
+2014-05-16  Richard Biener  <rguenther@suse.de>
+
 	* tree-ssa-sccvn.c (visit_use): Also constant-fold calls.
 
 2014-05-15  Peter Bergner  <bergner@vnet.ibm.com>
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 8c52f8c..66d0694 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,12 @@
 2014-05-16  Richard Biener  <rguenther@suse.de>
 
+	* gcc.dg/tree-ssa/ssa-fre-39.c: New testcase.
+	* gcc.dg/tree-ssa/ssa-fre-40.c: Likewise.
+	* gcc.dg/tree-ssa/ssa-pre-8.c: One more elimination.
+	* gcc.dg/tree-ssa/struct-aliasing-2.c: Scan cddce1 dump.
+
+2014-05-16  Richard Biener  <rguenther@suse.de>
+
 	* gcc.dg/tree-ssa/ssa-fre-41.c: New testcase.
 
 2014-05-15  Martin Jambor  <mjambor@suse.cz>
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-39.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-39.c
new file mode 100644
index 0000000..a30926c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-39.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-fre1" } */
+
+int foo (int i)
+{
+  int k = i + 1;
+  int j = i + 1;
+  if (k != j)
+    k = k + 1;
+  if (k != j)
+    k = k + 1;
+  k = k - i;
+  return k;
+}
+
+/* We should be able to value-number the final assignment to k to 1.  */
+
+/* { dg-final { scan-tree-dump "k_. = 1;" "fre1" } } */
+/* { dg-final { cleanup-tree-dump "fre1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-40.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-40.c
new file mode 100644
index 0000000..dd085a0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-40.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-fre1" } */
+
+int x;
+int foo (int *p)
+{
+  x = 0;
+  if (x)
+    *p = 1;
+  return x;
+}
+
+/* The final load of x should be replaced as well as the
+   aliasing store via *p is not reachable.  */
+
+/* { dg-final { scan-tree-dump-not "= x;" "fre1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-8.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-8.c
index f08ef7f..dab57fa 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-8.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-8.c
@@ -17,7 +17,9 @@ foo (__SIZE_TYPE__ i, struct s *array)
   return 0;
 }
 /* We should eliminate two address calculations, and one load.  */
+/* We also elimiate the PHI node feeding the return because the case
+   returning 1 is unreachable.  */
 /* We used to eliminate a cast but that was before POINTER_PLUS_EXPR
    was added.  */
-/* { dg-final { scan-tree-dump-times "Eliminated: 3" 1 "fre1"} } */
+/* { dg-final { scan-tree-dump-times "Eliminated: 4" 1 "fre1"} } */
 /* { dg-final { cleanup-tree-dump "fre1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/struct-aliasing-2.c b/gcc/testsuite/gcc.dg/tree-ssa/struct-aliasing-2.c
index c348bdf..66a5442 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/struct-aliasing-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/struct-aliasing-2.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-fre1" } */
+/* { dg-options "-O2 -fdump-tree-cddce1" } */
 
 struct S { unsigned f; };
 
@@ -12,8 +12,8 @@ foo ( struct S *p)
 }
 
 
-/* There should only be one load of p->f because fwprop can change
-   *(int *)&p->f into just (int)p->f.  */
-/* { dg-final { scan-tree-dump-times "= \[^\n\]*p_.\\\(D\\\)" 1 "fre1" } } */
-/* { dg-final { cleanup-tree-dump "fre1" } } */
+/* There should only be one load of p->f because FRE removes the redundancy
+   by realizing it can cast the result of either to the other.  */
+/* { dg-final { scan-tree-dump-times "= \[^\n\]*p_.\\\(D\\\)" 1 "cddce1" } } */
+/* { dg-final { cleanup-tree-dump "cddce1" } } */
 
diff --git a/gcc/tree-inline.c b/gcc/tree-inline.c
index 9207e9f..bc2b271 100644
--- a/gcc/tree-inline.c
+++ b/gcc/tree-inline.c
@@ -1984,7 +1984,8 @@ copy_edges_for_bb (basic_block bb, gcov_type count_scale, basic_block ret_bb,
 	flags = old_edge->flags;
 
 	/* Return edges do get a FALLTHRU flag when the get inlined.  */
-	if (old_edge->dest->index == EXIT_BLOCK && !old_edge->flags
+	if (old_edge->dest->index == EXIT_BLOCK
+	    && !(old_edge->flags & (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE|EDGE_FAKE))
 	    && old_edge->dest->aux != EXIT_BLOCK_PTR_FOR_FN (cfun))
 	  flags |= EDGE_FALLTHRU;
 	new_edge = make_edge (new_bb, (basic_block) old_edge->dest->aux, flags);
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 93a7e30..84c0d6e 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -51,6 +51,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "params.h"
 #include "tree-ssa-propagate.h"
 #include "tree-ssa-sccvn.h"
+#include "tree-cfg.h"
+#include "domwalk.h"
 
 /* This algorithm is based on the SCC algorithm presented by Keith
    Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
@@ -2661,6 +2663,25 @@ set_ssa_val_to (tree from, tree to)
   tree currval = SSA_VAL (from);
   HOST_WIDE_INT toff, coff;
 
+  /* The only thing we allow as value numbers are ssa_names
+     and invariants.  So assert that here.  We don't allow VN_TOP
+     as visiting a stmt should produce a value-number other than
+     that.
+     ???  Still VN_TOP can happen for unreachable code, so force
+     it to varying in that case.  Not all code is prepared to
+     get VN_TOP on valueization.  */
+  if (to == VN_TOP)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Forcing value number to varying on "
+		 "receiving VN_TOP\n");
+      to = from;
+    }
+
+  gcc_assert (to != NULL_TREE
+	      && (TREE_CODE (to) == SSA_NAME
+		  || is_gimple_min_invariant (to)));
+
   if (from != to)
     {
       if (currval == from)
@@ -2680,13 +2701,6 @@ set_ssa_val_to (tree from, tree to)
 	to = from;
     }
 
-  /* The only thing we allow as value numbers are VN_TOP, ssa_names
-     and invariants.  So assert that here.  */
-  gcc_assert (to != NULL_TREE
-	      && (to == VN_TOP
-		  || TREE_CODE (to) == SSA_NAME
-		  || is_gimple_min_invariant (to)));
-
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "Setting value number of ");
@@ -3071,7 +3085,6 @@ visit_phi (gimple phi)
   tree result;
   tree sameval = VN_TOP;
   bool allsame = true;
-  unsigned i;
 
   /* TODO: We could check for this in init_sccvn, and replace this
      with a gcc_assert.  */
@@ -3080,27 +3093,30 @@ visit_phi (gimple phi)
 
   /* See if all non-TOP arguments have the same value.  TOP is
      equivalent to everything, so we can ignore it.  */
-  for (i = 0; i < gimple_phi_num_args (phi); i++)
-    {
-      tree def = PHI_ARG_DEF (phi, i);
+  edge_iterator ei;
+  edge e;
+  FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
+    if (e->flags & EDGE_EXECUTABLE)
+      {
+	tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
 
-      if (TREE_CODE (def) == SSA_NAME)
-	def = SSA_VAL (def);
-      if (def == VN_TOP)
-	continue;
-      if (sameval == VN_TOP)
-	{
-	  sameval = def;
-	}
-      else
-	{
-	  if (!expressions_equal_p (def, sameval))
-	    {
-	      allsame = false;
-	      break;
-	    }
-	}
-    }
+	if (TREE_CODE (def) == SSA_NAME)
+	  def = SSA_VAL (def);
+	if (def == VN_TOP)
+	  continue;
+	if (sameval == VN_TOP)
+	  {
+	    sameval = def;
+	  }
+	else
+	  {
+	    if (!expressions_equal_p (def, sameval))
+	      {
+		allsame = false;
+		break;
+	      }
+	  }
+      }
 
   /* If all value numbered to the same value, the phi node has that
      value.  */
@@ -4140,6 +4156,105 @@ set_hashtable_value_ids (void)
     set_value_id_for_result (vr->result, &vr->value_id);
 }
 
+class cond_dom_walker : public dom_walker
+{
+public:
+  cond_dom_walker () : dom_walker (CDI_DOMINATORS), fail (false) {}
+
+  virtual void before_dom_children (basic_block);
+
+  bool fail;
+};
+
+void
+cond_dom_walker::before_dom_children (basic_block bb)
+{
+  edge e;
+  edge_iterator ei;
+
+  if (fail)
+    return;
+
+  /* If any of the predecessor edges are still marked as possibly
+     executable consider this block reachable.  */
+  bool reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (cfun);
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    reachable |= (e->flags & EDGE_EXECUTABLE);
+
+  /* If the block is not reachable all outgoing edges are not
+     executable.  */
+  if (!reachable)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Marking all outgoing edges of unreachable "
+		 "BB %d as not executable\n", bb->index);
+
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	e->flags &= ~EDGE_EXECUTABLE;
+      return;
+    }
+
+  gimple stmt = last_stmt (bb);
+  if (!stmt)
+    return;
+
+  /* Value-number the last stmts SSA uses.  */
+  ssa_op_iter i;
+  tree op;
+  FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
+    if (VN_INFO (op)->visited == false
+	&& !DFS (op))
+      {
+	fail = true;
+	return;
+      }
+
+  /* ???  We can even handle stmts with outgoing EH or ABNORMAL edges
+     if value-numbering can prove they are not reachable.  Handling
+     computed gotos is also possible.  */
+  tree val;
+  switch (gimple_code (stmt))
+    {
+    case GIMPLE_COND:
+      {
+	tree lhs = gimple_cond_lhs (stmt);
+	tree rhs = gimple_cond_rhs (stmt);
+	/* Work hard in computing the condition and take into account
+	   the valueization of the defining stmt.  */
+	if (TREE_CODE (lhs) == SSA_NAME)
+	  lhs = vn_get_expr_for (lhs);
+	if (TREE_CODE (rhs) == SSA_NAME)
+	  rhs = vn_get_expr_for (rhs);
+	val = fold_binary (gimple_cond_code (stmt),
+			   boolean_type_node, lhs, rhs);
+	break;
+      }
+    case GIMPLE_SWITCH:
+      val = gimple_switch_index (stmt);
+      break;
+    case GIMPLE_GOTO:
+      val = gimple_goto_dest (stmt);
+      break;
+    default:
+      val = NULL_TREE;
+      break;
+    }
+  if (!val)
+    return;
+
+  edge taken = find_taken_edge (bb, vn_valueize (val));
+  if (!taken)
+    return;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Marking all edges out of BB %d but (%d -> %d) as "
+	     "not executable\n", bb->index, bb->index, taken->dest->index);
+
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    if (e != taken)
+      e->flags &= ~EDGE_EXECUTABLE;
+}
+
 /* Do SCCVN.  Returns true if it finished, false if we bailed out
    due to resource constraints.  DEFAULT_VN_WALK_KIND_ specifies
    how we use the alias oracle walking during the VN process.  */
@@ -4147,6 +4262,7 @@ set_hashtable_value_ids (void)
 bool
 run_scc_vn (vn_lookup_kind default_vn_walk_kind_)
 {
+  basic_block bb;
   size_t i;
   tree param;
 
@@ -4164,6 +4280,26 @@ run_scc_vn (vn_lookup_kind default_vn_walk_kind_)
 	VN_INFO (def)->valnum = def;
     }
 
+  /* Mark all edges as possibly executable.  */
+  FOR_ALL_BB_FN (bb, cfun)
+    {
+      edge_iterator ei;
+      edge e;
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	e->flags |= EDGE_EXECUTABLE;
+    }
+
+  /* Walk all blocks in dominator order, value-numbering the last stmts
+     SSA uses and decide whether outgoing edges are not executable.  */
+  cond_dom_walker walker;
+  walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+  if (walker.fail)
+    {
+      free_scc_vn ();
+      return false;
+    }
+
+  /* Value-number remaining SSA names.  */
   for (i = 1; i < num_ssa_names; ++i)
     {
       tree name = ssa_name (i);