even more range_of tweaks

From-SVN: r275590

gcc/ChangeLog

@@ -13150,6 +13150,73 @@
 	* ipa-devirt.c (skip_in_fields_list_p): New.
 	(odr_types_equivalent_p): Use it.
 
+2019-06-12  Aldy Hernandez  <aldyh@redhat.com>
+
+	* gimple-ssa-evrp.c (evrp_dom_walker::before_dom_children): Use
+	value_range::singleton_p.
+	* tree-vrp.c (value_range_constant_singleton): Remove.
+	* tree-vrp.h (value_range_constant_singleton): Remove.
+	* vr-values.c (vr_values::singleton): Use
+	value_range::singleton_p.
+
+2019-06-13  Aldy Hernandez  <aldyh@redhat.com>
+
+	* gimple-loop-versioning.cc (prune_loop_conditions): Use
+	may_contain_p.
+	* tree-vrp (value_range_base::may_contain_p): Call into
+	value_inside_range.
+	(value_inside_range): Make private inside value_range_base class.
+	Take min/max from *this.
+	(range_includes_p): Remove.
+	* tree-vrp.h (value_range_base): Add value_inside_range.
+	(range_includes_p): Remove.
+	(range_includes_zero_p): Call may_contain_p.
+	* vr-values.c (compare_range_with_value): Same.
+
+2019-06-07  Aldy Hernandez  <aldyh@redhat.com>
+
+	* tree-vrp.h (value_range_base::intersect): New.
+	(value_range::intersect_helper): Move from here...
+	(value_range_base::intersect_helper): ...to here.
+	* tree-vrp.c (value_range::intersect_helper): Rename to...
+	(value_range_base::intersect_helper): ...this, and rewrite to
+	return a value instead of modifying THIS in place.
+	Also, move equivalence handling...
+	(value_range::intersect): ...here, while calling intersect_helper.
+	* gimple-fold.c (size_must_be_zero_p): Use value_range_base when
+	calling intersect.
+	* gimple-ssa-evrp-analyze.c (ecord_ranges_from_incoming_edge):
+	Same.
+	* vr-values.c (vrp_evaluate_conditional_warnv_with_ops): Same.
+
+2019-06-03  Aldy Hernandez  <aldyh@redhat.com>
+	* tree-vrp.h (value_range_base::nonzero_p): New.
+	(value_range_base::set_nonnull): Rename to...
+	(value_range_base::set_nonzero): ...this.
+	(value_range_base::set_null): Rename to...
+	(value_range_base::set_zero): ...this.
+	(value_range::set_nonnull): Remove.
+	(value_range::set_null): Remove.
+	* tree-vrp.c (range_is_null): Remove.
+	(range_is_nonnull): Remove.
+	(extract_range_from_binary_expr): Use value_range_base::*zero_p
+	instead of range_is_*null.
+	(extract_range_from_unary_expr): Same.
+	(value_range_base::set_nonnull): Rename to...
+	(value_range_base::set_nonzero): ...this.
+	(value_range::set_nonnull): Remove.
+	(value_range_base::set_null): Rename to...
+	(value_range_base::set_zero): ...this.
+	(value_range::set_null): Remove.
+	(extract_range_from_binary_expr): Rename set_*null uses to
+	set_*zero.
+	(extract_range_from_unary_expr): Same.
+	(union_helper): Same.
+	* vr-values.c (get_value_range): Use set_*zero instead of
+	set_*null.
+	(vr_values::extract_range_from_binary_expr): Same.
+	(vr_values::extract_range_basic): Same.
+
 2019-04-13  Jakub Jelinek  <jakub@redhat.com>
 
 	PR target/89093

gcc/Makefile.in

@@ -221,6 +221,9 @@ libgcov-merge-tool.o-warn = -Wno-error
 gimple-match.o-warn = -Wno-unused
 generic-match.o-warn = -Wno-unused
 dfp.o-warn = -Wno-strict-aliasing
+# I fucking hate this warning and my stage1 compiler is too dumb.
+gimple-ssa-warn-restrict.o-warn = -Wno-format
+tree-ssa-strlen.o-warn = -Wno-format
 
 # All warnings have to be shut off in stage1 if the compiler used then
 # isn't gcc; configure determines that.  WARN_CFLAGS will be either
@@ -1351,6 +1354,7 @@ OBJS = \
 	graphite-poly.o \
 	graphite-scop-detection.o \
 	graphite-sese-to-poly.o \
+	grange.o \
 	gtype-desc.o \
 	haifa-sched.o \
 	hash-map-tests.o \
@@ -1452,6 +1456,8 @@ OBJS = \
 	print-tree.o \
 	profile.o \
 	profile-count.o \
+	range.o \
+	range-op.o \
 	read-md.o \
 	read-rtl.o \
 	read-rtl-function.o \
@@ -1490,6 +1496,10 @@ OBJS = \
 	spellcheck.o \
 	spellcheck-tree.o \
 	sreal.o \
+	ssa-range.o \
+	ssa-range-cache.o \
+	ssa-range-gori.o \
+	ssa-range-vrp.o \
 	stack-ptr-mod.o \
 	statistics.o \
 	stmt.o \
@@ -2548,6 +2558,7 @@ GTFILES = $(CPPLIB_H) $(srcdir)/input.h $(srcdir)/coretypes.h \
   $(srcdir)/stringpool.c $(srcdir)/tree.c $(srcdir)/varasm.c \
   $(srcdir)/gimple.h \
   $(srcdir)/gimple-ssa.h \
+  $(srcdir)/range.h $(srcdir)/range.cc \
   $(srcdir)/tree-ssanames.c $(srcdir)/tree-eh.c $(srcdir)/tree-ssa-address.c \
   $(srcdir)/tree-cfg.c $(srcdir)/tree-ssa-loop-ivopts.c \
   $(srcdir)/tree-dfa.c \

gcc/calls.c

@@ -54,6 +54,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "stringpool.h"
 #include "attribs.h"
 #include "builtins.h"
+#include "ssa-range.h"
 #include "gimple-fold.h"
 
 /* Like PREFERRED_STACK_BOUNDARY but in units of bytes, not bits.  */
@@ -1230,10 +1231,15 @@ alloc_max_size (void)
    returning a range of [0, 0] for a size in an anti-range [1, N] where
    N > PTRDIFF_MAX.  A zero range is a (nearly) invalid argument to
    allocation functions like malloc but it is a valid argument to
-   functions like memset.  */
+   functions like memset.
+
+   CALL is a statement indicating the point in the IL from where we
+   want to inquire about the range.  EXP does not need to appear
+   within CALL.  */
 
 bool
