One last tweak before we move onto the new world/branch.

From-SVN: r259404

gcc/ChangeLog

@@ -1,3 +1,19 @@
+2017-08-24  Aldy Hernandez  <aldyh@redhat.com>
+
+	PR middle-end/81931
+	* tree-ssanames.c (get_nonzero_bits): Use element_precision
+	instead of TYPE_PRECISION.
+
+2017-08-22  Aldy Hernandez  <aldyh@redhat.com>
+
+	* wide-int.h (hwi_with_prec::hwi_with_prec): Sign extend.
+
+2017-10-26  Richard Sandiford  <richard.sandiford@linaro.org>
+
+	* wide-int-print.cc (print_hex): Loop based on extract_uhwi.
+	Don't print any bits outside the precision of the value.
+	* wide-int.cc (test_printing): Add some new tests.
+
 2018-03-20  David H. Gutteridge  <dhgutteridge@sympatico.ca>
 
 	PR target/84838

gcc/Makefile.in

@@ -1437,6 +1437,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 \
@@ -1476,6 +1478,10 @@ OBJS = \
 	spellcheck.o \
 	spellcheck-tree.o \
 	sreal.o \
+	ssa-range.o \
+	ssa-range-bb.o \
+	ssa-range-global.o \
+	ssa-range-stmt.o \
 	stack-ptr-mod.o \
 	statistics.o \
 	stmt.o \
@@ -2553,6 +2559,7 @@ GTFILES = $(CPP_ID_DATA_H) $(srcdir)/input.h $(srcdir)/coretypes.h \
   $(srcdir)/gimple.h \
   $(srcdir)/gimple-ssa.h \
   $(srcdir)/tree-chkp.c \
+  $(srcdir)/range.h $(srcdir)/range.c \
   $(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/builtins.c

@@ -34,6 +34,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tm_p.h"
 #include "stringpool.h"
 #include "tree-vrp.h"
+#include "range.h"
 #include "tree-ssanames.h"
 #include "expmed.h"
 #include "optabs.h"
@@ -2945,6 +2946,52 @@ builtin_memcpy_read_str (void *data, HOST_WIDE_INT offset,
   return c_readstr (str + offset, mode);
 }
 
+/* If a range IR may have wrapped in such a way that we can guess the
+   range is positive, return TRUE and set PROBABLE_MAX_SIZE.
+   Otherwise, return FALSE and leave PROBABLE_MAX_SIZE unchanged.  */
+
+static bool
+range_may_have_wrapped (irange ir,
+			unsigned HOST_WIDE_INT *probable_max_size)
+{
+  /* Code like:
+
+       signed int n;
+       if (n < 100)
+         {
+           # RANGE [0, 99][0xffff8000, 0xffffffff]
+	   _1 = (unsigned) n;
+	   memcpy (a, b, _1)
+         }
+
+     Produce a range allowing negative values of N.  We can still use
+     the information and make a guess that N is not negative.  */
+  if (ir.num_pairs () != 2
+      || ir.lower_bound () != 0)
+    return false;
+
+  const_tree type = ir.get_type ();
+  unsigned precision = TYPE_PRECISION (type);
+  gcc_assert (TYPE_UNSIGNED (type));
+
+  /* Build a range with all the negatives: [0xffff8000, 0xffffffff].  */
+  wide_int minus_one = wi::bit_not (wide_int::from (0, precision, UNSIGNED));
+  wide_int smallest_neg = wi::lshift (minus_one, precision / 2 - 1);
+  irange negatives (type, smallest_neg, minus_one);
+
+  irange orig_range = ir;
+  ir.intersect (negatives);
+  if (ir == negatives)
+    {
+      wide_int max = orig_range.upper_bound (0); // Get the 99 in [0, 99].
+      if (!wi::fits_uhwi_p (max))
+	return false;
+      *probable_max_size = max.to_uhwi ();
+      return true;
+    }
+  return false;
+}
+
 /* LEN specify length of the block of memcpy/memset operation.
    Figure out its range and put it into MIN_SIZE/MAX_SIZE. 
    In some cases we can make very likely guess on max size, then we
@@ -2964,7 +3011,6 @@ determine_block_size (tree len, rtx len_rtx,
   else
     {
       wide_int min, max;
-      enum value_range_type range_type = VR_UNDEFINED;
 
       /* Determine bounds from the type.  */
       if (tree_fits_uhwi_p (TYPE_MIN_VALUE (TREE_TYPE (len))))
@@ -2977,34 +3023,18 @@ determine_block_size (tree len, rtx len_rtx,
       else
 	*probable_max_size = *max_size = GET_MODE_MASK (GET_MODE (len_rtx));
 
-      if (TREE_CODE (len) == SSA_NAME)
-	range_type = get_range_info (len, &min, &max);
-      if (range_type == VR_RANGE)
+      if (TREE_CODE (len) == SSA_NAME && get_range_info (len, &min, &max))
 	{
-	  if (wi::fits_uhwi_p (min) && *min_size < min.to_uhwi ())
-	    *min_size = min.to_uhwi ();
-	  if (wi::fits_uhwi_p (max) && *max_size > max.to_uhwi ())
-	    *probable_max_size = *max_size = max.to_uhwi ();
-	}
-      else if (range_type == VR_ANTI_RANGE)
-	{
-	  /* Anti range 0...N lets us to determine minimal size to N+1.  */
-	  if (min == 0)
+	  irange ir (len);
+	  if (range_may_have_wrapped (ir, probable_max_size))
+	    ;
+	  else
 	    {
-	      if (wi::fits_uhwi_p (max) && max.to_uhwi () + 1 != 0)
-		*min_size = max.to_uhwi () + 1;
+	      if (wi::fits_uhwi_p (min) && *min_size < min.to_uhwi ())
+		*min_size = min.to_uhwi ();
+	      if (wi::fits_uhwi_p (max) && *max_size > max.to_uhwi ())
+		*probable_max_size = *max_size = max.to_uhwi ();
 	    }
-	  /* Code like
-
-	     int n;
-	     if (n < 100)
-	       memcpy (a, b, n)
-
-	     Produce anti range allowing negative values of N.  We still
-	     can use the information and make a guess that N is not negative.
-	     */
-	  else if (!wi::leu_p (max, 1 << 30) && wi::fits_uhwi_p (min))
-	    *probable_max_size = min.to_uhwi () - 1;
 	}
     }
   gcc_checking_assert (*max_size <=
@@ -3116,7 +3146,7 @@ check_access (tree exp, tree, tree, tree dstwrite,
     dstsize = maxobjsize;
 
   if (dstwrite)
-    get_size_range (dstwrite, range);
+    get_size_range (dstwrite, range, /*range_starts_at=*/0);
 
   tree func = get_callee_fndecl (exp);
 
@@ -3338,9 +3368,7 @@ compute_objsize (tree dest, int ostype)
 	      && INTEGRAL_TYPE_P (TREE_TYPE (off)))
 	    {
 	      wide_int min, max;
-	      enum value_range_type rng = get_range_info (off, &min, &max);
-
-	      if (rng == VR_RANGE)
+	      if (get_range_info (off, &min, &max))
 		{
 		  if (tree size = compute_objsize (dest, ostype))
 		    {

gcc/calls.c

@@ -49,6 +49,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "rtl-iter.h"
 #include "tree-chkp.h"
 #include "tree-vrp.h"
+#include "range.h"
 #include "tree-ssanames.h"
 #include "rtl-chkp.h"
 #include "intl.h"
@@ -1300,10 +1301,12 @@ 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.
+
+   RANGE_STARTS_AT is the number where the range will start from.  */
 
 bool
-get_size_range (tree exp, tree range[2], bool allow_zero /* = false */)
+get_size_range (tree exp, tree range[2], unsigned range_starts_at /* = 1*/)
 {
   if (tree_fits_uhwi_p (exp))
     {
@@ -1314,16 +1317,10 @@ get_size_range (tree exp, tree range[2], bool allow_zero /* = false */)
 
   tree exptype = TREE_TYPE (exp);
   bool integral = INTEGRAL_TYPE_P (exptype);
-
   wide_int min, max;
-  enum value_range_type range_type;
-
-  if (TREE_CODE (exp) == SSA_NAME && integral)
-    range_type = get_range_info (exp, &min, &max);
-  else
-    range_type = VR_VARYING;
-
-  if (range_type == VR_VARYING)
+  if (TREE_CODE (exp) != SSA_NAME
+      || !integral
+      || !get_range_info (exp, &min, &max))
     {
       if (integral)
 	{
@@ -1339,64 +1336,29 @@ 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)
+  /* Remove negative numbers from the range.  */
+  irange positives, ir (exp);
+  range_positives (&positives, exptype, range_starts_at);
+  if (!positives.intersect (ir).empty_p ())
     {
-      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));
-	    }
-	}
-      else
-	{
-	  max = min - 1;
-	  min = wi::zero (expprec);
-	}
+      /* Remove the unknown parts of a multi-range.
+	 This will transform [5,10][20,MAX] into [5,10].  */
+      if (positives.num_pairs () > 1
+	  && positives.upper_bound () == wide_int (wi::to_wide
+						   (TYPE_MAX_VALUE (exptype))))
+	positives.remove_pair (positives.num_pairs () - 1);
+
+      range[0] = wide_int_to_tree (exptype, positives.lower_bound ());
+      range[1] = wide_int_to_tree (exptype, positives.upper_bound ());
+    }
+  else
+    {
+      /* If removing the negative numbers didn't give us anything
+	 back, the entire range was negative. Leave things as they
+	 were, and let the caller sort it out.  */
+      range[0] = wide_int_to_tree (exptype, min);
+      range[1] = wide_int_to_tree (exptype, max);
     }
-
-  range[0] = wide_int_to_tree (exptype, min);
-  range[1] = wide_int_to_tree (exptype, max);
-
   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], unsigned range_starts_at = 1);
 extern rtx rtx_for_static_chain (const_tree, bool);
 
 #endif // GCC_CALLS_H

gcc/common.opt

@@ -2646,6 +2646,11 @@ ftree-vrp
 Common Report Var(flag_tree_vrp) Init(0) Optimization
 Perform Value Range Propagation on trees.
 
+ftree-rvrp
+Common Report Var(flag_tree_rvrp) Init(1) Optimization
+Perform New Ranger Value Range Propagation on trees.
+
+
 fsplit-paths
 Common Report Var(flag_split_paths) Init(0) Optimization
 Split paths leading to loop backedges.

gcc/fold-const.c

@@ -76,6 +76,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "md5.h"
 #include "case-cfn-macros.h"
 #include "stringpool.h"
+#include "range.h"
 #include "tree-vrp.h"
 #include "tree-ssanames.h"
 #include "selftest.h"
@@ -9204,7 +9205,6 @@ bool
 expr_not_equal_to (tree t, const wide_int &w)
 {
   wide_int min, max, nz;
-  value_range_type rtype;
   switch (TREE_CODE (t))
     {
     case INTEGER_CST:
@@ -9213,18 +9213,12 @@ expr_not_equal_to (tree t, const wide_int &w)
     case SSA_NAME:
       if (!INTEGRAL_TYPE_P (TREE_TYPE (t)))
 	return false;
-      rtype = get_range_info (t, &min, &max);
-      if (rtype == VR_RANGE)
+      if (SSA_NAME_RANGE_INFO (t))
 	{
-	  if (wi::lt_p (max, w, TYPE_SIGN (TREE_TYPE (t))))
-	    return true;
-	  if (wi::lt_p (w, min, TYPE_SIGN (TREE_TYPE (t))))
+	  irange ri (t);
+	  if (!ri.contains_p (w))
 	    return true;
 	}
-      else if (rtype == VR_ANTI_RANGE
-	       && wi::le_p (min, w, TYPE_SIGN (TREE_TYPE (t)))
-	       && wi::le_p (w, max, TYPE_SIGN (TREE_TYPE (t))))
-	return true;
       /* If T has some known zero bits and W has any of those bits set,
 	 then T is known not to be equal to W.  */
       if (wi::ne_p (wi::zext (wi::bit_and_not (w, get_nonzero_bits (t)),

gcc/function-tests.c

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

gcc/gengtype-parse.c

@@ -300,6 +300,13 @@ require_template_declaration (const char *tmpl_name)
 	{
 	  if (T.code == '*')
 	    {
+	      /* Handle simple multiplication by a constant.  Do not
+		 treat it like indirection.  */
+	      if (token () == NUM)
+		{
+		  str = concat (str, advance (), (char *) 0);
+		  continue;
+		}
 	      id = "*";
 	      if (num_indirections++)
 		parse_error ("only one level of indirection is supported"

gcc/gengtype.c

@@ -1719,6 +1719,7 @@ open_base_files (void)
       "optabs.h", "libfuncs.h", "debug.h", "internal-fn.h", "gimple-fold.h",
       "tree-eh.h", "gimple-iterator.h", "gimple-ssa.h", "tree-cfg.h",
       "tree-vrp.h", "tree-phinodes.h", "ssa-iterators.h", "stringpool.h",
+      "range.h",
       "tree-ssanames.h", "tree-ssa-loop.h", "tree-ssa-loop-ivopts.h",
       "tree-ssa-loop-manip.h", "tree-ssa-loop-niter.h", "tree-into-ssa.h",
       "tree-dfa.h", "tree-ssa.h", "reload.h", "cpp-id-data.h", "tree-chrec.h",

gcc/gimple-fold.c

@@ -648,11 +648,6 @@ size_must_be_zero_p (tree size)
   if (TREE_CODE (size) != SSA_NAME)
     return false;
 
-  wide_int min, max;
-  enum value_range_type rtype = get_range_info (size, &min, &max);
-  if (rtype != VR_ANTI_RANGE)
-    return false;
-
   tree type = TREE_TYPE (size);
   int prec = TYPE_PRECISION (type);
 
@@ -662,7 +657,10 @@ size_must_be_zero_p (tree size)
      can be stored in ssize_t, the signed counterpart of size_t.  */
   wide_int ssize_max = wi::lshift (wi::one (prec), prec - 1) - 1;
 
-  return wi::eq_p (min, wone) && wi::geu_p (max, ssize_max);
+  irange not_zero (type, wone, ssize_max);
+  irange size_range (size);
+  return (size_range.contains_p (0)
+	  && size_range.intersect (not_zero).empty_p ());
 }
 
 /* Fold function call to builtin mem{{,p}cpy,move}.  Try to detect and

gcc/gimple-pretty-print.c

@@ -2140,22 +2140,17 @@ dump_ssaname_info (pretty_printer *buffer, tree node, int spc)
 	}
     }
 
-  if (!POINTER_TYPE_P (TREE_TYPE (node))
-      && SSA_NAME_RANGE_INFO (node))
+  if (!POINTER_TYPE_P (TREE_TYPE (node)) && SSA_NAME_RANGE_INFO (node))
     {
-      wide_int min, max, nonzero_bits;
-      value_range_type range_type = get_range_info (node, &min, &max);
+      irange ri (node);
+      wide_int nonzero_bits;
 
-      if (range_type == VR_VARYING)
+      if (ri.empty_p ())
 	pp_printf (buffer, "# RANGE VR_VARYING");
-      else if (range_type == VR_RANGE || range_type == VR_ANTI_RANGE)
+      else
 	{
 	  pp_printf (buffer, "# RANGE ");
-	  pp_printf (buffer, "%s[", range_type == VR_RANGE ? "" : "~");
-	  pp_wide_int (buffer, min, TYPE_SIGN (TREE_TYPE (node)));
-	  pp_printf (buffer, ", ");
-	  pp_wide_int (buffer, max, TYPE_SIGN (TREE_TYPE (node)));
-	  pp_printf (buffer, "]");
+	  ri.dump (buffer);
 	}
       nonzero_bits = get_nonzero_bits (node);
       if (nonzero_bits != -1)

gcc/gimple-ssa-evrp.c

@@ -41,6 +41,9 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-cfgcleanup.h"
 #include "vr-values.h"
 #include "gimple-ssa-evrp-analyze.h"
+#include "ssa-range.h"
+#include "ssa-range-global.h"
+
 
 class evrp_folder : public substitute_and_fold_engine
 {
@@ -347,3 +350,174 @@ make_pass_early_vrp (gcc::context *ctxt)
   return new pass_early_vrp (ctxt);
 }
 
+
+/* Main entry point for the early Ranger vrp pass.  */
+
+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;
+    }
+  // probably dont need this.
+  if (virtual_operand_p (name))
+    return false;
+  return true;
+}
+
+static unsigned int
+execute_ranger_vrp ()
+{
+  path_ranger ranger;
+  
+  basic_block bb;
+  irange r;
+  wide_int i;
+  unsigned x;
+  bitmap_iterator bi;
+  bitmap touched = BITMAP_ALLOC (NULL);
+
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      gcond *cond;
+      gimple *stmt = last_stmt (bb);
+      if (stmt && (cond = dyn_cast <gcond *> (stmt)))
+        {
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "Considering ");
+	      print_gimple_stmt (dump_file, cond, 0,0);
+	    }
+	  if (ranger.path_range_stmt (r, stmt))
+	    {
+	      if (dump_file)
+	        {
+		  fprintf (dump_file, "Found a range for the expression: ");
+		  r.dump (dump_file);
+		  fprintf (dump_file, "\n");
+		}
+
+	      if (r.singleton_p (i))
+	        {
+		  if (!argument_ok_to_propagate (gimple_cond_lhs (cond)) ||
+		      !argument_ok_to_propagate (gimple_cond_rhs (cond)))
+		    {
+		      if (dump_file)
+			{
+			  fprintf (dump_file, "Found  BB%d branch",bb->index);
+			  print_gimple_stmt (dump_file, stmt, 0, 0);
+			  fprintf (dump_file, "cannot eliminate. proprules.\n");
+			  fprintf (stderr,"\n  *********************** caught one\n");
+			}
+		      continue;
+		    }
+
+		  /* If either operand is an ssa_name, set the touched bit for
+		     potential removal later if no uses are left.  */
+		  tree t = valid_irange_ssa (gimple_cond_lhs (cond));
+		  if (t)
+		    bitmap_set_bit (touched, SSA_NAME_VERSION (t));
+		  t = valid_irange_ssa (gimple_cond_rhs (cond));
+		  if (t)
+		    bitmap_set_bit (touched, SSA_NAME_VERSION (t));
+
+		  if (dump_file)
+		    {
+		      fprintf (dump_file, "eliminating BB%d branch",bb->index);
+		      print_gimple_stmt (dump_file, stmt, 0, 0);
+		    }
+
+		  /* Rewrite the condition to either true or false.  */
+		  if (wi::eq_p (i, 0))
+		    gimple_cond_make_false (cond);
+		  else
+		    gimple_cond_make_true (cond);
+
+		  if (dump_file)
+		    {
+		      fprintf (dump_file, "Re-written to: \n");
+		      print_gimple_stmt (dump_file, cond, 0, 0);
+		      fprintf (dump_file, "\n");
+		    }
+		}
+	    }
+	}
+
+    }
+
+  // Now visit each name that was rewritten and see if the definiing statement
+  // can be deleted due to no more uses in the program
+  EXECUTE_IF_SET_IN_BITMAP (touched, 0, x, bi)
+    {
+      tree name = ssa_name (x);
+      gimple *s = SSA_NAME_DEF_STMT (name);
+      
+      if (s)
+        {
+	  if (has_zero_uses (name))
+	    {
+	      if (dump_file)
+		{
+		  fprintf (dump_file, "Should delete");
+		  print_gimple_stmt (dump_file, s, 0, 0);
+		}
+	    }
+	  else
+	    {
+	      if (dump_file)
+		{
+		  fprintf (dump_file, "Still has uses, Could not delete ");
+		  print_gimple_stmt (dump_file, s, 0, 0);
+		}
+	    }
+	}
+    }
+  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/gimple-ssa-warn-alloca.c

@@ -217,13 +217,12 @@ alloca_call_type_by_arg (tree arg, tree arg_casted, edge e, unsigned max_size)
       && TREE_CODE (limit) == SSA_NAME)
     {
       wide_int min, max;
-      value_range_type range_type = get_range_info (limit, &min, &max);
 
-      if (range_type == VR_UNDEFINED || range_type == VR_VARYING)
+      if (!get_range_info (limit, &min, &max))
 	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
+      // get any range information 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).
       //
@@ -253,13 +252,12 @@ cast_from_signed_p (tree ssa, tree *invalid_casted_type)
   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.
+// Return TRUE if TYPE has a maximum range of MAX.
 
 static bool
-is_max (tree x, wide_int max)
+is_max (tree type, wide_int max)
 {
-  return wi::max_value (TREE_TYPE (x)) == max;
+  return wi::max_value (type) == max;
 }
 
 // Analyze the alloca call in STMT and return the alloca type with its
@@ -305,88 +303,87 @@ alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type)
     }
 
   // Check the range info if available.
-  if (TREE_CODE (len) == SSA_NAME)
+  if (TREE_CODE (len) == SSA_NAME && get_range_info (len, &min, &max))
     {
-      value_range_type range_type = get_range_info (len, &min, &max);
-      if (range_type == VR_RANGE)
+      irange r (len);
+      if (wi::leu_p (max, max_size))
+	return alloca_type_and_limit (ALLOCA_OK);
+      else if (is_max (TREE_TYPE (len), max)
+	       && !r.range_for_type_p ()
+	       && cast_from_signed_p (len, invalid_casted_type))
 	{
-	  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);
-	      else if (range_type != VR_VARYING)
-		return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, 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.
+	  // A cast from signed to unsigned may cause us to have very
+	  // large numbers that can be caught with the above
+	  // heuristic.
 	  //
 	  // This is here to catch things like:
 	  // void foo(signed int n) {
 	  //   if (n < 100)
-	  //     alloca(n);
+	  //     {
+	  //       # RANGE [0,99][0xff80, 0xffff]
+	  //       unsigned int _1 = (unsigned int) n;
+	  //       alloca (_1);
+	  //     }
 	  //   ...
 	  // }
-	  if (cast_from_signed_p (len, invalid_casted_type))
+	  //
+	  // Unfortunately it 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;
+	}
+      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 through the cast when it's from unsigned to
+	  // unsigned, otherwise we 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);
+	  bool have_range = true;
+	  if (gimple_assign_cast_p (def))
+
 	    {
-	      // 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;
+	      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;
+		  have_range = get_range_info (len_casted, &min, &max);
+		}
 	    }
+	  // An unknown range or a range of the entire domain is
+	  // really no range at all.
+	  if (!have_range
+	      || (!len_casted && is_max (TREE_TYPE (len), max))
+	      || (len_casted && is_max (TREE_TYPE (len_casted), max)))
+	    {
+	      // Fall through.
+	    }
+	  else
+	    return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, max);
 	}
       // No easily determined range and try other things.
     }

