[PATCH 00/16] prange supporting patchset

[PATCH 00/16] prange supporting patchset

[Aldy Hernandez]

In this cycle, we will be contributing ranges for pointers (prange),
to disambiguate pointers from integers in a range.  Initially they
will behave exactly as they do now, with just two integer end points
and a bitmask, but eventually we will track points-to info in a less
hacky manner than what we do with the pointer equivalency class
(pointer_equiv_analyzer).

This first set of patches implements a bunch of little cleanups and
set-ups that will make it easier to drop in prange in a week or two.
The patches in this set are non-intrusive, and don't touch code that
changes much in the release, so they should be safe to push now.

There should be no change in behavior in any of these patches.

All patches have been tested on x86-64 Linux.

Aldy Hernandez (16):
  Make vrange an abstract class.
  Add a virtual vrange destructor.
  Make some Value_Range's explicitly integer.
  Add tree versions of lower and upper bounds to vrange.
  Move bitmask routines to vrange base class.
  Remove GTY support for vrange and derived classes.
  Make fold_cond_with_ops use a boolean type for range_true/range_false.
  Change range_includes_zero_p argument to a reference.
  Verify that reading back from vrange_storage doesn't drop bits.
  Accept a vrange in get_legacy_range.
  Move get_bitmask_from_range out of irange class.
  Make some integer specific ranges generic Value_Range's.
  Accept any vrange in range_includes_zero_p.
  Move print_irange_* out of vrange_printer class.
  Remove range_zero and range_nonzero.
  Callers of irange_bitmask must normalize value/mask pairs.

 gcc/gimple-range-op.cc          |   6 +-
 gcc/gimple-ssa-warn-access.cc   |   4 +-
 gcc/ipa-cp.cc                   |   9 +-
 gcc/ipa-prop.cc                 |  10 +-
 gcc/range-op-mixed.h            |   2 +-
 gcc/range-op-ptr.cc             |  14 +-
 gcc/range-op.cc                 |  20 ++-
 gcc/range.cc                    |  14 --
 gcc/range.h                     |   2 -
 gcc/tree-ssa-ccp.cc             |   1 +
 gcc/tree-ssa-loop-niter.cc      |  16 +-
 gcc/tree-ssa-loop-split.cc      |   6 +-
 gcc/tree-ssa-strlen.cc          |   2 +-
 gcc/value-query.cc              |   4 +-
 gcc/value-range-pretty-print.cc |  83 +++++-----
 gcc/value-range-pretty-print.h  |   2 -
 gcc/value-range-storage.cc      |  20 ++-
 gcc/value-range-storage.h       |   4 -
 gcc/value-range.cc              | 284 ++++++++++++++++----------------
 gcc/value-range.h               | 166 ++++++++-----------
 gcc/vr-values.cc                |   7 +-
 21 files changed, 310 insertions(+), 366 deletions(-)

-- 
2.44.0

[COMMITTED 01/16] Make vrange an abstract class.

[Aldy Hernandez]

Explicitly make vrange an abstract class.  This involves fleshing out
the unsupported_range overrides which we were inheriting by default
from vrange.

gcc/ChangeLog:

	* value-range.cc (unsupported_range::accept): Move down.
 	(vrange::contains_p):  Rename to...
	(unsupported_range::contains_p): ...this.
	(vrange::singleton_p): Rename to...
	(unsupported_range::singleton_p): ...this.
	(vrange::set): Rename to...
	(unsupported_range::set): ...this.
	(vrange::type): Rename to...
	(unsupported_range::type): ...this.
	(vrange::supports_type_p): Rename to...
	(unsupported_range::supports_type_p): ...this.
	(vrange::set_undefined): Rename to...
	(unsupported_range::set_undefined): ...this.
	(vrange::set_varying): Rename to...
	(unsupported_range::set_varying): ...this.
	(vrange::union_): Rename to...
	(unsupported_range::union_): ...this.
	(vrange::intersect): Rename to...
	(unsupported_range::intersect): ...this.
	(vrange::zero_p): Rename to...
	(unsupported_range::zero_p): ...this.
	(vrange::nonzero_p): Rename to...
	(unsupported_range::nonzero_p): ...this.
	(vrange::set_nonzero): Rename to...
	(unsupported_range::set_nonzero): ...this.
	(vrange::set_zero): Rename to...
	(unsupported_range::set_zero): ...this.
	(vrange::set_nonnegative): Rename to...
	(unsupported_range::set_nonnegative): ...this.
	(vrange::fits_p): Rename to...
	(unsupported_range::fits_p): ...this.
	(unsupported_range::operator=): New.
	(frange::fits_p): New.
	* value-range.h (class vrange): Make an abstract class.
	(class unsupported_range): Declare override methods.
---
 gcc/value-range.cc | 62 ++++++++++++++++++++++++++++++----------------
 gcc/value-range.h  | 53 ++++++++++++++++++++++++---------------
 2 files changed, 73 insertions(+), 42 deletions(-)

diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 70375f7abf9..632d77305cc 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -37,12 +37,6 @@ irange::accept (const vrange_visitor &v) const
   v.visit (*this);
 }
 
-void
-unsupported_range::accept (const vrange_visitor &v) const
-{
-  v.visit (*this);
-}
-
 // Convenience function only available for integers and pointers.
 
 wide_int
@@ -86,52 +80,58 @@ debug (const irange_bitmask &bm)
   fprintf (stderr, "\n");
 }
 
-// Default vrange definitions.
+// Definitions for unsupported_range.
+
+void
+unsupported_range::accept (const vrange_visitor &v) const
+{
+  v.visit (*this);
+}
 
 bool
-vrange::contains_p (tree) const
+unsupported_range::contains_p (tree) const
 {
   return varying_p ();
 }
 
 bool
-vrange::singleton_p (tree *) const
+unsupported_range::singleton_p (tree *) const
 {
   return false;
 }
 
 void
-vrange::set (tree min, tree, value_range_kind)
+unsupported_range::set (tree min, tree, value_range_kind)
 {
   set_varying (TREE_TYPE (min));
 }
 
 tree
-vrange::type () const
+unsupported_range::type () const
 {
   return void_type_node;
 }
 
 bool
-vrange::supports_type_p (const_tree) const
+unsupported_range::supports_type_p (const_tree) const
 {
   return false;
 }
 
 void
-vrange::set_undefined ()
+unsupported_range::set_undefined ()
 {
   m_kind = VR_UNDEFINED;
 }
 
 void
-vrange::set_varying (tree)
+unsupported_range::set_varying (tree)
 {
   m_kind = VR_VARYING;
 }
 
 bool
-vrange::union_ (const vrange &r)
+unsupported_range::union_ (const vrange &r)
 {
   if (r.undefined_p () || varying_p ())
     return false;
@@ -145,7 +145,7 @@ vrange::union_ (const vrange &r)
 }
 
 bool
-vrange::intersect (const vrange &r)
+unsupported_range::intersect (const vrange &r)
 {
   if (undefined_p () || r.varying_p ())
     return false;
@@ -164,41 +164,53 @@ vrange::intersect (const vrange &r)
 }
 
 bool
-vrange::zero_p () const
+unsupported_range::zero_p () const
 {
   return false;
 }
 
 bool
-vrange::nonzero_p () const
+unsupported_range::nonzero_p () const
 {
   return false;
 }
 
 void
-vrange::set_nonzero (tree type)
+unsupported_range::set_nonzero (tree type)
 {
   set_varying (type);
 }
 
 void
-vrange::set_zero (tree type)
+unsupported_range::set_zero (tree type)
 {
   set_varying (type);
 }
 
 void
-vrange::set_nonnegative (tree type)
+unsupported_range::set_nonnegative (tree type)
 {
   set_varying (type);
 }
 
 bool
-vrange::fits_p (const vrange &) const
+unsupported_range::fits_p (const vrange &) const
 {
   return true;
 }
 
+unsupported_range &
+unsupported_range::operator= (const vrange &r)
+{
+  if (r.undefined_p ())
+    set_undefined ();
+  else if (r.varying_p ())
+    set_varying (void_type_node);
+  else
+    gcc_unreachable ();
+  return *this;
+}
+
 // Assignment operator for generic ranges.  Copying incompatible types
 // is not allowed.
 
@@ -359,6 +371,12 @@ frange::accept (const vrange_visitor &v) const
   v.visit (*this);
 }
 
+bool
+frange::fits_p (const vrange &) const
+{
+  return true;
+}
+
 // Flush denormal endpoints to the appropriate 0.0.
 
 void
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 9531df56988..e7f61950a24 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -80,21 +80,21 @@ class GTY((user)) vrange
   friend class range_op_handler;
 public:
   virtual void accept (const class vrange_visitor &v) const = 0;
-  virtual void set (tree, tree, value_range_kind = VR_RANGE);
-  virtual tree type () const;
-  virtual bool supports_type_p (const_tree type) const;
-  virtual void set_varying (tree type);
-  virtual void set_undefined ();
-  virtual bool union_ (const vrange &);
-  virtual bool intersect (const vrange &);
-  virtual bool singleton_p (tree *result = NULL) const;
-  virtual bool contains_p (tree cst) const;
-  virtual bool zero_p () const;
-  virtual bool nonzero_p () const;
-  virtual void set_nonzero (tree type);
-  virtual void set_zero (tree type);
-  virtual void set_nonnegative (tree type);
-  virtual bool fits_p (const vrange &r) const;
+  virtual void set (tree, tree, value_range_kind = VR_RANGE) = 0;
+  virtual tree type () const = 0;
+  virtual bool supports_type_p (const_tree type) const = 0;
+  virtual void set_varying (tree type) = 0;
+  virtual void set_undefined () = 0;
+  virtual bool union_ (const vrange &) = 0;
+  virtual bool intersect (const vrange &) = 0;
+  virtual bool singleton_p (tree *result = NULL) const = 0;
+  virtual bool contains_p (tree cst) const = 0;
+  virtual bool zero_p () const = 0;
+  virtual bool nonzero_p () const = 0;
+  virtual void set_nonzero (tree type) = 0;
+  virtual void set_zero (tree type) = 0;
+  virtual void set_nonnegative (tree type) = 0;
+  virtual bool fits_p (const vrange &r) const = 0;
 
   bool varying_p () const;
   bool undefined_p () const;
@@ -401,11 +401,23 @@ public:
   {
     set_undefined ();
   }
-  virtual void set_undefined () final override
-  {
-    m_kind = VR_UNDEFINED;
-  }
-  virtual void accept (const vrange_visitor &v) const override;
+  void set (tree min, tree, value_range_kind = VR_RANGE) final override;
+  tree type () const final override;
+  bool supports_type_p (const_tree) const final override;
+  void set_varying (tree) final override;
+  void set_undefined () final override;
+  void accept (const vrange_visitor &v) const final override;
+  bool union_ (const vrange &r) final override;
+  bool intersect (const vrange &r) final override;
+  bool singleton_p (tree * = NULL) const final override;
+  bool contains_p (tree) const final override;
+  bool zero_p () const final override;
+  bool nonzero_p () const final override;
+  void set_nonzero (tree type) final override;
+  void set_zero (tree type) final override;
+  void set_nonnegative (tree type) final override;
+  bool fits_p (const vrange &) const final override;
+  unsupported_range& operator= (const vrange &r);
 };
 
 // The NAN state as an opaque object.
