Merge evrp dom walker with substitute_and_fold engine.

6 files changed, 178 insertions, 6 deletions

diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c
index 599e145..af953cb 100644
--- a/gcc/gimple-ssa-evrp.c
+++ b/gcc/gimple-ssa-evrp.c
@@ -310,6 +310,68 @@ evrp_dom_walker::cleanup (void)
   evrp_folder.vr_values->cleanup_edges_and_switches ();
 }
 
+class xevrp_folder : public substitute_and_fold_engine
+{
+public:
+  xevrp_folder () : range_analyzer (true)
+  {
+    vr_values = range_analyzer.get_vr_values ();
+  }
+
+  ~xevrp_folder ()
+  {
+    if (dump_file)
+      {
+	fprintf (dump_file, "\nValue ranges after Early VRP:\n\n");
+	range_analyzer.dump_all_value_ranges (dump_file);
+	fprintf (dump_file, "\n");
+      }
+    vr_values->cleanup_edges_and_switches ();
+  }
+
+  tree get_value (tree op)
+  {
+    return vr_values->op_with_constant_singleton_value_range (op);
+  }
+
+  void pre_fold_bb (basic_block bb)
+  {
+    if (dump_file && (dump_flags & TDF_DETAILS))
+      fprintf (dump_file, "Visiting BB%d\n", bb->index);
+    range_analyzer.enter (bb);
+  }
+
+  void pre_fold_stmt (gimple *stmt)
+  {
+    if (dump_file && (dump_flags & TDF_DETAILS))
+      {
+	fprintf (dump_file, "Visiting stmt ");
+	print_gimple_stmt (dump_file, stmt, 0);
+      }
+    range_analyzer.record_ranges_from_stmt (stmt, false);
+  }
+
+  bool fold_stmt (gimple_stmt_iterator *gsi)
+  {
+    return vr_values->simplify_stmt_using_ranges (gsi);
+  }
+
+  void post_fold_bb (basic_block bb)
+  {
+    range_analyzer.leave (bb);
+  }
+
+  void post_fold_stmt (gimple *stmt)
+  {
+    range_analyzer.get_vr_values ()->set_defs_to_varying (stmt);
+  }
+
+private:
+  DISABLE_COPY_AND_ASSIGN (xevrp_folder);
+  class vr_values *vr_values;
+  class evrp_range_analyzer range_analyzer;
+};
+
 /* Main entry point for the early vrp pass which is a simplified non-iterative
    version of vrp where basic blocks are visited in dominance order.  Value
    ranges discovered in early vrp will also be used by ipa-vrp.  */
@@ -326,10 +388,16 @@ execute_early_vrp ()
   scev_initialize ();
   calculate_dominance_info (CDI_DOMINATORS);
 
+  xevrp_folder folder;
+  folder.substitute_and_fold ();
+
+  if (0)
+    {
   /* Walk stmts in dominance order and propagate VRP.  */
   evrp_dom_walker walker;
   walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
   walker.cleanup ();
+    }
 
   scev_finalize ();
   loop_optimizer_finalize ();
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-30.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-30.c
index 1d1fe82..ed7f7ee 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-30.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-30.c
@@ -8,9 +8,8 @@ void test_bcopy (const void *s)
 {
   char d[33];
 
-  /* Bcopy is transformed into memmove and those calls are expanded
-     inline in EVRP, before DSE runs, so this test doesn't actually
-     verify that DSE does its job.  */
+  /* Bcopy is transformed into memmove before DSE runs, so this test
+     doesn't actually verify that DSE does its job.  */
   __builtin_bcopy (s, d, sizeof d);
   __builtin_bcopy (s, d, sizeof d);
 
@@ -28,4 +27,17 @@ void test_bzero (void)
 }
 
 /* { dg-final { scan-tree-dump-times "builtin_memset" 1 "dse1" } } */