gcc/gimple-ssa-warn-restrict.c

@@ -308,7 +308,7 @@ builtin_memref::extend_offset_range (tree offset)
   if (TREE_CODE (offset) == SSA_NAME)
     {
       wide_int min, max;
-      value_range_type rng = get_range_info (offset, &min, &max);
+      value_range_type rng = get_range_info_as_value_range (offset, &min, &max);
       if (rng == VR_RANGE)
 	{
 	  offrange[0] += offset_int::from (min, SIGNED);

gcc/internal-fn.c

@@ -521,7 +521,7 @@ get_min_precision (tree arg, signop sign)
   if (TREE_CODE (arg) != SSA_NAME)
     return prec + (orig_sign != sign);
   wide_int arg_min, arg_max;
-  while (get_range_info (arg, &arg_min, &arg_max) != VR_RANGE)
+  while (!get_range_info (arg, &arg_min, &arg_max))
     {
       gimple *g = SSA_NAME_DEF_STMT (arg);
       if (is_gimple_assign (g)

gcc/ipa-cp.c

@@ -1009,8 +1009,6 @@ ipcp_bits_lattice::set_to_constant (widest_int value, widest_int mask)
 void
 ipcp_bits_lattice::get_value_and_mask (tree operand, widest_int *valuep, widest_int *maskp)
 {
-  wide_int get_nonzero_bits (const_tree);
-
   if (TREE_CODE (operand) == INTEGER_CST)
     {
       *valuep = wi::to_widest (operand);

gcc/ipa-prop.c

@@ -1886,7 +1886,7 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
 	  value_range_type type;
 	  if (TREE_CODE (arg) == SSA_NAME
 	      && param_type
-	      && (type = get_range_info (arg, &min, &max))
+	      && (type = get_range_info_as_value_range (arg, &min, &max))
 	      && (type == VR_RANGE || type == VR_ANTI_RANGE))
 	    {
 	      value_range tmpvr,resvr;
@@ -1896,6 +1896,18 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
 	      tmpvr.max = wide_int_to_tree (TREE_TYPE (arg), max);
 	      tmpvr.equiv = NULL;
 	      memset (&resvr, 0, sizeof (resvr));
+	      /* FIXME: Can we rewrite this to avoid calling the
+		 internals of VRP here?  We should really get rid of
+		 the call to get_range_info_as_value_range() above,
+		 and this value_range business throughout this file.
+
+		 At this point, we should only be looking at
+		 SSA_NAME_RANGE_INFO (through get_range_info()).
+
+		 Perhaps we could look at all the uses of value_range
+		 in this file, and if they are only used on
+		 INTEGRAL_TYPE_P's, rewrite this to use the irage
+		 class.  */
 	      extract_range_from_unary_expr (&resvr, NOP_EXPR, param_type,
 					     &tmpvr, TREE_TYPE (arg));
 	      if (resvr.type == VR_RANGE || resvr.type == VR_ANTI_RANGE)

gcc/passes.c

@@ -61,6 +61,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-cfgcleanup.h"
 #include "insn-addr.h" /* for INSN_ADDRESSES_ALLOC.  */
 #include "diagnostic-core.h" /* for fnotice */
+#include "ssa-range.h"
 #include "stringpool.h"
 #include "attribs.h"
 
@@ -2493,6 +2494,12 @@ execute_one_pass (opt_pass *pass)
     do_per_function (verify_curr_properties,
 		     (void *)(size_t)pass->properties_required);
 
+  if (pass->name && !strcmp (pass->name, "rvrp"))
+    {
+      path_ranger r;
+      r.exercise (dump_file);
+    }
+
   /* Do it!  */
   todo_after = pass->execute (cfun);
 

gcc/passes.def

@@ -93,6 +93,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);
+	  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,73 @@
+/* Header file for range operator class.
+   Copyright (C) 2017 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
+
+/* This class is implmented 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.  Tihs is mostly for logical true false, but can serve other
+       purposes.   
+         ie   0 = op1 - op2 implies op2 has the same range as op1.
+
+*/
+
+
+
+class irange_operator
+{
+public:
+  virtual void dump (FILE *f) const = 0;
+
+  /* Set a range based on this operation between 2 operands.
+     Return the TRUE if a valid range is created.  */
+  virtual bool fold_range (irange& r, const irange& op1,
+			   const irange& op2) const;
+
+  /* Set the range for op? in the general case. R is the range for the LHS
+     of the expression, VAL is the range for the other operand, and
+     the result is returned in R.
+     ie   [range] = op1 + VAL
+     This is re-formed as  new_range = [range] - VAL.
+     Return TRUE if the operation could be performd and the range is valid.  */
+  virtual bool op1_irange (irange& r, const irange& lhs,
+			   const irange& op2) const;
+  virtual bool op2_irange (irange& r, const irange& lhs,
+			   const irange& op1) const;
+};
+
+extern irange_operator *irange_op_handler(enum tree_code code);
+
+#endif /* GCC_RANGE_OP_H */

gcc/range.h

@@ -0,0 +1,324 @@
+/* Header file for range analysis.
+   Copyright (C) 2017 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
+
+class irange_storage;
+
+/* This is a class for working with ranges, currently integer ones.
+   With it you can specify a range of [5,10] (5 through 10 inclusive),
+   or even ranges including multi-part ranges [-10,5][30,40][50,60].
+   This last one specifies the union of the different sub-ranges.
+
+   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 (GC).
+   Consequently, there are no GTY markers.  For long term storage, use
+   the irange_storage class described later.  */
+class irange
+{
+  friend class irange_storage;
+ public:
+  /* Maximum number of pairs of ranges allowed.  */
+  static const unsigned int max_pairs = 3;
+
+ private:
+  /* Number of items in bounds[].  */
+  unsigned char nitems;
+  /* Whether or not a set operation overflowed.  */
+  bool overflow;
+  /* The type of the range.  */
+  const_tree type;
+  /* The pairs of sub-ranges in the range.  */
+  wide_int bounds[max_pairs * 2];
+
+  void insert (const wide_int &x, const wide_int &y, unsigned pos);
+  void prepend (const wide_int &x, const wide_int &y);
+  void append (const wide_int &x, const wide_int &y);
+  void remove (unsigned i, unsigned j);
+  void canonicalize ();
+
+ public:
+  /* When constructing a range, this specifies wether this is a
+     regular range, or the inverse of a range.  */
+  enum kind { PLAIN, INVERSE };
+  irange () { type = NULL_TREE; nitems = 0; }
+  explicit irange (const_tree t) { set_range (t); }
+  irange (const_tree typ, const wide_int &lbound, const wide_int &ubound,
+	  kind rt = PLAIN)
+    { set_range (typ, lbound, ubound, rt); }
+  irange (const_tree typ, const_tree lbound, const_tree ubound,
+	  kind rt = PLAIN)
+    { set_range (typ, wi::to_wide (lbound), wi::to_wide (ubound), rt); }
+  irange (const irange &);
+  irange (const irange_storage *stor, tree typ) { set_range (stor, typ); }
+  irange (const_tree t, int x, int y, kind k = PLAIN)
+						    { set_range (t, x, y, k); }
+
+  void set_range (const irange_storage *, const_tree);
+  void set_range (const_tree);
+  void set_range (const_tree, const wide_int &lbound, const wide_int &ubound,
+		  kind rt = PLAIN);
+  void set_range (const_tree typ, const_tree lbound, const_tree ubound,
+		  kind rt = PLAIN)
+    { set_range (typ, wi::to_wide (lbound), wi::to_wide (ubound), rt);  }
+  void set_range (const_tree t, int x, int y, kind rt = PLAIN);
+  void set_range_for_type (const_tree);
+
+  bool overflow_p () const { return overflow && !TYPE_OVERFLOW_WRAPS (type); }
+  void set_overflow () { overflow = true; }
+  void clear_overflow () { overflow = false; }
+
+  unsigned num_pairs () const { return nitems / 2; }
+  /* Returns the lower bound of PAIR.  */
+  wide_int lower_bound (unsigned pair = 0) const
+    {
+      gcc_assert (nitems != 0 && pair <= num_pairs ());
+      return bounds[pair * 2];
+    }
+  /* Returns the uppermost bound.  */
+  wide_int upper_bound () const
+    {
+      gcc_assert (nitems != 0);
+      return bounds[nitems - 1];
+    }
+  wide_int upper_bound (unsigned pair) const;
+
+  /* Remove a sub-range from a range.  PAIR is the zero-based
+     sub-range to remove.  */
+  void remove_pair (unsigned pair) { remove (pair * 2, pair * 2 + 1); }
+  void clear () { nitems = 0; }
+  void clear (const_tree t) { type = t; nitems = 0; overflow = false; }
+  bool empty_p () const { return !nitems; }
+  bool range_for_type_p () const;
+  bool simple_range_p () const { return nitems == 2; }
+  bool zero_p () const { return *this == irange (type, 0, 0); }
+  bool non_zero_p () const
+    {
+      irange nz;
+      nz.set_range (type, 0, 0, INVERSE);
+      return *this == nz;
+    }
+  inline bool singleton_p (wide_int &) const;
+
+  void dump () const;
+  void dump (pretty_printer *pp) const;
+  void dump (FILE *) const;
+
+  bool valid_p () const;
+  void cast (const_tree type);
+  bool contains_p (const wide_int &element) const;
+  bool contains_p (const_tree) const;
+  bool contains_p (int) const;
+
+  const_tree get_type () const { return type; }
+
+  void intersect_mask (const wide_int& mask);
+
+  irange& operator= (const irange &r);
+  irange& operator= (const_tree t);
+
+  bool operator== (const irange &r) const;
+  bool operator!= (const irange &r) const { return !(*this == r); }
+
+  irange &union_ (const wide_int &x, const wide_int &y);
+  irange &union_ (const irange &r);
+  irange &intersect (const wide_int &x, const wide_int &y);
+  irange &intersect (const irange &r);
+  irange &invert ();
+};
+
+/* Return TRUE if range contains exactly one element.  If so, set ELEM
+   to said element.  */
+
+inline bool
+irange::singleton_p (wide_int &elem) const
+{
+  if (num_pairs () == 1 && bounds[0] == bounds[1])
+    {
+      elem = bounds[0];
+      return true;
+    }
+  return false;
+}
+
+/* Return R1 U R2.  */
+static inline
+irange irange_union (const irange &r1, const irange &r2)
+{
+  return irange (r1).union_ (r2);
+}
+
+/* Return R1 ^ R2.  */
+static inline
+irange irange_intersect (const irange &r1, const irange &r2)
+{
+  return irange (r1).intersect (r2);
+}
+
+/* Return the inverse range of R1.  */
+static inline
+irange irange_invert (const irange &r1)
+{
+  return irange (r1).invert ();
+}
+
+void range_zero (irange *r, tree type);
+void range_one (irange *r, tree type);
+bool range_non_zero (irange *r, tree type);
+void range_positives (irange *r, tree type, unsigned int);
+
+// From ssa-range-gen.c.  
+// class gori will control this  until we get globals set up properly.
+bool get_global_ssa_range (irange& r, tree name);
+void set_global_ssa_range (tree name, const irange&r);
+
+
+/* An irange is inefficient when it comes to memory, so this class is
+   used to store iranges in memory (off of an SSA_NAME likely).  It is
+   a variable length structure that contains the sub-range pairs as
+   well as the non-zero bitmask.  The number of entries are
+   irnage::max_pairs * 2 + 1 (to accomodate the non-zero bits).
+
+   To store an irange class X into this memory efficient irange_storage
+   class use:
+
+	irange X;
+	irange_storage *stow = irange_storage::ggc_alloc_init (X);
+   or
+	irange_storage *stow = irange_storage::ggc_alloc (precision);
+	stow->set_irange (X);
+
+   To convert it back to an irange use:
+
+	tree type = ...;
+	irange X (stow, type);
+   or
+	if (SSA_NAME_RANGE_INFO (ssa)) {
+	  irange X (ssa);
+	  ...
+	}
+   or
+	irange x;
+	stow->extract_irange (x, TYPE);
+
+   To get at the nonzero bits use:
+
+	irange_storage *stow = ...;
+	stow->set_nonzero_bits();
+	stow->get_nonzero_bits();
+*/
+
+class GTY((variable_size)) irange_storage
+{
+  friend class irange;
+ public:
+  /* These are the pair of subranges for the irange.  The last
+     wide_int allocated is a mask representing which bits in an
+     integer are known to be non-zero.  */
+  trailing_wide_ints<irange::max_pairs * 2 + 1> trailing_bounds;
+
+  void set_irange (const irange &);
+  /* Returns the size of an irange_storage with PRECISION.  */
+  static size_t size (unsigned precision)
+  { return sizeof (irange_storage)
+      /* There is a +1 for the non-zero bits field.  */
+      + trailing_wide_ints<irange::max_pairs * 2 + 1>::extra_size (precision);
+  }
+  /* Allocate GC memory for an irange_storage with PRECISION.
+
+     Note: The precision is set, but the irange_storage returned is
+     otherwise uninitialized.  The caller must still call
+     stow->set_irange().  */
+  static irange_storage *ggc_alloc (unsigned precision)
+  { irange_storage *stow = static_cast<irange_storage *> (ggc_internal_alloc
+							  (size (precision)));
+    stow->trailing_bounds.set_precision (precision);
+    stow->set_nonzero_bits (wi::shwi (-1, precision));
+    return stow;
+  }
+  /* Like irange_storage::ggc_alloc (), but initialize the storage to
+     the range in IR.  */
+  static irange_storage *ggc_alloc_init (const irange &ir)
+  {
+    unsigned precision = TYPE_PRECISION (ir.type);
+    irange_storage *stow = static_cast<irange_storage *> (ggc_internal_alloc
+							  (size (precision)));
+    stow->set_irange (ir);
+    stow->set_nonzero_bits (wi::shwi (-1, precision));
+    return stow;
+  }
+  /* Extract the current range onto OUTPUT with a type of TYP.
+     Returns the range.  */
+  inline irange &extract_irange (irange &output, const_tree typ);
+  /* Set the nonzero bit mask to WI.  */
+  void set_nonzero_bits (const wide_int &wi)
+  { trailing_bounds[irange::max_pairs * 2] = wi; }
+  /* Return the nonzero bits in the range.  */
+  wide_int get_nonzero_bits (void)
+  { return trailing_bounds[irange::max_pairs * 2]; }
+};
+
+/* Extract the range in THIS and store it in OUTPUT with a type of TYP.
+   Returns OUTPUT.  */
+
+inline irange &
+irange_storage::extract_irange (irange &output, const_tree typ)
+{
+  output.set_range (this, typ);
+  return output;
+}
+
+// ----------------------------------------------------------------------
+
+/* Return T if it is a valid type for irange to operator on. 
+   Otherwise return NULL_TREE.  */
+static inline
+tree valid_irange_type (tree t)
+{
+  if (t && (INTEGRAL_TYPE_P (t) || POINTER_TYPE_P (t)))
+    return t;
+  return NULL_TREE;
+}
+
+/* Return T if it is an SSA_NAME and a valid type for irange to operator on. 
+   Otherwise return NULL_TREE.  */
+static inline
+tree valid_irange_ssa (tree t)
+{
+  if (t && TREE_CODE (t) == SSA_NAME && valid_irange_type (TREE_TYPE (t)))
+    return t;
+  return NULL_TREE;
+}
+
+#endif // GCC_RANGE_H

gcc/selftest.h

@@ -214,6 +214,7 @@ extern void unique_ptr_tests_cc_tests ();
 extern void vec_c_tests ();
 extern void wide_int_cc_tests ();
 extern void predict_c_tests ();
+extern void irange_tests ();
 extern void simplify_rtx_c_tests ();
 extern void vec_perm_indices_c_tests ();
 

gcc/ssa-range-bb.c

@@ -0,0 +1,792 @@
+/* On-demand ssa range generator for blocks.
+   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-bb.h"
+#include "ssa-range-global.h"
+
+/* Is the last stmt in a block interesting to look at for range info.  */
+
+gimple *
+last_stmt_gori (basic_block bb)
+{
+  gimple *stmt;
+
+  stmt = last_stmt (bb);
+  if (stmt && gimple_code (stmt) == GIMPLE_COND)
+    return stmt;
+  return NULL;
+}
+   
+/* GORI_MAP is used to determine 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."  */
+
+class gori_map
+{
+  vec<bitmap> outgoing;		/* BB: Outgoing ranges generated.  */
+  vec<bitmap> incoming;		/* BB: ranges coming in.  */
+  vec<bitmap> def_chain;	/* SSA_NAME : def chain components. */
+  void calculate_gori (basic_block bb);
+  bool in_chain_p (unsigned name, unsigned def);
+  bitmap imports (basic_block bb);
+  bitmap exports (basic_block bb);
+  bitmap calc_def_chain (tree name, basic_block bb);
+  void process_stmt (gimple *stmt, bitmap result, basic_block bb);
+public:
+  gori_map ();
+  ~gori_map ();
+  bool in_chain_p (tree name, tree def, basic_block bb = NULL);
+  bool is_export_p (tree name, basic_block bb);
+  bool is_import_p (tree name, basic_block bb);
+  tree single_import (tree name);
+  void dump (FILE *f);
+  void dump (FILE *f, basic_block bb);
+};
+
+gori_map::gori_map ()
+{
+  outgoing.create (0);
+  outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
+  incoming.create (0);
+  incoming.safe_grow_cleared (last_basic_block_for_fn (cfun));
+  def_chain.create (0);
+  def_chain.safe_grow_cleared (num_ssa_names);
+}
+
+gori_map::~gori_map ()
+{
+  unsigned x, bb;
+  for (bb = 0; bb < outgoing.length (); ++bb)
+    if (outgoing[bb])
+      BITMAP_FREE (outgoing[bb]);
+  outgoing.release ();
+
+  for (bb = 0; bb < incoming.length (); ++bb)
+    if (incoming[bb])
+      BITMAP_FREE (incoming[bb]);
+  incoming.release ();
+
+  for (x = 0; x < def_chain.length (); ++x)
+    if (def_chain[x])
+      BITMAP_FREE (def_chain[x]);
+  def_chain.release ();
+}
+
+bitmap
+gori_map::imports (basic_block bb)
+{
+  if (!incoming[bb->index])
+    calculate_gori (bb);
+  return incoming[bb->index];
+}
+
+bool
+gori_map::is_import_p (tree name, basic_block bb)
+{
+  return bitmap_bit_p (imports (bb), SSA_NAME_VERSION (name));
+}
+
+bitmap
+gori_map::exports (basic_block bb)
+{
+  if (!outgoing[bb->index])
+    calculate_gori (bb);
+  return outgoing[bb->index];
+}
+
+bool
+gori_map::is_export_p (tree name, basic_block bb)
+{
+  return bitmap_bit_p (exports (bb), SSA_NAME_VERSION (name));
+}
+
+bool
+gori_map::in_chain_p (tree name, tree def, basic_block bb)
+{
+  if (TREE_CODE (def) != SSA_NAME || TREE_CODE (name) != SSA_NAME)
+    return false;
+
+  unsigned def_index = SSA_NAME_VERSION (def);
+  unsigned name_index = SSA_NAME_VERSION (name);
+  gimple *stmt;
+
+  if (SSA_NAME_IS_DEFAULT_DEF (def))
+    return false;
+
+  stmt = SSA_NAME_DEF_STMT (def);
+  if (bb)
+    {
+      /* If the definition is not in a specified BB, return false;.  */
+      if (gimple_bb (stmt) != bb)
+        return false;
+    }
+  else
+    bb = gimple_bb (stmt);
+
+  if (outgoing[bb->index] == NULL)
+    calculate_gori (bb);
+
+  return in_chain_p (name_index, def_index);
+}
+
+bool
+gori_map::in_chain_p (unsigned name, unsigned def)
+{
+  if (def_chain[def] == NULL)
+    return false;
+  return bitmap_bit_p (def_chain[def], name);
+}
+
+tree
+gori_map::single_import (tree name)
+{
+  tree ret = NULL_TREE;
+  unsigned name_index = SSA_NAME_VERSION (name);
+  unsigned index;
+  basic_block bb;
+  bitmap_iterator bi;
+
+  bb = gimple_bb (SSA_NAME_DEF_STMT (name));
+  if (bb && !incoming[bb->index])
+    calculate_gori (bb);
+  if (def_chain [name_index] == NULL)
+    return NULL_TREE;
+
+  EXECUTE_IF_AND_IN_BITMAP (def_chain [name_index], incoming[bb->index], 0,
+			    index, bi)
+    {
+      if (!ret)
+        ret = ssa_name (index);
+      else
+	return NULL_TREE;
+    }
+  return ret;
+}
+
+void
+gori_map::process_stmt (gimple *stmt, bitmap result, basic_block bb)
+{
+  range_stmt rn (stmt);
+  bitmap b;
+
+  if (!rn.valid ())
+    return;
+
+  tree ssa1 = rn.ssa_operand1 ();
+  tree ssa2 = rn.ssa_operand2 ();
+
+  if (ssa1)
+    {
+      b = calc_def_chain (ssa1, bb);
+      if (b)
+	bitmap_copy (result, b);
+      bitmap_set_bit (result, SSA_NAME_VERSION (ssa1));
+    }
+  if (ssa2)
+    {
+      b = calc_def_chain (ssa2, bb);
+      if (b)
+	bitmap_ior_into (result, b);
+      bitmap_set_bit (result, SSA_NAME_VERSION (ssa2));
+    }
+  return;
+}
+
+
+bitmap
+gori_map::calc_def_chain (tree name, basic_block bb)
+{
+  gimple *stmt = SSA_NAME_DEF_STMT (name);
+  unsigned v = SSA_NAME_VERSION (name);
+  range_stmt rn;
+
+  if (!stmt || gimple_bb (stmt) != bb || is_a <gphi *> (stmt))
+    {
+      bitmap_set_bit (incoming[bb->index], v);
+      return NULL;
+    }
+  if (def_chain[v])
+    return def_chain[v];
+
+  def_chain[v] = BITMAP_ALLOC (NULL);
+  process_stmt (stmt, def_chain[v], bb);
+
+  return def_chain[v];
+}
+
+void
+gori_map::calculate_gori (basic_block bb)
+{
+  gimple *stmt;
+  gcc_assert (outgoing[bb->index] == NULL);
+  outgoing[bb->index] = BITMAP_ALLOC (NULL);
+  incoming[bb->index] = BITMAP_ALLOC (NULL);
+
+  stmt = last_stmt_gori (bb);
+  if (stmt)
+    process_stmt (stmt, outgoing[bb->index], bb);
+}
+
+void
+gori_map::dump(FILE *f, basic_block bb)
+{
+  tree t;
+  unsigned x, y;
+  bitmap_iterator bi;
+
+  if (!outgoing[bb->index])
+    {
+      fprintf (f, "BB%d was not processed.\n", bb->index);
+      return;
+    }
+
+  for (x = 1; x < num_ssa_names; x++)
+    {
+      tree name = ssa_name (x);
+      if (!name)
+	continue;
+      gimple *stmt = SSA_NAME_DEF_STMT (name);
+      if (stmt && gimple_bb (stmt) == bb && def_chain[x] &&
+	  !bitmap_empty_p (def_chain[x]))
+        {
+	  print_generic_expr (f, name, TDF_SLIM);
+	  if ((t = single_import (name)))
+	    {
+	      fprintf (f, "  : (single import : ");
+	      print_generic_expr (f, t, TDF_SLIM);
+	      fprintf (f, ")");
+	    }
+	  fprintf (f, "  :");
+	  EXECUTE_IF_SET_IN_BITMAP (def_chain[x], 0, y, bi)
+	    {
+	      print_generic_expr (f, ssa_name (y), TDF_SLIM);
+	      fprintf (f, "  ");
+	    }
+	  fprintf (f, "\n");
+	}
+    }
+
+  fprintf (f, "BB%d imports: ",bb->index);
+  EXECUTE_IF_SET_IN_BITMAP (incoming[bb->index], 0, y, bi)
+    {
+      print_generic_expr (f, ssa_name (y), TDF_SLIM);
+      fprintf (f, "  ");
+    }
+  fprintf (f, "\nBB%d exports: ",bb->index);
+  EXECUTE_IF_SET_IN_BITMAP (outgoing[bb->index], 0, y, bi)
+    {
+      print_generic_expr (f, ssa_name (y), TDF_SLIM);
+      fprintf (f, "  ");
+    }
+  fprintf (f, "\n");
+}
+
+void
+gori_map::dump(FILE *f)
+{
+  basic_block bb;
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      fprintf (f, "----BB %d----\n", bb->index);
+      dump (f, bb);
+      fprintf (f, "\n");
+    }
+}
+/* -------------------------------------------------------------------------*/
+
+block_ranger::block_ranger () : bool_zero (boolean_type_node, 0, 0),
+				bool_one (boolean_type_node, 1, 1)
+{
+  gori = new gori_map ();
+  initialize_global_ssa_range_cache ();
+
+}
+
+block_ranger::~block_ranger ()
+{
+  destroy_global_ssa_range_cache ();
+  delete gori;
+}
+
+
+// Internally, the range operators all use boolen_type_node when comparisons
+// and such are made to create ranges for logical operations.
+// some languages, such as fortran, may use boolean types with different
+// precisions and these are incompatible.   This routine will look at the 
+// 2 ranges, and if there is a mismatch between the boolean types, will change
+// the range generated from the default node to the other type.
+//
+void
+block_ranger::normalize_bool_type (irange& r1, irange& r2)
+{
+  const_tree t1 = r1.get_type ();
+  const_tree t2 = r2.get_type ();
+  if (TREE_CODE (t1) != BOOLEAN_TYPE || TREE_CODE (t2) != BOOLEAN_TYPE)
+    return;
+
+  if (t1 == t2)
+    return;
+
+  /* If neither is boolean_type_node, assume they are compatible.  */
+  if (t1 == boolean_type_node)
+      r1.cast (t2);
+  else
+    if (t2 == boolean_type_node)
+      r2.cast (t1);
+}
+
+/* This routine will return what  is globally known about the range for an
+   operand of any kind.  */
+bool
+block_ranger::get_operand_range (irange& r, tree op,
+				 gimple *s ATTRIBUTE_UNUSED)
+{
+  /* This check allows unary operations to be handled without having to 
+     make an explicit check for the existence of a second operand.  */
+  if (!op)
+    return false;
+
+  if (TREE_CODE (op) == INTEGER_CST)
+    r.set_range (TREE_TYPE (op), op, op);
+  else
+    if (TREE_CODE (op) == SSA_NAME)
+      r = op;
+    else
+      if (TYPE_P (op))
+	r.set_range_for_type (op);
+      else
+        /* Default to range for the type of the expression.   */
+	r.set_range_for_type (TREE_TYPE (op));
+
+  return true;
+}
+
+
+/* Given a logical STMT, calculate true and false for each potential path 
+   using NAME and resolve the outcome based on the logical operator.  */
+bool
+block_ranger::process_logical (range_stmt stmt, irange& r, tree name,
+		       const irange& lhs)
+{
+  range_stmt op_stmt;
+  irange op1_range, op2_range;
+  tree op1, op2;
+  bool op1_in_chain, op2_in_chain;
+  bool ret;
+
+  irange op1_true, op1_false, op2_true, op2_false;
+
+  /* Reaching this point means NAME is not in this stmt, but one of the
+     names in it ought to be derived from it.  */
+  op1 = stmt.operand1 ();
+  op2 = stmt.operand2 ();
+
+  op1_in_chain = gori->in_chain_p (name, op1);
+  op2_in_chain = gori->in_chain_p (name, op2);
+
+  /* If neither operand is derived, then this stmt tells us nothing. */
+  if (!op1_in_chain && !op2_in_chain)
+    return false;
+
+  /* The false path is not always a simple inversion of the true side.
+     Calulate ranges for true and false on both sides. */
+  if (op1_in_chain)
+    {
+      ret = get_range_from_stmt (SSA_NAME_DEF_STMT (op1), op1_true, name,
+				 bool_one);
+      ret &= get_range_from_stmt (SSA_NAME_DEF_STMT (op1), op1_false, name,
+				  bool_zero);
+    }
+  else
+    {
+      ret = get_operand_range (op1_true, name, stmt);
+      ret &= get_operand_range (op1_false, name, stmt);
+    }
+
+  /* If operand1 evaluated OK, move on to operand 2.  */
+  if (ret)
+    {
+      if (op2_in_chain)
+	{
+	  ret &= get_range_from_stmt (SSA_NAME_DEF_STMT (op2), op2_true,
+				      name, bool_one);
+	  ret &= get_range_from_stmt (SSA_NAME_DEF_STMT (op2), op2_false,
+				      name, bool_zero);
+	}
+      else
+	{
+	  ret &= get_operand_range (op2_true, name, stmt);
+	  ret &= get_operand_range (op2_false, name, stmt);
+	}
+    }
+
+  if (!ret || !stmt.fold_logical (r, lhs, op1_true, op1_false, op2_true,
+				  op2_false))
+    r.set_range_for_type (TREE_TYPE (name));
+  return true;
+}
+
+
+/* Given the expression in STMT, return an evaluation in R for NAME.
+   Returning false means the name being looked for was NOT resolvable.  */
+bool
+block_ranger::get_range_from_stmt (range_stmt stmt, irange& r, tree name,
+				   const irange& lhs)
+{
+  irange op1_range, op2_range, tmp_range;
+  tree op1, op2;
+  bool op1_in_chain, op2_in_chain;
+
+  if (!stmt.valid ())
+    return false;
+
+  if (lhs.empty_p ())
+    {
+      r.clear (TREE_TYPE (name));
+      return true;
+    }
+
+  op1 = stmt.operand1 ();
+  op2 = stmt.operand2 ();
+
+  if (op1 == name)
+    { 
+      if (!op2)
+        return stmt.op1_irange (r, lhs);
+      if (get_operand_range (op2_range, op2, stmt))
+	return stmt.op1_irange (r, lhs, op2_range);
+      else
+        return false;
+    }
+
+  if (op2 == name)
+    {
+      if (get_operand_range (op1_range, op1, stmt))
+	return stmt.op2_irange (r, lhs, op1_range);
+      else
+        return false;
+    }
+
+  /* Check for boolean cases which require developing ranges and combining.  */
+  if (stmt.logical_expr_p ())
+    return process_logical (stmt, r, name, lhs);
+
+  /* Reaching this point means NAME is not in this stmt, but one of the
+     names in it ought to be derived from it.  */
+  op1_in_chain = gori->in_chain_p (name, op1);
+  op2_in_chain = op2 && gori->in_chain_p (name, op2);
+
+  /* If neither operand is derived, then this stmt tells us nothing. */
+  if (!op1_in_chain && !op2_in_chain)
+    return false;
+
+  /* Pick up an operand range for each argument.  */
+  if (!get_operand_range (op1_range, op1, stmt))
+    return false;
+  if (op2 && !get_operand_range (op2_range, op2, stmt))
+    return false;
+
+  /* Can't resolve both sides at once, so take a guess at operand 1, calculate
+     operand 2 and check if the guess at operand 1 was good.  */
+  if (op1_in_chain && op2_in_chain)
+    {
+      // Get an op2_range based on the op1 range. 
+      if (!stmt.op2_irange (tmp_range, lhs, op1_range))
+        return false;
+      // And combine it with the raw possibilty.
+      normalize_bool_type (op2_range, tmp_range);
+      op2_range.intersect (tmp_range);
+      if (!get_range_from_stmt (SSA_NAME_DEF_STMT (op2), r, name, op2_range))
+        return false;
+
+      // Now the same for operand 1
+      if (!stmt.op1_irange (tmp_range, lhs, op2_range))
+        return false;
+      normalize_bool_type (op1_range, tmp_range);
+      op1_range.intersect (tmp_range);
+      if (!get_range_from_stmt (SSA_NAME_DEF_STMT (op1), r, name, op1_range))
+        return false;
+      // Do we need to possibly reevaluate op2?
+      return true;
+    }
+  else
+    if (op1_in_chain)
+      {
+        if (!op2)
+	  {
+	    if (!stmt.op1_irange (tmp_range, lhs))
+	      return false;
+	  }
+	else
+	  {
+	    if (!stmt.op1_irange (tmp_range, lhs, op2_range))
+	      return false;
+	  }
+	normalize_bool_type (op1_range, tmp_range);
+	op1_range.intersect (tmp_range);
+	return get_range_from_stmt (SSA_NAME_DEF_STMT (op1), r, name,
+				    op1_range);
+      }
+    else
+
+  if (!stmt.op2_irange (tmp_range, lhs, op1_range))
+    return false;
+  normalize_bool_type (op2_range, tmp_range);
+  op2_range.intersect (tmp_range);
+  return get_range_from_stmt (SSA_NAME_DEF_STMT (op2), r, name, op2_range);
+}
+ 
+void
+block_ranger::dump (FILE *f)
+{
+
+  if (!f)
+    return;
+
+  fprintf (f, "\nDUMPING GORI MAP\n");
+  gori->dump (f);
+  fprintf (f, "\n");
+
+  fprintf (f, "\nDUMPING Globals table\n");
+  dump_global_ssa_range_cache (f);
+}
+
+
+/* Name is not directly mentioned in the gori map, but if one of the
+   compnents it is built from are, we can derive the value from that. ie
+	 a_3 = c_2 * 2
+	 b_6 = a_3 + 5
+	 if (a_3 > 10)
+   The GORI map will only have c_2 and a_3 since they comprise the
+   calculation of a_3.   b_6 will not be there as the only way to know
+   that b_6 can be calculated from a_3 would be to visit all the uses of
+   a_3 and see whether it is used to help define b_6.
+   Far easier now that b_6 is requested would be to simply check now
+   if a_3 is used to construct b_6. If it is get the expression for a_3
+   and adjust it to b_6.  */
+   
+#if 0
+bool
+block_ranger::get_derived_range_stmt (range_stmt& stmt, tree name, basic_block bb)
+{
+  gimple *s;
+  tree n1,n2;
+  unsigned name_v = SSA_NAME_VERSION (name);
+
+  s = last_stmt_gori (bb);
+  gcc_assert (s);
+
+  stmt = s;
+  if (!stmt.valid ())
+    return false;
+
+  n1 = stmt.ssa_operand1 ();
+  n2 = stmt.ssa_operand2 ();
+
+  if (n1 && !bitmap_bit_p (def_chain[name_v], SSA_NAME_VERSION (n1)))
+    n1 = NULL_TREE;
+    
+  if (n2 && !bitmap_bit_p (def_chain[name_v], SSA_NAME_VERSION (n2)))
+    n2 = NULL_TREE;
+  
+  /* Non-null n1 or n2 indicates it is used in the calculating name.  */
+
+  /* Used on both sides too complicated.  */
+  if (n1 && n2)
+    return false;
+  /* Well we aren't actually DOING it yet... :-)  */
+  return false;
+}
+#endif
+
+
+tree
+block_ranger::single_import (tree name)
+{
+  return gori->single_import (name);
+}
+
+bool
+block_ranger::range_p (basic_block bb, tree name)
+{
+  return gori->is_export_p (name, bb);
+}
+
+
+/* Known range on an edge.  */
+bool
+block_ranger::range_on_edge (irange& r, tree name, edge e)
+{
+  gimple *stmt;
+  basic_block bb = e->src;
+
+  if (!valid_irange_ssa (name))
+    return false;
+
+  if (!range_p (bb, name))
+    return false;
+
+  stmt = last_stmt_gori (bb);
+  gcc_assert (stmt);
+
+  if (e->flags & EDGE_TRUE_VALUE)
+    return get_range_from_stmt (stmt, r, name, bool_one);
+
+  if (e->flags & EDGE_FALSE_VALUE)
+    return get_range_from_stmt (stmt, r, name, bool_zero);
+
+  return false;
+}
+
+
+
+void
+block_ranger::exercise (FILE *output)
+{
+
+  basic_block bb;
+  irange range;
+  
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      edge_iterator ei;
+      edge e;
+      bool printed = false;
+      FOR_EACH_EDGE (e, ei, bb->succs)
+        {
+	  unsigned x;
+	  for (x = 1; x < num_ssa_names; x++)
+	    {
+	      tree name = ssa_name (x);
+	      if (name && range_p (bb, name))
+		{
+		  if (range_on_edge (range, name, e))
+		    {
+		      if (output)
+			{
+			  printed = true;
+			  fprintf (output, "BB%3d: ", bb->index);
+			  if (e->flags & EDGE_TRUE_VALUE)
+			    fprintf (output, " T: ");
+			  else if (e->flags & EDGE_FALSE_VALUE)
+			    fprintf (output, " F: ");
+			  print_generic_expr (output, name, TDF_SLIM);
+			  fprintf(output, "  \t");
+			  range.dump(output);
+			}
+		    }
+		}
+	    }
+	}
+      if (printed)
+        fprintf (output, "\n");
+
+    }
+    
+  if (output)
+    dump (output);
+
+}
+
+
+/* Attempt to evaluate the epression using whatever is globally known about
+   the operands.  If it can be evaluated, TRUE is returned
+   and the range is returned in R.  */
+
+bool
+block_ranger::range_of_def (irange& r, gimple *g)
+{
+  range_stmt rn (g);
+  irange r1, r2;
+
+  /* If we don't understand the stmt... */
+  if (!rn.valid())
+    return false;
+  
+  tree op1 = rn.operand1 ();
+  tree op2 = rn.operand2 ();
+
+  get_operand_range (r1, op1);
+  if (op2)
+    return rn.fold (r, r1);
+
+  get_operand_range (r2, op2);
+  return rn.fold (r, r1, r2);
+}
+
+/* This method will attempt to evaluate the expression by replacing any
+   occurrence of ssa_name NAME with the range NAME_RANGE. If it can be
+   evaluated, TRUE is returned and the resulting range returned in R.  */
+bool
+block_ranger::range_of_def (irange& r, gimple *g, tree name,
+		    const irange& range_of_name)
+{
+  range_stmt rn (g);
+
+  /* If we don't understand the stmt... */
+  if (!rn.valid())
+    return false;
+  
+  irange r1, r2;
+  tree op1 = rn.operand1 ();
+  tree op2 = rn.operand2 ();
+
+  if (op1 == name)
+    r1 = range_of_name;
+  else
+    get_operand_range (r1, op1);
+
+  if (!op2)
+    return rn.fold (r, r1);
+
+  if (op2 == name)
+    r2 = range_of_name;
+  else
+    get_operand_range (r2, op2);
+
+  return rn.fold (r, r1, r2);
+}
+

gcc/ssa-range-bb.h

@@ -0,0 +1,63 @@
+/* Header file for ssa-range generator.
+   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_BB_H
+#define GCC_SSA_RANGE_BB_H
+
+#include "range.h"
+#include "range-op.h"
+#include "ssa-range-stmt.h"
+
+/* This is the primary interface class for the range generator at the basic
+   block level. It allows the client to query a range for an ssa-name within
+   a basic block, either on an outgoing edge, or on an individual statement.  */
+
+class block_ranger
+{
+  class gori_map *gori; 	/* Generates Outgoing Range Info.  */
+  irange bool_zero;
+  irange bool_one;
+  bool process_logical (range_stmt stmt, irange& r, tree name,
+			const irange& lhs);
+  bool get_range_from_stmt (range_stmt stmt, irange& r, tree name,
+			    const irange& lhs);
+protected:
+  virtual bool get_operand_range (irange& r, tree op, gimple *s = NULL);
+  void normalize_bool_type (irange& r1, irange& r2);
+public:
+  block_ranger ();
+  ~block_ranger ();
+
+  /* True if NAME Generates range info on one or more outgoing edges of BB.  */
+  bool range_p (basic_block bb, tree name);
+  /* What is the static calculated range of NAME on outgoing edge E.  */
+  bool range_on_edge (irange& r, tree name, edge e);
+  /* What infomation does stmt g provide about the lhs.  */
+  bool range_of_def (irange& r, gimple *g);
+  /* What does g provide about the lhs if NAME has RANGE_FOR_NAME.  */
+  bool range_of_def (irange& r, gimple *g, tree name,
+		     const irange& range_for_name);
+
+  tree single_import (tree name);
+  void dump (FILE *f);
+  void exercise (FILE *f);
+};
+
+#endif /* GCC_SSA_RANGE_BB_H */

gcc/ssa-range-global.c

@@ -0,0 +1,215 @@
+/* Global ssa ranges. 
+   Copyright (C) 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/>.  */
+
+/* This "global" cache is used with the range engine until such time
+   that we can unify everything to the ranges that are contained in 
+   the ssa_name itself.  There appears to be some issues with reading an
+   writing that at the moment, and there ought to be a central place to
+   read/write global ranges anyway, rather than direct SSA_NAME read/write.
+
+   When retreiving a global name, a check is first made to see if the 
+   global irange cache has a range associated with it, and that is returned
+   if it does.  If it does not, then any range assocaited with the
+   existing SSA_NAME_RANGE_INFO field is extracted and that is used.
+
+   Any SETs of ranges are localized to the global cache maintained here.
+
+   At the end of range generation/processing, a call is made to
+   copy_to_range_info() to flush this cache into the SSA_NAME_RANGE_INFO
+   fields.  */
+
+
+#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 "ssa.h"
+#include "optabs-tree.h"
+#include "gimple-pretty-print.h"
+#include "diagnostic-core.h"
+#include "ssa-range-global.h"
+
+class ssa_global_cache
+{
+private:
+  vec<irange_storage *> tab;
+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 copy_to_range_info ();
+  void dump (FILE *f = stderr);
+};
+
+ssa_global_cache *globals = NULL;
+
+/* Initialize the global cache.  */
+void
+initialize_global_ssa_range_cache ()
+{
+  gcc_assert (globals == NULL);
+  globals = new ssa_global_cache ();
+}
+
+/* Destroy the global cache. NOte we currently don't call copy_to_range_info 
+   due to some memory corruptions issues.  */
+void
+destroy_global_ssa_range_cache ()
+{
+  delete globals;
+  globals = NULL;
+}
+
+/* Dump the contents of the global cache to F.  */
+void
+dump_global_ssa_range_cache (FILE *f)
+{
+  if (globals)
+    globals->dump (f);
+}
+
+
+/* This function will retreive what is currently globally known about SSA_NAME.
+   It first tries the global_cache, then resorts to the SSA_NAME_RANGE_INFO.  */
+bool
+get_global_ssa_range (irange& r, tree name)
+{
+  if (globals)
+    return globals->get_global_range (r, name);
+
+  r.set_range (name);
+  return false;
+}
+
+/* Set a new global range for NAME.  */
+void
+set_global_ssa_range (tree name, const irange&r)
+{
+  gcc_assert (globals);
+  globals->set_global_range (name, r);
+}
+
+/* Clear the global range for NAME.  */
+void
+clear_global_ssa_range (tree name)
+{
+  gcc_assert (globals);
+  globals->clear_global_range (name);
+}
+// ---------------------------------------------------------------
+
+/* Initialize a global cache.  */
+ssa_global_cache::ssa_global_cache ()
+{
+  tab.create (0);
+  tab.safe_grow_cleared (num_ssa_names);
+}
+
+/* Deconstruct a global cache.  */
+ssa_global_cache::~ssa_global_cache ()
+{
+  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
+{
+  irange_storage *stow = tab[SSA_NAME_VERSION (name)];
+  if (stow)
+    {
+      r.set_range (stow, TREE_TYPE (name));
+      return true;
+    }
+  r.set_range (name);
+  return false;
+}
+
+/* Set the range for NAME to R in the glonbal cache.  */
+void
+ssa_global_cache::set_global_range (tree name, const irange& r)
+{
+  irange_storage *m = tab[SSA_NAME_VERSION (name)];
+
+  if (m)
+    m->set_irange (r);
+  else
+    {
+      m = irange_storage::ggc_alloc_init (r);
+      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)
+{
+  tab[SSA_NAME_VERSION (name)] = NULL;
+}
+
+/* Clear the global cache.  */
+void
+ssa_global_cache::clear ()
+{
+  memset (tab.address(), 0, tab.length () * sizeof (irange_storage *));
+}
+
+/* If there is any range information in the global cache, flush it out to
+   the legacy SSA_NAME_RANGE_INFO fields.  */
+void
+ssa_global_cache::copy_to_range_info ()
+{
+  unsigned x;
+  irange r;
+  for ( x = 1; x < num_ssa_names; x++)
+    if (get_global_range (r, ssa_name (x)))
+      {
+        if (!r.range_for_type_p ())
+	  {
+	    irange_storage *stow = irange_storage::ggc_alloc_init (r);
+	    SSA_NAME_RANGE_INFO (ssa_name (x)) = stow;
+	  }
+      }
+}
+
+/* Dump the contents of the global cache to F.  */
+void
+ssa_global_cache::dump (FILE *f)
+{
+  unsigned x;
+  irange r;
+  for ( x = 1; x < num_ssa_names; x++)
+    if (valid_irange_ssa (ssa_name (x)) && get_global_range (r, ssa_name (x)))
+      {
+        print_generic_expr (f, ssa_name (x), 0);
+	fprintf (f, "  : ");
+        r.dump (f);
+      }
+}
+
+

gcc/ssa-range-global.h

@@ -0,0 +1,32 @@
+/* Global ssa ranges. 
+   Copyright (C) 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_GLOBAL_H
+#define GCC_SSA_RANGE_GLOBAL_H
+
+void initialize_global_ssa_range_cache ();
+void destroy_global_ssa_range_cache ();
+void dump_global_ssa_range_cache (FILE *f);
+
+bool get_global_ssa_range (irange& r, tree name);
+void set_global_ssa_range (tree name, const irange&r);
+void clear_global_ssa_range (tree name);
+
+#endif /* GCC_SSA_RANGE_GLOBAL_H  */

gcc/ssa-range-stmt.c

@@ -0,0 +1,308 @@
+/* SSA range statement summary.
+   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-stmt.h"
+
+
+/* Validate that the statement and all operands of this expression are
+   operable on iranges. If it is valid, set the stmt pointer.  */
+void
+range_stmt::validate_stmt (gimple *s)
+{
+  // Check for supported statements
+  switch (gimple_code (s))
+    {
+      case GIMPLE_COND:
+      case GIMPLE_ASSIGN:
+	g = s;
+        break;
+
+      default:
+        g = NULL;
+    }
+
+  // Must have a ranger operation handler as well.
+  if (g && handler ())
+    {
+      // Now verify all the operanmds are compatible
+      tree op1 = operand1 ();
+      tree op2 = operand2 ();
+      tree ssa1 = valid_irange_ssa (op1);
+      tree ssa2 = valid_irange_ssa (op2);
+
+      if (ssa1 || (TREE_CODE (op1) == INTEGER_CST && !TREE_OVERFLOW (op1))) 
+	{
+	  if (!op2)
+	   return;
+	  if (ssa2 || (TREE_CODE (op2) == INTEGER_CST && !TREE_OVERFLOW (op2)))
+	   return;
+	}
+    }
+  g = NULL;
+}
+
+
+/* Return TRUE if CODE with operands of type TYPE is a boolean
+   evaluation.  These are important to identify as both sides of a logical
+   binary expression must be evaluated in order to calculate a range.  */
+bool
+range_stmt::logical_expr_p () const
+{
+  /* Look for boolean and/or condition.  */
+  switch (get_code ())
+    {
+      case TRUTH_AND_EXPR:
+      case TRUTH_OR_EXPR:
+        return true;
+
+      case BIT_AND_EXPR:
+      case BIT_IOR_EXPR:
+        if (types_compatible_p (TREE_TYPE (operand1 ()), boolean_type_node))
+	  return true;
+	break;
+
+      default:
+        break;
+    }
+  return false;
+}
+
+
+/* Evaluate a binary logical expression given true and false ranges for each
+   of the operands. Base the result on the value in the LHS.  */
+bool
+range_stmt::fold_logical (irange& r, const irange& lhs, const irange& op1_true,
+			  const irange& op1_false, const irange& op2_true,
+			  const irange& op2_false) const
+{
+  gcc_checking_assert (logical_expr_p ());
+ 
+  /* If the LHS can be TRUE OR FALSE, then both need to be evaluated and
+     combined, otherwise any range restrictions that have been determined
+     leading up to this point would be lost.  */
+  if (!wi::eq_p (lhs.lower_bound(), lhs.upper_bound()))
+    {
+      irange r1;
+      irange bool_zero (boolean_type_node, 0, 0);
+      irange bool_one (boolean_type_node, 1, 1);
+      if (fold_logical (r1, bool_zero, op1_true, op1_false, op2_true,
+			op2_false) &&
+	  fold_logical (r, bool_one, op1_true, op1_false, op2_true, op2_false))
+	{
+	  r.union_ (r1);
+	  return true;
+	}
+      return false;
+
+    }
+
+  /* Now combine based on whether the result is TRUE or FALSE.  */
+  switch (get_code ())
+    {
+
+      /* A logical operation on two ranges is executed with operand ranges that
+	 have been determined for both a TRUE and FALSE result..
+	 Assuming x_8 is an unsigned char:
+		b_1 = x_8 < 20
+		b_2 = x_8 > 5
+	 if we are looking for the range of x_8, the operand ranges will be:
+	 will be: 
+	 b_1 TRUE	x_8 = [0, 19]
+	 b_1 FALSE  	x_8 = [20, 255]
+	 b_2 TRUE 	x_8 = [6, 255]
+	 b_2 FALSE	x_8 = [0,5]. */
+	       
+      /*	c_2 = b_1 && b_2
+	 The result of an AND operation with a TRUE result is the intersection
+	 of the 2 TRUE ranges, [0,19] intersect [6,255]  ->   [6, 19]. */
+      case TRUTH_AND_EXPR:
+      case BIT_AND_EXPR:
+        if (!lhs.zero_p ())
+	  r = irange_intersect (op1_true, op2_true);
+	else
+	  {
+	    /* The FALSE side is the union of the other 3 cases.  */
+	    irange ff = irange_intersect (op1_false, op2_false);
+	    irange tf = irange_intersect (op1_true, op2_false);
+	    irange ft = irange_intersect (op1_false, op2_true);
+	    r = irange_union (ff, tf);
+	    r.union_ (ft);
+	  }
+        break;
+
+      /* 	c_2 = b_1 || b_2
+	 An OR operation will only take the FALSE path if both operands are
+	 false, so [20, 255] intersect [0, 5] is the union: [0,5][20,255].  */
+      case TRUTH_OR_EXPR:
+      case BIT_IOR_EXPR:
+        if (lhs.zero_p ())
+	  r = irange_intersect (op1_false, op2_false);
+	else
+	  {
+	    /* The TRUE side of the OR operation will be the union of the other
+	       three combinations.  */
+	    irange tt = irange_intersect (op1_true, op2_true);
+	    irange tf = irange_intersect (op1_true, op2_false);
+	    irange ft = irange_intersect (op1_false, op2_true);
+	    r = irange_union (tt, tf);
+	    r.union_ (ft);
+	  }
+	break;
+
+      default:
+        gcc_unreachable ();
+    }
+
+  return true;
+}
+
+/* This method will attempt to resolve a unary expression with value R1 to
+   a range.  If the expression can be resolved, true is returned, and the
+   range is returned in RES.  */
+
+bool
+range_stmt::fold (irange &res, const irange& r1) const
+{
+  irange r2;
+  tree lhs = gimple_get_lhs (g);
+  /* Single ssa operations require the LHS type as the second range.  */
+  if (lhs)
+    r2.set_range_for_type (TREE_TYPE (lhs));
+  else
+    r2.clear (r1.get_type ());
+
+  return handler()->fold_range (res, r1, r2);
+}
+
+/* This method will attempt to resolve a binary expression with operand
+   values R1 tnd R2 to a range.  If the expression can be resolved, true is
+   returned, and the range is returned in RES.  */
+
+bool
+range_stmt::fold (irange &res, const irange& r1, const irange& r2) const
+{
+  // Make sure this isnt a unary operation being passed a second range.
+  gcc_assert (operand2 ());
+  return handler() ->fold_range (res, r1, r2);
+}
+
+/* This method will evaluate a range for the operand of a unary expression
+   given a range for the LHS of the expression in LHS_RANGE. If it can be
+   evaluated, TRUE is returned and the resulting range returned in RES.  */
+bool
+range_stmt::op1_irange (irange& r, const irange& lhs_range) const
+{  
+  irange type_range;
+  if (lhs_range.empty_p ())
+    {
+      r.clear (TREE_TYPE (operand1 ()));
+      return true;
+    }
+  type_range.set_range_for_type (TREE_TYPE (operand1 ()));
+  return handler ()->op1_irange (r, lhs_range, type_range);
+}
+
+/* This method will evaluate a range for operand 1 of a binary expression
+   given a range for the LHS in LHS_RANGE and a range for operand 2 in
+   OP2_RANGE. If it can be evaluated, TRUE is returned and the resulting
+   range returned in RES.  */
+bool
+range_stmt::op1_irange (irange& r, const irange& lhs_range,
+			const irange& op2_range) const
+{  
+  gcc_assert (operand2 () != NULL);
+  if (op2_range.empty_p () || lhs_range.empty_p ())
+    {
+      r.clear (op2_range.get_type ());
+      return true;
+    }
+  return handler ()->op1_irange (r, lhs_range, op2_range);
+}
+
+/* This method will evaluate a range for operand 2 of a binary expression
+   given a range for the LHS in LHS_RANGE and a range for operand 1 in
+   OP1_RANGE. If it can be evaluated, TRUE is returned and the resulting
+   range returned in RES.  */
+bool
+range_stmt::op2_irange (irange& r, const irange& lhs_range,
+			const irange& op1_range) const
+{  
+  if (op1_range.empty_p () || lhs_range.empty_p ())
+    {
+      r.clear (op1_range.get_type ());
+      return true;
+    }
+  return handler ()->op2_irange (r, lhs_range, op1_range);
+}
+
+/* This method will dump the internal state of the statement summary.  */
+void
+range_stmt::dump (FILE *f) const
+{
+  tree lhs = gimple_get_lhs (g);
+  tree op1 = operand1 ();
+  tree op2 = operand2 ();
+
+  if (lhs)
+    {
+      print_generic_expr (f, lhs, TDF_SLIM);
+      fprintf (f, " = ");
+    }
+
+  if (!op2)
+    handler ()->dump (f);
+
+  print_generic_expr (f, op1, TDF_SLIM);
+
+  if (op2)
+    {
+      handler ()->dump (f);
+      print_generic_expr (f, op2, TDF_SLIM);
+    }
+
+}
+
+
+

gcc/ssa-range-stmt.h

@@ -0,0 +1,175 @@
+/* Header file for ssa-range generator stmt summary.
+   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_STMT_H
+#define GCC_SSA_RANGE_STMT_H
+
+#include "range.h"
+#include "range-op.h"
+
+/* This class is used summarize expressions that are supported by the
+   irange_operator class, and provide an interface to the operators on
+   the expression.  
+
+   The contents of the stmt are abstracted away from gimple (or any other IL)
+
+   The expression or its operands can be resolved to a range if 2 of the
+   3 operands have ranges supplied for them. 
+   
+   This class is not meant to be cached in any way, just utilized within the
+   range engine to communicate required components of an expression.  */
+
+
+class range_stmt
+{
+private:
+  gimple *g;
+  void validate_stmt (gimple *s);
+  class irange_operator *handler() const;
+  tree_code get_code () const;
+public:
+  range_stmt ();
+  range_stmt (gimple *stmt);
+  range_stmt &operator= (gimple *stmt);
+
+  bool valid () const;
+  operator gimple *() const;
+
+  tree operand1 () const;
+  tree operand2 () const;
+  tree ssa_operand1 () const;
+  tree ssa_operand2 () const;
+
+  bool fold (irange& res, const irange& r1) const;
+  bool op1_irange (irange& r, const irange& lhs_range) const;
+
+  bool fold (irange& res, const irange& r1, const irange& r2) const;
+  bool op1_irange (irange& r, const irange& lhs_range,
+		   const irange& op2_range) const;
+  bool op2_irange (irange& r, const irange& lhs_range,
+		   const irange& op1_range) const;
+
+  bool logical_expr_p () const;
+  bool fold_logical (irange& r, const irange& lhs, const irange& op1_true,
+		     const irange& op1_false, const irange& op2_true,
+		     const irange& op2_false) const;
+
+  void dump (FILE *f) const;
+};
+
+
+/* Initialize a range statement to invalid.  */
+inline
+range_stmt::range_stmt ()
+{
+  g = NULL;
+}
+
+/* Initialize a range statement from gimple statement S.  */
+inline 
+range_stmt::range_stmt (gimple *s)
+{
+  validate_stmt (s);
+}
+
+/* Initialize a range statement from gimple statement S.  */
+inline range_stmt&
+range_stmt::operator= (gimple *s)
+{
+  validate_stmt (s);
+  return *this;
+}
+
+/* Return true is this is a valid range summary.  */
+inline bool
+range_stmt::valid () const
+{
+  return g != NULL;
+}
+
+inline tree_code
+range_stmt::get_code () const
+{
+  return gimple_expr_code (g);
+}
+
+inline tree
+range_stmt::operand1 () const
+{
+  switch (gimple_code (g))
+    {
+      case GIMPLE_COND:
+        return gimple_cond_lhs (g);
+      case GIMPLE_ASSIGN:
+        return gimple_assign_rhs1 (g);
+      default:
+        break;
+    }
+  return NULL;
+}
+
+inline tree
+range_stmt::operand2 () const
+{
+  switch (gimple_code (g))
+    {
+      case GIMPLE_COND:
+        return gimple_cond_rhs (g);
+      case GIMPLE_ASSIGN:
+        if (gimple_num_ops (g) >= 3)
+	  return gimple_assign_rhs2 (g);
+	else
+	  return NULL;
+      default:
+        break;
+    }
+  return NULL;
+}
+
+inline tree
+range_stmt::ssa_operand1() const
+{
+  tree op1 = operand1 ();
+  if (op1 && TREE_CODE (op1) == SSA_NAME)
+    return op1;
+  return NULL_TREE;
+}
+
+inline tree
+range_stmt::ssa_operand2 () const
+{
+  tree op2 = operand2 ();
+  if (op2 && TREE_CODE (op2) == SSA_NAME)
+    return op2;
+  return NULL_TREE;
+}
+
+inline irange_operator *
+range_stmt::handler () const
+{
+  return irange_op_handler (get_code ());
+}
+
+inline 
+range_stmt::operator gimple *() const
+{
+  return g;
+}
+#endif /* GCC_SSA_RANGE_STMT_H */

gcc/ssa-range.c

@@ -0,0 +1,805 @@
+/* On-demand ssa range generator.
+   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 "domwalk.h"
+#include "ssa-range.h"
+#include "ssa-range-global.h"
+
+
+class ssa_block_ranges
+{
+private:
+  vec<irange_storage *> tab;
+  irange_storage *type_range;
+  const_tree type;
+public:
+  ssa_block_ranges (tree t);
+  ~ssa_block_ranges ();
+
+  void set_bb_range (const basic_block bb, const irange &r);
+  void set_bb_range_for_type (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);
+};
+
+ssa_block_ranges::ssa_block_ranges (tree t)
+{
+  irange tr;
+  gcc_assert (TYPE_P (t));
+  type = t;
+
+  tab.create (0);
+  tab.safe_grow_cleared (last_basic_block_for_fn (cfun));
+
+  tr.set_range_for_type (t);
+  type_range = irange_storage::ggc_alloc_init (tr);
+
+  tab[ENTRY_BLOCK_PTR_FOR_FN (cfun)->index] = type_range;
+}
+
+ssa_block_ranges::~ssa_block_ranges ()
+{
+  tab.release ();
+}
+
+void
+ssa_block_ranges::set_bb_range (const basic_block bb, const irange& r)
+{
+  irange_storage *m = tab[bb->index];
+
+  if (m && m != type_range)
+    m->set_irange (r);
+  else
+    m = irange_storage::ggc_alloc_init (r);
+
+  tab[bb->index] = m;
+}
+
+void
+ssa_block_ranges::set_bb_range_for_type (const basic_block bb)
+{
+  tab[bb->index] = type_range;
+}
+
+
+bool
+ssa_block_ranges::get_bb_range (irange& r, const basic_block bb)
+{
+  irange_storage *m = tab[bb->index];
+  if (m)
+    {
+      r.set_range (m, type);
+      return true;
+    }
+  return false;
+}
+
+
+// Returns true if a range is present
+bool
+ssa_block_ranges::bb_range_p (const basic_block bb)
+{
+  return tab[bb->index] != NULL;
+}
+
+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);
+      }
+}
+
+// -------------------------------------------------------------------------
+
+class block_range_cache
+{
+private:
+  vec<ssa_block_ranges *> ssa_ranges;
+public:
+  block_range_cache ();
+  ~block_range_cache ();
+  ssa_block_ranges& get_block_ranges (tree name);
+
+  void dump (FILE *f);
+};
+
+
+
+block_range_cache::block_range_cache ()
+{
+  ssa_ranges.create (0);
+  ssa_ranges.safe_grow_cleared (num_ssa_names);
+}
+
+block_range_cache::~block_range_cache ()
+{
+  unsigned x;
+  for (x = 0; x < ssa_ranges.length (); ++x)
+    {
+      if (ssa_ranges[x])
+	delete ssa_ranges[x];
+    }
+  ssa_ranges.release ();
+}
+
+ssa_block_ranges&
+block_range_cache::get_block_ranges (tree name)
+{
+  unsigned v = SSA_NAME_VERSION (name);
+  if (!ssa_ranges[v])
+    ssa_ranges[v] = new ssa_block_ranges (TREE_TYPE (name));
+
+  return *(ssa_ranges[v]);
+}
+
+void
+block_range_cache::dump (FILE *f)
+{
+  unsigned x;
+  for (x = 0; x < num_ssa_names; ++x)
+    {
+      if (ssa_ranges[x])
+        {
+	  fprintf (f, " Ranges for ");
+	  print_generic_expr (f, ssa_name (x), 0);
+	  fprintf (f, ":\n");
+	  ssa_ranges[x]->dump (f);
+	}
+    }
+  
+}
+// -------------------------------------------------------------------------
+
+path_ranger::path_ranger () 
+{
+  block_cache = new block_range_cache ();
+}
+
+path_ranger::~path_ranger () 
+{
+  delete block_cache;
+}
+
+
+void
+path_ranger::range_for_bb (irange &r, tree name, basic_block bb,
+			   basic_block def_bb)
+{
+  bool res;
+  determine_block (name, bb, def_bb);
+  res = block_cache->get_block_ranges (name).get_bb_range (r, bb);
+  gcc_assert (res);
+}
+
+bool
+path_ranger::path_range_entry (irange& r, tree name, basic_block bb)
+{
+  gimple *def_stmt;
+  basic_block def_bb = NULL;
+
+  if (!valid_irange_ssa (name))
+    return false;
+
+  def_stmt = SSA_NAME_DEF_STMT (name);
+  if (def_stmt)
+    def_bb = gimple_bb (def_stmt);;
+
+  if (!def_bb)
+    def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
+
+  /* Start with any known range.  */
+  get_global_ssa_range (r, name);
+
+  /* If its defined in this basic block, then there is no range on entry,
+     otherwise, go figure out what is known in predecessor blocks.  */
+  if (def_bb != bb)
+    {
+      irange block_range;
+      range_for_bb (block_range, name, bb, def_bb);
+      r.intersect (block_range);
+    }
+
+  return true;
+}
+
+
+/* Known range on an edge on the path back to the DEF of name.  */
+bool
+path_ranger::path_range_edge (irange& r, tree name, edge e)
+{
+  basic_block bb = e->src;
+
+  if (!valid_irange_ssa (name))
+    return false;
+
+  /* Get an initial range for NAME.  */
+  
+  gimple *stmt = SSA_NAME_DEF_STMT (name);
+  if (stmt && gimple_bb (stmt) == e->src)
+    {
+      /* If it is in this block, evaluate it.  */
+      if (!path_range_stmt (r, stmt))
+        r.set_range (name);
+    }
+  else
+    /* The name comes from outside this block, so evaluate it's value on
+       entry to the block.  */
+    if (!path_range_entry (r, name, bb))
+      error (" Why can't we get a live on entry range? ");
+
+  /* Now intersect it with what NAME evaluates to on this edge.  */
+  irange edge_range;
+  if (range_on_edge (edge_range, name, e))
+    {
+      normalize_bool_type (edge_range, r);
+      r.intersect (edge_range);
+    }
+  return true;
+
+}
+
+void
+path_ranger::determine_block (tree name, basic_block bb, basic_block def_bb)
+{
+  edge_iterator ei;
+  edge e;
+  irange er;
+  irange block_result;
+
+  if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
+      || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
+      || bb == def_bb)
+    return;
+
+  /* If the block cache is set, then we've already visited this block.  */
+  if (block_cache->get_block_ranges (name).bb_range_p (bb))
+    return;
+
+  /* Avoid infinite recursion by marking this block as calculated.  */
+  block_cache->get_block_ranges (name).set_bb_range_for_type (bb);
+
+  /* Visit each predecessor to resolve them.  */
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      determine_block (name, e->src, def_bb);
+    }
+
+  block_result.clear (TREE_TYPE (name));
+  /* Now Union all the ranges on the incoming edges.  */
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      irange pred_range;
+      basic_block src = e->src;
+      // Should be using range_on_def??? or something.
+      if (src == def_bb)
+        get_global_ssa_range (pred_range, name);
+      else
+        {
+	  bool res;
+	  res = block_cache->get_block_ranges (name).get_bb_range (pred_range,
+								   src);
+	  gcc_assert (res);
+	}
+
+      if (range_on_edge (er, name, e))
+        {
+	  pred_range.intersect (er);
+	  er.intersect (pred_range);
+	}
+
+      block_result.union_ (pred_range);
+
+      if (block_result.range_for_type_p ())
+        break;
+    }
+
+  if (block_result.range_for_type_p ())
+    block_cache->get_block_ranges (name).set_bb_range_for_type (bb);
+  else
+    block_cache->get_block_ranges (name).set_bb_range (bb, block_result);
+}
+
+
+bool
+path_ranger::process_phi (irange &r, gphi *phi)
+{
+  tree phi_def = gimple_phi_result (phi);
+  unsigned x;
+
+  if (!valid_irange_ssa (phi_def))
+    return false;
+
+  // If this node has already been processed, just return it.
+  if (get_global_ssa_range (r, phi_def))
+    return true;
+
+  // Avoid infinite recursion by initializing global cache 
+  r.set_range (phi_def);
+  set_global_ssa_range (phi_def, r);
+ 
+  // And start with an empty range, unioning in each areument's range.
+  r.clear (TREE_TYPE (phi_def));
+  for (x = 0; x < gimple_phi_num_args (phi); x++)
+    {
+      irange arg_range;
+      tree arg = gimple_phi_arg_def (phi, x);
+      edge e = gimple_phi_arg_edge (phi, x);
+      if (!path_range_edge (arg_range, arg, e))
+	if (!get_operand_range (arg_range, arg))
+	  return false;
+
+      normalize_bool_type (r, arg_range);
+      r.union_ (arg_range);
+      if (r.range_for_type_p ())
+	break;
+    }
+
+  set_global_ssa_range (phi_def, r);
+  return true;
+}
+
+
+bool
+path_ranger::path_range_stmt (irange& r, gimple *g)
+{
+  tree name = gimple_get_lhs (g);
+  irange range_op1, range_op2;
+  range_stmt rn;
+  basic_block bb = gimple_bb (g);
+  bool res;
+
+  if (is_a <gphi *> (g))
+    {
+      gphi *phi = as_a <gphi *> (g);
+      return process_phi (r, phi);
+    }
+ 
+  // Not all statements have a LHS.  */
+  if (name)
+    {
+      // If this STMT has already been processed, return that value. 
+      if (get_global_ssa_range (r, name))
+	return true;
+     
+      // avoid infinite recursion by initializing global cache 
+      r.set_range (name);
+      set_global_ssa_range (name, r);
+    }
+
+  rn = g;
+  if (!rn.valid ())
+    return false;
+
+  if (!path_get_operand (range_op1, rn.operand1 (), bb))
+    return false;
+    
+  // If this is a unary operation, call fold now.  
+  if (!rn.operand2 ())
+    res = rn.fold (r, range_op1);
+  else
+    {
+
+      if (!path_get_operand (range_op2, rn.operand2 (), bb))
+	return false;
+
+      normalize_bool_type (range_op1, range_op2);
+      res = rn.fold (r, range_op1, range_op2);
+    }
+
+  if (name)
+    {
+      if (res)
+	set_global_ssa_range (name, r);
+      else
+	clear_global_ssa_range (name);
+    }
+  return res;
+}
+
+
+static inline gimple *
+ssa_name_same_bb_p (tree name, basic_block bb)
+{
+  gimple *g = SSA_NAME_DEF_STMT (name);
+  if (!g || gimple_bb (g) != bb)
+   return NULL;
+  return g;
+}
+
+
+/* Determine a range for NAME in basic block BB.
+   If FULL is true, then rescursively call the path ranger to fully evaluate
+   a range for NAME.
+   if FULL is false, then dont go outside the current block to find a best 
+   guess range.
+   if edge E is specified, then only follow E for calculations.  */
+
+bool
+path_ranger::path_get_operand (irange &r, tree name, basic_block bb)
+{
+  if (!valid_irange_ssa (name))
+    return get_operand_range (r, name);
+    
+  // check if the defining statement is in the same block.
+  gimple *s = ssa_name_same_bb_p (name, bb);
+  if (s)
+    {
+      // This means NAME is defined in the same block, simply try to extract 
+      // a range from that statement. 
+      if (!path_range_stmt (r, s))
+	return block_ranger::get_operand_range (r, name);
+      return true;
+    }
+
+  if (path_range_entry (r, name, bb))
+    return true;
+  return block_ranger::get_operand_range (r, name);
+}
+
+bool
+path_ranger::get_operand_range (irange&r, tree op, gimple *s)
+{
+    
+  if (!s)
+    return block_ranger::get_operand_range (r, op, s);
+  else
+    return path_get_operand (r, op, gimple_bb (s));
+}
+
+bool
+path_ranger::path_fold_stmt (irange &r, range_stmt &rn, basic_block bb, edge e)
+{
+  irange range_op1, range_op2;
+
+  if (!rn.ssa_operand1 () || !ssa_name_same_bb_p (rn.ssa_operand1 (), bb) ||
+      !path_range_of_def (range_op1, SSA_NAME_DEF_STMT (rn.ssa_operand1 ()), e))
+    get_operand_range (range_op1, rn.operand1 ());
+
+  // If this is a unary operation, call fold now.  
+  if (!rn.operand2 ())
+    return rn.fold (r, range_op1);
+
+  if (!rn.ssa_operand2 () || !ssa_name_same_bb_p (rn.ssa_operand2 (), bb) ||
+      !path_range_of_def (range_op2,
+			  SSA_NAME_DEF_STMT (rn.ssa_operand2 ()), e))
+    get_operand_range (range_op2, rn.operand2 ());
+
+  normalize_bool_type (range_op1, range_op2);
+  return rn.fold (r, range_op1, range_op2);
+}
+
+// Attempt to evaluate NAME within the basic block it is defined as far
+// as possible. With an edge provided, we must do the calculation on demand
+// since the global cache involves collating ALL the incoming edges.  This
+// can potentially change all the values in the block.
+bool
+path_ranger::path_range_of_def (irange &r, gimple *g, edge e)
+{
+  if (!e)
+    return path_range_of_def (r, g);
+
+  basic_block bb = gimple_bb (g);
+  tree arg;
+
+  /* If an edge is provided, it must be an incoming edge to this BB.  */
+  gcc_assert (e->dest == bb);
+
+  // Note that since we are remaining within BB, we do not attempt to further
+  // evaluate any of the arguments of a PHI at this point.
+  // a recursive call could be made to evaluate any SSA_NAMEs on their
+  // repsective edgesin PATH form, but we leave that as something to look into
+  // later.  For the moment, just pick up any edge information since its cheap.
+  if (is_a <gphi *> (g))
+    {
+      gphi *phi = as_a <gphi *> (g);
+      gcc_assert (e->dest == bb);
+      arg = gimple_phi_arg_def (phi, e->dest_idx);
+      // Pick up anything simple we might know about the incoming edge. 
+	if (!range_on_edge (r, arg, e))
+	  return get_operand_range (r, arg);
+	return true;
+      }
+
+    range_stmt rn(g);
+    if (!rn.valid())
+      return false; 
+    return path_fold_stmt (r, rn, bb, e);
+
+  }
+
+  // Attempt to evaluate NAME within the basic block it is defined as far
+  // as possible. IF a PHI is encountered at the beginning of the block, either
+  // fully evalaute it, or if E is provided, use just the value from that edge.
+  bool
+  path_ranger::path_range_of_def (irange &r, gimple *g)
+  {
+    tree name;
+    basic_block bb = gimple_bb (g);
+    tree arg;
+    irange range_op1, range_op2;
+
+    // Note that since we are remaining within BB, we do not attempt to further
+    // evaluate any of the arguments of a PHI at this point.
+    // a recursive call could be made to evaluate any SSA_NAMEs on their
+    // repsective edgesin PATH form, but we leave that as something to look into
+    // later.  For the moment, just pick up any edge information since its cheap.
+    if (is_a <gphi *> (g))
+      {
+	gphi *phi = as_a <gphi *> (g);
+	tree phi_def = gimple_phi_result (phi);
+	irange tmp;
+	unsigned x;
+	edge e;
+
+	if (!valid_irange_ssa (phi_def))
+	  return false;
+	if (get_global_ssa_range (r, phi_def))
+	  return true;
+
+	// Avoid infinite recursion by initializing global cache 
+	r.set_range (phi_def);
+	set_global_ssa_range (phi_def, r);
+
+	r.clear (TREE_TYPE (phi_def));
+	for (x = 0; x < gimple_phi_num_args (phi); x++)
+	  {
+	    arg = gimple_phi_arg_def (phi, x);
+	    e = gimple_phi_arg_edge (phi, x);
+	    if (!path_range_edge (range_op2, arg, e))
+	      if (!get_operand_range (range_op2, arg))
+		return false;
+
+	    normalize_bool_type (r, range_op2);
+	    r.union_ (range_op2);
+	    if (r.range_for_type_p ())
+	      return true;
+	  }
+
+	set_global_ssa_range (phi_def, r);
+	return true;
+      }
+
+    range_stmt rn(g);
+    if (!rn.valid())
+      return false;
+
+    name = gimple_get_lhs (g);
+
+    /* If there is no LHS, then we are simply folding an expression.  */
+    if (!name)
+      return path_fold_stmt (r, rn, bb);
+
+    if (get_global_ssa_range (r, name))
+      return true;
+
+    // avoid infinite recursion by initializing global cache 
+    r.set_range (name);
+    set_global_ssa_range (name, r);
+
+    bool res = path_fold_stmt (r, rn, bb);
+
+    if (res)
+      set_global_ssa_range (name, r);
+    return res;
+  }
+
+  /* Calculate the known range for NAME on a path of basic blocks in
+     BBS.  If such a range exists, store it in R and return TRUE,
+     otherwise return FALSE.
+
+     DIR is FORWARD if BBS[0] is the definition and the last block is
+     the use.  DIR is REVERSE if the blocks are in reverse order.
+
+     If there is an edge leading into this path that we'd like to take
+     into account, such edge is START_EDGE.  Otherwise, START_EDGE is
+     set to NULL.  */
+
+  bool
+  path_ranger::path_range (irange &r, tree name, const vec<basic_block> &bbs,
+			   enum path_range_direction dir, edge start_edge)
+  {
+    if (bbs.is_empty ())
+      return false;
+
+    /* If the first block defines NAME and it has meaningful range
+       information, use it, otherwise fall back to range for type.
+
+       Note: The first block may not always define NAME because we may
+       have pruned the paths such that the first block (bb1) is just the
+       first block that contains range info (bb99).  For example:
+
+       bb1:
+	 x = 55;
+	 ...
+	 ...
+       bb99:
+	 if (x > blah).
+    */
+    basic_block first_bb = dir == FORWARD ? bbs[0] : bbs[bbs.length () - 1];
+    gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+    if (gimple_bb (def_stmt) == first_bb && start_edge)
+      {
+	if (!path_range_of_def (r, def_stmt, start_edge))
+	  get_global_ssa_range (r, name);
+      }
+    else
+      get_global_ssa_range (r, name);
+
+    if (dir == REVERSE)
+      return path_range_reverse (r, name, bbs);
+
+    for (unsigned i = 1; i < bbs.length (); ++i)
+      {
+	edge e = find_edge (bbs[i - 1], bbs[i]);
+	gcc_assert (e);
+	irange redge;
+	if (range_on_edge (redge, name, e))
+	r.intersect (redge);
+    }
+
+  if (r.range_for_type_p ())
+    return false;
+  return true;
+}
+
+/* The same as above, but handle the case where BBS are a path of
+   basic blocks in reverse order.
+
+   BBS[0] is the USE of NAME.
+   BBS[LEN-1] is the DEF of NAME.  */
+
+bool
+path_ranger::path_range_reverse (irange &r, tree name,
+				 const vec<basic_block> &bbs)
+{
+  for (int i = bbs.length () - 1; i > 0; --i)
+    {
+      edge e = find_edge (bbs[i], bbs[i - 1]);
+      gcc_assert (e);
+      irange redge;
+      if (range_on_edge (redge, name, e))
+	r.intersect (redge);
+    }
+
+  if (r.range_for_type_p ())
+    return false;
+  return true;
+}
+
+void
+path_ranger::dump(FILE *f)
+{
+  block_ranger::dump (f);
+}
+
+
+void
+path_ranger::exercise (FILE *output)
+{
+
+  basic_block bb;
+  irange range;
+
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      unsigned x;
+      edge_iterator ei;
+      edge e;
+      bool printed = false;
+
+      /* This dramatically slows down builds, so only when printing.  */
+      if (output)
+        {
+	  fprintf (output, "----- BB%d -----\n", bb->index);
+	  for (x = 1; x < num_ssa_names; x++)
+	    {
+	      tree name = ssa_name (x);
+	      if (name && path_range_entry (range, name, bb))
+		{
+		  if (output && !range.range_for_type_p ())
+		    {
+		      if (!printed)
+			fprintf (output,"   Ranges on entry :\n");
+		      printed = true;
+		      fprintf (output, "     ");
+		      print_generic_expr (output, name, 0);
+		      fprintf (output, " : ");
+		      range.dump (output);
+		    }
+		}
+	    }
+	  if (printed)
+	    fprintf (output, "\n");
+	  dump_bb (output, bb, 2, 0);
+	  printed = false;
+	}
+
+      FOR_EACH_EDGE (e, ei, bb->succs)
+        {
+	  for (x = 1; x < num_ssa_names; x++)
+	    {
+	      tree name = ssa_name (x);
+	      if (name && range_p (bb, name))
+		{
+		  if (path_range_edge (range, name, e))
+		    {
+		      if (output && !range.range_for_type_p ())
+			{
+			  printed = true;
+			  fprintf (output, "     %d->%d ", e->src->index,
+				   e->dest->index);
+			  if (e->flags & EDGE_TRUE_VALUE)
+			    fprintf (output, " (T) ");
+			  else if (e->flags & EDGE_FALSE_VALUE)
+			    fprintf (output, " (F) ");
+			  else
+			    fprintf (output, "     ");
+			  print_generic_expr (output, name, TDF_SLIM);
+			  fprintf(output, "  \t");
+			  range.dump(output);
+			}
+		    }
+		}
+	    }
+	}
+      if (printed)
+        fprintf (output, "\n");
+
+    }
+
+  if (output)
+    dump (output);
+
+}
+

gcc/ssa-range.h

@@ -0,0 +1,63 @@
+/* Header file for ssa-range generator.
+   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 "ssa-range-bb.h"
+
+/* This class utilizes the basic block GORI map and is used to query the range
+   of SSA_NAMEs across multiple basic blocks and edges.  */
+class path_ranger : public block_ranger
+{
+private:
+  class block_range_cache *block_cache;
+
+  void range_for_bb (irange &r, tree name, basic_block bb, basic_block def_bb);
+  void determine_block (tree name, basic_block bb, basic_block def_bb);
+  bool path_range_reverse (irange &r, tree name, const vec<basic_block> &);
+  bool path_fold_stmt (irange &r, range_stmt &rn, basic_block bb,
+		       edge e = NULL);
+  bool process_phi (irange &r, gphi *phi);
+  bool path_get_operand (irange &r, tree name, basic_block bb);
+protected:
+  virtual bool get_operand_range (irange &r, tree op, gimple *s = NULL);
+public:
+  enum path_range_direction { FORWARD, REVERSE };
+  path_ranger ();
+  ~path_ranger ();
+
+  /* What is the known range of name from its DEF point to edge E.  */
+  bool path_range_edge (irange& r, tree name, edge e);
+  bool path_range_entry (irange& r, tree name, basic_block bb);
+  // Get ive the range of the LHS of the statement.
+  bool path_range_stmt (irange& r, gimple *g);
+
+  bool path_range (irange &r, tree name, const vec<basic_block> &bbs,
+		   enum path_range_direction, edge start_edge = NULL);
+  // Evaluate expression within a BB as much as possible.
+  bool path_range_of_def (irange& r, gimple *g);
+  bool path_range_of_def (irange& r, gimple *g, edge e);
+
+  void dump (FILE *f);
+  void exercise (FILE *f);   /* do a full mapping pass, dump if provided.  */
+};
+
+#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/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" } */
+/* { dg-options "-O2 -fdisable-tree-evrp -fdisable-tree-rvrp -fdump-tree-profile_estimate" } */
 
 extern int global;
 extern int global2;

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-rvrp -fdisable-tree-evrp -fdump-tree-vrp1-details" } */
 
 int
 foo (int a)

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/timevar.def

@@ -152,6 +152,7 @@ DEFTIMEVAR (TV_TREE_CLEANUP_CFG	     , "tree CFG cleanup")
 DEFTIMEVAR (TV_TREE_TAIL_MERGE       , "tree tail merge")
 DEFTIMEVAR (TV_TREE_VRP              , "tree VRP")
 DEFTIMEVAR (TV_TREE_EARLY_VRP        , "tree Early VRP")
+DEFTIMEVAR (TV_TREE_RANGER_VRP       , "tree Ranger VRP")
 DEFTIMEVAR (TV_TREE_COPY_PROP        , "tree copy propagation")
 DEFTIMEVAR (TV_FIND_REFERENCED_VARS  , "tree find ref. vars")
 DEFTIMEVAR (TV_TREE_PTA		     , "tree PTA")

gcc/tree-core.h

@@ -33,7 +33,7 @@ struct function;
 struct real_value;
 struct fixed_value;
 struct ptr_info_def;
-struct range_info_def;
+class irange_storage;
 struct die_struct;
 
 
@@ -1062,9 +1062,6 @@ struct GTY(()) tree_base {
        TRANSACTION_EXPR_OUTER in
 	   TRANSACTION_EXPR
 
-       SSA_NAME_ANTI_RANGE_P in
-	   SSA_NAME
-
        MUST_TAIL_CALL in
 	   CALL_EXPR
 
@@ -1426,6 +1423,7 @@ struct GTY(()) ssa_use_operand_t {
   tree *GTY((skip(""))) use;
 };
 
+class irange;
 struct GTY(()) tree_ssa_name {
   struct tree_typed typed;
 
@@ -1439,8 +1437,8 @@ struct GTY(()) tree_ssa_name {
   union ssa_name_info_type {
     /* Pointer attributes used for alias analysis.  */
     struct GTY ((tag ("0"))) ptr_info_def *ptr_info;
-    /* Value range attributes used for zero/sign extension elimination.  */
-    struct GTY ((tag ("1"))) range_info_def *range_info;
+    /* Value range attributes.  */
+    class GTY ((tag ("1"))) irange_storage *range_info;
   } GTY ((desc ("%1.typed.type ?" \
 		"!POINTER_TYPE_P (TREE_TYPE ((tree)&%1)) : 2"))) info;
 

gcc/tree-data-ref.c

@@ -99,6 +99,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-vrp.h"
 #include "tree-ssanames.h"
 #include "tree-eh.h"
+#include "range.h"
 
 static struct datadep_stats
 {
@@ -720,15 +721,19 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
 		   to be [A, B].  */
 		if (TREE_CODE (tmp_var) != SSA_NAME)
 		  return false;
-		wide_int var_min, var_max;
-		value_range_type vr_type = get_range_info (tmp_var, &var_min,
-							   &var_max);
-		wide_int var_nonzero = get_nonzero_bits (tmp_var);
-		signop sgn = TYPE_SIGN (itype);
-		if (intersect_range_with_nonzero_bits (vr_type, &var_min,
-						       &var_max, var_nonzero,
-						       sgn) != VR_RANGE)
+
+		if (!SSA_NAME_RANGE_INFO (tmp_var))
 		  return false;
+		irange var_range (tmp_var);
+		// irange var_nonzero;
+		// get_nonzero_bits_as_range (var_nonzero, tmp_var);
+		// FIXME: enable after get_nonzero_bits_as_range gets tested.
+		// var_range.intersect (var_nonzero);
+		// if (var_range.empty_p ())
+		//   return false;
+		wide_int var_min = var_range.lower_bound ();
+		wide_int var_max = var_range.upper_bound ();
+		signop sgn = TYPE_SIGN (itype);
 
 		/* See whether the range of OP0 (i.e. TMP_VAR + TMP_OFF)
 		   is known to be [A + TMP_OFF, B + TMP_OFF], with all
@@ -5404,7 +5409,7 @@ dr_step_indicator (struct data_reference *dr, int useful_min)
       /* Get the range of values that the unconverted step actually has.  */
       wide_int step_min, step_max;
       if (TREE_CODE (step) != SSA_NAME
-	  || get_range_info (step, &step_min, &step_max) != VR_RANGE)
+	  || !get_range_info (step, &step_min, &step_max))
 	{
 	  step_min = wi::to_wide (TYPE_MIN_VALUE (type));
 	  step_max = wi::to_wide (TYPE_MAX_VALUE (type));

gcc/tree-pass.h

@@ -450,6 +450,7 @@ extern gimple_opt_pass *make_pass_check_data_deps (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_copy_prop (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_isolate_erroneous_paths (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_early_vrp (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_ranger_vrp (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_vrp (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_uncprop (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_return_slot (gcc::context *ctxt);

gcc/tree-scalar-evolution.c

@@ -3157,7 +3157,7 @@ iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step)
     base_min = base_max = wi::to_wide (base);
   else if (TREE_CODE (base) == SSA_NAME
 	   && INTEGRAL_TYPE_P (TREE_TYPE (base))
-	   && get_range_info (base, &base_min, &base_max) == VR_RANGE)
+	   && get_range_info (base, &base_min, &base_max))
     ;
   else
     return true;
@@ -3166,7 +3166,7 @@ iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step)
     step_min = step_max = wi::to_wide (step);
   else if (TREE_CODE (step) == SSA_NAME
 	   && INTEGRAL_TYPE_P (TREE_TYPE (step))
-	   && get_range_info (step, &step_min, &step_max) == VR_RANGE)
+	   && get_range_info (step, &step_min, &step_max))
     ;
   else
     return true;

gcc/tree-ssa-copy.c

@@ -558,8 +558,8 @@ fini_copy_prop (void)
 		   && !SSA_NAME_RANGE_INFO (copy_of[i].value)
 		   && var_bb == copy_of_bb)
 	    duplicate_ssa_name_range_info (copy_of[i].value,
-					   SSA_NAME_RANGE_TYPE (var),
-					   SSA_NAME_RANGE_INFO (var));
+					   SSA_NAME_RANGE_INFO (var),
+					   TREE_TYPE (var));
 	}
     }
 

gcc/tree-ssa-loop-niter.c

@@ -226,7 +226,7 @@ refine_value_range_using_guard (tree type, tree var,
     }
   else if (TREE_CODE (varc1) == SSA_NAME
 	   && INTEGRAL_TYPE_P (type)
-	   && get_range_info (varc1, &minv, &maxv) == VR_RANGE)
+	   && get_range_info (varc1, &minv, &maxv))
     {
       gcc_assert (wi::le_p (minv, maxv, sgn));
       wi::to_mpz (minv, minc1, sgn);
@@ -348,8 +348,6 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off,
   int cnt = 0;
   mpz_t minm, maxm;
   basic_block bb;
-  wide_int minv, maxv;
-  enum value_range_type rtype = VR_VARYING;
 
   /* If the expression is a constant, we know its value exactly.  */
   if (integer_zerop (var))
@@ -369,7 +367,8 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off,
       gphi_iterator gsi;
 
       /* Either for VAR itself...  */
-      rtype = get_range_info (var, &minv, &maxv);
+      wide_int minv, maxv;
+      bool have_range = get_range_info (var, &minv, &maxv);
       /* Or for PHI results in loop->header where VAR is used as
 	 PHI argument from the loop preheader edge.  */
       for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
@@ -377,12 +376,11 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off,
 	  gphi *phi = gsi.phi ();
 	  wide_int minc, maxc;
 	  if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var
-	      && (get_range_info (gimple_phi_result (phi), &minc, &maxc)
-		  == VR_RANGE))
+	      && get_range_info (gimple_phi_result (phi), &minc, &maxc))
 	    {
-	      if (rtype != VR_RANGE)
+	      if (!have_range)
 		{
-		  rtype = VR_RANGE;
+		  have_range = true;
 		  minv = minc;
 		  maxv = maxc;
 		}
@@ -396,7 +394,7 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off,
 		     involved.  */
 		  if (wi::gt_p (minv, maxv, sgn))
 		    {
-		      rtype = get_range_info (var, &minv, &maxv);
+		      have_range = get_range_info (var, &minv, &maxv);
 		      break;
 		    }
 		}
@@ -404,17 +402,17 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off,
 	}
       mpz_init (minm);
       mpz_init (maxm);
-      if (rtype != VR_RANGE)
-	{
-	  mpz_set (minm, min);
-	  mpz_set (maxm, max);
-	}
-      else
+      if (have_range)
 	{
 	  gcc_assert (wi::le_p (minv, maxv, sgn));
 	  wi::to_mpz (minv, minm, sgn);
 	  wi::to_mpz (maxv, maxm, sgn);
 	}
+      else
+	{
+	  mpz_set (minm, min);
+	  mpz_set (maxm, max);
+	}
       /* Now walk the dominators of the loop header and use the entry
 	 guards to refine the estimates.  */
       for (bb = loop->header;
@@ -3225,7 +3223,7 @@ record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple *stmt,
       if (TREE_CODE (orig_base) == SSA_NAME
 	  && TREE_CODE (high) == INTEGER_CST
 	  && INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
-	  && (get_range_info (orig_base, &min, &max) == VR_RANGE
+	  && (get_range_info (orig_base, &min, &max)
 	      || get_cst_init_from_scev (orig_base, &max, false))
 	  && wi::gts_p (wi::to_wide (high), max))
 	base = wide_int_to_tree (unsigned_type, max);
@@ -3243,7 +3241,7 @@ record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple *stmt,
       if (TREE_CODE (orig_base) == SSA_NAME
 	  && TREE_CODE (low) == INTEGER_CST
 	  && INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
-	  && (get_range_info (orig_base, &min, &max) == VR_RANGE
+	  && (get_range_info (orig_base, &min, &max)
 	      || get_cst_init_from_scev (orig_base, &min, true))
 	  && wi::gts_p (min, wi::to_wide (low)))
 	base = wide_int_to_tree (unsigned_type, min);
@@ -4486,7 +4484,6 @@ scev_var_range_cant_overflow (tree var, tree step, struct loop *loop)
 {
   tree type;
   wide_int minv, maxv, diff, step_wi;
-  enum value_range_type rtype;
 
   if (TREE_CODE (step) != INTEGER_CST || !INTEGRAL_TYPE_P (TREE_TYPE (var)))
     return false;
@@ -4497,8 +4494,7 @@ scev_var_range_cant_overflow (tree var, tree step, struct loop *loop)
   if (!def_bb || !dominated_by_p (CDI_DOMINATORS, loop->latch, def_bb))
     return false;
 
-  rtype = get_range_info (var, &minv, &maxv);
-  if (rtype != VR_RANGE)
+  if (!get_range_info (var, &minv, &maxv))
     return false;
 
   /* VAR is a scev whose evolution part is STEP and value range info

gcc/tree-ssa-phiopt.c

@@ -1159,11 +1159,11 @@ value_replacement (basic_block cond_bb, basic_block middle_bb,
 	{
 	  /* If available, we can use VR of phi result at least.  */
 	  tree phires = gimple_phi_result (phi);
-	  struct range_info_def *phires_range_info
+	  irange_storage *phires_range_info
 	    = SSA_NAME_RANGE_INFO (phires);
 	  if (phires_range_info)
-	    duplicate_ssa_name_range_info (lhs, SSA_NAME_RANGE_TYPE (phires),
-					   phires_range_info);
+	    duplicate_ssa_name_range_info (lhs, phires_range_info,
+					   TREE_TYPE (phires));
 	}
       gimple_stmt_iterator gsi_from;
       for (int i = prep_cnt - 1; i >= 0; --i)

gcc/tree-ssa-pre.c

@@ -3113,12 +3113,11 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum,
       && SSA_NAME_RANGE_INFO (expr->u.nary->op[0]))
     {
       wide_int min, max;
-      if (get_range_info (expr->u.nary->op[0], &min, &max) == VR_RANGE
+      if (get_range_info (expr->u.nary->op[0], &min, &max)
 	  && !wi::neg_p (min, SIGNED)
 	  && !wi::neg_p (max, SIGNED))
 	/* Just handle extension and sign-changes of all-positive ranges.  */
-	set_range_info (temp,
-			SSA_NAME_RANGE_TYPE (expr->u.nary->op[0]),
+	set_range_info (temp, VR_RANGE,
 			wide_int_storage::from (min, TYPE_PRECISION (type),
 						TYPE_SIGN (type)),
 			wide_int_storage::from (max, TYPE_PRECISION (type),

gcc/tree-ssa-sccvn.c

@@ -3425,11 +3425,7 @@ set_ssa_val_to (tree from, tree to)
 		{
 		  /* Save old info.  */
 		  if (! VN_INFO (to)->info.range_info)
-		    {
-		      VN_INFO (to)->info.range_info = SSA_NAME_RANGE_INFO (to);
-		      VN_INFO (to)->range_info_anti_range_p
-			= SSA_NAME_ANTI_RANGE_P (to);
-		    }
+		    VN_INFO (to)->info.range_info = SSA_NAME_RANGE_INFO (to);
 		  /* Rather than allocating memory and unioning the info
 		     just clear it.  */
 		  if (dump_file && (dump_flags & TDF_DETAILS))
@@ -4686,11 +4682,7 @@ scc_vn_restore_ssa_info (void)
 	    SSA_NAME_PTR_INFO (name) = VN_INFO (name)->info.ptr_info;
 	  else if (INTEGRAL_TYPE_P (TREE_TYPE (name))
 		   && VN_INFO (name)->info.range_info)
-	    {
-	      SSA_NAME_RANGE_INFO (name) = VN_INFO (name)->info.range_info;
-	      SSA_NAME_ANTI_RANGE_P (name)
-		= VN_INFO (name)->range_info_anti_range_p;
-	    }
+	    SSA_NAME_RANGE_INFO (name) = VN_INFO (name)->info.range_info;
 	}
     }
 }
@@ -5468,8 +5460,8 @@ eliminate_dom_walker::before_dom_children (basic_block b)
 		       && ! VN_INFO_RANGE_INFO (sprime)
 		       && b == sprime_b)
 		duplicate_ssa_name_range_info (sprime,
-					       VN_INFO_RANGE_TYPE (lhs),
-					       VN_INFO_RANGE_INFO (lhs));
+					       VN_INFO_RANGE_INFO (lhs),
+					       TREE_TYPE (lhs));
 	    }
 
 	  /* Inhibit the use of an inserted PHI on a loop header when

gcc/tree-ssa-sccvn.h

@@ -201,9 +201,6 @@ typedef struct vn_ssa_aux
      insertion of such with EXPR as definition is required before
      a use can be created of it.  */
   unsigned needs_insertion : 1;
-
-  /* Whether range-info is anti-range.  */
-  unsigned range_info_anti_range_p : 1;
 } *vn_ssa_aux_t;
 
 enum vn_lookup_kind { VN_NOWALK, VN_WALK, VN_WALKREWRITE };
@@ -263,7 +260,7 @@ vn_valueize (tree name)
 
 /* Get at the original range info for NAME.  */
 
-inline range_info_def *
+inline irange_storage *
 VN_INFO_RANGE_INFO (tree name)
 {
   return (VN_INFO (name)->info.range_info
@@ -271,24 +268,6 @@ VN_INFO_RANGE_INFO (tree name)
 	  : SSA_NAME_RANGE_INFO (name));
 }
 
-/* Whether the original range info of NAME is an anti-range.  */
-
-inline bool
-VN_INFO_ANTI_RANGE_P (tree name)
-{
-  return (VN_INFO (name)->info.range_info
-	  ? VN_INFO (name)->range_info_anti_range_p
-	  : SSA_NAME_ANTI_RANGE_P (name));
-}
-
-/* Get at the original range info kind for NAME.  */
-
-inline value_range_type
-VN_INFO_RANGE_TYPE (tree name)
-{
-  return VN_INFO_ANTI_RANGE_P (name) ? VR_ANTI_RANGE : VR_RANGE;
-}
-
 /* Get at the original pointer info for NAME.  */
 
 inline ptr_info_def *

gcc/tree-ssa-strlen.c

@@ -1810,24 +1810,8 @@ maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi, tree src, tree cnt)
     cntrange[0] = cntrange[1] = wi::to_wide (cnt);
   else if (TREE_CODE (cnt) == SSA_NAME)
     {
-      enum value_range_type rng = get_range_info (cnt, cntrange, cntrange + 1);
-      if (rng == VR_RANGE)
+      if (get_range_info (cnt, cntrange, cntrange + 1))
 	;
-      else if (rng == VR_ANTI_RANGE)
-	{
-	  wide_int maxobjsize = wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node));
-
-	  if (wi::ltu_p (cntrange[1], maxobjsize))
-	    {
-	      cntrange[0] = cntrange[1] + 1;
-	      cntrange[1] = maxobjsize;
-	    }
-	  else
-	    {
-	      cntrange[1] = cntrange[0] - 1;
-	      cntrange[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt)));
-	    }
-	}
       else
 	return false;
     }
