Initial implementation of ranger VRP pass.

9 files changed, 167 insertions, 8 deletions

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 52ba209..89a56c3 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1328,6 +1328,7 @@ OBJS = \
 	gimple-low.o \
 	gimple-pretty-print.o \
 	gimple-ranger.o \
+	gimple-ranger-vrp.o \
 	gimple-range-cache.o \
 	gimple-range-cfg.o \
 	gimple-range-stmt.o \
diff --git a/gcc/common.opt b/gcc/common.opt
index 9fc9211..9c830ab 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2922,6 +2922,10 @@ fvect-cost-model
 Common Alias(fvect-cost-model=,dynamic,unlimited)
 Enables the dynamic vectorizer cost model.  Preserved for backward compatibility.
 
+;; Allow RVRP to make IL changes.
+frvrp-changes
+Common Var(flag_rvrp_changes) Init(1)
+
 ftree-vect-loop-version
 Common Ignore
 Does nothing. Preserved for backward compatibility.
diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index d06931f..9e20b0a 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -483,7 +483,8 @@ debug (gori_map &g)
 }
 
 const value_range_equiv *
-range_store::get_value_range (const_tree expr ATTRIBUTE_UNUSED)
+range_store::get_value_range (const_tree expr ATTRIBUTE_UNUSED,
+			      gimple *stmt ATTRIBUTE_UNUSED)
 {
   gcc_unreachable ();
   return NULL;
diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h
index 3ea8945..7a5e168 100644
--- a/gcc/gimple-range-gori.h
+++ b/gcc/gimple-range-gori.h
@@ -139,7 +139,8 @@ class range_store
 {
 public:
   virtual bool range_of_expr (irange &r, tree expr, gimple *stmt = NULL) = 0;
-  virtual const value_range_equiv *get_value_range (const_tree expr);
+  virtual const value_range_equiv *get_value_range (const_tree expr,
+						    gimple *stmt = NULL);
 };
 
 // This class utilizes a GORI map to determine which SSA_NAMES can
diff --git a/gcc/gimple-ranger-vrp.cc b/gcc/gimple-ranger-vrp.cc
new file mode 100644
index 0000000..284862d
--- /dev/null
+++ b/gcc/gimple-ranger-vrp.cc
@@ -0,0 +1,149 @@
+/* Value range propagation pass using the ranger.
+   Copyright (C) 2020 Free Software Foundation, Inc.
+   Contributed by Aldy Hernandez <aldyh@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "tree.h"
+#include "gimple.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "gimple-pretty-print.h"
+#include "cfganal.h"
+#include "gimple-fold.h"
+#include "tree-eh.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-ssa-loop.h"
+#include "cfgloop.h"
+#include "tree-scalar-evolution.h"
+#include "tree-ssa-propagate.h"
+#include "alloc-pool.h"
+#include "domwalk.h"
+#include "tree-cfgcleanup.h"
+#include "vr-values.h"
+#include "gimple-ssa-evrp-analyze.h"
+#include "gimple-ranger.h"
+
+#define DEBUG_RVRP getenv("DEBUG_RVRP")
+
+class rvrp_ranger : public trace_ranger
+{
+public:
+  // This is the range getter for the simplifier, but is really only
+  // used for the conditional folding which still uses equivalences.
+  virtual const value_range_equiv *get_value_range (const_tree expr,
+						    gimple *stmt)
+  {
+    widest_irange r;
+    if (range_of_expr (r, const_cast<tree> (expr), stmt))
+      return new value_range_equiv (r); // FIXME: leaks
+    return new value_range_equiv (TREE_TYPE (expr));
+  }
+};
+
+class rvrp_folder : public substitute_and_fold_engine
+{
+public:
+  rvrp_folder () : simplifier (&ranger) { }
+
+  tree get_value (tree op, gimple *stmt)
+  {
+    if (disable_il_changes_p ())
+      return NULL;
+
+    widest_irange r;
+    tree singleton;
+    if (ranger.range_of_expr (r, op, stmt) && r.singleton_p (&singleton))
+      return singleton;
+    return NULL;
+  }
+
+  bool fold_stmt (gimple_stmt_iterator *gsi)
+  {
+    if (disable_il_changes_p ())
+      return false;
+
+    return simplifier.simplify (gsi);
+  }
+
+  bool disable_il_changes_p ()
+  {
+    return !flag_rvrp_changes;
+  }
+
+private:
+  rvrp_ranger ranger;
+  simplify_using_ranges simplifier;
+};
+
+static unsigned int
+execute_ranger_vrp ()
+{
+  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);
+
+  rvrp_folder folder;
+  folder.substitute_and_fold ();
+
+  scev_finalize ();
+  loop_optimizer_finalize ();
+  return 0;
+}
+
+namespace {
+
+const pass_data pass_data_ranger_vrp =
+{
+ GIMPLE_PASS,			// type
+ "rvrp",			// name
+ OPTGROUP_NONE,			// optinfo_flags
+ TV_TREE_EARLY_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_ranger_vrp : public gimple_opt_pass
+{
+public:
+  pass_ranger_vrp (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_ranger_vrp, ctxt)
+    {}
+  opt_pass * clone () { return new pass_ranger_vrp (m_ctxt); }
+  virtual bool gate (function *)
+    { return flag_tree_vrp != 0; }
+  virtual unsigned int execute (function *)
+    { return execute_ranger_vrp (); }
+};
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_ranger_vrp (gcc::context *ctxt)
+{
+  return new pass_ranger_vrp (ctxt);
+}
diff --git a/gcc/passes.def b/gcc/passes.def
index b6bd4f3..2ec4dfb 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -84,6 +84,7 @@ along with GCC; see the file COPYING3.  If not see
 	     execute TODO_rebuild_alias at this point.  */
 	  NEXT_PASS (pass_build_ealias);
 	  NEXT_PASS (pass_fre, true /* may_iterate */);
+	  NEXT_PASS (pass_ranger_vrp);
 	  NEXT_PASS (pass_early_vrp);
 	  NEXT_PASS (pass_merge_phi);
           NEXT_PASS (pass_dse);
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 5ff4357..e37a30d 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -446,6 +446,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_ranger_vrp (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_vrp (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_uncprop (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_return_slot (gcc::context *ctxt);
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index eab4cb4..8913da4 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -148,7 +148,7 @@ vr_values::get_lattice_entry (const_tree var)
    return NULL.  Otherwise create an empty range if none existed for VAR.  */
 
 const value_range_equiv *
-vr_values::get_value_range (const_tree var)
+vr_values::get_value_range (const_tree var, gimple *stmt ATTRIBUTE_UNUSED)
 {
   /* If we have no recorded ranges, then return NULL.  */
   if (!vr_value)
@@ -2513,7 +2513,7 @@ simplify_using_ranges::vrp_evaluate_conditional (tree_code code, tree op0,
 	 always fold regardless of the value of OP0.  If -Wtype-limits
 	 was specified, emit a warning.  */
       tree type = TREE_TYPE (op0);
-      const value_range_equiv *vr0 = get_value_range_equiv (op0);
+      const value_range_equiv *vr0 = get_value_range_equiv (op0, stmt);
 
       if (vr0->kind () == VR_RANGE
 	  && INTEGRAL_TYPE_P (type)
@@ -2566,7 +2566,7 @@ simplify_using_ranges::vrp_visit_cond_stmt (gcond *stmt, edge *taken_edge_p)
 	  fprintf (dump_file, "\t");
 	  print_generic_expr (dump_file, use);
 	  fprintf (dump_file, ": ");
-	  dump_value_range (dump_file, store->get_value_range (use));
+	  dump_value_range (dump_file, get_value_range_equiv (use, stmt));
 	}
 
       fprintf (dump_file, "\n");
diff --git a/gcc/vr-values.h b/gcc/vr-values.h
index a0fb538..9311355 100644
--- a/gcc/vr-values.h
+++ b/gcc/vr-values.h
@@ -40,8 +40,9 @@ private:
   // This is named differently than get_value_range to make it obvious
   // that it returns an equivalence.  Only use this for calculations
   // that may take equivalences, otherwise use range_of_expr.
-  const value_range_equiv *get_value_range_equiv (const_tree op)
-  { return store->get_value_range (op); }
+  const value_range_equiv *get_value_range_equiv (const_tree op,
+						  gimple *stmt = NULL)
+  { return store->get_value_range (op, stmt); }
   bool simplify_truth_ops_using_ranges (gimple_stmt_iterator *, gimple *);
   bool simplify_div_or_mod_using_ranges (gimple_stmt_iterator *, gimple *);
   bool simplify_abs_using_ranges (gimple_stmt_iterator *, gimple *);
@@ -100,7 +101,7 @@ class vr_values : public range_store
  public:
   virtual ~vr_values (void);
 
-  const value_range_equiv *get_value_range (const_tree);
+  const value_range_equiv *get_value_range (const_tree, gimple *stmt = NULL);
   void set_vr_value (tree, value_range_equiv *);
   value_range_equiv *swap_vr_value (tree, value_range_equiv *);
   bool range_of_expr (irange &r, tree expr, gimple *stmt = NULL);