Merge evrp uses of substitute_and_fold_engine into the engine itself.

This patch merges the evrp uses of the substitute and fold engine into
the engine itself, at least the parts that can be re-used by other
engine uses.  It also adds a context parameter to get_value() for
further use.

gcc/
	* gimple-loop-versioning.cc (loop_versioning::name_prop::get_value):
	Add stmt parameter.
	* gimple-ssa-evrp.c (class evrp_folder): New.
	(class evrp_dom_walker): Remove.
	(execute_early_vrp): Use evrp_folder instead of evrp_dom_walker.
	* tree-ssa-ccp.c (ccp_folder::get_value): Add stmt parameter.
	* tree-ssa-copy.c (copy_folder::get_value): Same.
	* tree-ssa-propagate.c (substitute_and_fold_engine::replace_uses_in):
	Pass stmt to get_value.
	(substitute_and_fold_engine::replace_phi_args_in): Same.
	(substitute_and_fold_dom_walker::after_dom_children): Call
	post_fold_bb.
	(substitute_and_fold_dom_walker::foreach_new_stmt_in_bb): New.
	(substitute_and_fold_dom_walker::propagate_into_phi_args): New.
	(substitute_and_fold_dom_walker::before_dom_children): Adjust to
	call virtual functions for folding, pre_folding, and post folding.
	Call get_value with PHI.  Tweak dump.
	* tree-ssa-propagate.h (class substitute_and_fold_engine):
	New argument to get_value.
	New virtual function pre_fold_bb.
	New virtual function post_fold_bb.
	New virtual function pre_fold_stmt.
	New virtual function post_new_stmt.
	New function propagate_into_phi_args.
	* tree-vrp.c (vrp_folder::get_value): Add stmt argument.
	* vr-values.c (vr_values::extract_range_from_stmt): Adjust dump
	output.
	(vr_values::fold_cond): New.
	(vr_values::simplify_cond_using_ranges_1): Call fold_cond.
	* vr-values.h (class vr_values): Add
	simplify_cond_using_ranges_when_edge_is_known.
gcc/testsuite/
	* gcc.dg/tree-ssa/ssa-dse-30.c: Adjust test for folding of
	memmove happening later.

1 files changed, 63 insertions, 271 deletions

diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c
index 599e145..af780fd 100644
--- a/gcc/gimple-ssa-evrp.c
+++ b/gcc/gimple-ssa-evrp.c
@@ -44,272 +44,67 @@ along with GCC; see the file COPYING3.  If not see
 
 class evrp_folder : public substitute_and_fold_engine
 {
- public:
-  tree get_value (tree) FINAL OVERRIDE;
-  evrp_folder (class vr_values *vr_values_) : vr_values (vr_values_) { }
-  bool simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
-    { return vr_values->simplify_stmt_using_ranges (gsi); }
-  class vr_values *vr_values;
-
- private:
-  DISABLE_COPY_AND_ASSIGN (evrp_folder);
-};
-
-tree
-evrp_folder::get_value (tree op)
-{
-  return vr_values->op_with_constant_singleton_value_range (op);
-}
-
-/* evrp_dom_walker visits the basic blocks in the dominance order and set
-   the Value Ranges (VR) for SSA_NAMEs in the scope.  Use this VR to
-   discover more VRs.  */
-
-class evrp_dom_walker : public dom_walker
-{
 public:
-  evrp_dom_walker ()
-    : dom_walker (CDI_DOMINATORS),
-      evrp_range_analyzer (true),
-      evrp_folder (evrp_range_analyzer.get_vr_values ())
-    {
-      need_eh_cleanup = BITMAP_ALLOC (NULL);
-    }
-  ~evrp_dom_walker ()
-    {
-      BITMAP_FREE (need_eh_cleanup);
-    }
-  virtual edge before_dom_children (basic_block);
-  virtual void after_dom_children (basic_block);
-  void cleanup (void);
-
- private:
-  DISABLE_COPY_AND_ASSIGN (evrp_dom_walker);
-  bitmap need_eh_cleanup;
-  auto_vec<gimple *> stmts_to_fixup;
-  auto_vec<gimple *> stmts_to_remove;
-
-  class evrp_range_analyzer evrp_range_analyzer;
-  class evrp_folder evrp_folder;
+  evrp_folder () : m_range_analyzer (/*update_global_ranges=*/true),
+    m_vr_values (m_range_analyzer.get_vr_values ())
+  {
+  }
+
+  ~evrp_folder ()
+  {
+    m_vr_values->cleanup_edges_and_switches ();
+
+    if (dump_file)
+      {
+	fprintf (dump_file, "\nValue ranges after Early VRP:\n\n");
+	m_range_analyzer.dump_all_value_ranges (dump_file);
+	fprintf (dump_file, "\n");
+      }
+  }
+
+  tree get_value (tree op, gimple *stmt ATTRIBUTE_UNUSED) OVERRIDE
+  {
+    return m_vr_values->op_with_constant_singleton_value_range (op);
+  }
+
+  void pre_fold_bb (basic_block bb) OVERRIDE
+  {
+    if (dump_file && (dump_flags & TDF_DETAILS))
+      fprintf (dump_file, "evrp visiting BB%d\n", bb->index);
+    m_range_analyzer.enter (bb);
+  }
+
+  void pre_fold_stmt (gimple *stmt) OVERRIDE
+  {
+    if (dump_file && (dump_flags & TDF_DETAILS))
+      {
+	fprintf (dump_file, "evrp visiting stmt ");
+	print_gimple_stmt (dump_file, stmt, 0);
+      }
+    m_range_analyzer.record_ranges_from_stmt (stmt, false);
+  }
+
+  bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
+  {
+    return m_vr_values->simplify_stmt_using_ranges (gsi);
+  }
+
+  void post_fold_bb (basic_block bb) OVERRIDE
+  {
+    m_range_analyzer.leave (bb);
+  }
+
+  void post_new_stmt (gimple *stmt) OVERRIDE
+  {
+    m_vr_values->set_defs_to_varying (stmt);
+  }
+
+private:
+  DISABLE_COPY_AND_ASSIGN (evrp_folder);
+  class evrp_range_analyzer m_range_analyzer;
+  class vr_values *m_vr_values;
 };
 