@@ -3321,16 +3305,9 @@ strlen_check_and_optimize_stmt (gimple_stmt_iterator *gsi, bool *cleanup_eh)
 			/* Reading a character before the final '\0'
 			   character.  Just set the value range to ~[0, 0]
 			   if we don't have anything better.  */
-			wide_int min, max;
 			tree type = TREE_TYPE (lhs);
-			enum value_range_type vr
-			  = get_range_info (lhs, &min, &max);
-			if (vr == VR_VARYING
-			    || (vr == VR_RANGE
-				&& min == wi::min_value (TYPE_PRECISION (type),
-							 TYPE_SIGN (type))
-				&& max == wi::max_value (TYPE_PRECISION (type),
-							 TYPE_SIGN (type))))
+			irange ir (lhs);
+			if (ir.range_for_type_p ())
 			  set_range_info (lhs, VR_ANTI_RANGE,
 					  wi::zero (TYPE_PRECISION (type)),
 					  wi::zero (TYPE_PRECISION (type)));

gcc/tree-ssanames.c

@@ -336,35 +336,31 @@ set_range_info_raw (tree name, enum value_range_type range_type,
 {
   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
   gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE);
-  range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+  irange_storage *ri = SSA_NAME_RANGE_INFO (name);
   unsigned int precision = TYPE_PRECISION (TREE_TYPE (name));
 
   /* Allocate if not available.  */
   if (ri == NULL)
     {
-      size_t size = (sizeof (range_info_def)
-		     + trailing_wide_ints <3>::extra_size (precision));
-      ri = static_cast<range_info_def *> (ggc_internal_alloc (size));
-      ri->ints.set_precision (precision);
+      ri = irange_storage::ggc_alloc (precision);
       SSA_NAME_RANGE_INFO (name) = ri;
       ri->set_nonzero_bits (wi::shwi (-1, precision));
     }
 
-  /* Record the range type.  */
-  if (SSA_NAME_RANGE_TYPE (name) != range_type)
-    SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE);
-
-  /* Set the values.  */
-  ri->set_min (min);
-  ri->set_max (max);
+  signop sign = TYPE_SIGN (TREE_TYPE (name));
+  irange local (TREE_TYPE (name),
+		wide_int_storage::from (min, precision, sign),
+		wide_int_storage::from (max, precision, sign),
+		range_type == VR_ANTI_RANGE ? irange::INVERSE : irange::PLAIN);
+  ri->set_irange (local);
 
   /* If it is a range, try to improve nonzero_bits from the min/max.  */
   if (range_type == VR_RANGE)
     {
-      wide_int xorv = ri->get_min () ^ ri->get_max ();
+      wide_int xorv = min ^ max;
       if (xorv != 0)
 	xorv = wi::mask (precision - wi::clz (xorv), false, precision);
-      ri->set_nonzero_bits (ri->get_nonzero_bits () & (ri->get_min () | xorv));
+      ri->set_nonzero_bits (ri->get_nonzero_bits () & (min | xorv));
     }
 }
 