-/* { dg-final { scan-tree-dump-not "builtin_(bcopy|bzero|memcpy|memmove)" "dse1" } } */
+
+/* Merging the evrp folder into substitute_and_fold_engine shuffled
+   the order of gimple_fold a bit, so evrp is no longer folding the
+   memmove inline.  This folding is instead done by forwprop.  Thus, I
+   have remmoved the |memmove in the test below as this is not done
+   until after dse.
+
+   What happened was that the propagator engine only called gimple
+   fold if replace_uses_in() was successful.  On the other hand, EVRP
+   called gimple fold regardless.
+
+   If we really care about previous behavior, we could put a call to
+   gimple ::fold_stmt into xevrp_folder::fold_stmt().  */
+/* { dg-final { scan-tree-dump-not "builtin_(bcopy|bzero|memcpy)" "dse1" } } */
diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c
index 06d4b2a..d86b4f88 100644
--- a/gcc/tree-ssa-propagate.c
+++ b/gcc/tree-ssa-propagate.c
@@ -982,7 +982,10 @@ public:
     }
 
     virtual edge before_dom_children (basic_block);
-    virtual void after_dom_children (basic_block) {}
+    virtual void after_dom_children (basic_block bb)
+    {
+      substitute_and_fold_engine->post_fold_bb (bb);
+    }
 
     bool something_changed;
     vec<gimple *> stmts_to_remove;
@@ -990,11 +993,58 @@ public:
     bitmap need_eh_cleanup;
 
     class substitute_and_fold_engine *substitute_and_fold_engine;
+private:
+    void massage_new_statments (gimple_stmt_iterator old_gsi,
+				gimple_stmt_iterator new_gsi);
 };
 
