[gcc r14-4424] Create a fast VRP pass

[gcc r14-4424] Create a fast VRP pass

[Andrew Macleod]

https://gcc.gnu.org/g:56cbd50e8e60ee01afc9bacf25baf7e66be8d367

commit r14-4424-g56cbd50e8e60ee01afc9bacf25baf7e66be8d367
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Oct 2 18:32:49 2023 -0400

    Create a fast VRP pass
    
            * timevar.def (TV_TREE_FAST_VRP): New.
            * tree-pass.h (make_pass_fast_vrp): New prototype.
            * tree-vrp.cc (class fvrp_folder): New.
            (fvrp_folder::fvrp_folder): New.
            (fvrp_folder::~fvrp_folder): New.
            (fvrp_folder::value_of_expr): New.
            (fvrp_folder::value_on_edge): New.
            (fvrp_folder::value_of_stmt): New.
            (fvrp_folder::pre_fold_bb): New.
            (fvrp_folder::post_fold_bb): New.
            (fvrp_folder::pre_fold_stmt): New.
            (fvrp_folder::fold_stmt): New.
            (execute_fast_vrp): New.
            (pass_data_fast_vrp): New.
            (pass_vrp:execute): Check for fast VRP pass.
            (make_pass_fast_vrp): New.

Diff:
---
 gcc/timevar.def |   1 +
 gcc/tree-pass.h |   1 +
 gcc/tree-vrp.cc | 124 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 126 insertions(+)

diff --git a/gcc/timevar.def b/gcc/timevar.def
index 9523598f60e..d21b08c030d 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -160,6 +160,7 @@ DEFTIMEVAR (TV_TREE_TAIL_MERGE       , "tree tail merge")
 DEFTIMEVAR (TV_TREE_VRP              , "tree VRP")
 DEFTIMEVAR (TV_TREE_VRP_THREADER     , "tree VRP threader")
 DEFTIMEVAR (TV_TREE_EARLY_VRP        , "tree Early VRP")
+DEFTIMEVAR (TV_TREE_FAST_VRP         , "tree Fast VRP")
 DEFTIMEVAR (TV_TREE_COPY_PROP        , "tree copy propagation")
 DEFTIMEVAR (TV_FIND_REFERENCED_VARS  , "tree find ref. vars")
 DEFTIMEVAR (TV_TREE_PTA		     , "tree PTA")
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index eba2d54ac76..9c4b1e4185c 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -470,6 +470,7 @@ extern gimple_opt_pass *make_pass_check_data_deps (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_copy_prop (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_isolate_erroneous_paths (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_early_vrp (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_fast_vrp (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_vrp (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_assumptions (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_uncprop (gcc::context *ctxt);
diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc
index 4f8c7745461..19d8f995d70 100644
--- a/gcc/tree-vrp.cc
+++ b/gcc/tree-vrp.cc
@@ -1092,6 +1092,106 @@ execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p,
   return 0;
 }
 
+// Implement a Fast VRP folder.  Not quite as effective but faster.
+
+class fvrp_folder : public substitute_and_fold_engine
+{
+public:
+  fvrp_folder (dom_ranger *dr) : substitute_and_fold_engine (),
+				 m_simplifier (dr)
+  { m_dom_ranger = dr; }
+
+  ~fvrp_folder () { }
+
+  tree value_of_expr (tree name, gimple *s = NULL) override
+  {
+    // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
+    if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
+      return NULL;
+    return m_dom_ranger->value_of_expr (name, s);
+  }
+
+  tree value_on_edge (edge e, tree name) override
+  {
+    // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
+    if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
+      return NULL;
+    return m_dom_ranger->value_on_edge (e, name);
+  }
+
+  tree value_of_stmt (gimple *s, tree name = NULL) override
+  {
+    // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
+    if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
+      return NULL;
+    return m_dom_ranger->value_of_stmt (s, name);
+  }
+
+  void pre_fold_bb (basic_block bb) override
+  {
+    m_dom_ranger->pre_bb (bb);
+    // Now process the PHIs in advance.
+    gphi_iterator psi = gsi_start_phis (bb);
+    for ( ; !gsi_end_p (psi); gsi_next (&psi))
+      {
+	tree name = gimple_range_ssa_p (PHI_RESULT (psi.phi ()));
+	if (name)
+	  {
+	    Value_Range vr(TREE_TYPE (name));
+	    m_dom_ranger->range_of_stmt (vr, psi.phi (), name);
+	  }
+      }
+  }
+
+  void post_fold_bb (basic_block bb) override
+  {
+    m_dom_ranger->post_bb (bb);
+  }
+
+  void pre_fold_stmt (gimple *s) override
+  {
+    // Ensure range_of_stmt has been called.
+    tree type = gimple_range_type (s);
+    if (type)
+      {
+	Value_Range vr(type);
+	m_dom_ranger->range_of_stmt (vr, s);
+      }
+  }
+
+  bool fold_stmt (gimple_stmt_iterator *gsi) override
+  {
+    bool ret = m_simplifier.simplify (gsi);
+    if (!ret)
+      ret = ::fold_stmt (gsi, follow_single_use_edges);
+    return ret;
+  }
+
+private:
+  DISABLE_COPY_AND_ASSIGN (fvrp_folder);
+  simplify_using_ranges m_simplifier;
+  dom_ranger *m_dom_ranger;
+};
+
+
+// Main entry point for a FAST VRP pass using a dom ranger.
+
+unsigned int
+execute_fast_vrp (struct function *fun)
+{
+  calculate_dominance_info (CDI_DOMINATORS);
+  dom_ranger dr;
+  fvrp_folder folder (&dr);
+
+  gcc_checking_assert (!fun->x_range_query);
+  fun->x_range_query = &dr;
+
+  folder.substitute_and_fold ();
+
+  fun->x_range_query = NULL;
+  return 0;
+}
+
 namespace {
 
 const pass_data pass_data_vrp =
@@ -1120,6 +1220,20 @@ const pass_data pass_data_early_vrp =
   ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
 };
 
+const pass_data pass_data_fast_vrp =
+{
+  GIMPLE_PASS, /* type */
+  "fvrp", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_TREE_FAST_VRP, /* tv_id */
+  PROP_ssa, /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
+};
+
+
 class pass_vrp : public gimple_opt_pass
 {
 public:
@@ -1139,6 +1253,10 @@ public:
   bool gate (function *) final override { return flag_tree_vrp != 0; }
   unsigned int execute (function *fun) final override
     {
+      // Check for fast vrp.
+      if (&data == &pass_data_fast_vrp)
+	return execute_fast_vrp (fun);
+
       return execute_ranger_vrp (fun, warn_array_bounds_p, final_p);
     }
 
@@ -1224,6 +1342,12 @@ make_pass_early_vrp (gcc::context *ctxt)
   return new pass_vrp (ctxt, pass_data_early_vrp, false);
 }
 
+gimple_opt_pass *
+make_pass_fast_vrp (gcc::context *ctxt)
+{
+  return new pass_vrp (ctxt, pass_data_fast_vrp, false);
+}
+
 gimple_opt_pass *
 make_pass_assumptions (gcc::context *ctx)
 {