@@ -382,7 +378,7 @@ set_range_info (tree name, enum value_range_type range_type,
   if (min == wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type))
       && max == wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
     {
-      range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+      irange_storage *ri = SSA_NAME_RANGE_INFO (name);
       if (ri == NULL)
 	return;
       if (ri->get_nonzero_bits () == -1)
@@ -397,26 +393,28 @@ set_range_info (tree name, enum value_range_type range_type,
 }
 
 
-/* Gets range information MIN, MAX and returns enum value_range_type
-   corresponding to tree ssa_name NAME.  enum value_range_type returned
-   is used to determine if MIN and MAX are valid values.  */
+/* If there is range information available for the given ssa_name
+   NAME, returns TRUE and sets MIN, MAX accordingly.  */
 
-enum value_range_type
+bool
 get_range_info (const_tree name, wide_int *min, wide_int *max)
 {
   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
   gcc_assert (min && max);
-  range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 
   /* Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs
      with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision.  */
-  if (!ri || (GET_MODE_PRECISION (SCALAR_INT_TYPE_MODE (TREE_TYPE (name)))
-	      > 2 * HOST_BITS_PER_WIDE_INT))
-    return VR_VARYING;
+  if (!SSA_NAME_RANGE_INFO (name)
+      // FIXME: ?? Do we need this precision stuff ??
+      || (GET_MODE_PRECISION (SCALAR_INT_TYPE_MODE (TREE_TYPE (name)))
+	  > 2 * HOST_BITS_PER_WIDE_INT))
+    return false;
 
-  *min = ri->get_min ();
-  *max = ri->get_max ();
-  return SSA_NAME_RANGE_TYPE (name);
+  irange ri (name);
+  gcc_assert (ri.valid_p ());
+  *min = ri.lower_bound ();
+  *max = ri.upper_bound ();
+  return true;
 }
 
 /* Set nonnull attribute to pointer NAME.  */
@@ -451,7 +449,7 @@ get_ptr_nonnull (const_tree name)
 /* Change non-zero bits bitmask of NAME.  */
 
 void
-set_nonzero_bits (tree name, const wide_int_ref &mask)
+set_nonzero_bits (tree name, const wide_int &mask)
 {
   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
   if (SSA_NAME_RANGE_INFO (name) == NULL)
@@ -462,7 +460,7 @@ set_nonzero_bits (tree name, const wide_int_ref &mask)
 			  wi::to_wide (TYPE_MIN_VALUE (TREE_TYPE (name))),
 			  wi::to_wide (TYPE_MAX_VALUE (TREE_TYPE (name))));
     }