+void
+substitute_and_fold_dom_walker::massage_new_statments
+				(gimple_stmt_iterator old_gsi,
+				 gimple_stmt_iterator new_gsi)
+{
+  basic_block bb = gsi_bb (new_gsi);
+  if (gsi_end_p (old_gsi))
+    old_gsi = gsi_start_bb (bb);
+  else
+    gsi_next (&old_gsi);
+  while (gsi_stmt (old_gsi) != gsi_stmt (new_gsi))
+    {
+      gimple *stmt = gsi_stmt (old_gsi);
+      substitute_and_fold_engine->post_fold_stmt (stmt);
+      gsi_next (&old_gsi);
+    }
+}
+
+void
+substitute_and_fold_engine::propagate_into_phi_args (basic_block bb)
+{
+  edge e;
+  edge_iterator ei;
+  /* Visit BB successor PHI nodes and replace PHI args.  */
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    {
+      for (gphi_iterator gpi = gsi_start_phis (e->dest);
+	   !gsi_end_p (gpi); gsi_next (&gpi))
+	{
+	  gphi *phi = gpi.phi ();
+	  use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
+	  tree arg = USE_FROM_PTR (use_p);
+	  if (TREE_CODE (arg) != SSA_NAME
+	      || virtual_operand_p (arg))
+	    continue;
+	  tree val = get_value (arg);
+	  if (val && may_propagate_copy (arg, val))
+	    propagate_value (use_p, val);
+	}
+    }
+}
+
 edge
 substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
 {
+  substitute_and_fold_engine->pre_fold_bb (bb);
+
   /* Propagate known values into PHI nodes.  */
   for (gphi_iterator i = gsi_start_phis (bb);
        !gsi_end_p (i);
@@ -1027,6 +1077,8 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
       bool did_replace;
       gimple *stmt = gsi_stmt (i);
 
+      substitute_and_fold_engine->pre_fold_stmt (stmt);
+
       /* No point propagating into a stmt we have a value for we
          can propagate into all uses.  Mark it for removal instead.  */
       tree lhs = gimple_get_lhs (stmt);
@@ -1063,6 +1115,9 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
       /* Replace real uses in the statement.  */
       did_replace |= substitute_and_fold_engine->replace_uses_in (stmt);
 
+      gimple_stmt_iterator prev_gsi = i;
+      gsi_prev (&prev_gsi);
+
       /* If we made a replacement, fold the statement.  */
       if (did_replace)
 	{
@@ -1083,7 +1138,7 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
 	 specific information.  Do this before propagating
 	 into the stmt to not disturb pass specific information.  */
       update_stmt_if_modified (stmt);
-      if (substitute_and_fold_engine->fold_stmt(&i))
+      if (substitute_and_fold_engine->fold_stmt (&i))
 	{
 	  did_replace = true;
 	  prop_stats.num_stmts_folded++;
@@ -1114,6 +1169,8 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
       /* Now cleanup.  */
       if (did_replace)
 	{
+	  massage_new_statments (prev_gsi, i);
+
 	  /* If we cleaned up EH information from the statement,
 	     remove EH edges.  */
 	  if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
@@ -1152,6 +1209,9 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
 	    fprintf (dump_file, "Not folded\n");
 	}
     }
+
+  substitute_and_fold_engine->propagate_into_phi_args (bb);
+
   return NULL;
 }
 
diff --git a/gcc/tree-ssa-propagate.h b/gcc/tree-ssa-propagate.h
index 0d0f1c2..88b532b 100644
--- a/gcc/tree-ssa-propagate.h
+++ b/gcc/tree-ssa-propagate.h
@@ -110,6 +110,13 @@ class substitute_and_fold_engine
   bool replace_uses_in (gimple *);
   bool replace_phi_args_in (gphi *);
 
+  virtual void pre_fold_bb (basic_block) { }
+  virtual void post_fold_bb (basic_block) { }
+  virtual void pre_fold_stmt (gimple *) { }
+  virtual void post_fold_stmt (gimple *) { }
+
+  void propagate_into_phi_args (basic_block);
+
   /* Users like VRP can set this when they want to perform
      folding for every propagation.  */
   bool fold_all_stmts;
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 94f8f22..1ea121f 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -3698,6 +3698,27 @@ range_fits_type_p (const value_range_equiv *vr,
   return true;
 }
 
+bool
+vr_values::simplify_cond_using_ranges_when_edge_is_known (gcond *cond)
+{
+  /* ?? vrp_folder::fold_predicate_in() is a superset of this.  At
+     some point we should merge all variants of this code.  */
+  edge taken_edge;
+  vrp_visit_cond_stmt (cond, &taken_edge);
+  if (taken_edge)
+    {
+      if (taken_edge->flags & EDGE_TRUE_VALUE)
+	gimple_cond_make_true (cond);
+      else if (taken_edge->flags & EDGE_FALSE_VALUE)
+	gimple_cond_make_false (cond);
+      else
+	gcc_unreachable ();
+      update_stmt (cond);
+      return true;
+    }
+  return false;
+}
+
 /* Simplify a conditional using a relational operator to an equality
    test if the range information indicates only one value can satisfy
    the original conditional.  */
@@ -3709,6 +3730,9 @@ vr_values::simplify_cond_using_ranges_1 (gcond *stmt)
   tree op1 = gimple_cond_rhs (stmt);
   enum tree_code cond_code = gimple_cond_code (stmt);
 
+  if (simplify_cond_using_ranges_when_edge_is_known (stmt))
+    return true;
+
   if (cond_code != NE_EXPR
       && cond_code != EQ_EXPR
       && TREE_CODE (op0) == SSA_NAME
diff --git a/gcc/vr-values.h b/gcc/vr-values.h
index 1a768e5..2a6273c 100644
--- a/gcc/vr-values.h
+++ b/gcc/vr-values.h
@@ -138,6 +138,7 @@ class vr_values : public trace_vr_gori_interface
   bool simplify_bit_ops_using_ranges (gimple_stmt_iterator *, gimple *);
   bool simplify_min_or_max_using_ranges (gimple_stmt_iterator *, gimple *);
   bool simplify_cond_using_ranges_1 (gcond *);
+  bool simplify_cond_using_ranges_when_edge_is_known (gcond *);
   bool simplify_switch_using_ranges (gswitch *);
   bool simplify_float_conversion_using_ranges (gimple_stmt_iterator *,
 					       gimple *);