-get_size_range (tree exp, tree range[2], bool allow_zero /* = false */)
+get_size_range (tree exp, tree range[2], bool allow_zero /* = false */,
+		gimple *call /* = NULL */)
 {
   if (tree_fits_uhwi_p (exp))
     {
@@ -1244,21 +1250,26 @@ get_size_range (tree exp, tree range[2], bool allow_zero /* = false */)
 
   tree exptype = TREE_TYPE (exp);
   bool integral = INTEGRAL_TYPE_P (exptype);
+  global_ranger ranger;
+  irange r;
 
-  wide_int min, max;
-  enum value_range_kind range_type;
-
-  if (integral)
-    range_type = determine_value_range (exp, &min, &max);
-  else
-    range_type = VR_VARYING;
-
-  if (range_type == VR_VARYING)
+  /* If we don't have a ranger, use global range info.  */
+  if (!call
+      && TREE_CODE (exp) == SSA_NAME && integral
+      && SSA_NAME_RANGE_INFO (exp))
     {
+      wide_int min, max;
+      enum value_range_kind kind = get_range_info (exp, &min, &max);
+      r = irange (kind, exptype, min, max);
+    }
+  else if (!call || TREE_CODE (exp) != SSA_NAME || !integral
+	   || !ranger.range_of_expr (r, exp, call)
+	   || r.undefined_p ())
+    {
+      /* Use the full range of the type of the expression when
+	 no value range information is available.  */
       if (integral)
 	{
-	  /* Use the full range of the type of the expression when
-	     no value range information is available.  */
 	  range[0] = TYPE_MIN_VALUE (exptype);
 	  range[1] = TYPE_MAX_VALUE (exptype);
 	  return true;
@@ -1269,64 +1280,48 @@ get_size_range (tree exp, tree range[2], bool allow_zero /* = false */)
       return false;
     }
 
-  unsigned expprec = TYPE_PRECISION (exptype);
-
-  bool signed_p = !TYPE_UNSIGNED (exptype);
-
-  if (range_type == VR_ANTI_RANGE)
+  /* Special case for ~[1,MAX].  This means it's either zero or
+     greater than MAX.  Even though 0 would normally be detected by
+     -Walloc-zero, unless ALLOW_ZERO is true, set the range to [MAX,
+     TYPE_MAX] so that when MAX is greater than the limit the whole
+     range is diagnosed.  */
+  if (r.num_pairs () > 1
+      && r.lower_bound (0) == wi::to_wide (TYPE_MIN_VALUE (exptype))
+      && r.upper_bound (0) == wi::zero (TYPE_PRECISION (exptype)))
     {
-      if (signed_p)
-	{
-	  if (wi::les_p (max, 0))
-	    {
-	      /* EXP is not in a strictly negative range.  That means
-		 it must be in some (not necessarily strictly) positive
-		 range which includes zero.  Since in signed to unsigned
-		 conversions negative values end up converted to large
-		 positive values, and otherwise they are not valid sizes,
-		 the resulting range is in both cases [0, TYPE_MAX].  */
-	      min = wi::zero (expprec);
-	      max = wi::to_wide (TYPE_MAX_VALUE (exptype));
-	    }
-	  else if (wi::les_p (min - 1, 0))
-	    {
-	      /* EXP is not in a negative-positive range.  That means EXP
-		 is either negative, or greater than max.  Since negative
-		 sizes are invalid make the range [MAX + 1, TYPE_MAX].  */
-	      min = max + 1;
-	      max = wi::to_wide (TYPE_MAX_VALUE (exptype));
-	    }
-	  else
-	    {
-	      max = min - 1;
-	      min = wi::zero (expprec);
-	    }
-	}
-      else if (wi::eq_p (0, min - 1))
-	{
-	  /* EXP is unsigned and not in the range [1, MAX].  That means
-	     it's either zero or greater than MAX.  Even though 0 would
-	     normally be detected by -Walloc-zero, unless ALLOW_ZERO
-	     is true, set the range to [MAX, TYPE_MAX] so that when MAX
-	     is greater than the limit the whole range is diagnosed.  */
-	  if (allow_zero)
-	    min = max = wi::zero (expprec);
-	  else
-	    {
-	      min = max + 1;
-	      max = wi::to_wide (TYPE_MAX_VALUE (exptype));
-	    }
-	}
+      if (allow_zero)
+	r = range_zero (exptype);
       else
-	{
-	  max = min - 1;
-	  min = wi::zero (expprec);
-	}
+	r.intersect (irange (VR_ANTI_RANGE, exptype,
+			     r.lower_bound (0),
+			     r.upper_bound (0)));
+      range[0] = wide_int_to_tree (exptype, r.lower_bound ());
+      range[1] = wide_int_to_tree (exptype, r.upper_bound ());
+      return true;
     }
 
-  range[0] = wide_int_to_tree (exptype, min);
-  range[1] = wide_int_to_tree (exptype, max);
+  /* EXP may not be in a strictly negative range, since in signed to
+     unsigned conversions negative values end up converted to large
+     positive values.  Remove the extreme ends of the range that may
+     have come from conversions.  */
+  if (!TYPE_UNSIGNED (exptype) && r.num_pairs () > 1)
+    {
+      if (r.lower_bound (0) == wi::to_wide (TYPE_MIN_VALUE (exptype)))
+	{
+	  irange orig = r;
+	  r.intersect (range_positives (exptype));
+	  if (r.undefined_p ())
+	    r = orig;
+	}
+      /* This will transform [5,10][20,MAX] into [5,10].  */
+      else if (r.upper_bound () == wi::to_wide (TYPE_MAX_VALUE (exptype)))
+	r.intersect (irange (VR_ANTI_RANGE, exptype,
+			     r.lower_bound (r.num_pairs () - 1),
+			     r.upper_bound (r.num_pairs () - 1)));
+    }
 
+  range[0] = wide_int_to_tree (exptype, r.lower_bound ());
+  range[1] = wide_int_to_tree (exptype, r.upper_bound ());
   return true;
 }
 

gcc/calls.h

@@ -40,7 +40,7 @@ extern bool reference_callee_copied (CUMULATIVE_ARGS *, machine_mode,
 extern void maybe_warn_alloc_args_overflow (tree, tree, tree[2], int[2]);
 extern tree get_attr_nonstring_decl (tree, tree * = NULL);
 extern void maybe_warn_nonstring_arg (tree, tree);
-extern bool get_size_range (tree, tree[2], bool = false);
+extern bool get_size_range (tree, tree[2], bool = false, gimple * = NULL);
 extern rtx rtx_for_static_chain (const_tree, bool);
 
 #endif // GCC_CALLS_H

gcc/common.opt

@@ -1773,6 +1773,53 @@ fipa-vrp
 Common Report Var(flag_ipa_vrp) Optimization
 Perform IPA Value Range Propagation.
 
+ftree-rvrp
+Common Report Var(flag_tree_rvrp) Init(0) Optimization
+Perform Ranger Value Range Propagation on trees.
+
+; Temporary testing construct.
+frvrp-order=
+Common Joined RejectNegative Enum(rvrp_order) Var(flag_rvrp_order) Init(RVRP_ORDER_UNSPECIFIED)
+-frvrp-order=[dom|postdom|forward|backward|conditionals]	Set the ranger VRP traversal order.
+
+Enum
+Name(rvrp_order) Type(enum rvrp_order) UnknownError(unknown rvrp order %qs)
+
+EnumValue
+Enum(rvrp_order) String(dom) Value(RVRP_ORDER_DOMINATOR)
+
+EnumValue
+Enum(rvrp_order) String(postdom) Value(RVRP_ORDER_POSTDOM)
+
+EnumValue
+Enum(rvrp_order) String(forward) Value(RVRP_ORDER_FORWARD)
+
+EnumValue
+Enum(rvrp_order) String(backward) Value(RVRP_ORDER_BACKWARD)
+
+EnumValue
+Enum(rvrp_order) String(conditionals) Value(RVRP_ORDER_CONDITIONALS)
+
+;; Perform VRP range folding with either range-ops or the traditional
+;; extract_range_from_{binary,unary}_expr functions.  This is meant to
+;; be a transitional testing construct to verify that both agree.
+
+franges=
+Common Joined RejectNegative Enum(ranges_mode) Var(flag_ranges_mode) Init(RANGES_CHECKING)
+-franges=[checking|vrp|range-ops]	Set the mode for calculating ranges.
+
+Enum
+Name(ranges_mode) Type(enum ranges_mode) UnknownError(unknown ranges mode %qs)
+
+EnumValue
+Enum(ranges_mode) String(checking) Value(RANGES_CHECKING)
+
+EnumValue
+Enum(ranges_mode) String(vrp) Value(RANGES_VRP)
+
+EnumValue
+Enum(ranges_mode) String(range-ops) Value(RANGES_RANGE_OPS)
+
 fira-algorithm=
 Common Joined RejectNegative Enum(ira_algorithm) Var(flag_ira_algorithm) Init(IRA_ALGORITHM_CB) Optimization
 -fira-algorithm=[CB|priority]	Set the used IRA algorithm.

gcc/dbgcnt.def

@@ -176,6 +176,8 @@ DEBUG_COUNTER (pre)
 DEBUG_COUNTER (pre_insn)
 DEBUG_COUNTER (prefetch)
 DEBUG_COUNTER (registered_jump_thread)
+DEBUG_COUNTER (ranger_export_count)
+DEBUG_COUNTER (rvrp_fold_count)
 DEBUG_COUNTER (sched2_func)
 DEBUG_COUNTER (sched_block)
 DEBUG_COUNTER (sched_breakdep)

gcc/flag-types.h

@@ -145,6 +145,26 @@ enum ira_algorithm
   IRA_ALGORITHM_PRIORITY
 };
 
+/* Basic block traversal order for RVRP.  */
+enum rvrp_order
+{
+  RVRP_ORDER_UNSPECIFIED,
+  RVRP_ORDER_DOMINATOR,
+  RVRP_ORDER_POSTDOM,
+  RVRP_ORDER_FORWARD,
+  RVRP_ORDER_BACKWARD,
+  RVRP_ORDER_CONDITIONALS
+};
+
+/* Which method to use for operations on ranges.  */
+enum ranges_mode
+{
+  RANGES_VRP = 1,
+  RANGES_RANGE_OPS = 2,
+  /* Use both VPR and range-ops, and verify that the results agree.  */
+  RANGES_CHECKING = 3
+};
+
 /* The regions used for the integrated register allocator (IRA).  */
 enum ira_region
 {

gcc/function-tests.c

@@ -570,6 +570,19 @@ test_conversion_to_ssa ()
   ASSERT_EQ (SSA_NAME, TREE_CODE (gimple_return_retval (return_stmt)));
 }
 
+/* Test range folding.  We must start this here because we need cfun
+   set.  */
+
+static void
+test_ranges ()
+{
+  tree fndecl = build_trivial_high_gimple_function ();
+  function *fun = DECL_STRUCT_FUNCTION (fndecl);
+  push_cfun (fun);
+  range_tests ();
+  pop_cfun ();
+}
+
 /* Test of expansion from gimple-ssa to RTL.  */
 
 static void
@@ -674,6 +687,7 @@ function_tests_c_tests ()
   test_gimplification ();
   test_building_cfg ();
   test_conversion_to_ssa ();
+  test_ranges ();
   test_expansion_to_rtl ();
 }
 

gcc/gimple-ssa-evrp.c

@@ -58,7 +58,7 @@ class evrp_folder : public substitute_and_fold_engine
 tree
 evrp_folder::get_value (tree op)
 {
-  return vr_values->op_with_constant_singleton_value_range (op);
+  return vr_values->singleton (op, NULL);
 }
 
 /* evrp_dom_walker visits the basic blocks in the dominance order and set
@@ -73,11 +73,9 @@ public:
       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);
@@ -85,9 +83,8 @@ public:
 
  private:
   DISABLE_COPY_AND_ASSIGN (evrp_dom_walker);
-  bitmap need_eh_cleanup;
-  auto_vec<gimple *> stmts_to_fixup;
   auto_vec<gimple *> stmts_to_remove;
+  propagate_cleanups fixups;
 
   class evrp_range_analyzer evrp_range_analyzer;
   class evrp_folder evrp_folder;
@@ -128,8 +125,6 @@ evrp_dom_walker::before_dom_children (basic_block bb)
       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))
 	{
@@ -208,25 +203,7 @@ evrp_dom_walker::before_dom_children (basic_block bb)
 		->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);
-	    }
+	  fixups.record_change (old_stmt, stmt);
 	}
     }
 
@@ -293,19 +270,6 @@ evrp_dom_walker::cleanup (void)
 	}
     }
 
-  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 ();
 }
 

gcc/gimple-ssa-sprintf.c

@@ -86,6 +86,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "alloc-pool.h"
 #include "vr-values.h"
 #include "gimple-ssa-evrp-analyze.h"
+#include "ssa-range.h"
 
 /* The likely worst case value of MB_LEN_MAX for the target, large enough
    for UTF-8.  Ideally, this would be obtained by a target hook if it were
@@ -120,23 +121,6 @@ static int warn_level;
 
 struct format_result;
 
-class sprintf_dom_walker : public dom_walker
-{
- public:
-  sprintf_dom_walker ()
-    : dom_walker (CDI_DOMINATORS),
-      evrp_range_analyzer (false) {}
-  ~sprintf_dom_walker () {}
-
-  edge before_dom_children (basic_block) FINAL OVERRIDE;
-  void after_dom_children (basic_block) FINAL OVERRIDE;
-  bool handle_gimple_call (gimple_stmt_iterator *);
-
-  struct call_info;
-  bool compute_format_length (call_info &, format_result *);
-  class evrp_range_analyzer evrp_range_analyzer;
-};
-
 class pass_sprintf_length : public gimple_opt_pass
 {
   bool fold_return_value;
@@ -684,7 +668,7 @@ fmtresult::type_max_digits (tree type, int base)
 
 static bool
 get_int_range (tree, HOST_WIDE_INT *, HOST_WIDE_INT *, bool, HOST_WIDE_INT,
-	       class vr_values *vr_values);
+	       gimple *);
 
 /* Description of a format directive.  A directive is either a plain
    string or a conversion specification that starts with '%'.  */
@@ -713,13 +697,15 @@ struct directive
   /* Format specifier character.  */
   char specifier;
 
+  gimple *callstmt;
+
   /* The argument of the directive or null when the directive doesn't
      take one or when none is available (such as for vararg functions).  */
   tree arg;
 
   /* Format conversion function that given a directive and an argument
      returns the formatting result.  */
-  fmtresult (*fmtfunc) (const directive &, tree, vr_values *);
+  fmtresult (*fmtfunc) (const directive &, tree);
 
   /* Return True when a the format flag CHR has been used.  */
   bool get_flag (char chr) const
@@ -756,9 +742,9 @@ struct directive
      or 0, whichever is greater.  For a non-constant ARG in some range
      set width to its range adjusting each bound to -1 if it's less.
      For an indeterminate ARG set width to [0, INT_MAX].  */
-  void set_width (tree arg, vr_values *vr_values)
+  void set_width (tree arg)
   {
-    get_int_range (arg, width, width + 1, true, 0, vr_values);
+    get_int_range (arg, width, width + 1, true, 0, callstmt);
   }
 
   /* Set both bounds of the precision range to VAL.  */
@@ -772,9 +758,9 @@ struct directive
      or -1 whichever is greater.  For a non-constant ARG in some range
      set precision to its range adjusting each bound to -1 if it's less.
      For an indeterminate ARG set precision to [-1, INT_MAX].  */
-  void set_precision (tree arg, vr_values *vr_values)
+  void set_precision (tree arg)
   {
-    get_int_range (arg, prec, prec + 1, false, -1, vr_values);
+    get_int_range (arg, prec, prec + 1, false, -1, callstmt);
   }
 
   /* Return true if both width and precision are known to be
@@ -904,7 +890,7 @@ bytes_remaining (unsigned HOST_WIDE_INT navail, const format_result &res)
 
 /* Description of a call to a formatted function.  */
 
-struct sprintf_dom_walker::call_info
+struct call_info
 {
   /* Function call statement.  */
   gimple *callstmt;
@@ -978,7 +964,7 @@ struct sprintf_dom_walker::call_info
 /* Return the result of formatting a no-op directive (such as '%n').  */
 
 static fmtresult
-format_none (const directive &, tree, vr_values *)
+format_none (const directive &, tree)
 {
   fmtresult res (0);
   return res;
@@ -987,7 +973,7 @@ format_none (const directive &, tree, vr_values *)
 /* Return the result of formatting the '%%' directive.  */
 
 static fmtresult
-format_percent (const directive &, tree, vr_values *)
+format_percent (const directive &, tree)
 {
   fmtresult res (1);
   return res;
@@ -1047,7 +1033,7 @@ build_intmax_type_nodes (tree *pintmax, tree *puintmax)
 static bool
 get_int_range (tree arg, HOST_WIDE_INT *pmin, HOST_WIDE_INT *pmax,
 	       bool absolute, HOST_WIDE_INT negbound,
-	       class vr_values *vr_values)
+	       gimple *call)
 {
   /* The type of the result.  */
   const_tree type = integer_type_node;
@@ -1086,8 +1072,9 @@ get_int_range (tree arg, HOST_WIDE_INT *pmin, HOST_WIDE_INT *pmax,
 	  && TYPE_PRECISION (argtype) <= TYPE_PRECISION (type))
 	{
 	  /* Try to determine the range of values of the integer argument.  */
-	  const value_range *vr = vr_values->get_value_range (arg);
-	  if (range_int_cst_p (vr))
+	  irange r;
+	  if (on_demand_get_range_on_stmt (r, arg, call)
+	      && !r.undefined_p ())
 	    {
 	      HOST_WIDE_INT type_min
 		= (TYPE_UNSIGNED (argtype)
@@ -1096,8 +1083,10 @@ get_int_range (tree arg, HOST_WIDE_INT *pmin, HOST_WIDE_INT *pmax,
 
 	      HOST_WIDE_INT type_max = tree_to_uhwi (TYPE_MAX_VALUE (argtype));
 
-	      *pmin = TREE_INT_CST_LOW (vr->min ());
-	      *pmax = TREE_INT_CST_LOW (vr->max ());
+	      tree max = wide_int_to_tree (TREE_TYPE (arg), r.upper_bound ());
+	      tree min = wide_int_to_tree (TREE_TYPE (arg), r.lower_bound ());
+	      *pmin = TREE_INT_CST_LOW (min);
+	      *pmax = TREE_INT_CST_LOW (max);
 
 	      if (*pmin < *pmax)
 		{
@@ -1118,7 +1107,7 @@ get_int_range (tree arg, HOST_WIDE_INT *pmin, HOST_WIDE_INT *pmax,
 	 provided.  */
       if (unknown)
 	return get_int_range (NULL_TREE, pmin, pmax, absolute,
-			      negbound, vr_values);
+			      negbound, call);
     }
 
   /* Adjust each bound as specified by ABSOLUTE and NEGBOUND.  */
@@ -1203,7 +1192,7 @@ adjust_range_for_overflow (tree dirtype, tree *argmin, tree *argmax)
    used when the directive argument or its value isn't known.  */
 
 static fmtresult
-format_integer (const directive &dir, tree arg, vr_values *vr_values)
+format_integer (const directive &dir, tree arg)
 {
   tree intmax_type_node;
   tree uintmax_type_node;
@@ -1386,11 +1375,12 @@ format_integer (const directive &dir, tree arg, vr_values *vr_values)
     {
       /* Try to determine the range of values of the integer argument
 	 (range information is not available for pointers).  */
-      const value_range *vr = vr_values->get_value_range (arg);
-      if (range_int_cst_p (vr))
+      irange r;
+      if (on_demand_get_range_on_stmt (r, arg, dir.callstmt) &&
+	  !r.undefined_p ())
 	{
-	  argmin = vr->min ();
-	  argmax = vr->max ();
+	  argmin = wide_int_to_tree (TREE_TYPE (arg), r.lower_bound ());
+	  argmax = wide_int_to_tree (TREE_TYPE (arg), r.upper_bound ());
 
 	  /* Set KNOWNRANGE if the argument is in a known subrange
 	     of the directive's type and neither width nor precision
@@ -1403,11 +1393,7 @@ format_integer (const directive &dir, tree arg, vr_values *vr_values)
 	  res.argmin = argmin;
 	  res.argmax = argmax;
 	}
-      else if (vr->kind () == VR_ANTI_RANGE)
-	{
-	  /* Handle anti-ranges if/when bug 71690 is resolved.  */
-	}
-      else if (vr->varying_p () || vr->undefined_p ())
+      else
 	{
 	  /* The argument here may be the result of promoting the actual
 	     argument to int.  Try to determine the type of the actual
@@ -1420,7 +1406,7 @@ format_integer (const directive &dir, tree arg, vr_values *vr_values)
 	      if (code == INTEGER_CST)
 		{
 		  arg = gimple_assign_rhs1 (def);
-		  return format_integer (dir, arg, vr_values);
+		  return format_integer (dir, arg);
 		}
 
 	      if (code == NOP_EXPR)
@@ -1465,16 +1451,16 @@ format_integer (const directive &dir, tree arg, vr_values *vr_values)
       /* For unsigned conversions/directives or signed when
 	 the minimum is positive, use the minimum and maximum to compute
 	 the shortest and longest output, respectively.  */
-      res.range.min = format_integer (dir, argmin, vr_values).range.min;
-      res.range.max = format_integer (dir, argmax, vr_values).range.max;
+      res.range.min = format_integer (dir, argmin).range.min;
+      res.range.max = format_integer (dir, argmax).range.max;
     }
   else if (tree_int_cst_sgn (argmax) < 0)
     {
       /* For signed conversions/directives if maximum is negative,
 	 use the minimum as the longest output and maximum as the
 	 shortest output.  */
-      res.range.min = format_integer (dir, argmax, vr_values).range.min;
-      res.range.max = format_integer (dir, argmin, vr_values).range.max;
+      res.range.min = format_integer (dir, argmax).range.min;
+      res.range.max = format_integer (dir, argmin).range.max;
     }
   else
     {
@@ -1483,11 +1469,11 @@ format_integer (const directive &dir, tree arg, vr_values *vr_values)
 	 length of the output of both minimum and maximum and pick the
 	 longer.  */
       unsigned HOST_WIDE_INT max1
-	= format_integer (dir, argmin, vr_values).range.max;
+	= format_integer (dir, argmin).range.max;
       unsigned HOST_WIDE_INT max2
-	= format_integer (dir, argmax, vr_values).range.max;
+	= format_integer (dir, argmax).range.max;
       res.range.min
-	= format_integer (dir, integer_zero_node, vr_values).range.min;
+	= format_integer (dir, integer_zero_node).range.min;
       res.range.max = MAX (max1, max2);
     }
 
@@ -1836,7 +1822,7 @@ format_floating (const directive &dir, const HOST_WIDE_INT prec[2])
    ARG.  */
 
 static fmtresult
-format_floating (const directive &dir, tree arg, vr_values *)
+format_floating (const directive &dir, tree arg)
 {
   HOST_WIDE_INT prec[] = { dir.prec[0], dir.prec[1] };
   tree type = (dir.modifier == FMT_LEN_L || dir.modifier == FMT_LEN_ll
@@ -2110,7 +2096,7 @@ get_string_length (tree str, unsigned eltsize)
    vsprinf).  */
 
 static fmtresult
-format_character (const directive &dir, tree arg, vr_values *vr_values)
+format_character (const directive &dir, tree arg)
 {
   fmtresult res;
 
@@ -2123,7 +2109,7 @@ format_character (const directive &dir, tree arg, vr_values *vr_values)
       res.range.min = 0;
 
       HOST_WIDE_INT min, max;
-      if (get_int_range (arg, &min, &max, false, 0, vr_values))
+      if (get_int_range (arg, &min, &max, false, 0, dir.callstmt))
 	{
 	  if (min == 0 && max == 0)
 	    {
@@ -2186,7 +2172,7 @@ format_character (const directive &dir, tree arg, vr_values *vr_values)
    vsprinf).  */
 
 static fmtresult
-format_string (const directive &dir, tree arg, vr_values *)
+format_string (const directive &dir, tree arg)
 {
   fmtresult res;
 
@@ -2376,7 +2362,7 @@ format_string (const directive &dir, tree arg, vr_values *)
 /* Format plain string (part of the format string itself).  */
 
 static fmtresult
-format_plain (const directive &dir, tree, vr_values *)
+format_plain (const directive &dir, tree)
 {
   fmtresult res (dir.len);
   return res;
@@ -2386,7 +2372,7 @@ format_plain (const directive &dir, tree, vr_values *)
    should be diagnosed given the AVAILable space in the destination.  */
 
 static bool
-should_warn_p (const sprintf_dom_walker::call_info &info,
+should_warn_p (const call_info &info,
 	       const result_range &avail, const result_range &result)
 {
   if (result.max <= avail.min)
@@ -2457,7 +2443,7 @@ should_warn_p (const sprintf_dom_walker::call_info &info,
 
 static bool
 maybe_warn (substring_loc &dirloc, location_t argloc,
-	    const sprintf_dom_walker::call_info &info,
+	    const call_info &info,
 	    const result_range &avail_range, const result_range &res,
 	    const directive &dir)
 {
@@ -2737,9 +2723,8 @@ maybe_warn (substring_loc &dirloc, location_t argloc,
    in *RES.  Return true if the directive has been handled.  */
 
 static bool
-format_directive (const sprintf_dom_walker::call_info &info,
-		  format_result *res, const directive &dir,
-		  class vr_values *vr_values)
+format_directive (const call_info &info,
+		  format_result *res, const directive &dir)
 {
   /* Offset of the beginning of the directive from the beginning
      of the format string.  */
@@ -2764,7 +2749,7 @@ format_directive (const sprintf_dom_walker::call_info &info,
     return false;
 
   /* Compute the range of lengths of the formatted output.  */
-  fmtresult fmtres = dir.fmtfunc (dir, dir.arg, vr_values);
+  fmtresult fmtres = dir.fmtfunc (dir, dir.arg);
 
   /* Record whether the output of all directives is known to be
      bounded by some maximum, implying that their arguments are
@@ -3086,13 +3071,13 @@ format_directive (const sprintf_dom_walker::call_info &info,
    the directive.  */
 
 static size_t
-parse_directive (sprintf_dom_walker::call_info &info,
+parse_directive (call_info &info,
 		 directive &dir, format_result *res,
-		 const char *str, unsigned *argno,
-		 vr_values *vr_values)
+		 const char *str, unsigned *argno)
 {
   const char *pcnt = strchr (str, target_percent);
   dir.beg = str;
+  dir.callstmt = info.callstmt;
 
   if (size_t len = pcnt ? pcnt - str : *str ? strlen (str) : 1)
     {
@@ -3410,7 +3395,7 @@ parse_directive (sprintf_dom_walker::call_info &info,
   if (star_width)
     {
       if (INTEGRAL_TYPE_P (TREE_TYPE (star_width)))
-	dir.set_width (star_width, vr_values);
+	dir.set_width (star_width);
       else
 	{
 	  /* Width specified by a va_list takes on the range [0, -INT_MIN]
@@ -3443,7 +3428,7 @@ parse_directive (sprintf_dom_walker::call_info &info,
   if (star_precision)
     {
       if (INTEGRAL_TYPE_P (TREE_TYPE (star_precision)))
-	dir.set_precision (star_precision, vr_values);
+	dir.set_precision (star_precision);
       else
 	{
 	  /* Precision specified by a va_list takes on the range [-1, INT_MAX]
@@ -3526,9 +3511,8 @@ parse_directive (sprintf_dom_walker::call_info &info,
    on, false otherwise (e.g., when a unknown or unhandled directive was seen
    that caused the processing to be terminated early).  */
 
-bool
-sprintf_dom_walker::compute_format_length (call_info &info,
-					   format_result *res)
+static bool
+compute_format_length (call_info &info, format_result *res)
 {
   if (dump_file)
     {
@@ -3564,12 +3548,10 @@ sprintf_dom_walker::compute_format_length (call_info &info,
       directive dir = directive ();
       dir.dirno = dirno;
 
-      size_t n = parse_directive (info, dir, res, pf, &argno,
-				  evrp_range_analyzer.get_vr_values ());
+      size_t n = parse_directive (info, dir, res, pf, &argno);
 
       /* Return failure if the format function fails.  */
-      if (!format_directive (info, res, dir,
-			     evrp_range_analyzer.get_vr_values ()))
+      if (!format_directive (info, res, dir))
 	return false;
 
       /* Return success the directive is zero bytes long and it's
@@ -3617,7 +3599,7 @@ get_destination_size (tree dest)
    of its return values.  */
 
 static bool
-is_call_safe (const sprintf_dom_walker::call_info &info,
+is_call_safe (const call_info &info,
 	      const format_result &res, bool under4k,
 	      unsigned HOST_WIDE_INT retval[2])
 {
@@ -3676,7 +3658,7 @@ is_call_safe (const sprintf_dom_walker::call_info &info,
 
 static bool
 try_substitute_return_value (gimple_stmt_iterator *gsi,
-			     const sprintf_dom_walker::call_info &info,
+			     const call_info &info,
 			     const format_result &res)
 {
   tree lhs = gimple_get_lhs (info.callstmt);
@@ -3794,7 +3776,7 @@ try_substitute_return_value (gimple_stmt_iterator *gsi,
 
 static bool
 try_simplify_call (gimple_stmt_iterator *gsi,
-		   const sprintf_dom_walker::call_info &info,
+		   const call_info &info,
 		   const format_result &res)
 {
   unsigned HOST_WIDE_INT dummy[2];
@@ -3851,8 +3833,8 @@ get_user_idx_format (tree fndecl, unsigned *idx_args)
    functions and if so, handle it.  Return true if the call is removed
    and gsi_next should not be performed in the caller.  */
 
-bool
-sprintf_dom_walker::handle_gimple_call (gimple_stmt_iterator *gsi)
+static bool
+handle_gimple_call (gimple_stmt_iterator *gsi)
 {
   call_info info = call_info ();
 
@@ -4119,11 +4101,14 @@ sprintf_dom_walker::handle_gimple_call (gimple_stmt_iterator *gsi)
 	  /* Try to determine the range of values of the argument
 	     and use the greater of the two at level 1 and the smaller
 	     of them at level 2.  */
-	  const value_range *vr = evrp_range_analyzer.get_value_range (size);
-	  if (range_int_cst_p (vr))
+	  irange r;
+	  if (on_demand_get_range_on_stmt (r, size, info.callstmt)
+	      && !r.undefined_p ())
 	    {
-	      unsigned HOST_WIDE_INT minsize = TREE_INT_CST_LOW (vr->min ());
-	      unsigned HOST_WIDE_INT maxsize = TREE_INT_CST_LOW (vr->max ());
+	      tree max = wide_int_to_tree (TREE_TYPE (size), r.upper_bound ());
+	      tree min = wide_int_to_tree (TREE_TYPE (size), r.lower_bound ());
+	      unsigned HOST_WIDE_INT minsize = TREE_INT_CST_LOW (min);
+	      unsigned HOST_WIDE_INT maxsize = TREE_INT_CST_LOW (max);
 	      dstsize = warn_level < 2 ? maxsize : minsize;
 
 	      if (minsize > target_int_max ())
@@ -4137,7 +4122,7 @@ sprintf_dom_walker::handle_gimple_call (gimple_stmt_iterator *gsi)
 	      if (maxsize > target_int_max ())
 		posunder4k = false;
 	    }
-	  else if (vr->varying_p ())
+	  else
 	    {
 	      /* POSIX requires snprintf to fail if DSTSIZE is greater
 		 than INT_MAX.  Since SIZE's range is unknown, avoid
@@ -4257,18 +4242,14 @@ sprintf_dom_walker::handle_gimple_call (gimple_stmt_iterator *gsi)
   return call_removed;
 }
 
-edge
-sprintf_dom_walker::before_dom_children (basic_block bb)
+static void
+sprintf_walk (basic_block bb)
 {
-  evrp_range_analyzer.enter (bb);
   for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si); )
     {
       /* Iterate over statements, looking for function calls.  */
       gimple *stmt = gsi_stmt (si);
 
-      /* First record ranges generated by this statement.  */
-      evrp_range_analyzer.record_ranges_from_stmt (stmt, false);
-
       if (is_gimple_call (stmt) && handle_gimple_call (&si))
 	/* If handle_gimple_call returns true, the iterator is
 	   already pointing to the next statement.  */
@@ -4276,13 +4257,6 @@ sprintf_dom_walker::before_dom_children (basic_block bb)
 
       gsi_next (&si);
     }
-  return NULL;
-}
-
-void
-sprintf_dom_walker::after_dom_children (basic_block bb)
-{
-  evrp_range_analyzer.leave (bb);
 }
 
 /* Execute the pass for function FUN.  */
@@ -4292,22 +4266,9 @@ pass_sprintf_length::execute (function *fun)
 {
   init_target_to_host_charmap ();
 
-  calculate_dominance_info (CDI_DOMINATORS);
-  bool use_scev = optimize > 0 && flag_printf_return_value;
-  if (use_scev)
-    {
-      loop_optimizer_init (LOOPS_NORMAL);
-      scev_initialize ();
-    }
-
-  sprintf_dom_walker sprintf_dom_walker;
-  sprintf_dom_walker.walk (ENTRY_BLOCK_PTR_FOR_FN (fun));
-
-  if (use_scev)
-    {
-      scev_finalize ();
-      loop_optimizer_finalize ();
-    }
+  basic_block bb;
+  FOR_EACH_BB_FN (bb, fun)
+    sprintf_walk (bb);
 
   /* Clean up object size info.  */
   fini_object_sizes ();

gcc/gimple-ssa-warn-alloca.c

@@ -37,6 +37,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "calls.h"
 #include "cfgloop.h"
 #include "intl.h"
+#include "ssa-range.h"
 
 static unsigned HOST_WIDE_INT adjusted_warn_limit (bool);
 
@@ -56,8 +57,7 @@ class pass_walloca : public gimple_opt_pass
 {
 public:
   pass_walloca (gcc::context *ctxt)
-    : gimple_opt_pass(pass_data_walloca, ctxt), first_time_p (false)
-  {}
+    : gimple_opt_pass(pass_data_walloca, ctxt), first_time_p (false) {}
   opt_pass *clone () { return new pass_walloca (m_ctxt); }
   void set_pass_param (unsigned int n, bool param)
     {
@@ -100,12 +100,6 @@ enum alloca_type {
   // Alloca argument may be too large.
   ALLOCA_BOUND_MAYBE_LARGE,
 
-  // Alloca argument is bounded but of an indeterminate size.
-  ALLOCA_BOUND_UNKNOWN,
-
-  // Alloca argument was casted from a signed integer.
-  ALLOCA_CAST_FROM_SIGNED,
-
   // Alloca appears in a loop.
   ALLOCA_IN_LOOP,
 
@@ -136,6 +130,15 @@ public:
   }
 };
 
+/* Return TRUE if the user specified a limit for either VLAs or ALLOCAs.  */
+
+static bool
+warn_limit_specified_p (bool is_vla)
+{
+  unsigned HOST_WIDE_INT max = is_vla ? warn_vla_limit : warn_alloca_limit;
+  return max != HOST_WIDE_INT_MAX;
+}
+
 /* Return the value of the argument N to -Walloca-larger-than= or
    -Wvla-larger-than= adjusted for the target data model so that
    when N == HOST_WIDE_INT_MAX, the adjusted value is set to
@@ -159,40 +162,9 @@ adjusted_warn_limit (bool idx)
   return limits[idx];
 }
 
-
-// NOTE: When we get better range info, this entire function becomes
-// irrelevant, as it should be possible to get range info for an SSA
-// name at any point in the program.
-//
-// We have a few heuristics up our sleeve to determine if a call to
-// alloca() is within bounds.  Try them out and return the type of
-// alloca call with its assumed limit (if applicable).
-//
-// Given a known argument (ARG) to alloca() and an EDGE (E)
-// calculating said argument, verify that the last statement in the BB
-// in E->SRC is a gate comparing ARG to an acceptable bound for
-// alloca().  See examples below.
-//
-// If set, ARG_CASTED is the possible unsigned argument to which ARG
-// was casted to.  This is to handle cases where the controlling
-// predicate is looking at a casted value, not the argument itself.
-//    arg_casted = (size_t) arg;
-//    if (arg_casted < N)
-//      goto bb3;
-//    else
-//      goto bb5;
-//
-// MAX_SIZE is WARN_ALLOCA= adjusted for VLAs.  It is the maximum size
-// in bytes we allow for arg.
-
-static class alloca_type_and_limit
-alloca_call_type_by_arg (tree arg, tree arg_casted, edge e,
-			 unsigned HOST_WIDE_INT max_size)
+static struct alloca_type_and_limit
+alloca_call_type_by_arg (unsigned HOST_WIDE_INT max_size)
 {
-  basic_block bb = e->src;
-  gimple_stmt_iterator gsi = gsi_last_bb (bb);
-  gimple *last = gsi_stmt (gsi);
-
   const offset_int maxobjsize = tree_to_shwi (max_object_size ());
 
   /* When MAX_SIZE is greater than or equal to PTRDIFF_MAX treat
@@ -200,142 +172,18 @@ alloca_call_type_by_arg (tree arg, tree arg_casted, edge e,
      report them as (potentially) unbounded.  */
   alloca_type unbounded_result = (max_size < maxobjsize.to_uhwi ()
 				  ? ALLOCA_UNBOUNDED : ALLOCA_OK);
-
-  if (!last || gimple_code (last) != GIMPLE_COND)
-    {
-      return alloca_type_and_limit (unbounded_result);
-    }
-
-  enum tree_code cond_code = gimple_cond_code (last);
-  if (e->flags & EDGE_TRUE_VALUE)
-    ;
-  else if (e->flags & EDGE_FALSE_VALUE)
-    cond_code = invert_tree_comparison (cond_code, false);
-  else
-      return alloca_type_and_limit (unbounded_result);
-
-  // Check for:
-  //   if (ARG .COND. N)
-  //     goto <bb 3>;
-  //   else
-  //     goto <bb 4>;
-  //   <bb 3>:
-  //   alloca(ARG);
-  if ((cond_code == LE_EXPR
-       || cond_code == LT_EXPR
-       || cond_code == GT_EXPR
-       || cond_code == GE_EXPR)
-      && (gimple_cond_lhs (last) == arg
-	  || gimple_cond_lhs (last) == arg_casted))
-    {
-      if (TREE_CODE (gimple_cond_rhs (last)) == INTEGER_CST)
-	{
-	  tree rhs = gimple_cond_rhs (last);
-	  int tst = wi::cmpu (wi::to_widest (rhs), max_size);
-	  if ((cond_code == LT_EXPR && tst == -1)
-	      || (cond_code == LE_EXPR && (tst == -1 || tst == 0)))
-	    return alloca_type_and_limit (ALLOCA_OK);
-	  else
-	    {
-	      // Let's not get too specific as to how large the limit
-	      // may be.  Someone's clearly an idiot when things
-	      // degrade into "if (N > Y) alloca(N)".
-	      if (cond_code == GT_EXPR || cond_code == GE_EXPR)
-		rhs = integer_zero_node;
-	      return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE,
-					    wi::to_wide (rhs));
-	    }
-	}
-      else
-	{
-	  /* Analogous to ALLOCA_UNBOUNDED, when MAX_SIZE is greater
-	     than or equal to PTRDIFF_MAX, treat allocations with
-	     an unknown bound as OK.  */
-	  alloca_type unknown_result
-	    = (max_size < maxobjsize.to_uhwi ()
-	       ? ALLOCA_BOUND_UNKNOWN : ALLOCA_OK);
-	  return alloca_type_and_limit (unknown_result);
-	}
-    }
-
-  // Similarly, but check for a comparison with an unknown LIMIT.
-  //   if (LIMIT .COND. ARG)
-  //     alloca(arg);
-  //
-  //   Where LIMIT has a bound of unknown range.
-  //
-  // Note: All conditions of the form (ARG .COND. XXXX) where covered
-  // by the previous check above, so we only need to look for (LIMIT
-  // .COND. ARG) here.
-  tree limit = gimple_cond_lhs (last);
-  if ((gimple_cond_rhs (last) == arg
-       || gimple_cond_rhs (last) == arg_casted)
-      && TREE_CODE (limit) == SSA_NAME)
-    {
-      wide_int min, max;
-      value_range_kind range_type = get_range_info (limit, &min, &max);
-
-      if (range_type == VR_UNDEFINED || range_type == VR_VARYING)
-	return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN);
-
-      // ?? It looks like the above `if' is unnecessary, as we never
-      // get any VR_RANGE or VR_ANTI_RANGE here.  If we had a range
-      // for LIMIT, I suppose we would have taken care of it in
-      // alloca_call_type(), or handled above where we handle (ARG .COND. N).
-      //
-      // If this ever triggers, we should probably figure out why and
-      // handle it, though it is likely to be just an ALLOCA_UNBOUNDED.
-      return alloca_type_and_limit (unbounded_result);
-    }
-
   return alloca_type_and_limit (unbounded_result);
 }
 
-// Return TRUE if SSA's definition is a cast from a signed type.
-// If so, set *INVALID_CASTED_TYPE to the signed type.
-
-static bool
-cast_from_signed_p (tree ssa, tree *invalid_casted_type)
-{
-  gimple *def = SSA_NAME_DEF_STMT (ssa);
-  if (def
-      && !gimple_nop_p (def)
-      && gimple_assign_cast_p (def)
-      && !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def))))
-    {
-      *invalid_casted_type = TREE_TYPE (gimple_assign_rhs1 (def));
-      return true;
-    }
-  return false;
-}
-
-// Return TRUE if X has a maximum range of MAX, basically covering the
-// entire domain, in which case it's no range at all.
-
-static bool
-is_max (tree x, wide_int max)
-{
-  return wi::max_value (TREE_TYPE (x)) == max;
-}
-
 // Analyze the alloca call in STMT and return the alloca type with its
 // corresponding limit (if applicable).  IS_VLA is set if the alloca
 // call was created by the gimplifier for a VLA.
-//
-// If the alloca call may be too large because of a cast from a signed
-// type to an unsigned type, set *INVALID_CASTED_TYPE to the
-// problematic signed type.
 
 static class alloca_type_and_limit
-alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type)
+alloca_call_type (global_ranger &ranger, gimple *stmt, bool is_vla)
 {
   gcc_assert (gimple_alloca_call_p (stmt));
-  bool tentative_cast_from_signed = false;
   tree len = gimple_call_arg (stmt, 0);
-  tree len_casted = NULL;
-  wide_int min, max;
-  edge_iterator ei;
-  edge e;
 
   gcc_assert (!is_vla || warn_vla_limit >= 0);
   gcc_assert (is_vla || warn_alloca_limit >= 0);
@@ -362,118 +210,9 @@ alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type)
       return alloca_type_and_limit (ALLOCA_OK);
     }
 
-  // Check the range info if available.
-  if (TREE_CODE (len) == SSA_NAME)
-    {
-      value_range_kind range_type = get_range_info (len, &min, &max);
-      if (range_type == VR_RANGE)
-	{
-	  if (wi::leu_p (max, max_size))
-	    return alloca_type_and_limit (ALLOCA_OK);
-	  else
-	    {
-	      // A cast may have created a range we don't care
-	      // about.  For instance, a cast from 16-bit to
-	      // 32-bit creates a range of 0..65535, even if there
-	      // is not really a determinable range in the
-	      // underlying code.  In this case, look through the
-	      // cast at the original argument, and fall through
-	      // to look at other alternatives.
-	      //
-	      // We only look at through the cast when its from
-	      // unsigned to unsigned, otherwise we may risk
-	      // looking at SIGNED_INT < N, which is clearly not
-	      // what we want.  In this case, we'd be interested
-	      // in a VR_RANGE of [0..N].
-	      //
-	      // Note: None of this is perfect, and should all go
-	      // away with better range information.  But it gets
-	      // most of the cases.
-	      gimple *def = SSA_NAME_DEF_STMT (len);
-	      if (gimple_assign_cast_p (def))
-		{
-		  tree rhs1 = gimple_assign_rhs1 (def);
-		  tree rhs1type = TREE_TYPE (rhs1);
-
-		  // Bail if the argument type is not valid.
-		  if (!INTEGRAL_TYPE_P (rhs1type))
-		    return alloca_type_and_limit (ALLOCA_OK);
-
-		  if (TYPE_UNSIGNED (rhs1type))
-		    {
-		      len_casted = rhs1;
-		      range_type = get_range_info (len_casted, &min, &max);
-		    }
-		}
-	      // An unknown range or a range of the entire domain is
-	      // really no range at all.
-	      if (range_type == VR_VARYING
-		  || (!len_casted && is_max (len, max))
-		  || (len_casted && is_max (len_casted, max)))
-		{
-		  // Fall through.
-		}
-	      else if (range_type == VR_ANTI_RANGE)
-		return alloca_type_and_limit (ALLOCA_UNBOUNDED);
-
-	      if (range_type != VR_VARYING)
-		{
-		  const offset_int maxobjsize
-		    = wi::to_offset (max_object_size ());
-		  alloca_type result = (max_size < maxobjsize
-					? ALLOCA_BOUND_MAYBE_LARGE : ALLOCA_OK);
-		  return alloca_type_and_limit (result, max);
-		}
-	    }
-	}
-      else if (range_type == VR_ANTI_RANGE)
-	{
-	  // There may be some wrapping around going on.  Catch it
-	  // with this heuristic.  Hopefully, this VR_ANTI_RANGE
-	  // nonsense will go away, and we won't have to catch the
-	  // sign conversion problems with this crap.
-	  //
-	  // This is here to catch things like:
-	  // void foo(signed int n) {
-	  //   if (n < 100)
-	  //     alloca(n);
-	  //   ...
-	  // }
-	  if (cast_from_signed_p (len, invalid_casted_type))
-	    {
-	      // Unfortunately this also triggers:
-	      //
-	      // __SIZE_TYPE__ n = (__SIZE_TYPE__)blah;
-	      // if (n < 100)
-	      //   alloca(n);
-	      //
-	      // ...which is clearly bounded.  So, double check that
-	      // the paths leading up to the size definitely don't
-	      // have a bound.
-	      tentative_cast_from_signed = true;
-	    }
-	}
-      // No easily determined range and try other things.
-    }
-
-  // If we couldn't find anything, try a few heuristics for things we
-  // can easily determine.  Check these misc cases but only accept
-  // them if all predecessors have a known bound.
-  class alloca_type_and_limit ret = alloca_type_and_limit (ALLOCA_OK);
-  FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
-    {
-      gcc_assert (!len_casted || TYPE_UNSIGNED (TREE_TYPE (len_casted)));
-      ret = alloca_call_type_by_arg (len, len_casted, e, max_size);
-      if (ret.type != ALLOCA_OK)
-	break;
-    }
-
-  if (ret.type != ALLOCA_OK && tentative_cast_from_signed)
-    ret = alloca_type_and_limit (ALLOCA_CAST_FROM_SIGNED);
-
+  struct alloca_type_and_limit ret = alloca_type_and_limit (ALLOCA_OK);
   // If we have a declared maximum size, we can take it into account.
-  if (ret.type != ALLOCA_OK
-      && gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
+  if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX))
     {
       tree arg = gimple_call_arg (stmt, 2);
       if (compare_tree_int (arg, max_size) <= 0)
@@ -486,9 +225,29 @@ alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type)
 				? ALLOCA_BOUND_MAYBE_LARGE : ALLOCA_OK);
 	  ret = alloca_type_and_limit (result, wi::to_wide (arg));
 	}
+      return ret;
     }
 
-  return ret;
+  // If the user specified a limit, use it possibly warn.
+  irange r;
+  if (warn_limit_specified_p (is_vla)
+      && TREE_CODE (len) == SSA_NAME
+      && ranger.range_of_expr (r, len, stmt)
+      && !r.varying_p ())
+    {
+      // The invalid bits are anything outside of [0, MAX_SIZE].
+      static irange invalid_range (VR_ANTI_RANGE,
+				   build_int_cst (size_type_node, 0),
+				   build_int_cst (size_type_node, max_size));
+
+      r.intersect (invalid_range);
+      if (!r.undefined_p ())
+	return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE,
+				      wi::to_wide (integer_zero_node));
+      return alloca_type_and_limit (ALLOCA_OK);
+    }
+
+  return alloca_call_type_by_arg (max_size);
 }
 
 // Return TRUE if STMT is in a loop, otherwise return FALSE.
@@ -504,6 +263,7 @@ in_loop_p (gimple *stmt)
 unsigned int
 pass_walloca::execute (function *fun)
 {
+  global_ranger ranger;
   basic_block bb;
   FOR_EACH_BB_FN (bb, fun)
     {
@@ -535,9 +295,8 @@ pass_walloca::execute (function *fun)
 	  else if (warn_alloca_limit < 0)
 	    continue;
 
-	  tree invalid_casted_type = NULL;
 	  class alloca_type_and_limit t
-	    = alloca_call_type (stmt, is_vla, &invalid_casted_type);
+	    = alloca_call_type (ranger, stmt, is_vla);
 
 	  unsigned HOST_WIDE_INT adjusted_alloca_limit
 	    = adjusted_warn_limit (false);
@@ -595,11 +354,6 @@ pass_walloca::execute (function *fun)
 		  }
 	      }
 	      break;
-	    case ALLOCA_BOUND_UNKNOWN:
-	      warning_at (loc, wcode,
-			  is_vla ? G_("variable-length array bound is unknown")
-			  : G_("%<alloca%> bound is unknown"));
-	      break;
 	    case ALLOCA_UNBOUNDED:
 	      warning_at (loc, wcode,
 			  is_vla ? G_("unbounded use of variable-length array")
@@ -609,16 +363,6 @@ pass_walloca::execute (function *fun)
 	      gcc_assert (!is_vla);
 	      warning_at (loc, wcode, "use of %<alloca%> within a loop");
 	      break;
-	    case ALLOCA_CAST_FROM_SIGNED:
-	      gcc_assert (invalid_casted_type != NULL_TREE);
-	      warning_at (loc, wcode,
-			  is_vla ? G_("argument to variable-length array "
-				      "may be too large due to "
-				      "conversion from %qT to %qT")
-			  : G_("argument to %<alloca%> may be too large "
-			       "due to conversion from %qT to %qT"),
-			  invalid_casted_type, size_type_node);
-	      break;
 	    case ALLOCA_ARG_IS_ZERO:
 	      warning_at (loc, wcode,
 			  is_vla ? G_("argument to variable-length array "

gcc/gimple-ssa-warn-restrict.c

@@ -30,6 +30,7 @@
 #include "builtins.h"
 #include "ssa.h"
 #include "gimple-pretty-print.h"
+#include "ssa-range.h"
 #include "gimple-ssa-warn-restrict.h"
 #include "diagnostic-core.h"
 #include "fold-const.h"
@@ -78,21 +79,10 @@ pass_wrestrict::gate (function *fun ATTRIBUTE_UNUSED)
   return warn_array_bounds || warn_restrict || warn_stringop_overflow;
 }
 
-/* Class to walk the basic blocks of a function in dominator order.  */
-class wrestrict_dom_walker : public dom_walker
-{
- public:
-  wrestrict_dom_walker () : dom_walker (CDI_DOMINATORS) {}
+static void check_call (gimple *);
 
-  edge before_dom_children (basic_block) FINAL OVERRIDE;
-  bool handle_gimple_call (gimple_stmt_iterator *);
-
- private:
-  void check_call (gimple *);
-};
-
-edge
-wrestrict_dom_walker::before_dom_children (basic_block bb)
+static void
+wrestrict_walk (basic_block bb)
 {
   /* Iterate over statements, looking for function calls.  */
   for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
@@ -104,19 +94,14 @@ wrestrict_dom_walker::before_dom_children (basic_block bb)
 
       check_call (stmt);
     }
-
-  return NULL;
 }
 
-/* Execute the pass for function FUN, walking in dominator order.  */
-
 unsigned
 pass_wrestrict::execute (function *fun)
 {
-  calculate_dominance_info (CDI_DOMINATORS);
-
-  wrestrict_dom_walker walker;
-  walker.walk (ENTRY_BLOCK_PTR_FOR_FN (fun));
+  basic_block bb;
+  FOR_EACH_BB_FN (bb, fun)
+    wrestrict_walk (bb);
 
   return 0;
 }
@@ -158,11 +143,13 @@ public:
      only the destination reference is.  */
   bool strbounded_p;
 
-  builtin_memref (tree, tree);
+  builtin_memref (gimple *, tree, tree);
 
   tree offset_out_of_bounds (int, offset_int[2]) const;
 
 private:
+  /* Built-in call.  */
+  gimple *call;
 
   /* Ctor helper to set or extend OFFRANGE based on argument.  */
   void extend_offset_range (tree);
@@ -229,7 +216,7 @@ class builtin_access
    a size SIZE in bytes.  If SIZE is NULL_TREE then the size is assumed
    to be unknown.  */
 
-builtin_memref::builtin_memref (tree expr, tree size)
+builtin_memref::builtin_memref (gimple *_call, tree expr, tree size)
 : ptr (expr),
   ref (),
   base (),
@@ -238,7 +225,8 @@ builtin_memref::builtin_memref (tree expr, tree size)
   offrange (),
   sizrange (),
   maxobjsize (tree_to_shwi (max_object_size ())),
-  strbounded_p ()
+  strbounded_p (),
+  call (_call)
 {
   /* Unfortunately, wide_int default ctor is a no-op so array members
      of the type must be set individually.  */
@@ -257,7 +245,7 @@ builtin_memref::builtin_memref (tree expr, tree size)
       tree range[2];
       /* Determine the size range, allowing for the result to be [0, 0]
 	 for SIZE in the anti-range ~[0, N] where N >= PTRDIFF_MAX.  */
-      get_size_range (size, range, true);
+      get_size_range (size, range, true, call);
       sizrange[0] = wi::to_offset (range[0]);
       sizrange[1] = wi::to_offset (range[1]);
       /* get_size_range returns SIZE_MAX for the maximum size.
@@ -298,6 +286,28 @@ builtin_memref::builtin_memref (tree expr, tree size)
     }
 }
 
+/* Get the range SSA would have if control flowed to STMT.  This is
+   the ranger equivalence of get_range_info.  */
+
+static inline value_range_kind
+ranger_get_range_info (gimple *stmt, tree ssa, wide_int *min, wide_int *max)
+{
+  /* Don't call the ranger if we have no CFG.  */
+  if (DECL_SAVED_TREE (cfun->decl))
+    return VR_VARYING;
+
+  irange r;
+  if (!on_demand_get_range_on_stmt (r, ssa, stmt))
+    return VR_VARYING;
+  if (r.undefined_p ())
+    return VR_UNDEFINED;
+
+  value_range_base vr = irange_to_value_range (r);
+  *min = wi::to_wide (vr.min ());
+  *max = wi::to_wide (vr.max ());
+  return vr.kind ();
+}
+
 /* Ctor helper to set or extend OFFRANGE based on the OFFSET argument.
    Pointer offsets are represented as unsigned sizetype but must be
    treated as signed.  */
@@ -321,7 +331,7 @@ builtin_memref::extend_offset_range (tree offset)
       /* A pointer offset is represented as sizetype but treated
 	 as signed.  */
       wide_int min, max;
-      value_range_kind rng = get_range_info (offset, &min, &max);
+      value_range_kind rng = ranger_get_range_info (call, offset, &min, &max);
       if (rng == VR_ANTI_RANGE && wi::lts_p (max, min))
 	{
 	  /* Convert an anti-range whose upper bound is less than
@@ -737,7 +747,7 @@ builtin_access::builtin_access (gimple *call, builtin_memref &dst,
 
       tree size = gimple_call_arg (call, sizeargno);
       tree range[2];
-      if (get_size_range (size, range, true))
+      if (get_size_range (size, range, true, call))
 	{
 	  bounds[0] = wi::to_offset (range[0]);
 	  bounds[1] = wi::to_offset (range[1]);
@@ -1815,8 +1825,8 @@ maybe_diag_access_bounds (location_t loc, gimple *call, tree func, int strict,
 /* Check a CALL statement for restrict-violations and issue warnings
    if/when appropriate.  */
 
-void
-wrestrict_dom_walker::check_call (gimple *call)
+static void
+check_call (gimple *call)
 {
   /* Avoid checking the call if it has already been diagnosed for
      some reason.  */
@@ -1932,8 +1942,8 @@ check_bounds_or_overlap (gimple *call, tree dst, tree src, tree dstsize,
 
   tree func = gimple_call_fndecl (call);
 
-  builtin_memref dstref (dst, dstsize);
-  builtin_memref srcref (src, srcsize);
+  builtin_memref dstref (call, dst, dstsize);
+  builtin_memref srcref (call, src, srcsize);
 
   builtin_access acs (call, dstref, srcref);
 

gcc/grange.cc

@@ -0,0 +1,363 @@
+/* Code for range related grange gimple statement.
+   Copyright (C) 2019 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@redhat.com>
+   and 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 "insn-codes.h"
+#include "rtl.h"
+#include "tree.h"
+#include "gimple.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "optabs-tree.h"
+#include "gimple-pretty-print.h"
+#include "diagnostic-core.h"
+#include "flags.h"
+#include "fold-const.h"
+#include "stor-layout.h"
+#include "calls.h"
+#include "cfganal.h"
+#include "gimple-fold.h"
+#include "tree-eh.h"
+#include "gimple-iterator.h"
+#include "gimple-walk.h"
+#include "tree-cfg.h"
+#include "wide-int.h"
+#include "range.h"
+#include "grange.h"
+#include "ssa-range.h"
+
+// This function looks for situations when walking the use/def chains
+// may provide additonal contextual range information not exposed on
+// this statement.  Like knowing the IMAGPART return value from a
+// builtin function is a boolean result.
+
+void
+gimple_range_adjustment (const grange *s, irange &res)
+{
+  switch (gimple_expr_code (s))
+    {
+    case IMAGPART_EXPR:
+      {
+	irange r;
+	tree name;
+	tree type = TREE_TYPE (gimple_assign_lhs (s));
+
+	name = TREE_OPERAND (gimple_assign_rhs1 (s), 0);
+	if (TREE_CODE (name) == SSA_NAME)
+	  {
+	    gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+	    if (def_stmt && is_gimple_call (def_stmt)
+		&& gimple_call_internal_p (def_stmt))
+	      {
+		switch (gimple_call_internal_fn (def_stmt))
+		  {
+		  case IFN_ADD_OVERFLOW:
+		  case IFN_SUB_OVERFLOW:
+		  case IFN_MUL_OVERFLOW:
+		  case IFN_ATOMIC_COMPARE_EXCHANGE:
+		    r.set_varying (boolean_type_node);
+		    range_cast (r, type);
+		    res.intersect (r);
+		  default:
+		    break;
+		  }
+	      }
+	  }
+	break;
+      }
+
+    default:
+      break;
+    }
+}
+
+
+// This file implements the gimple range statement and associated data.
+// the grange statement kind provides access to the range-op fold machinery
+// as well as to a set of range adjustemnts which are gimple IL aware.
+//
+// This allows a statement to make adjustments to operands
+// or results based on IL contextual information such as specific feeding
+// statements or operand position.
+//
+// A table is indexed by tree-code which provides any neccessary code
+// for implementing the IL specific work. It is modelled after the range op
+// table where a class is implemented for a given tree code, and
+// auto-registered into the table for use when it is encountered.
+
+static gimple *
+calc_single_range (irange &r, gswitch *sw, edge e)
+{
+  unsigned x, lim;
+  lim = gimple_switch_num_labels (sw);
+  tree type = TREE_TYPE (gimple_switch_index (sw));
+
+  // ADA currently has cases where the index is 64 bits and the case
+  // arguments are  32 bit, causing a trap when we create a case_range.
+  // Until this is resolved (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87798)
+  // punt on these switches.  
+  // cfamily fails during a bootstrap due to a signed index and unsigned cases.
+  // so changing to types_compatible_p for now.
+  tree case_type = TREE_TYPE (CASE_LOW (gimple_switch_label (sw, 1)));
+  if (lim > 1 && !types_compatible_p (type, case_type))
+    return NULL;
+
+
+  if (e != gimple_switch_default_edge (cfun, sw))
+    {
+      r.set_undefined ();
+      // Loop through all the switches edges, ignoring the default edge.
+      // unioning the ranges together.
+      for (x = 1; x < lim; x++)
+	{
+	  if (gimple_switch_edge (cfun, sw, x) != e)
+	    continue;
+	  tree low = CASE_LOW (gimple_switch_label (sw, x));
+	  tree high = CASE_HIGH (gimple_switch_label (sw, x));
+	  if (!high)
+	    high = low;
+	  irange case_range (low, high);
+	  r.union_ (case_range);
+	}
+    }
+  else
+    {
+      r.set_varying (type);
+      // Loop through all the switches edges, ignoring the default edge.
+      // intersecting the ranges not covered by the case.
+      for (x = 1; x < lim; x++)
+	{
+	  tree low = CASE_LOW (gimple_switch_label (sw, x));
+	  tree high = CASE_HIGH (gimple_switch_label (sw, x));
+	  if (!high)
+	    high = low;
+	  irange case_range (VR_ANTI_RANGE, low, high);
+	  r.intersect (case_range);
+	}
+    }
+  return sw;
+}
+
+
+// If there is a range control statment at the end of block BB, return it.
+
+gimple_stmt_iterator
+gsi_outgoing_range_stmt (basic_block bb)
+{
+  gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
+  if (!gsi_end_p (gsi))
+    {
+      gimple *s = gsi_stmt (gsi);
+      if (is_a<gcond *> (s) || is_a<gswitch *> (s))
+	return gsi;
+    }
+  return gsi_none ();
+}
+
+gimple *
+gimple_outgoing_range_stmt_p (basic_block bb)
+{
+  // This will return NULL if there is not a branch statement.
+  return gsi_stmt (gsi_outgoing_range_stmt (bb));
+}
+
+// Calculate the range forced on on edge E by control flow, if any,  and
+// return it in R.  Return the statment which defines the range, otherwise
+// return NULL;
+
+gimple *
+gimple_outgoing_edge_range_p (irange &r, edge e)
+{
+  // Determine if there is an outgoing edge.
+  gimple *s = gimple_outgoing_range_stmt_p (e->src);
+  if (!s)
+    return NULL;
+  if (is_a<gcond *> (s))
+    {
+      if (e->flags & EDGE_TRUE_VALUE)
+	r = irange (boolean_true_node, boolean_true_node);
+      else if (e->flags & EDGE_FALSE_VALUE)
+	r = irange (boolean_false_node, boolean_false_node);
+      else
+	gcc_unreachable ();
+      return s;
+    }
+
+  gcc_checking_assert (is_a<gswitch *> (s));
+  gswitch *sw = as_a<gswitch *> (s);
+  tree type = TREE_TYPE (gimple_switch_index (sw));
+
+  if (!irange::supports_type_p (type))
+    return NULL;
+
+  return calc_single_range (r, sw, e);
+}
+
+
+// ------------------------------------------------------------------------
+// grange statement kind implementation. 
+
+// Return the grange_adjust pointer for this statement, if there is one..
+
+// Return the range_operator pointer for this statement.
+
+inline range_operator *
+gimple_range_handler (const grange *s)
+{
+  return range_op_handler (gimple_expr_code (s), gimple_expr_type (s));
+}
+
+// Return the first operand of this statement if it is a valid operand 
+// supported by ranges, otherwise return NULL_TREE. 
+
+tree
+gimple_range_operand1 (const grange *s)
+{
+  switch (gimple_code (s))
+    {
+      case GIMPLE_COND:
+        return gimple_cond_lhs (s);
+      case GIMPLE_ASSIGN:
+        {
+	  tree expr = gimple_assign_rhs1 (s);
+	  if (gimple_assign_rhs_code (s) == ADDR_EXPR)
+	    {
+	      // If the base address is an SSA_NAME, we return it here.
+	      // This allows processing of the range of that name, while the
+	      // rest of the expression is simply ignored.  The code in
+	      // range_ops will see the ADDR_EXPR and do the right thing.
+	      tree base = get_base_address (TREE_OPERAND (expr, 0));
+	      if (base != NULL_TREE && TREE_CODE (base) == MEM_REF)
+	        {
+		  // If the base address is an SSA_NAME, return it. 
+		  tree b = TREE_OPERAND (base, 0);
+		  if (TREE_CODE (b) == SSA_NAME)
+		    return b;
+		}
+	    }
+	  return expr;
+	}
+      default:
+        break;
+    }
+  return NULL;
+}
+
+
+// Fold this unary statement uusing R1 as operand1's range, returning the
+// result in RES.  Return false if the operation fails.
+
+bool
+gimple_range_fold (const grange *s, irange &res, const irange &r1)
+{
+  tree type = gimple_expr_type (s);;
+  irange r2 (type);
+  // Single ssa operations require the LHS type as the second range.
+
+  return gimple_range_fold (s, res, r1, r2);
+}
+
+
+// Fold this binary statement using R1 and R2 as the operands ranges,
+// returning the result in RES.  Return false if the operation fails.
+
+bool
+gimple_range_fold (const grange *s, irange &res, const irange &r1,
+		   const irange &r2)
+{
+  irange adj_range;
+
+  res = gimple_range_handler (s)->fold_range (gimple_expr_type (s), r1, r2);
+
+  // If there are any gimple lookups, do those now.
+  gimple_range_adjustment (s, res);
+  return true;
+}
+
+
+// Calculate what we can determine of the range of this unary statement's
+// operand if the lhs of the expression has the range LHS_RANGE.  Return false
+// if nothing can be determined.
+
+bool
+gimple_range_calc_op1 (const grange *s, irange &r, const irange &lhs_range)
+{  
+  irange type_range;
+  gcc_checking_assert (gimple_num_ops (s) < 3);
+  // An empty range is viral, so return an empty range.
+  
+  tree type = TREE_TYPE (gimple_range_operand1 (s));
+  if (lhs_range.undefined_p ())
+    {
+      r.set_undefined ();
+      return true;
+    }
+  // Unary operations require the type of the first operand in the second range
+  // position.
+  type_range.set_varying (type);
+  return gimple_range_handler (s)->op1_range (r, type, lhs_range, type_range);
+}
+
+
+// Calculate what we can determine of the range of this statement's first 
+// operand if the lhs of the expression has the range LHS_RANGE and the second
+// operand has the range OP2_RANGE.  Return false if nothing can be determined.
+
+bool
+gimple_range_calc_op1 (const grange *s, irange &r, const irange &lhs_range,
+		       const irange &op2_range)
+{  
+  // Unary operation are allowed to pass a range in for second operand
+  // as there are often additional restrictions beyond the type which can
+  // be imposed.  See operator_cast::op1_irange.()
+  
+  tree type = TREE_TYPE (gimple_range_operand1 (s));
+  // An empty range is viral, so return an empty range.
+  if (op2_range.undefined_p () || lhs_range.undefined_p ())
+    {
+      r.set_undefined ();
+      return true;
+    }
+  return gimple_range_handler (s)->op1_range (r, type, lhs_range, op2_range);
+}
+
+
+// Calculate what we can determine of the range of this statement's second
+// operand if the lhs of the expression has the range LHS_RANGE and the first
+// operand has the range OP1_RANGE.  Return false if nothing can be determined.
+
+bool
+gimple_range_calc_op2 (const grange *s, irange &r, const irange &lhs_range,
+		       const irange &op1_range)
+{  
+  tree type = TREE_TYPE (gimple_range_operand2 (s));
+  // An empty range is viral, so return an empty range.
+  if (op1_range.undefined_p () || lhs_range.undefined_p ())
+    {
+      r.set_undefined ();
+      return true;
+    }
+  return gimple_range_handler (s)->op2_range (r, type, lhs_range, op1_range);
+}

gcc/grange.h

@@ -0,0 +1,153 @@
+/* Header file for grange gimple statement implementation.
+   Copyright (C) 2019 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@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/>.  */
+
+#ifndef GCC_GRANGE_H
+#define GCC_GRANGE_H
+
+#include "range.h"
+#include "range-op.h"
+
+// Gimple statement which supports range_op operations.
+// This can map to gimple assign or cond statements, so quick access to the
+// operands is provided so the user does not need to know which it is.
+// Also provides access to the range operator interface taking care of 
+// filling in unary operand requirements from the statement.
+//
+// usage is typical gimple statement style:
+// foo (gimple *s)
+// {
+//   grange gr = s;
+//   if (!gr)
+//     return false;  // NULL means this stmt cannot generate ranges.
+//   < ...decide on some ranges... >
+//   /* And call the range fold routine for this statement.  */
+//   return gimple_range_fold (gr, res_range, op1_range, op2_range);
+
+class GTY((tag("GCC_SSA_RANGE_OPERATOR")))
+  grange: public gimple
+{
+  // Adds no new fields, adds invariant 
+  // stmt->code == GIMPLE_ASSIGN || stmt->code == GIMPLE_COND
+  // and there is a range_operator handler for gimple_expr_code().
+};
+
+template <>
+template <>
+inline bool
+is_a_helper <const grange *>::test (const gimple *gs)
+{ 
+  // Supported statement kind and there is a handler for the expression code.
+  if (dyn_cast<const gassign *> (gs) || dyn_cast<const gcond *>(gs))
+    {
+      enum tree_code c = gimple_expr_code (gs);
+      tree expr_type = gimple_expr_type (gs);
+      return range_op_handler (c, expr_type);
+    }
+  return false;
+}
+
+template <>
+template <>
+inline bool
+is_a_helper <grange *>::test (gimple *gs)
+{ 
+  // Supported statement kind and there is a handler for the expression code.
+  // Supported statement kind and there is a handler for the expression code.
+  if (dyn_cast<gassign *> (gs) || dyn_cast<gcond *>(gs))
+    {
+      enum tree_code c = gimple_expr_code (gs);
+      tree expr_type = gimple_expr_type (gs);
+      return range_op_handler (c, expr_type);
+    }
+  return false;
+}
+
+// Return the LHS of this statement. If there isn't a LHS return NULL_TREE.
+
+static inline tree
+gimple_range_lhs (const grange *s)
+{
+  if (gimple_code (s) == GIMPLE_ASSIGN)
+    return gimple_assign_lhs (s);
+  return NULL_TREE;
+}
+
+
+// Return the second operand of this statement, otherwise return NULL_TREE.
+
+static inline tree
+gimple_range_operand2 (const grange *s)
+{
+  if (gimple_code (s) == GIMPLE_COND)
+    return gimple_cond_rhs (s);
+
+  // At this point it must be an assignemnt statement.
+  if (gimple_num_ops (s) >= 3)
+    return gimple_assign_rhs2 (s);
+  return NULL_TREE;
+}
+
+
+
+extern tree gimple_range_operand1 (const grange *s);
+extern bool gimple_range_fold (const grange *s, irange &res,
+			       const irange &r1);
+extern bool gimple_range_fold (const grange *s, irange &res,
+			       const irange &r1, const irange &r2);
+extern bool gimple_range_calc_op1 (const grange *s, irange &r,
+				   const irange &lhs_range);
+extern bool gimple_range_calc_op1 (const grange *s, irange &r,
+				   const irange &lhs_range,
+				   const irange &op2_range);
+extern bool gimple_range_calc_op2 (const grange *s, irange &r,
+				   const irange &lhs_range,
+				   const irange &op1_range);
+
+
+extern gimple_stmt_iterator gsi_outgoing_range_stmt (basic_block bb);
+extern gimple *gimple_outgoing_range_stmt_p (basic_block bb);
+extern gimple *gimple_outgoing_edge_range_p (irange &r, edge e);
+
+static inline tree
+valid_range_ssa_p (tree exp)
+{
+  if (exp && TREE_CODE (exp) == SSA_NAME && irange::supports_ssa_p (exp))
+    return exp;
+  return NULL_TREE;
+}
+
+static inline irange
+ssa_name_range (tree name)
+{
+  gcc_checking_assert (irange::supports_ssa_p (name));
+  tree type = TREE_TYPE (name);
+  if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
+    {
+      // Return a range from an SSA_NAME's available range.  
+      wide_int min, max;
+      enum value_range_kind kind = get_range_info (name, &min, &max);
+      return irange (kind, type, min, max);
+    }
+ // Otherwise return range for the type.
+ return irange (type);
+}
+
+
+#endif // GCC_GRANGE_H

gcc/opts.c

@@ -526,6 +526,7 @@ static const struct default_options default_options_table[] =
     { OPT_LEVELS_2_PLUS, OPT_ftree_switch_conversion, NULL, 1 },
     { OPT_LEVELS_2_PLUS, OPT_ftree_tail_merge, NULL, 1 },
     { OPT_LEVELS_2_PLUS, OPT_ftree_vrp, NULL, 1 },
+    { OPT_LEVELS_2_PLUS, OPT_ftree_rvrp, NULL, 1 },
     { OPT_LEVELS_2_PLUS, OPT_fvect_cost_model_, NULL, VECT_COST_MODEL_CHEAP },
 
     /* -O2 and -Os optimizations.  */

gcc/params.def

@@ -1314,6 +1314,15 @@ DEFPARAM (PARAM_FSM_SCALE_PATH_BLOCKS,
 	  "Scale factor to apply to the number of blocks in a threading path when comparing to the number of (scaled) statements.",
 	  3, 1, 10)
 
+/* Temporary aid to disable the range based threader while
+   benchmarking.  This is needed because early threading (which runs
+   before [er]vrp) will modify the IL and make it harder to compare
+   [er]vrp speeds.  */
+DEFPARAM (PARAM_FSM_RANGE_BASED_THREADING,
+	  "fsm-range-based-threading",
+	  "Set to 1 if range based threading is enabled in backwards threader.",
+	  1, 0, 1)
+
 DEFPARAM (PARAM_MAX_FSM_THREAD_PATH_INSNS,
 	  "max-fsm-thread-path-insns",
 	  "Maximum number of instructions to copy when duplicating blocks on a finite state automaton jump thread path.",

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);

gcc/range-op.h

@@ -0,0 +1,92 @@
+/* Header file for range operator class.
+   Copyright (C) 2017-2019 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@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/>.  */
+
+#ifndef GCC_RANGE_OP_H
+#define GCC_RANGE_OP_H
+
+#if USE_IRANGE
+#define value_range_base irange
+#define value_range_storage irange_storage
+#endif
+
+// This class is implemented for each kind of operator that is supported by
+// the range generator.  It serves dual purposes.
+//
+// 1 - Generates range information for the specific operation between
+//     the 4 possible combinations of integers and ranges.
+//     This provides the ability to fold ranges for an expression.
+//
+// 2 - Performs range algebra on the expression such that a range can be
+//     adjusted in terms of one of the operands:
+//       def = op1 + op2
+//     Given a range for def, we can possibly adjust the range so its in
+//     terms of either operand.
+//     op1_adjust (def_range, op2) will adjust the range in place so its
+//     in terms of op1.  since op1 = def - op2, it will subtract op2 from
+//     each element of the range.
+//
+// 3 - Creates a range for an operand based on whether the result is 0 or
+//     non-zero.  This is mostly for logical true false, but can serve other
+//     purposes.
+//       ie   0 = op1 - op2 implies op2 has the same range as op1.
+
+
+class range_operator
+{
+public:
+  // Set a range based on this operation between 2 operands.
+  // TYPE is the expected type of the range.
+  virtual value_range_base fold_range (tree type,
+				       const value_range_base &lh,
+				       const value_range_base &rh) const;
+
+  // Set the range for op? in the general case. LHS is the range for
+  // the LHS of the expression, OP[12]is the range for the other
+  // TYPE is the expected type of the range.
+  // operand, and the result is returned in R.
+  // Return TRUE if the operation is performed and a valid range is available.
+  // ie   [LHS] = ??? + OP2
+  // is re-formed as  R = [LHS] - OP2.
+  virtual bool op1_range (value_range_base &r, tree type,
+			  const value_range_base &lhs,
+			  const value_range_base &op2) const;
+  virtual bool op2_range (value_range_base &r, tree type,
+			  const value_range_base &lhs,
+			  const value_range_base &op1) const;
+protected:
+  // Perform this operation on 2 sub ranges, return the result as a
+  // range of TYPE.
+  virtual value_range_base wi_fold (tree type,
+				    const wide_int &lh_lb,
+				    const wide_int &lh_ub,
+				    const wide_int &rh_lb,
+				    const wide_int &rh_ub) const;
+};
+
+extern range_operator *range_op_handler(enum tree_code code, tree type);
+
+extern void range_cast (value_range_base &, tree type);
+
+#if USE_IRANGE
+#undef value_range_base
+#undef value_range_storage
+#endif
+
+#endif // GCC_RANGE_OP_H

gcc/range.cc

@@ -0,0 +1,896 @@
+/* High resolution range class.
+   Copyright (C) 2017-2019 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 "gimple-pretty-print.h"
+#include "fold-const.h"
+#include "ssa.h"
+#include "range.h"
+#include "wide-int-range.h"
+
+// Common code between the alternate irange implementations.
+
+// Return TRUE if two types are compatible for range operations.
+
+static bool
+range_compatible_p (tree t1, tree t2)
+{
+  if (POINTER_TYPE_P (t1) && POINTER_TYPE_P (t2))
+    return true;
+
+  return types_compatible_p (t1, t2);
+}
+
+bool
+irange::operator== (const irange &r) const
+{
+  // Special case this because a freshly initialized range may be
+  // typeless.
+  if (undefined_p ())
+    return r.undefined_p ();
+
+  if (num_pairs () != r.num_pairs ()
+      || !range_compatible_p (type (), r.type ()))
+    return false;
+
+  for (unsigned p = 0; p < num_pairs (); p++)
+    if (wi::ne_p (lower_bound (p), r.lower_bound (p))
+	|| wi::ne_p (upper_bound (p), r.upper_bound (p)))
+      return false;
+
+  return true;
+}
+
+bool
+irange::operator!= (const irange &r) const
+{
+  return !(*this == r);
+}
+
+irange
+range_intersect (const irange &r1, const irange &r2)
+{
+  irange tmp (r1);
+  tmp.intersect (r2);
+  return tmp;
+}
+
+irange
+range_invert (const irange &r1)
+{
+  irange tmp (r1);
+  tmp.invert ();
+  return tmp;
+}
+
+irange
+range_union (const irange &r1, const irange &r2)
+{
+  irange tmp (r1);
+  tmp.union_ (r2);
+  return tmp;
+}
+
+irange
+range_zero (tree type)
+{
+  return irange (build_zero_cst (type), build_zero_cst (type));
+}
+
+irange
+range_nonzero (tree type)
+{
+  return irange (VR_ANTI_RANGE,
+		 build_zero_cst (type), build_zero_cst (type));
+}
+
+irange
+range_positives (tree type)
+{
+  unsigned prec = TYPE_PRECISION (type);
+  signop sign = TYPE_SIGN (type);
+  return irange (type, wi::zero (prec), wi::max_value (prec, sign));
+}
+
+irange
+range_negatives (tree type)
+{
+  unsigned prec = TYPE_PRECISION (type);
+  signop sign = TYPE_SIGN (type);
+  irange r;
+  if (sign == UNSIGNED)
+    r.set_undefined ();
+  else
+    r = irange (type, wi::min_value (prec, sign), wi::minus_one (prec));
+  return r;
+}
+
+#if USE_IRANGE
+// Standalone irange implementation.
+
+// Subtract 1 from X and set OVERFLOW if the operation overflows.
+
+static wide_int inline
+subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow)
+{
+  // A signed 1-bit bit-field, has a range of [-1,0] so subtracting +1
+  // overflows, since +1 is unrepresentable.  This is why we have an
+  // addition of -1 here.
+  if (TYPE_SIGN (type) == SIGNED)
+    return wi::add (x, -1 , SIGNED, &overflow);
+  else
+    return wi::sub (x, 1, UNSIGNED, &overflow);
+}
+
+// Set range from wide ints.
+
+void
+irange::init (tree type, const wide_int &lbound, const wide_int &ubound,
+	      value_range_kind rt)
+{
+  if (rt == VR_UNDEFINED)
+    {
+      set_undefined ();
+      return;
+    }
+  if (rt == VR_VARYING)
+    {
+      set_varying (type);
+      return;
+    }
+  gcc_checking_assert (irange::supports_type_p (type));
+  gcc_checking_assert (TYPE_PRECISION (type) == lbound.get_precision ());
+  gcc_checking_assert (lbound.get_precision () == ubound.get_precision ());
+  m_type = type;
+  gcc_checking_assert (wi::le_p (lbound, ubound, TYPE_SIGN (type)));
+  if (rt == VR_ANTI_RANGE)
+    {
+      // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
+      wi::overflow_type ovf;
+      m_nitems = 0;
+      wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+      wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+
+      // If we will overflow, don't bother.  This will handle unsigned
+      // underflow which doesn't set the overflow bit.
+      if (lbound != min)
+	{
+	  m_bounds[m_nitems++] = min;
+	  m_bounds[m_nitems++] = subtract_one (lbound, type, ovf);
+	  if (ovf)
+	    m_nitems = 0;
+	}
+      // If we will overflow, don't bother.  This will handle unsigned
+      // overflow which doesn't set the overflow bit.
+      if (ubound != max)
+	{
+	  m_bounds[m_nitems++] = wi::add (ubound, 1, TYPE_SIGN (type), &ovf);
+	  if (ovf)
+	    m_nitems--;
+	  else
+	    m_bounds[m_nitems++] = max;
+	}
+      // If we get here with N==0, it means we tried to calculate the
+      // inverse of [-MIN, +MAX] which is actually the empty set, and
+      // N==0 maps nicely to the empty set.
+    }
+  else
+    {
+      m_bounds[0] = lbound;
+      m_bounds[1] = ubound;
+      m_nitems = 2;
+    }
+}
+
+irange::irange (tree type)
+{
+  set_varying (type);
+}
+
+irange::irange (value_range_kind rt, tree type,
+		const wide_int &lbound, const wide_int &ubound)
+{
+  init (type, lbound, ubound, rt);
+}
+
+irange::irange (tree type, const wide_int &lbound, const wide_int &ubound)
+{
+  init (type, lbound, ubound, VR_RANGE);
+}
+
+irange::irange (value_range_kind rt, tree lbound, tree ubound)
+{
+  gcc_checking_assert (rt == VR_RANGE || rt == VR_ANTI_RANGE);
+  tree type = TREE_TYPE (lbound);
+  init (type, wi::to_wide (lbound), wi::to_wide (ubound), rt);
+}
+
+irange::irange (tree lbound, tree ubound)
+{
+  tree type = TREE_TYPE (lbound);
+  init (type, wi::to_wide (lbound), wi::to_wide (ubound), VR_RANGE);
+}
+
+// Mark pair [i, j] to empty.  This is done by building a non-sensical pair.
+
+void
+irange_storage::set_empty_pair (unsigned i, unsigned j, tree type)
+{
+  unsigned precision = trailing_bounds[0].get_precision ();
+  if (precision == 1 && TYPE_SIGN (type) == SIGNED)
+    {
+      // For stupid ass signed 1-bit types, we can't use [1, 0] as a
+      // nonsensical pair, since it maps to [-1, 0] which is valid.
+      // In this case, use [0, 1] which is invalid in this brain-dead world.
+      trailing_bounds[i] = wi::zero (precision);
+      trailing_bounds[j] = wi::one (precision);
+    }
+  else
+    {
+      // For almost all types, we mark empty ranges with a nonsensical [1, 0] range.
+      trailing_bounds[i] = wi::one (precision);
+      trailing_bounds[j] = wi::zero (precision);
+    }
+}
+
+irange::irange (tree type, const irange_storage *storage)
+{
+  m_type = type;
+  m_nitems = 0;
+  unsigned i = 0;
+  unsigned precision = wi::get_precision (storage->trailing_bounds[0]);
+  gcc_checking_assert (precision == TYPE_PRECISION (type));
+  while (i < m_max_pairs * 2)
+    {
+      if (storage->empty_pair_p (i, i + 1, type))
+	break;
+      m_bounds[i] = storage->trailing_bounds[i];
+      m_bounds[i + 1] = storage->trailing_bounds[i + 1];
+      i += 2;
+    }
+  m_nitems = i;
+}
+
+// Set range from the full domain of TYPE.
+
+void
+irange::set_varying (tree type)
+{
+  wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+  wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+  init (type, min, max);
+}
+
+bool
+irange::valid_p () const
+{
+  if (m_type == NULL
+      || m_nitems % 2
+      || m_nitems > m_max_pairs * 2)
+    return false;
+
+  if (undefined_p ())
+    return true;
+
+  // Check that the bounds are in the right order.
+  // So for [a,b][c,d][e,f] we must have: a <= b < c <= d < e <= f.
+  if (wi::gt_p (lower_bound (0), upper_bound (0), TYPE_SIGN (m_type)))
+    return false;
+  for (unsigned p = 1; p < num_pairs (); ++p)
+    {
+      if (wi::le_p (lower_bound (p), upper_bound (p - 1), TYPE_SIGN (m_type)))
+	return false;
+      if (wi::gt_p (lower_bound (p), upper_bound (p), TYPE_SIGN (m_type)))
+	return false;
+    }
+  return true;
+}
+
+void
+irange::check () const
+{
+  gcc_assert (valid_p ());
+}
+
+// Return TRUE if the current range contains wide-int ELEMENT.
+
+bool
+irange::contains_p (const wide_int &element) const
+{
+  for (unsigned p = 0; p < num_pairs (); ++p)
+    if (wi::ge_p (element, lower_bound (p), TYPE_SIGN (m_type))
+	&& wi::le_p (element, upper_bound (p), TYPE_SIGN (m_type)))
+      return true;
+  return false;
+}
+
+// Return TRUE if the current range contains tree ELEMENT.
+
+bool
+irange::contains_p (tree element) const
+{
+  return contains_p (wi::to_wide (element));
+}
+
+// Remove PAIR.
+
+void
+irange::remove_pair (unsigned pair)
+{
+  unsigned i = pair * 2;
+  unsigned j = i + 1;
+  gcc_checking_assert (i < m_nitems && i < j);
+  unsigned dst = i;
+  unsigned ndeleted = j - i + 1;
+  for (++j; j < m_nitems; ++j)
+    m_bounds[dst++] = m_bounds[j];
+  m_nitems -= ndeleted;
+}
+
+// Canonicalize the current range.
+
+void
+irange::canonicalize ()
+{
+  if (undefined_p ())
+    return;
+
+  // Fix any out of order ranges: [10,20][-5,5] into [-5,5][10,20].
+  signop sign = TYPE_SIGN (m_type);
+  for (unsigned p = 0; p < num_pairs (); ++p)
+    for (unsigned q = p; q < num_pairs (); ++q)
+      if (wi::gt_p (lower_bound (p), lower_bound (q), sign))
+	{
+	  wide_int t1 = lower_bound (p);
+	  wide_int t2 = upper_bound (p);
+	  set_lower_bound (p, lower_bound (q));
+	  set_upper_bound (p, upper_bound (q));
+	  set_lower_bound (q, t1);
+	  set_upper_bound (q, t2);
+	}
+  // Merge sub-ranges when appropriate.
+  for (unsigned p = 0; p < num_pairs () - 1; )
+    {
+      // Merge edges that touch:
+      // [9,10][11,20] => [9,20]
+      // [9,10][10,20] => [9,20].
+      wi::overflow_type ovf;
+      if (upper_bound (p) == lower_bound (p + 1)
+	  || (wi::add (upper_bound (p), 1, sign, &ovf) == lower_bound (p + 1)
+	      && !ovf))
+	{
+	  set_upper_bound (p, upper_bound (p + 1));
+	  remove_pair (p + 1);
+	}
+      // Merge pairs that bleed into each other:
+      // [10,20][11,18] => [10,20]
+      // [10,20][15,30] => [10,30]
+      else if (wi::le_p (lower_bound (p), lower_bound (p + 1), sign)
+	       && wi::ge_p (upper_bound (p), lower_bound (p + 1), sign))
+	{
+	  set_upper_bound (p, wi::max (upper_bound (p), upper_bound (p + 1), sign));
+	  remove_pair (p + 1);
+	}
+      else
+	++p;
+    }
+  if (flag_checking)
+    check ();
+}
+
+// THIS = THIS U R
+
+void
+irange::union_ (const irange &r)
+{
+  if (undefined_p ())
+    {
+      *this = r;
+      return;
+    }
+  else if (r.undefined_p ())
+    return;
+
+  gcc_checking_assert (range_compatible_p (m_type, r.m_type));
+
+  // Do not worry about merging and such by reserving twice as many
+  // pairs as needed, and then simply sort the 2 ranges into this
+  // intermediate form.
+  //
+  // The intermediate result will have the property that the beginning
+  // of each range is <= the beginning of the next range.  There may
+  // be overlapping ranges at this point.  I.e. this would be valid
+  // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
+  // contraint : -20 < -10 < 0 < 40 When the range is rebuilt into r,
+  // the merge is performed.
+  //
+  // [Xi,Yi]..[Xn,Yn]  U  [Xj,Yj]..[Xm,Ym]   -->  [Xk,Yk]..[Xp,Yp]
+  signop sign = TYPE_SIGN (m_type);
+  wide_int res[m_max_pairs * 4];
+  wide_int u1 ;
+  wi::overflow_type ovf;
+  unsigned i = 0, j = 0, k = 0;
+
+  while (i < m_nitems && j < r.m_nitems)
+    {
+      // lower of Xi and Xj is the lowest point.
+      if (wi::le_p (m_bounds[i], r.m_bounds[j], sign))
+        {
+	  res[k++] = m_bounds[i];
+	  res[k++] = m_bounds[i + 1];
+	  i += 2;
+	}
+      else
+        {
+	  res[k++] = r.m_bounds[j];
+	  res[k++] = r.m_bounds[j + 1];
+	  j += 2;
+	}
+    }
+  for ( ; i < m_nitems; i += 2)
+    {
+      res[k++] = m_bounds[i];
+      res[k++] = m_bounds[i + 1];
+    }
+  for ( ; j < r.m_nitems; j += 2)
+    {
+      res[k++] = r.m_bounds[j];
+      res[k++] = r.m_bounds[j + 1];
+    }
+
+  // Now normalize the vector removing any overlaps.
+  i = 2;
+  int prec = TYPE_PRECISION (m_type);
+  wide_int max_val = wi::max_value (prec, sign);
+  for (j = 2; j < k ; j += 2)
+    {
+      if (res[i - 1] == max_val)
+        break;
+      u1 = wi::add (res[i - 1], 1, sign, &ovf);
+
+      // Overflow indicates we are at MAX already.
+      // A wide int bug requires the previous max_val check
+      // trigger: gcc.c-torture/compile/pr80443.c  with -O3
+      if (ovf)
+        break;
+
+      // Current upper+1 is >= lower bound next pair, then we merge ranges.
+      if (wi::ge_p (u1, res[j], sign))
+        {
+	  // New upper bounds is greater of current or the next one.
+	  if (wi::gt_p (res[j + 1], res [i - 1], sign))
+	    res [i - 1] = res[j + 1];
+	}
+      else
+        {
+	  // This is a new distinct range, but no point in copying it
+	  // if it is already in the right place.
+	  if (i != j)
+	    {
+	      res[i++] = res[j];
+	      res[i++] = res[j + 1];
+	    }
+	  else
+	    i += 2;
+
+	}
+    }
+
+  // At this point, the vector should have i ranges, none
+  // overlapping. Now it simply needs to be copied, and if there are
+  // too many ranges, merge some.  We wont do any analysis as to what
+  // the "best" merges are, simply combine the final ranges into one.
+  if (i > m_max_pairs * 2)
+    {
+      res[m_max_pairs * 2 - 1] = res[i - 1];
+      i = m_max_pairs * 2;
+    }
+
+  for (j = 0; j < i ; j++)
+    m_bounds[j] = res [j];
+  m_nitems = i;
+
+  if (flag_checking)
+    check ();
+}
+
+// THIS = THIS ^ [X,Y].
+
+void
+irange::intersect (const wide_int &x, const wide_int &y)
+{
+  if (undefined_p ())
+    return;
+
+  unsigned pos = 0;
+  for (unsigned i = 0; i < m_nitems; i += 2)
+    {
+      signop sign = TYPE_SIGN (m_type);
+      wide_int newlo = wi::max (m_bounds[i], x, sign);
+      wide_int newhi = wi::min (m_bounds[i + 1], y, sign);
+      if (wi::gt_p (newlo, newhi, sign))
+	{
+	  // If the new sub-range doesn't make sense, it's an
+	  // impossible range and must be kept out of the result.
+	}
+      else
+	{
+	  m_bounds[pos++] = newlo;
+	  m_bounds[pos++] = newhi;
+	}
+    }
+  m_nitems = pos;
+  if (flag_checking)
+    check ();
+}
+
+// THIS = THIS ^ R.
+
+void
+irange::intersect (const irange &r)
+{
+  irange orig_range (*this);
+
+  // Intersection with an empty range is an empty range.
+  if (orig_range.undefined_p () || r.undefined_p ())
+    {
+      set_undefined ();
+      return;
+    }
+
+  gcc_checking_assert (range_compatible_p (m_type, r.m_type));
+
+  // The general algorithm is as follows.
+  //
+  // Intersect each sub-range of R with all of ORIG_RANGE one at a time, and
+  // join/union the results of these intersections together.  I.e:
+  //
+  //   [10,20][30,40][50,60] ^ [15,25][38,51][55,70]
+  //
+  // Step 1: [10,20][30,40][50,60] ^ [15,25] => [15,20]
+  // Step 2: [10,20][30,40][50,60] ^ [38,51] => [38,40]
+  // Step 3: [10,20][30,40][50,60] ^ [55,70] => [55,60]
+  // Final:  [15,20] U [38,40] U [55,60] => [15,20][38,40][55,60]
+  set_undefined ();
+  for (unsigned i = 0; i < r.m_nitems; i += 2)
+    {
+      irange tmp (orig_range);
+      tmp.intersect (r.m_bounds[i], r.m_bounds[i + 1]);
+      union_ (tmp);
+    }
+  // There is no check here because the calls to union_ above would
+  // have verified sanity.
+}
+
+// Set THIS to the inverse of its range.
+
+void
+irange::invert ()
+{
+  if (undefined_p ())
+    return;
+
+  // We always need one more set of bounds to represent an inverse, so
+  // if we're at the limit, we can't properly represent things.
+  //
+  // For instance, to represent the inverse of a 2 sub-range set
+  // [5, 10][20, 30], we would need a 3 sub-range set
+  // [-MIN, 4][11, 19][31, MAX].
+  //
+  // In this case, return the most conservative thing.
+  //
+  // However, if any of the extremes of the range are -MIN/+MAX, we
+  // know we will not need an extra bound.  For example:
+  //
+  // 	INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
+  // 	INVERT([-MIN,20][30,MAX]) => [21,29]
+  wide_int min = wi::min_value (TYPE_PRECISION (m_type), TYPE_SIGN (m_type));
+  wide_int max = wi::max_value (TYPE_PRECISION (m_type), TYPE_SIGN (m_type));
+  if (m_nitems == m_max_pairs * 2
+      && m_bounds[0] != min
+      && m_bounds[m_nitems] != max)
+    {
+      m_bounds[1] = max;
+      m_nitems = 2;
+      return;
+    }
+
+  // The algorithm is as follows.  To calculate INVERT ([a,b][c,d]), we
+  // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
+  //
+  // If there is an over/underflow in the calculation for any
+  // sub-range, we eliminate that subrange.  This allows us to easily
+  // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX].  And since
+  // we eliminate the underflow, only [6, MAX] remains.
+
+  unsigned i = 0;
+  wi::overflow_type ovf;
+
+  // Construct leftmost range.
+  irange orig_range (*this);
+  m_nitems = 0;
+  // If this is going to underflow on the MINUS 1, don't even bother
+  // checking.  This also handles subtracting one from an unsigned 0,
+  // which doesn't set the underflow bit.
+  if (min != orig_range.m_bounds[i])
+    {
+      m_bounds[m_nitems++] = min;
+      m_bounds[m_nitems++] = subtract_one (orig_range.m_bounds[i],
+					   m_type, ovf);
+      if (ovf)
+	m_nitems = 0;
+    }
+  i++;
+  // Construct middle ranges if applicable.
+  if (orig_range.m_nitems > 2)
+    {
+      unsigned j = i;
+      for (; j < (unsigned) (orig_range.m_nitems - 2); j += 2)
+	{
+	  // The middle ranges cannot have MAX/MIN, so there's no need
+	  // to check for unsigned overflow on the +1 and -1 here.
+	  m_bounds[m_nitems++]
+	    = wi::add (orig_range.m_bounds[j], 1, TYPE_SIGN (m_type), &ovf);
+	  m_bounds[m_nitems++]
+	    = subtract_one (orig_range.m_bounds[j + 1], m_type, ovf);
+	  if (ovf)
+	    m_nitems -= 2;
+	}
+      i = j;
+    }
+  // Construct rightmost range.
+  //
+  // However, if this will overflow on the PLUS 1, don't even bother.
+  // This also handles adding one to an unsigned MAX, which doesn't
+  // set the overflow bit.
+  if (max != orig_range.m_bounds[i])
+    {
+      m_bounds[m_nitems++]
+	= wi::add (orig_range.m_bounds[i], 1, TYPE_SIGN (m_type), &ovf);
+      m_bounds[m_nitems++] = max;
+      if (ovf)
+	m_nitems -= 2;
+    }
+
+  if (flag_checking)
+    check ();
+}
+
+// Dump the current range onto BUFFER.
+
+void
+irange::dump (pretty_printer *buffer) const
+{
+  if (undefined_p ())
+    {
+      pp_string (buffer, "[]");
+      pp_flush (buffer);
+      return;
+    }
+
+  wide_int min = wi::min_value (TYPE_PRECISION (m_type), TYPE_SIGN (m_type));
+  wide_int max = wi::max_value (TYPE_PRECISION (m_type), TYPE_SIGN (m_type));
+  if (POINTER_TYPE_P (m_type) && nonzero_p ())
+    pp_string (buffer, "[ non-zero pointer ]");
+  else
+    for (unsigned i = 0; i < m_nitems; ++i)
+      {
+	if (i % 2 == 0)
+	  pp_character (buffer, '[');
+
+	// Wide ints may be sign extended to the full extent of the
+	// underlying HWI storage, even if the precision we care about
+	// is smaller.  Chop off the excess bits for prettier output.
+	signop sign = TYPE_UNSIGNED (m_type) ? UNSIGNED : SIGNED;
+	widest_int val = widest_int::from (m_bounds[i], sign);
+	val &= wi::mask<widest_int> (m_bounds[i].get_precision (), false);
+
+	if (i == 0
+	    && INTEGRAL_TYPE_P (m_type)
+	    && !TYPE_UNSIGNED (m_type)
+	    && m_bounds[i] == min
+	    && TYPE_PRECISION (m_type) != 1)
+	  pp_string (buffer, "-INF");
+	else if (i + 1 == m_nitems
+	    && INTEGRAL_TYPE_P (m_type)
+	    && !TYPE_UNSIGNED (m_type)
+	    && m_bounds[i] == max
+	    && TYPE_PRECISION (m_type) != 1)
+	  pp_string (buffer, "+INF");
+	else
+	  {
+	    if (val > 0xffff)
+	      print_hex (val, pp_buffer (buffer)->digit_buffer);
+	    else
+	      print_dec (m_bounds[i], pp_buffer (buffer)->digit_buffer, sign);
+	    pp_string (buffer, pp_buffer (buffer)->digit_buffer);
+	  }
+	if (i % 2 == 0)
+	  pp_string (buffer, ", ");
+	else
+	  pp_character (buffer, ']');
+      }
+
+  pp_character (buffer, ' ');
+  dump_generic_node (buffer, m_type, 0, TDF_NONE, false);
+  pp_flush (buffer);
+}
+
+// Dump the current range onto FILE F.
+
+void
+irange::dump (FILE *f) const
+{
+  pretty_printer buffer;
+  buffer.buffer->stream = f;
+  dump (&buffer);
+}
+
+// Like above but dump to STDERR.
+//
+// You'd think we could have a default parameter for dump(FILE),
+// but gdb currently doesn't do default parameters gracefully-- or at
+// all, and since this is a function we need to be callable from the
+// debugger...
+
+void
+irange::dump () const
+{
+  dump (stderr);
+}
+
+// Initialize the current irange_storage to the irange in IR.
+
+void
+irange_storage::set (const irange &ir, tree type)
+{
+  if (type)
+    gcc_checking_assert (ir.undefined_p ()
+			 || types_compatible_p (type, ir.type ()));
+  else
+    type = ir.type ();
+  unsigned precision = TYPE_PRECISION (type);
+  trailing_bounds.set_precision (precision);
+  unsigned i;
+  for (i = 0; i < ir.num_pairs () * 2; ++i)
+    trailing_bounds[i] = ir.m_bounds[i];
+
+  // Clear the remaining empty ranges.
+  for (; i < irange::m_max_pairs * 2; i += 2)
+    set_empty_pair (i, i + 1, type);
+}
+
+// Update a previously initialized irange_storage to NEW_RANGE, iff the
+// precision of the present range is the same as the precision of
+// the new range.  Return TRUE if update was successful.
+
+bool
+irange_storage::update (const irange &new_range, tree type)
+{
+  if (trailing_bounds.get_precision () == TYPE_PRECISION (type))
+    {
+      set (new_range, type);
+      return true;
+    }
+  return false;
+}
+
+// Return TRUE if range contains exactly one element and set RESULT to it.
+
+bool
+irange::singleton_p (tree *result) const
+{
+  if (num_pairs () == 1 && lower_bound (0) == upper_bound (0))
+    {
+      if (result)
+	*result = wide_int_to_tree (type (), lower_bound ());
+      return true;
+    }
+  return false;
+}
+
+// Convert irange to a value_range.
+
+value_range_base
+irange_to_value_range (const irange &r)
+{
+  value_range_base vr;
+  if (r.varying_p ())
+    {
+      vr.set_varying (r.type ());
+      return vr;
+    }
+  if (r.undefined_p ())
+    {
+      vr.set_undefined ();
+      return vr;
+    }
+  tree type = r.type ();
+  unsigned int precision = TYPE_PRECISION (type);
+  // Represent non-zero correctly.
+  if (TYPE_UNSIGNED (type)
+      && r.num_pairs () == 1
+      && r.lower_bound () == wi::uhwi (1, precision)
+      && r.upper_bound () == wi::max_value (precision, UNSIGNED)
+      // Do not get confused by booleans.
+      && TYPE_PRECISION (type) != 1)
+    vr = value_range (VR_ANTI_RANGE,
+		      build_int_cst (type, 0), build_int_cst (type, 0));
+  // Represent anti-ranges.
+  else if ((r.num_pairs () == 2
+	    || r.num_pairs () == 3)
+	   // Do not get confused by booleans.
+	   && TYPE_PRECISION (type) != 1
+	   && r.lower_bound () == wi::min_value (precision, TYPE_SIGN (type))
+	   && r.upper_bound () == wi::max_value (precision, TYPE_SIGN (type)))
+    {
+      irange tmp = r;
+      if (r.num_pairs () == 3)
+	{
+	  // Hack to make up for the fact that we can compute finer
+	  // grained ranges that VRP can only approximate with an
+	  // anti-range.  Attempt to reconstruct sub-ranges of the form:
+	  //
+	  //	[0, 94][96, 127][0xff80, 0xffff] => ~[95,95]
+	  //	[0, 1][3, 0x7fffffff][0xff..80000000, 0xff..ff] => ~[2, 2].
+	  //
+	  // Merge the last two bounds.
+	  tmp = irange (type, r.lower_bound (0), r.upper_bound (0));
+	  tmp.union_ (irange (type, r.lower_bound (1), r.upper_bound ()));
+	}
+      tmp = range_invert (tmp);
+      vr = value_range (VR_ANTI_RANGE,
+			wide_int_to_tree (type, tmp.lower_bound ()),
+			wide_int_to_tree (type, tmp.upper_bound ()));
+    }
+  else
+    vr = value_range (VR_RANGE,
+		      wide_int_to_tree (type, r.lower_bound ()),
+		      wide_int_to_tree (type, r.upper_bound ()));
+  return vr;
+}
+
+// Convert a value_range into an irange.
+
+static irange
+value_range_to_irange (const value_range_base &vr)
+{
+  if (vr.varying_p ())
+    return irange (vr.type ());
+  if (vr.undefined_p ())
+    {
+      irange r;
+      r.set_undefined ();
+      return r;
+    }
+  return irange (vr.kind (), vr.min (), vr.max ());
+}
+
+irange::irange (const value_range_base &vr)
+{
+  *this = value_range_to_irange (vr);
+}
+
+#endif // USE_IRANGE

gcc/range.h

@@ -0,0 +1,366 @@
+/* Header file for high resolution range class. -*- C++ -*-
+   Copyright (C) 2017-2019 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/>.  */
+
+#ifndef GCC_RANGE_H
+#define GCC_RANGE_H
+
+// Set to one if irange is a standalone class, or zero if irange is
+// just value_range_base underneath.
+#define USE_IRANGE 1
+
+class value_range_base;
+
+#if USE_IRANGE
+// This is the standalone irange implementation.
+
+class irange_storage;
+
+// This is a class for working with ranges, currently integer ones.
+// With it you can specify a range of [5,10] or even ranges including
+// multi-part ranges [-10,5][30,40][50,60].
+//
+// Inverse ranges are represented as an actual range.  For instance,
+// the inverse of 0 is [-MIN,-1][1,+MAX] for a signed integer.
+//
+// Methods are provided for intersecting and uniting ranges, as well
+// as converting between them.  In performing any of these operations,
+// when no efficient way can be computed, we may default to a more
+// conservative range.
+//
+// For example, the inverse of [5,10][15,20][30,40] is actually
+// [-MIN,4][11,14][21,29][41,+MAX].  If this cannot be efficiently or
+// quickly computed, we may opt to represent the inverse as
+// [-MIN,4][41,+MAX] which is an equivalent conservative
+// representation.
+//
+// This class is not meant to live in long term storage.
+// Consequently, there are no GTY markers.  For long term storage, use
+// the irange_storage class described later.
+
+class irange
+{
+  friend class irange_storage;
+  friend void range_tests ();
+
+ public:
+  irange ();
+  irange (tree type);
+  irange (value_range_kind, tree type, const wide_int &, const wide_int &);
+  irange (tree type, const wide_int &, const wide_int &);
+  irange (value_range_kind, tree, tree);
+  irange (tree, tree);
+  irange (tree type, const irange_storage *);
+  irange (const value_range_base &);
+
+  static bool supports_type_p (tree type);
+  static bool supports_ssa_p (tree ssa);
+  static bool supports_p (tree expr);
+
+  void set_varying (tree);
+  void set_undefined ();
+
+  unsigned num_pairs () const;
+  wide_int lower_bound (unsigned pair = 0) const;
+  wide_int upper_bound () const;
+  wide_int upper_bound (unsigned pair) const;
+
+  tree type () const;
+
+  bool varying_p () const;
+  bool undefined_p () const;
+  bool zero_p () const;
+  bool nonzero_p () const;
+  // These two take a tree instead of a wide_int, for API
+  // compatibility with value_range.
+  bool singleton_p (tree * = NULL) const;
+  bool contains_p (tree) const;
+
+  bool operator== (const irange &r) const;
+  bool operator!= (const irange &r) const;
+
+  void union_ (const irange &r);
+  void intersect (const irange &r);
+  void invert ();
+
+  void dump () const;
+  void dump (FILE *) const;
+
+private:
+  void init (tree type, const wide_int &, const wide_int &,
+	     value_range_kind = VR_RANGE);
+  void canonicalize ();
+  void set_lower_bound (unsigned pair, const wide_int &);
+  void set_upper_bound (unsigned pair, const wide_int &);
+  void remove_pair (unsigned pair);
+  void intersect (const wide_int &x, const wide_int &y);
+  bool contains_p (const wide_int &element) const;
+  void dump (pretty_printer *pp) const;
+  bool valid_p () const;
+  void check () const;
+
+  tree m_type;
+  unsigned char m_nitems;
+  static const unsigned int m_max_pairs = 3;
+  wide_int m_bounds[m_max_pairs * 2];
+}; // class irange
+
+inline
+irange::irange () : m_type (NULL), m_nitems (0)
+{
+}
+
+inline wide_int
+irange::lower_bound (unsigned pair) const
+{
+  return m_bounds[pair * 2];
+}
+
+inline wide_int
+irange::upper_bound () const
+{
+  return m_bounds[m_nitems - 1];
+}
+
+inline wide_int
+irange::upper_bound (unsigned pair) const
+{
+  return m_bounds[pair * 2 + 1];
+}
+
+inline void
+irange::set_lower_bound (unsigned pair, const wide_int &i)
+{
+  m_bounds[pair * 2 ] = i;
+}
+
+inline void
+irange::set_upper_bound (unsigned pair, const wide_int &i)
+{
+  m_bounds[pair * 2 + 1] = i;
+}
+
+inline unsigned
+irange::num_pairs () const
+{
+  return m_nitems / 2;
+}
+
+inline tree
+irange::type () const
+{
+  gcc_checking_assert (!undefined_p ());
+  return m_type;
+}
+
+inline void
+irange::set_undefined ()
+{
+  m_type = NULL;
+  m_nitems = 0;
+}
+
+inline bool
+irange::undefined_p () const
+{
+  return !m_nitems;
+}
+
+inline bool
+irange::zero_p () const
+{
+  if (m_nitems != 2)
+    return false;
+  wide_int z = wi::zero (TYPE_PRECISION (m_type));
+  return (m_nitems == 2 && m_bounds[0] == z && m_bounds[1] == z);
+}
+
+inline bool
+irange::nonzero_p () const
+{
+  if (undefined_p ())
+    return false;
+  unsigned prec = TYPE_PRECISION (m_type);
+  return *this == irange (VR_ANTI_RANGE, m_type,
+			  wi::zero (prec), wi::zero (prec));
+}
+
+// Return true if this range is the full range for its type.
+
+inline bool
+irange::varying_p () const
+{
+  return (m_nitems == 2 &&
+	  m_bounds[0] == wi::min_value (TYPE_PRECISION (m_type),
+					TYPE_SIGN (m_type)) &&
+	  m_bounds[1] == wi::max_value (TYPE_PRECISION (m_type),
+					TYPE_SIGN (m_type)));
+}
+
+// An irange is memory inefficient, so this class is used to store
+// them in memory.  It is a variable length structure that contains
+// the sub-range pairs as well as the non-zero bitmask.  The number of
+// entries are m_max_pairs * 2 + 1 (to accomodate the non-zero bits).
+//
+// To store an irange class X into an irange_storage use:
+//
+// 	irange X = ...;
+// 	irange_storage *stow = irange_storage::alloc (X, range_type);
+//
+// To convert it back into an irange use:
+//
+// 	tree type = ...;
+// 	irange X (type, stow);
+//
+// To get at the nonzero bits:
+//
+// 	irange_storage *stow = ...;
+// 	stow->set_nonzero_bits();
+// 	stow->get_nonzero_bits();
+
+class GTY((variable_size)) irange_storage
+{
+  friend class irange;
+
+ public:
+  static irange_storage *alloc (const irange &, tree type);
+  bool update (const irange &, tree type);
+
+ private:
+  static size_t size (unsigned precision);
+  void set (const irange &, tree type);
+  bool empty_pair_p (unsigned, unsigned, tree) const;
+  void set_empty_pair (unsigned, unsigned, tree);
+  void set_nonzero_bits (const wide_int &);
+  wide_int get_nonzero_bits ();
+
+  // The last wide_int in this field is a mask representing which bits in
+  // an integer are known to be non-zero.
+  trailing_wide_ints<irange::m_max_pairs * 2 + 1> trailing_bounds;
+};
+
+// Return the nonzero bits in the range.
+
+inline wide_int
+irange_storage::get_nonzero_bits ()
+{
+  return trailing_bounds[irange::m_max_pairs * 2];
+}
+
+// Set the nonzero bit mask to WI.
+inline void
+irange_storage::set_nonzero_bits (const wide_int &wi)
+{
+  trailing_bounds[irange::m_max_pairs * 2] = wi;
+}
+
+// Returns the size of an irange_storage with PRECISION.
+
+inline size_t
+irange_storage::size (unsigned precision)
+{
+  return sizeof (irange_storage)
+    /* There is a +1 for the non-zero bits field.  */
+    + trailing_wide_ints<irange::m_max_pairs * 2 + 1>::extra_size (precision);
+}
+
+// Allocate GC memory for an irange_storage with PRECISION and
+// initialize it to IR.
+
+inline irange_storage *
+irange_storage::alloc (const irange &ir, tree type)
+{
+  if (type)
+    gcc_checking_assert (ir.undefined_p ()
+			 || types_compatible_p (type, ir.type ()));
+  else
+    type = ir.type ();
+  unsigned precision = TYPE_PRECISION (type);
+  irange_storage *stow = static_cast<irange_storage *> (ggc_internal_alloc
+							(size (precision)));
+  stow->set (ir, type);
+  stow->set_nonzero_bits (wi::shwi (-1, precision));
+  return stow;
+}
+
+// Return TRUE if pair [i, j] is marked as empty.
+
+inline bool
+irange_storage::empty_pair_p (unsigned i, unsigned j, tree type) const
+{
+  unsigned precision = wi::get_precision (trailing_bounds[0]);
+  if (precision == 1 && TYPE_SIGN (type) == SIGNED)
+    return (trailing_bounds[i] == wi::zero (precision)
+	    && trailing_bounds[j] == wi::one (precision));
+  return (trailing_bounds[i] == wi::one (precision)
+	  && trailing_bounds[j] == wi::zero (precision));
+}
+
+// Return true if TYPE is a valid type for irange to operate on.
+// Otherwise return FALSE.
+
+inline bool
+irange::supports_type_p (tree type)
+{
+  if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)))
+    return type;
+  return NULL;
+}
+
+// Return true if SSA is a valid ssa_name for irange to operate on.
+// Otherwise return FALSE.
+
+inline bool
+irange::supports_ssa_p (tree ssa)
+{
+  if (!SSA_NAME_IS_VIRTUAL_OPERAND (ssa))
+    return supports_type_p (TREE_TYPE (ssa));
+ return false;
+}
+
+// Return true if EXPR is a valid tree expression for irange to operate on.
+// Otherwise return FALSE.
+
+inline bool
+irange::supports_p (tree expr)
+{
+  if (TYPE_P (expr))
+    return supports_type_p (expr);
+  else if (TREE_CODE (expr) == SSA_NAME)
+    return supports_ssa_p (expr);
+  return supports_type_p (TREE_TYPE (expr));
+}
+
+value_range_base irange_to_value_range (const irange &);
+#else // USE_IRANGE
+class value_range_storage;
+typedef value_range_base irange;
+typedef value_range_storage irange_storage;
+#endif // USE_IRANGE
+
+// Common code between the alternate irange implementations.
+
+irange range_zero (tree type);
+irange range_nonzero (tree type);
+irange range_intersect (const irange &, const irange &);
+irange range_union (const irange &, const irange &);
+irange range_invert (const irange &);
+irange range_positives (tree type);
+irange range_negatives (tree type);
+#endif // GCC_RANGE_H

gcc/selftest.h

@@ -259,6 +259,10 @@ extern int num_passes;
 
 } /* end of namespace selftest.  */
 
+/* This is outside of the selftest namespace because it's a friend of
+   value_range_base.  */
+extern void range_tests ();
+
 /* Macros for writing tests.  */
 
 /* Evaluate EXPR and coerce to bool, calling

gcc/ssa-range-cache.cc

@@ -0,0 +1,730 @@
+/* SSA range cache related functionalilty.
+   Copyright (C) 2017-2018 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@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 "insn-codes.h"
+#include "rtl.h"
+#include "tree.h"
+#include "gimple.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "optabs-tree.h"
+#include "gimple-pretty-print.h"
+#include "diagnostic-core.h"
+#include "flags.h"
+#include "fold-const.h"
+#include "stor-layout.h"
+#include "calls.h"
+#include "cfganal.h"
+#include "gimple-fold.h"
+#include "tree-eh.h"
+#include "gimple-iterator.h"
+#include "gimple-walk.h"
+#include "tree-cfg.h"
+#include "wide-int.h"
+#include "ssa-range.h"
+#include "ssa-range-gori.h"
+#include "fold-const.h"
+
+// During contructor, Allocate the vector of ssa_names.
+
+non_null_ref::non_null_ref ()
+{
+  m_nn.create (0);
+  m_nn.safe_grow_cleared (num_ssa_names);
+}
+
+// Free any bitmaps which were allocated,a swell as the vector itself.
+
+non_null_ref::~non_null_ref ()
+{
+  unsigned x;
+  for (x = 0; x< m_nn.length (); x++)
+    if (m_nn[x])
+      BITMAP_FREE (m_nn[x]);
+}
+
+// Return true if NAME has a non-null dereference in block bb.  If this is the
+// first query for NAME, calculate the summary first.
+
+bool
+non_null_ref::non_null_deref_p (tree name, basic_block bb)
+{
+  if (!POINTER_TYPE_P (TREE_TYPE (name)))
+    return false;
+
+  unsigned v = SSA_NAME_VERSION (name);
+  if (!m_nn[v])
+    process_name (name);
+
+  return bitmap_bit_p (m_nn[v], bb->index);
+}
+
+// Allocate an populate the bitmap for NAME.  An ON bit for a block index
+// indicates there is a non-null reference in that block.
+// In order to populate the bitmap, a quick run of all the immediate uses
+// are made and the statement checked to see if a non-null dereference is made
+// on that statement.
+
+void
+non_null_ref::process_name (tree name)
+{
+  unsigned v = SSA_NAME_VERSION (name);
+  use_operand_p use_p;
+  imm_use_iterator iter;
+  bitmap b;
+
+  // Only tracked for pointers.
+  if (!POINTER_TYPE_P (TREE_TYPE (name)))
+    return;
+
+  // Already processed if a bitmap has been allocated.
+  if (m_nn[v])
+    return;
+
+  b = BITMAP_ALLOC (NULL);
+
+  // Loop over each immediate use and see if it implies a non-null value.
+  FOR_EACH_IMM_USE_FAST (use_p, iter, name)
+    {
+      gimple *s = USE_STMT (use_p);
+      unsigned index = gimple_bb (s)->index;
+      tree value;
+      enum tree_code comp_code;
+
+      // If bit is already set for this block, dont bother looking again.
+      if (bitmap_bit_p (b, index))
+        continue;
+
+      // If we can infer a != 0 range, then set the bit for this BB
+      if (infer_value_range (s, name, &comp_code, &value))
+        {
+	  if (comp_code == NE_EXPR && integer_zerop (value))
+	    bitmap_set_bit (b, index);
+	}
+    }
+
+  m_nn[v] = b;
+}
+
+// This class implements a cache of ranges indexed by basic block.
+// It represents all that is known about an SSA_NAME on entry to each block
+// It caches a range-for-type varying range so it doesnt need to be reformed all
+// the time.  If a range is ever always associated with a type, we can use that
+// instead,.
+// Whenever varying is being set for a block, the cache simply points
+// to this cached one rather than create a new one each time.
+
+class ssa_block_ranges
+{
+public:
+  ssa_block_ranges (tree t);
+  ~ssa_block_ranges ();
+
+  void set_bb_range (const basic_block bb, const irange &r);
+  void set_bb_varying (const basic_block bb);
+  bool get_bb_range (irange &r, const basic_block bb);
+  bool bb_range_p (const basic_block bb);
+
+  void dump(FILE *f);
+private:
+  vec<irange_storage *> m_tab;
+  irange_storage *m_type_range;
+  tree m_type;
+};
+
+
+// Initialize a block cache for an ssa_name of type T
+
+ssa_block_ranges::ssa_block_ranges (tree t)
+{
+  irange tr;
+  gcc_assert (TYPE_P (t));
+  m_type = t;
+
+  m_tab.create (0);
+  m_tab.safe_grow_cleared (last_basic_block_for_fn (cfun));
+
+  // Create the cached type range.
+  tr.set_varying (t);
+  m_type_range = irange_storage::alloc (tr, t);
+
+  m_tab[ENTRY_BLOCK_PTR_FOR_FN (cfun)->index] = m_type_range;
+}
+
+// Destruct block range.
+
+ssa_block_ranges::~ssa_block_ranges ()
+{
+  m_tab.release ();
+}
+
+// Set the range for block BB to be R.
+
+void
+ssa_block_ranges::set_bb_range (const basic_block bb, const irange &r)
+{
+  irange_storage *m = m_tab[bb->index];
+
+  // If there is already range memory for this block, reuse it.
+  if (m && m != m_type_range && m->update (r, m_type))
+    ;
+  else
+    m = irange_storage::alloc (r, m_type);
+
+  m_tab[bb->index] = m;
+}
+
+// Set the range for block BB to the range for the type.
+
+void
+ssa_block_ranges::set_bb_varying (const basic_block bb)
+{
+  m_tab[bb->index] = m_type_range;
+}
+
+// Return the range associated with block BB in R. Return false if there is no
+// range,
+
+bool
+ssa_block_ranges::get_bb_range (irange &r, const basic_block bb)
+{
+  irange_storage *m = m_tab[bb->index];
+  if (m)
+    {
+      r = irange (m_type, m);
+      return true;
+    }
+  return false;
+}
+
+// Returns true if a range is present
+
+bool
+ssa_block_ranges::bb_range_p (const basic_block bb)
+{
+  return m_tab[bb->index] != NULL;
+}
+
+
+// Print the list of known ranges for file F in a nice format.
+
+void
+ssa_block_ranges::dump (FILE *f)
+{
+  basic_block bb;
+  irange r;
+
+  FOR_EACH_BB_FN (bb, cfun)
+    if (get_bb_range (r, bb))
+      {
+	fprintf (f, "BB%d  -> ", bb->index);
+	r.dump (f);
+	fprintf (f, "\n");
+      }
+}
+
+// -------------------------------------------------------------------------
+
+// Initialize the block cache.
+
+block_range_cache::block_range_cache ()
+{
+  m_ssa_ranges.create (0);
+  m_ssa_ranges.safe_grow_cleared (num_ssa_names);
+}
+
+// Remove any m_block_caches which have been created.
+
+block_range_cache::~block_range_cache ()
+{
+  unsigned x;
+  for (x = 0; x < m_ssa_ranges.length (); ++x)
+    {
+      if (m_ssa_ranges[x])
+	delete m_ssa_ranges[x];
+    }
+  // Release the vector itself.
+  m_ssa_ranges.release ();
+}
+
+// Return a reference to the m_block_cache for NAME. If it has not been
+// accessed yet, allocate it.
+
+ssa_block_ranges &
+block_range_cache::get_block_ranges (tree name)
+{
+  unsigned v = SSA_NAME_VERSION (name);
+  if (v >= m_ssa_ranges.length ())
+    m_ssa_ranges.safe_grow_cleared (num_ssa_names + 1);
+
+  if (!m_ssa_ranges[v])
+    m_ssa_ranges[v] = new ssa_block_ranges (TREE_TYPE (name));
+
+  return *(m_ssa_ranges[v]);
+}
+
+// Set the range for NAME on entry to block BB to R.
+
+void
+block_range_cache::set_bb_range (tree name, const basic_block bb,
+				 const irange &r)
+{
+  gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
+  return get_block_ranges (name).set_bb_range (bb, r);
+}
+
+// Set the range for NAME on entry to block BB to varying..
+
+void
+block_range_cache::set_bb_varying (tree name, const basic_block bb)
+{
+  gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
+  return get_block_ranges (name).set_bb_varying (bb);
+}
+
+// Return the range for NAME on entry to BB in R.  Return true if here is one.
+
+bool 
+block_range_cache::get_bb_range (irange &r, tree name, const basic_block bb)
+{
+  gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
+  return get_block_ranges (name).get_bb_range (r, bb);
+}
+
+// Return true if NAME has a range set in block BB.
+
+bool 
+block_range_cache::bb_range_p (tree name, const basic_block bb)
+{
+  gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
+  return get_block_ranges (name).bb_range_p (bb);
+}
+
+// Print all known block caches to file F.
+void
+block_range_cache::dump (FILE *f)
+{
+  unsigned x;
+  for (x = 0; x < m_ssa_ranges.length (); ++x)
+    {
+      if (m_ssa_ranges[x])
+        {
+	  fprintf (f, " Ranges for ");
+	  print_generic_expr (f, ssa_name (x), TDF_NONE);
+	  fprintf (f, ":\n");
+	  m_ssa_ranges[x]->dump (f);
+	  fprintf (f, "\n");
+	}
+    }
+  
+}
+
+// Print all known ranges on entry to blobk BB to file F.
+void
+block_range_cache::dump (FILE *f, basic_block bb, bool print_varying)
+{
+  unsigned x;
+  irange r;
+  bool summarize_varying = false;
+  for (x = 1; x < m_ssa_ranges.length (); ++x)
+    {
+      if (!valid_range_ssa_p (ssa_name (x)))
+        continue;
+      if (m_ssa_ranges[x] && m_ssa_ranges[x]->get_bb_range (r, bb))
+        {
+	  if (!print_varying && r.varying_p ())
+	    {
+	      summarize_varying = true;
+	      continue;
+	    }
+	  print_generic_expr (f, ssa_name (x), TDF_NONE);
+	  fprintf (f, "\t");
+	  r.dump(f);
+	  fprintf (f, "\n");
+	}
+    }
+  // If there were any varying entries, lump them all together.
+  if (summarize_varying)
+    {
+      fprintf (f, "VARYING_P on entry : ");
+      for (x = 1; x < num_ssa_names; ++x)
+	{
+	  if (!valid_range_ssa_p (ssa_name (x)))
+	    continue;
+	  if (m_ssa_ranges[x] && m_ssa_ranges[x]->get_bb_range (r, bb))
+	    {
+	      if (r.varying_p ())
+		{
+		  print_generic_expr (f, ssa_name (x), TDF_NONE);
+		  fprintf (f, "  ");
+	        }
+	    }
+	}
+      fprintf (f, "\n");
+    }
+}
+// -------------------------------------------------------------------------
+
+// Initialize a global cache.
+
+ssa_global_cache::ssa_global_cache ()
+{
+  m_tab.create (0);
+  m_tab.safe_grow_cleared (num_ssa_names);
+}
+
+// Deconstruct a global cache.
+
+ssa_global_cache::~ssa_global_cache ()
+{
+  m_tab.release ();
+}
+
+// Retrieve the global range of NAME from cache memory if it exists. 
+// Return the value in R.
+
+bool
+ssa_global_cache::get_global_range (irange &r, tree name) const
+{
+  unsigned v = SSA_NAME_VERSION (name);
+  if (v >= m_tab.length ())
+    return false;
+   
+  irange_storage *stow = m_tab[v];
+  if (!stow)
+    return false;
+  r = irange (TREE_TYPE (name), stow);
+  return true;
+}
+
+// Set the range for NAME to R in the global cache.
+
+void
+ssa_global_cache::set_global_range (tree name, const irange &r)
+{
+  unsigned v = SSA_NAME_VERSION (name);
+  if (v >= m_tab.length ())
+    m_tab.safe_grow_cleared (num_ssa_names + 1);
+  irange_storage *m = m_tab[v];
+
+  if (m && m->update (r, TREE_TYPE (name)))
+    ;
+  else
+    {
+      m = irange_storage::alloc (r, TREE_TYPE (name));
+      m_tab[SSA_NAME_VERSION (name)] = m;
+    }
+}
+
+// Set the range for NAME to R in the glonbal cache.
+
+void
+ssa_global_cache::clear_global_range (tree name)
+{
+  unsigned v = SSA_NAME_VERSION (name);
+  if (v >= m_tab.length ())
+    m_tab.safe_grow_cleared (num_ssa_names + 1);
+  m_tab[v] = NULL;
+}
+
+// Clear the global cache.
+
+void
+ssa_global_cache::clear ()
+{
+  memset (m_tab.address(), 0, m_tab.length () * sizeof (irange_storage *));
+}
+
+// Dump the contents of the global cache to F. 
+
+void
+ssa_global_cache::dump (FILE *f)
+{
+  unsigned x;
+  irange r;
+  fprintf (f, "Non-varying global ranges:\n");
+  fprintf (f, "=========================:\n");
+  for ( x = 1; x < num_ssa_names; x++)
+    if (valid_range_ssa_p (ssa_name (x)) &&
+	get_global_range (r, ssa_name (x))  && !r.varying_p ())
+      {
+        print_generic_expr (f, ssa_name (x), TDF_NONE);
+	fprintf (f, "  : ");
+        r.dump (f);
+	fprintf (f, "\n");
+      }
+  fputc ('\n', f);
+}
+
+
+// COnstruct a gori_cache object.
+
+gori_cache::gori_cache ()
+{
+  m_workback.create (0);
+  m_workback.safe_grow_cleared (last_basic_block_for_fn (cfun));
+  m_update_list.create (0);
+  m_update_list.safe_grow_cleared (last_basic_block_for_fn (cfun));
+  m_update_list.truncate (0);
+}
+
+// Destruct a gori_cache object.
+
+gori_cache::~gori_cache ()
+{
+  m_workback.release ();
+  m_update_list.release ();
+}
+
+// Return true if NAME has a non-null dereference in block BB.
+
+bool
+gori_cache::non_null_deref_p (tree name, basic_block bb)
+{
+  return m_non_null.non_null_deref_p (name, bb);
+}
+
+void
+gori_cache::dump_block (FILE *f, basic_block bb)
+{
+  m_on_entry.dump (f, bb);
+}
+
+
+// Return a static range for NAME on entry to basic block BB in R.
+// If calc is true, Fill any cache entries required between BB and the def 
+// block for NAME.  Otherwise, return false if the cache is empty.
+
+bool
+gori_cache::block_range (irange &r, basic_block bb, tree name, bool calc)
+{
+
+  gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+  basic_block def_bb = NULL;
+
+  gcc_checking_assert (valid_range_ssa_p (name));
+
+  if (calc)
+    {
+      if (def_stmt)
+	def_bb = gimple_bb (def_stmt);;
+      if (!def_bb)
+        {
+	  // IF we get to the entry block, this better be a default def
+	  // or range_on_entry was called fo a block not dominated by 
+	  // the def.  This would be a bug.
+	  gcc_checking_assert (SSA_NAME_IS_DEFAULT_DEF (name));
+	  def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
+	}
+      
+      // There is no range on entry for the defintion block.
+      if (def_bb == bb)
+	return false;
+
+      // Otherwise, go figure out what is known in predecessor blocks.
+      fill_block_cache (name, bb, def_bb);
+      gcc_checking_assert (m_on_entry.bb_range_p (name, bb));
+    }
+  return m_on_entry.get_bb_range (r, name, bb);
+}
+
+// Return the static range for NAME on edge E in R. If there is no
+// range-on-entry cache for E->src, then return false.
+// If this is the def block, then see if the DEF can be evaluated with them
+// import name, otherwise use varying as the range.
+// If there is any outgoing range information on edge E, incorporate it 
+// into the results.
+
+bool
+gori_cache::edge_range (irange &r, edge e, tree name)
+{
+  basic_block src = e->src;
+  irange er, tmp;
+  gimple *s = SSA_NAME_DEF_STMT (name);
+  basic_block def_bb = ((s && gimple_bb (s)) ? gimple_bb (s) :
+					       ENTRY_BLOCK_PTR_FOR_FN (cfun));
+
+  if (src == def_bb)
+    {
+      // Check to see if the import has a cache_entry, and if it does use that
+      // in an evaluation to get a static starting value.
+      // The import should have a range if the global range is requested
+      // before any other lookups.
+      tree term = terminal_name (name);
+      if (!term || !m_on_entry.get_bb_range (tmp, term, src) ||
+	  !range_from_import (r, name, tmp))
+	{
+	  // Try to pick up any known value first. 
+	  if (!m_globals.get_global_range (r, name))
+	    r = ssa_name_range (name);
+	}
+    }
+  else
+    if (!m_on_entry.get_bb_range (r, name, src))
+      return false;
+
+  // Check if pointers have any non-null dereferences.
+  // Non-call exceptions mean we could throw in the middle of he block,
+  // so just punt for now on those.
+  if (r.varying_p () && m_non_null.non_null_deref_p (name, src) &&
+      !cfun->can_throw_non_call_exceptions)
+    r = range_nonzero (TREE_TYPE (name));
+
+  if (outgoing_edge_range_p (er, e, name, &r))
+    r = er;
+  return true;
+}
+
+void
+gori_cache::add_to_update (basic_block bb)
+{
+  if (!m_update_list.contains (bb))
+    m_update_list.quick_push (bb);
+}
+
+#define DEBUG_CACHE (0 && dump_file)
+
+// If there is anything in the iterative update_list, continue processing NAME
+// until the list of blocks is empty.  
+
+void
+gori_cache::iterative_cache_update (tree name)
+{
+  basic_block bb;
+  edge_iterator ei;
+  edge e;
+  irange new_range;
+  irange current_range;
+  irange e_range;
+
+  // Process each block by seeing if it's calculated range on entry is the same
+  // as it's cached value. IF there is a difference, update the cache to 
+  // reflect the new value, and check to see if any successors have cache 
+  // entries which may need to be checked for updates.
+  
+  while (m_update_list.length () > 0)
+    {
+      bb = m_update_list.pop ();
+if (DEBUG_CACHE) fprintf (dump_file, "FWD visiting block %d\n", bb->index);
+
+      gcc_assert (m_on_entry.get_bb_range (current_range, name, bb));
+      // Calculate the "new" range on entry by unioning the pred edges..
+      new_range.set_undefined ();
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	{
+	  gcc_assert (edge_range (e_range, e, name));
+	  new_range.union_ (e_range);
+	  if (new_range.varying_p ())
+	    break;
+	}
+      // If the range on entry has changed, update it.
+      if (new_range != current_range)
+	{
+if (DEBUG_CACHE) { fprintf (dump_file, "updating range from/to "); current_range.dump (dump_file); new_range.dump (dump_file); }
+	  m_on_entry.set_bb_range (name, bb, new_range);
+	  // Mark each successor that has a range to re-check it's range 
+	  FOR_EACH_EDGE (e, ei, bb->succs)
+	    if (m_on_entry.bb_range_p (name, e->dest))
+	      add_to_update (e->dest);
+	}
+    }
+if (DEBUG_CACHE) fprintf (dump_file, "DONE visiting blocks \n\n");
+}
+
+// Make sure that the range-on-entry cache for NAME is set for block BB.
+// Work back thourgh the CFG to DEF_BB ensuring the range is calculated 
+// on the block/edges leading back to that point.
+
+void
+gori_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
+{
+  edge_iterator ei;
+  edge e;
+  irange block_result;
+  irange undefined;
+
+  // At this point we shouldnt be looking at the def, entry or exit block.
+  gcc_checking_assert (bb != def_bb && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) &&
+		       bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
+
+  // If the block cache is set, then we've already visited this block.
+  if (m_on_entry.bb_range_p (name, bb))
+    return;
+
+  // Visit each block back to the DEF.  Initialize each one to UNDEFINED.
+  // m_visited at the end will contain all the blocks that we needed to set
+  // the range_on_entry cache for.
+  m_workback.truncate (0);
+  m_workback.quick_push (bb);
+  undefined.set_undefined ();
+  m_on_entry.set_bb_range (name, bb, undefined);
+  gcc_checking_assert (m_update_list.length () == 0);
+
+if (DEBUG_CACHE) { fprintf (dump_file, "\n"); print_generic_expr (dump_file, name, TDF_SLIM); fprintf (dump_file, " : "); }
+
+  while (m_workback.length () > 0)
+    {
+      basic_block node = m_workback.pop ();
+if (DEBUG_CACHE)  fprintf (dump_file, "BACK visiting block %d\n", node->index);
+
+      FOR_EACH_EDGE (e, ei, node->preds)
+        {
+	  basic_block pred = e->src;
+	  irange r;
+	  // If the pred block is the def block add this BB to update list.
+	  if (pred == def_bb) 
+	    {
+	      add_to_update (node);
+	      continue;
+	    }
+
+	  // If the pred is entry but NOT def, then it is used before defined,
+	  // It'll get set to []. and no need to update it.
+	  if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun))
+	    continue;
+
+	  // Regardless of whther we have visited pred or not, if the pred has
+	  // a non-null reference, revisit this block.
+	  if (m_non_null.non_null_deref_p (name, pred))
+	    add_to_update (node);
+
+	  // If the pred block already has a range, or if it can contribute
+	  // something new. Ie, the edge generates a range of some sort.
+	  if (m_on_entry.get_bb_range (r, name, pred))
+	    {
+	      if (!r.undefined_p () || has_edge_range_p (e, name))
+		add_to_update (node);
+	      continue;
+	    }
+	    
+	  // If the pred hasn't been visited (has no range), add it to the list.
+	  gcc_checking_assert (!m_on_entry.bb_range_p (name, pred));
+	  m_on_entry.set_bb_range (name, pred, undefined);
+	  m_workback.quick_push (pred);
+	}
+    }
+
+  iterative_cache_update (name);
+}

gcc/ssa-range-cache.h

@@ -0,0 +1,105 @@
+/* Header file for SSA range cache classes.
+   Copyright (C) 2017-2018 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@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/>.  */
+
+#ifndef GCC_SSA_RANGE_CACHE_H
+#define GCC_SSA_RANGE_CACHE_H
+
+// This global cache is used with the range engine as markers for what
+// has been visited during this incarnation.  Once the ranger evaluates
+// a name, it is typically not re-evaluated again.   
+//
+
+class ssa_global_cache
+{
+public:
+  ssa_global_cache ();
+  ~ssa_global_cache ();
+  bool get_global_range (irange& r, tree name) const;
+  void set_global_range (tree name, const irange&r);
+  void clear_global_range (tree name);
+  void clear ();
+  void dump (FILE *f = stderr);
+private:
+  vec<irange_storage *> m_tab;
+};
+
+// Class used to track non-null references of an ssa-name
+// A vector of bitmaps indexed by ssa-name is maintained. When indexed by 
+// Basic Block, an on-bit indicates there is a non-null dereference for
+// that ssa_name in that basic block.
+
+class non_null_ref
+{
+public:
+  non_null_ref ();
+  ~non_null_ref ();
+  bool non_null_deref_p (tree name, basic_block bb);
+private:
+  vec <bitmap> m_nn;
+  void process_name (tree name);
+};
+
+// This class manages a vector of pointers to ssa_block ranges.
+// THis provides the basis for the "range on entry" cache for
+// all ssa-names.
+
+class block_range_cache
+{
+public:
+  block_range_cache ();
+  ~block_range_cache ();
+
+  // Hide the details of the block cache with these wrappers
+  void set_bb_range (tree name, const basic_block bb, const irange &r);
+  void set_bb_varying (tree name, const basic_block bb);
+  bool get_bb_range (irange &r, tree name, const basic_block bb);
+  bool bb_range_p (tree name, const basic_block bb);
+
+  void dump (FILE *f);
+  void dump (FILE *f, basic_block bb, bool print_varying = true);
+private:
+  vec<class ssa_block_ranges *> m_ssa_ranges;
+  ssa_block_ranges &get_block_ranges (tree name);
+};
+
+class gori_cache : public gori_compute
+{
+public:
+  gori_cache ();
+  ~gori_cache ();
+  bool non_null_deref_p (tree name, basic_block bb);
+  bool block_range (irange &r, basic_block bb, tree name, bool calc = true);
+  void dump_block (FILE *f, basic_block bb);
+
+  ssa_global_cache m_globals;
+
+private:
+  void add_to_update (basic_block bb);
+  bool edge_range (irange &r, edge e, tree name);
+  void fill_block_cache (tree name, basic_block bb, basic_block def_bb);
+  void iterative_cache_update (tree name);
+
+  block_range_cache m_on_entry;
+  non_null_ref m_non_null;
+  vec<basic_block> m_workback;
+  vec<basic_block> m_update_list;
+};
+
+#endif // GCC_SSA_RANGE_CACHE_H

gcc/ssa-range-gori.h

@@ -0,0 +1,189 @@
+/* Header file for SSA range GORI structures.
+   Copyright (C) 2017-2018 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@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/>.  */
+
+#ifndef GCC_SSA_RANGE_GORI_H
+#define GCC_SSA_RANGE_GORI_H
+
+/* RANGE_DEF_CHAIN is used to determine what ssa-names in a block can have range
+   information calculated for them, and what the dependencies on each other are.
+
+   Information for a basic block is calculated once and stored.  It is only
+   calculated the first time a query is made, so if no queries are made, there
+   is little overhead.
+   
+   The def_chain bitmap is indexed by ssa_name version.  Bits are set within
+   this bitmap to indicate ssa_names that are defined in the SAME block and used
+   to calculate this ssa_name.
+
+   One import is maintained per def-chain.  An IMPORT is defined as an ssa-name
+   in the def chain which occurs outside the basic block. A change in the value
+   of this ssa-name can change the value of any name in the chain. 
+
+   If there is more than one import, or an ssa-Name originates WITHIN the same 
+   basic block but is defined by a statement that the range engine does not
+   know how to calculate, then there is no import for the entire chain.
+
+    <bb 2> :
+      _1 = x_4(D) + -2;
+      _2 = _1 * 4;
+      j_7 = foo ();
+      q_5 = _2 + 3;
+      if (q_5 <= 13)
+
+    _1  : (import : x_4(D))  :x_4(D)
+    _2  : (import : x_4(D))  :_1  x_4(D)
+    q_5  : (import : x_4(D))  :_1  _2  x_4(D)
+
+    This dump indicates the bits set in the def_chain vector and ther import, as
+    well as demonstrates the def_chain bits for the related ssa_names.
+
+    Checking the chain for _2 indicates that _1 and x_4 are used in its
+    evaluation, and with x_4 being an import.
+
+    For the purpose of defining an import, PHI node defintions  are considered
+    imports as the dont really reside in the block, but rather are
+    accumulators of values from incoming edges.
+    
+    Def chains also only include statements which are valid grange's so
+    a def chain will only span statements for which the range engine
+    implements operations.  */
+
+
+class range_def_chain
+{
+public:
+  range_def_chain ();
+  ~range_def_chain ();
+  tree terminal_name (tree name);
+  bool has_def_chain (tree name);
+  bitmap get_def_chain (tree name);
+  bool in_chain_p (tree name, tree def);
+private:
+  vec<bitmap> m_def_chain;	// SSA_NAME : def chain components.
+  vec<tree> m_terminal;	        // SSA_NAME : chain terminal name.
+  tree build_def_chain (tree name, bitmap result, basic_block bb);
+};
+
+
+/* GORI_MAP is used to accumulate what ssa-names in a block can generate range
+   information, and provides tools for the block ranger to enable it to
+   efficiently calculate these ranges.
+   GORI stands for "Generates Outgoing Range Information."
+
+   It utilizes the range_def_chain class to contruct def_chains.
+   information for a basic block is calculated once and stored. It is only
+   calculated the first time a query is made, so if no queries are made, there
+   is little overhead.
+   
+   2 bitmaps are maintained for each basic block:
+   m_outgoing  : a set bit indicates a range can be generated for a name.
+   m_incoming  : a set bit means a this name come from outside the block and is
+	       used in the calculation of some outgoing range.
+   
+   Generally speaking, the m_outgoing vector is the union of the entire
+   def_chain of all ssa-names used in the last statement of the block which
+   generate ranges.  The m_incoming vector is the union of all the terminal
+   names of those def chains.  They act as a one-stop summary for the block.  */
+
+class gori_map : public range_def_chain
+{
+public:
+  gori_map ();
+  ~gori_map ();
+
+  bool is_export_p (tree name, basic_block bb);
+  bool def_chain_in_export_p (tree name, basic_block bb);
+  bool is_import_p (tree name, basic_block bb);
+
+  void dump (FILE *f);
+  void dump (FILE *f, basic_block bb);
+private:
+  vec<bitmap> m_outgoing;	// BB: Outgoing ranges generated.
+  vec<bitmap> m_incoming;	// BB: ranges coming in.
+  void maybe_add_gori (tree name, basic_block bb);
+  void calculate_gori (basic_block bb);
+  bitmap imports (basic_block bb);
+  bitmap exports (basic_block bb);
+};
+
+// Calculate range for NAME when it occurs somewhere on stmt S.  This is not
+// part of the gori_compute class as it has no requirements for the
+// def_chains.  given :
+//  	if (c_3 < 10)
+// It can calculate a range for c_3 of [MIN, 9] on the outgoing edge since it
+// is referenced in the statement which generates the range.
+
+extern bool compute_operand_range_on_stmt (irange &r, gimple *s,
+					   const irange &lhs, tree name,
+					   irange *name_range = NULL);
+
+// This class enhances the GORI map to add functionality to compute the value
+// of named operands from the def chain.  It Adds a single entry point which
+// will find a range for NAME based on the def chain of def of S.  S is
+// presumed to have the known range LHS.  If a range is supplied for IMPORT
+// it is taken to be the value of the terminal name pof the def chain, if
+// it should be needed.  Given:
+// BB4:
+//     a_2 = b_6 + 6
+//     c_3 = a_2 * 2
+//     if (c_3 < 9)
+// it builds defintion chains which will allow the calculation
+// of ssa-names found within these chains.  In this example, it can also
+// generate ranges for a_2 and b_6 on the outgoing edges.
+
+class gori_compute : public gori_map
+{
+public:
+  gori_compute ();
+  ~gori_compute ();
+
+  bool has_edge_range_p (edge e, tree name);
+  bool outgoing_edge_range_p (irange &r, edge e, tree name,
+			      irange *name_range = NULL);
+protected:
+  bool range_from_import (irange &r, tree name, irange &import_range);
+private:
+  // Evaluate the range for NAME on stmt S if the lhs has range LHS. 
+  // Substituting results back until we encounter NAME.
+  bool compute_operand_range (irange &r, gimple *s, const irange &lhs,
+			      tree name, irange *name_range = NULL);
+  bool compute_operand_range_switch (irange &r, gswitch *s, const irange &lhs,
+				     tree name, irange *name_range);
+  bool compute_operand_range_op (irange &r, grange *stmt, const irange &lhs,
+				 tree name, irange *name_range);
+  bool compute_operand1_range (irange &r, grange *s, const irange &lhs,
+			       tree name, irange *name_range);
+  bool compute_operand2_range (irange &r, grange *s, const irange &lhs,
+			       tree name, irange *name_range);
+  bool compute_operand1_and_operand2_range (irange &r, grange *s, 
+					    const irange &lhs, tree name,
+					    irange *name_range);
+  bool compute_logical_operands (irange &r, grange *s, const irange &lhs,
+				 tree name, irange *name_range);
+  bool logical_combine (irange &r, enum tree_code code, const irange &lhs,
+		        const irange &op1_true, const irange &op1_false,
+		        const irange &op2_true, const irange &op2_false);
+  bool reevaluate_definition (irange &r, tree name, edge e,
+                              irange *block_range);
+  irange m_bool_zero;           /* Boolean zero cached.  */
+  irange m_bool_one;            /* Boolean true cached.  */
+};
+
+#endif // GCC_SSA_RANGE_GORI_H

gcc/ssa-range-vrp.c

@@ -0,0 +1,528 @@
+/* VRP implemented with SSA Ranger.
+   Copyright (C) 2018-2019 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@redhat.com>
+   and 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 "insn-codes.h"
+#include "rtl.h"
+#include "tree.h"
+#include "gimple.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "optabs-tree.h"
+#include "gimple-pretty-print.h"
+#include "diagnostic-core.h"
+#include "flags.h"
+#include "fold-const.h"
+#include "stor-layout.h"
+#include "calls.h"
+#include "cfganal.h"
+#include "gimple-fold.h"
+#include "tree-eh.h"
+#include "gimple-iterator.h"
+#include "gimple-walk.h"
+#include "tree-cfg.h"
+#include "wide-int.h"
+#include "domwalk.h"
+#include "ssa-range.h"
+#include "tree-ssa-dce.h"
+#include "cfgloop.h"
+#include "tree-scalar-evolution.h"
+#include "tree-ssa-loop.h"
+#include "alloc-pool.h"
+#include "range.h"
+#include "vr-values.h"
+#include "tree-ssa-propagate.h"
+#include "dbgcnt.h"
+
+class irange_misc : public range_misc
+{
+public:
+  irange_misc (global_ranger *r) : m_ranger (r) { }
+private:
+  virtual irange get_irange (tree, gimple *);
+  virtual tree singleton (tree, gimple *stmt);
+  global_ranger *m_ranger;
+};
+
+irange
+irange_misc::get_irange (tree op, gimple *stmt)
+{
+  if (TREE_CODE (op) == INTEGER_CST)
+    return irange (op, op);
+
+  irange r;
+  m_ranger->range_of_expr (r, op, stmt);
+  return r;
+}
+
+/* If OP has a value range with a single constant value return that,
+   otherwise return NULL_TREE.  This returns OP itself if OP is a
+   constant.  */
+
+tree
+irange_misc::singleton (tree op, gimple *stmt)
+{
+  if (is_gimple_min_invariant (op))
+    return op;
+
+  if (TREE_CODE (op) != SSA_NAME)
+    return NULL_TREE;
+
+  tree t;
+  if (get_irange (op, stmt).singleton_p (&t))
+    return t;
+  return NULL;
+}
+
+// Return TRUE if NAME can be propagated.,
+
+static bool
+argument_ok_to_propagate (tree name)
+{
+  if (TREE_CODE (name) != SSA_NAME)
+    return true;
+
+  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
+    {
+      // From may_propagate_copy
+      if (SSA_NAME_IS_DEFAULT_DEF (name) &&
+	  (SSA_NAME_VAR (name) == NULL_TREE ||
+	   TREE_CODE (SSA_NAME_VAR (name)) == VAR_DECL))
+	return true;
+      else
+        return false;
+    }
+
+  if (virtual_operand_p (name))
+    return false;
+  return true;
+}
+
+// Fold a constant GIMPLE_ASSIGN if possible.  Return TRUE if successful.
+
+static bool
+rvrp_fold_const_assign (gassign *assign, const irange &r)
+{
+  irange trange;
+  // ?? Perhaps we could set the assignment to 0 instead?
+  if (r.undefined_p ())
+    return false;
+  tree rhs;
+  gcc_assert (r.singleton_p (&rhs));
+
+  /* Avoid building incompatible assignments.
+
+     Fortran has different precision booleans and
+     operator_not_equal::fold_range is building booleans that don't
+     match.  Consequently, the global range table is being populated
+     by range kind:1 whereas sometimes Fortran can have other sized
+     booleans. */
+
+  delink_stmt_imm_use (assign);
+  gimple_assign_set_rhs_code (assign, SSA_NAME);
+  gimple_assign_set_rhs1 (assign, rhs);
+  gimple_set_num_ops (assign, 2);
+  return true;
+}
+
+// Fold a constant GIMPLE_COND if possible.  Return TRUE if successful.
+
+static bool
+rvrp_fold_const_cond (gcond *cond, const irange &r)
+{
+  /* Rewrite the condition to either true or false.  */
+  if (r.zero_p ())
+    gimple_cond_make_false (cond);
+  else
+    gimple_cond_make_true (cond);
+  return true;
+}
+
+// Fold STMT in place if possible.  Return TRUE if folding was successful.
+
+static bool
+rvrp_fold (ssa_ranger &ranger, gimple *stmt, bitmap touched)
+{
+  irange r;
+  if (ranger.range_of_stmt (r, stmt) && !r.varying_p ())
+    {
+      // If it folds to a constant and it's OK to propagate the args.
+      // Also, if it folds to [], the statement is unreachable (and
+      // the BB for that matter).  Fold the branch enough so we can
+      // nuke any possible SSA uses in the conditional.
+      if (r.singleton_p () || r.undefined_p ())
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	      fprintf (dump_file, "      Expression evaluates to singleton: ");
+	      r.dump (dump_file);
+	    }
+
+	  // Verify we can propagate all SSA names in statement.
+	  for (unsigned i = 1; i < gimple_num_ops (stmt); ++i)
+	    {
+	      tree t = gimple_op (stmt, i);
+	      if (t && !argument_ok_to_propagate (t))
+		return false;
+	    }
+	  // Potentially mark folded SSA_NAMEs for future deletion.
+	  for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
+	    {
+	      tree t = gimple_op (stmt, i);
+	      if (t && TREE_CODE (t) == SSA_NAME)
+		bitmap_set_bit (touched, SSA_NAME_VERSION (t));
+	    }
+
+	  bool changed = false;
+	  switch (gimple_code (stmt))
+	    {
+	    case GIMPLE_COND:
+	      changed = rvrp_fold_const_cond (dyn_cast <gcond *> (stmt), r);
+	      break;
+	    case GIMPLE_ASSIGN:
+	      changed = rvrp_fold_const_assign (dyn_cast <gassign *> (stmt),
+						r);
+	      break;
+	    default:
+	      gcc_unreachable ();
+	    }
+	  if (changed)
+	    {
+	      if (dump_file)
+		{
+		  fprintf (dump_file, "RVRP: %s rewritten to: ",
+			   gimple_code (stmt) == GIMPLE_COND
+			   ? "Branch" : "Statement");
+		  print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+		  fprintf (dump_file, "\n");
+		}
+	      update_stmt (stmt);
+	    }
+	  else if (dump_file)
+	    fprintf (dump_file, "RVRP: Cannot propagate.\n");
+	  return changed;
+	}
+    }
+  else
+    {
+      // The expression doesn't fold, but see if any operand evaluates
+      // to an empty range on one side, indicating the edge is not
+      // executable.
+    }
+  return false;
+}
+
+// Given a STMT for which we can't totally fold, attempt to simplify
+// it in place using known range information.
+//
+// Returns TRUE if any simplification was done.
+
+static bool
+rvrp_simplify (global_ranger &ranger, gimple_stmt_iterator *gsi)
+{
+  gimple *orig;
+  bool details = dump_file && (dump_flags & TDF_DETAILS);
+  if (details)
+    orig = gimple_copy (gsi_stmt (*gsi));
+
+  irange_misc misc (&ranger);
+  if (misc.simplify_stmt_using_ranges (gsi))
+    {
+      gimple *stmt = gsi_stmt (*gsi);
+      if (details)
+	{
+	  fprintf (dump_file, "RVRP: Simplifying:\t");
+	  print_gimple_stmt (dump_file, orig, 0, TDF_SLIM);
+	  fprintf (dump_file, "\t\t\t");
+	  print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	}
+      update_stmt (stmt);
+      return true;
+    }
+  return false;
+}
+
+// Given a bitmap of TOUCHED ssa names throughout the pass, attempt to
+// propagate any uses and possibly remove dead code.
+
+static void
+rvrp_final_propagate (global_ranger &ranger, bitmap touched)
+{
+  if (dump_file && (dump_flags & TDF_DETAILS) && !bitmap_empty_p (touched))
+    {
+      unsigned i;
+      bitmap_iterator bi;
+
+      fprintf (dump_file, "RVRP: Propagating SSAs: ");
+      EXECUTE_IF_SET_IN_BITMAP (touched, 0, i, bi)
+	{
+	  print_generic_expr (dump_file, ssa_name (i));
+	  fprintf (dump_file, ", ");
+	}
+      fprintf (dump_file, "\n");
+    }
+
+  propagate_from_worklist (touched);
+  simple_dce_from_worklist (touched);
+  ranger.export_global_ranges ();
+}
+
+// Perform a domwalk and accumulate all blocks into a vector.
+class dom_accumulator : public dom_walker
+{
+public:
+  dom_accumulator (cdi_direction dir, vec<basic_block> &blocks);
+  virtual ~dom_accumulator () { }
+  virtual edge before_dom_children (basic_block);
+private:
+  vec<basic_block> &m_bbs;
+};
+
+dom_accumulator::dom_accumulator (cdi_direction dir, vec<basic_block> &blocks)
+    : dom_walker (dir), m_bbs (blocks)
+{
+  if (dir == CDI_DOMINATORS)
+    walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+  else
+    walk (EXIT_BLOCK_PTR_FOR_FN (cfun));
+}
+
+edge
+dom_accumulator::before_dom_children (basic_block bb)
+{
+  m_bbs.quick_push (bb);
+  return NULL;
+}
+
+// Main rvrp engine that can run in a variety of different orders:
+// Dominator, post-dominator, forward block order, and backwards block
+// order.
+class rvrp_engine
+{
+public:
+  rvrp_engine (enum rvrp_order);
+  ~rvrp_engine ();
+
+private:
+  void run ();
+  void visit (basic_block);
+  void fold_and_simplify (gimple_stmt_iterator &);
+
+  dom_accumulator *m_dom_accumulator;
+  auto_vec<basic_block> m_bbs;
+  // This is a pointer instead of a scalar so we can delay
+  // construction until after loop info is available.
+  trace_ranger *m_ranger;
+  auto_bitmap m_touched;
+  propagate_cleanups m_cleanups;
+  enum rvrp_order m_order;
+};
+
+rvrp_engine::rvrp_engine (enum rvrp_order order)
+  : m_order (order)
+{
+  // Loop info must be initialized before the ranger because
+  // loop_optimizer_init() may alter the IL while normalizing loops.
+  calculate_dominance_info (CDI_DOMINATORS);
+  loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
+  scev_initialize ();
+
+  basic_block bb;
+  m_bbs.reserve (n_basic_blocks_for_fn (cfun));
+  m_ranger = new trace_ranger;
+
+  switch (order)
+    {
+    case RVRP_ORDER_DOMINATOR:
+      m_dom_accumulator = new dom_accumulator (CDI_DOMINATORS, m_bbs);
+      break;
+    case RVRP_ORDER_POSTDOM:
+      calculate_dominance_info (CDI_POST_DOMINATORS);
+      m_dom_accumulator = new dom_accumulator (CDI_POST_DOMINATORS, m_bbs);
+      break;
+    case RVRP_ORDER_FORWARD:
+    case RVRP_ORDER_CONDITIONALS:
+      FOR_EACH_BB_FN (bb, cfun)
+	m_bbs.quick_push (bb);
+      m_dom_accumulator = NULL;
+      break;
+    case RVRP_ORDER_BACKWARD:
+      FOR_EACH_BB_REVERSE_FN (bb, cfun)
+	m_bbs.quick_push (bb);
+      m_dom_accumulator = NULL;
+      break;
+    default:
+      gcc_unreachable ();
+    }
+  run ();
+}
+
+rvrp_engine::~rvrp_engine ()
+{
+  if (m_dom_accumulator)
+    delete m_dom_accumulator;
+
+  if (m_order == RVRP_ORDER_POSTDOM)
+    free_dominance_info (CDI_POST_DOMINATORS);
+
+  scev_finalize ();
+  loop_optimizer_finalize ();
+  free_dominance_info (CDI_DOMINATORS);
+
+  rvrp_final_propagate (*m_ranger, m_touched);
+}
+
+void
+rvrp_engine::fold_and_simplify (gimple_stmt_iterator &gsi)
+{
+  bool changed = false;
+  irange r;
+  gimple *stmt = gsi_stmt (gsi);
+
+  // Only process statements which are a COND expr or have a valid LHS.
+  if (gimple_code (stmt) != GIMPLE_COND &&
+      !valid_range_ssa_p (gimple_get_lhs (stmt)))
+    return;
+
+  // ?? This is only needed for propagate_mark_stmt_for_cleanup.
+  // Can we get away with a shallow copy?
+  gimple *old_stmt = gimple_copy (stmt);
+
+  if (!dbg_cnt (rvrp_fold_count))
+    return;
+
+  if (m_ranger->range_of_stmt (r, stmt))
+    changed = rvrp_fold (*m_ranger, stmt, m_touched);
+  if (!changed)
+    changed = rvrp_simplify (*m_ranger, &gsi);
+  if (changed)
+    m_cleanups.record_change (old_stmt, stmt);
+}
+
+void
+rvrp_engine::visit (basic_block bb)
+{
+  irange r;
+  gimple_stmt_iterator gsi;
+
+  if (dump_file)
+    fprintf (dump_file, "RVRP: Considering BB %d.\n", bb->index);
+
+  if (m_order == RVRP_ORDER_CONDITIONALS)
+    {
+      // Check if there is a conditional at the end of the block and visit it.
+      gsi = gsi_outgoing_range_stmt (bb);
+      if (!gsi_end_p (gsi))
+        fold_and_simplify (gsi);
+      return;
+    }
+
+  // Process all the PHI nodes.
+  for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
+       gsi_next (&gpi))
+    {
+      gphi *phi = gpi.phi ();
+      tree phi_def = gimple_phi_result (phi);
+      if (valid_range_ssa_p (phi_def))
+	m_ranger->range_of_stmt (r, phi);
+    }
+
+  // If processing in reverse, walk the IL bottom up.
+  if (m_order == RVRP_ORDER_BACKWARD)
+    for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
+      fold_and_simplify (gsi);
+  else
+    for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+      fold_and_simplify (gsi);
+}
+
+void
+rvrp_engine::run ()
+{
+  bool details = dump_file && (dump_flags & TDF_DETAILS);
+  basic_block bb;
+
+  // Create a temp ranger and exercise it before running in order to get a
+  // listing in the dump file, and to fully exercise the code.
+  if (details)
+    {
+      fprintf (dump_file, "RVRP: BEFORE rvrp ranger dump.\n");
+      global_ranger e;
+      e.calculate_and_dump (dump_file);
+    }
+
+  for (unsigned i = 0; m_bbs.iterate (i, &bb); ++i)
+    visit (bb);
+}
+
+static unsigned int
+execute_ranger_vrp ()
+{
+  enum rvrp_order order
+    = flag_rvrp_order ? flag_rvrp_order : RVRP_ORDER_DOMINATOR;
+  rvrp_engine w (order);
+  return 0;
+}
+
+namespace {
+
+const pass_data pass_data_ranger_vrp =
+{
+  GIMPLE_PASS, /* type */
+  "rvrp", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_TREE_RANGER_VRP, /* tv_id */
+  PROP_ssa, /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  ( TODO_cleanup_cfg | 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 methods: */
+  opt_pass * clone () { return new pass_ranger_vrp (m_ctxt); }
+  virtual bool gate (function *)
+    {
+      return flag_tree_rvrp != 0;
+    }
+  virtual unsigned int execute (function *)
+    { return execute_ranger_vrp (); }
+
+}; // class pass_vrp
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_ranger_vrp (gcc::context *ctxt)
+{
+  return new pass_ranger_vrp (ctxt);
+}

gcc/ssa-range.h

@@ -0,0 +1,198 @@
+/* Header file for SSA range interface.
+   Copyright (C) 2017-2018 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@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/>.  */
+
+#ifndef GCC_SSA_RANGE_H
+#define GCC_SSA_RANGE_H
+
+#include "grange.h"
+#include "ssa-range-gori.h"
+#include "ssa-range-cache.h"
+
+// This is the basic range generator interface. 
+//
+// This base class provides all the API entry points, but only provides 
+// functionality at the statement level.  Ie, it can calculate ranges on 
+// statements, but does no additonal lookup.
+//
+// All the range_of_* methods will return a range if the types is supported
+// by the range engine. It may be the full range for the type, AKA varying_p
+// or it may be a refined range.
+// If the range type is not supported, then false is returned.
+// The basic ssa_ranger class will also return false for range_on_entry and
+// range_on_exit as those make no sense at the statement level.
+//
+// outgoing_edge_range_p will only return a range if the edge specified 
+// defines a range for the specified name.  Otherwise false is returned.
+//
+//
+class stmt_ranger
+{
+  public:
+  
+  bool range_of_expr (irange &r, tree expr, gimple *s = NULL);
+  virtual irange range_of_ssa_name (tree name, gimple *s = NULL);
+  virtual bool range_of_stmt (irange &r, gimple *s, tree name = NULL_TREE);
+  virtual bool range_of_stmt_with_range (irange &r, gimple *s, tree name,
+					 const irange &name_range);
+protected:
+  bool range_of_grange  (irange &r, grange *s, tree name = NULL_TREE,
+			 const irange *name_range = NULL);
+
+  virtual bool range_of_phi (irange &r, gphi *phi, tree name = NULL_TREE,
+			     const irange *name_range = NULL);
+
+  bool range_of_call (irange &r, gcall *call, tree name = NULL_TREE,
+		      const irange *name_range = NULL);
+
+  bool range_of_cond_expr (irange &r, gassign* call, tree name = NULL_TREE,
+			   const irange *name_range = NULL);
+};
+
+class ssa_ranger : public stmt_ranger
+{
+  public:
+  virtual void range_on_edge (irange &r, edge e, tree name);
+  virtual void range_on_entry (irange &r, basic_block bb, tree name);
+  virtual void range_on_exit (irange &r, basic_block bb, tree name);
+
+  virtual bool outgoing_edge_range_p (irange &r, edge e, tree name,
+				      irange *name_range = NULL);
+  
+protected:
+  virtual bool range_of_phi (irange &r, gphi *phi, tree name = NULL_TREE,
+			     const irange *name_range = NULL);
+};
+
+// This class utilizes the gori summary to query the range
+// of SSA_NAMEs across multiple basic blocks and edges.  It builds a cache
+// of range on entry to blocks.  All work is done on-demand so it is relatively
+// lightweight until used.
+//
+// GORI stands for Generates Outgoing Range Info
+// Itutilizes the engine from ssa-range-gori.h to build
+// defintion chains on demand which enables the calculation of ranges for 
+// various ssa names that are related to those that actually generate ranges.
+//
+// It is lightweight to declare in this case, but for each basic block that is
+// queried, it will scan some or all of the statements in the block to
+// determine what ssa-names can have range information generated for them and
+// cache this information.  
+//
+// terminal_name () provides the "input" name to the chain of statements for
+// name that can change the calculation of its range.  This is usually outside 
+// the basic block the name is defind in..  ie,
+// bb4:
+//   a_2 = b_6 + 5
+//   c_3 = (a_2 < 25)
+// in this small example, b_6 is the
+// "terminal_name" returned for both a_2 and c_3 since a change in the
+// range of b_6 to calculate their results may produce a different range.
+
+
+class global_ranger : public ssa_ranger
+{
+public:
+  global_ranger ();
+  ~global_ranger ();
+
+  virtual irange range_of_ssa_name (tree name, gimple *s = NULL);
+  virtual bool range_of_stmt (irange &r, gimple *s, tree name = NULL_TREE);
+  virtual void range_on_entry (irange &r, basic_block bb, tree name);
+
+  virtual bool outgoing_edge_range_p (irange &r, edge e, tree name,
+				      irange *name_range = NULL);
+  tree terminal_name (tree name);
+
+  void export_global_ranges ();
+
+  void dump (FILE *f);
+  void calculate_and_dump (FILE *f);   /* Calculate all stmts and dump */
+
+protected:
+  gori_cache m_gori; 	  /* Generates Outgoing Range Info.  */
+};
+
+// FIXME: Forward declaration for loop_ranger.
+class vr_values;
+
+// A global ranger that uses SCEV/loop (if available) to refine PHI results.
+
+class loop_ranger : public global_ranger
+{
+public:
+  loop_ranger ();
+  ~loop_ranger ();
+private:
+  void adjust_phi_with_loop_info (irange &r, gphi *phi);
+  virtual bool range_of_phi (irange &r, gphi *phi, tree name,
+			     const irange *name_range);
+
+  vr_values *m_vr_values;
+};
+
+class trace_ranger : public loop_ranger
+{
+public:
+  trace_ranger();
+
+  virtual irange range_of_ssa_name (tree name, gimple *s = NULL);
+  virtual bool range_of_stmt (irange &r, gimple *s, tree name = NULL_TREE);
+  virtual void range_on_edge (irange &r, edge e, tree name);
+  virtual void range_on_entry (irange &r, basic_block bb, tree name);
+  virtual void range_on_exit (irange &r, basic_block bb, tree name);
+
+  // Calculate a range on edge E only if it is defined by E.
+  virtual bool outgoing_edge_range_p (irange &r, edge e, tree name,
+				      irange *name_range = NULL);
+private:
+  typedef global_ranger super;  // Inherited from class for easy changing.
+  static const unsigned bump = 2;
+  unsigned indent;
+  unsigned trace_count;		// Current trace index count.
+
+  bool dumping (unsigned counter, bool trailing = false);
+  bool trailer (unsigned counter, const char *caller, bool result, tree name,
+		const irange &r);
+};
+
+  
+
+// Like global_ranger::range_of_expr (), but make an on-the-fly ranger.
+// Return TRUE if SSA as seen from within STMT has a known range the is not
+// varying.  Set this range in R.
+//
+// NOTE: There is overhead involved with this function, so it
+// should only be used for very lightweight or unrelated range
+// queries.  This function is mostly meant for range queries that
+// don't need caching in subsequent calls.  */
+
+static inline bool
+on_demand_get_range_on_stmt (irange &r, tree ssa, gimple *stmt)
+{
+  if (!cfun->cfg)
+    return false;
+  loop_ranger ranger;
+  bool ret;
+  ret = ranger.range_of_expr (r, ssa, stmt);
+  if (ret && r.varying_p ())
+    return false;
+  return ret;
+}
+#endif // GCC_SSA_RANGE_H

gcc/ssa.h

@@ -26,6 +26,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "stringpool.h"
 #include "gimple-ssa.h"
 #include "tree-vrp.h"
+#include "range.h"
 #include "tree-ssanames.h"
 #include "tree-phinodes.h"
 #include "ssa-iterators.h" 

gcc/testsuite/g++.dg/debug/dwarf2/deallocator.C

@@ -5,7 +5,7 @@
 // FE generated debug info, without losing generality, only x86
 // assembly is scanned in this test.
 // { dg-do compile { target { i?86-*-* x86_64-*-* } } }
-// { dg-options "-O2 -fno-exceptions -gdwarf-2 -dA" }
+// { dg-options "-O1 -fno-exceptions -gdwarf-2 -dA" }
 
 struct t {
   t ();
@@ -44,3 +44,8 @@ void foo(int i)
 // { dg-final { scan-assembler "deallocator.C:24" } }
 // { dg-final { scan-assembler "deallocator.C:34" } }
 // { dg-final { scan-assembler "deallocator.C:21" } }
+
+// Note: With range-based threading, all of foo() gets flattened out,
+// and this test no longer passes.  Hence the use of -O1 above, as
+// opposed -O2.  This should be OK, as the original patch that
+// inspired this test was a front-end test.

gcc/testsuite/g++.dg/tree-ssa/pr61034.C

@@ -1,5 +1,6 @@
 // { dg-do compile }
-// { dg-options "-O2 -fdump-tree-fre3 -fdump-tree-optimized -fdelete-null-pointer-checks" }
+
+// { dg-options "-O2 -fdump-tree-fre3 -fdump-tree-optimized -fdelete-null-pointer-checks -fdisable-tree-rvrp" }
 
 #define assume(x) if(!(x))__builtin_unreachable()
 

gcc/testsuite/gcc.c-torture/execute/builtins/strnlen.c

@@ -1,6 +1,17 @@
 /* PR tree-optimization/81384 - built-in form of strnlen missing
    Test to verify that strnlen built-in expansion works correctly.  */
 
+/* FIXME: The -fprintf-return-value pass was previously calling the
+   evrp engine and setting global ranges.  These global ranges were
+   then being used by the RTL optimizers to optimize away strnlen
+   calls.
+
+   I've documented this here:
+
+   https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87813
+*/
+
+
 #define PTRDIFF_MAX __PTRDIFF_MAX__
 #define SIZE_MAX    __SIZE_MAX__
 #define NOIPA __attribute__ ((noipa))

gcc/testsuite/gcc.dg/Walloca-1.c

@@ -24,8 +24,7 @@ void foo1 (size_t len, size_t len2, size_t len3)
   char *s = alloca (123);
   useit (s);			// OK, constant argument to alloca
 
-  s = alloca (num);		// { dg-warning "large due to conversion" "" { target lp64 } }
-  // { dg-warning "unbounded use of 'alloca'" "" { target { ! lp64 } } .-1 }
+  s = alloca (num);		// { dg-warning "may be too large" }
   useit (s);
 
   s = alloca (30000);		/* { dg-warning "is too large" } */

gcc/testsuite/gcc.dg/Walloca-12.c

@@ -8,5 +8,5 @@ void g (unsigned int n)
 {
   if (n == 7)
     n = 11;
-  f (__builtin_alloca (n)); /* { dg-warning "unbounded use of 'alloca'" } */
+  f (__builtin_alloca (n)); /* { dg-warning "may be too large" } */
 }

gcc/testsuite/gcc.dg/Walloca-2.c

@@ -24,7 +24,7 @@ g2 (int n)
 {
   void *p;
   if (n < 2000)
-    p = __builtin_alloca (n); // { dg-warning "large due to conversion" }
+    p = __builtin_alloca (n); // { dg-warning "may be too large" }
   else
     p = __builtin_malloc (n);
   f (p);
@@ -36,9 +36,7 @@ g3 (int n)
   void *p;
   if (n > 0 && n < 3000)
     {
-      p = __builtin_alloca (n); // { dg-warning "'alloca' may be too large" "" { target lp64} }
-      // { dg-message "note:.*argument may be as large as 2999" "note" { target lp64 } .-1 }
-      // { dg-warning "unbounded use of 'alloca'" "" { target { ! lp64 } } .-2 }
+      p = __builtin_alloca (n); // { dg-warning "may be too large" }
     }
   else
     p = __builtin_malloc (n);

gcc/testsuite/gcc.dg/Walloca-3.c

@@ -13,7 +13,7 @@ g1 (__SIZE_TYPE__ n)
 {
   void *p;
   if (n < LIMIT)
-    p = __builtin_alloca (n); // { dg-warning "'alloca' bound is unknown" }
+    p = __builtin_alloca (n); // { dg-warning "may be too large" }
   else
     p = __builtin_malloc (n);
   f (p);
@@ -27,7 +27,7 @@ g2 (unsigned short n)
 {
   void *p;
   if (n < SHORT_LIMIT)
-    p = __builtin_alloca (n); // { dg-warning "'alloca' bound is unknown" }
+    p = __builtin_alloca (n); // { dg-warning "may be too large" }
   else
     p = __builtin_malloc (n);
   f (p);

gcc/testsuite/gcc.dg/Walloca-6.c

@@ -1,7 +1,6 @@
 /* { dg-do compile } */
 /* { dg-require-effective-target alloca } */
 /* { dg-options "-Walloca-larger-than=256 -O2" } */
-/* { dg-xfail-if "Currently broken but Andrew's work should fix this" { *-*-* } } */
 
 void f (void*);
 void g (__SIZE_TYPE__ n)

gcc/testsuite/gcc.dg/Wrestrict-20.c

@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -Wrestrict" } */
+
+unsigned n;
+
+void test_memcpy_warn (char *d)
+{
+  if (n > 10 && n < 20)
+    __builtin_memcpy (d, d + 2, n); /* { dg-warning "overlaps between" } */
+}

gcc/testsuite/gcc.dg/Wvla-larger-than-2.c

@@ -24,7 +24,6 @@ f2 (__SIZE_TYPE__ a)
     {
       // 11 * 4 bytes = 44: Not OK.
       uint32_t x[a]; // { dg-warning "array may be too large" }
-      // { dg-message "note:.*argument may be as large as 44" "note" { target *-*-* } .-1 }
       f0 (x);
     }
 }

gcc/testsuite/gcc.dg/gomp/for-24.c

@@ -11,7 +11,3 @@ void foo (void)
   for (i = 0; i < 37; ++i)
     bar(i);
 }
-
-/* { dg-final { scan-tree-dump-times "GOMP_parallel_loop_nonmonotonic_dynamic" 1 "ssa" } } */
-/* { dg-final { scan-tree-dump-times "GOMP_loop_nonmonotonic_dynamic_start" 0 "ssa" } } */
-/* { dg-final { scan-tree-dump-times "GOMP_loop_nonmonotonic_dynamic_next" 2 "ssa" } } */

gcc/testsuite/gcc.dg/old-style-asm-1.c

@@ -1,6 +1,6 @@
 /* PR inline-asm/8832 */
 /* { dg-do compile } */
-/* { dg-options "-O2 -dP" } */
+/* { dg-options "-O2 -dP -fdisable-tree-ethread -fdisable-tree-thread1 -fdisable-tree-thread2 -fdisable-tree-thread3 -fdisable-tree-thread4" } */
 
 /* Verify that GCC doesn't optimize
    old style asm instructions.  */

gcc/testsuite/gcc.dg/pr39874.c

@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-optimized" }  */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
 
 extern void func();
 
@@ -15,7 +15,7 @@ void test1(char *signature)
 
 void test2(char *signature)
 {
-  char ch = signature[0];
+  char ch = signature[1];
   if (ch == 15 || ch == 3)
   {
     if (ch > 14) func();

gcc/testsuite/gcc.dg/pr68217.c

@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fdisable-tree-evrp -fdisable-tree-rvrp -fdump-tree-vrp1" } */
 
 int foo (void)
 {

gcc/testsuite/gcc.dg/predict-9.c

@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-profile_estimate -fno-finite-loops" } */
+/* { dg-options "-O2 -fdisable-tree-ethread -fdisable-tree-rvrp -fdisable-tree-evrp -fdump-tree-profile_estimate -fno-finite-loops" } */
 
 extern int global;
 extern int global2;

gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-3.c

@@ -3,7 +3,7 @@
    that the sprintf return value (or value range) optimization is not
    performed for an unknown string.  */
 /* { dg-do compile } */
-/* { dg-options "-O2 -Wall -Werror -fdump-tree-optimized -fprintf-return-value" } */
+/* { dg-options "-O2 -Wall -Werror -fdump-tree-optimized -fprintf-return-value -fdisable-tree-thread1 -fdisable-tree-thread2 -fdisable-tree-thread3 -fdisable-tree-thread4" } */
 
 #define INT_MAX   __INT_MAX__
 #define INT_MIN   (-INT_MAX - 1)

gcc/testsuite/gcc.dg/tree-ssa/cunroll-9.c

@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-cunrolli-details -fdisable-tree-evrp" } */
+/* { dg-options "-O2 -fdump-tree-cunrolli-details -fdisable-tree-evrp -fdisable-tree-rvrp" } */
 void abort (void);
 int q (void);
 int a[10];

gcc/testsuite/gcc.dg/tree-ssa/evrp7.c

@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-evrp-details" } */
+/* { dg-options "-O2 -fdump-tree-evrp-details -fdisable-tree-rvrp" } */
 
 int test1(int i, int k)
 {

gcc/testsuite/gcc.dg/tree-ssa/evrp8.c

@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-evrp-details" } */
+/* { dg-options "-O2 -fdump-tree-evrp-details -fdisable-tree-rvrp" } */
 
 int foo(int i)
 {

gcc/testsuite/gcc.dg/tree-ssa/pr20318.c

@@ -1,5 +1,5 @@
 /* { dg-do compile { target { ! keeps_null_pointer_checks } } } */
-/* { dg-options "-O2 -fdump-tree-original -fdump-tree-vrp1 -fdelete-null-pointer-checks -fdisable-tree-evrp" } */
+/* { dg-options "-O2 -fdump-tree-original -fdump-tree-vrp1 -fdelete-null-pointer-checks -fdisable-tree-evrp -fdisable-tree-rvrp" } */
 
 extern int* f(int) __attribute__((returns_nonnull));
 extern void eliminate ();

gcc/testsuite/gcc.dg/tree-ssa/pr20702.c

@@ -4,7 +4,7 @@
    immediate successors of the basic block.  */
 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-dominator-opts -fdisable-tree-evrp -fdump-tree-vrp1-details -fdelete-null-pointer-checks" } */
+/* { dg-options "-O2 -fno-tree-dominator-opts -fdisable-tree-evrp -fdisable-tree-rvrp -fdump-tree-vrp1-details -fdelete-null-pointer-checks" } */
 
 extern void bar (int);
 

gcc/testsuite/gcc.dg/tree-ssa/pr21001.c

@@ -5,7 +5,7 @@
    range information out of the conditional.  */
 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-dominator-opts -fno-tree-fre -fdisable-tree-evrp -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fno-tree-dominator-opts -fno-tree-fre -fdisable-tree-ethread -fdisable-tree-thread1 -fdisable-tree-evrp -fdisable-tree-rvrp -fdump-tree-vrp1-details" } */
 
 int
 foo (int a)

gcc/testsuite/gcc.dg/tree-ssa/pr21086.c

@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1 -fdump-tree-dce2 -fdelete-null-pointer-checks" } */
+/* { dg-options "-O2 -fdisable-tree-rvrp -fdisable-tree-evrp -fdump-tree-vrp1 -fdump-tree-dce2 -fdelete-null-pointer-checks" } */
 
 int
 foo (int *p)

gcc/testsuite/gcc.dg/tree-ssa/pr21090.c

@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1 -fdelete-null-pointer-checks" } */
+/* { dg-options "-O2 -fdisable-tree-rvrp -fdisable-tree-evrp -fdump-tree-vrp1 -fdelete-null-pointer-checks" } */
 
 int g, h;
 

gcc/testsuite/gcc.dg/tree-ssa/pr21294.c

@@ -4,7 +4,7 @@
    allows us to eliminate the second "if" statement.  */
 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-dominator-opts -fdisable-tree-evrp -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fno-tree-dominator-opts -fdisable-tree-rvrp -fdisable-tree-evrp -fdump-tree-vrp1-details" } */
 
 struct f {
   int i;

gcc/testsuite/gcc.dg/tree-ssa/pr21458-2.c

@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-evrp-details" } */
+/* { dg-options "-O2 -fdisable-tree-rvrp -fdump-tree-evrp-details" } */
 
 extern void g (void);
 extern void bar (int);

gcc/testsuite/gcc.dg/tree-ssa/pr21458.c

@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fdisable-tree-rvrp -fdisable-tree-evrp -fdump-tree-vrp1" } */
 
 extern void g (void);
 extern void bar (int);

gcc/testsuite/gcc.dg/tree-ssa/pr21559.c

@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-evrp-details -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fdump-tree-evrp-details -fdump-tree-vrp1-details -fdisable-tree-rvrp" } */
 
 static int blocksize = 4096;
 

gcc/testsuite/gcc.dg/tree-ssa/pr21563.c

@@ -2,7 +2,7 @@
    Make sure VRP folds the second "if" statement.  */
 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-dominator-opts -fdisable-tree-evrp -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fno-tree-dominator-opts -fdisable-tree-ethread -fdisable-tree-thread1 -fdisable-tree-evrp -fdisable-tree-rvrp -fdump-tree-vrp1-details" } */
 
 int
 foo (int a)

gcc/testsuite/gcc.dg/tree-ssa/pr23744.c

@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-ccp -fdisable-tree-evrp -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fno-tree-ccp -fdisable-tree-rvrp -fdisable-tree-evrp -fdump-tree-vrp1" } */
 
 void h (void);
 

gcc/testsuite/gcc.dg/tree-ssa/pr25382.c

@@ -3,7 +3,7 @@
    Check that VRP now gets ranges from BIT_AND_EXPRs.  */
 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fno-tree-ccp -fdisable-tree-evrp -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fno-tree-ccp -fdisable-tree-rvrp -fdisable-tree-evrp -fdump-tree-vrp1" } */
 
 int
 foo (int a)

gcc/testsuite/gcc.dg/tree-ssa/pr49039.c

@@ -1,6 +1,6 @@
 /* PR tree-optimization/49039 */
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fdisable-tree-ethread -fdisable-tree-thread1 -fdisable-tree-thread2 -fdisable-tree-thread3 -fdisable-tree-thread4    -fdisable-tree-rvrp -fdisable-tree-evrp -fdump-tree-vrp1" } */
 
 extern void bar (void);
 

gcc/testsuite/gcc.dg/tree-ssa/pr58480.c

@@ -1,5 +1,5 @@
 /* { dg-do compile { target { ! keeps_null_pointer_checks } } } */
-/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1 -fdelete-null-pointer-checks" } */
+/* { dg-options "-O2 -fdisable-tree-rvrp -fdisable-tree-evrp -fdump-tree-vrp1 -fdelete-null-pointer-checks" } */
 
 extern void eliminate (void);
 extern void* f1 (void *a, void *b) __attribute__((nonnull));

gcc/testsuite/gcc.dg/tree-ssa/pr61839_1.c

@@ -1,6 +1,6 @@
 /* PR tree-optimization/61839.  */
 /* { dg-do run } */
-/* { dg-options "-O2 -fdump-tree-vrp1 -fdisable-tree-evrp -fdump-tree-optimized" } */
+/* { dg-options "-O2 -fdisable-tree-thread1 -fdump-tree-vrp1 -fdisable-tree-evrp -fdump-tree-optimized -fdisable-tree-rvrp" } */
 /* { dg-require-effective-target int32plus } */
 
 __attribute__ ((noinline))

gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c

@@ -1,6 +1,6 @@
 /* PR tree-optimization/61839.  */
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-evrp" } */
+/* { dg-options "-O2 -fdisable-tree-rvrp -fdump-tree-evrp" } */
 /* { dg-require-effective-target int32plus } */
 
 __attribute__ ((noinline))

gcc/testsuite/gcc.dg/tree-ssa/pr61839_3.c

@@ -1,6 +1,6 @@
 /* PR tree-optimization/61839.  */
 /* { dg-do run } */
-/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-optimized" } */
+/* { dg-options "-O2 -fdisable-tree-thread1 -fdump-tree-vrp1 -fdump-tree-optimized" } */
 
 __attribute__ ((noinline))
 int foo (int a, unsigned b)

gcc/testsuite/gcc.dg/tree-ssa/pr61839_4.c

@@ -1,6 +1,6 @@
 /* PR tree-optimization/61839.  */
 /* { dg-do run } */
-/* { dg-options "-O2 -fdump-tree-vrp1 -fdisable-tree-evrp -fdump-tree-optimized" } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -fdisable-tree-evrp -fdump-tree-optimized -fdisable-tree-rvrp" } */
 /* { dg-require-effective-target int32plus } */
 
 __attribute__ ((noinline))

gcc/testsuite/gcc.dg/tree-ssa/pr64130.c

@@ -1,6 +1,6 @@
 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-evrp" } */
+/* { dg-options "-O2 -fdump-tree-evrp -fdisable-tree-rvrp" } */
 
 __extension__ typedef __UINT32_TYPE__ uint32_t;
 

gcc/testsuite/gcc.dg/tree-ssa/pr68431.c

@@ -1,5 +1,5 @@
 /* PR tree-optimization/68431 */
-/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1-details" } */
+/* { dg-options "-O2 -fdisable-tree-evrp -fdisable-tree-rvrp -fdump-tree-vrp1-details" } */
 
 unsigned int x = 1;
 int

gcc/testsuite/gcc.dg/tree-ssa/pr88367.c

@@ -1,6 +1,6 @@
 /* PR c/88367 */
 /* { dg-do compile } */
-/* { dg-options "-fno-delete-null-pointer-checks -O2 -fdump-tree-optimized -fno-wrapv-pointer" } */
+/* { dg-options "-fno-delete-null-pointer-checks -O2 -fdump-tree-optimized -fno-wrapv-pointer -fdisable-tree-rvrp" } */
 /* { dg-final { scan-tree-dump-not "link_error \\(\\);" "optimized" } } */
 /* { dg-final { scan-tree-dump-times "bar \\(\\);" 2 "optimized" } } */
 

gcc/testsuite/gcc.dg/tree-ssa/rvrp-abs-1.c

@@ -0,0 +1,33 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-forwprop -fdisable-tree-ethread -fno-tree-fre -fdump-tree-rvrp" } */
+
+extern void abort ();
+extern void keep ();
+
+int g (int b) {
+  if (b < -23 || b > 64)
+    {
+      // b = [-MIN, -24][65, +MAX]
+      b = b > 0 ? b : -b;
+      // b = [24, MAX]
+      if (b == -20 || b == 20)
+        abort ();
+      if (b < 24)
+        abort ();
+      if (b < 25)
+        keep();
+    }
+  else
+    {
+      // b == [-23, 64]
+      b = b > 0 ? b : -b;
+      // b == [0, 64]
+      if (b < 0 || b > 64)
+        abort ();
+      if (b >= 0 && b < 65)
+        keep ();
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "abort" 0 "rvrp" } } */
+/* { dg-final { scan-tree-dump-times "keep" 2 "rvrp" } } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp-abs-2.c

@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-fwrapv -O2 -fno-tree-forwprop -fdisable-tree-ethread -fno-tree-fre -fdump-tree-rvrp" } */
+
+/* With -fwrapv, ABS_EXPR(-MIN) is undefined.  Test that we're not
+   making any assumptions on the absolute value of -MIN.  */
+
+extern void do_not_abort ();
+extern void keep ();
+
+int g (int b) {
+  if (b < -23 || b > 64)
+    {
+      // b = [-MIN, -24][65, +MAX]
+      b = b > 0 ? b : -b;
+      // b = [24, MAX]
+      if (b == -20 || b == 20)
+        do_not_abort ();
+      if (b < 24)
+        do_not_abort ();
+      if (b < 25)
+        keep();
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "do_not_abort" 2 "rvrp" } } */
+/* { dg-final { scan-tree-dump-times "keep" 1 "rvrp" } } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp-abs-3.c

@@ -0,0 +1,7 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-rvrp" } */
+
+#define ADD_NW(A,B) (__extension__({ __typeof(A+B) R; if(__builtin_add_overflow(A,B,&R)) __builtin_unreachable(); R ;}))
+_Bool a_b2(unsigned A,  unsigned B) { return ADD_NW(A,B) >= B; }
+
+/* { dg-final { scan-tree-dump "return 1;" "rvrp" } } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp-abs-4.c

@@ -0,0 +1,40 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-rvrp" } */
+
+void
+foo (distance, i, j)
+     int distance[13][13];
+     int i, j;
+{
+ if (distance[i][j] < 0)
+   distance[i][0] = ((distance[i][j]) < 0 ? -(distance[i][j])  : (distance[i][j]));
+}
+
+void
+foo2 (distance, i, j)
+     int distance[13][13];
+     int i, j;
+{
+ if (distance[i][j] <= 0)
+   distance[i][0] = ((distance[i][j]) < 0 ? -(distance[i][j])  : (distance[i][j]));
+}
+
+void
+foo3 (distance, i, j)
+     int distance[13][13];
+     int i, j;
+{
+ if (distance[i][j] > 0)
+   distance[i][0] = ((distance[i][j]) < 0 ? -(distance[i][j])  : (distance[i][j]));
+}
+
+void
+foo4 (distance, i, j)
+     double distance[13][13];
+     int i, j;
+{
+ if (distance[i][j] >= 0)
+   distance[i][0] = ((distance[i][j]) < 0 ? -(distance[i][j])  : (distance[i][j]));
+}
+
+/* { dg-final { scan-tree-dump-times "ABS_EXPR " 0 "rvrp"} } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp-and-1.c

@@ -0,0 +1,44 @@
+/* { dg-do run } */
+/* { dg-options "-O2 " } */
+
+extern void abort(void);
+
+/* Distilled from fedora package veusz where we were not combining bitwise
+ * AND's properly.  
+ * The test adds lots fo conditions so that if the range is not accurate, 
+ * it will shortcut the result and not get to the return 1 checks.  */
+
+int
+foo(int a, int i)
+{
+  if (i == 32 || i == 64 || i == 128)
+    {
+      int r = a & i;
+      if (r < 32 || r > 128)
+        return 0;
+      if (r >32 && r < 64)
+        return 0;
+      if (r > 64 && r < 128)
+        return 0;
+      if (r == 32)
+        return 1;
+      if (r == 64)
+        return 1;
+      if (r == 128)
+        return 1;
+    }
+  return 0;
+}
+
+
+int main()
+{
+  int x;
+  int count = 0;
+  for (x = 0; x < 255; x++)
+    if (foo (255, x))
+      count++;
+
+  if (count != 3)
+    abort();
+}

gcc/testsuite/gcc.dg/tree-ssa/rvrp-logic-1.c

@@ -0,0 +1,252 @@
+/* Extracted from fedora build for compile time issues with ranger 
+   taking a long time to evalaute deeply nested logical expressions.  */
+ 
+/*  { dg-do compile } */
+/*  { dg-options "-O2" } */
+
+
+typedef struct
+{
+  unsigned value;
+} aarch64_sys_reg;
+
+typedef unsigned long long aarch64_feature_set;
+
+int
+aarch64_sys_reg_supported_p (const aarch64_feature_set features,
+        const aarch64_sys_reg *reg)
+{
+
+
+  if (reg->value == ((((3) << 19) | (((0)) << 16) | ((4) << 12) | (((2)) << 8) | (((3)) << 5)) >> 5)
+      && !((~(features) & (0x00200000)) == 0))
+    return 0;
+
+
+  if ((reg->value == ((((3) << 19) | ((3) << 16) | ((13) << 12) | ((0) << 8) | ((7) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((13) << 12) | ((0) << 8) | ((7) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((13) << 12) | ((0) << 8) | ((7) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((6) << 16) | ((13) << 12) | ((0) << 8) | ((7) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((13) << 12) | ((0) << 8) | ((7) << 5)) >> 5))
+      && !((~(features) & (0x200000000000ULL)) == 0))
+      return 0;
+
+
+  if (reg->value == ((((3) << 19) | ((0) << 16) | ((0) << 12) | ((3) << 8) | ((4) << 5)) >> 5)
+      && !((~(features) & (0x400000000000ULL)) == 0))
+    return 0;
+
+
+  if (reg->value == ((((3) << 19) | (((3)) << 16) | ((4) << 12) | (((2)) << 8) | (((6)) << 5)) >> 5)
+      && !((~(features) & (0x800000000000ULL)) == 0))
+    return 0;
+
+
+  if ((reg->value == ((((3) << 19) | ((4) << 16) | ((2) << 12) | ((0) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((13) << 12) | ((0) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((14) << 12) | ((3) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((14) << 12) | ((3) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((14) << 12) | ((3) << 8) | ((2) << 5)) >> 5))
+      && !((~(features) & (0x01000000)) == 0))
+      return 0;
+
+
+  if ((reg->value == ((((3) << 19) | (((5)) << 16) | ((4) << 12) | (((0)) << 8) | (((0)) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | (((5)) << 16) | ((4) << 12) | (((0)) << 8) | (((1)) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((1) << 12) | ((0) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((1) << 12) | ((0) << 8) | ((2) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((2) << 12) | ((0) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((2) << 12) | ((0) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((2) << 12) | ((0) << 8) | ((2) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((5) << 12) | ((1) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((5) << 12) | ((1) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((5) << 12) | ((2) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((6) << 12) | ((0) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((10) << 12) | ((2) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((10) << 12) | ((3) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((12) << 12) | ((0) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((13) << 12) | ((0) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((14) << 12) | ((1) << 8) | ((0) << 5)) >> 5))
+      && !((~(features) & (0x01000000)) == 0))
+    return 0;
+
+
+  if ((reg->value == ((((3) << 19) | ((5) << 16) | ((14) << 12) | ((2) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((14) << 12) | ((2) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((14) << 12) | ((2) << 8) | ((2) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((14) << 12) | ((3) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((14) << 12) | ((3) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((14) << 12) | ((3) << 8) | ((2) << 5)) >> 5))
+      && !((~(features) & (0x01000000)) == 0))
+    return 0;
+
+
+
+
+  if (reg->value == ((((3) << 19) | ((0) << 16) | ((0) << 12) | ((7) << 8) | ((2) << 5)) >> 5)
+      && !((~(features) & (0x00000020)) == 0))
+    return 0;
+
+
+  if (reg->value == ((((3) << 19) | (((0)) << 16) | ((4) << 12) | (((2)) << 8) | (((4)) << 5)) >> 5)
+      && !((~(features) & (0x00000020)) == 0))
+    return 0;
+
+
+
+
+
+  if ((reg->value == ((((3) << 19) | ((0) << 16) | ((5) << 12) | ((3) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((5) << 12) | ((3) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((5) << 12) | ((3) << 8) | ((2) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((5) << 12) | ((3) << 8) | ((3) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((5) << 12) | ((4) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((5) << 12) | ((4) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((5) << 12) | ((4) << 8) | ((2) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((5) << 12) | ((4) << 8) | ((3) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((5) << 12) | ((5) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((5) << 12) | ((5) << 8) | ((1) << 5)) >> 5))
+      && !((~(features) & (0x04000000)) == 0))
+    return 0;
+
+
+  if ((reg->value == ((((3) << 19) | ((4) << 16) | ((5) << 12) | ((2) << 8) | ((3) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((12) << 12) | ((1) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((12) << 12) | ((1) << 8) | ((1) << 5)) >> 5))
+      && !((~(features) & (0x04000000)) == 0))
+    return 0;
+
+
+  if ((reg->value == ((((3) << 19) | ((0) << 16) | ((9) << 12) | ((10) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((9) << 12) | ((10) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((9) << 12) | ((10) << 8) | ((3) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((9) << 12) | ((10) << 8) | ((7) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((9) << 12) | ((9) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((9) << 12) | ((9) << 8) | ((2) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((9) << 12) | ((9) << 8) | ((3) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((9) << 12) | ((9) << 8) | ((4) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((9) << 12) | ((9) << 8) | ((5) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((9) << 12) | ((9) << 8) | ((6) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((9) << 12) | ((9) << 8) | ((7) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((9) << 12) | ((9) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((9) << 12) | ((9) << 8) | ((0) << 5)) >> 5))
+      && !((~(features) & (0x08000000)) == 0))
+    return 0;
+
+
+  if ((reg->value == ((((3) << 19) | ((0) << 16) | ((2) << 12) | ((1) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((2) << 12) | ((1) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((2) << 12) | ((1) << 8) | ((2) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((2) << 12) | ((1) << 8) | ((3) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((2) << 12) | ((2) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((2) << 12) | ((2) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((2) << 12) | ((2) << 8) | ((2) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((2) << 12) | ((2) << 8) | ((3) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((2) << 12) | ((3) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((2) << 12) | ((3) << 8) | ((1) << 5)) >> 5))
+      && !((~(features) & (0x00000040)) == 0))
+    return 0;
+
+
+  if ((reg->value == ((((3) << 19) | ((0) << 16) | ((0) << 12) | ((4) << 8) | ((4) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((1) << 12) | ((2) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((1) << 12) | ((2) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((6) << 16) | ((1) << 12) | ((2) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((1) << 12) | ((2) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((0) << 12) | ((0) << 8) | ((7) << 5)) >> 5))
+      && !((~(features) & (0x10000000)) == 0))
+    return 0;
+
+
+
+
+  if (reg->value == ((((3) << 19) | (((3)) << 16) | ((4) << 12) | (((2)) << 8) | (((5)) << 5)) >> 5)
+      && !((~(features) & (0x000000800ULL)) == 0))
+    return 0;
+
+
+  if ((reg->value == ((((3) << 19) | ((4) << 16) | ((2) << 12) | ((6) << 8) | ((2) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((2) << 12) | ((6) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((14) << 12) | ((4) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((14) << 12) | ((4) << 8) | ((2) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((14) << 12) | ((4) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((14) << 12) | ((5) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((14) << 12) | ((5) << 8) | ((2) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((14) << 12) | ((5) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((1) << 12) | ((3) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((2) << 12) | ((2) << 8) | ((0) << 5)) >> 5))
+      && !((~(features) & (0x000000800ULL)) == 0))
+    return 0;
+
+
+  if ((reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((1)) << 8) | (((0)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((1)) << 8) | (((1)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((1)) << 8) | (((2)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((1)) << 8) | (((3)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((1)) << 8) | (((5)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((1)) << 8) | (((7)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((4)) << 8) | (((0)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((4)) << 8) | (((4)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((1)) << 8) | (((1)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((1)) << 8) | (((5)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((1)) << 8) | (((6)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((6)) << 16) | (((8)) << 12) | (((1)) << 8) | (((1)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((6)) << 16) | (((8)) << 12) | (((1)) << 8) | (((5)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((1)) << 8) | (((0)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((1)) << 8) | (((4)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((6)) << 16) | (((8)) << 12) | (((1)) << 8) | (((0)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((6)) << 8) | (((1)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((6)) << 8) | (((3)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((6)) << 8) | (((5)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((6)) << 8) | (((7)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((2)) << 8) | (((1)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((2)) << 8) | (((3)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((2)) << 8) | (((5)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((2)) << 8) | (((7)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((5)) << 8) | (((1)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((5)) << 8) | (((3)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((5)) << 8) | (((5)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((0)) << 16) | (((8)) << 12) | (((5)) << 8) | (((7)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((0)) << 8) | (((2)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((0)) << 8) | (((6)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((4)) << 8) | (((2)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((4)) << 8) | (((6)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((4)) << 8) | (((3)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((4)) << 8) | (((7)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((6)) << 8) | (((1)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((6)) << 8) | (((5)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((2)) << 8) | (((1)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((2)) << 8) | (((5)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((5)) << 8) | (((1)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((4)) << 16) | (((8)) << 12) | (((5)) << 8) | (((5)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((6)) << 16) | (((8)) << 12) | (((6)) << 8) | (((1)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((6)) << 16) | (((8)) << 12) | (((6)) << 8) | (((5)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((6)) << 16) | (((8)) << 12) | (((2)) << 8) | (((1)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((6)) << 16) | (((8)) << 12) | (((2)) << 8) | (((5)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((6)) << 16) | (((8)) << 12) | (((5)) << 8) | (((1)) << 5)) >> 5)
+       || reg->value == ((((1) << 19) | (((6)) << 16) | (((8)) << 12) | (((5)) << 8) | (((5)) << 5)) >> 5))
+      && !((~(features) & (0x000000800ULL)) == 0))
+    return 0;
+
+
+
+  if ((reg->value == ((((3) << 19) | ((3) << 16) | ((2) << 12) | ((4) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((3) << 16) | ((2) << 12) | ((4) << 8) | ((1) << 5)) >> 5))
+      && !(((~(features) & (0x80000000000ULL)) == 0)
+    && ((~(features) & (0x2000000000ULL)) == 0)))
+    return 0;
+
+
+  if ((reg->value == ((((3) << 19) | ((3) << 16) | ((4) << 12) | ((2) << 8) | ((7) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((6) << 12) | ((6) << 8) | ((1) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((6) << 12) | ((5) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((4) << 16) | ((6) << 12) | ((5) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((6) << 16) | ((6) << 12) | ((6) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((5) << 16) | ((6) << 12) | ((6) << 8) | ((0) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((1) << 12) | ((0) << 8) | ((5) << 5)) >> 5)
+       || reg->value == ((((3) << 19) | ((0) << 16) | ((1) << 12) | ((0) << 8) | ((6) << 5)) >> 5))
+      && !(((~(features) & (0x1000000000000ULL)) == 0)))
+    return 0;
+
+  return 1;
+}

gcc/testsuite/gcc.dg/tree-ssa/rvrp-minmax-1.c

@@ -0,0 +1,27 @@
+/* rvrp min-max test adapted from PR tree-optimization/49039 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdisable-tree-evrp -fdisable-tree-ethread -fdump-tree-rvrp" } */
+
+extern void bar (void);
+
+void
+foo (unsigned int x, unsigned int y)
+{
+  unsigned int minv, maxv;
+  if (x >= 3 && x <= 6)
+    return;
+  if (y >= 5 && y <= 8)
+    return;
+  minv = x < y ? x : y;
+  maxv = x > y ? x : y;
+  if (minv == 5)
+    bar ();
+  if (minv == 6)
+    bar ();
+  if (maxv == 5)
+    bar ();
+  if (maxv == 6)
+    bar ();
+}
+
+/* { dg-final { scan-tree-dump-times "Branch rewritten" 4 "rvrp"} } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp-nonnull-ret.c

@@ -0,0 +1,17 @@
+/* { dg-do compile { target { ! keeps_null_pointer_checks } } } */
+/* { dg-options "-O2 -fdump-tree-original -fdump-tree-rvrp -fdelete-null-pointer-checks -fdisable-tree-evrp " } */
+
+extern int* f(int) __attribute__((returns_nonnull));
+extern void eliminate ();
+void g () {
+  if (f (2) == 0)
+    eliminate ();
+}
+void h () {
+  int *p = f (2);
+  if (p == 0)
+    eliminate ();
+}
+
+/* { dg-final { scan-tree-dump-times "== 0" 1 "original" } } */
+/* { dg-final { scan-tree-dump-times "Branch rewritten" 1 "rvrp" } } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp01.c

@@ -0,0 +1,16 @@
+/* Copy of pr21001.c for testing VRP adjusted for RVRP
+ *
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-fre -fdisable-tree-ethread -fdump-tree-rvrp-details" } */
+
+int
+foo (int a)
+{
+  int b = a != 0;
+  if (b)
+    if (a != 0)
+      return 1;
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Branch rewritten" 1 "rvrp"} } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp02.c

@@ -0,0 +1,16 @@
+/* Copy of pr21563 adjusted for rvrp.
+   Make sure VRP folds the second "if" statement.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-dominator-opts -fdisable-tree-ethread -fdisable-tree-thread1 -fdisable-tree-evrp -fdump-tree-rvrp-details" } */
+
+int
+foo (int a)
+{
+  if (a > 1)
+    if (a == 0)
+      return 1;
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Branch rewritten" 1 "rvrp"} } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp03.c

@@ -0,0 +1,19 @@
+/* Copied from pr25382 and adjusted for rvrp.
+   PR tree-optimization/25382
+   VRP used to ignore BIT_AND_EXPRs for the purpose of distilling ranges.
+   Check that VRP now gets ranges from BIT_AND_EXPRs.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-ccp -fdisable-tree-evrp -fdump-tree-rvrp" } */
+
+int
+foo (int a)
+{
+  int b = a & 0xff;
+  if (b > 300)
+    return 2;
+  else
+    return 1;
+}
+
+/* { dg-final { scan-tree-dump-times "Branch rewritten" 1 "rvrp" } } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp04.c

@@ -0,0 +1,17 @@
+/* copied from pr68431.c and adjusted for rvrp.
+   PR tree-optimization/68431 */
+/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-rvrp-details" } */
+
+unsigned int x = 1;
+int
+main (void)
+{
+  long long int a = -2LL;
+  int t = 1 <= (a / x);
+  if (t != 0)
+    __builtin_abort ();
+
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Branch rewritten" 1 "rvrp" } } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp05.c

@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-rvrp-details" } */
+
+int test1(int i, int k)
+{
+  if (i > 0 && i <= 5 && k >= 10 && k < 42)
+    {
+      int j = i + 1 + k;
+      if (j == 10)
+        return 0;
+    }
+  return 1;
+}
+
+/* { dg-final { scan-tree-dump "Branch rewritten" "rvrp" } } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp06.c

@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-rvrp" } */
+
+void f(unsigned);
+
+void
+f4 (unsigned a, unsigned b)
+{
+  if (a <= 5 && b <= 2)
+    {
+      int x = a * b * 4;
+      if (x > 40)
+        f (a);
+      if (x >= 0)
+        f (b);
+      else
+        f (a + b);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "Branch rewritten" 2 "rvrp" } } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp07.c

@@ -0,0 +1,28 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-rvrp-details" } */
+
+extern void abort ();
+extern void drink ();
+
+void beer (int x)
+{
+  if (x >= 12 && x <= 15)
+    {
+      // must be true
+      if (x & 0x4)
+	{
+	  drink ();
+	}
+      else
+        abort();
+     return;
+    }
+  abort();
+}
+
+int main()
+{
+  beer (3);
+}
+
+/* { dg-final { scan-tree-dump "Branch rewritten" "rvrp" } } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp08.c

@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdisable-tree-evrp -fdisable-tree-ethread -fdump-tree-rvrp-details" } */
+
+extern int global;
+extern int global2;
+extern int global3;
+
+void foo (int base)
+{
+  unsigned i;
+
+  // rvrp should be able to remove the (i > 123) comparison
+  for (i = base; i < 10; i++)
+    if (i > 123)
+      return;
+}
+
+/* { dg-final { scan-tree-dump-times "Branch rewritten" 1 "rvrp"} } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp09.c

@@ -0,0 +1,33 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-rvrp-details -fdisable-tree-ethread -fdisable-tree-forwprop1 -fdisable-tree-ccp1  -fdisable-tree-fre1 " } */
+
+/* NOTE: This stresses irange_adjust_bit_and_mask, which is currently
+   disabled until we can contribute it upstream.  */
+
+extern void exit (int);
+extern void abort (void);
+
+
+void
+signed_foo (char x)
+{
+
+  char a = x & 0x00;    
+  if (a > 0)   /*  This should fold  */
+    abort();
+
+  char b = x & 0x0f;
+  if (b > 0x0f)
+    abort ();
+
+  char c = x & 0x3c;
+  if (c > 0x3c)
+    abort ();
+
+  char d = x & 0xf0;
+  if (d > 0)
+     if (d < 16)
+       abort();
+}
+
+/* { dg-final { scan-tree-dump-times "Branch rewritten" 4 "rvrp"} } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp10.c

@@ -0,0 +1,8 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdisable-tree-ethread -fdisable-tree-thread1 -fdump-tree-rvrp -fno-tree-fre" } */
+
+/* This is from PR14052.  */
+
+int f2(int x) { return x == 1 || x == 3 || x == 1; }
+
+/* { dg-final { scan-tree-dump "Branch rewritten" "rvrp" } } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp11.c

@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-rvrp" } */
+extern void abort(void);
+
+void
+foo (int x)
+{
+ int y;
+ if (x > -4 && x < 0)
+   {
+     y = x * x;
+     if (y < 1 || y > 9)
+       abort();
+   }
+}
+
+/* { dg-final { scan-tree-dump "Branch rewritten" "rvrp"} } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp12.c

@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-ccp -fdisable-tree-ethread -fdump-tree-rvrp" } */
+
+extern void vrp_keep (void);
+extern void vrp_kill (void);
+
+void
+f2 (int s, int b)
+{
+  if (s > 4)
+    s = 4;
+  if (s < -16)
+    s = -16;
+  /* s in [-16, 4].   */
+  b = (b & 1) + 1;
+  /* b in range [1, 2].  */
+  b = s << b;
+  /* b in range [-64, 16].  */
+  if (b == -2)
+    vrp_keep ();
+  if (b <= -65)
+    vrp_kill ();
+  if (b >= 17)
+    vrp_kill ();
+}
+
+/* { dg-final { scan-tree-dump-times "vrp_keep \\(" 1 "rvrp"} } */
+/* { dg-final { scan-tree-dump-times "vrp_kill \\(" 0 "rvrp"} } */
+/* { dg-final { scan-tree-dump-times "Branch rewritten" 2 "rvrp"} } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp13.c

@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-rvrp -fdelete-null-pointer-checks" } */
+
+int g, h;
+
+int
+foo (int a)
+{
+  int *p;
+
+  if (a)
+    p = &g;
+  else
+    p = &h;
+
+  if (p != 0)
+    return 1;
+  else
+    return 0;
+}
+
+/* { dg-final { scan-tree-dump "Branch rewritten"  "rvrp" { target { ! keeps_null_pointer_checks } } } } */
+

gcc/testsuite/gcc.dg/tree-ssa/rvrp14.c

@@ -0,0 +1,21 @@
+/* adapted from PR tree-optimization/21294
+   In this testcase, noticing that &p->i cannot be null
+   allows us to eliminate the second "if" statement.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-dominator-opts -fdump-tree-rvrp" } */
+
+struct f {
+  int i;
+};
+
+int
+foo (struct f *p)
+{
+  if (p != 0)
+    if (&p->i != 0)
+      return 123;
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "Branch rewritten"  "rvrp"} } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp15.c

@@ -0,0 +1,28 @@
+/* RVRP test Adapted from PR tree-optimization/20702 to test pointer dereference.,
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-dominator-opts -fdisable-tree-evrp -fdump-tree-rvrp-details -fdelete-null-pointer-checks" } */
+
+extern void bar (int);
+
+int
+foo (int *p, int b)
+{
+  int a;
+
+  if (b)
+    bar (123);
+  else
+    bar (321);
+
+  a = *p;
+  if (p == 0)
+    return 0;
+
+  return a;
+}
+
+/* Target disabling -fdelete-null-pointer-checks should not fold checks */
+/* { dg-final { scan-tree-dump-times "Branch rewritten" 1 "rvrp" { target { ! keeps_null_pointer_checks } } } } */
+/* { dg-final { scan-tree-dump-times "Branch rewritten" 0 "rvrp" { target {   keeps_null_pointer_checks } } } } */
+

gcc/testsuite/gcc.dg/tree-ssa/rvrp16.c

@@ -0,0 +1,24 @@
+/* { dg-do compile { target { ! keeps_null_pointer_checks } } } */
+/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-rvrp -fdelete-null-pointer-checks" } */
+
+extern void eliminate (void);
+extern void keep(void);
+extern void* f1 (void *a, void *b) __attribute__((nonnull));
+extern void* f2 (void *a, void *b) __attribute__((nonnull(2)));
+void g1 (void*p, void*q){
+  f1 (q, p);
+  if (p == 0)
+    eliminate ();
+  if (q == 0)
+    eliminate ();
+}
+void g2 (void*p, void*q){
+  f2 (q, p);
+  if (p == 0)
+    eliminate ();
+  if (q == 0)
+    keep ();
+}
+
+/* { dg-final { scan-tree-dump-times "Branch rewritten" 3 "rvrp" } } */
+/* { dg-final { scan-tree-dump-times "keep" 1 "rvrp" } } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp17.c

@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-rvrp-details" } */
+
+/* Adapted from cunroll-9.c.  */
+
+void abort (void);
+int q (void);
+int a[10];
+int b[11];
+int
+t (int n)
+{
+  int i;
+  int sum = 0;
+  for (i = 0; i < n; i++)
+    {
+      if (i > 1000)
+	abort ();
+      if (q ())
+	sum += a[i];
+      else
+	sum += b[i];
+    }
+  return sum;
+}
+
+/* { dg-final { scan-tree-dump-times "Branch rewritten to" 1 "rvrp" } } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp18.c

@@ -0,0 +1,30 @@
+/* Rematerialize thru casts if the range fits the LHS type. */
+/* { dg-do compile } */
+/* { dg-options "-O2  -fdump-tree-rvrp" } */
+
+extern void kill(int i);
+extern void keep(int i);
+
+void
+foo (int i)
+{
+  int b = i + 10;
+  if (i >= 10 && i <= 100)
+    {
+      /* i has a range of [10, 100]  */
+      char c = (char) b;
+      if (c < 30)
+	{
+	  /* If we wind back thru the cast with the range of c being [10,29]
+	   * from the branch, and recognize that the range of b recalcualted 
+	   * iuses i which fits within * a cast to c, then we can use the range
+	   * for 'c' with 'b' as well and RVRP should be able to kill the call.
+	   * */
+	  if (b > 29)
+	    kill (b);
+	}
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "kill \\(" 0 "rvrp"} } */
+

gcc/testsuite/gcc.dg/tree-ssa/rvrp19.c

@@ -0,0 +1,25 @@
+/* Make sure back edges initialize the range on entry cache properly
+ * for "localized data".  This involves no loop analysis.*/
+/* { dg-do compile } */
+/* { dg-options "-O2  -fdump-tree-rvrp" } */
+
+extern void kill (int k);
+
+int main ()
+{ 
+  unsigned b = 0;
+  int c, d = -8;
+  /* The backedge to this loop provides b < 2 info. */
+  for (; b < 2; b++)
+    {
+      for (c = 1; c; c--)
+	d++;
+    }
+  /* Upon loop exit, we ought to know this.  */
+  if (b > 2)
+    kill (b);
+
+  return 0;
+}
+/* { dg-final { scan-tree-dump-times "kill \\(" 0 "rvrp"} } */
+

gcc/testsuite/gcc.dg/tree-ssa/rvrp20.c

@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Adapted from pr39874.c, but reading from signature[0] in both
+   functions.  The ranger should be able to set things up for ICF to
+   fold the second function entirely.  */
+
+extern void func();
+
+void test1(char *signature)
+{
+  char ch = signature[0];
+  if (ch == 15 || ch == 3)
+  {
+    if (ch == 15) func();
+  }
+}
+
+
+void test2(char *signature)
+{
+  char ch = signature[0];
+  if (ch == 15 || ch == 3)
+  {
+    if (ch > 14) func();
+  }
+}
+
+/* { dg-final { scan-tree-dump-times " == 15" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "test1 \\(signature.*tail call" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-not " == 3" "optimized" } } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp21.c

@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -fno-tree-vrp -fdisable-tree-evrp -ftree-rvrp -fdump-tree-rvrp" } */
+
+signed char arr[240];
+void foo (void)
+{
+
+  unsigned short i, length = 200;
+
+  for (i = 1; (int)i < (length - 1); i++)
+    arr[i] = -1;
+}
+
+/* i_12 = i_6 + 1... i_6 should be [1, 198] on the back edge,  */
+/* i_12 should be [2, 199].				   */
+/* { dg-final { scan-tree-dump "\\\[2, 199\\\]" "rvrp" } } */

gcc/testsuite/gcc.dg/tree-ssa/rvrp22.c

@@ -0,0 +1,43 @@
+/* See backwards thru casts if the range fits the LHS type. */
+/* { dg-do compile } */
+/* { dg-options "-O2  -fdump-tree-rvrp" } */
+
+extern void kill(int i);
+extern void keep(int i);
+
+void
+foo (int i)
+{
+  if (i >= 10)
+    {
+      if (i <= 100)
+	{
+	  /* i has a range of [10, 100]  */
+	  char c = (char) i;
+	  if (c < 30)
+	    {
+	      /* If we wind back thru the cast with the range of c being [10,29]
+	       * from the branch, and recognize that the range of i fits within
+	       * a cast to c, then there is no missing information in a cast
+	       * back to int. We can use the range calculated for 'c' with 'i'
+	       * as well and RVRP should be able to kill the call.  */
+	      if (i > 29)
+		kill (i);
+	    }
+	}
+      /* i has a range of [10, MAX]  */
+      char d  = (char) i;
+      if (d < 30)
+	{
+	  /* Here, a cast to a char and back is NOT equivalent, so we cannot use
+	   * the value of d to remove the call.  */
+	  if (i > 29)
+	    keep (i);
+	}
+
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "kill \\(" 0 "rvrp"} } */
+/* { dg-final { scan-tree-dump-times "keep \\(" 1 "rvrp"} } */
+