-  range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+  irange_storage *ri = SSA_NAME_RANGE_INFO (name);
   ri->set_nonzero_bits (mask);
 }
 
@@ -487,13 +485,30 @@ get_nonzero_bits (const_tree name)
       return wi::shwi (-1, precision);
     }
 
-  range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+  irange_storage *ri = SSA_NAME_RANGE_INFO (name);
   if (!ri)
     return wi::shwi (-1, precision);
 
   return ri->get_nonzero_bits ();
 }
 
+/* Similar to above, but return the non-zero bits as an irange in IR.  */
+/* FIXME: This possibly deprecates intersect_range_with_nonzero_bits.  */
+
+void
+get_nonzero_bits_as_range (irange &ir, const_tree name)
+{
+  wide_int nzb = get_nonzero_bits (name);
+  if (nzb == 0)
+    {
+      ir.set_range_for_type (TREE_TYPE (name));
+      ir.clear ();
+      return;
+    }
+  // FIXME: errr, this needs testing.
+  ir = irange (TREE_TYPE (name), wi::clz (nzb), wi::ctz (nzb));
+}
+
 /* Return TRUE is OP, an SSA_NAME has a range of values [0..1], false
    otherwise.
 
@@ -724,29 +739,38 @@ duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
   SSA_NAME_PTR_INFO (name) = new_ptr_info;
 }
 
-/* Creates a duplicate of the range_info_def at RANGE_INFO of type
-   RANGE_TYPE for use by the SSA name NAME.  */
+/* Creates a duplicate of the range info at OLD_RANGE_INFO for use by the
+   SSA name NAME.  */
 void