-edge
-evrp_dom_walker::before_dom_children (basic_block bb)
-{
-  if (dump_file && (dump_flags & TDF_DETAILS))
-    fprintf (dump_file, "Visiting BB%d\n", bb->index);
-
-  evrp_range_analyzer.enter (bb);
-
-  for (gphi_iterator gpi = gsi_start_phis (bb);
-       !gsi_end_p (gpi); gsi_next (&gpi))
-    {
-      gphi *phi = gpi.phi ();
-      tree lhs = PHI_RESULT (phi);
-      if (virtual_operand_p (lhs))
-	continue;
-
-      const value_range_equiv *vr = evrp_range_analyzer.get_value_range (lhs);
-      /* Mark PHIs whose lhs we fully propagate for removal.  */
-      tree val;
-      if (vr->singleton_p (&val) && may_propagate_copy (lhs, val))
-	{
-	  stmts_to_remove.safe_push (phi);
-	  continue;
-	}
-    }
-
-  edge taken_edge = NULL;
-
-  /* Visit all other stmts and discover any new VRs possible.  */
-  for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
-       !gsi_end_p (gsi); gsi_next (&gsi))
-    {
-      gimple *stmt = gsi_stmt (gsi);
-      tree output = NULL_TREE;
-      gimple *old_stmt = stmt;
-      bool was_noreturn = (is_gimple_call (stmt)
-			   && gimple_call_noreturn_p (stmt));
-
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	{
-	  fprintf (dump_file, "Visiting stmt ");
-	  print_gimple_stmt (dump_file, stmt, 0);
-	}
-
-      evrp_range_analyzer.record_ranges_from_stmt (stmt, false);
-
-      if (gcond *cond = dyn_cast <gcond *> (stmt))
-	{
-	  evrp_range_analyzer.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 (stmt);
-	    }
-	}
-      else if (stmt_interesting_for_vrp (stmt))
-	{
-	  output = get_output_for_vrp (stmt);
-	  if (output)
-	    {
-	      const value_range_equiv *vr
-		= evrp_range_analyzer.get_value_range (output);
-
-	      /* Mark stmts whose output we fully propagate for removal.  */
-	      tree val;
-	      if (vr->singleton_p (&val)
-		  && may_propagate_copy (output, val)
-		  && !stmt_could_throw_p (cfun, stmt)
-		  && !gimple_has_side_effects (stmt))
-		{
-		  stmts_to_remove.safe_push (stmt);
-		  continue;
-		}
-	    }
-	}
-
-      /* Try folding stmts with the VR discovered.  */
-      bool did_replace = evrp_folder.replace_uses_in (stmt);
-      gimple_stmt_iterator prev_gsi = gsi;
-      gsi_prev (&prev_gsi);
-      if (fold_stmt (&gsi, follow_single_use_edges)
-	  || did_replace)
-	{
-	  stmt = gsi_stmt (gsi);
-	  update_stmt (stmt);
-	  did_replace = true;
-	}
-      if (evrp_folder.simplify_stmt_using_ranges (&gsi))
-	{
-	  stmt = gsi_stmt (gsi);
-	  update_stmt (stmt);
-	  did_replace = true;
-	}
-
-      if (did_replace)
-	{
-	  /* If we wound up generating new stmts during folding
-	     drop all their defs to VARYING.  We can't easily
-	     process them because we've already instantiated
-	     ranges on uses on STMT that only hold after it.  */
-	  if (gsi_end_p (prev_gsi))
-	    prev_gsi = gsi_start_bb (bb);
-	  else
-	    gsi_next (&prev_gsi);
-	  while (gsi_stmt (prev_gsi) != gsi_stmt (gsi))
-	    {
-	      evrp_range_analyzer.get_vr_values ()
-		->set_defs_to_varying (gsi_stmt (prev_gsi));
-	      gsi_next (&prev_gsi);
-	    }
-
-	  /* If we cleaned up EH information from the statement,
-	     remove EH edges.  */
-	  if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
-	    bitmap_set_bit (need_eh_cleanup, bb->index);
-
-	  /* If we turned a not noreturn call into a noreturn one
-	     schedule it for fixup.  */
-	  if (!was_noreturn
-	      && is_gimple_call (stmt)
-	      && gimple_call_noreturn_p (stmt))
-	    stmts_to_fixup.safe_push (stmt);
-
-	  if (gimple_assign_single_p (stmt))
-	    {
-	      tree rhs = gimple_assign_rhs1 (stmt);
-	      if (TREE_CODE (rhs) == ADDR_EXPR)
-		recompute_tree_invariant_for_addr_expr (rhs);
-	    }
-	}
-    }
-
-  /* Visit BB successor PHI nodes and replace PHI args.  */
-  edge e;
-  edge_iterator ei;
-  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;
-	  const value_range_equiv
-	    *vr = evrp_range_analyzer.get_value_range (arg);
-	  tree val;
-	  if (vr->singleton_p (&val) && may_propagate_copy (arg, val))
-	    propagate_value (use_p, val);
-	}
-    }
- 
-  return taken_edge;
-}
-
-void
-evrp_dom_walker::after_dom_children (basic_block bb)
-{
-  evrp_range_analyzer.leave (bb);
-}
-
-/* Perform any cleanups after the main phase of EVRP has completed.  */
-
-void
-evrp_dom_walker::cleanup (void)
-{
-  if (dump_file)
-    {
-      fprintf (dump_file, "\nValue ranges after Early VRP:\n\n");
-      evrp_range_analyzer.dump_all_value_ranges (dump_file);
-      fprintf (dump_file, "\n");
-    }
-
-  /* Remove stmts in reverse order to make debug stmt creation possible.  */
-  while (! stmts_to_remove.is_empty ())
-    {
-      gimple *stmt = stmts_to_remove.pop ();
-      if (dump_file && dump_flags & TDF_DETAILS)
-	{
-	  fprintf (dump_file, "Removing dead stmt ");
-	  print_gimple_stmt (dump_file, stmt, 0);
-	  fprintf (dump_file, "\n");
-	}
-      gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
-      if (gimple_code (stmt) == GIMPLE_PHI)
-	remove_phi_node (&gsi, true);
-      else
-	{
-	  unlink_stmt_vdef (stmt);
-	  gsi_remove (&gsi, true);
-	  release_defs (stmt);
-	}
-    }
-
-  if (!bitmap_empty_p (need_eh_cleanup))
-    gimple_purge_all_dead_eh_edges (need_eh_cleanup);
-
-  /* Fixup stmts that became noreturn calls.  This may require splitting
-     blocks and thus isn't possible during the dominator walk.  Do this
-     in reverse order so we don't inadvertedly remove a stmt we want to
-     fixup by visiting a dominating now noreturn call first.  */
-  while (!stmts_to_fixup.is_empty ())
-    {
-      gimple *stmt = stmts_to_fixup.pop ();
-      fixup_noreturn_call (stmt);
-    }
-
-  evrp_folder.vr_values->cleanup_edges_and_switches ();
-}
-
 /* 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.  */
@@ -317,19 +112,17 @@ evrp_dom_walker::cleanup (void)
 static unsigned int
 execute_early_vrp ()
 {
-  /* Ideally this setup code would move into the ctor for the dominator
-     walk.  However, this setup can change the number of blocks which
+  /* Ideally this setup code would move into the ctor for the folder
+     However, this setup can change the number of blocks which
      invalidates the internal arrays that are set up by the dominator
-     walker.  */
+     walker in substitute_and_fold_engine.  */
   loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
   scev_initialize ();
   calculate_dominance_info (CDI_DOMINATORS);
 
-  /* Walk stmts in dominance order and propagate VRP.  */
-  evrp_dom_walker walker;
-  walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
-  walker.cleanup ();
+  evrp_folder folder;
+  folder.substitute_and_fold ();
 
   scev_finalize ();
   loop_optimizer_finalize ();
@@ -375,4 +168,3 @@ make_pass_early_vrp (gcc::context *ctxt)
 {
   return new pass_early_vrp (ctxt);
 }
-