@@ -507,6 +519,7 @@ public:
   virtual void set_nonzero (tree type) override;
   virtual void set_zero (tree type) override;
   virtual void set_nonnegative (tree type) override;
+  virtual bool fits_p (const vrange &) const override;
   frange& operator= (const frange &);
   bool operator== (const frange &) const;
   bool operator!= (const frange &r) const { return !(*this == r); }
-- 
2.44.0

[COMMITTED 02/16] Add a virtual vrange destructor.

[Aldy Hernandez]

Richi mentioned in PR113476 that it would be cleaner to move the
destructor from int_range to the base class.  Although this isn't
strictly necessary, as there are no users, it is good to future proof
things, and the overall impact is miniscule.

gcc/ChangeLog:

	* value-range.h (vrange::~vrange): New.
	(int_range::~int_range): Make final override.
---
 gcc/value-range.h | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/gcc/value-range.h b/gcc/value-range.h
index e7f61950a24..b7c83982385 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -95,6 +95,7 @@ public:
   virtual void set_zero (tree type) = 0;
   virtual void set_nonnegative (tree type) = 0;
   virtual bool fits_p (const vrange &r) const = 0;
+  virtual ~vrange () { }
 
   bool varying_p () const;
   bool undefined_p () const;
@@ -382,7 +383,7 @@ public:
   int_range (tree type);
   int_range (const int_range &);
   int_range (const irange &);
-  virtual ~int_range ();
+  ~int_range () final override;
   int_range& operator= (const int_range &);
 protected:
   int_range (tree, tree, value_range_kind = VR_RANGE);
-- 
2.44.0

[COMMITTED 03/16] Make some Value_Range's explicitly integer.

[Aldy Hernandez]

Fix some Value_Range's that we know ahead of time will be only
integers.  This avoids using the polymorphic Value_Range unnecessarily

gcc/ChangeLog:

	* gimple-ssa-warn-access.cc (check_nul_terminated_array): Make Value_Range an int_range.
	(memmodel_to_uhwi): Same
	* tree-ssa-loop-niter.cc (refine_value_range_using_guard): Same.
	(determine_value_range): Same.
	(infer_loop_bounds_from_signedness): Same.
	(scev_var_range_cant_overflow): Same.
---
 gcc/gimple-ssa-warn-access.cc |  4 ++--
 gcc/tree-ssa-loop-niter.cc    | 12 ++++++------
 2 files changed, 8 insertions(+), 8 deletions(-)

diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc
index dedaae27b31..450c1caa765 100644
--- a/gcc/gimple-ssa-warn-access.cc
+++ b/gcc/gimple-ssa-warn-access.cc
@@ -330,7 +330,7 @@ check_nul_terminated_array (GimpleOrTree expr, tree src, tree bound)
   wide_int bndrng[2];
   if (bound)
     {
-      Value_Range r (TREE_TYPE (bound));
+      int_range<2> r (TREE_TYPE (bound));
 
       get_range_query (cfun)->range_of_expr (r, bound);
 
@@ -2816,7 +2816,7 @@ memmodel_to_uhwi (tree ord, gimple *stmt, unsigned HOST_WIDE_INT *cstval)
     {
       /* Use the range query to determine constant values in the absence
 	 of constant propagation (such as at -O0).  */
-      Value_Range rng (TREE_TYPE (ord));
+      int_range<2> rng (TREE_TYPE (ord));
       if (!get_range_query (cfun)->range_of_expr (rng, ord, stmt)
 	  || !rng.singleton_p (&ord))
 	return false;
diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index c6d010f6d89..cbc9dbc5a1f 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -214,7 +214,7 @@ refine_value_range_using_guard (tree type, tree var,
   get_type_static_bounds (type, mint, maxt);
   mpz_init (minc1);
   mpz_init (maxc1);
-  Value_Range r (TREE_TYPE (varc1));
+  int_range<2> r (TREE_TYPE (varc1));
   /* Setup range information for varc1.  */
   if (integer_zerop (varc1))
     {
@@ -368,7 +368,7 @@ determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
       gphi_iterator gsi;
 
       /* Either for VAR itself...  */
-      Value_Range var_range (TREE_TYPE (var));
+      int_range<2> var_range (TREE_TYPE (var));
       get_range_query (cfun)->range_of_expr (var_range, var);
       if (var_range.varying_p () || var_range.undefined_p ())
 	rtype = VR_VARYING;
@@ -382,7 +382,7 @@ determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
 
       /* Or for PHI results in loop->header where VAR is used as
 	 PHI argument from the loop preheader edge.  */
-      Value_Range phi_range (TREE_TYPE (var));
+      int_range<2> phi_range (TREE_TYPE (var));
       for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
 	{
 	  gphi *phi = gsi.phi ();
@@ -408,7 +408,7 @@ determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
 		     involved.  */
 		  if (wi::gt_p (minv, maxv, sgn))
 		    {
-		      Value_Range vr (TREE_TYPE (var));
+		      int_range<2> vr (TREE_TYPE (var));
 		      get_range_query (cfun)->range_of_expr (vr, var);
 		      if (vr.varying_p () || vr.undefined_p ())
 			rtype = VR_VARYING;
@@ -4367,7 +4367,7 @@ infer_loop_bounds_from_signedness (class loop *loop, gimple *stmt)
 
   low = lower_bound_in_type (type, type);
   high = upper_bound_in_type (type, type);
-  Value_Range r (TREE_TYPE (def));
+  int_range<2> r (TREE_TYPE (def));
   get_range_query (cfun)->range_of_expr (r, def);
   if (!r.varying_p () && !r.undefined_p ())
     {
@@ -5426,7 +5426,7 @@ scev_var_range_cant_overflow (tree var, tree step, class loop *loop)
   if (!def_bb || !dominated_by_p (CDI_DOMINATORS, loop->latch, def_bb))
     return false;
 
-  Value_Range r (TREE_TYPE (var));
+  int_range<2> r (TREE_TYPE (var));
   get_range_query (cfun)->range_of_expr (r, var);
   if (r.varying_p () || r.undefined_p ())
     return false;
-- 
2.44.0

Re: [COMMITTED 03/16] Make some Value_Range's explicitly integer.

[Richard Biener]

On Sun, Apr 28, 2024 at 9:07 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> Fix some Value_Range's that we know ahead of time will be only
> integers.  This avoids using the polymorphic Value_Range unnecessarily

But isn't Value_Range a variable-size irange but int_range<2> doesn't
support more than two sub-ranges?

So it doesn't look obvious that this isn't actually a regression?

Richard.

> gcc/ChangeLog:
>
>         * gimple-ssa-warn-access.cc (check_nul_terminated_array): Make Value_Range an int_range.
>         (memmodel_to_uhwi): Same
>         * tree-ssa-loop-niter.cc (refine_value_range_using_guard): Same.
>         (determine_value_range): Same.
>         (infer_loop_bounds_from_signedness): Same.
>         (scev_var_range_cant_overflow): Same.
> ---
>  gcc/gimple-ssa-warn-access.cc |  4 ++--
>  gcc/tree-ssa-loop-niter.cc    | 12 ++++++------
>  2 files changed, 8 insertions(+), 8 deletions(-)
>
> diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc
> index dedaae27b31..450c1caa765 100644
> --- a/gcc/gimple-ssa-warn-access.cc
> +++ b/gcc/gimple-ssa-warn-access.cc
> @@ -330,7 +330,7 @@ check_nul_terminated_array (GimpleOrTree expr, tree src, tree bound)
>    wide_int bndrng[2];
>    if (bound)
>      {
> -      Value_Range r (TREE_TYPE (bound));
> +      int_range<2> r (TREE_TYPE (bound));
>
>        get_range_query (cfun)->range_of_expr (r, bound);
>
> @@ -2816,7 +2816,7 @@ memmodel_to_uhwi (tree ord, gimple *stmt, unsigned HOST_WIDE_INT *cstval)
>      {
>        /* Use the range query to determine constant values in the absence
>          of constant propagation (such as at -O0).  */
> -      Value_Range rng (TREE_TYPE (ord));
> +      int_range<2> rng (TREE_TYPE (ord));
>        if (!get_range_query (cfun)->range_of_expr (rng, ord, stmt)
>           || !rng.singleton_p (&ord))
>         return false;
> diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
> index c6d010f6d89..cbc9dbc5a1f 100644
> --- a/gcc/tree-ssa-loop-niter.cc
> +++ b/gcc/tree-ssa-loop-niter.cc
> @@ -214,7 +214,7 @@ refine_value_range_using_guard (tree type, tree var,
>    get_type_static_bounds (type, mint, maxt);
>    mpz_init (minc1);
>    mpz_init (maxc1);
> -  Value_Range r (TREE_TYPE (varc1));
> +  int_range<2> r (TREE_TYPE (varc1));
>    /* Setup range information for varc1.  */
>    if (integer_zerop (varc1))
>      {
> @@ -368,7 +368,7 @@ determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
>        gphi_iterator gsi;
>
>        /* Either for VAR itself...  */
> -      Value_Range var_range (TREE_TYPE (var));
> +      int_range<2> var_range (TREE_TYPE (var));
>        get_range_query (cfun)->range_of_expr (var_range, var);
>        if (var_range.varying_p () || var_range.undefined_p ())
>         rtype = VR_VARYING;
> @@ -382,7 +382,7 @@ determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
>
>        /* Or for PHI results in loop->header where VAR is used as
>          PHI argument from the loop preheader edge.  */
> -      Value_Range phi_range (TREE_TYPE (var));
> +      int_range<2> phi_range (TREE_TYPE (var));
>        for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
>         {
>           gphi *phi = gsi.phi ();
> @@ -408,7 +408,7 @@ determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
>                      involved.  */
>                   if (wi::gt_p (minv, maxv, sgn))
>                     {
> -                     Value_Range vr (TREE_TYPE (var));
> +                     int_range<2> vr (TREE_TYPE (var));
>                       get_range_query (cfun)->range_of_expr (vr, var);
>                       if (vr.varying_p () || vr.undefined_p ())
>                         rtype = VR_VARYING;
> @@ -4367,7 +4367,7 @@ infer_loop_bounds_from_signedness (class loop *loop, gimple *stmt)
>
>    low = lower_bound_in_type (type, type);
>    high = upper_bound_in_type (type, type);
> -  Value_Range r (TREE_TYPE (def));
> +  int_range<2> r (TREE_TYPE (def));
>    get_range_query (cfun)->range_of_expr (r, def);
>    if (!r.varying_p () && !r.undefined_p ())
>      {
> @@ -5426,7 +5426,7 @@ scev_var_range_cant_overflow (tree var, tree step, class loop *loop)
>    if (!def_bb || !dominated_by_p (CDI_DOMINATORS, loop->latch, def_bb))
>      return false;
>
> -  Value_Range r (TREE_TYPE (var));
> +  int_range<2> r (TREE_TYPE (var));
>    get_range_query (cfun)->range_of_expr (r, var);
>    if (r.varying_p () || r.undefined_p ())
>      return false;
> --
> 2.44.0
>

Re: [COMMITTED 03/16] Make some Value_Range's explicitly integer.

[Aldy Hernandez]

[-- Attachment #1: Type: text/plain, Size: 5099 bytes --]

Ughhh, you're right.  Thanks for spotting this.

I'm testing the attached patch and will commit if it passes tests.

Aldy

On Tue, Apr 30, 2024 at 9:46 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Sun, Apr 28, 2024 at 9:07 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> > Fix some Value_Range's that we know ahead of time will be only
> > integers.  This avoids using the polymorphic Value_Range unnecessarily
>
> But isn't Value_Range a variable-size irange but int_range<2> doesn't
> support more than two sub-ranges?
>
> So it doesn't look obvious that this isn't actually a regression?
>
> Richard.
>
> > gcc/ChangeLog:
> >
> >         * gimple-ssa-warn-access.cc (check_nul_terminated_array): Make Value_Range an int_range.
> >         (memmodel_to_uhwi): Same
> >         * tree-ssa-loop-niter.cc (refine_value_range_using_guard): Same.
> >         (determine_value_range): Same.
> >         (infer_loop_bounds_from_signedness): Same.
> >         (scev_var_range_cant_overflow): Same.
> > ---
> >  gcc/gimple-ssa-warn-access.cc |  4 ++--
> >  gcc/tree-ssa-loop-niter.cc    | 12 ++++++------
> >  2 files changed, 8 insertions(+), 8 deletions(-)
> >
> > diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc
> > index dedaae27b31..450c1caa765 100644
> > --- a/gcc/gimple-ssa-warn-access.cc
> > +++ b/gcc/gimple-ssa-warn-access.cc
> > @@ -330,7 +330,7 @@ check_nul_terminated_array (GimpleOrTree expr, tree src, tree bound)
> >    wide_int bndrng[2];
> >    if (bound)
> >      {
> > -      Value_Range r (TREE_TYPE (bound));
> > +      int_range<2> r (TREE_TYPE (bound));
> >
> >        get_range_query (cfun)->range_of_expr (r, bound);
> >
> > @@ -2816,7 +2816,7 @@ memmodel_to_uhwi (tree ord, gimple *stmt, unsigned HOST_WIDE_INT *cstval)
> >      {
> >        /* Use the range query to determine constant values in the absence
> >          of constant propagation (such as at -O0).  */
> > -      Value_Range rng (TREE_TYPE (ord));
> > +      int_range<2> rng (TREE_TYPE (ord));
> >        if (!get_range_query (cfun)->range_of_expr (rng, ord, stmt)
> >           || !rng.singleton_p (&ord))
> >         return false;
> > diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
> > index c6d010f6d89..cbc9dbc5a1f 100644
> > --- a/gcc/tree-ssa-loop-niter.cc
> > +++ b/gcc/tree-ssa-loop-niter.cc
> > @@ -214,7 +214,7 @@ refine_value_range_using_guard (tree type, tree var,
> >    get_type_static_bounds (type, mint, maxt);
> >    mpz_init (minc1);
> >    mpz_init (maxc1);
> > -  Value_Range r (TREE_TYPE (varc1));
> > +  int_range<2> r (TREE_TYPE (varc1));
> >    /* Setup range information for varc1.  */
> >    if (integer_zerop (varc1))
> >      {
> > @@ -368,7 +368,7 @@ determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
> >        gphi_iterator gsi;
> >
> >        /* Either for VAR itself...  */
> > -      Value_Range var_range (TREE_TYPE (var));
> > +      int_range<2> var_range (TREE_TYPE (var));
> >        get_range_query (cfun)->range_of_expr (var_range, var);
> >        if (var_range.varying_p () || var_range.undefined_p ())
> >         rtype = VR_VARYING;
> > @@ -382,7 +382,7 @@ determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
> >
> >        /* Or for PHI results in loop->header where VAR is used as
> >          PHI argument from the loop preheader edge.  */
> > -      Value_Range phi_range (TREE_TYPE (var));
> > +      int_range<2> phi_range (TREE_TYPE (var));
> >        for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
> >         {
> >           gphi *phi = gsi.phi ();
> > @@ -408,7 +408,7 @@ determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
> >                      involved.  */
> >                   if (wi::gt_p (minv, maxv, sgn))
> >                     {
> > -                     Value_Range vr (TREE_TYPE (var));
> > +                     int_range<2> vr (TREE_TYPE (var));
> >                       get_range_query (cfun)->range_of_expr (vr, var);
> >                       if (vr.varying_p () || vr.undefined_p ())
> >                         rtype = VR_VARYING;
> > @@ -4367,7 +4367,7 @@ infer_loop_bounds_from_signedness (class loop *loop, gimple *stmt)
> >
> >    low = lower_bound_in_type (type, type);
> >    high = upper_bound_in_type (type, type);
> > -  Value_Range r (TREE_TYPE (def));
> > +  int_range<2> r (TREE_TYPE (def));
> >    get_range_query (cfun)->range_of_expr (r, def);
> >    if (!r.varying_p () && !r.undefined_p ())
> >      {
> > @@ -5426,7 +5426,7 @@ scev_var_range_cant_overflow (tree var, tree step, class loop *loop)
> >    if (!def_bb || !dominated_by_p (CDI_DOMINATORS, loop->latch, def_bb))
> >      return false;
> >
> > -  Value_Range r (TREE_TYPE (var));
> > +  int_range<2> r (TREE_TYPE (var));
> >    get_range_query (cfun)->range_of_expr (r, var);
> >    if (r.varying_p () || r.undefined_p ())
> >      return false;
> > --
> > 2.44.0
> >
>

[-- Attachment #2: 0001-Change-int_range-2-to-infinite-precision.patch --]
[-- Type: text/x-patch, Size: 4232 bytes --]

From f43749b8381a9b1b0a4f1ab2cb288cb821f04319 Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Tue, 30 Apr 2024 10:36:58 +0200
Subject: [PATCH] Change int_range<2> to infinite precision.

In my previous change I mistakenly changed Value_Range to
int_range<2>.  The former has "infinite" precision for integer ranges,
whereas int_range<2> has two sub-ranges.  This should have been
int_range_max.

gcc/ChangeLog:

	* gimple-ssa-warn-access.cc (check_nul_terminated_array): Change
	int_range<2> to int_range_max.
	(memmodel_to_uhwi): Same.
	* tree-ssa-loop-niter.cc (refine_value_range_using_guard): Same.
	(determine_value_range): Same.
	(infer_loop_bounds_from_signedness): Same.
	(scev_var_range_cant_overflow): Same.
---
 gcc/gimple-ssa-warn-access.cc |  4 ++--
 gcc/tree-ssa-loop-niter.cc    | 12 ++++++------
 2 files changed, 8 insertions(+), 8 deletions(-)

diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc
index 450c1caa765..2c10d19e7f3 100644
--- a/gcc/gimple-ssa-warn-access.cc
+++ b/gcc/gimple-ssa-warn-access.cc
@@ -330,7 +330,7 @@ check_nul_terminated_array (GimpleOrTree expr, tree src, tree bound)
   wide_int bndrng[2];
   if (bound)
     {
-      int_range<2> r (TREE_TYPE (bound));
+      int_range_max r (TREE_TYPE (bound));
 
       get_range_query (cfun)->range_of_expr (r, bound);
 
@@ -2816,7 +2816,7 @@ memmodel_to_uhwi (tree ord, gimple *stmt, unsigned HOST_WIDE_INT *cstval)
     {
       /* Use the range query to determine constant values in the absence
 	 of constant propagation (such as at -O0).  */
-      int_range<2> rng (TREE_TYPE (ord));
+      int_range_max rng (TREE_TYPE (ord));
       if (!get_range_query (cfun)->range_of_expr (rng, ord, stmt)
 	  || !rng.singleton_p (&ord))
 	return false;
diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index adbc1936982..0fde07e626f 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -214,7 +214,7 @@ refine_value_range_using_guard (tree type, tree var,
   get_type_static_bounds (type, mint, maxt);
   mpz_init (minc1);
   mpz_init (maxc1);
-  int_range<2> r (TREE_TYPE (varc1));
+  int_range_max r (TREE_TYPE (varc1));
   /* Setup range information for varc1.  */
   if (integer_zerop (varc1))
     {
@@ -368,7 +368,7 @@ determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
       gphi_iterator gsi;
 
       /* Either for VAR itself...  */
-      int_range<2> var_range (TREE_TYPE (var));
+      int_range_max var_range (TREE_TYPE (var));
       get_range_query (cfun)->range_of_expr (var_range, var);
       if (var_range.varying_p () || var_range.undefined_p ())
 	rtype = VR_VARYING;
@@ -382,7 +382,7 @@ determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
 
       /* Or for PHI results in loop->header where VAR is used as
 	 PHI argument from the loop preheader edge.  */
-      int_range<2> phi_range (TREE_TYPE (var));
+      int_range_max phi_range (TREE_TYPE (var));
       for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
 	{
 	  gphi *phi = gsi.phi ();
@@ -408,7 +408,7 @@ determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
 		     involved.  */
 		  if (wi::gt_p (minv, maxv, sgn))
 		    {
-		      int_range<2> vr (TREE_TYPE (var));
+		      int_range_max vr (TREE_TYPE (var));
 		      get_range_query (cfun)->range_of_expr (vr, var);
 		      if (vr.varying_p () || vr.undefined_p ())
 			rtype = VR_VARYING;
@@ -4367,7 +4367,7 @@ infer_loop_bounds_from_signedness (class loop *loop, gimple *stmt)
 
   low = lower_bound_in_type (type, type);
   high = upper_bound_in_type (type, type);
-  int_range<2> r (TREE_TYPE (def));
+  int_range_max r (TREE_TYPE (def));
   get_range_query (cfun)->range_of_expr (r, def);
   if (!r.varying_p () && !r.undefined_p ())
     {
@@ -5426,7 +5426,7 @@ scev_var_range_cant_overflow (tree var, tree step, class loop *loop)
   if (!def_bb || !dominated_by_p (CDI_DOMINATORS, loop->latch, def_bb))
     return false;
 
-  int_range<2> r (TREE_TYPE (var));
+  int_range_max r (TREE_TYPE (var));
   get_range_query (cfun)->range_of_expr (r, var);
   if (r.varying_p () || r.undefined_p ())
     return false;
-- 
2.44.0

[COMMITTED 04/16] Add tree versions of lower and upper bounds to vrange.

[Aldy Hernandez]

This patch adds vrange::lbound() and vrange::ubound() that return
trees.  These can be used in generic code that is type agnostic, and
avoids special casing for pointers and integers in places where we
handle both.  It also cleans up a wart in the Value_Range class.

gcc/ChangeLog:

	* tree-ssa-loop-niter.cc (refine_value_range_using_guard): Convert
	bound to wide_int.
	* value-range.cc (Value_Range::lower_bound): Remove.
	(Value_Range::upper_bound): Remove.
	(unsupported_range::lbound): New.
	(unsupported_range::ubound): New.
	(frange::lbound): New.
	(frange::ubound): New.
	(irange::lbound): New.
	(irange::ubound): New.
	* value-range.h (class vrange): Add lbound() and ubound().
	(class irange): Same.
	(class frange): Same.
	(class unsupported_range): Same.
	(class Value_Range): Rename lower_bound and upper_bound to lbound
	and ubound respectively.
---
 gcc/tree-ssa-loop-niter.cc |  4 +--
 gcc/value-range.cc         | 56 ++++++++++++++++++++++++--------------
 gcc/value-range.h          | 13 +++++++--
 3 files changed, 48 insertions(+), 25 deletions(-)

diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index cbc9dbc5a1f..adbc1936982 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -4067,7 +4067,7 @@ record_nonwrapping_iv (class loop *loop, tree base, tree step, gimple *stmt,
       Value_Range base_range (TREE_TYPE (orig_base));
       if (get_range_query (cfun)->range_of_expr (base_range, orig_base)
 	  && !base_range.undefined_p ())
-	max = base_range.upper_bound ();
+	max = wi::to_wide (base_range.ubound ());
       extreme = fold_convert (unsigned_type, low);
       if (TREE_CODE (orig_base) == SSA_NAME
 	  && TREE_CODE (high) == INTEGER_CST
@@ -4090,7 +4090,7 @@ record_nonwrapping_iv (class loop *loop, tree base, tree step, gimple *stmt,
       Value_Range base_range (TREE_TYPE (orig_base));
       if (get_range_query (cfun)->range_of_expr (base_range, orig_base)
 	  && !base_range.undefined_p ())
-	min = base_range.lower_bound ();
+	min = wi::to_wide (base_range.lbound ());
       extreme = fold_convert (unsigned_type, high);
       if (TREE_CODE (orig_base) == SSA_NAME
 	  && TREE_CODE (low) == INTEGER_CST
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 632d77305cc..ccac517d4c4 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -37,26 +37,6 @@ irange::accept (const vrange_visitor &v) const
   v.visit (*this);
 }
 
-// Convenience function only available for integers and pointers.
-
-wide_int
-Value_Range::lower_bound () const
-{
-  if (is_a <irange> (*m_vrange))
-    return as_a <irange> (*m_vrange).lower_bound ();
-  gcc_unreachable ();
-}
-
-// Convenience function only available for integers and pointers.
-
-wide_int
-Value_Range::upper_bound () const
-{
-  if (is_a <irange> (*m_vrange))
-    return as_a <irange> (*m_vrange).upper_bound ();
-  gcc_unreachable ();
-}
-
 void
 Value_Range::dump (FILE *out) const
 {
@@ -211,6 +191,18 @@ unsupported_range::operator= (const vrange &r)
   return *this;
 }
 
+tree
+unsupported_range::lbound () const
+{
+  return NULL;
+}
+
+tree
+unsupported_range::ubound () const
+{
+  return NULL;
+}
+
 // Assignment operator for generic ranges.  Copying incompatible types
 // is not allowed.
 
@@ -957,6 +949,18 @@ frange::set_nonnegative (tree type)
   set (type, dconst0, frange_val_max (type));
 }
 
+tree
+frange::lbound () const
+{
+  return build_real (type (), lower_bound ());
+}
+
+tree
+frange::ubound () const
+{
+  return build_real (type (), upper_bound ());
+}
+
 // Here we copy between any two irange's.
 
 irange &
@@ -2086,6 +2090,18 @@ irange::union_bitmask (const irange &r)
   return true;
 }
 
+tree
+irange::lbound () const
+{
+  return wide_int_to_tree (type (), lower_bound ());
+}
+
+tree
+irange::ubound () const
+{
+  return wide_int_to_tree (type (), upper_bound ());
+}
+
 void
 irange_bitmask::verify_mask () const
 {
diff --git a/gcc/value-range.h b/gcc/value-range.h
index b7c83982385..f216f1b82c1 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -96,6 +96,8 @@ public:
   virtual void set_nonnegative (tree type) = 0;
   virtual bool fits_p (const vrange &r) const = 0;
   virtual ~vrange () { }
+  virtual tree lbound () const = 0;
+  virtual tree ubound () const = 0;
 
   bool varying_p () const;
   bool undefined_p () const;
@@ -298,6 +300,8 @@ public:
   wide_int lower_bound (unsigned = 0) const;
   wide_int upper_bound (unsigned) const;
   wide_int upper_bound () const;
+  virtual tree lbound () const override;
+  virtual tree ubound () const override;
 
   // Predicates.
   virtual bool zero_p () const override;
@@ -419,6 +423,8 @@ public:
   void set_nonnegative (tree type) final override;
   bool fits_p (const vrange &) const final override;
   unsupported_range& operator= (const vrange &r);
+  tree lbound () const final override;
+  tree ubound () const final override;
 };
 
 // The NAN state as an opaque object.
@@ -526,6 +532,8 @@ public:
   bool operator!= (const frange &r) const { return !(*this == r); }
   const REAL_VALUE_TYPE &lower_bound () const;
   const REAL_VALUE_TYPE &upper_bound () const;
+  virtual tree lbound () const override;
+  virtual tree ubound () const override;
   nan_state get_nan_state () const;
   void update_nan ();
   void update_nan (bool sign);
@@ -710,7 +718,6 @@ public:
   void dump (FILE *) const;
   static bool supports_type_p (const_tree type);
 
-  // Convenience methods for vrange compatibility.
   tree type () { return m_vrange->type (); }
   bool varying_p () const { return m_vrange->varying_p (); }
   bool undefined_p () const { return m_vrange->undefined_p (); }
@@ -726,8 +733,8 @@ public:
     { init (type); return m_vrange->set_nonzero (type); }
   bool nonzero_p () const { return m_vrange->nonzero_p (); }
   bool zero_p () const { return m_vrange->zero_p (); }
-  wide_int lower_bound () const; // For irange/prange comparability.
-  wide_int upper_bound () const; // For irange/prange comparability.
+  tree lbound () const { return m_vrange->lbound (); }
+  tree ubound () const { return m_vrange->ubound (); }
   void accept (const vrange_visitor &v) const { m_vrange->accept (v); }
 private:
   void init (tree type);
-- 
2.44.0

[COMMITTED 05/16] Move bitmask routines to vrange base class.

[Aldy Hernandez]

Any range can theoretically have a bitmask of set bits.  This patch
moves the bitmask accessors to the base class.  This cleans up some
users in IPA*, and will provide a cleaner interface when prange is in
place.

gcc/ChangeLog:

	* ipa-cp.cc (propagate_bits_across_jump_function): Access bitmask
	through base class.
	(ipcp_store_vr_results): Same.
	* ipa-prop.cc (ipa_compute_jump_functions_for_edge): Same.
	(ipcp_get_parm_bits): Same.
	(ipcp_update_vr): Same.
	* range-op-mixed.h (update_known_bitmask): Change argument to vrange.
	* range-op.cc (update_known_bitmask): Same.
	* value-range.cc (vrange::update_bitmask):  New.
	(irange::set_nonzero_bits): Move to vrange class.
	(irange::get_nonzero_bits): Same.
	* value-range.h (class vrange): Add update_bitmask, get_bitmask,
	get_nonzero_bits, and set_nonzero_bits.
	(class irange): Make bitmask methods virtual overrides.
	(class Value_Range): Add get_bitmask and update_bitmask.
---
 gcc/ipa-cp.cc        |  9 +++------
 gcc/ipa-prop.cc      | 10 ++++------
 gcc/range-op-mixed.h |  2 +-
 gcc/range-op.cc      |  4 ++--
 gcc/value-range.cc   | 16 ++++++++++++++--
 gcc/value-range.h    | 14 +++++++++-----
 6 files changed, 33 insertions(+), 22 deletions(-)

diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc
index b7add455bd5..a688dced5c9 100644
--- a/gcc/ipa-cp.cc
+++ b/gcc/ipa-cp.cc
@@ -2485,8 +2485,7 @@ propagate_bits_across_jump_function (cgraph_edge *cs, int idx,
       jfunc->m_vr->get_vrange (vr);
       if (!vr.undefined_p () && !vr.varying_p ())
 	{
-	  irange &r = as_a <irange> (vr);
-	  irange_bitmask bm = r.get_bitmask ();
+	  irange_bitmask bm = vr.get_bitmask ();
 	  widest_int mask
 	    = widest_int::from (bm.mask (), TYPE_SIGN (parm_type));
 	  widest_int value
@@ -6346,14 +6345,13 @@ ipcp_store_vr_results (void)
 		{
 		  Value_Range tmp = plats->m_value_range.m_vr;
 		  tree type = ipa_get_type (info, i);
-		  irange &r = as_a<irange> (tmp);
 		  irange_bitmask bm (wide_int::from (bits->get_value (),
 						     TYPE_PRECISION (type),
 						     TYPE_SIGN (type)),
 				     wide_int::from (bits->get_mask (),
 						     TYPE_PRECISION (type),
 						     TYPE_SIGN (type)));
-		  r.update_bitmask (bm);
+		  tmp.update_bitmask (bm);
 		  ipa_vr vr (tmp);
 		  ts->m_vr->quick_push (vr);
 		}
@@ -6368,14 +6366,13 @@ ipcp_store_vr_results (void)
 	      tree type = ipa_get_type (info, i);
 	      Value_Range tmp;
 	      tmp.set_varying (type);
-	      irange &r = as_a<irange> (tmp);
 	      irange_bitmask bm (wide_int::from (bits->get_value (),
 						 TYPE_PRECISION (type),
 						 TYPE_SIGN (type)),
 				 wide_int::from (bits->get_mask (),
 						 TYPE_PRECISION (type),
 						 TYPE_SIGN (type)));
-	      r.update_bitmask (bm);
+	      tmp.update_bitmask (bm);
 	      ipa_vr vr (tmp);
 	      ts->m_vr->quick_push (vr);
 	    }
diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
index 374e998aa64..b57f9750431 100644
--- a/gcc/ipa-prop.cc
+++ b/gcc/ipa-prop.cc
@@ -2381,8 +2381,7 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
 	      irange_bitmask bm (value, mask);
 	      if (!addr_nonzero)
 		vr.set_varying (TREE_TYPE (arg));
-	      irange &r = as_a <irange> (vr);
-	      r.update_bitmask (bm);
+	      vr.update_bitmask (bm);
 	      ipa_set_jfunc_vr (jfunc, vr);
 	    }
 	  else if (addr_nonzero)
@@ -5785,8 +5784,8 @@ ipcp_get_parm_bits (tree parm, tree *value, widest_int *mask)
   vr[i].get_vrange (tmp);
   if (tmp.undefined_p () || tmp.varying_p ())
     return false;
-  irange &r = as_a <irange> (tmp);
-  irange_bitmask bm = r.get_bitmask ();
+  irange_bitmask bm;
+  bm = tmp.get_bitmask ();
   *mask = widest_int::from (bm.mask (), TYPE_SIGN (TREE_TYPE (parm)));
   *value = wide_int_to_tree (TREE_TYPE (parm), bm.value ());
   return true;
@@ -5857,8 +5856,7 @@ ipcp_update_vr (struct cgraph_node *node, ipcp_transformation *ts)
 	      if (POINTER_TYPE_P (TREE_TYPE (parm))
 		  && opt_for_fn (node->decl, flag_ipa_bit_cp))
 		{
-		  irange &r = as_a<irange> (tmp);
-		  irange_bitmask bm = r.get_bitmask ();
+		  irange_bitmask bm = tmp.get_bitmask ();
 		  unsigned tem = bm.mask ().to_uhwi ();
 		  unsigned HOST_WIDE_INT bitpos = bm.value ().to_uhwi ();
 		  unsigned align = tem & -tem;
diff --git a/gcc/range-op-mixed.h b/gcc/range-op-mixed.h
index 1b470811829..3ee7c9d6e0d 100644
--- a/gcc/range-op-mixed.h
+++ b/gcc/range-op-mixed.h
@@ -22,7 +22,7 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_RANGE_OP_MIXED_H
 #define GCC_RANGE_OP_MIXED_H
 
-void update_known_bitmask (irange &, tree_code, const irange &, const irange &);
+void update_known_bitmask (vrange &, tree_code, const vrange &, const vrange &);
 bool minus_op1_op2_relation_effect (irange &lhs_range, tree type,
 				    const irange &, const irange &,
 				    relation_kind rel);
diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 4ccb86ef0ba..aeff55cfd78 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -415,8 +415,8 @@ range_op_handler::operand_check_p (tree t1, tree t2, tree t3) const
 // LH and RH.
 
 void
-update_known_bitmask (irange &r, tree_code code,
-		      const irange &lh, const irange &rh)
+update_known_bitmask (vrange &r, tree_code code,
+		      const vrange &lh, const vrange &rh)
 {
   if (r.undefined_p () || lh.undefined_p () || rh.undefined_p ()
       || r.singleton_p ())
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index ccac517d4c4..926f7b707ea 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -68,6 +68,18 @@ unsupported_range::accept (const vrange_visitor &v) const
   v.visit (*this);
 }
 
+void
+vrange::update_bitmask (const class irange_bitmask &)
+{
+}
+
+irange_bitmask
+vrange::get_bitmask () const
+{
+  // Return all unknown bits for the given precision.
+  return irange_bitmask (TYPE_PRECISION (type ()));
+}
+
 bool
 unsupported_range::contains_p (tree) const
 {
@@ -2010,7 +2022,7 @@ irange::get_bitmask () const
 // normalize the range if anything changed.
 
 void
-irange::set_nonzero_bits (const wide_int &bits)
+vrange::set_nonzero_bits (const wide_int &bits)
 {
   gcc_checking_assert (!undefined_p ());
   irange_bitmask bm (wi::zero (TYPE_PRECISION (type ())), bits);
@@ -2020,7 +2032,7 @@ irange::set_nonzero_bits (const wide_int &bits)
 // Return the nonzero bits in R.
 
 wide_int
-irange::get_nonzero_bits () const
+vrange::get_nonzero_bits () const
 {
   gcc_checking_assert (!undefined_p ());
   irange_bitmask bm = get_bitmask ();
diff --git a/gcc/value-range.h b/gcc/value-range.h
index f216f1b82c1..991ffeafcb8 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -98,6 +98,10 @@ public:
   virtual ~vrange () { }
   virtual tree lbound () const = 0;
   virtual tree ubound () const = 0;
+  virtual void update_bitmask (const class irange_bitmask &);
+  virtual irange_bitmask get_bitmask () const;
+  wide_int get_nonzero_bits () const;
+  void set_nonzero_bits (const wide_int &bits);
 
   bool varying_p () const;
   bool undefined_p () const;
@@ -326,11 +330,8 @@ public:
   virtual bool fits_p (const vrange &r) const override;
   virtual void accept (const vrange_visitor &v) const override;
 
-  void update_bitmask (const irange_bitmask &);
-  irange_bitmask get_bitmask () const;
-  // Nonzero masks.
-  wide_int get_nonzero_bits () const;
-  void set_nonzero_bits (const wide_int &bits);
+  virtual void update_bitmask (const class irange_bitmask &) override;
+  virtual irange_bitmask get_bitmask () const override;
 
 protected:
   void maybe_resize (int needed);
@@ -735,6 +736,9 @@ public:
   bool zero_p () const { return m_vrange->zero_p (); }
   tree lbound () const { return m_vrange->lbound (); }
   tree ubound () const { return m_vrange->ubound (); }
+  irange_bitmask get_bitmask () const { return m_vrange->get_bitmask (); }
+  void update_bitmask (const class irange_bitmask &bm)
+  { return m_vrange->update_bitmask (bm); }
   void accept (const vrange_visitor &v) const { m_vrange->accept (v); }
 private:
   void init (tree type);
-- 
2.44.0

[COMMITTED 06/16] Remove GTY support for vrange and derived classes.

[Aldy Hernandez]

Now that we have a vrange storage class to save ranges in long-term
memory, there is no need for GTY markers for any of the vrange
classes, since they should never live in GC.

gcc/ChangeLog:

	* value-range-storage.h: Remove friends.
	* value-range.cc (gt_ggc_mx): Remove.
	(gt_pch_nx): Remove.
	* value-range.h (class vrange): Remove GTY markers.
	(class irange): Same.
	(class int_range): Same.
	(class frange): Same.
	(gt_ggc_mx): Remove.
	(gt_pch_nx): Remove.
---
 gcc/value-range-storage.h |  4 ---
 gcc/value-range.cc        | 73 ---------------------------------------
 gcc/value-range.h         | 46 +++---------------------
 3 files changed, 4 insertions(+), 119 deletions(-)

diff --git a/gcc/value-range-storage.h b/gcc/value-range-storage.h
index d94c520aa73..5756de7e32d 100644
--- a/gcc/value-range-storage.h
+++ b/gcc/value-range-storage.h
@@ -75,10 +75,6 @@ private:
   static size_t size (const irange &r);
   const unsigned short *lengths_address () const;
   unsigned short *write_lengths_address ();
-  friend void gt_ggc_mx_irange_storage (void *);
-  friend void gt_pch_p_14irange_storage (void *, void *,
-					      gt_pointer_operator, void *);
-  friend void gt_pch_nx_irange_storage (void *);
 
   // The shared precision of each number.
   unsigned short m_precision;
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 926f7b707ea..b901c864a7b 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -2165,79 +2165,6 @@ vrp_operand_equal_p (const_tree val1, const_tree val2)
   return true;
 }
 
-void
-gt_ggc_mx (irange *x)
-{
-  if (!x->undefined_p ())
-    gt_ggc_mx (x->m_type);
-}
-
-void
-gt_pch_nx (irange *x)
-{
-  if (!x->undefined_p ())
-    gt_pch_nx (x->m_type);
-}
-
-void
-gt_pch_nx (irange *x, gt_pointer_operator op, void *cookie)
-{
-  for (unsigned i = 0; i < x->m_num_ranges; ++i)
-    {
-      op (&x->m_base[i * 2], NULL, cookie);
-      op (&x->m_base[i * 2 + 1], NULL, cookie);
-    }
-}
-
-void
-gt_ggc_mx (frange *x)
-{
-  gt_ggc_mx (x->m_type);
-}
-
-void
-gt_pch_nx (frange *x)
-{
-  gt_pch_nx (x->m_type);
-}
-
-void
-gt_pch_nx (frange *x, gt_pointer_operator op, void *cookie)
-{
-  op (&x->m_type, NULL, cookie);
-}
-
-void
-gt_ggc_mx (vrange *x)
-{
-  if (is_a <irange> (*x))
-    return gt_ggc_mx ((irange *) x);
-  if (is_a <frange> (*x))
-    return gt_ggc_mx ((frange *) x);
-  gcc_unreachable ();
-}
-
-void
-gt_pch_nx (vrange *x)
-{
-  if (is_a <irange> (*x))
-    return gt_pch_nx ((irange *) x);
-  if (is_a <frange> (*x))
-    return gt_pch_nx ((frange *) x);
-  gcc_unreachable ();
-}
-
-void
-gt_pch_nx (vrange *x, gt_pointer_operator op, void *cookie)
-{
-  if (is_a <irange> (*x))
-    gt_pch_nx ((irange *) x, op, cookie);
-  else if (is_a <frange> (*x))
-    gt_pch_nx ((frange *) x, op, cookie);
-  else
-    gcc_unreachable ();
-}
-
 #define DEFINE_INT_RANGE_INSTANCE(N)					\
   template int_range<N>::int_range(tree_node *,				\
 				   const wide_int &,			\
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 991ffeafcb8..2650ded6d10 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -72,7 +72,7 @@ enum value_range_discriminator
 //	if (f.supports_type_p (type)) ...
 //    }
 
-class GTY((user)) vrange
+class vrange
 {
   template <typename T> friend bool is_a (vrange &);
   friend class Value_Range;
@@ -279,7 +279,7 @@ irange_bitmask::intersect (const irange_bitmask &orig_src)
 
 // An integer range without any storage.
 
-class GTY((user)) irange : public vrange
+class irange : public vrange
 {
   friend value_range_kind get_legacy_range (const irange &, tree &, tree &);
   friend class irange_storage;
@@ -350,10 +350,6 @@ protected:
   // Hard limit on max ranges allowed.
   static const int HARD_MAX_RANGES = 255;
 private:
-  friend void gt_ggc_mx (irange *);
-  friend void gt_pch_nx (irange *);
-  friend void gt_pch_nx (irange *, gt_pointer_operator, void *);
-
   bool varying_compatible_p () const;
   bool intersect_bitmask (const irange &r);
   bool union_bitmask (const irange &r);
@@ -379,7 +375,7 @@ protected:
 // HARD_MAX_RANGES.  This new storage is freed upon destruction.
 
 template<unsigned N, bool RESIZABLE = false>
-class GTY((user)) int_range : public irange
+class int_range : public irange
 {
 public:
   int_range ();
@@ -484,13 +480,10 @@ nan_state::neg_p () const
 // The representation is a type with a couple of endpoints, unioned
 // with the set of { -NAN, +Nan }.
 
-class GTY((user)) frange : public vrange
+class frange : public vrange
 {
   friend class frange_storage;
   friend class vrange_printer;
-  friend void gt_ggc_mx (frange *);
-  friend void gt_pch_nx (frange *);
-  friend void gt_pch_nx (frange *, gt_pointer_operator, void *);
 public:
   frange ();
   frange (const frange &);
@@ -991,37 +984,6 @@ range_includes_zero_p (const irange *vr)
   return vr->contains_p (zero);
 }
 
-extern void gt_ggc_mx (vrange *);
-extern void gt_pch_nx (vrange *);
-extern void gt_pch_nx (vrange *, gt_pointer_operator, void *);
-extern void gt_ggc_mx (irange *);
-extern void gt_pch_nx (irange *);
-extern void gt_pch_nx (irange *, gt_pointer_operator, void *);
-extern void gt_ggc_mx (frange *);
-extern void gt_pch_nx (frange *);
-extern void gt_pch_nx (frange *, gt_pointer_operator, void *);
-
-template<unsigned N>
-inline void
-gt_ggc_mx (int_range<N> *x)
-{
-  gt_ggc_mx ((irange *) x);
-}
-
-template<unsigned N>
-inline void
-gt_pch_nx (int_range<N> *x)
-{
-  gt_pch_nx ((irange *) x);
-}
-
-template<unsigned N>
-inline void
-gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie)
-{
-  gt_pch_nx ((irange *) x, op, cookie);
-}
-
 // Constructors for irange
 
 inline
-- 
2.44.0

[COMMITTED 07/16] Make fold_cond_with_ops use a boolean type for range_true/range_false.

[Aldy Hernandez]

Conditional operators are always boolean, regardless of their
operands.  Getting the type wrong is not currently a problem, but will
be when prange's can no longer store an integer.

gcc/ChangeLog:

	* vr-values.cc (simplify_using_ranges::fold_cond_with_ops): Remove
	type from range_true and range_false.
---
 gcc/vr-values.cc | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc
index a7e291a16e5..ff68d40c355 100644
--- a/gcc/vr-values.cc
+++ b/gcc/vr-values.cc
@@ -320,9 +320,9 @@ simplify_using_ranges::fold_cond_with_ops (enum tree_code code,
   range_op_handler handler (code);
   if (handler && handler.fold_range (res, type, r0, r1))
     {
-      if (res == range_true (type))
+      if (res == range_true ())
 	return boolean_true_node;
-      if (res == range_false (type))
+      if (res == range_false ())
 	return boolean_false_node;
     }
   return NULL;
-- 
2.44.0

[COMMITTED 08/16] Change range_includes_zero_p argument to a reference.

[Aldy Hernandez]

Make range_includes_zero_p take an argument instead of a pointer for
consistency in the range-op code.

gcc/ChangeLog:

	* gimple-range-op.cc (cfn_clz::fold_range): Change
	range_includes_zero_p argument to a reference.
	(cfn_ctz::fold_range): Same.
	* range-op.cc (operator_plus::lhs_op1_relation): Same.
	* value-range.h (range_includes_zero_p): Same.
---
 gcc/gimple-range-op.cc |  6 +++---
 gcc/range-op.cc        |  2 +-
 gcc/value-range.h      | 10 +++++-----
 3 files changed, 9 insertions(+), 9 deletions(-)

diff --git a/gcc/gimple-range-op.cc b/gcc/gimple-range-op.cc
index a98f7db62a7..9c50c00549e 100644
--- a/gcc/gimple-range-op.cc
+++ b/gcc/gimple-range-op.cc
@@ -853,7 +853,7 @@ public:
     // __builtin_ffs* and __builtin_popcount* return [0, prec].
     int prec = TYPE_PRECISION (lh.type ());
     // If arg is non-zero, then ffs or popcount are non-zero.
-    int mini = range_includes_zero_p (&lh) ? 0 : 1;
+    int mini = range_includes_zero_p (lh) ? 0 : 1;
     int maxi = prec;
 
     // If some high bits are known to be zero, decrease the maximum.
@@ -945,7 +945,7 @@ cfn_clz::fold_range (irange &r, tree type, const irange &lh,
       if (mini == -2)
 	mini = 0;
     }
-  else if (!range_includes_zero_p (&lh))
+  else if (!range_includes_zero_p (lh))
     {
       mini = 0;
       maxi = prec - 1;
@@ -1007,7 +1007,7 @@ cfn_ctz::fold_range (irange &r, tree type, const irange &lh,
 	mini = -2;
     }
   // If arg is non-zero, then use [0, prec - 1].
-  if (!range_includes_zero_p (&lh))
+  if (!range_includes_zero_p (lh))
     {
       mini = 0;
       maxi = prec - 1;
diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index aeff55cfd78..6ea7d624a9b 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -1657,7 +1657,7 @@ operator_plus::lhs_op1_relation (const irange &lhs,
     }
 
   // If op2 does not contain 0, then LHS and OP1 can never be equal.
-  if (!range_includes_zero_p (&op2))
+  if (!range_includes_zero_p (op2))
     return VREL_NE;
 
   return VREL_VARYING;
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 2650ded6d10..62f123e2a4b 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -972,16 +972,16 @@ irange::contains_p (tree cst) const
 }
 
 inline bool
-range_includes_zero_p (const irange *vr)
+range_includes_zero_p (const irange &vr)
 {
-  if (vr->undefined_p ())
+  if (vr.undefined_p ())
     return false;
 
-  if (vr->varying_p ())
+  if (vr.varying_p ())
     return true;
 
-  wide_int zero = wi::zero (TYPE_PRECISION (vr->type ()));
-  return vr->contains_p (zero);
+  wide_int zero = wi::zero (TYPE_PRECISION (vr.type ()));
+  return vr.contains_p (zero);
 }
 
 // Constructors for irange
-- 
2.44.0

[COMMITTED 09/16] Verify that reading back from vrange_storage doesn't drop bits.

[Aldy Hernandez]

We have a sanity check in the irange storage code to make sure that
reading back a cache entry we have just written to yields exactly the
same range.  There's no need to do this only for integers.  This patch
moves the code to a more generic place.

However, doing so tickles a latent bug in the frange code where a
range is being pessimized from [0.0, 1.0] to [-0.0, 1.0].  Exclude
checking frange's until this bug is fixed.

gcc/ChangeLog:

	* value-range-storage.cc (irange_storage::set_irange): Move
	verification code from here...
	(vrange_storage::set_vrange): ...to here.
---
 gcc/value-range-storage.cc | 20 +++++++++++++-------
 1 file changed, 13 insertions(+), 7 deletions(-)

diff --git a/gcc/value-range-storage.cc b/gcc/value-range-storage.cc
index f00474ad0e6..09a29776a0e 100644
--- a/gcc/value-range-storage.cc
+++ b/gcc/value-range-storage.cc
@@ -165,6 +165,19 @@ vrange_storage::set_vrange (const vrange &r)
     }
   else
     gcc_unreachable ();
+
+  // Verify that reading back from the cache didn't drop bits.
+  if (flag_checking
+      // FIXME: Avoid checking frange, as it currently pessimizes some ranges:
+      //
+      // gfortran.dg/pr49472.f90 pessimizes [0.0, 1.0] into [-0.0, 1.0].
+      && !is_a <frange> (r)
+      && !r.undefined_p ())
+    {
+      Value_Range tmp (r);
+      get_vrange (tmp, r.type ());
+      gcc_checking_assert (tmp == r);
+    }
 }
 
 // Restore R from storage.
@@ -306,13 +319,6 @@ irange_storage::set_irange (const irange &r)
   irange_bitmask bm = r.m_bitmask;
   write_wide_int (val, len, bm.value ());
   write_wide_int (val, len, bm.mask ());
-
-  if (flag_checking)
-    {
-      int_range_max tmp;
-      get_irange (tmp, r.type ());
-      gcc_checking_assert (tmp == r);
-    }
 }
 
 static inline void
-- 
2.44.0

[COMMITTED 10/16] Accept a vrange in get_legacy_range.

[Aldy Hernandez]

In preparation for prange, make get_legacy_range take a generic
vrange, not just an irange.

gcc/ChangeLog:

	* value-range.cc (get_legacy_range): Make static and add another
	version of get_legacy_range that takes a vrange.
	* value-range.h (class irange): Remove unnecessary friendship with
	get_legacy_range.
	(get_legacy_range): Accept a vrange.
---
 gcc/value-range.cc | 17 ++++++++++++++++-
 gcc/value-range.h  |  3 +--
 2 files changed, 17 insertions(+), 3 deletions(-)

diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index b901c864a7b..44929b210aa 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -1004,7 +1004,7 @@ irange::operator= (const irange &src)
   return *this;
 }
 
-value_range_kind
+static value_range_kind
 get_legacy_range (const irange &r, tree &min, tree &max)
 {
   if (r.undefined_p ())
@@ -1041,6 +1041,21 @@ get_legacy_range (const irange &r, tree &min, tree &max)
   return VR_RANGE;
 }
 
+// Given a range in V, return an old-style legacy range consisting of
+// a value_range_kind with a MIN/MAX.  This is to maintain
+// compatibility with passes that still depend on VR_ANTI_RANGE, and
+// only works for integers and pointers.
+
+value_range_kind
+get_legacy_range (const vrange &v, tree &min, tree &max)
+{
+  if (is_a <irange> (v))
+    return get_legacy_range (as_a <irange> (v), min, max);
+
+  gcc_unreachable ();
+  return VR_UNDEFINED;
+}
+
 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
    This means adjusting VRTYPE, MIN and MAX representing the case of a
    wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 62f123e2a4b..d2e8fd5a4d9 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -281,7 +281,6 @@ irange_bitmask::intersect (const irange_bitmask &orig_src)
 
 class irange : public vrange
 {
-  friend value_range_kind get_legacy_range (const irange &, tree &, tree &);
   friend class irange_storage;
   friend class vrange_printer;
 public:
@@ -886,7 +885,7 @@ Value_Range::supports_type_p (const_tree type)
   return irange::supports_p (type) || frange::supports_p (type);
 }
 
-extern value_range_kind get_legacy_range (const irange &, tree &min, tree &max);
+extern value_range_kind get_legacy_range (const vrange &, tree &min, tree &max);
 extern void dump_value_range (FILE *, const vrange *);
 extern bool vrp_operand_equal_p (const_tree, const_tree);
 inline REAL_VALUE_TYPE frange_val_min (const_tree type);
-- 
2.44.0

[COMMITTED 11/16] Move get_bitmask_from_range out of irange class.

[Aldy Hernandez]

prange will also have bitmasks, so it will need to use get_bitmask_from_range.

gcc/ChangeLog:

	* value-range.cc (get_bitmask_from_range): Move out of irange class.
	(irange::get_bitmask): Call function instead of internal method.
	* value-range.h (class irange): Remove get_bitmask_from_range.
---
 gcc/value-range.cc | 52 +++++++++++++++++++++++-----------------------
 gcc/value-range.h  |  1 -
 2 files changed, 26 insertions(+), 27 deletions(-)

diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 44929b210aa..d9689bd469f 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -31,6 +31,30 @@ along with GCC; see the file COPYING3.  If not see
 #include "fold-const.h"
 #include "gimple-range.h"
 
+// Return the bitmask inherent in a range.
+
+static irange_bitmask
+get_bitmask_from_range (tree type,
+			const wide_int &min, const wide_int &max)
+{
+  unsigned prec = TYPE_PRECISION (type);
+
+  // All the bits of a singleton are known.
+  if (min == max)
+    {
+      wide_int mask = wi::zero (prec);
+      wide_int value = min;
+      return irange_bitmask (value, mask);
+    }
+
+  wide_int xorv = min ^ max;
+
+  if (xorv != 0)
+    xorv = wi::mask (prec - wi::clz (xorv), false, prec);
+
+  return irange_bitmask (wi::zero (prec), min | xorv);
+}
+
 void
 irange::accept (const vrange_visitor &v) const
 {
@@ -1881,31 +1905,6 @@ irange::invert ()
     verify_range ();
 }
 
-// Return the bitmask inherent in the range.
-
-irange_bitmask
-irange::get_bitmask_from_range () const
-{
-  unsigned prec = TYPE_PRECISION (type ());
-  wide_int min = lower_bound ();
-  wide_int max = upper_bound ();
-
-  // All the bits of a singleton are known.
-  if (min == max)
-    {
-      wide_int mask = wi::zero (prec);
-      wide_int value = lower_bound ();
-      return irange_bitmask (value, mask);
-    }
-
-  wide_int xorv = min ^ max;
-
-  if (xorv != 0)
-    xorv = wi::mask (prec - wi::clz (xorv), false, prec);
-
-  return irange_bitmask (wi::zero (prec), min | xorv);
-}
-
 // Remove trailing ranges that this bitmask indicates can't exist.
 
 void
@@ -2027,7 +2026,8 @@ irange::get_bitmask () const
   // in the mask.
   //
   // See also the note in irange_bitmask::intersect.
-  irange_bitmask bm = get_bitmask_from_range ();
+  irange_bitmask bm
+    = get_bitmask_from_range (type (), lower_bound (), upper_bound ());
   if (!m_bitmask.unknown_p ())
     bm.intersect (m_bitmask);
   return bm;
diff --git a/gcc/value-range.h b/gcc/value-range.h
index d2e8fd5a4d9..ede90a496d8 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -352,7 +352,6 @@ private:
   bool varying_compatible_p () const;
   bool intersect_bitmask (const irange &r);
   bool union_bitmask (const irange &r);
-  irange_bitmask get_bitmask_from_range () const;
   bool set_range_from_bitmask ();
 
   bool intersect (const wide_int& lb, const wide_int& ub);
-- 
2.44.0

[COMMITTED 12/16] Make some integer specific ranges generic Value_Range's.

[Aldy Hernandez]

There are some irange uses that should be Value_Range, because they
can be either integers or pointers.  This will become a problem when
prange comes live.

gcc/ChangeLog:

	* tree-ssa-loop-split.cc (split_at_bb_p): Make int_range a Value_Range.
	* tree-ssa-strlen.cc (get_range): Same.
	* value-query.cc (range_query::get_tree_range):  Handle both
	integers and pointers.
	* vr-values.cc (simplify_using_ranges::fold_cond_with_ops): Make
	r0 and r1 Value_Range's.
---
 gcc/tree-ssa-loop-split.cc | 6 +++---
 gcc/tree-ssa-strlen.cc     | 2 +-
 gcc/value-query.cc         | 4 +---
 gcc/vr-values.cc           | 3 ++-
 4 files changed, 7 insertions(+), 8 deletions(-)

diff --git a/gcc/tree-ssa-loop-split.cc b/gcc/tree-ssa-loop-split.cc
index a770ea371a2..a6be0cef7b0 100644
--- a/gcc/tree-ssa-loop-split.cc
+++ b/gcc/tree-ssa-loop-split.cc
@@ -144,18 +144,18 @@ split_at_bb_p (class loop *loop, basic_block bb, tree *border, affine_iv *iv,
 	   value range.  */
 	else
 	  {
-	    int_range<2> r;
+	    Value_Range r (TREE_TYPE (op0));
 	    get_global_range_query ()->range_of_expr (r, op0, stmt);
 	    if (!r.varying_p () && !r.undefined_p ()
 		&& TREE_CODE (op1) == INTEGER_CST)
 	      {
 		wide_int val = wi::to_wide (op1);
-		if (known_eq (val, r.lower_bound ()))
+		if (known_eq (val, wi::to_wide (r.lbound ())))
 		  {
 		    code = (code == EQ_EXPR) ? LE_EXPR : GT_EXPR;
 		    break;
 		  }
-		else if (known_eq (val, r.upper_bound ()))
+		else if (known_eq (val, wi::to_wide (r.ubound ())))
 		  {
 		    code = (code == EQ_EXPR) ? GE_EXPR : LT_EXPR;
 		    break;
diff --git a/gcc/tree-ssa-strlen.cc b/gcc/tree-ssa-strlen.cc
index e09c9cc081f..61c3da22322 100644
--- a/gcc/tree-ssa-strlen.cc
+++ b/gcc/tree-ssa-strlen.cc
@@ -215,7 +215,7 @@ get_range (tree val, gimple *stmt, wide_int minmax[2],
       rvals = get_range_query (cfun);
     }
 
-  value_range vr;
+  Value_Range vr (TREE_TYPE (val));
   if (!rvals->range_of_expr (vr, val, stmt))
     return NULL_TREE;
 
diff --git a/gcc/value-query.cc b/gcc/value-query.cc
index eda71dc89d3..052b7511565 100644
--- a/gcc/value-query.cc
+++ b/gcc/value-query.cc
@@ -156,11 +156,9 @@ range_query::get_tree_range (vrange &r, tree expr, gimple *stmt)
     {
     case INTEGER_CST:
       {
-	irange &i = as_a <irange> (r);
 	if (TREE_OVERFLOW_P (expr))
 	  expr = drop_tree_overflow (expr);
-	wide_int w = wi::to_wide (expr);
-	i.set (TREE_TYPE (expr), w, w);
+	r.set (expr, expr);
 	return true;
       }
 
diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc
index ff68d40c355..0572bf6c8c7 100644
--- a/gcc/vr-values.cc
+++ b/gcc/vr-values.cc
@@ -310,7 +310,8 @@ tree
 simplify_using_ranges::fold_cond_with_ops (enum tree_code code,
 					   tree op0, tree op1, gimple *s)
 {
-  int_range_max r0, r1;
+  Value_Range r0 (TREE_TYPE (op0));
+  Value_Range r1 (TREE_TYPE (op1));
   if (!query->range_of_expr (r0, op0, s)
       || !query->range_of_expr (r1, op1, s))
     return NULL_TREE;
-- 
2.44.0

[COMMITTED 13/16] Accept any vrange in range_includes_zero_p.

[Aldy Hernandez]

Accept a vrange, as this will be used for either integers or pointers.

gcc/ChangeLog:

	* value-range.h (range_includes_zero_p): Accept vrange.
---
 gcc/value-range.h | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/gcc/value-range.h b/gcc/value-range.h
index ede90a496d8..0ab717697f0 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -970,7 +970,7 @@ irange::contains_p (tree cst) const
 }
 
 inline bool
-range_includes_zero_p (const irange &vr)
+range_includes_zero_p (const vrange &vr)
 {
   if (vr.undefined_p ())
     return false;
@@ -978,8 +978,7 @@ range_includes_zero_p (const irange &vr)
   if (vr.varying_p ())
     return true;
 
-  wide_int zero = wi::zero (TYPE_PRECISION (vr.type ()));
-  return vr.contains_p (zero);
+  return vr.contains_p (build_zero_cst (vr.type ()));
 }
 
 // Constructors for irange
-- 
2.44.0

[COMMITTED 14/16] Move print_irange_* out of vrange_printer class.

[Aldy Hernandez]

Move some code out of the irange pretty printers so it can be shared
with pointers.

gcc/ChangeLog:

	* value-range-pretty-print.cc (print_int_bound): New.
	(print_irange_bitmasks): New.
	(vrange_printer::print_irange_bound): Remove.
	(vrange_printer::print_irange_bitmasks): Remove.
	* value-range-pretty-print.h: Remove print_irange_bitmasks and
	print_irange_bound
---
 gcc/value-range-pretty-print.cc | 83 ++++++++++++++++-----------------
 gcc/value-range-pretty-print.h  |  2 -
 2 files changed, 41 insertions(+), 44 deletions(-)

diff --git a/gcc/value-range-pretty-print.cc b/gcc/value-range-pretty-print.cc
index c75cbea3955..b6d23dce6d2 100644
--- a/gcc/value-range-pretty-print.cc
+++ b/gcc/value-range-pretty-print.cc
@@ -30,6 +30,44 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple-range.h"
 #include "value-range-pretty-print.h"
 
+static void
+print_int_bound (pretty_printer *pp, const wide_int &bound, tree type)
+{
+  wide_int type_min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+  wide_int type_max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+
+  if (INTEGRAL_TYPE_P (type)
+      && !TYPE_UNSIGNED (type)
+      && bound == type_min
+      && TYPE_PRECISION (type) != 1)
+    pp_string (pp, "-INF");
+  else if (bound == type_max && TYPE_PRECISION (type) != 1)
+    pp_string (pp, "+INF");
+  else
+    pp_wide_int (pp, bound, TYPE_SIGN (type));
+}
+
+static void
+print_irange_bitmasks (pretty_printer *pp, const irange_bitmask &bm)
+{
+  if (bm.unknown_p ())
+    return;
+
+  pp_string (pp, " MASK ");
+  char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p;
+  unsigned len_mask, len_val;
+  if (print_hex_buf_size (bm.mask (), &len_mask)
+      | print_hex_buf_size (bm.value (), &len_val))
+    p = XALLOCAVEC (char, MAX (len_mask, len_val));
+  else
+    p = buf;
+  print_hex (bm.mask (), p);
+  pp_string (pp, p);
+  pp_string (pp, " VALUE ");
+  print_hex (bm.value (), p);
+  pp_string (pp, p);
+}
+
 void
 vrange_printer::visit (const unsupported_range &r) const
 {
@@ -66,51 +104,12 @@ vrange_printer::visit (const irange &r) const
   for (unsigned i = 0; i < r.num_pairs (); ++i)
     {
       pp_character (pp, '[');
-      print_irange_bound (r.lower_bound (i), r.type ());
+      print_int_bound (pp, r.lower_bound (i), r.type ());
       pp_string (pp, ", ");
-      print_irange_bound (r.upper_bound (i), r.type ());
+      print_int_bound (pp, r.upper_bound (i), r.type ());
       pp_character (pp, ']');
     }
- print_irange_bitmasks (r);
-}
-
-void
-vrange_printer::print_irange_bound (const wide_int &bound, tree type) const
-{
-  wide_int type_min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
-  wide_int type_max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
-
-  if (INTEGRAL_TYPE_P (type)
-      && !TYPE_UNSIGNED (type)
-      && bound == type_min
-      && TYPE_PRECISION (type) != 1)
-    pp_string (pp, "-INF");
-  else if (bound == type_max && TYPE_PRECISION (type) != 1)
-    pp_string (pp, "+INF");
-  else
-    pp_wide_int (pp, bound, TYPE_SIGN (type));
-}
-
-void
-vrange_printer::print_irange_bitmasks (const irange &r) const
-{
-  irange_bitmask bm = r.m_bitmask;
-  if (bm.unknown_p ())
-    return;
-
-  pp_string (pp, " MASK ");
-  char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p;
-  unsigned len_mask, len_val;
-  if (print_hex_buf_size (bm.mask (), &len_mask)
-      | print_hex_buf_size (bm.value (), &len_val))
-    p = XALLOCAVEC (char, MAX (len_mask, len_val));
-  else
-    p = buf;
-  print_hex (bm.mask (), p);
-  pp_string (pp, p);
-  pp_string (pp, " VALUE ");
-  print_hex (bm.value (), p);
-  pp_string (pp, p);
+  print_irange_bitmasks (pp, r.m_bitmask);
 }
 
 void
diff --git a/gcc/value-range-pretty-print.h b/gcc/value-range-pretty-print.h
index ca85fd6157c..44cd6e81298 100644
--- a/gcc/value-range-pretty-print.h
+++ b/gcc/value-range-pretty-print.h
@@ -29,8 +29,6 @@ public:
   void visit (const irange &) const override;
   void visit (const frange &) const override;
 private:
-  void print_irange_bound (const wide_int &w, tree type) const;
-  void print_irange_bitmasks (const irange &) const;
   void print_frange_nan (const frange &) const;
   void print_real_value (tree type, const REAL_VALUE_TYPE &r) const;
 
-- 
2.44.0

[COMMITTED 15/16] Remove range_zero and range_nonzero.

[Aldy Hernandez]

Remove legacy range_zero and range_nonzero as they return by value,
which make it not work in a separate irange and prange world.  Also,
we already have set_zero and set_nonzero methods in vrange.

gcc/ChangeLog:

	* range-op-ptr.cc (pointer_plus_operator::wi_fold): Use method
	range setters instead of out of line functions.
	(pointer_min_max_operator::wi_fold): Same.
	(pointer_and_operator::wi_fold): Same.
	(pointer_or_operator::wi_fold): Same.
	* range-op.cc (operator_negate::fold_range): Same.
	(operator_addr_expr::fold_range): Same.
	(range_op_cast_tests): Same.
	* range.cc (range_zero): Remove.
	(range_nonzero): Remove.
	* range.h (range_zero): Remove.
	(range_nonzero): Remove.
	* value-range.cc (range_tests_misc): Use method instead of out of
	line function.
---
 gcc/range-op-ptr.cc | 14 +++++++-------
 gcc/range-op.cc     | 14 ++++++++------
 gcc/range.cc        | 14 --------------
 gcc/range.h         |  2 --
 gcc/value-range.cc  |  7 ++++---
 5 files changed, 19 insertions(+), 32 deletions(-)

diff --git a/gcc/range-op-ptr.cc b/gcc/range-op-ptr.cc
index 2c85d75b5e8..7343ef635f3 100644
--- a/gcc/range-op-ptr.cc
+++ b/gcc/range-op-ptr.cc
@@ -101,10 +101,10 @@ pointer_plus_operator::wi_fold (irange &r, tree type,
       && !TYPE_OVERFLOW_WRAPS (type)
       && (flag_delete_null_pointer_checks
 	  || !wi::sign_mask (rh_ub)))
-    r = range_nonzero (type);
+    r.set_nonzero (type);
   else if (lh_lb == lh_ub && lh_lb == 0
 	   && rh_lb == rh_ub && rh_lb == 0)
-    r = range_zero (type);
+    r.set_zero (type);
   else
    r.set_varying (type);
 }
@@ -150,9 +150,9 @@ pointer_min_max_operator::wi_fold (irange &r, tree type,
   // are varying.
   if (!wi_includes_zero_p (type, lh_lb, lh_ub)
       && !wi_includes_zero_p (type, rh_lb, rh_ub))
-    r = range_nonzero (type);
+    r.set_nonzero (type);
   else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub))
-    r = range_zero (type);
+    r.set_zero (type);
   else
     r.set_varying (type);
 }
@@ -175,7 +175,7 @@ pointer_and_operator::wi_fold (irange &r, tree type,
   // For pointer types, we are really only interested in asserting
   // whether the expression evaluates to non-NULL.
   if (wi_zero_p (type, lh_lb, lh_ub) || wi_zero_p (type, lh_lb, lh_ub))
-    r = range_zero (type);
+    r.set_zero (type);
   else
     r.set_varying (type);
 }
@@ -236,9 +236,9 @@ pointer_or_operator::wi_fold (irange &r, tree type,
   // whether the expression evaluates to non-NULL.
   if (!wi_includes_zero_p (type, lh_lb, lh_ub)
       && !wi_includes_zero_p (type, rh_lb, rh_ub))
-    r = range_nonzero (type);
+    r.set_nonzero (type);
   else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub))
-    r = range_zero (type);
+    r.set_zero (type);
   else
     r.set_varying (type);
 }
diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 6ea7d624a9b..ab3a4f0b200 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -4364,9 +4364,11 @@ operator_negate::fold_range (irange &r, tree type,
 {
   if (empty_range_varying (r, type, lh, rh))
     return true;
-  // -X is simply 0 - X.
-  return range_op_handler (MINUS_EXPR).fold_range (r, type,
-						   range_zero (type), lh);
+
+// -X is simply 0 - X.
+  int_range<1> zero;
+  zero.set_zero (type);
+  return range_op_handler (MINUS_EXPR).fold_range (r, type, zero, lh);
 }
 
 bool
@@ -4391,7 +4393,7 @@ operator_addr_expr::fold_range (irange &r, tree type,
 
   // Return a non-null pointer of the LHS type (passed in op2).
   if (lh.zero_p ())
-    r = range_zero (type);
+    r.set_zero (type);
   else if (lh.undefined_p () || contains_zero_p (lh))
     r.set_varying (type);
   else
@@ -4675,7 +4677,7 @@ range_op_cast_tests ()
   if (TYPE_PRECISION (integer_type_node)
       > TYPE_PRECISION (short_integer_type_node))
     {
-      r0 = range_nonzero (integer_type_node);
+      r0.set_nonzero (integer_type_node);
       range_cast (r0, short_integer_type_node);
       r1 = int_range<1> (short_integer_type_node,
 			 min_limit (short_integer_type_node),
@@ -4687,7 +4689,7 @@ range_op_cast_tests ()
   //
   // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
   // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
-  r0 = range_nonzero (short_integer_type_node);
+  r0.set_nonzero (short_integer_type_node);
   range_cast (r0, integer_type_node);
   r1 = int_range<1> (integer_type_node, INT (-32768), INT (-1));
   r2 = int_range<1> (integer_type_node, INT (1), INT (32767));
diff --git a/gcc/range.cc b/gcc/range.cc
index c68f387f71c..b362e0f12e0 100644
--- a/gcc/range.cc
+++ b/gcc/range.cc
@@ -29,20 +29,6 @@ along with GCC; see the file COPYING3.  If not see
 #include "ssa.h"
 #include "range.h"
 
-value_range
-range_zero (tree type)
-{
-  wide_int zero = wi::zero (TYPE_PRECISION (type));
-  return value_range (type, zero, zero);
-}
-
-value_range
-range_nonzero (tree type)
-{
-  wide_int zero = wi::zero (TYPE_PRECISION (type));
-  return value_range (type, zero, zero, VR_ANTI_RANGE);
-}
-
 value_range
 range_positives (tree type)
 {
diff --git a/gcc/range.h b/gcc/range.h
index 391ea02daf5..eccb9490e4d 100644
--- a/gcc/range.h
+++ b/gcc/range.h
@@ -21,8 +21,6 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_RANGE_H
 #define GCC_RANGE_H
 
-value_range range_zero (tree type);
-value_range range_nonzero (tree type);
 value_range range_positives (tree type);
 value_range range_negatives (tree type);
 
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index d9689bd469f..a27de5534e1 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -2447,7 +2447,8 @@ range_tests_misc ()
   ASSERT_TRUE (not_255 == range_uchar (0, 254));
 
   // Test that NOT(0) is [1..255] in 8-bit land.
-  int_range<2> not_zero = range_nonzero (unsigned_char_type_node);
+  int_range<2> not_zero;
+  not_zero.set_nonzero (unsigned_char_type_node);
   ASSERT_TRUE (not_zero == range_uchar (1, 255));
 
   // Check that [0,127][0x..ffffff80,0x..ffffff]
@@ -2526,7 +2527,7 @@ range_tests_misc ()
   ASSERT_TRUE (r0 == r2);
 
   // Test that booleans and their inverse work as expected.
-  r0 = range_zero (boolean_type_node);
+  r0.set_zero (boolean_type_node);
   ASSERT_TRUE (r0 == range_false ());
   r0.invert ();
   ASSERT_TRUE (r0 == range_true ());
@@ -2534,7 +2535,7 @@ range_tests_misc ()
   // Make sure NULL and non-NULL of pointer types work, and that
   // inverses of them are consistent.
   tree voidp = build_pointer_type (void_type_node);
-  r0 = range_zero (voidp);
+  r0.set_zero (voidp);
   r1 = r0;
   r0.invert ();
   r0.invert ();
-- 
2.44.0

[COMMITTED 16/16] Callers of irange_bitmask must normalize value/mask pairs.

[Aldy Hernandez]

As per the documentation, irange_bitmask must have the unknown bits in
the mask set to 0 in the value field.  Even though we say we must have
normalized value/mask bits, we don't enforce it, opting to normalize
on the fly in union and intersect.  Avoiding this lazy enforcing as
well as the extra saving/restoring involved in returning the changed
status, gives us a performance increase of 1.25% for VRP and 1.51% for
ipa-CP.

gcc/ChangeLog:

	* tree-ssa-ccp.cc (ccp_finalize): Normalize before calling
	set_bitmask.
	* value-range.cc (irange::intersect_bitmask): Calculate changed
	irange_bitmask bits on our own.
	(irange::union_bitmask): Same.
	(irange_bitmask::verify_mask): Verify that bits are normalized.
	* value-range.h (irange_bitmask::union_): Do not normalize.
	Remove return value.
	(irange_bitmask::intersect): Same.
---
 gcc/tree-ssa-ccp.cc |  1 +
 gcc/value-range.cc  |  7 +++++--
 gcc/value-range.h   | 24 ++++++------------------
 3 files changed, 12 insertions(+), 20 deletions(-)

diff --git a/gcc/tree-ssa-ccp.cc b/gcc/tree-ssa-ccp.cc
index f6a5cd0ee6e..3749126b5f7 100644
--- a/gcc/tree-ssa-ccp.cc
+++ b/gcc/tree-ssa-ccp.cc
@@ -1024,6 +1024,7 @@ ccp_finalize (bool nonzero_p)
 	  unsigned int precision = TYPE_PRECISION (TREE_TYPE (val->value));
 	  wide_int value = wi::to_wide (val->value);
 	  wide_int mask = wide_int::from (val->mask, precision, UNSIGNED);
+	  value = value & ~mask;
 	  set_bitmask (name, value, mask);
 	}
     }
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index a27de5534e1..ca6d521c625 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -2067,7 +2067,8 @@ irange::intersect_bitmask (const irange &r)
 
   irange_bitmask bm = get_bitmask ();
   irange_bitmask save = bm;
-  if (!bm.intersect (r.get_bitmask ()))
+  bm.intersect (r.get_bitmask ());
+  if (save == bm)
     return false;
 
   m_bitmask = bm;
@@ -2099,7 +2100,8 @@ irange::union_bitmask (const irange &r)
 
   irange_bitmask bm = get_bitmask ();
   irange_bitmask save = bm;
-  if (!bm.union_ (r.get_bitmask ()))
+  bm.union_ (r.get_bitmask ());
+  if (save == bm)
     return false;
 
   m_bitmask = bm;
@@ -2133,6 +2135,7 @@ void
 irange_bitmask::verify_mask () const
 {
   gcc_assert (m_value.get_precision () == m_mask.get_precision ());
+  gcc_checking_assert (wi::bit_and (m_mask, m_value) == 0);
 }
 
 void
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 0ab717697f0..11c73faca1b 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -139,8 +139,8 @@ public:
   void set_unknown (unsigned prec);
   bool unknown_p () const;
   unsigned get_precision () const;
-  bool union_ (const irange_bitmask &src);
-  bool intersect (const irange_bitmask &src);
+  void union_ (const irange_bitmask &src);
+  void intersect (const irange_bitmask &src);
   bool operator== (const irange_bitmask &src) const;
   bool operator!= (const irange_bitmask &src) const { return !(*this == src); }
   void verify_mask () const;
@@ -233,29 +233,18 @@ irange_bitmask::operator== (const irange_bitmask &src) const
   return m_value == src.m_value && m_mask == src.m_mask;
 }
 
-inline bool
-irange_bitmask::union_ (const irange_bitmask &orig_src)
+inline void
+irange_bitmask::union_ (const irange_bitmask &src)
 {
-  // Normalize mask.
-  irange_bitmask src (orig_src.m_value & ~orig_src.m_mask, orig_src.m_mask);
-  m_value &= ~m_mask;
-
-  irange_bitmask save (*this);
   m_mask = (m_mask | src.m_mask) | (m_value ^ src.m_value);
   m_value = m_value & src.m_value;
   if (flag_checking)
     verify_mask ();
-  return *this != save;
 }
 
-inline bool
-irange_bitmask::intersect (const irange_bitmask &orig_src)
+inline void
+irange_bitmask::intersect (const irange_bitmask &src)
 {
-  // Normalize mask.
-  irange_bitmask src (orig_src.m_value & ~orig_src.m_mask, orig_src.m_mask);
-  m_value &= ~m_mask;
-
-  irange_bitmask save (*this);
   // If we have two known bits that are incompatible, the resulting
   // bit is undefined.  It is unclear whether we should set the entire
   // range to UNDEFINED, or just a subset of it.  For now, set the
@@ -274,7 +263,6 @@ irange_bitmask::intersect (const irange_bitmask &orig_src)
     }
   if (flag_checking)
     verify_mask ();
-  return *this != save;
 }
 
 // An integer range without any storage.
-- 
2.44.0