-duplicate_ssa_name_range_info (tree name, enum value_range_type range_type,
-			       struct range_info_def *range_info)
+duplicate_ssa_name_range_info (tree name, irange_storage *old_range_info,
+			       tree old_type)
 {
-  struct range_info_def *new_range_info;
-
   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
   gcc_assert (!SSA_NAME_RANGE_INFO (name));
 
-  if (!range_info)
+  if (!old_range_info)
     return;
 
   unsigned int precision = TYPE_PRECISION (TREE_TYPE (name));
-  size_t size = (sizeof (range_info_def)
-		 + trailing_wide_ints <3>::extra_size (precision));
-  new_range_info = static_cast<range_info_def *> (ggc_internal_alloc (size));
-  memcpy (new_range_info, range_info, size);
-
-  gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE);
-  SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE);
+  irange_storage *new_range_info = irange_storage::ggc_alloc (precision);
   SSA_NAME_RANGE_INFO (name) = new_range_info;
+  /* If NAME was created with copy_ssa_name_fn(), we may have gotten
+     the TYPE_MAIN_VARIANT for the original type, which may be a
+     different typedef of the original type.  If so, convert the range
+     to be consistent.
+
+     NOTE: I have also seen tree-ssa-pre.c copy the range of an
+     'unsigned long long' onto the range of a 'unsigned long'.  So the
+     two types are not necessarily of the same size.  */
+  if (TREE_TYPE (name) != old_type)
+    {
+      irange ir (old_range_info, old_type);
+      ir.cast (TREE_TYPE (name));
+      new_range_info->set_irange (ir);
+      new_range_info->set_nonzero_bits (old_range_info->get_nonzero_bits ());
+      return;
+    }
+  memcpy (new_range_info, old_range_info, irange_storage::size (precision));
 }
 
 
@@ -767,11 +791,11 @@ duplicate_ssa_name_fn (struct function *fn, tree name, gimple *stmt)
     }
   else
     {
-      struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name);
+      irange_storage *old_range_info = SSA_NAME_RANGE_INFO (name);
 
       if (old_range_info)
-	duplicate_ssa_name_range_info (new_name, SSA_NAME_RANGE_TYPE (name),
-				       old_range_info);
+	duplicate_ssa_name_range_info (new_name,
+				       old_range_info, TREE_TYPE (name));
     }
 
   return new_name;

gcc/tree-ssanames.h

@@ -45,14 +45,12 @@ struct GTY(()) ptr_info_def
   unsigned int misalign;
 };
 
-/* Value range information for SSA_NAMEs representing non-pointer variables.  */
+/* Used bits information for SSA_NAMEs representing non-pointer variables.  */
 
-struct GTY ((variable_size)) range_info_def {
-  /* Minimum, maximum and nonzero bits.  */
-  TRAILING_WIDE_INT_ACCESSOR (min, ints, 0)
-  TRAILING_WIDE_INT_ACCESSOR (max, ints, 1)
-  TRAILING_WIDE_INT_ACCESSOR (nonzero_bits, ints, 2)
-  trailing_wide_ints <3> ints;
+struct GTY ((variable_size)) nonzero_bits_def {
+  /* Mask representing which bits are known to be used in an integer.  */
+  TRAILING_WIDE_INT_ACCESSOR (nonzero_bits, ints, 0)
+  trailing_wide_ints <1> ints;
 };
 
 
@@ -73,10 +71,10 @@ extern void set_range_info_raw (tree, enum value_range_type,
 				const wide_int_ref &,
 				const wide_int_ref &);
 /* Gets the value range from SSA.  */
-extern enum value_range_type get_range_info (const_tree, wide_int *,
-					     wide_int *);
-extern void set_nonzero_bits (tree, const wide_int_ref &);
+extern bool get_range_info (const_tree, wide_int *, wide_int *);
+extern void set_nonzero_bits (tree, const wide_int &);
 extern wide_int get_nonzero_bits (const_tree);
+extern void get_nonzero_bits_as_range (irange &, const_tree);
 extern bool ssa_name_has_boolean_range (tree);
 extern void init_ssanames (struct function *, int);
 extern void fini_ssanames (struct function *);
@@ -97,8 +95,7 @@ extern bool get_ptr_nonnull (const_tree);
 extern tree copy_ssa_name_fn (struct function *, tree, gimple *);
 extern void duplicate_ssa_name_ptr_info (tree, struct ptr_info_def *);
 extern tree duplicate_ssa_name_fn (struct function *, tree, gimple *);
-extern void duplicate_ssa_name_range_info (tree, enum value_range_type,
-					   struct range_info_def *);
+extern void duplicate_ssa_name_range_info (tree, irange_storage *, tree);
 extern void reset_flow_sensitive_info (tree);
 extern void reset_flow_sensitive_info_in_bb (basic_block);
 extern void release_defs (gimple *);

gcc/tree-vect-patterns.c

@@ -2976,7 +2976,7 @@ vect_recog_divmod_pattern (vec<gimple *> *stmts,
 
       wide_int oprnd0_min, oprnd0_max;
       int msb = 1;
-      if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max) == VR_RANGE)
+      if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max))
 	{
 	  if (!wi::neg_p (oprnd0_min, TYPE_SIGN (itype)))
 	    msb = 0;

gcc/tree-vrp.c

@@ -513,6 +513,71 @@ abs_extent_range (value_range *vr, tree min, tree max)
   set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL);
 }
 
+/* Return TRUE if an irange is an ANTI_RANGE.  This is a temporary
+   measure offering backward compatibility with range_info_def, and
+   will go away.  */
+
+static bool
+irange_is_anti_range (irange r)
+{
+  const_tree type = r.get_type ();
+  // Remember: VR_ANTI_RANGE([3,10]) ==> [-MIN,2][11,MAX]
+  unsigned int precision = TYPE_PRECISION (type);
+  wide_int min = wi::min_value (precision, TYPE_SIGN (type));
+  wide_int max = wi::max_value (precision, TYPE_SIGN (type));
+  return (r.num_pairs () == 2
+          && r.lower_bound () == min
+          && r.upper_bound () == max);
+}
+
+/* Convert the range info of an SSA name into VRP's internal
+   value_range representation.  Return VR_RANGE/VR_ANTI_RANGE if range
+   info is available for the SSA name, otherwise VR_VARYING is
+   returned.  MIN/MAX is set if range info is available.
+
+   FIXME: Any use of this function outside of tree-vrp must be
+   converted.  For instance, ipa-prop.c.  */
+
+enum value_range_type
+get_range_info_as_value_range (const_tree ssa, wide_int *min, wide_int *max)
+{
+  if (!SSA_NAME_RANGE_INFO (ssa)
+      || (GET_MODE_PRECISION (SCALAR_INT_TYPE_MODE (TREE_TYPE (ssa)))
+	  > 2 * HOST_BITS_PER_WIDE_INT))
+    return VR_VARYING;
+
+  irange ri (ssa);
+  if (irange_is_anti_range (ri))
+    {
+      irange tmp (ri);
+      tmp.invert ();
+      gcc_assert (!tmp.overflow_p ());
+      if (tmp.num_pairs () != 1)
+       {
+         fprintf (stderr, "Inverse of anti range does not have 2 elements.\n");
+         fprintf (stderr, "Type: ");
+         debug_generic_stmt (const_cast<tree> (ri.get_type ()));
+         fprintf (stderr, "Original anti range:\n");
+         ri.dump ();
+         fprintf (stderr, "\n");
+         fprintf (stderr, "Supposed inverse of anti range:\n");
+         tmp.dump ();
+         fprintf (stderr, "\n");
+         gcc_unreachable ();
+       }
+      *min = tmp.lower_bound ();
+      *max = tmp.upper_bound ();
+      return VR_ANTI_RANGE;
+    }
+
+  /* We chop off any middle ranges, because range_info_def has no use
+     for such granularity.  */
+  *min = ri.lower_bound ();
+  *max = ri.upper_bound ();
+  return VR_RANGE;
+}
+
+
 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes.  */
 
 bool
@@ -5316,9 +5381,10 @@ remove_range_assertions (void)
 		    && all_imm_uses_in_stmt_or_feed_cond (var, stmt,
 							  single_pred (bb)))
 		  {
-		    set_range_info (var, SSA_NAME_RANGE_TYPE (lhs),
-				    SSA_NAME_RANGE_INFO (lhs)->get_min (),
-				    SSA_NAME_RANGE_INFO (lhs)->get_max ());
+		    wide_int min, max;
+		    enum value_range_type rtype
+		      = get_range_info_as_value_range (lhs, &min, &max);
+		    set_range_info (var, rtype, min, max);
 		    maybe_set_nonzero_bits (single_pred_edge (bb), var);
 		  }
 	      }

gcc/tree-vrp.h

@@ -60,6 +60,10 @@ extern void extract_range_from_unary_expr (value_range *vr,
 					   value_range *vr0_,
 					   tree op0_type);
 
+enum value_range_type get_range_info_as_value_range (const_tree ssa,
+						     wide_int *min,
+						     wide_int *max);
+
 extern bool vrp_operand_equal_p (const_tree, const_tree);
 extern enum value_range_type intersect_range_with_nonzero_bits
   (enum value_range_type, wide_int *, wide_int *, const wide_int &, signop);

gcc/tree.c

@@ -13863,7 +13863,6 @@ verify_type (const_tree t)
     }
 }
 
-
 /* Return 1 if ARG interpreted as signed in its precision is known to be
    always positive or 2 if ARG is known to be always negative, or 3 if
    ARG may be positive or negative.  */
@@ -13902,7 +13901,7 @@ get_range_pos_neg (tree arg)
   if (TREE_CODE (arg) != SSA_NAME)
     return 3;
   wide_int arg_min, arg_max;
-  while (get_range_info (arg, &arg_min, &arg_max) != VR_RANGE)
+  while (!get_range_info (arg, &arg_min, &arg_max))
     {
       gimple *g = SSA_NAME_DEF_STMT (arg);
       if (is_gimple_assign (g)
@@ -13912,6 +13911,8 @@ get_range_pos_neg (tree arg)
 	  if (INTEGRAL_TYPE_P (TREE_TYPE (t))
 	      && TYPE_PRECISION (TREE_TYPE (t)) <= prec)
 	    {
+	      /* Narrower value zero extended into wider type
+		 will always result in positive values.  */
 	      if (TYPE_UNSIGNED (TREE_TYPE (t))
 		  && TYPE_PRECISION (TREE_TYPE (t)) < prec)
 		return 1;

gcc/tree.h

@@ -1765,14 +1765,6 @@ extern tree maybe_wrap_with_location (tree, location_t);
 #define SSA_NAME_PTR_INFO(N) \
    SSA_NAME_CHECK (N)->ssa_name.info.ptr_info
 
-/* True if SSA_NAME_RANGE_INFO describes an anti-range.  */
-#define SSA_NAME_ANTI_RANGE_P(N) \
-    SSA_NAME_CHECK (N)->base.static_flag
-
-/* The type of range described by SSA_NAME_RANGE_INFO.  */
-#define SSA_NAME_RANGE_TYPE(N) \
-    (SSA_NAME_ANTI_RANGE_P (N) ? VR_ANTI_RANGE : VR_RANGE)
-
 /* Value range info attributes for SSA_NAMEs of non pointer-type variables.  */
 #define SSA_NAME_RANGE_INFO(N) \
     SSA_NAME_CHECK (N)->ssa_name.info.range_info

gcc/vr-values.c

@@ -127,7 +127,8 @@ vr_values::get_value_range (const_tree var)
 	  else if (INTEGRAL_TYPE_P (TREE_TYPE (sym)))
 	    {
 	      wide_int min, max;
-	      value_range_type rtype = get_range_info (var, &min, &max);
+	      value_range_type rtype
+		= get_range_info_as_value_range (var, &min, &max);
 	      if (rtype == VR_RANGE || rtype == VR_ANTI_RANGE)
 		set_value_range (vr, rtype,
 				 wide_int_to_tree (TREE_TYPE (var), min),
@@ -184,7 +185,7 @@ vr_values::update_value_range (const_tree var, value_range *new_vr)
   if (INTEGRAL_TYPE_P (TREE_TYPE (var)))
     {
       wide_int min, max;
-      value_range_type rtype = get_range_info (var, &min, &max);
+      value_range_type rtype = get_range_info_as_value_range (var, &min, &max);
       if (rtype == VR_RANGE || rtype == VR_ANTI_RANGE)
 	{
 	  tree nr_min, nr_max;
@@ -3813,7 +3814,7 @@ simplify_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
      case innerop was created during substitute-and-fold.  */
   wide_int imin, imax;
   if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop))
-      || get_range_info (innerop, &imin, &imax) != VR_RANGE)
+      || !get_range_info (innerop, &imin, &imax))
     return false;
   innermin = widest_int::from (imin, TYPE_SIGN (TREE_TYPE (innerop)));
   innermax = widest_int::from (imax, TYPE_SIGN (TREE_TYPE (innerop)));