SSA range class and removal of VR_ANTI_RANGEs
diff mbox

Message ID dbad7708-d495-402c-c9d8-626a9c8202b9@redhat.com
State New
Headers show

Commit Message

Aldy Hernandez May 23, 2017, 10:48 a.m. UTC
Howdy!

For Andrew's upcoming on-demand range work I have created a range class 
for use in his engine.  Currently, the range class is only for SSA 
integers, but there is no reason why we couldn't adapt this for RTL or 
non-integer types at a later time.

The class can live outside of his work, as can be demonstrated by the 
attached patch.  With it, I was able to rewrite the post-VRP range 
information to use this class and get rid of VR_ANTI_RANGE throughout 
the compiler.  A VR_ANTI_RANGE of ~[5,10] becomes [-MIN,4][11,+MAX].

The internal structure of VRP is unchanged.  I have only changed the 
outward facing structures.

A good example of how much cleaner using an actual range rather than 
VR_ANTI_RANGEs is the change to get_size_range() in the attached patch. 
We remove an assortment of contortions into:

+  /* Remove negative numbers from the range.  */
+  irange positives;
+  range_positives (&positives, exptype, allow_zero ? 0 : 1);
+  if (positives.Intersect (*ir))
+    {
+      /* Remove the unknown parts of a multi-range.
+        This will transform [5,10][20,MAX] into [5,10].  */
+      if (positives.num_ranges () > 1
+         && positives.upper_bound () == wide_int (TYPE_MAX_VALUE 
(exptype)))
+       positives.remove_range (positives.num_ranges () - 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);
      }

A few notes:

1. There are still two uses of VR_ANTI_RANGEs left after this patch: 
ip-cp.c and ipa-prop.c.  I didn't look too hard at these two passes, as 
they are using `struct value_range' which should only have been used 
*before* VRP finishes.  I can work on this as a follow-up.

2. I have not included ChangeLog entries, as I would hate to write them, 
and have the API or significant things change from under me as part of 
the review.  I can certainly cobble the ChangeLog entries as soon as/if 
we agree that this is an acceptable approach.

3. There are lots of unit tests to maintain sanity.  The cast ones in 
particular will definitely need refinement as Andrew's work stresses the 
class.

The attached patch passes bootstrap and tests.

I have also benchmarked an assortment of .ii files (from a previous 
bootstrap) with no noticeable difference in -O2 compilation time.  So, I 
would prefer to tackle any micro-optimizations either as a follow-up or 
if it actually becomes noticeable--. Yeah, yeah, I know.  Wishful 
thinking ;-).


Fire away!
Aldy

p.s. Please refer any comments as to why we need the class, or why we 
need on-demand range information to Andrew :-P.

Comments

Nathan Sidwell May 23, 2017, 11:28 a.m. UTC | #1
On 05/23/2017 06:48 AM, Aldy Hernandez wrote:

> The class can live outside of his work, as can be demonstrated by the 
> attached patch.  With it, I was able to rewrite the post-VRP range 
> information to use this class and get rid of VR_ANTI_RANGE throughout 
> the compiler.  A VR_ANTI_RANGE of ~[5,10] becomes [-MIN,4][11,+MAX].

Seems useful.

> +  /* Remove negative numbers from the range.  */
> +  irange positives;
> +  range_positives (&positives, exptype, allow_zero ? 0 : 1);

'allow_zero ? 0 : 1' looks mighty strange. I know that's a nit, but you 
placed it front and centre!

> +  if (positives.Intersect (*ir))

I notice you have a number of Uppercase member fns ...

nathan
Jakub Jelinek May 23, 2017, 12:11 p.m. UTC | #2
On Tue, May 23, 2017 at 06:48:15AM -0400, Aldy Hernandez wrote:
> --- a/gcc/tree-ssanames.h
> +++ b/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.  */
> -
> -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;
> +/* Used bits information for SSA_NAMEs representing non-pointer variables.  */
> +
> +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;
>  };
>  
>  
> --- a/gcc/tree-core.h
> +++ b/gcc/tree-core.h
> @@ -1416,11 +1413,15 @@ 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 *range_info;
>    } GTY ((desc ("%1.typed.type ?" \
>  		"!POINTER_TYPE_P (TREE_TYPE ((tree)&%1)) : 2"))) info;
>  
> +  /* For non-pointer types, this specifies a mask for the bits that
> +     are known to be set.  */
> +  struct nonzero_bits_def *nonzero_bits;
> +
>    /* Immediate uses list for this SSA_NAME.  */
>    struct ssa_use_operand_t imm_uses;
>  };

I'm worried a lot here about compile time memory usage increase, especially
with EVRP and IPA-VRP and even more so with LTO.
The changes mean that for every SSA_NAME of any kind we now need 8 more
bytes, and for every SSA_NAME that has range info (typically both range info
and nonzero_bits; in the old implementation the two were tied together for a
good reason, many ranges also imply some non-zero bits and from non-zero
bits one can in many cases derive a range) much more than that (through
the nonzero_bits_def you get all the overhead of trailing_wide_ints -
the 3 fields it has, just save on the actual 2 lengths and 2 HWI sets,
but then you add 3x 8 bytes and 6x size of the whole wide_int which is
from what I understood not really meant as the memory storage of wide ints
in data structures, but as something not memory efficient you can work
quickly on (so ideal for automatic variables in functions that work with
those).  So it is a 8 byte growth for SSA_NAMEs without ranges and
8+3*8+6*32-2*4-2*8*x growth for SSA_NAMEs with ranges if x is the number
of HWIs needed to represent the integers of that type (so most commonly
x=1).  For x=1 8+3*8+6*32-2*4-2*8*x is 200 bytes growth.
With say 10000000 SSA_NAMEs, 5000000 of them with ranges, that will be
already a 1GB difference, dunno how many SSA_NAMEs are there e.g. in firefox
LTO build.
Can the nonzero_bits stuff be folded back into irange (and have code to
maintain nonzero_bits in addition to ranges as before (from setting a range
compute or update nonzero_bits and vice versa)?  Can you use
trailing_wide_int for the irange storage of the values?  Can you allocate
only as many HWIs as you really need, rather than always 6?
Again, it can be different between a class you use for accessing the
information and manipulating it and for actual underlying storage on
SSA_NAMEs.

> --- /dev/null
> +++ b/gcc/range.h
> +
> +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
> +#define MAX_RANGES	6
> +
> +typedef class irange *irange_p;
> +enum irange_type { RANGE_PLAIN, RANGE_INVERT };
> +
> +class GTY(()) irange
> +{
> + private:
> +  bool overflow;
> +  size_t n;
> +  void prepend (wide_int x, wide_int y);
> +  void append (wide_int x, wide_int y);
> +  void remove (unsigned i, unsigned j);
> +  void canonicalize ();
> +  /* This is stupid.  These two should be private, but the GTY
> +     machinery can't look inside an irange.  */
> + public:
> +  tree type;
> +  wide_int bounds[MAX_RANGES];
> +
> +public:
...
> +  void Union (wide_int x, wide_int y);
> +  bool Union (const irange &r);
> +  bool Union (const irange &r1, const irange &r2);

Do we really want methods starting with capital letters?
I understand why you can't use union, but I don't think we use CamelCase
anywhere.

	Jakub
David Malcolm May 23, 2017, 2:29 p.m. UTC | #3
On Tue, 2017-05-23 at 14:11 +0200, Jakub Jelinek wrote:
> On Tue, May 23, 2017 at 06:48:15AM -0400, Aldy Hernandez wrote:

[...]

> > --- /dev/null
> > +++ b/gcc/range.h
> > +
> > +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
> > +#define MAX_RANGES	6
> > +
> > +typedef class irange *irange_p;
> > +enum irange_type { RANGE_PLAIN, RANGE_INVERT };

The irange class needs a leading comment, which would go a long way to
documenting the patch as a whole, I think (i.e. I'm not just nit
-picking here :) )

> > +class GTY(()) irange
> > +{
> > + private:
> > +  bool overflow;
> > +  size_t n;
> > +  void prepend (wide_int x, wide_int y);
> > +  void append (wide_int x, wide_int y);
> > +  void remove (unsigned i, unsigned j);
> > +  void canonicalize ();
> > +  /* This is stupid.  These two should be private, but the GTY
> > +     machinery can't look inside an irange.  */
> > + public:
> > +  tree type;
> > +  wide_int bounds[MAX_RANGES];
> > +
> > +public:
> ...
> > +  void Union (wide_int x, wide_int y);
> > +  bool Union (const irange &r);
> > +  bool Union (const irange &r1, const irange &r2);
> 
> Do we really want methods starting with capital letters?
> I understand why you can't use union, but I don't think we use
> CamelCase
> anywhere.

FWIW in the JIT, I have a class switch_ (i.e. with a trailing
underscore).  Maybe we should use trailing underscores for names that
clash with reserved words?

Dave
Jakub Jelinek May 23, 2017, 2:34 p.m. UTC | #4
On Tue, May 23, 2017 at 10:29:58AM -0400, David Malcolm wrote:
> > Do we really want methods starting with capital letters?
> > I understand why you can't use union, but I don't think we use
> > CamelCase
> > anywhere.
> 
> FWIW in the JIT, I have a class switch_ (i.e. with a trailing
> underscore).  Maybe we should use trailing underscores for names that
> clash with reserved words?

union_ and not_ is just fine with me.

	Jakub
Andrew MacLeod May 23, 2017, 2:38 p.m. UTC | #5
On 05/23/2017 08:11 AM, Jakub Jelinek wrote:
> On Tue, May 23, 2017 at 06:48:15AM -0400, Aldy Hernandez wrote:
>> --- a/gcc/tree-ssanames.h
>> +++ b/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.  */
>> -
>> -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;
>> +/* Used bits information for SSA_NAMEs representing non-pointer variables.  */
>> +
>> +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;
>>   };
>>   
>>   
>> --- a/gcc/tree-core.h
>> +++ b/gcc/tree-core.h
>> @@ -1416,11 +1413,15 @@ 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 *range_info;
>>     } GTY ((desc ("%1.typed.type ?" \
>>   		"!POINTER_TYPE_P (TREE_TYPE ((tree)&%1)) : 2"))) info;
>>   
>> +  /* For non-pointer types, this specifies a mask for the bits that
>> +     are known to be set.  */
>> +  struct nonzero_bits_def *nonzero_bits;
>> +
>>     /* Immediate uses list for this SSA_NAME.  */
>>     struct ssa_use_operand_t imm_uses;
>>   };
> I'm worried a lot here about compile time memory usage increase, especially
> with EVRP and IPA-VRP and even more so with LTO.
> The changes mean that for every SSA_NAME of any kind we now need 8 more
> bytes, and for every SSA_NAME that has range info (typically both range info
> and nonzero_bits; in the old implementation the two were tied together for a
> good reason, many ranges also imply some non-zero bits and from non-zero
> bits one can in many cases derive a range) much more than that (through

As follow on work we have discussed an interface which would be able to 
calculate a bitmask (for either zeros or ones) from a range and vice 
versa.. Meaning we wouldn't to need to store both unless the ssa_name is 
used in such a way that it generates both.  ie.  when we create a range 
from a bit operation, we simply store the bit version and not a range, 
otherwise we create an irange but not a bitrange. When you query and ask 
the ssa_name for an irange,  if there is no irange and there is a bit 
pattern, we can generate the irange from that on demand.    Likewise, if 
there is an irange and no bit pattern, we can generate any known on or 
off bits from the irange. The only time there would be both would be 
when we can somehow find some real benefit from having both.. I doubt 
that would be very common.

I think aldy simply copied the bitrange stuff wholesale in a separate 
array just to get it working..  converting between the two was follow on 
work to make things more efficient once it was fundamentally working.



>   
> the nonzero_bits_def you get all the overhead of trailing_wide_ints -
> the 3 fields it has, just save on the actual 2 lengths and 2 HWI sets,
> but then you add 3x 8 bytes and 6x size of the whole wide_int which is
> from what I understood not really meant as the memory storage of wide ints
> in data structures, but as something not memory efficient you can work
> quickly on (so ideal for automatic variables in functions that work with
> those).  So it is a 8 byte growth for SSA_NAMEs without ranges and
> 8+3*8+6*32-2*4-2*8*x growth for SSA_NAMEs with ranges if x is the number
> of HWIs needed to represent the integers of that type (so most commonly
> x=1).  For x=1 8+3*8+6*32-2*4-2*8*x is 200 bytes growth.
> With say 10000000 SSA_NAMEs, 5000000 of them with ranges, that will be
> already a 1GB difference, dunno how many SSA_NAMEs are there e.g. in firefox
> LTO build.
why don't we actually try measuring it and see if it is noticeable? and 
if it is, where the issues really are. You really think we have relevant 
range info  for 50% of the ssa_names in a program?  Id be surprised.  
Again, thats something we should probably measure and see whats 
typical.  the range table should only be used when we can refine the 
global range to something other than range_for_type().

We can also change the representation of the range to be 2 ranges like 
it is today..  we're just defaulting to 3 because it seems like it may 
carry more useful information some times.   The long range plan is that 
this can be tweaked at runtime to only use as much as we need or ant to 
represent a range..  allowing an increase in the range precision for 
specific optimizations that might care, and decreasing it the rest of 
the time.  None of the external API enforces a particular number of ranges.

More importantly, when the on-demand range work comes online it will end 
the proliferation of SSA_NAMES which carry ASSERT_EXPR information.  We 
won't see the trail of new  ssa_names the ASSET_EXPR chains create. I 
suspect that will eliminate storing global ranges and bits for most SSA 
names, which is likely to make this class a win regardless.
That we will have to wait and see until my code is more functional in a 
month or so
> Can the nonzero_bits stuff be folded back into irange (and have code to
> maintain nonzero_bits in addition to ranges as before (from setting a range
> compute or update nonzero_bits and vice versa)?  Can you use
the two are completely different representations of information, it 
seems cleaner to have them separate but allow one to generate the other 
when required.  I suspect most of the time we only need to save one or 
the other. having another class and the ability to convert from one to 
the other seems like a better solution.
> trailing_wide_int for the irange storage of the values?  Can you allocate
> only as many HWIs as you really need, rather than always 6?
probably.
> Again, it can be different between a class you use for accessing the
> information and manipulating it and for actual underlying storage on
> SSA_NAMEs.
Im not familiar with the details of how wide_int and host vs target 
integers really works. I don't think Aldy is either.  If there is a more 
efficient way to store an integer fr this use case then by all means we 
can do that.  to get things working we just used what was easily 
available.   if there is a more efficient way to represent it, perhaps 
it makes sense to create a class for a"memory_efficient_wide_int" and 
allow it to convert back and forth from a wide_int as needed?

I had just assumed that if there was something better for storing it 
we'd have already be using it to save bytes in an ssa_name.

we also need to centralize accessing the range info for an ssa_name.... 
which hasn't been done yet.  That would be a prerequisite for being able 
to convert back and forth between bits and ranges. so we could  have 
something like:

bool ssa_get_irange (irange& i);
bool ssa_get_one_bits (bitmap **ones);
bool ssa_get_zero_bits (bitmap **zeros);

and whatever set_ routines are needed.  those routines would manage the 
irange and bitrange information vectors and call any conversion routines 
as needed.


we'd just like to start pushing the range info out of a branch so it 
starts getting as much use as possible during stage 1.  If later on in 
stage 1 we discover we aren't getting significant enough reduction from 
memory tweaks and the on-demand work, we can always change the 
underlying implementation of the irange class back to be the same 
implementation we have today... it'll just be through a central 
interface rather than everyone accessing the information directly 
themselves.  So that would be our bail-out plan and still be a win in my 
books.

>> --- /dev/null
>> +++ b/gcc/range.h
>> +
>> +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
>> +#define MAX_RANGES	6
>> +
>> +typedef class irange *irange_p;
>> +enum irange_type { RANGE_PLAIN, RANGE_INVERT };
>> +
>> +class GTY(()) irange
>> +{
>> + private:
>> +  bool overflow;
>> +  size_t n;
>> +  void prepend (wide_int x, wide_int y);
>> +  void append (wide_int x, wide_int y);
>> +  void remove (unsigned i, unsigned j);
>> +  void canonicalize ();
>> +  /* This is stupid.  These two should be private, but the GTY
>> +     machinery can't look inside an irange.  */
>> + public:
>> +  tree type;
>> +  wide_int bounds[MAX_RANGES];
>> +
>> +public:
> ...
>> +  void Union (wide_int x, wide_int y);
>> +  bool Union (const irange &r);
>> +  bool Union (const irange &r1, const irange &r2);
> Do we really want methods starting with capital letters?
> I understand why you can't use union, but I don't think we use CamelCase
> anywhere.

alternatives names are welcome.... it was just for convenience.. not 
intended to be CamelCase.. It is an artifact I introduced back when I 
was first coding up the API.  We could change then to range_intersect, 
range_union, and range_not..   just a bit unwieldy for a method name 
within a range class, but certainly usable


Andrew
Andrew MacLeod May 23, 2017, 2:40 p.m. UTC | #6
On 05/23/2017 10:34 AM, Jakub Jelinek wrote:
> On Tue, May 23, 2017 at 10:29:58AM -0400, David Malcolm wrote:
>>> Do we really want methods starting with capital letters?
>>> I understand why you can't use union, but I don't think we use
>>> CamelCase
>>> anywhere.
>> FWIW in the JIT, I have a class switch_ (i.e. with a trailing
>> underscore).  Maybe we should use trailing underscores for names that
>> clash with reserved words?
> union_ and not_ is just fine with me.
>
> 	Jakub

I was also going to ask if we had any rules regarding using a trailing _ 
for the union, intersect and not routines :-)  I'm fine with that as 
well   I'd do intersect_ as wel for some consistency


Andrew
Jakub Jelinek May 23, 2017, 2:54 p.m. UTC | #7
On Tue, May 23, 2017 at 10:38:44AM -0400, Andrew MacLeod wrote:
> As follow on work we have discussed an interface which would be able to
> calculate a bitmask (for either zeros or ones) from a range and vice versa..

Sometimes the range vs. nonzero_bits info is redundant, you can compute
one from the other or vice versa without any information loss, but in many
cases it is not redundant, you can have e.g. known zero least significant or
some middle bits, or the range boundaries are not powers of two or powers of
two - 1.  The point is that with the coexistence of both it can be gradually
improved, first you e.g. find some range, then CCP can use the corresponding
nonzero_bits knowledge from that range in bitwise mask propagation, then you
notice some other bits are known to be zero, perhaps from that adjust the
value range again if possible, ...

> why don't we actually try measuring it and see if it is noticeable? and if
> it is, where the issues really are. You really think we have relevant range
> info  for 50% of the ssa_names in a program?  Id be surprised.  Again, thats
> something we should probably measure and see whats typical.  the range table
> should only be used when we can refine the global range to something other
> than range_for_type().

I'm not used to build firefox and various other large C++ projects with LTO
regularly, so it would be harder for me to get that stuff working and
measure it, but I think e.g. Honza or Martin L. do that often and could
provide hints on what is needed to test that, then we can have exact
numbers.

> We can also change the representation of the range to be 2 ranges like it is

Well, the current representation is just 1 range (2 numbers) + 1 extra
number for the nonzero_bits bitmask.

> More importantly, when the on-demand range work comes online it will end the
> proliferation of SSA_NAMES which carry ASSERT_EXPR information.  We won't
> see the trail of new  ssa_names the ASSET_EXPR chains create. I suspect that
> will eliminate storing global ranges and bits for most SSA names, which is
> likely to make this class a win regardless.

Are you sure it is desirable to recompute it in all cases, rather than just
use what you have recorded and recompute what you don't have computed yet?
E.g. various ranges come from if (cond) __builtin_unreachable (); style
asserts, we do want to drop them at some point and the only spot to keep
that info afterwards is SSA_NAME range info.

> Im not familiar with the details of how wide_int and host vs target integers
> really works. I don't think Aldy is either.  If there is a more efficient
> way to store an integer fr this use case then by all means we can do that.
> to get things working we just used what was easily available.   if there is
> a more efficient way to represent it, perhaps it makes sense to create a
> class for a"memory_efficient_wide_int" and allow it to convert back and
> forth from a wide_int as needed?

You want to talk to Richard Sandiford mainly here I guess.  There are many
flavors of wide ints, for different purposes.

	Jakub
Richard Sandiford May 23, 2017, 3:14 p.m. UTC | #8
Andrew MacLeod <amacleod@redhat.com> writes:
> On 05/23/2017 08:11 AM, Jakub Jelinek wrote:
>> On Tue, May 23, 2017 at 06:48:15AM -0400, Aldy Hernandez wrote:
>>> --- a/gcc/tree-ssanames.h
>>> +++ b/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.  */
>>> -
>>> -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;
>>> +/* Used bits information for SSA_NAMEs representing non-pointer variables.  */
>>> +
>>> +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;
>>>   };
>>>   
>>>   
>>> --- a/gcc/tree-core.h
>>> +++ b/gcc/tree-core.h
>>> @@ -1416,11 +1413,15 @@ 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 *range_info;
>>>     } GTY ((desc ("%1.typed.type ?" \
>>>   		"!POINTER_TYPE_P (TREE_TYPE ((tree)&%1)) : 2"))) info;
>>>   
>>> +  /* For non-pointer types, this specifies a mask for the bits that
>>> +     are known to be set.  */
>>> +  struct nonzero_bits_def *nonzero_bits;
>>> +
>>>     /* Immediate uses list for this SSA_NAME.  */
>>>     struct ssa_use_operand_t imm_uses;
>>>   };
>> I'm worried a lot here about compile time memory usage increase, especially
>> with EVRP and IPA-VRP and even more so with LTO.
>> The changes mean that for every SSA_NAME of any kind we now need 8 more
>> bytes, and for every SSA_NAME that has range info (typically both range info
>> and nonzero_bits; in the old implementation the two were tied together for a
>> good reason, many ranges also imply some non-zero bits and from non-zero
>> bits one can in many cases derive a range) much more than that (through
>
> As follow on work we have discussed an interface which would be able to 
> calculate a bitmask (for either zeros or ones) from a range and vice 
> versa.. Meaning we wouldn't to need to store both unless the ssa_name is 
> used in such a way that it generates both.  ie.  when we create a range 
> from a bit operation, we simply store the bit version and not a range, 
> otherwise we create an irange but not a bitrange. When you query and ask 
> the ssa_name for an irange,  if there is no irange and there is a bit 
> pattern, we can generate the irange from that on demand.    Likewise, if 
> there is an irange and no bit pattern, we can generate any known on or 
> off bits from the irange. The only time there would be both would be 
> when we can somehow find some real benefit from having both.. I doubt 
> that would be very common.
>
> I think aldy simply copied the bitrange stuff wholesale in a separate 
> array just to get it working..  converting between the two was follow on 
> work to make things more efficient once it was fundamentally working.
>
>
>
>>   
>> the nonzero_bits_def you get all the overhead of trailing_wide_ints -
>> the 3 fields it has, just save on the actual 2 lengths and 2 HWI sets,
>> but then you add 3x 8 bytes and 6x size of the whole wide_int which is
>> from what I understood not really meant as the memory storage of wide ints
>> in data structures, but as something not memory efficient you can work
>> quickly on (so ideal for automatic variables in functions that work with
>> those).  So it is a 8 byte growth for SSA_NAMEs without ranges and
>> 8+3*8+6*32-2*4-2*8*x growth for SSA_NAMEs with ranges if x is the number
>> of HWIs needed to represent the integers of that type (so most commonly
>> x=1).  For x=1 8+3*8+6*32-2*4-2*8*x is 200 bytes growth.
>> With say 10000000 SSA_NAMEs, 5000000 of them with ranges, that will be
>> already a 1GB difference, dunno how many SSA_NAMEs are there e.g. in firefox
>> LTO build.
> why don't we actually try measuring it and see if it is noticeable? and 
> if it is, where the issues really are. You really think we have relevant 
> range info  for 50% of the ssa_names in a program?  Id be surprised.  
> Again, thats something we should probably measure and see whats 
> typical.  the range table should only be used when we can refine the 
> global range to something other than range_for_type().
>
> We can also change the representation of the range to be 2 ranges like 
> it is today..  we're just defaulting to 3 because it seems like it may 
> carry more useful information some times.   The long range plan is that 
> this can be tweaked at runtime to only use as much as we need or ant to 
> represent a range..  allowing an increase in the range precision for 
> specific optimizations that might care, and decreasing it the rest of 
> the time.  None of the external API enforces a particular number of ranges.
>
> More importantly, when the on-demand range work comes online it will end 
> the proliferation of SSA_NAMES which carry ASSERT_EXPR information.  We 
> won't see the trail of new  ssa_names the ASSET_EXPR chains create. I 
> suspect that will eliminate storing global ranges and bits for most SSA 
> names, which is likely to make this class a win regardless.
> That we will have to wait and see until my code is more functional in a 
> month or so
>> Can the nonzero_bits stuff be folded back into irange (and have code to
>> maintain nonzero_bits in addition to ranges as before (from setting a range
>> compute or update nonzero_bits and vice versa)?  Can you use
> the two are completely different representations of information, it 
> seems cleaner to have them separate but allow one to generate the other 
> when required.  I suspect most of the time we only need to save one or 
> the other. having another class and the ability to convert from one to 
> the other seems like a better solution.
>> trailing_wide_int for the irange storage of the values?  Can you allocate
>> only as many HWIs as you really need, rather than always 6?
> probably.
>> Again, it can be different between a class you use for accessing the
>> information and manipulating it and for actual underlying storage on
>> SSA_NAMEs.
> Im not familiar with the details of how wide_int and host vs target 
> integers really works. I don't think Aldy is either.  If there is a more 
> efficient way to store an integer fr this use case then by all means we 
> can do that.  to get things working we just used what was easily 
> available.   if there is a more efficient way to represent it, perhaps 
> it makes sense to create a class for a"memory_efficient_wide_int" and 
> allow it to convert back and forth from a wide_int as needed?

Like Jakub says, that's effectively what trailing_wide_int is.
You calculate exactly how many HWIs you need to represent the numbers,
then adjust the amount of allocated memory accordingly.  So once you've
computed the range in a local irange, a version of irange with
trailing_wide_ints would be better for long-term storage.
It has an overhead of 64 bits for <= 5 integers, on top of the
HWIs themselves.

Thanks,
Richard
Andrew MacLeod May 23, 2017, 3:24 p.m. UTC | #9
On 05/23/2017 10:54 AM, Jakub Jelinek wrote:
> On Tue, May 23, 2017 at 10:38:44AM -0400, Andrew MacLeod wrote:
>> As follow on work we have discussed an interface which would be able to
>> calculate a bitmask (for either zeros or ones) from a range and vice versa..
> Sometimes the range vs. nonzero_bits info is redundant, you can compute
> one from the other or vice versa without any information loss, but in many
> cases it is not redundant, you can have e.g. known zero least significant or
> some middle bits, or the range boundaries are not powers of two or powers of
> two - 1.  The point is that with the coexistence of both it can be gradually
> improved, first you e.g. find some range, then CCP can use the corresponding
> nonzero_bits knowledge from that range in bitwise mask propagation, then you
> notice some other bits are known to be zero, perhaps from that adjust the
> value range again if possible, ...

Right, but we do only need to store both for those cases which we are 
actually refining the info.  and via a central manager of the 
information it can know when that is a thing to do and do it.  I also 
hope to ad some of the bit inormation ot the on demand system.. tat'll 
come later tho.    I simply maintain that the vast majority of ssa_names 
are unlikely to need both, not that we never need both.   This seems 
like statistics that shouldn't be too hard to find with some simple 
looking at the data at the end of compilation or various passes.

>
>> why don't we actually try measuring it and see if it is noticeable? and if
>> it is, where the issues really are. You really think we have relevant range
>> info  for 50% of the ssa_names in a program?  Id be surprised.  Again, thats
>> something we should probably measure and see whats typical.  the range table
>> should only be used when we can refine the global range to something other
>> than range_for_type().
> I'm not used to build firefox and various other large C++ projects with LTO
> regularly, so it would be harder for me to get that stuff working and
> measure it, but I think e.g. Honza or Martin L. do that often and could
> provide hints on what is needed to test that, then we can have exact
> numbers.
that seems reasonable.  I think we ought to look at the low hanging 
fruit for making it more efficient to start with before hassling them or 
that.. unless it is trivial.   It would be useful t have input from 
"heavy" application users if there is any/much impact.
>> We can also change the representation of the range to be 2 ranges like it is
> Well, the current representation is just 1 range (2 numbers) + 1 extra
> number for the nonzero_bits bitmask.

oh yeah,right.... but anti range is evil. Its worth losing a little bit 
of memory to get rid of that, imo  :-)

>
>> More importantly, when the on-demand range work comes online it will end the
>> proliferation of SSA_NAMES which carry ASSERT_EXPR information.  We won't
>> see the trail of new  ssa_names the ASSET_EXPR chains create. I suspect that
>> will eliminate storing global ranges and bits for most SSA names, which is
>> likely to make this class a win regardless.
> Are you sure it is desirable to recompute it in all cases, rather than just
> use what you have recorded and recompute what you don't have computed yet?
> E.g. various ranges come from if (cond) __builtin_unreachable (); style
> asserts, we do want to drop them at some point and the only spot to keep
> that info afterwards is SSA_NAME range info.

I think it will be desirable in most cases.  The on-demand system does 
*not* use assert_exprs.   It will make them mostly obsolete, and the 
goal is to eventually eliminate them from the IL completely.

Most assert_exprs exist to provide ranges on sub-branches of the CFG.  
These we are likely to be able to simply replace with the on-demand 
mechanism.  I suspect we'll find some cases where we find its more 
useful to have a new global ssa_name which carries information,  but I 
expect the situation which requires that to be fairly rare.

There will be a cycle where I have to identify cases we missing and 
catch those... or introduce a new ssa_name to handle the situation until 
such time that it can be addressed. I hope to get thru most of that in 
this stage 1
>> Im not familiar with the details of how wide_int and host vs target integers
>> really works. I don't think Aldy is either.  If there is a more efficient
>> way to store an integer fr this use case then by all means we can do that.
>> to get things working we just used what was easily available.   if there is
>> a more efficient way to represent it, perhaps it makes sense to create a
>> class for a"memory_efficient_wide_int" and allow it to convert back and
>> forth from a wide_int as needed?
> You want to talk to Richard Sandiford mainly here I guess.  There are many
> flavors of wide ints, for different purposes.
I did not know that :-)   Aldy, maybe you should have a chat :-)

Andrew
Martin Sebor May 23, 2017, 5:19 p.m. UTC | #10
>> --- /dev/null
>> +++ b/gcc/range.h
>> +
>> +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
>> +#define MAX_RANGES	6
>> +
>> +typedef class irange *irange_p;
>> +enum irange_type { RANGE_PLAIN, RANGE_INVERT };
>> +
>> +class GTY(()) irange
>> +{
>> + private:
>> +  bool overflow;
>> +  size_t n;

Since space usage is of concern, defining the biggest member first
and using a smaller type should help as the first step.  Say:

   tree type;
   wide_int bounds[MAX_RANGES];
   unsigned char n: 7;   // 127 > MAX_RANGES
   bool overflow: 1 ;

There may be other tricks to play with the array although turning
it into a flexible array member will defeat the bit-field gain.

>> +  void prepend (wide_int x, wide_int y);
>> +  void append (wide_int x, wide_int y);
>> +  void remove (unsigned i, unsigned j);
>> +  void canonicalize ();
>> +  /* This is stupid.  These two should be private, but the GTY
>> +     machinery can't look inside an irange.  */
>> + public:
>> +  tree type;
>> +  wide_int bounds[MAX_RANGES];
>> +
>> +public:
> ...
>> +  void Union (wide_int x, wide_int y);
>> +  bool Union (const irange &r);
>> +  bool Union (const irange &r1, const irange &r2);
>
> Do we really want methods starting with capital letters?
> I understand why you can't use union, but I don't think we use CamelCase
> anywhere.

One way to get around the problem is to make the functions non-
members and rename them in the process:

   irange& irange_union (irange &, wide_int, wide_int);
   irange& irange_union (irange &, const irange &);
   irange& irange_union (irange &, const irange &, const irange &);

Making them friends of class irange will let them access private
members.  Returning irange& makes chaining multiple calls possible.

I think making interfaces thin and providing operations as non
member functions is also considered the preferable design these
days.

Martin
Martin Sebor May 23, 2017, 7:26 p.m. UTC | #11
On 05/23/2017 04:48 AM, Aldy Hernandez wrote:
> Howdy!
>
> For Andrew's upcoming on-demand range work I have created a range class
> for use in his engine.  Currently, the range class is only for SSA
> integers, but there is no reason why we couldn't adapt this for RTL or
> non-integer types at a later time.
>
> The class can live outside of his work, as can be demonstrated by the
> attached patch.  With it, I was able to rewrite the post-VRP range
> information to use this class and get rid of VR_ANTI_RANGE throughout
> the compiler.  A VR_ANTI_RANGE of ~[5,10] becomes [-MIN,4][11,+MAX].
>
> The internal structure of VRP is unchanged.  I have only changed the
> outward facing structures.
>
> A good example of how much cleaner using an actual range rather than
> VR_ANTI_RANGEs is the change to get_size_range() in the attached patch.
> We remove an assortment of contortions into:
>
> +  /* Remove negative numbers from the range.  */
> +  irange positives;
> +  range_positives (&positives, exptype, allow_zero ? 0 : 1);
> +  if (positives.Intersect (*ir))
> +    {
> +      /* Remove the unknown parts of a multi-range.
> +        This will transform [5,10][20,MAX] into [5,10].  */
> +      if (positives.num_ranges () > 1
> +         && positives.upper_bound () == wide_int (TYPE_MAX_VALUE
> (exptype)))
> +       positives.remove_range (positives.num_ranges () - 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);
>      }
>
> A few notes:
>
> 1. There are still two uses of VR_ANTI_RANGEs left after this patch:
> ip-cp.c and ipa-prop.c.  I didn't look too hard at these two passes, as
> they are using `struct value_range' which should only have been used
> *before* VRP finishes.  I can work on this as a follow-up.
>
> 2. I have not included ChangeLog entries, as I would hate to write them,
> and have the API or significant things change from under me as part of
> the review.  I can certainly cobble the ChangeLog entries as soon as/if
> we agree that this is an acceptable approach.
>
> 3. There are lots of unit tests to maintain sanity.  The cast ones in
> particular will definitely need refinement as Andrew's work stresses the
> class.
>
> The attached patch passes bootstrap and tests.
>
> I have also benchmarked an assortment of .ii files (from a previous
> bootstrap) with no noticeable difference in -O2 compilation time.  So, I
> would prefer to tackle any micro-optimizations either as a follow-up or
> if it actually becomes noticeable--. Yeah, yeah, I know.  Wishful
> thinking ;-).
>
>
> Fire away!
> Aldy
>
> p.s. Please refer any comments as to why we need the class, or why we
> need on-demand range information to Andrew :-P.

I'm pretty excited about this work (as you know :) so just a few
longish comments on/suggestions for the design of the class to
make it ever so slightly easier to work with.  Since YMMV, feel
free to disregard what you don't like.

+#define MAX_RANGES	6
+

This seems like an implementation detail that clients of the class
shouldn't know about or have access to.  Suggest to hide that from
the interface (e.g., by making a private member of irange).

+typedef class irange *irange_p;

FWIW, I find pointer typedefs more trouble than worth.  They
obscure the fact that they are pointers and cannot be made const
by adding the const qualifier.  E.g., this:

   void foo (const irange_p);

doesn't declare foo to take a pointer to a const range as one
might hope but rather a const pointer to a non-const range.

+enum irange_type { RANGE_PLAIN, RANGE_INVERT };

Consider making this a member and renaming it to something like
'kind' to avoid giving the impression that it's somehow a type
that's related to class irange.  Making it a member also avoids
the need to prefix the enumerators with RANGE_, and makes it
convenient to refer to PLAIN and INVERT using the dot and arrow
operators (in addition to irange::PLAIN).

+
+class GTY(()) irange
+{
+ private:
+  bool overflow;
+  size_t n;

Suggest to use a more descriptive name for the member.

+  void prepend (wide_int x, wide_int y);
+  void append (wide_int x, wide_int y);
+  void remove (unsigned i, unsigned j);
+  void canonicalize ();
+  /* This is stupid.  These two should be private, but the GTY
+     machinery can't look inside an irange.  */
+ public:
+  tree type;
+  wide_int bounds[MAX_RANGES];
+
+public:
+  irange () { type = NULL_TREE; n = 0; }
+  irange (tree t);

Should the range be implicitly convertible from any tree or would
it better if it required explicit conversion (i.e., should the ctor
be declared explicit)?  The usual rule of thumb is to err on the
side of safety to avoid accidentally creating objects of the class).

+  irange (tree t, wide_int lbound, wide_int ubound,
+	  irange_type rt = RANGE_PLAIN);
+  irange (const irange &r);
+
+  void set_range (tree t);
+  void set_range (tree t, wide_int lbound, wide_int ubound,
+		  irange_type rt = RANGE_PLAIN);
+
+  bool overflow_p () { return overflow && !TYPE_OVERFLOW_WRAPS (type);

Suggest to declare this function const.

}
+  void set_overflow () { overflow = true; }
+  void clear_overflow () { overflow = false; }
+
+  unsigned num_ranges () { return n / 2; }
+  wide_int lower_bound () const { return bounds[0]; }
+  wide_int lower_bound (unsigned index);

The implementation does this:

+  gcc_assert (n != 0 && index <= n/2);

Why is n required to be non-zero when overload just above has
well-defined behavior for the same index?  That seems needlessly
error prone (could cause ICEs), and will require callers to use
different algorithms for accessing the first lower bound versus
those with non-zero indices.  Suggest to define a single inline
form the function instead (taking an index, possibly with
a default argument).  That way the same algorithm can be used
to access any element.

+  wide_int upper_bound () const { return bounds[n - 1]; }
+  wide_int upper_bound (unsigned index);

Suggest to declare these five functions const.

+
+  void remove_range (unsigned i) { remove (i, i + 1); }

Since there is a remove() function, suggest to rename the one
argument form to remove() to avoid having to remember which is
which when calling it.

+  void clear () { n = 0; }
+  void clear (tree t) { type = t; n = 0; overflow = false; }
+  bool empty_p () const { return !n; }


+  bool range_for_type_p () const;
+  bool simple_range_p () const { return n == 2; }
+
+  void dump ();
+  void dump (pretty_printer *pp);
+  void dump (FILE *);

Suggest to declare these three const.

+
+  bool valid_p ();

Suggest to make it const.

+  void cast (tree type);
+  bool contains_p (wide_int element);
+  bool contains_p (tree);
+
+  tree get_type () { return type; }

Suggest to declare these three functions const (even if they call
functions that aren't const, as long as they don't modify any members
they should be const; it's better to cast the constness away in the
implementation than let "const-incorrect" implementation details leak
into the interface).

+
+  irange& operator= (const irange &r);
+  irange& operator= (tree t);
+
+  bool operator== (const irange &r) const;
+  bool operator!= (const irange &r) const { return !(*this == r); }

Suggest to define equality and inequality as non-members for
symmetry.  Since there is an implicit conversion from tree to
irange, this is valid:

   void f (irange ir, tree t)
   {
     ir == t;
   }

but with operator==() as a member, this isn't

   void f (irange ir, tree t)
   {
     t == ir;
   }

making the operator asymmetric (the opposite is usually expected).

+
+  void Union (wide_int x, wide_int y);
+  bool Union (const irange &r);
+  bool Union (const irange &r1, const irange &r2);
+
+  // THIS = THIS ^ [X,Y].  Return TRUE if result is non-empty.
+  bool Intersect (wide_int x, wide_int y, bool readonly = false);
+  // THIS = THIS ^ R.  Return TRUE if result is non-empty.
+  // THIS = R1 ^ R2.  Return TRUE if result is non-empty.
+  bool Intersect (const irange &r1, const irange &r2, bool readonly = 
false);
+  // Return TRUE if THIS ^ R will be non-empty.
+  bool Intersect_p (const irange &r)
+    { return Intersect (r, /*readonly=*/true); }

I would suggest the following changes to Union, Intersect, and Not:

1) Define all three members without the readonly argument and
    returning irange& (i.e., *this).  The return value can be
    used wherever irange& is expected, and the is_empty() member
    function can be called on it to obtain the same result.  E.g.,
    Intersect A with B, storing the result in A:

    irange A, B;
    if (A.Intersect (B).is_empty ()) { ... }

2) Add non-members like so:

   irange range_union (const irange &lhs, const irange &rhs)
   {
     return irange (lhs).Union (rhs);
   }

   and find out if the union of A or B is empty without modifying
   either argument:

   irange A, B;
   if (range_union (A, B).is_empty ()) { ... }

+
+  bool Not ();
+  bool Not (const irange& r);

Given that this function computes the inverted range of *this,
should it be called something like Invert instead?

Martin

PS For the names, have you considered using the bitwise operators?
I.e., operator| for union, operator& for intersection, and operator~
for not (aka invert).
Andrew MacLeod May 23, 2017, 7:47 p.m. UTC | #12
On 05/23/2017 03:26 PM, Martin Sebor wrote:
> On 05/23/2017 04:48 AM, Aldy Hernandez wrote:
>> Howdy!
> +typedef class irange *irange_p;
>
> FWIW, I find pointer typedefs more trouble than worth.  They
> obscure the fact that they are pointers and cannot be made const
> by adding the const qualifier.  E.g., this:
>
>   void foo (const irange_p);
>
> doesn't declare foo to take a pointer to a const range as one
> might hope but rather a const pointer to a non-const range.
>

yeah, the trend is to expose pointers, like 'gimple *' does. extracting 
types from trees into 'ttype *' was doing the same thing.  we should be 
able to punt on irange_p.

>
> +
> +public:
> +  irange () { type = NULL_TREE; n = 0; }
> +  irange (tree t);
>
> Should the range be implicitly convertible from any tree or would
> it better if it required explicit conversion (i.e., should the ctor
> be declared explicit)?  The usual rule of thumb is to err on the
> side of safety to avoid accidentally creating objects of the class).
>
the original idea was to allow it to be created from either
   a) an ssa_name, which would return what global range we know about 
the name,
   b) a type , and set it to the range_for_type().
and it would gcc_assert fail on any other kind.

a) may or may not be a good idea or useful long term... it might be 
better to simply always go through a central ssa_name range server 
class, which doesnt quite exist yet.  That would subsume this.
b) some day (haha), this would be statically types as irange (ttype *) 
rather than tree for types.    It could also be provided trough an 
external routine.. irange_for_type (tree type)

neither are probably needed

> +  irange (tree t, wide_int lbound, wide_int ubound,
> +      irange_type rt = RANGE_PLAIN);
> +  irange (const irange &r);
> +
> +  void set_range (tree t);
> +  void set_range (tree t, wide_int lbound, wide_int ubound,
> +          irange_type rt = RANGE_PLAIN);
> +
> +  bool overflow_p () { return overflow && !TYPE_OVERFLOW_WRAPS (type);
>
> Suggest to declare this function const.

I figured this would come up.  We ought to properly constify the entire 
class where appropriate. the more code that gets written using 
un-constified code, the harder it is to go back an constify it.


> PS For the names, have you considered using the bitwise operators?
> I.e., operator| for union, operator& for intersection, and operator~
> for not (aka invert).


I'd be more tempted to follow the bitmap model and ( how you mentioned 
earlier I think) have friend routines for range_intersect(), 
range_invert(), range_union().  especially since we want 2 variations. 
one which takes a single parameter and works into 'this',  and another 
variation that builds a new range from 2 parametered ranges .

I feel overloading those operators would make the code a little less 
readable?  at least to me.

Andrew
Richard Biener May 24, 2017, 8:11 a.m. UTC | #13
On Tue, May 23, 2017 at 12:48 PM, Aldy Hernandez <aldyh@redhat.com> wrote:
> Howdy!
>
> For Andrew's upcoming on-demand range work I have created a range class for
> use in his engine.  Currently, the range class is only for SSA integers, but
> there is no reason why we couldn't adapt this for RTL or non-integer types
> at a later time.
>
> The class can live outside of his work, as can be demonstrated by the
> attached patch.  With it, I was able to rewrite the post-VRP range
> information to use this class and get rid of VR_ANTI_RANGE throughout the
> compiler.  A VR_ANTI_RANGE of ~[5,10] becomes [-MIN,4][11,+MAX].
>
> The internal structure of VRP is unchanged.  I have only changed the outward
> facing structures.
>
> A good example of how much cleaner using an actual range rather than
> VR_ANTI_RANGEs is the change to get_size_range() in the attached patch. We
> remove an assortment of contortions into:
>
> +  /* Remove negative numbers from the range.  */
> +  irange positives;
> +  range_positives (&positives, exptype, allow_zero ? 0 : 1);
> +  if (positives.Intersect (*ir))
> +    {
> +      /* Remove the unknown parts of a multi-range.
> +        This will transform [5,10][20,MAX] into [5,10].  */
> +      if (positives.num_ranges () > 1
> +         && positives.upper_bound () == wide_int (TYPE_MAX_VALUE
> (exptype)))
> +       positives.remove_range (positives.num_ranges () - 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);
>      }
>
> A few notes:
>
> 1. There are still two uses of VR_ANTI_RANGEs left after this patch: ip-cp.c
> and ipa-prop.c.  I didn't look too hard at these two passes, as they are
> using `struct value_range' which should only have been used *before* VRP
> finishes.  I can work on this as a follow-up.

So my ultimate goal was to somehow make the range operations in VRP
(union, intersect, unary and binary ops) have an API that can be easily
used with both the internal VRP lattice ranges and the SSA name associated
ranges.  Now that we have C++ we could either use some kind of adaptors
or make them templates -- or something else.

> 2. I have not included ChangeLog entries, as I would hate to write them, and
> have the API or significant things change from under me as part of the
> review.  I can certainly cobble the ChangeLog entries as soon as/if we agree
> that this is an acceptable approach.
>
> 3. There are lots of unit tests to maintain sanity.  The cast ones in
> particular will definitely need refinement as Andrew's work stresses the
> class.
>
> The attached patch passes bootstrap and tests.
>
> I have also benchmarked an assortment of .ii files (from a previous
> bootstrap) with no noticeable difference in -O2 compilation time.  So, I
> would prefer to tackle any micro-optimizations either as a follow-up or if
> it actually becomes noticeable--. Yeah, yeah, I know.  Wishful thinking ;-).

+      // If we will overflow, don't bother.  This will handle unsigned
+      // underflow which doesn't set the overflow bit.
+      //
+      // Note: Perhaps all these &ovf checks are unecessary since we
+      // are manually checking for overflow with the if() below.

no multi-line // comments please.  What's wrong with /* ... */?

+// Convert the current range in place into a range of type NEW_TYPE.
+// The type of the original range is changed to the new type.
+
+void
+irange::cast (tree new_type)
+{
+  if (!n)

so this duplicates VRP unary op with NOP/CONVERT_EXPR.

+void
+irange::Union (wide_int x, wide_int y)
+{

why capital U?




>
> Fire away!
> Aldy
>
> p.s. Please refer any comments as to why we need the class, or why we need
> on-demand range information to Andrew :-P.
Richard Biener May 24, 2017, 8:25 a.m. UTC | #14
..On Tue, May 23, 2017 at 5:24 PM, Andrew MacLeod <amacleod@redhat.com> wrot
> On 05/23/2017 10:54 AM, Jakub Jelinek wrote:
>>
>> On Tue, May 23, 2017 at 10:38:44AM -0400, Andrew MacLeod wrote:
>>>
>>> As follow on work we have discussed an interface which would be able to
>>> calculate a bitmask (for either zeros or ones) from a range and vice
>>> versa..
>>
>> Sometimes the range vs. nonzero_bits info is redundant, you can compute
>> one from the other or vice versa without any information loss, but in many
>> cases it is not redundant, you can have e.g. known zero least significant
>> or
>> some middle bits, or the range boundaries are not powers of two or powers
>> of
>> two - 1.  The point is that with the coexistence of both it can be
>> gradually
>> improved, first you e.g. find some range, then CCP can use the
>> corresponding
>> nonzero_bits knowledge from that range in bitwise mask propagation, then
>> you
>> notice some other bits are known to be zero, perhaps from that adjust the
>> value range again if possible, ...
>
>
> Right, but we do only need to store both for those cases which we are
> actually refining the info.  and via a central manager of the information it
> can know when that is a thing to do and do it.  I also hope to ad some of
> the bit inormation ot the on demand system.. tat'll come later tho.    I
> simply maintain that the vast majority of ssa_names are unlikely to need
> both, not that we never need both.   This seems like statistics that
> shouldn't be too hard to find with some simple looking at the data at the
> end of compilation or various passes.
>
>>
>>> why don't we actually try measuring it and see if it is noticeable? and
>>> if
>>> it is, where the issues really are. You really think we have relevant
>>> range
>>> info  for 50% of the ssa_names in a program?  Id be surprised.  Again,
>>> thats
>>> something we should probably measure and see whats typical.  the range
>>> table
>>> should only be used when we can refine the global range to something
>>> other
>>> than range_for_type().
>>
>> I'm not used to build firefox and various other large C++ projects with
>> LTO
>> regularly, so it would be harder for me to get that stuff working and
>> measure it, but I think e.g. Honza or Martin L. do that often and could
>> provide hints on what is needed to test that, then we can have exact
>> numbers.
>
> that seems reasonable.  I think we ought to look at the low hanging fruit
> for making it more efficient to start with before hassling them or that..
> unless it is trivial.   It would be useful t have input from "heavy"
> application users if there is any/much impact.
>>>
>>> We can also change the representation of the range to be 2 ranges like it
>>> is
>>
>> Well, the current representation is just 1 range (2 numbers) + 1 extra
>> number for the nonzero_bits bitmask.
>
>
> oh yeah,right.... but anti range is evil. Its worth losing a little bit of
> memory to get rid of that, imo  :-)

Well, anti-ranges are "evil" for actual working with ranges.  They are nice
for optimizing the storage requirements though.

As I'm replying late I'll add that yes, it does make a difference in memory
use.  We've seen this with IPA VRP info eating up 1 GB extra memory
for firefox so we optimized it to use trailing wide-ints.  So ..

+#define MAX_RANGES     6
...
+class GTY(()) irange
+{
...
+ public:
+  tree type;
+  wide_int bounds[MAX_RANGES];

is definitely a no-go.  type is also redundant.  Making 'n' a size_t is stupid.

Please apply some more common sense here...

We need to really think about making this a bit more flexible than just handling
integer ranges, eventually tracking non-zero bits as well.

So first of all I'd suggest to make MAX_RANGES a template parameter
so we can eventually use the same representation in both the VRP lattice,
the SSA name info and the basic range ops (I see you re-implemented all
of those rather than refactoring the VRP ones which would have benefited
most from "getting rid of anti-ranges").

What's this overflow flag for anyway?

That said, I think it's the wrong approach to start mucking with SSA name
associated ranges given they are supposed to be a cheap storage variant
of what VRP computes.  Start by making the VRP machinery work from
on-demand-ranges.  I do have some prototypes from last year or the year
before to do this -- the helpers VRP machinery is already generic enough
if you make use of VRPs range type.

>>
>>> More importantly, when the on-demand range work comes online it will end
>>> the
>>> proliferation of SSA_NAMES which carry ASSERT_EXPR information.  We won't
>>> see the trail of new  ssa_names the ASSET_EXPR chains create. I suspect
>>> that
>>> will eliminate storing global ranges and bits for most SSA names, which
>>> is
>>> likely to make this class a win regardless.
>>
>> Are you sure it is desirable to recompute it in all cases, rather than
>> just
>> use what you have recorded and recompute what you don't have computed yet?
>> E.g. various ranges come from if (cond) __builtin_unreachable (); style
>> asserts, we do want to drop them at some point and the only spot to keep
>> that info afterwards is SSA_NAME range info.
>
>
> I think it will be desirable in most cases.  The on-demand system does *not*
> use assert_exprs.   It will make them mostly obsolete, and the goal is to
> eventually eliminate them from the IL completely.

They are not in the IL.  They are only temporarily there during VRP
(not early VRP
for example) to make VRP work as a SSA propagation pass.

> Most assert_exprs exist to provide ranges on sub-branches of the CFG.  These
> we are likely to be able to simply replace with the on-demand mechanism.  I
> suspect we'll find some cases where we find its more useful to have a new
> global ssa_name which carries information,  but I expect the situation which
> requires that to be fairly rare.
>
> There will be a cycle where I have to identify cases we missing and catch
> those... or introduce a new ssa_name to handle the situation until such time
> that it can be addressed. I hope to get thru most of that in this stage 1

But if you do on-demand ranges why do you need to change the SSA name
associated ranges at all?

>>>
>>> Im not familiar with the details of how wide_int and host vs target
>>> integers
>>> really works. I don't think Aldy is either.  If there is a more efficient
>>> way to store an integer fr this use case then by all means we can do
>>> that.
>>> to get things working we just used what was easily available.   if there
>>> is
>>> a more efficient way to represent it, perhaps it makes sense to create a
>>> class for a"memory_efficient_wide_int" and allow it to convert back and
>>> forth from a wide_int as needed?
>>
>> You want to talk to Richard Sandiford mainly here I guess.  There are many
>> flavors of wide ints, for different purposes.
>
> I did not know that :-)   Aldy, maybe you should have a chat :-)

There's trailing_wide_ints.  But having 6 of them is still expensive.

Something nice would be to make wide_ints not tied to use HOST_WIDE_INT
as basic element type but for example uint32.

> Andrew
Andrew MacLeod May 24, 2017, 3:43 p.m. UTC | #15
stlll bounced.. html must have snuck in somewhere, and the mailer sent 
it anyway -P

trying again...

On 05/24/2017 11:38 AM, Andrew MacLeod wrote:
> On 05/24/2017 04:25 AM, Richard Biener wrote:
> >> What's this overflow flag for anyway?
>
> The new on-demand range calculators do operations on ranges, and that 
> flag is set when a range calculation may have overflowed... which is 
> of use when issuing warnings or deciding to not use a range.
> ie given a made up example:
>
> signed char a,b;
> a_1 = b_3 +10;
> if (b_3 > 100)  foo (a_1)
>
> on the true side we know b_3 has the range [101,127].  It also 
> calculates the range of a_1 as [111, 127][-128,-119]  and sets the 
> overflow bit since the calculation of a_1 can overflow for some 
> elements of the range of b_3.    Anyone wanting to use the range can 
> check the overflow if its something they care about.  The overflow 
> stuff has not been completely flushed out yet, but it is in place for 
> the moment.  we can decide down the road if it serves enough purpose 
> to stick around, or needs expansion, or whatever.
> >> > That said, I think it's the wrong approach to start mucking with 
> SSA > name associated ranges given they are supposed to be a cheap 
> storage > variant of what VRP computes.  Start by making the VRP 
> machinery work > from on-demand-ranges.  I do have some prototypes 
> from last year or > the year before to do this -- the helpers VRP 
> machinery is already > generic enough if you make use of VRPs range type.
>
> well its also no longer just contained to VRP. This work is all driven 
> by the desire of other optimizations to access range information.  
> Some have hacked their required bits into vrp, making vrp a sort of  
> mini optimization phase, others have attempted to leverage 
> assert_exprs at their point in time (not too successfully I think?) , 
> others just live with the lack of contextual range info after VRP... 
> after looking at it, i decided trying to teach other optimizations 
> about assert_expr in order to make their info available later was not 
> something that seemed like a good long term solution.
>
> The most pressing matter was the desire for CFG sensitive range 
> information outside of VRP.  Since assert_exprs are gone after VRP, we 
> loose the information on the branches of a diamond without a lot of 
> hackery.  The on-demand system is positioned to leave VRP as is for 
> the moment, and allow passes outside of VRP to pick up the range info 
> VRP generated and refine that range based on branches.   Once this is 
> working well, I'd have the confidence to then maybe go into VRP and 
> try to replace the assert_exprs with the on demand system.  This 
> allows the proving ground to be outside of VRP for just the passes 
> which are desperate for better ranges.   This allows the on-demand 
> system to be tested, utilized, and various efficiencies explored 
> without impacting any optimizations negatively by trying to replace 
> VRP up front and not getting everything it does or consuming too much 
> compilation time or memory..
>
> I'll shortly prepare the writeup for the on demand mechanism.. I'm 
> still getting it working :-P
> >> >>> >>>> More importantly, when the on-demand range work comes 
> online it >>>> will end the proliferation of SSA_NAMES which carry 
> ASSERT_EXPR >>>> information.  We won't see the trail of new  
> ssa_names the >>>> ASSET_EXPR chains create. I suspect that will 
> eliminate storing >>>> global ranges and bits for most SSA names, 
> which is likely to >>>> make this class a win regardless. >>> >>> Are 
> you sure it is desirable to recompute it in all cases, rather >>> than 
> just use what you have recorded and recompute what you don't >>> have 
> computed yet? E.g. various ranges come from if (cond) >>> 
> __builtin_unreachable (); style asserts, we do want to drop them >>> 
> at some point and the only spot to keep that info afterwards is >>> 
> SSA_NAME range info. >> >> >> I think it will be desirable in most 
> cases.  The on-demand system >> does *not* use assert_exprs.   It will 
> make them mostly obsolete, >> and the goal is to eventually eliminate 
> them from the IL >> completely. > > They are not in the IL.  They are 
> only temporarily there during VRP > (not early VRP for example) to 
> make VRP work as a SSA propagation > pass.
>
> right but a number of other optimization want the contextual 
> information assert_expr's provide.. outside of VRP.  so either we have 
> to keep the multitude of ssa_names that asset_exprs create in order to 
> maintain the range info, either via copies or maintaining the 
> assert_expr, or we do something else.
>
> >> Most assert_exprs exist to provide ranges on sub-branches of the >> CFG.  These we are likely to be able to simply replace with the >> 
> on-demand mechanism.  I suspect we'll find some cases where we find >> 
> its more useful to have a new global ssa_name which carries >> 
> information,  but I expect the situation which requires that to be >> 
> fairly rare. >> >> There will be a cycle where I have to identify 
> cases we missing and >> catch those... or introduce a new ssa_name to 
> handle the situation >> until such time that it can be addressed. I 
> hope to get thru most >> of that in this stage 1 > > But if you do 
> on-demand ranges why do you need to change the SSA > name associated 
> ranges at all?
>
> It will still be of use for things which are learned.  VRP has 
> algorithms which iterate around loops and refine the known global 
> bounds of things like loop indexes and such that aren't immediately 
> obvious by simply looking at the static information in the IL.   Other 
> optimizations will likely do similar things and can help refine the 
> known global bounds,  This is then combined with whatever the static 
> ranges the ondemand system picks up form the IL to give better 
> contextual ranges.
>
> >> >>>> >>>> Im not familiar with the details of how wide_int and host 
> vs >>>> target integers really works. I don't think Aldy is either.  
> If >>>> there is a more efficient way to store an integer fr this use 
> >>>> case then by all means we can do that. to get things working we 
> >>>> just used what was easily available.   if there is a more >>>> 
> efficient way to represent it, perhaps it makes sense to create >>>> a 
> class for a"memory_efficient_wide_int" and allow it to >>>> convert 
> back and forth from a wide_int as needed? >>> >>> You want to talk to 
> Richard Sandiford mainly here I guess.  There >>> are many flavors of 
> wide ints, for different purposes. >> >> I did not know that :-)   
> Aldy, maybe you should have a chat :-) > > There's 
> trailing_wide_ints.  But having 6 of them is still > expensive. > > 
> Something nice would be to make wide_ints not tied to use > 
> HOST_WIDE_INT as basic element type but for example uint32.
>
> Yeah, wide_int always seemed kinda like overkill for some things... it 
> would be nice to have something simple and efficient.  we can also 
> drop to 2 ranges  instead of 3 initially too, if that helps.  and as I 
> mentioned, if necessary we can always implement the current irange 
> class using todays data structures if its really that big a deal.
>
> My original desire was to implement the range class as a chameleon 
> class which would use only what it needed from a pool of singe range, 
> double range, or whatever else was allowed by the current optimization 
> state.   That seemed like overkill to get the stuff up and running, 
> but would use only the actual amount of memory needed... and none if 
> there was no range info.  well, other than the pointer to the range 
> class for each ssa_name.
>
>
> So at the moment, the bottom line is we need to make the ranges more 
> efficient than they are currently.  Aldy has been focusing on getting 
> things working more so than efficiency of implementation, so that is 
> something he needs to focus on now...
>
> what would be the most efficient way to represent a range bound if it 
> isn't trailing_wide_int?  can we have some sort of class or typedef 
> that is set up at configuration time to would either be a basic 
> integral type or whatever else would work best?
>
>
> Andrew
>
Richard Biener May 24, 2017, 4:04 p.m. UTC | #16
On May 24, 2017 5:38:53 PM GMT+02:00, Andrew MacLeod <amacleod@redhat.com> wrote:
>On 05/24/2017 04:25 AM, Richard Biener wrote:
>> > What's this overflow flag for anyway?
>
>The new on-demand range calculators do operations on ranges, and that 
>flag is set when a range calculation may have overflowed... which is of
>
>use when issuing warnings or deciding to not use a range.
>ie given a made up example:
>
>signed char a,b;
>a_1 = b_3 +10;
>if (b_3 > 100)  foo (a_1)
>
>on the true side we know b_3 has the range [101,127].  It also 
>calculates the range of a_1 as [111, 127][-128,-119]  and sets the 
>overflow bit since the calculation of a_1 can overflow for some
>elements 
>of the range of b_3.    Anyone wanting to use the range can check the 
>overflow if its something they care about.  The overflow stuff has not 
>been completely flushed out yet, but it is in place for the moment.  we
>
>can decide down the road if it serves enough purpose to stick around,
>or 
>needs expansion, or whatever.
>> > > That said, I think it's the wrong approach to start mucking with 
>SSA > name associated ranges given they are supposed to be a cheap 
>storage > variant of what VRP computes.  Start by making the VRP 
>machinery work > from on-demand-ranges.  I do have some prototypes from
>
>last year or > the year before to do this -- the helpers VRP machinery 
>is already > generic enough if you make use of VRPs range type.
>
>well its also no longer just contained to VRP. This work is all driven 
>by the desire of other optimizations to access range information.  Some
>
>have hacked their required bits into vrp, making vrp a sort of  mini 
>optimization phase, others have attempted to leverage assert_exprs at 
>their point in time (not too successfully I think?) , others just live 
>with the lack of contextual range info after VRP... after looking at
>it, 
>i decided trying to teach other optimizations about assert_expr in
>order 
>to make their info available later was not something that seemed like a
>
>good long term solution.
>
>The most pressing matter was the desire for CFG sensitive range 
>information outside of VRP.  Since assert_exprs are gone after VRP, we 
>loose the information on the branches of a diamond without a lot of 
>hackery.  

That's what my prototype does.  I'll dig it out and will send it after public holidays tomorrow.  I do not believe in duplicating all the range operations we have in VRP.

Richard.

The on-demand system is positioned to leave VRP as is for the
>
>moment, and allow passes outside of VRP to pick up the range info VRP 
>generated and refine that range based on branches.   Once this is 
>working well, I'd have the confidence to then maybe go into VRP and try
>
>to replace the assert_exprs with the on demand system. This allows the 
>proving ground to be outside of VRP for just the passes which are 
>desperate for better ranges.   This allows the on-demand system to be 
>tested, utilized, and various efficiencies explored without impacting 
>any optimizations negatively by trying to replace VRP up front and not 
>getting everything it does or consuming too much compilation time or 
>memory..
>
>I'll shortly prepare the writeup for the on demand mechanism.. I'm
>still 
>getting it working :-P
>> > >>> >>>> More importantly, when the on-demand range work comes
>online 
>it >>>> will end the proliferation of SSA_NAMES which carry ASSERT_EXPR
>
> >>>> information.  We won't see the trail of new  ssa_names the >>>> 
>ASSET_EXPR chains create. I suspect that will eliminate storing >>>> 
>global ranges and bits for most SSA names, which is likely to >>>> make
>
>this class a win regardless. >>> >>> Are you sure it is desirable to 
>recompute it in all cases, rather >>> than just use what you have 
>recorded and recompute what you don't >>> have computed yet? E.g. 
>various ranges come from if (cond) >>> __builtin_unreachable (); style 
>asserts, we do want to drop them >>> at some point and the only spot to
>
>keep that info afterwards is >>> SSA_NAME range info. >> >> >> I think 
>it will be desirable in most cases.  The on-demand system >> does *not*
>
>use assert_exprs.   It will make them mostly obsolete, >> and the goal 
>is to eventually eliminate them from the IL >> completely. > > They are
>
>not in the IL.  They are only temporarily there during VRP > (not early
>
>VRP for example) to make VRP work as a SSA propagation > pass.
>
>right but a number of other optimization want the contextual
>information 
>assert_expr's provide.. outside of VRP.  so either we have to keep the 
>multitude of ssa_names that asset_exprs create in order to maintain the
>
>range info, either via copies or maintaining the assert_expr, or we do 
>something else.
>
>>> Most assert_exprs exist to provide ranges on sub-branches of the  >>
>CFG.  These we are likely to be able to simply replace with the >> 
>on-demand mechanism.  I suspect we'll find some cases where we find >> 
>its more useful to have a new global ssa_name which carries >> 
>information,  but I expect the situation which requires that to be >> 
>fairly rare. >> >> There will be a cycle where I have to identify cases
>
>we missing and >> catch those... or introduce a new ssa_name to handle 
>the situation >> until such time that it can be addressed. I hope to
>get 
>thru most >> of that in this stage 1 > > But if you do on-demand ranges
>
>why do you need to change the SSA > name associated ranges at all?
>
>It will still be of use for things which are learned.  VRP has 
>algorithms which iterate around loops and refine the known global
>bounds 
>of things like loop indexes and such that aren't immediately obvious by
>
>simply looking at the static information in the IL. Other optimizations
>
>will likely do similar things and can help refine the known global 
>bounds,  This is then combined with whatever the static ranges the 
>ondemand system picks up form the IL to give better contextual ranges.
>
>> > >>>> >>>> Im not familiar with the details of how wide_int and host
>
>vs >>>> target integers really works. I don't think Aldy is either.  If
>
>>>>> there is a more efficient way to store an integer fr this use >>>>
>
>case then by all means we can do that. to get things working we >>>> 
>just used what was easily available.   if there is a more >>>>
>efficient 
>way to represent it, perhaps it makes sense to create >>>> a class for 
>a"memory_efficient_wide_int" and allow it to >>>> convert back and
>forth 
>from a wide_int as needed? >>> >>> You want to talk to Richard
>Sandiford 
>mainly here I guess.  There >>> are many flavors of wide ints, for 
>different purposes. >> >> I did not know that :-)   Aldy, maybe you 
>should have a chat :-) > > There's trailing_wide_ints.  But having 6 of
>
>them is still > expensive. > > Something nice would be to make
>wide_ints 
>not tied to use > HOST_WIDE_INT as basic element type but for example 
>uint32.
>
>Yeah, wide_int always seemed kinda like overkill for some things... it 
>would be nice to have something simple and efficient.  we can also drop
>
>to 2 ranges  instead of 3 initially too, if that helps. and as I 
>mentioned, if necessary we can always implement the current irange
>class 
>using todays data structures if its really that big a deal.
>
>My original desire was to implement the range class as a chameleon
>class 
>which would use only what it needed from a pool of singe range, double 
>range, or whatever else was allowed by the current optimization state. 
> 
>That seemed like overkill to get the stuff up and running, but would
>use 
>only the actual amount of memory needed... and none if there was no 
>range info.  well, other than the pointer to the range class for each 
>ssa_name.
>
>
>So at the moment, the bottom line is we need to make the ranges more 
>efficient than they are currently.  Aldy has been focusing on getting 
>things working more so than efficiency of implementation, so that is 
>something he needs to focus on now...
>
>what would be the most efficient way to represent a range bound  if it 
>isn't trailing_wide_int?  can we have some sort of class or typedef
>that 
>is set up at configuration time to would either be a basic integral
>type 
>or whatever else would work best?
>
>
>Andrew
Mike Stump May 25, 2017, 3:05 p.m. UTC | #17
On May 24, 2017, at 1:25 AM, Richard Biener <richard.guenther@gmail.com> wrote:
> 
> There's trailing_wide_ints.  But having 6 of them is still expensive.
> 
> Something nice would be to make wide_ints not tied to use HOST_WIDE_INT
> as basic element type but for example uint32.

wide_int was made so that they would be calculation time efficient at the expense of a little space efficiency.  The underlying type is fairly arbitrary, and indeed, one could add it as a template parameter, and have all the existing code just use HWI for that parameter.  The new space saving version, could pass char, or short, or int, if they wanted to.  The only down side should be an extreme slowdown on operations.  It would be a lot of work to do this... but thought I would mention it.  Earlier on, we used int for testing to ensure that the code was solid, as when using a 64-bit chunk, most code never needs more than 1.  With a 32-bit type, the odds of more than 1 being used spike up considerably.
Richard Biener May 26, 2017, 8:57 a.m. UTC | #18
On Thu, May 25, 2017 at 5:05 PM, Mike Stump <mikestump@comcast.net> wrote:
> On May 24, 2017, at 1:25 AM, Richard Biener <richard.guenther@gmail.com> wrote:
>>
>> There's trailing_wide_ints.  But having 6 of them is still expensive.
>>
>> Something nice would be to make wide_ints not tied to use HOST_WIDE_INT
>> as basic element type but for example uint32.
>
> wide_int was made so that they would be calculation time efficient at the expense of a little space efficiency.  The underlying type is fairly arbitrary, and indeed, one could add it as a template parameter, and have all the existing code just use HWI for that parameter.  The new space saving version, could pass char, or short, or int, if they wanted to.  The only down side should be an extreme slowdown on operations.  It would be a lot of work to do this... but thought I would mention it.  Earlier on, we used int for testing to ensure that the code was solid, as when using a 64-bit chunk, most code never needs more than 1.  With a 32-bit type, the odds of more than 1 being used spike up considerably.
>

Yes.  I think my original argument was that with 64bits the code path
for >1 element get not very much coverage.

The most difficulties will be generalizing all those HWI using
interfaces in the API...

Richard.
Richard Biener May 26, 2017, 12:26 p.m. UTC | #19
On Wed, May 24, 2017 at 6:04 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On May 24, 2017 5:38:53 PM GMT+02:00, Andrew MacLeod <amacleod@redhat.com> wrote:
>>On 05/24/2017 04:25 AM, Richard Biener wrote:
>>> > What's this overflow flag for anyway?
>>
>>The new on-demand range calculators do operations on ranges, and that
>>flag is set when a range calculation may have overflowed... which is of
>>
>>use when issuing warnings or deciding to not use a range.
>>ie given a made up example:
>>
>>signed char a,b;
>>a_1 = b_3 +10;
>>if (b_3 > 100)  foo (a_1)
>>
>>on the true side we know b_3 has the range [101,127].  It also
>>calculates the range of a_1 as [111, 127][-128,-119]  and sets the
>>overflow bit since the calculation of a_1 can overflow for some
>>elements
>>of the range of b_3.    Anyone wanting to use the range can check the
>>overflow if its something they care about.  The overflow stuff has not
>>been completely flushed out yet, but it is in place for the moment.  we
>>
>>can decide down the road if it serves enough purpose to stick around,
>>or
>>needs expansion, or whatever.
>>> > > That said, I think it's the wrong approach to start mucking with
>>SSA > name associated ranges given they are supposed to be a cheap
>>storage > variant of what VRP computes.  Start by making the VRP
>>machinery work > from on-demand-ranges.  I do have some prototypes from
>>
>>last year or > the year before to do this -- the helpers VRP machinery
>>is already > generic enough if you make use of VRPs range type.
>>
>>well its also no longer just contained to VRP. This work is all driven
>>by the desire of other optimizations to access range information.  Some
>>
>>have hacked their required bits into vrp, making vrp a sort of  mini
>>optimization phase, others have attempted to leverage assert_exprs at
>>their point in time (not too successfully I think?) , others just live
>>with the lack of contextual range info after VRP... after looking at
>>it,
>>i decided trying to teach other optimizations about assert_expr in
>>order
>>to make their info available later was not something that seemed like a
>>
>>good long term solution.
>>
>>The most pressing matter was the desire for CFG sensitive range
>>information outside of VRP.  Since assert_exprs are gone after VRP, we
>>loose the information on the branches of a diamond without a lot of
>>hackery.
>
> That's what my prototype does.  I'll dig it out and will send it after public holidays tomorrow.  I do not believe in duplicating all the range operations we have in VRP.

Ok, so finally found that prototype to expose such API, see attached.

It of course no longer applies but its goal should be clear -- compute
a value range of a GENERIC expr (might be just an SSA name) in
given context (the prototype uses a loop *, but a BB would work here
as well).  It doesn't yet walk GIMPLE defs but only uses pre-recorded
SSA values, it has an "interesting" way to gather dominating conditions
and it lacks any caching.

IMHO any such interface should work like SCEV operates, thus maintain
a cache plus limiting stmt walks up to some dominator.

VRP now has a (nicely) factored way to generate "asserts" for conditionals
so you can register ranges for dominating asserts easily (and cache those).

Rather than recursing like in the prototype you'd (at least for the non-GENERIC
expr parts) compute a worklist of DEFs plus dominating conditions that are
interesting and then do regular forward iteration.

IMHO for any on-demant interface it's important that setup cost and cost
is bound by the size of the "expression" involved.

Richard.
Martin Jambor May 29, 2017, 5:48 p.m. UTC | #20
Hi,

On Wed, May 24, 2017 at 10:25:40AM +0200, Richard Biener wrote:
> Well, anti-ranges are "evil" for actual working with ranges.  They are nice
> for optimizing the storage requirements though.
> 
> As I'm replying late I'll add that yes, it does make a difference in memory
> use.  We've seen this with IPA VRP info eating up 1 GB extra memory
> for firefox so we optimized it to use trailing wide-ints.

Actually, the way we got most of that memory under control was to use
ggc_cache_remove hasher to store each unique value_range only once and
share it among all jump functions that referred to it.  See
ipa_vr_ggc_hash_traits and ipa_bit_ggc_hash_traits, it was
surprisingly easy to set up and helped a lot, just sharing the
non-NULL VR collapsed 706245 separate value_range structures into one.
Of course, one has to be careful not to change VR for all those
sharing it when intending to update it for just one of the parameters
it describes, but since you are devising an API, it can be taken care
of easily.

Hope this helps,

Martin
Aldy Hernandez May 31, 2017, 2:20 p.m. UTC | #21
On 05/23/2017 08:11 AM, Jakub Jelinek wrote:
> On Tue, May 23, 2017 at 06:48:15AM -0400, Aldy Hernandez wrote:

[ughh, one more time, but CCing the list.]

Sorry, for the delayed response.  I was fighting with Firefox + LTO to 
gather some data :).

> I'm worried a lot here about compile time memory usage increase, especially
> with EVRP and IPA-VRP and even more so with LTO.
> The changes mean that for every SSA_NAME of any kind we now need 8 more
> bytes, and for every SSA_NAME that has range info (typically both range info
> and nonzero_bits; in the old implementation the two were tied together for a
> good reason, many ranges also imply some non-zero bits and from non-zero
> bits one can in many cases derive a range) much more than that (through
> the nonzero_bits_def you get all the overhead of trailing_wide_ints -
> the 3 fields it has, just save on the actual 2 lengths and 2 HWI sets,
> but then you add 3x 8 bytes and 6x size of the whole wide_int which is
> from what I understood not really meant as the memory storage of wide ints
> in data structures, but as something not memory efficient you can work
> quickly on (so ideal for automatic variables in functions that work with
> those).  So it is a 8 byte growth for SSA_NAMEs without ranges and
> 8+3*8+6*32-2*4-2*8*x growth for SSA_NAMEs with ranges if x is the number
> of HWIs needed to represent the integers of that type (so most commonly
> x=1).  For x=1 8+3*8+6*32-2*4-2*8*x is 200 bytes growth.
> With say 10000000 SSA_NAMEs, 5000000 of them with ranges, that will be
> already a 1GB difference, dunno how many SSA_NAMEs are there e.g. in firefox
> LTO build.
> Can the nonzero_bits stuff be folded back into irange (and have code to
> maintain nonzero_bits in addition to ranges as before (from setting a range
> compute or update nonzero_bits and vice versa)?  Can you use
> trailing_wide_int for the irange storage of the values?  Can you allocate
> only as many HWIs as you really need, rather than always 6?
> Again, it can be different between a class you use for accessing the
> information and manipulating it and for actual underlying storage on
> SSA_NAMEs.

Before I fire off some stats, a few things.  Yes, we can do better. Yes, 
we can use trailing wide ints or another idiom.  Yes, we could join 
nonzero bits with the range info (if absolutely necessary, because as 
I'll show below, the extra word doesn't blow up memory as much as 
advertised).

Thanks to Martin Liska and Markus I was able to build a three-month old 
firefox branch with GCC7 LTO.  I built firefox with -O2 -flto=9, and 
then looked at the biggest partition at the end of VRP1 (that is, 
warn_array_bound_p == true).

The short version is that I don't see anywhere close to 10 million 
SSA_NAMEs.  Of the SSA_NAMEs we do get, 25% are pointers and irrelevant. 
   22% of the non-pointer SSA_NAMEs actually have range information, and 
of this range info 32% is actually useless because it spans the entire 
domain.  So, unless I'm misunderstanding something, even in the worst 
case scenario (in firefox + LTO anyways), I don't see such a big blow up 
of memory.

Now on to the actual numbers.  Remember, this is only for one of the 
partitions during the ltrans stage of LTO, running VRP1, since this 
seems to be the granular level of a compilation process.  If you're 
trying to compile 20 partitions at the same time, get more memory :).

The biggest number of SSA_NAMEs I saw was actually 472,225.  Of these, 
357,032 were non-pointers, so could conceivably have range information. 
In reality, 77,398 had range information, so 16% of all pointer and 
non-pointer SSA_NAMEs actually have range information.

Now here's the interesting bit... in analyzing those 77,398 ranges, I 
noticed that a great many of them were useless.  They consisted of the 
range for the entire domain even with no NON_ZERO_BITS set.  The new 
implementation will obviously not have this limitation :-).  Taking this 
into account, I see a total of 52,718 non-useless ranges out of 472,225. 
  That's about 11%.

In the compilation of this large partition, G.stats.total_allocated is 
2,192,677,688, so about 2 gigs of memory.  Of which the total 
non-useless range info is 1,686,976 for vanilla GCC7.  This looks like 
less than 2 megs. I calculated the range info memory consumption with 
(sizeof (range_info_def) + trailing_wide_ints <3>::extra_size (precision)).

Assuming a pathological case of 200 extra bytes in each of the 52,718 
non-useless ranges, we'd have 10 megabytes of extra data.  And that's in 
a compilation that already consumes 2 gigs of memory.  Isn't that like 
less than half of a percent?  We could even account for that extra 
pointer in SSA_NAME and add less than 4 megs to that number (472,225 * 8 
bytes).

Again, do not take this as an excuse for the careless memory layout of 
my patch (after all, it was meant as a proof of concept).  I will 
re-arrange things and optimize things a bit.  However, I also don't 
think that adding a word or two here is going to make a difference, 
since even at the pathological case, we're only increasing memory by 
less than a percent.

This begs the question, is firefox with LTO representative of a large 
enough sample?  Am I wrong in analyzing SSA_NAME usage at the end of 
VRP1?  Are there programs out there with 10 million SSA_NAMEs, for which 
a larger range info would be a non-trivial increase of the compilation 
process's memory?

I will post a less horrible version, but in the meantime I wanted to 
show some numbers.

Thanks to everyone for their input.
Aldy

p.s. I did measure the number of entries in the internal VR_VALUE table 
for the above case.  It had 103,577 non-empty entries.  Again, this 
doesn't look like a significant increase in memory, even for this 
internal VRP representation.
Jakub Jelinek May 31, 2017, 3:10 p.m. UTC | #22
On Wed, May 31, 2017 at 10:20:51AM -0400, Aldy Hernandez wrote:
> The biggest number of SSA_NAMEs I saw was actually 472,225.  Of these,
> 357,032 were non-pointers, so could conceivably have range information. In
> reality, 77,398 had range information, so 16% of all pointer and non-pointer
> SSA_NAMEs actually have range information.

I've tried to look just at insn-recog.c with the usual stage3 flags +
-fsanitize=address,undefined and I see there
ssa_name_nodes_created
4092344
(of course, that doesn't mean there are 4M SSA_NAMEs all live at the same
time, but I think they don't go through ggc_free and thus the only way that
number goes down is during GC.  There are both 72 and 80 bytes alloc pools,
even a 32MB increase is something we shouldn't ignore.
Furthermore, as e.g. PR80917 shows, we really should track nonzero bits next
to value ranges, the current tracking of it only in tree-ssa-ccp which
doesn't have ASSERT_EXPRs nor any kind of framework to do something similar
without them is insufficient.

	Jakub
Richard Biener May 31, 2017, 3:36 p.m. UTC | #23
On May 31, 2017 5:10:04 PM GMT+02:00, Jakub Jelinek <jakub@redhat.com> wrote:
>On Wed, May 31, 2017 at 10:20:51AM -0400, Aldy Hernandez wrote:
>> The biggest number of SSA_NAMEs I saw was actually 472,225.  Of
>these,
>> 357,032 were non-pointers, so could conceivably have range
>information. In
>> reality, 77,398 had range information, so 16% of all pointer and
>non-pointer
>> SSA_NAMEs actually have range information.
>
>I've tried to look just at insn-recog.c with the usual stage3 flags +
>-fsanitize=address,undefined and I see there
>ssa_name_nodes_created
>4092344
>(of course, that doesn't mean there are 4M SSA_NAMEs all live at the
>same
>time, but I think they don't go through ggc_free and thus the only way
>that
>number goes down is during GC.  There are both 72 and 80 bytes alloc
>pools,
>even a 32MB increase is something we shouldn't ignore.
>Furthermore, as e.g. PR80917 shows, we really should track nonzero bits
>next
>to value ranges, the current tracking of it only in tree-ssa-ccp which
>doesn't have ASSERT_EXPRs nor any kind of framework to do something
>similar
>without them is insufficient.

I think the important part to recognize is that the VR type used during propagation does (and likely should) not have to be the same as that used for long-term storage alongside SSA names.

The first thing to do is improve the one we use internally in VRP where we can also add a separate bit-lattice easily (though we have to iterate until both converge).

Richard.

>	Jakub
Jakub Jelinek May 31, 2017, 4:28 p.m. UTC | #24
On Wed, May 31, 2017 at 05:36:12PM +0200, Richard Biener wrote:
> On May 31, 2017 5:10:04 PM GMT+02:00, Jakub Jelinek <jakub@redhat.com> wrote:
> >On Wed, May 31, 2017 at 10:20:51AM -0400, Aldy Hernandez wrote:
> >> The biggest number of SSA_NAMEs I saw was actually 472,225.  Of
> >these,
> >> 357,032 were non-pointers, so could conceivably have range
> >information. In
> >> reality, 77,398 had range information, so 16% of all pointer and
> >non-pointer
> >> SSA_NAMEs actually have range information.
> >
> >I've tried to look just at insn-recog.c with the usual stage3 flags +
> >-fsanitize=address,undefined and I see there
> >ssa_name_nodes_created
> >4092344
> >(of course, that doesn't mean there are 4M SSA_NAMEs all live at the
> >same
> >time, but I think they don't go through ggc_free and thus the only way
> >that
> >number goes down is during GC.  There are both 72 and 80 bytes alloc
> >pools,
> >even a 32MB increase is something we shouldn't ignore.
> >Furthermore, as e.g. PR80917 shows, we really should track nonzero bits
> >next
> >to value ranges, the current tracking of it only in tree-ssa-ccp which
> >doesn't have ASSERT_EXPRs nor any kind of framework to do something
> >similar
> >without them is insufficient.
> 
> I think the important part to recognize is that the VR type used during
> propagation does (and likely should) not have to be the same as that used
> for long-term storage alongside SSA names.
> 
> The first thing to do is improve the one we use internally in VRP where we
> can also add a separate bit-lattice easily (though we have to iterate
> until both converge).

I believe Andrew/Aldy's goal is to make the "during VRP propagation" vs.
in other passes line fuzzier, but I agree it would be best to do it
like wide_int can - have a template that can work on different range/nz bits
storages, and have a compact storage for the on SSA_NAME data and
less compact one for other purposes.

	Jakub
Richard Biener May 31, 2017, 4:46 p.m. UTC | #25
On May 31, 2017 6:28:26 PM GMT+02:00, Jakub Jelinek <jakub@redhat.com> wrote:
>On Wed, May 31, 2017 at 05:36:12PM +0200, Richard Biener wrote:
>> On May 31, 2017 5:10:04 PM GMT+02:00, Jakub Jelinek
><jakub@redhat.com> wrote:
>> >On Wed, May 31, 2017 at 10:20:51AM -0400, Aldy Hernandez wrote:
>> >> The biggest number of SSA_NAMEs I saw was actually 472,225.  Of
>> >these,
>> >> 357,032 were non-pointers, so could conceivably have range
>> >information. In
>> >> reality, 77,398 had range information, so 16% of all pointer and
>> >non-pointer
>> >> SSA_NAMEs actually have range information.
>> >
>> >I've tried to look just at insn-recog.c with the usual stage3 flags
>+
>> >-fsanitize=address,undefined and I see there
>> >ssa_name_nodes_created
>> >4092344
>> >(of course, that doesn't mean there are 4M SSA_NAMEs all live at the
>> >same
>> >time, but I think they don't go through ggc_free and thus the only
>way
>> >that
>> >number goes down is during GC.  There are both 72 and 80 bytes alloc
>> >pools,
>> >even a 32MB increase is something we shouldn't ignore.
>> >Furthermore, as e.g. PR80917 shows, we really should track nonzero
>bits
>> >next
>> >to value ranges, the current tracking of it only in tree-ssa-ccp
>which
>> >doesn't have ASSERT_EXPRs nor any kind of framework to do something
>> >similar
>> >without them is insufficient.
>> 
>> I think the important part to recognize is that the VR type used
>during
>> propagation does (and likely should) not have to be the same as that
>used
>> for long-term storage alongside SSA names.
>> 
>> The first thing to do is improve the one we use internally in VRP
>where we
>> can also add a separate bit-lattice easily (though we have to iterate
>> until both converge).
>
>I believe Andrew/Aldy's goal is to make the "during VRP propagation"
>vs.
>in other passes line fuzzier

I realize that.  But for caching purposes they do have to keep a sparse lattice anyway which can use a more precise info (and also expose that through another API than the persistent one).
It's hopefully going to be much like SCEV.

I've not yet seen any code of course (not that I have high hopes...)

Richard.


, but I agree it would be best to do it
>like wide_int can - have a template that can work on different range/nz
>bits
>storages, and have a compact storage for the on SSA_NAME data and
>less compact one for other purposes.
>
>	Jakub
Jeff Law June 7, 2017, 2:43 a.m. UTC | #26
On 05/23/2017 05:28 AM, Nathan Sidwell wrote:
> On 05/23/2017 06:48 AM, Aldy Hernandez wrote:
> 
>> The class can live outside of his work, as can be demonstrated by the
>> attached patch.  With it, I was able to rewrite the post-VRP range
>> information to use this class and get rid of VR_ANTI_RANGE throughout
>> the compiler.  A VR_ANTI_RANGE of ~[5,10] becomes [-MIN,4][11,+MAX].
> 
> Seems useful.
That's the idea :-)

The general consensus is that ANTI ranges are just painful to support
and they can be represented as two distinct sub-intervals -- and we know
how to operate on those subintervals reasonably well.

I haven't looked at the this version of the patch, but earlier versions
did show how dropping anti range support and instead using the new
representation cleaned things up considerably.

In reality I suspect the only really important anti range is ~[0,0]
anyway.  Everything else is likely small potatoes.


> 
>> +  /* Remove negative numbers from the range.  */
>> +  irange positives;
>> +  range_positives (&positives, exptype, allow_zero ? 0 : 1);
> 
> 'allow_zero ? 0 : 1' looks mighty strange. I know that's a nit, but you
> placed it front and centre!
> 
>> +  if (positives.Intersect (*ir))
> 
> I notice you have a number of Uppercase member fns ...
Aldy, this ought to get fixed :-)

jeff
Jeff Law June 7, 2017, 2:44 a.m. UTC | #27
On 05/23/2017 08:34 AM, Jakub Jelinek wrote:
> On Tue, May 23, 2017 at 10:29:58AM -0400, David Malcolm wrote:
>>> Do we really want methods starting with capital letters?
>>> I understand why you can't use union, but I don't think we use
>>> CamelCase
>>> anywhere.
>>
>> FWIW in the JIT, I have a class switch_ (i.e. with a trailing
>> underscore).  Maybe we should use trailing underscores for names that
>> clash with reserved words?
> 
> union_ and not_ is just fine with me.
Likewise.  No strong opinions here.

jeff
Aldy Hernandez June 20, 2017, 8:41 a.m. UTC | #28
On 05/23/2017 03:26 PM, Martin Sebor wrote:
> On 05/23/2017 04:48 AM, Aldy Hernandez wrote:

> +  void Union (wide_int x, wide_int y);
> +  bool Union (const irange &r);
> +  bool Union (const irange &r1, const irange &r2);
> +
> +  // THIS = THIS ^ [X,Y].  Return TRUE if result is non-empty.
> +  bool Intersect (wide_int x, wide_int y, bool readonly = false);
> +  // THIS = THIS ^ R.  Return TRUE if result is non-empty.
> +  // THIS = R1 ^ R2.  Return TRUE if result is non-empty.
> +  bool Intersect (const irange &r1, const irange &r2, bool readonly = 
> false);
> +  // Return TRUE if THIS ^ R will be non-empty.
> +  bool Intersect_p (const irange &r)
> +    { return Intersect (r, /*readonly=*/true); }
> 
> I would suggest the following changes to Union, Intersect, and Not:
> 
> 1) Define all three members without the readonly argument and
>     returning irange& (i.e., *this).  The return value can be
>     used wherever irange& is expected, and the is_empty() member
>     function can be called on it to obtain the same result.  E.g.,
>     Intersect A with B, storing the result in A:
> 
>     irange A, B;
>     if (A.Intersect (B).is_empty ()) { ... }
> 
> 2) Add non-members like so:
> 
>    irange range_union (const irange &lhs, const irange &rhs)
>    {
>      return irange (lhs).Union (rhs);
>    }
> 
>    and find out if the union of A or B is empty without modifying
>    either argument:
> 
>    irange A, B;
>    if (range_union (A, B).is_empty ()) { ... }

Perhaps we could provide an implicit conversion from irange to bool such 
that we could write:

if (range_union (A, B)) { ... }

as well as being able to write:

if (!range_union (A, B).is_empty ()) { ... }

That is, have range_union() return an irange as suggested, but have a 
bool overload (or whatever the C++ nomenclature is) such that converting 
an irange to a bool is interpreted as ``nitems != 0''.

Is this acceptable C++ practice?

Thanks.
Aldy
Martin Sebor June 20, 2017, 2:59 p.m. UTC | #29
On 06/20/2017 02:41 AM, Aldy Hernandez wrote:
>
>
> On 05/23/2017 03:26 PM, Martin Sebor wrote:
>> On 05/23/2017 04:48 AM, Aldy Hernandez wrote:
>
>> +  void Union (wide_int x, wide_int y);
>> +  bool Union (const irange &r);
>> +  bool Union (const irange &r1, const irange &r2);
>> +
>> +  // THIS = THIS ^ [X,Y].  Return TRUE if result is non-empty.
>> +  bool Intersect (wide_int x, wide_int y, bool readonly = false);
>> +  // THIS = THIS ^ R.  Return TRUE if result is non-empty.
>> +  // THIS = R1 ^ R2.  Return TRUE if result is non-empty.
>> +  bool Intersect (const irange &r1, const irange &r2, bool readonly =
>> false);
>> +  // Return TRUE if THIS ^ R will be non-empty.
>> +  bool Intersect_p (const irange &r)
>> +    { return Intersect (r, /*readonly=*/true); }
>>
>> I would suggest the following changes to Union, Intersect, and Not:
>>
>> 1) Define all three members without the readonly argument and
>>     returning irange& (i.e., *this).  The return value can be
>>     used wherever irange& is expected, and the is_empty() member
>>     function can be called on it to obtain the same result.  E.g.,
>>     Intersect A with B, storing the result in A:
>>
>>     irange A, B;
>>     if (A.Intersect (B).is_empty ()) { ... }
>>
>> 2) Add non-members like so:
>>
>>    irange range_union (const irange &lhs, const irange &rhs)
>>    {
>>      return irange (lhs).Union (rhs);
>>    }
>>
>>    and find out if the union of A or B is empty without modifying
>>    either argument:
>>
>>    irange A, B;
>>    if (range_union (A, B).is_empty ()) { ... }
>
> Perhaps we could provide an implicit conversion from irange to bool such
> that we could write:
>
> if (range_union (A, B)) { ... }
>
> as well as being able to write:
>
> if (!range_union (A, B).is_empty ()) { ... }
>
> That is, have range_union() return an irange as suggested, but have a
> bool overload (or whatever the C++ nomenclature is) such that converting
> an irange to a bool is interpreted as ``nitems != 0''.
>
> Is this acceptable C++ practice?

Implicit conversion to bool is a common way of testing validity
but I don't think it would be too surprising to use it as a test
for non-emptiness.  An alternative to consider is to provide
an implicit conversion to an unsigned integer (instead of
num_ranges()(*)) and have it return the number of ranges.  That
will make it possible to do the same thing as above while also
simplifying the API.

Martin

[*] FWIW, there's nothing wrong with the name num_ranges() but
those familiar with the C++ standard library are going to be
accustomed to size() as the name of a function that returns
the number of elements in a container.  Since the irange class
is an ordered sequence of ranges, size() would work for it too.

PS Thinking of the irange class as a container of ranges suggests
the design might benefit from introducing a simple lower-level
abstraction (class) for a single contiguous range.
Aldy Hernandez June 21, 2017, 6:20 a.m. UTC | #30
On 06/20/2017 10:59 AM, Martin Sebor wrote:
> On 06/20/2017 02:41 AM, Aldy Hernandez wrote:
>>
>>
>> On 05/23/2017 03:26 PM, Martin Sebor wrote:
>>> On 05/23/2017 04:48 AM, Aldy Hernandez wrote:
>>
>>> +  void Union (wide_int x, wide_int y);
>>> +  bool Union (const irange &r);
>>> +  bool Union (const irange &r1, const irange &r2);
>>> +
>>> +  // THIS = THIS ^ [X,Y].  Return TRUE if result is non-empty.
>>> +  bool Intersect (wide_int x, wide_int y, bool readonly = false);
>>> +  // THIS = THIS ^ R.  Return TRUE if result is non-empty.
>>> +  // THIS = R1 ^ R2.  Return TRUE if result is non-empty.
>>> +  bool Intersect (const irange &r1, const irange &r2, bool readonly =
>>> false);
>>> +  // Return TRUE if THIS ^ R will be non-empty.
>>> +  bool Intersect_p (const irange &r)
>>> +    { return Intersect (r, /*readonly=*/true); }
>>>
>>> I would suggest the following changes to Union, Intersect, and Not:
>>>
>>> 1) Define all three members without the readonly argument and
>>>     returning irange& (i.e., *this).  The return value can be
>>>     used wherever irange& is expected, and the is_empty() member
>>>     function can be called on it to obtain the same result.  E.g.,
>>>     Intersect A with B, storing the result in A:
>>>
>>>     irange A, B;
>>>     if (A.Intersect (B).is_empty ()) { ... }
>>>
>>> 2) Add non-members like so:
>>>
>>>    irange range_union (const irange &lhs, const irange &rhs)
>>>    {
>>>      return irange (lhs).Union (rhs);
>>>    }
>>>
>>>    and find out if the union of A or B is empty without modifying
>>>    either argument:
>>>
>>>    irange A, B;
>>>    if (range_union (A, B).is_empty ()) { ... }
>>
>> Perhaps we could provide an implicit conversion from irange to bool such
>> that we could write:
>>
>> if (range_union (A, B)) { ... }
>>
>> as well as being able to write:
>>
>> if (!range_union (A, B).is_empty ()) { ... }
>>
>> That is, have range_union() return an irange as suggested, but have a
>> bool overload (or whatever the C++ nomenclature is) such that converting
>> an irange to a bool is interpreted as ``nitems != 0''.
>>
>> Is this acceptable C++ practice?
> 
> Implicit conversion to bool is a common way of testing validity
> but I don't think it would be too surprising to use it as a test
> for non-emptiness.  An alternative to consider is to provide
> an implicit conversion to an unsigned integer (instead of
> num_ranges()(*)) and have it return the number of ranges.  That
> will make it possible to do the same thing as above while also
> simplifying the API.

I really like this.

I have added an implicit conversion to unsigned that returns the number 
of sub-ranges.  However, I have also left the empty_p() method for a 
cleaner interface within the class itself.  It feels wrong to type "if 
(!*this)" to represent emptiness within the class.

> 
> Martin
> 
> [*] FWIW, there's nothing wrong with the name num_ranges() but
> those familiar with the C++ standard library are going to be
> accustomed to size() as the name of a function that returns
> the number of elements in a container.  Since the irange class
> is an ordered sequence of ranges, size() would work for it too.

In my upcoming patch I have renamed num_ranges() to num_pairs() which I 
thought was clearer, but if you still feel strongly about this, I can 
rename to size().

> 
> PS Thinking of the irange class as a container of ranges suggests
> the design might benefit from introducing a simple lower-level
> abstraction (class) for a single contiguous range.

Hmmm, indeed.  Perhaps when the dust settles with the patch I'm about to 
post :).

Thanks for your suggestions.
Aldy
Richard Sandiford June 22, 2017, 12:16 p.m. UTC | #31
Aldy Hernandez <aldyh@redhat.com> writes:
> On 06/20/2017 10:59 AM, Martin Sebor wrote:
>> On 06/20/2017 02:41 AM, Aldy Hernandez wrote:
>>> On 05/23/2017 03:26 PM, Martin Sebor wrote:
>>>> On 05/23/2017 04:48 AM, Aldy Hernandez wrote:
>>>
>>>> +  void Union (wide_int x, wide_int y);
>>>> +  bool Union (const irange &r);
>>>> +  bool Union (const irange &r1, const irange &r2);
>>>> +
>>>> +  // THIS = THIS ^ [X,Y].  Return TRUE if result is non-empty.
>>>> +  bool Intersect (wide_int x, wide_int y, bool readonly = false);
>>>> +  // THIS = THIS ^ R.  Return TRUE if result is non-empty.
>>>> +  // THIS = R1 ^ R2.  Return TRUE if result is non-empty.
>>>> +  bool Intersect (const irange &r1, const irange &r2, bool readonly =
>>>> false);
>>>> +  // Return TRUE if THIS ^ R will be non-empty.
>>>> +  bool Intersect_p (const irange &r)
>>>> +    { return Intersect (r, /*readonly=*/true); }
>>>>
>>>> I would suggest the following changes to Union, Intersect, and Not:
>>>>
>>>> 1) Define all three members without the readonly argument and
>>>>     returning irange& (i.e., *this).  The return value can be
>>>>     used wherever irange& is expected, and the is_empty() member
>>>>     function can be called on it to obtain the same result.  E.g.,
>>>>     Intersect A with B, storing the result in A:
>>>>
>>>>     irange A, B;
>>>>     if (A.Intersect (B).is_empty ()) { ... }
>>>>
>>>> 2) Add non-members like so:
>>>>
>>>>    irange range_union (const irange &lhs, const irange &rhs)
>>>>    {
>>>>      return irange (lhs).Union (rhs);
>>>>    }
>>>>
>>>>    and find out if the union of A or B is empty without modifying
>>>>    either argument:
>>>>
>>>>    irange A, B;
>>>>    if (range_union (A, B).is_empty ()) { ... }
>>>
>>> Perhaps we could provide an implicit conversion from irange to bool such
>>> that we could write:
>>>
>>> if (range_union (A, B)) { ... }
>>>
>>> as well as being able to write:
>>>
>>> if (!range_union (A, B).is_empty ()) { ... }
>>>
>>> That is, have range_union() return an irange as suggested, but have a
>>> bool overload (or whatever the C++ nomenclature is) such that converting
>>> an irange to a bool is interpreted as ``nitems != 0''.
>>>
>>> Is this acceptable C++ practice?
>> 
>> Implicit conversion to bool is a common way of testing validity
>> but I don't think it would be too surprising to use it as a test
>> for non-emptiness.  An alternative to consider is to provide
>> an implicit conversion to an unsigned integer (instead of
>> num_ranges()(*)) and have it return the number of ranges.  That
>> will make it possible to do the same thing as above while also
>> simplifying the API.
>
> I really like this.
>
> I have added an implicit conversion to unsigned that returns the number 
> of sub-ranges.  However, I have also left the empty_p() method for a 
> cleaner interface within the class itself.  It feels wrong to type "if 
> (!*this)" to represent emptiness within the class.

Conversions to bool and conversions to int both seem dangerous.
E.g. people might try "range1 | range2" as a shorthand for taking the
union of the ranges.  It'll compile but instead give the bitwise OR
of the two range counts.

How about instead having helper functions like intersect_p,
as for bitmaps?

Thanks,
Richard
Martin Sebor June 22, 2017, 4:54 p.m. UTC | #32
On 06/22/2017 06:16 AM, Richard Sandiford wrote:
> Aldy Hernandez <aldyh@redhat.com> writes:
>> On 06/20/2017 10:59 AM, Martin Sebor wrote:
>>> On 06/20/2017 02:41 AM, Aldy Hernandez wrote:
>>>> On 05/23/2017 03:26 PM, Martin Sebor wrote:
>>>>> On 05/23/2017 04:48 AM, Aldy Hernandez wrote:
>>>>
>>>>> +  void Union (wide_int x, wide_int y);
>>>>> +  bool Union (const irange &r);
>>>>> +  bool Union (const irange &r1, const irange &r2);
>>>>> +
>>>>> +  // THIS = THIS ^ [X,Y].  Return TRUE if result is non-empty.
>>>>> +  bool Intersect (wide_int x, wide_int y, bool readonly = false);
>>>>> +  // THIS = THIS ^ R.  Return TRUE if result is non-empty.
>>>>> +  // THIS = R1 ^ R2.  Return TRUE if result is non-empty.
>>>>> +  bool Intersect (const irange &r1, const irange &r2, bool readonly =
>>>>> false);
>>>>> +  // Return TRUE if THIS ^ R will be non-empty.
>>>>> +  bool Intersect_p (const irange &r)
>>>>> +    { return Intersect (r, /*readonly=*/true); }
>>>>>
>>>>> I would suggest the following changes to Union, Intersect, and Not:
>>>>>
>>>>> 1) Define all three members without the readonly argument and
>>>>>     returning irange& (i.e., *this).  The return value can be
>>>>>     used wherever irange& is expected, and the is_empty() member
>>>>>     function can be called on it to obtain the same result.  E.g.,
>>>>>     Intersect A with B, storing the result in A:
>>>>>
>>>>>     irange A, B;
>>>>>     if (A.Intersect (B).is_empty ()) { ... }
>>>>>
>>>>> 2) Add non-members like so:
>>>>>
>>>>>    irange range_union (const irange &lhs, const irange &rhs)
>>>>>    {
>>>>>      return irange (lhs).Union (rhs);
>>>>>    }
>>>>>
>>>>>    and find out if the union of A or B is empty without modifying
>>>>>    either argument:
>>>>>
>>>>>    irange A, B;
>>>>>    if (range_union (A, B).is_empty ()) { ... }
>>>>
>>>> Perhaps we could provide an implicit conversion from irange to bool such
>>>> that we could write:
>>>>
>>>> if (range_union (A, B)) { ... }
>>>>
>>>> as well as being able to write:
>>>>
>>>> if (!range_union (A, B).is_empty ()) { ... }
>>>>
>>>> That is, have range_union() return an irange as suggested, but have a
>>>> bool overload (or whatever the C++ nomenclature is) such that converting
>>>> an irange to a bool is interpreted as ``nitems != 0''.
>>>>
>>>> Is this acceptable C++ practice?
>>>
>>> Implicit conversion to bool is a common way of testing validity
>>> but I don't think it would be too surprising to use it as a test
>>> for non-emptiness.  An alternative to consider is to provide
>>> an implicit conversion to an unsigned integer (instead of
>>> num_ranges()(*)) and have it return the number of ranges.  That
>>> will make it possible to do the same thing as above while also
>>> simplifying the API.
>>
>> I really like this.
>>
>> I have added an implicit conversion to unsigned that returns the number
>> of sub-ranges.  However, I have also left the empty_p() method for a
>> cleaner interface within the class itself.  It feels wrong to type "if
>> (!*this)" to represent emptiness within the class.
>
> Conversions to bool and conversions to int both seem dangerous.
> E.g. people might try "range1 | range2" as a shorthand for taking the
> union of the ranges.  It'll compile but instead give the bitwise OR
> of the two range counts.

Yes, that's a valid point and the reason why conversion to "bool"
as a test for validity is sometimes implemented as a conversion
to some unique pointer type, e.g.,

   struct UniquePointerType;
   operator UniquePointerType* () const;

To avoid the same problem with an implicit conversion to integer
the bitwise operator overloads (and any others of concern) could
either be deleted from the overload set, e.g., using some sort
of an enable_if trick (or declared as private members), or defined
with the expected meaning (that could also obviate the problem with
the capitalization of Union() if the operators were the only way
to achieve that).

But I don't have a strong preference for any of these approaches.

Martin

>
> How about instead having helper functions like intersect_p,
> as for bitmaps?
>
> Thanks,
> Richard
>

Patch
diff mbox

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 8ace3c2..5e48d6e 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1416,6 +1416,7 @@  OBJS = \
 	print-rtl-function.o \
 	print-tree.o \
 	profile.o \
+	range.o \
 	read-md.o \
 	read-rtl.o \
 	read-rtl-function.o \
@@ -2484,6 +2485,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 \
diff --git a/gcc/builtins.c b/gcc/builtins.c
index 4f6c9c4..328f028 100644
--- a/gcc/builtins.c
+++ b/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"
@@ -2894,6 +2895,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_ranges () != 2
+      || ir.lower_bound () != 0)
+    return false;
+
+  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
@@ -2913,7 +2960,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))))
@@ -2926,34 +2972,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)
+	  if (range_may_have_wrapped (*SSA_NAME_RANGE_INFO (len),
+				      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 <=
@@ -3136,7 +3166,7 @@  check_sizes (int opt, tree exp, tree size, tree maxlen, tree src, tree objsize)
   bool exactsize = size && tree_fits_uhwi_p (size);
 
   if (size)
-    get_size_range (size, range);
+    get_size_range (size, range, /*allow_zero=*/true);
 
   /* First check the number of bytes to be written against the maximum
      object size.  */
diff --git a/gcc/calls.c b/gcc/calls.c
index 91a4466..3070878 100644
--- a/gcc/calls.c
+++ b/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"
@@ -1256,10 +1257,12 @@  alloc_max_size (void)
    after adjusting it if necessary to make EXP a valid size argument to
    an allocation function declared with attribute alloc_size (whose
    argument may be signed), or to a string manipulation function like
-   memset.  */
+   memset.
+
+   INCLUDE_ZERO is TRUE if 0 should be included in a valid range.  */
 
 bool
-get_size_range (tree exp, tree range[2])
+get_size_range (tree exp, tree range[2], bool allow_zero)
 {
   if (tree_fits_uhwi_p (exp))
     {
@@ -1269,11 +1272,10 @@  get_size_range (tree exp, tree range[2])
     }
 
   wide_int min, max;
-  enum value_range_type range_type
+  irange *ir
     = ((TREE_CODE (exp) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (exp)))
-       ? get_range_info (exp, &min, &max) : VR_VARYING);
-
-  if (range_type == VR_VARYING)
+       ? get_range_info (exp, &min, &max) : NULL);
+  if (!ir)
     {
       /* No range information available.  */
       range[0] = NULL_TREE;
@@ -1282,61 +1284,29 @@  get_size_range (tree exp, tree range[2])
     }
 
   tree exptype = TREE_TYPE (exp);
-  unsigned expprec = TYPE_PRECISION (exptype);
-  wide_int wzero = wi::zero (expprec);
-  wide_int wmaxval = wide_int (TYPE_MAX_VALUE (exptype));
-
-  bool signed_p = !TYPE_UNSIGNED (exptype);
 
-  if (range_type == VR_ANTI_RANGE)
+  /* Remove negative numbers from the range.  */
+  irange positives;
+  range_positives (&positives, exptype, allow_zero ? 0 : 1);
+  if (positives.Intersect (*ir))
     {
-      if (signed_p)
-	{
-	  if (wi::les_p (max, wzero))
-	    {
-	      /* 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 = wzero;
-	      max = wmaxval;
-	    }
-	  else if (wi::les_p (min - 1, wzero))
-	    {
-	      /* 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 = wmaxval;
-	    }
-	  else
-	    {
-	      max = min - 1;
-	      min = wzero;
-	    }
-	}
-      else if (wi::eq_p (wzero, 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 set the range to
-	     [MAX, TYPE_MAX] so that when MAX is greater than the limit
-	     the whole range is diagnosed.  */
-	  min = max + 1;
-	  max = wmaxval;
-	}
-      else
-	{
-	  max = min - 1;
-	  min = wzero;
-	}
+      /* Remove the unknown parts of a multi-range.
+	 This will transform [5,10][20,MAX] into [5,10].  */
+      if (positives.num_ranges () > 1
+	  && positives.upper_bound () == wide_int (TYPE_MAX_VALUE (exptype)))
+	positives.remove_range (positives.num_ranges () - 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;
 }
 
diff --git a/gcc/calls.h b/gcc/calls.h
index df5817f..85ad78c 100644
--- a/gcc/calls.h
+++ b/gcc/calls.h
@@ -38,6 +38,6 @@  extern bool pass_by_reference (CUMULATIVE_ARGS *, machine_mode,
 extern bool reference_callee_copied (CUMULATIVE_ARGS *, machine_mode,
 				     tree, bool);
 extern void maybe_warn_alloc_args_overflow (tree, tree, tree[2], int[2]);
-extern bool get_size_range (tree, tree[2]);
+extern bool get_size_range (tree, tree[2], bool include_zero = false);
 
 #endif // GCC_CALLS_H
diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index 736552c..0c48018 100644
--- a/gcc/fold-const.c
+++ b/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"
@@ -9063,7 +9064,7 @@  bool
 expr_not_equal_to (tree t, const wide_int &w)
 {
   wide_int min, max, nz;
-  value_range_type rtype;
+  irange *ri;
   switch (TREE_CODE (t))
     {
     case INTEGER_CST:
@@ -9072,17 +9073,8 @@  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 (wi::lt_p (max, w, TYPE_SIGN (TREE_TYPE (t))))
-	    return true;
-	  if (wi::lt_p (w, min, TYPE_SIGN (TREE_TYPE (t))))
-	    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))))
+      ri = SSA_NAME_RANGE_INFO (t);
+      if (ri && !ri->contains_p (w))
 	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.  */
diff --git a/gcc/function-tests.c b/gcc/function-tests.c
index ca30028..f1f884d 100644
--- a/gcc/function-tests.c
+++ b/gcc/function-tests.c
@@ -574,6 +574,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
@@ -677,6 +690,7 @@  function_tests_c_tests ()
   test_gimplification ();
   test_building_cfg ();
   test_conversion_to_ssa ();
+  test_iranges ();
   test_expansion_to_rtl ();
 }
 
diff --git a/gcc/gengtype.c b/gcc/gengtype.c
index b02e9ff..1c281c3 100644
--- a/gcc/gengtype.c
+++ b/gcc/gengtype.c
@@ -1715,6 +1715,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",
diff --git a/gcc/gimple-pretty-print.c b/gcc/gimple-pretty-print.c
index c99dfe1..9ae5453 100644
--- a/gcc/gimple-pretty-print.c
+++ b/gcc/gimple-pretty-print.c
@@ -2109,22 +2109,17 @@  dump_ssaname_info (pretty_printer *buffer, tree node, int spc)
 	}
     }
 
-  if (!POINTER_TYPE_P (TREE_TYPE (node))
-      && SSA_NAME_RANGE_INFO (node))
+  irange *ri = SSA_NAME_RANGE_INFO (node);
+  if (!POINTER_TYPE_P (TREE_TYPE (node)) && ri)
     {
-      wide_int min, max, nonzero_bits;
-      value_range_type range_type = get_range_info (node, &min, &max);
+      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)
diff --git a/gcc/gimple-ssa-sprintf.c b/gcc/gimple-ssa-sprintf.c
index f43778b..0dd87a4 100644
--- a/gcc/gimple-ssa-sprintf.c
+++ b/gcc/gimple-ssa-sprintf.c
@@ -1132,8 +1132,7 @@  get_int_range (tree arg, HOST_WIDE_INT *pmin, HOST_WIDE_INT *pmax,
 	{
 	  /* Try to determine the range of values of the integer argument.  */
 	  wide_int min, max;
-	  enum value_range_type range_type = get_range_info (arg, &min, &max);
-	  if (range_type == VR_RANGE)
+	  if (get_range_info (arg, &min, &max))
 	    {
 	      HOST_WIDE_INT type_min
 		= (TYPE_UNSIGNED (argtype)
@@ -1432,8 +1431,7 @@  format_integer (const directive &dir, tree arg)
       /* Try to determine the range of values of the integer argument
 	 (range information is not available for pointers).  */
       wide_int min, max;
-      enum value_range_type range_type = get_range_info (arg, &min, &max);
-      if (range_type == VR_RANGE)
+      if (get_range_info (arg, &min, &max))
 	{
 	  argmin = wide_int_to_tree (argtype, min);
 	  argmax = wide_int_to_tree (argtype, max);
@@ -1449,11 +1447,7 @@  format_integer (const directive &dir, tree arg)
 	  res.argmin = argmin;
 	  res.argmax = argmax;
 	}
-      else if (range_type == VR_ANTI_RANGE)
-	{
-	  /* Handle anti-ranges if/when bug 71690 is resolved.  */
-	}
-      else if (range_type == VR_VARYING)
+      else
 	{
 	  /* The argument here may be the result of promoting the actual
 	     argument to int.  Try to determine the type of the actual
@@ -3877,9 +3871,7 @@  pass_sprintf_length::handle_gimple_call (gimple_stmt_iterator *gsi)
 	     and use the greater of the two at level 1 and the smaller
 	     of them at level 2.  */
 	  wide_int min, max;
-	  enum value_range_type range_type
-	    = get_range_info (size, &min, &max);
-	  if (range_type == VR_RANGE)
+	  if (get_range_info (size, &min, &max))
 	    {
 	      dstsize
 		= (warn_level < 2
diff --git a/gcc/gimple-ssa-warn-alloca.c b/gcc/gimple-ssa-warn-alloca.c
index ec95cc6..9f96af4 100644
--- a/gcc/gimple-ssa-warn-alloca.c
+++ b/gcc/gimple-ssa-warn-alloca.c
@@ -216,13 +216,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).
       //
@@ -252,13 +251,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
@@ -284,104 +282,103 @@  alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type)
 
   // Adjust warn_alloca_max_size for VLAs, by taking the underlying
   // type into account.
-  unsigned HOST_WIDE_INT max_size;
+  unsigned HOST_WIDE_INT max_user_size;
   if (is_vla)
-    max_size = (unsigned HOST_WIDE_INT) warn_vla_limit;
+    max_user_size = (unsigned HOST_WIDE_INT) warn_vla_limit;
   else
-    max_size = (unsigned HOST_WIDE_INT) warn_alloca_limit;
+    max_user_size = (unsigned HOST_WIDE_INT) warn_alloca_limit;
 
   // Check for the obviously bounded case.
   if (TREE_CODE (len) == INTEGER_CST)
     {
-      if (tree_to_uhwi (len) > max_size)
+      if (tree_to_uhwi (len) > max_user_size)
 	return alloca_type_and_limit (ALLOCA_BOUND_DEFINITELY_LARGE, len);
       if (integer_zerop (len))
 	return alloca_type_and_limit (ALLOCA_ARG_IS_ZERO);
       ret = alloca_type_and_limit (ALLOCA_OK);
     }
   // Check the range info if available.
-  else if (TREE_CODE (len) == SSA_NAME)
+  else 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 = SSA_NAME_RANGE_INFO (len);
+      if (wi::leu_p (max, max_user_size))
+	ret = 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))
-	    ret = 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))
+
+	    {
+	      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)))
 	    {
-	      // 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;
+	      // Fall through.
 	    }
+	  else
+	    return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, max);
 	}
       // No easily determined range and try other things.
     }
@@ -397,7 +394,7 @@  alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type)
 	{
 	  gcc_assert (!len_casted || TYPE_UNSIGNED (TREE_TYPE (len_casted)));
 	  ret = alloca_call_type_by_arg (len, len_casted,
-					 EDGE_PRED (bb, ix), max_size);
+					 EDGE_PRED (bb, ix), max_user_size);
 	  if (ret.type != ALLOCA_OK)
 	    break;
 	}
diff --git a/gcc/internal-fn.c b/gcc/internal-fn.c
index 75fe027..df6aa0a 100644
--- a/gcc/internal-fn.c
+++ b/gcc/internal-fn.c
@@ -496,7 +496,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)
diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c
index 10741a2..c1e034f 100644
--- a/gcc/ipa-prop.c
+++ b/gcc/ipa-prop.c
@@ -1896,7 +1896,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;
@@ -1906,6 +1906,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)
diff --git a/gcc/range.c b/gcc/range.c
new file mode 100644
index 0000000..2506185
--- /dev/null
+++ b/gcc/range.c
@@ -0,0 +1,1317 @@ 
+/* SSA range analysis implementation. -*- C++ -*-
+   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/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "tree.h"
+#include "gimple.h"
+#include "gimple-pretty-print.h"
+#include "fold-const.h"
+#include "ssa.h"
+#include "range.h"
+#include "selftest.h"
+
+
+void
+irange::set_range (tree t, wide_int lbound, wide_int ubound,
+		      irange_type rt)
+{
+  gcc_assert (INTEGRAL_TYPE_P (t) || POINTER_TYPE_P (t));
+  gcc_assert (TYPE_PRECISION (t) == lbound.get_precision ());
+  gcc_assert (lbound.get_precision () == ubound.get_precision ());
+  overflow = false;
+  type = t;
+  gcc_assert (wi::le_p (lbound, ubound, TYPE_SIGN (type)));
+  if (rt == RANGE_INVERT)
+    {
+      // We calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
+      bool ovf;
+      n = 0;
+      wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+      wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+
+      // If we will overflow, don't bother.  This will handle unsigned
+      // underflow which doesn't set the overflow bit.
+      //
+      // Note: Perhaps all these &ovf checks are unecessary since we
+      // are manually checking for overflow with the if() below.
+      if (lbound != min)
+	{
+	  bounds[n++] = min;
+	  bounds[n++] = wi::sub (lbound, 1, TYPE_SIGN (type), &ovf);
+	  if (ovf)
+	    n = 0;
+	}
+      // If we will overflow, don't bother.  This will handle unsigned
+      // overflow which doesn't set the overflow bit.
+      if (ubound != max)
+	{
+	  bounds[n++] = wi::add (ubound, 1, TYPE_SIGN (type), &ovf);
+	  if (ovf)
+	    n--;
+	  else
+	    bounds[n++] = max;
+	}
+
+      // If we get here with N==0, it means we tried to calculate the
+      // inverse of [-MIN, +MAX] which is actually the empty set, and
+      // N==0 maps nicely to the empty set :).
+    }
+  else
+    {
+      n = 2;
+      bounds[0] = lbound;
+      bounds[1] = ubound;
+    }
+}
+
+void
+irange::set_range (tree type)
+{
+  gcc_assert (TYPE_P (type));
+  gcc_assert (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type));
+  wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+  wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+  set_range (type, min, max);
+}
+
+irange::irange (tree t, wide_int lbound, wide_int ubound,
+		      irange_type rt)
+{
+  set_range (t, lbound, ubound, rt);
+}
+
+irange::irange (const irange &r)
+{
+  type = r.type;
+  overflow = false;
+  n = r.n;
+  for (unsigned i = 0; i < n; ++i)
+    bounds[i] = r.bounds[i];
+}
+
+// Build a range for the entire domain for TYPE.
+
+irange::irange (tree type)
+{
+  gcc_assert (TYPE_P (type));
+  set_range (type);
+}
+
+bool
+irange::operator== (const irange &r) const
+{
+  if (type != r.type || n != r.n || overflow != r.overflow)
+    return false;
+  for (unsigned i = 0; i < n; ++i)
+    if (bounds[i] != r.bounds[i])
+      return false;
+  return true;
+}
+
+irange&
+irange::operator= (const irange &r)
+{
+  type = r.type;
+  n = r.n;
+  overflow = r.overflow;
+  for (unsigned i = 0; i < n; ++i)
+    bounds[i] = r.bounds[i];
+  return *this;
+}
+
+
+irange&
+irange::operator= (tree t)
+{
+  set_range (t);
+  return *this;
+}
+
+// Return true if this range is the full range for it's type
+bool
+irange::range_for_type_p () const
+{
+  irange tmp (type);
+  return (*this == tmp);
+}
+
+
+bool
+irange::valid_p ()
+{
+  if (!n)
+    return false;
+  if (n % 2)
+    return false;
+  if (n > MAX_RANGES)
+    return false;
+  // Check that the bounds are in the right order.
+  //
+  // So for [a,b][c,d][e,f] we must have:
+  // a <= b < c <= d < e <= f
+  if (wi::gt_p (bounds[0], bounds[1], TYPE_SIGN (type)))
+    return false;
+  for (unsigned i = 2; i < n; i += 2)
+    {
+      if (wi::le_p (bounds[i], bounds[i-1], TYPE_SIGN (type)))
+	return false;
+      if (wi::gt_p (bounds[i], bounds[i+1], TYPE_SIGN (type)))
+	return false;
+    }
+  return true;
+}
+
+// Convert the current range in place into a range of type NEW_TYPE.
+// The type of the original range is changed to the new type.
+
+void
+irange::cast (tree new_type)
+{
+  if (!n)
+    {
+      type = new_type;
+      return;
+    }
+  bool sign_change = TYPE_SIGN (new_type) != TYPE_SIGN (type);
+  unsigned new_precision = TYPE_PRECISION (new_type);
+
+  // If nothing changed, this may be a useless type conversion between
+  // two variants of the same type.
+  if (!sign_change && TYPE_PRECISION (type) == new_precision)
+    {
+      type = new_type;
+      return;
+    }
+
+  // If any of the old bounds are outside of the representable range
+  // for the new type, conservatively default to the entire range of
+  // the new type.
+  if (new_precision < TYPE_PRECISION (type))
+    {
+      // Get the extreme bounds for the new type, but within the old type,
+      // so we can properly compare them.
+      wide_int lbound = fold_convert (type, TYPE_MIN_VALUE (new_type));
+      wide_int ubound = fold_convert (type, TYPE_MAX_VALUE (new_type));
+
+      if (wi::lt_p (bounds[0], lbound, TYPE_SIGN (type))
+	  || wi::gt_p (bounds[n - 1], ubound, TYPE_SIGN (type)))
+	{
+	  bounds[0] = wide_int::from (lbound, new_precision,
+				      TYPE_SIGN (new_type));
+	  bounds[1] = wide_int::from (ubound, new_precision,
+				      TYPE_SIGN (new_type));
+	  type = new_type;
+	  n = 2;
+	  return;
+	}
+    }
+
+  wide_int orig_low = lower_bound ();
+  wide_int orig_high = upper_bound ();
+  wide_int min = wi::min_value (new_precision, TYPE_SIGN (new_type));
+  wide_int max = wi::max_value (new_precision, TYPE_SIGN (new_type));
+  for (unsigned i = 0; i < n; i += 2)
+    {
+      tree b0 = fold_convert (new_type, wide_int_to_tree (type, bounds[i]));
+      tree b1 = fold_convert (new_type, wide_int_to_tree (type, bounds[i+1]));
+      bool sbit0 = bounds[i].sign_mask () < 0;
+      bool sbit1 = bounds[i + 1].sign_mask () < 0;
+
+      // If we're not doing a sign change, or we are moving to a
+      // higher precision, we can just blindly chop off bits.
+      if (!sign_change
+	  || (TYPE_UNSIGNED (type)
+	      && !TYPE_UNSIGNED (new_type)
+	      && new_precision > TYPE_PRECISION (type))
+	  || sbit0 == sbit1)
+	{
+	  bounds[i] = b0;
+	  bounds[i + 1] = b1;
+	}
+      else
+	{
+	  // If we're about to go over the maximum number of ranges
+	  // allowed, convert to something conservative and cast again.
+	  if (n >= MAX_RANGES)
+	    {
+	      bounds[0] = orig_low;
+	      bounds[1] = orig_high;
+	      n = 2;
+	      cast (new_type);
+	      return;
+	    }
+
+	  //  If we're about to construct [MIN, b1==MAX].  That's just
+	  //  the entire range.
+	  if ((wide_int) b1 == max)
+	    {
+	      bounds[0] = min;
+	      bounds[1] = max;
+	      n = 2;
+	      type = new_type;
+	      return;
+	    }
+	  // From no sign bit to sign bit: [15, 150] => [15,127][-128,-106]
+	  if (!sbit0 && sbit1)
+	    {
+	      bounds[i] = min;
+	      bounds[i + 1] = b1;
+	      bounds[n++] = b0;
+	      bounds[n++] = max;
+	    }
+	  // From sign bit to no sign bit: [-5, 5] => [251,255][0,5]
+	  else
+	    {
+	      bounds[i] = min;
+	      bounds[i + 1] = b1;
+	      bounds[n++] = b0;
+	      bounds[n++] = max;
+	    }
+	}
+    }
+  type = new_type;
+  if (sign_change)
+    canonicalize ();
+  gcc_assert (valid_p ());
+}
+
+// Return TRUE if the current range contains ELEMENT.
+
+bool
+irange::contains_p (wide_int element)
+{
+  for (unsigned i = 0; i < n; i += 2)
+    if (wi::ge_p (element, bounds[i], TYPE_SIGN (type))
+	&& wi::le_p (element, bounds[i + 1], TYPE_SIGN (type)))
+      return true;
+  return false;
+}
+
+// Like above, but ELEMENT can be an INTEGER_CST of any type.
+
+bool
+irange::contains_p (tree element)
+{
+  gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (element)));
+  element = fold_convert (type, element);
+  if (TREE_OVERFLOW (element))
+    return false;
+  wide_int wi = element;
+  return contains_p (wi);
+}
+
+// Canonicalize the current range.
+
+void
+irange::canonicalize ()
+{
+  if (n < 2)
+    return;
+
+  // Fix any out of order ranges: [10,20][-5,5] into [-5,5][10,20].
+  //
+  // This is not a true sort by design because I *think* we won't
+  // create any truly wacky ranges during casting.  As a temporary
+  // measure, check assert(valid_p()) afterwards and if we catch
+  // anything, rewrite this into a bubble sort.
+  for (unsigned i = 0; i < n - 2; i += 2)
+    if (wi::gt_p (bounds[i], bounds[i + 2], TYPE_SIGN (type)))
+      {
+	wide_int x = bounds[i], y = bounds[i + 1];
+	bounds[i] = bounds[i + 2];
+	bounds[i + 1] = bounds[i + 3];
+	bounds[i + 2] = x;
+	bounds[i + 3] = y;
+      }
+  gcc_assert (valid_p ()); // See note before for(;;).
+
+  // Merge any edges that touch.
+  // [9,10][11,20] => [9,20]
+  for (unsigned i = 1; i < n - 2; i += 2)
+    {
+      bool ovf;
+      wide_int x = wi::add (bounds[i], 1, TYPE_SIGN (type), &ovf);
+      // No need to check for overflow here for the +1, since the
+      // middle ranges cannot have MAXINT.
+      if (x == bounds[i + 1])
+	{
+	  bounds[i] = bounds[i + 2];
+	  remove (i + 1, i + 2);
+	}
+    }
+}
+
+// Prepend [X,Y] into THIS.
+
+void
+irange::prepend (wide_int x, wide_int y)
+{
+  // If we have enough space, shift everything to the right and prepend.
+  if (n < MAX_RANGES)
+    {
+      for (unsigned i = n; i; i -= 2)
+	{
+	  bounds[i] = bounds[i - 2];
+	  bounds[i + 1] = bounds[i - 1];
+	}
+      bounds[0] = x;
+      bounds[1] = y;
+      n += 2;
+    }
+  // Otherwise, merge it with the first entry.
+  else
+    bounds[0] = x;
+  canonicalize ();
+}
+
+// Place [X,Y] at the end of THIS.
+
+void
+irange::append (wide_int x, wide_int y)
+{
+  // If we have enough space, make space at the end and append.
+  if (n < MAX_RANGES)
+    {
+      bounds[n++] = x;
+      bounds[n++] = y;
+    }
+  // Otherwise, merge it with the last entry.
+  else
+    bounds[n - 1] = y;
+  canonicalize ();
+}
+
+// Remove the bound entries from [i..j].
+
+void
+irange::remove (unsigned i, unsigned j)
+{
+  gcc_assert (i < n && i < j);
+  unsigned dst = i;
+  unsigned ndeleted = j - i + 1;
+  for (++j; j < n; ++j)
+    bounds[dst++] = bounds[j];
+  n -= ndeleted;
+}
+
+// THIS = THIS U [X,Y]
+
+void
+irange::Union (wide_int x, wide_int y)
+{
+  if (empty_p ())
+    {
+      bounds[0] = x;
+      bounds[1] = y;
+      n = 2;
+      return;
+    }
+
+  // If [X,Y] comes before, put it at the front.
+  if (wi::lt_p (y, bounds[0], TYPE_SIGN (type)))
+    {
+      prepend (x, y);
+      return;
+    }
+  // If [X,Y] comes after, put it at the end.
+  if (wi::gt_p (x, bounds[n - 1], TYPE_SIGN (type)))
+    {
+      append (x, y);
+      return;
+    }
+  // Handle [X,Y] swalling up all of THIS.
+  if (wi::le_p (x, bounds[0], TYPE_SIGN (type))
+      && wi::ge_p (y, bounds[n - 1], TYPE_SIGN (type)))
+    {
+      bounds[0] = x;
+      bounds[1] = y;
+      n = 2;
+      return;
+    }
+  // Handle X starting before, while Y is within.
+  //              Y
+  // X[a,b][c,d][e,f][g,h][i,j]
+  // ==> [X,Y][g,h][i,j]
+  if (wi::lt_p (x, bounds[0], TYPE_SIGN (type)))
+    {
+      bounds[0] = x;
+
+      //    Y
+      // X[a,b]   => [X,b]
+      if (n == 2)
+	return;
+
+      for (unsigned i = 1; i < n; i += 2)
+	if (wi::le_p (y, bounds[i], TYPE_SIGN (type)))
+	  {
+	    if (y == bounds[i])
+	      bounds[1] = y;
+	    else
+	      bounds[1] = bounds[i];
+	    remove (2, i);
+	    return;
+	  }
+      gcc_unreachable ();
+    }
+  // Handle Y being outside, while X is within.
+  //              X           Y
+  // [a,b][c,d][e,f][g,h][i,j]
+  // ==> [a,b][c,d][e,Y]
+  if (wi::gt_p (y, bounds[n - 1], TYPE_SIGN (type)))
+    {
+      for (unsigned i = 0; i < n; i += 2)
+	if (wi::ge_p (bounds[i + 1], x, TYPE_SIGN (type)))
+	  {
+	    bounds[i + 1] = y;
+	    n = i + 2;
+	    return;
+	  }
+      gcc_unreachable ();
+    }
+
+  // At this point, [X,Y] must be completely inside.
+  //  X           Y
+  // [a,b][c,d][e,f][g,h]
+  gcc_assert (wi::ge_p (x, bounds[0], TYPE_SIGN (type))
+	      && wi::le_p (y, bounds[n - 1], TYPE_SIGN (type)));
+
+  // Find X.
+  gcc_assert (n >= 2);
+  unsigned xpos = ~0U;
+  unsigned i = n;
+  do
+    {
+      i -= 2;
+      if (wi::ge_p (x, bounds[i], TYPE_SIGN (type)))
+	{
+	  xpos = i;
+	  break;
+	}
+    }
+  while (i);
+  gcc_assert (xpos != ~0U);
+
+  // Find Y.
+  unsigned ypos = ~0U;
+  for (i = 1; i < n; i += 2)
+    if (wi::le_p (y, bounds[i], TYPE_SIGN (type)))
+      {
+	ypos = i;
+	break;
+      }
+  gcc_assert (ypos != ~0U);
+
+  // If [x,y] is inside of subrange [xpos,ypos], there's nothing to do.
+  if (xpos + 1 == ypos)
+    return;
+
+  // Merge the sub-ranges in between xpos and ypos.
+  y = bounds[ypos];
+  remove (xpos + 2, ypos);
+  bounds[xpos + 1] = y;
+}
+
+// THIS = R1 U R2
+
+bool
+irange::Union (const irange &r1, const irange &r2)
+{
+  gcc_assert (r1.type == r2.type);
+
+  if (r1.empty_p ())
+    {
+      *this = r2;
+      return true;
+    }
+  else if (r2.empty_p ())
+    {
+      *this = r1;
+      return true;
+    }
+
+  *this = r1;
+  for (unsigned i = 0; i < r2.n; i += 2)
+    Union (r2.bounds[i], r2.bounds[i + 1]);
+
+  overflow |= r1.overflow;
+  return true;
+}
+
+// THIS = THIS U R
+
+bool
+irange::Union (const irange &r)
+{
+  if (*this == r)
+    return true;
+  return Union (*this, r);
+}
+
+// THIS = THIS ^ [X,Y]
+//
+// Returns TRUE if the result of the intersection is non-empty.
+//
+// If READONLY is TRUE, we are only interested in determining if the
+// operation will yield a non-empty value.  THIS is left unchanged.
+
+bool
+irange::Intersect (wide_int x, wide_int y, bool readonly)
+{
+  unsigned pos = 0;
+
+  for (unsigned i = 0; i < n; i += 2)
+    {
+      wide_int newlo = wi::max (bounds[i], x, TYPE_SIGN (type));
+      wide_int newhi = wi::min (bounds[i + 1], y, TYPE_SIGN (type));
+      if (wi::gt_p (newlo, newhi, TYPE_SIGN (type)))
+	{
+	  // If the new sub-range doesn't make sense, it's an
+	  // impossible range and must be kept out of the result.
+	}
+      else
+	{
+	  if (readonly)
+	    return true;
+	  bounds[pos++] = newlo;
+	  bounds[pos++] = newhi;
+	}
+    }
+  n = pos;
+  return n != 0;
+}
+
+// THIS = R1 ^ R2
+//
+// Returns TRUE if the result of the intersection is non-empty.
+//
+// If READONLY is TRUE, we are only interested in determining if the
+// operation will yield a non-empty value.  THIS is left unchanged.
+
+bool
+irange::Intersect (const irange &r1, const irange &r2, bool readonly)
+{
+  gcc_assert (r1.type == r2.type);
+
+  if (!readonly)
+    clear (r1.type);
+
+  // Intersection with an empty range is an empty range.
+  if (r1.empty_p () || r2.empty_p ())
+    return false;
+
+  // The general algorithm is as follows.
+  //
+  // Intersect each sub-range of R2 with all of R1 one at a time, and
+  // join/union the results of these intersections together.  I.e:
+  //
+  // [10,20][30,40][50,60] ^ [15,25][38,51][55,70]
+  //
+  // Step 1: [10,20][30,40][50,60] ^ [15,25] => [15,20]
+  // Step 2: [10,20][30,40][50,60] ^ [38,51] => [38,40]
+  // Step 3: [10,20][30,40][50,60] ^ [55,70] => [55,60]
+  // Final:  [15,20] U [38,40] U [55,60] => [15,20][38,40][55,60]
+
+  // ?? We should probably accumulate into a new range instead of
+  // joining at each step, and stop making a copy of R1 at every step.
+
+  for (unsigned i = 0; i < r2.n; i += 2)
+    {
+      irange chunk (r1);
+      if (chunk.Intersect (r2.bounds[i], r2.bounds[i + 1]))
+	{
+	  if (readonly)
+	    return true;
+	  Union (chunk);
+	}
+    }
+
+  // Overflow is sticky only if both ranges overflowed.
+  overflow = (r1.overflow && r2.overflow);
+  return n != 0;
+}
+
+// THIS = THIS ^ R
+//
+// Returns TRUE if the result of the intersection is non-empty.
+//
+// If READONLY is TRUE, we are only interested in determining if the
+// operation will yield a non-empty value.  THIS is left unchanged.
+
+bool
+irange::Intersect (const irange &r, bool readonly)
+{
+  irange q = *this;
+  return Intersect (q, r, readonly);
+}
+
+// THIS = NOT(R).
+
+bool
+irange::Not (const irange& r)
+{
+  type = r.type;
+  overflow = r.overflow;
+
+  // We always need one more set of bounds to represent a NOT, so if
+  // we're at the limit, we can't properly represent things.
+  //
+  // For instance, to represent a NOT of a 2 sub-range set
+  // [5, 10][20, 30], we would need a 3 sub-range set
+  // [-MIN, 4][11, 19][31, MAX].
+  //
+  // In this case convert the current range to something more
+  // conservative, and return the NOT of that.
+  if (r.n >= MAX_RANGES)
+    {
+      bounds[0] = r.bounds[0];
+      bounds[1] = r.bounds[n - 1];
+      n = 2;
+      return Not ();
+    }
+
+  // The inverse of the empty set is the entire domain.
+  if (r.empty_p ())
+    {
+      set_range (type);
+      return false;
+    }
+
+  // The algorithm is as follows.  To calculate NOT ([a,b][c,d]), we
+  // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
+  //
+  // If there is an over/underflow in the calculation for any
+  // sub-range, we eliminate that subrange.  This allows us to easily
+  // calculate NOT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX].  And since
+  // we eliminate the underflow, only [6, MAX] remains.
+
+  unsigned i = 0;
+  bool ovf;
+
+  // Construct leftmost range.
+  n = 0;
+  wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+  // If this is going to underflow on the MINUS 1, don't even bother
+  // checking.  This also handles subtracting one from an unsigned 0,
+  // which doesn't set the underflow bit.
+  if (min != r.bounds[i])
+    {
+      bounds[n++] = min;
+      bounds[n++] = wi::sub (r.bounds[i], 1, TYPE_SIGN (type), &ovf);
+      if (ovf)
+	n = 0;
+    }
+  i++;
+  // Construct middle ranges if applicable.
+  if (r.n > 2)
+    {
+      unsigned j = i;
+      for (; j < r.n - 2; j += 2)
+	{
+	  /* The middle ranges cannot have MAX/MIN, so there's no need
+	     to check for unsigned overflow on the +1 and -1 here.  */
+	  bounds[n++] = wi::add (r.bounds[j], 1, TYPE_SIGN (type), &ovf);
+	  bounds[n++] = wi::sub (r.bounds[j + 1], 1, TYPE_SIGN (type), &ovf);
+	  if (ovf)
+	    n -= 2;
+	}
+      i = j;
+    }
+  // Construct rightmost range.
+  wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+  // If this will overflow on the PLUS 1, don't even bother.  This
+  // also handles adding one to an unsigned MAX, which doesn't set the
+  // overflow bit.
+  if (max != r.bounds[i])
+    {
+      bounds[n++] = wi::add (r.bounds[i], 1, TYPE_SIGN (type), &ovf);
+      bounds[n++] = max;
+      if (ovf)
+	n -= 2;
+    }
+
+  return n != 0;
+}
+
+// THIS = Not (THIS).
+
+bool
+irange::Not ()
+{
+  irange tmp (*this);
+  return Not (tmp);
+}
+
+wide_int
+irange::lower_bound (unsigned index)
+{
+  gcc_assert (n != 0 && index <= n/2);
+  return bounds[index * 2];
+}
+
+wide_int
+irange::upper_bound (unsigned index)
+{
+  gcc_assert (n != 0 && index <= n/2);
+  return bounds[index * 2 + 1];
+}
+
+/* Dump the current range onto BUFFER.  */
+
+void
+irange::dump (pretty_printer *buffer)
+{
+  if (!n)
+    {
+      pp_string (buffer, "[]");
+      return;
+    }
+  for (unsigned i = 0; i < n; ++i)
+    {
+      if (i % 2 == 0)
+	pp_character (buffer, '[');
+      wide_int val = bounds[i];
+      print_hex (val, pp_buffer (buffer)->digit_buffer);
+      pp_string (buffer, pp_buffer (buffer)->digit_buffer);
+      if (i % 2 == 0)
+	pp_string (buffer, ", ");
+      else
+	pp_character (buffer, ']');
+    }
+  if (overflow)
+    pp_string (buffer, "(overflow)");
+
+  pp_string (buffer, " precision = ");
+  pp_decimal_int (buffer, TYPE_PRECISION (type));
+}
+
+/* Dump the current range onto FILE F.  */
+
+void
+irange::dump (FILE *f)
+{
+  pretty_printer buffer;
+  buffer.buffer->stream = f;
+  dump (&buffer);
+  pp_newline_and_flush (&buffer);
+}
+
+/* Like above but dump to STDERR.
+
+   ?? You'd think we could have a default parameter for dump(FILE),
+   but gdb currently doesn't do default parameters gracefully-- or at
+   all, and since this is a function we need to be callable from the
+   debugger... */
+
+void
+irange::dump ()
+{
+  dump (stderr);
+}
+
+bool
+make_irange (irange_p result, tree lb, tree ub, tree type)
+{
+  irange r (TREE_TYPE (lb), lb, ub);
+  *result = r;
+  if (result->valid_p ())
+    {
+      if (type)
+        result->cast (type);
+      return true;
+    }
+  return false;
+}
+
+bool
+make_irange_not (irange_p result, tree not_exp, tree type)
+{
+  irange r (TREE_TYPE (not_exp), not_exp, not_exp, RANGE_INVERT);
+  *result = r;
+  if (result->valid_p ())
+    {
+      if (type)
+        result->cast (type);
+      return true;
+    }
+  return false;
+}
+
+void
+range_one (irange_p r, tree type)
+{
+  tree one = build_int_cst (type, 1);
+  r->set_range (type, one, one);
+}
+
+void
+range_zero (irange_p r, tree type)
+{
+  tree zero = build_int_cst (type, 0);
+  r->set_range (type, zero, zero);
+}
+
+bool
+range_non_zero (irange_p r, tree type)
+{
+  tree zero = build_int_cst (type, 0);
+  return make_irange_not (r, zero, type);
+}
+
+/* Set the range of R to the set of positive numbers starting at START.  */
+
+void
+range_positives (irange_p r, tree type, unsigned int start)
+{
+  r->set_range (type, build_int_cst (type, start), TYPE_MAX_VALUE (type));
+}
+
+#ifdef CHECKING_P
+namespace selftest {
+
+
+#define INT(N) build_int_cst (integer_type_node, (N))
+#define UINT(N) build_int_cstu (unsigned_type_node, (N))
+#define INT16(N) build_int_cst (short_integer_type_node, (N))
+#define UINT16(N) build_int_cstu (short_unsigned_type_node, (N))
+#define INT64(N) build_int_cstu (long_long_integer_type_node, (N))
+#define UINT64(N) build_int_cstu (long_long_unsigned_type_node, (N))
+#define UINT128(N) build_int_cstu (u128_type, (N))
+#define UCHAR(N) build_int_cst (unsigned_char_type_node, (N))
+#define SCHAR(N) build_int_cst (signed_char_type_node, (N))
+
+#define RANGE1(A,B) irange (integer_type_node, INT(A), INT(B))
+
+#define RANGE2(A,B,C,D)					\
+( i1 = irange (integer_type_node, INT (A), INT (B)),	\
+  i2 = irange (integer_type_node, INT (C), INT (D)),	\
+  i1.Union (i2),					\
+  i1 )
+
+#define RANGE3(A,B,C,D,E,F) 				\
+( i1 = irange (integer_type_node, INT (A), INT (B)),	\
+  i2 = irange (integer_type_node, INT (C), INT (D)),	\
+  i3 = irange (integer_type_node, INT (E), INT (F)),	\
+  i1.Union (i2),					\
+  i1.Union (i3),					\
+  i1 )
+
+// Run all of the selftests within this file.
+
+void
+irange_tests ()
+{
+  tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1);
+  irange i1, i2, i3;
+  irange r0, r1, rold;
+  ASSERT_FALSE (r0.valid_p ());
+
+  // Test that NOT(255) is [0..254] in 8-bit land.
+  irange not_255;
+  make_irange_not (&not_255, UCHAR(255), unsigned_char_type_node);
+  ASSERT_TRUE (not_255 == irange (unsigned_char_type_node,
+				  UCHAR(0), UCHAR(254)));
+
+  // Test that NOT(0) is [1..255] in 8-bit land.
+  irange not_zero;
+  range_non_zero (&not_zero, unsigned_char_type_node);
+  ASSERT_TRUE (not_zero == irange (unsigned_char_type_node,
+				   UCHAR(1), UCHAR(255)));
+
+  // Check that [0,127][0x..ffffff80,0x..ffffff] == ~[128, 0x..ffffff7f]
+  r0 = irange (u128_type, UINT128(0), UINT128(127), RANGE_PLAIN);
+  tree high = build_minus_one_cst (u128_type);
+  // low = -1 - 127 => 0x..ffffff80
+  tree low = fold_build2 (MINUS_EXPR, u128_type, high, UINT128(127));
+  r1 = irange (u128_type, low, high); // [0x..ffffff80, 0x..ffffffff]
+  // r0 = [0,127][0x..ffffff80,0x..fffffff]
+  r0.Union (r1);
+  // r1 = [128, 0x..ffffff7f]
+  r1 = irange (u128_type,
+	       UINT128(128),
+	       fold_build2 (MINUS_EXPR, u128_type,
+			    build_minus_one_cst (u128_type),
+			    UINT128(128)));
+  r0.Not ();
+  ASSERT_TRUE (r0 == r1);
+
+  r0.set_range (integer_type_node);
+  tree minint = wide_int_to_tree (integer_type_node, r0.lower_bound ());
+  tree maxint = wide_int_to_tree (integer_type_node, r0.upper_bound ());
+
+  r0.set_range (short_integer_type_node);
+  tree minshort = wide_int_to_tree (short_integer_type_node, r0.lower_bound ());
+  tree maxshort = wide_int_to_tree (short_integer_type_node, r0.upper_bound ());
+
+  r0.set_range (unsigned_type_node);
+  tree maxuint = wide_int_to_tree (unsigned_type_node, r0.upper_bound ());
+
+  // Check that ~[0,5] => [6,MAX] for unsigned int.
+  r0 = irange (unsigned_type_node, UINT(0), UINT(5), RANGE_PLAIN);
+  r0.Not ();
+  ASSERT_TRUE (r0 == irange (unsigned_type_node, UINT(6), maxuint));
+
+  // Check that ~[10,MAX] => [0,9] for unsigned int.
+  r0 = irange (unsigned_type_node, UINT(10), maxuint, RANGE_PLAIN);
+  r0.Not ();
+  ASSERT_TRUE (r0 == irange (unsigned_type_node, UINT(0), UINT(9)));
+
+  // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
+  r0.set_range (u128_type, UINT128(0), UINT128(5), RANGE_INVERT);
+  r1 = irange (u128_type, UINT128(6), build_minus_one_cst (u128_type));
+  ASSERT_TRUE (r0 == r1);
+
+  // Check that [~5] is really [-MIN,4][6,MAX]
+  r0 = irange (integer_type_node, INT(5), INT(5), RANGE_INVERT);
+  r1 = irange (integer_type_node, minint, INT(4));
+  ASSERT_TRUE (r1.Union (irange (integer_type_node, INT(6), maxint)));
+
+  ASSERT_TRUE (r0 == r1);
+
+  r1.set_range (integer_type_node, INT(5), INT(5));
+  ASSERT_TRUE (r1.valid_p ());
+  irange r2 (r1);
+  ASSERT_TRUE (r1 == r2);
+
+  r1 = RANGE1 (5, 10);
+  ASSERT_TRUE (r1.valid_p ());
+
+  r1 = irange (integer_type_node, (wide_int) INT(5), (wide_int) INT(10));
+  ASSERT_TRUE (r1.valid_p ());
+  ASSERT_TRUE (r1.contains_p (INT (7)));
+
+  r1 = irange (signed_char_type_node, SCHAR(0), SCHAR(20));
+  ASSERT_TRUE (r1.contains_p (INT(15)));
+  ASSERT_FALSE (r1.contains_p (INT(300)));
+
+  // If a range is in any way outside of the range for the converted
+  // to range, default to the range for the new type.
+  r1 = irange (integer_type_node, integer_zero_node, maxint);
+  r1.cast (short_integer_type_node);
+  ASSERT_TRUE (r1.lower_bound () == minshort && r1.upper_bound() == maxshort);
+
+  // (unsigned char)[-5,-1] => [251,255]
+  r0 = rold = irange (signed_char_type_node, SCHAR (-5), SCHAR(-1));
+  r0.cast (unsigned_char_type_node);
+  ASSERT_TRUE (r0 == irange (unsigned_char_type_node,
+			     UCHAR(251), UCHAR(255)));
+  r0.cast (signed_char_type_node);
+  ASSERT_TRUE (r0 == rold);
+
+  // (signed char)[15, 150] => [-128,-106][15,127]
+  r0 = rold = irange (unsigned_char_type_node, UCHAR(15), UCHAR(150));
+  r0.cast (signed_char_type_node);
+  r1 = irange (signed_char_type_node, SCHAR(15), SCHAR(127));
+  r2 = irange (signed_char_type_node, SCHAR(-128), SCHAR(-106));
+  r1.Union (r2);
+  ASSERT_TRUE (r1 == r0);
+  r0.cast (unsigned_char_type_node);
+  ASSERT_TRUE (r0 == rold);
+
+  // (unsigned char)[-5, 5] => [0,5][251,255]
+  r0 = rold = irange (signed_char_type_node, SCHAR(-5), SCHAR(5));
+  r0.cast (unsigned_char_type_node);
+  r1 = irange (unsigned_char_type_node, UCHAR(251), UCHAR(255));
+  r2 = irange (unsigned_char_type_node, UCHAR(0), UCHAR(5));
+  r1.Union (r2);
+  ASSERT_TRUE (r0 == r1);
+  r0.cast (signed_char_type_node);
+  ASSERT_TRUE (r0 == rold);
+
+  // (unsigned char)[-5,5] => [0,255]
+  r0 = irange (integer_type_node, INT(-5), INT(5));
+  r0.cast (unsigned_char_type_node);
+  r1 = irange (unsigned_char_type_node,
+	       TYPE_MIN_VALUE (unsigned_char_type_node),
+	       TYPE_MAX_VALUE (unsigned_char_type_node));
+  ASSERT_TRUE (r0 == r1);
+
+  // (unsigned char)[5U,1974U] => [0,255]
+  r0 = irange (unsigned_type_node, UINT(5), UINT(1974));
+  r0.cast (unsigned_char_type_node);
+  ASSERT_TRUE (r0 == irange (unsigned_char_type_node, UCHAR(0), UCHAR(255)));
+  r0.cast (integer_type_node);
+  // Going to a wider range should not sign extend.
+  ASSERT_TRUE (r0 == RANGE1 (0, 255));
+
+  // (unsigned char)[-350,15] => [0,255]
+  r0 = irange (integer_type_node, INT(-350), INT(15));
+  r0.cast (unsigned_char_type_node);
+  ASSERT_TRUE (r0 == irange (unsigned_char_type_node,
+			     TYPE_MIN_VALUE (unsigned_char_type_node),
+			     TYPE_MAX_VALUE (unsigned_char_type_node)));
+
+  // Casting [-120,20] from signed char to unsigned short.
+  //    (unsigned)[(signed char)-120, (signed char)20]
+  // => (unsigned)[0, 0x14][0x88, 0xff]
+  // => [0,0x14][0xff88,0xffff]
+  r0 = irange (signed_char_type_node, SCHAR(-120), SCHAR(20));
+  r0.cast (short_unsigned_type_node);
+  r1 = irange (short_unsigned_type_node, UINT16(0), UINT16(0x14));
+  r2 = irange (short_unsigned_type_node, UINT16(0xff88), UINT16(0xffff));
+  r1.Union (r2);
+  ASSERT_TRUE (r0 == r1);
+  // Casting back to signed char (a smaller type), would be outside of the
+  // range, we it'll be the entire range of the signed char.
+  r0.cast (signed_char_type_node);
+  ASSERT_TRUE (r0 == irange (signed_char_type_node,
+			     TYPE_MIN_VALUE (signed_char_type_node),
+			     TYPE_MAX_VALUE (signed_char_type_node)));
+
+  // unsigned char -> signed short
+  //    (signed short)[(unsigned char)25, (unsigned char)250]
+  // => [(signed short)25, (signed short)250]
+  r0 = rold = irange (unsigned_char_type_node, UCHAR(25), UCHAR(250));
+  r0.cast (short_integer_type_node);
+  r1 = irange (short_integer_type_node, INT16(25), INT16(250));
+  ASSERT_TRUE (r0 == r1);
+  r0.cast (unsigned_char_type_node);
+  ASSERT_TRUE (r0 == rold);
+
+  // Test casting a wider signed [-MIN,MAX] to a narrower unsigned.
+  r0 = irange (long_long_integer_type_node,
+	       TYPE_MIN_VALUE (long_long_integer_type_node),
+	       TYPE_MAX_VALUE (long_long_integer_type_node));
+  r0.cast (short_unsigned_type_node);
+  r1 = irange (short_unsigned_type_node,
+	       TYPE_MIN_VALUE (short_unsigned_type_node),
+	       TYPE_MAX_VALUE (short_unsigned_type_node));
+  ASSERT_TRUE (r0 == r1);
+
+  // Test that casting a range with MAX_RANGES that changes sign is
+  // done conservatively.
+  //
+  //    (unsigned short)[-5,5][20,30][40,50]...
+  // => (unsigned short)[-5,50]
+  // => [0,50][65531,65535]
+  r0 = irange (short_integer_type_node, INT16(-5), INT16(5));
+  gcc_assert (MAX_RANGES * 10 + 10 < 32767);
+  for (unsigned i = 2; i < MAX_RANGES; i += 2)
+    {
+      r1 = irange (short_integer_type_node, INT16(i * 10), INT16(i * 10 + 10));
+      r0.Union (r1);
+    }
+  r0.cast(short_unsigned_type_node);
+  r1 = irange (short_unsigned_type_node, INT16(0), INT16(50));
+  r2 = irange (short_unsigned_type_node, INT16(65531), INT16(65535));
+  r1.Union (r2);
+  ASSERT_TRUE (r0 == r1);
+
+  // NOT([10,20]) ==> [-MIN,9][21,MAX]
+  r0 = r1 = irange (integer_type_node, INT(10), INT(20));
+  r2 = irange (integer_type_node, minint, INT(9));
+  ASSERT_TRUE (r2.Union (irange (integer_type_node, INT(21), maxint)));
+  ASSERT_TRUE (r1.Not ());
+  ASSERT_TRUE (r1 == r2);
+  // Test that NOT(NOT(x)) == x.
+  ASSERT_TRUE (r2.Not ());
+  ASSERT_TRUE (r0 == r2);
+
+  // NOT(-MIN,+MAX) is the empty set and should return false.
+  r0 = irange (integer_type_node, wide_int_to_tree (integer_type_node, minint),
+		  wide_int_to_tree (integer_type_node, maxint));
+  ASSERT_FALSE (r0.Not ());
+  r1.clear ();
+  ASSERT_TRUE (r0 == r1);
+
+  // Test uninitialized.Not(xxx).
+  r0 = RANGE1 (10, 20);
+  {
+    irange uninitialized;
+    uninitialized.Not(r0);
+    r1 = irange (integer_type_node, INT(10), INT(20), RANGE_INVERT);
+    ASSERT_TRUE (uninitialized == r1);
+  }
+
+  // Test that booleans and their inverse work as expected.
+  range_zero (&r0, boolean_type_node);
+  ASSERT_TRUE (r0 == irange (boolean_type_node,
+			     build_int_cst (boolean_type_node, 0),
+			     build_int_cst (boolean_type_node, 0)));
+  r0.Not();
+  ASSERT_TRUE (r0 == irange (boolean_type_node,
+			     build_int_cst (boolean_type_node, 1),
+			     build_int_cst (boolean_type_node, 1)));
+
+  // Casting NONZERO to a narrower type will wrap/overflow so
+  // it's just the entire range for the narrower type.
+  //
+  // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32].  This is
+  // is outside of the range of a smaller range, return the full
+  // smaller range.
+  range_non_zero (&r0, integer_type_node);
+  r0.cast (short_integer_type_node);
+  r1 = irange (short_integer_type_node,
+	       TYPE_MIN_VALUE (short_integer_type_node),
+	       TYPE_MAX_VALUE (short_integer_type_node));
+  ASSERT_TRUE (r0 == r1);
+
+  // Casting NONZERO from a narrower signed to a wider signed.
+  //
+  // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
+  // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16]
+  range_non_zero (&r0, short_integer_type_node);
+  r0.cast (integer_type_node);
+  r1 = RANGE1 (-32768, -1);
+  r2 = RANGE1 (1, 32767);
+  r1.Union (r2);
+  ASSERT_TRUE (r0 == r1);
+
+  // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20]
+  r0 = RANGE1 (10, 20);
+  r1 = RANGE1 (5, 8);
+  r0.Union (r1);
+  r1 = RANGE1 (1, 3);
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE3 (1, 3, 5, 8, 10, 20));
+
+  // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20]
+  r1 = irange (integer_type_node, INT(-5), INT(0));
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE3 (-5, 3, 5, 8, 10, 20));
+
+  // [10,20] U [30,40] ==> [10,20][30,40]
+  r0 = irange (integer_type_node, INT(10), INT(20));
+  r1 = irange (integer_type_node, INT(30), INT(40));
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE2 (10, 20, 30, 40));
+  // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60]
+  r1 = irange (integer_type_node, INT(50), INT(60));
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE3 (10, 20, 30, 40, 50, 60));
+  // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,80]
+  r1 = irange (integer_type_node, INT(70), INT(80));
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE3 (10, 20, 30, 40, 50, 80));
+
+  // 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);
+  range_zero (&r0, voidp);
+  r1 = r0;
+  r0.Not();
+  r0.Not ();
+  ASSERT_TRUE (r0 == r1);
+
+  // [10,20][30,40][50,60] U [6,35] => [6,40][50,60]
+  r0 = RANGE3 (10, 20, 30, 40, 50, 60);
+  r1 = RANGE1 (6, 35);
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE2 (6,40,50,60));
+
+  r0 = RANGE3 (10, 20, 30, 40, 50, 60);
+  r1 = RANGE1 (6, 60);
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE1 (6,60));
+
+  // [10,20][30,40][50,60] U [6,70] => [6,70]
+  r0 = RANGE3 (10, 20, 30, 40, 50, 60);
+  r1 = RANGE1 (6, 70);
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE1 (6,70));
+
+  // [10,20][30,40][50,60] U [35,70] => [10,20][30,70]
+  r0 = RANGE3 (10,20,30,40,50,60);
+  r1 = RANGE1 (35,70);
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE2 (10,20,30,70));
+
+  // [10,20][30,40] U [25,70] => [10,70]
+  r0 = RANGE2 (10,20,30,40);
+  r1 = RANGE1 (25,70);
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE2 (10,20,30,70));
+
+  // [10,20][30,40][50,60] U [15,35] => [10,40][50,60]
+  r0 = RANGE3 (10,20,30,40,50,60);
+  r1 = RANGE1 (15,35);
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE2 (10,40,50,60));
+
+  // [10,20] U [15, 30] => [10, 30]
+  r0 = RANGE1 (10,20);
+  r1 = RANGE1 (15,30);
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE1 (10,30));
+
+  // [10,20] U [25,25] => [10,20][25,25]
+  r0 = RANGE1 (10,20);
+  r1 = RANGE1 (25,25);
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE2 (10,20,25,25));
+
+  // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60]
+  r0 = RANGE3 (10,20,30,40,50,60);
+  r1 = RANGE1 (35,35);
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE3 (10,20,30,40,50,60));
+
+  // [15,40] U [] => [15,40]
+  r0 = RANGE1 (15,40);
+  r1.clear ();
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE1 (15,40));
+
+  // [10,20] U [10,10] => [10,20]
+  r0 = RANGE1 (10,20);
+  r1 = RANGE1 (10,10);
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE1 (10,20));
+
+  // [10,20] U [9,9] => [9,20]
+  r0 = RANGE1 (10,20);
+  r1 = RANGE1 (9,9);
+  r0.Union (r1);
+  ASSERT_TRUE (r0 == RANGE1 (9,20));
+
+  // [10,10][12,12][20,100] ^ [15,200]
+  r0 = RANGE3 (10,10,12,12,20,100);
+  r1 = RANGE1 (15,200);
+  r0.Intersect (r1);
+  ASSERT_TRUE (r0 == RANGE1 (20,100));
+
+  // [10,20][30,40][50,60] ^ [15,25][38,51][55,70] => [15,20][38,40][50,60]
+  r0 = RANGE3 (10,20,30,40,50,60);
+  r1 = RANGE3 (15,25,38,51,55,70);
+  r0.Intersect (r1);
+  ASSERT_TRUE (r0 == RANGE3 (15,20,38,40,50,60));
+
+  // [15,20][30,40][50,60] ^ [15,35][40,90][100,200] => [15,20][30,35][40,60]
+  r0 = RANGE3 (15,20,30,40,50,60);
+  r1 = RANGE3 (15,35,40,90,100,200);
+  r0.Intersect (r1);
+  ASSERT_TRUE (r0 == RANGE3 (15,20,30,35,40,60));
+
+  // [10,20][30,40] U [40,50] => [40,40]
+  r0 = RANGE2 (10,20,30,40);
+  r1 = RANGE1 (40,50);
+  r0.Intersect (r1);
+  ASSERT_TRUE (r0 == RANGE1 (40,40));
+
+  // Test non-destructive intersection.
+  r0 = rold = RANGE1 (10, 20);
+  ASSERT_TRUE (r0.Intersect_p (RANGE1 (15, 30)));
+  ASSERT_TRUE (r0 == rold);
+}
+
+} // namespace selftest
+#endif // CHECKING_P
diff --git a/gcc/range.h b/gcc/range.h
new file mode 100644
index 0000000..2a2ea06
--- /dev/null
+++ b/gcc/range.h
@@ -0,0 +1,111 @@ 
+/* 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
+#define MAX_RANGES	6
+
+typedef class irange *irange_p;
+enum irange_type { RANGE_PLAIN, RANGE_INVERT };
+
+class GTY(()) irange
+{
+ private:
+  bool overflow;
+  size_t n;
+  void prepend (wide_int x, wide_int y);
+  void append (wide_int x, wide_int y);
+  void remove (unsigned i, unsigned j);
+  void canonicalize ();
+  /* This is stupid.  These two should be private, but the GTY
+     machinery can't look inside an irange.  */
+ public:
+  tree type;
+  wide_int bounds[MAX_RANGES];
+
+public:
+  irange () { type = NULL_TREE; n = 0; }
+  irange (tree t);
+  irange (tree t, wide_int lbound, wide_int ubound,
+	  irange_type rt = RANGE_PLAIN);
+  irange (const irange &r);
+
+  void set_range (tree t);
+  void set_range (tree t, wide_int lbound, wide_int ubound,
+		  irange_type rt = RANGE_PLAIN);
+
+  bool overflow_p () { return overflow && !TYPE_OVERFLOW_WRAPS (type); }
+  void set_overflow () { overflow = true; }
+  void clear_overflow () { overflow = false; }
+
+  unsigned num_ranges () { return n / 2; }
+  wide_int lower_bound () const { return bounds[0]; }
+  wide_int lower_bound (unsigned index);
+  wide_int upper_bound () const { return bounds[n - 1]; }
+  wide_int upper_bound (unsigned index);
+
+  void remove_range (unsigned i) { remove (i, i + 1); }
+  void clear () { n = 0; }
+  void clear (tree t) { type = t; n = 0; overflow = false; }
+  bool empty_p () const { return !n; }
+  bool range_for_type_p () const;
+  bool simple_range_p () const { return n == 2; }
+
+  void dump ();
+  void dump (pretty_printer *pp);
+  void dump (FILE *);
+
+  bool valid_p ();
+  void cast (tree type);
+  bool contains_p (wide_int element);
+  bool contains_p (tree);
+
+  tree get_type () { return type; }
+
+  irange& operator= (const irange &r);
+  irange& operator= (tree t);
+
+  bool operator== (const irange &r) const;
+  bool operator!= (const irange &r) const { return !(*this == r); }
+
+  void Union (wide_int x, wide_int y);
+  bool Union (const irange &r);
+  bool Union (const irange &r1, const irange &r2);
+
+  // THIS = THIS ^ [X,Y].  Return TRUE if result is non-empty.
+  bool Intersect (wide_int x, wide_int y, bool readonly = false);
+  // THIS = THIS ^ R.  Return TRUE if result is non-empty.
+  bool Intersect (const irange &r, bool readonly = false);
+  // THIS = R1 ^ R2.  Return TRUE if result is non-empty.
+  bool Intersect (const irange &r1, const irange &r2, bool readonly = false);
+  // Return TRUE if THIS ^ R will be non-empty.
+  bool Intersect_p (const irange &r)
+    { return Intersect (r, /*readonly=*/true); }
+
+  bool Not ();
+  bool Not (const irange& r);
+};
+
+void range_zero (irange_p r, tree type);
+void range_one (irange_p r, tree type);
+bool range_non_zero (irange_p r, tree type);
+void range_positives (irange_p r, tree type, unsigned int);
+
+#endif /* GCC_RANGE_H */
diff --git a/gcc/selftest.h b/gcc/selftest.h
index dad53e9..e15cb07 100644
--- a/gcc/selftest.h
+++ b/gcc/selftest.h
@@ -196,6 +196,7 @@  extern void tree_c_tests ();
 extern void tree_cfg_c_tests ();
 extern void vec_c_tests ();
 extern void wide_int_cc_tests ();
+extern void irange_tests ();
 
 extern int num_passes;
 
diff --git a/gcc/ssa.h b/gcc/ssa.h
index 4bc6b3f..f84d6e8 100644
--- a/gcc/ssa.h
+++ b/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" 
diff --git a/gcc/tree-core.h b/gcc/tree-core.h
index ea73477..139e328 100644
--- a/gcc/tree-core.h
+++ b/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;
 struct die_struct;
 
 
@@ -1043,9 +1043,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
 
@@ -1416,11 +1413,15 @@  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 *range_info;
   } GTY ((desc ("%1.typed.type ?" \
 		"!POINTER_TYPE_P (TREE_TYPE ((tree)&%1)) : 2"))) info;
 
+  /* For non-pointer types, this specifies a mask for the bits that
+     are known to be set.  */
+  struct nonzero_bits_def *nonzero_bits;
+
   /* Immediate uses list for this SSA_NAME.  */
   struct ssa_use_operand_t imm_uses;
 };
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index 95f65b0..f218d05 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -3332,7 +3332,7 @@  iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step)
     base_min = base_max = 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;
@@ -3341,7 +3341,7 @@  iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step)
     step_min = step_max = 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;
diff --git a/gcc/tree-ssa-copy.c b/gcc/tree-ssa-copy.c
index 9f0fe54..7c02148 100644
--- a/gcc/tree-ssa-copy.c
+++ b/gcc/tree-ssa-copy.c
@@ -545,8 +545,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),
+					   SSA_NAME_NONZERO_BITS (var));
 	}
     }
 
diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
index c0e06bb..d7fb66f 100644
--- a/gcc/tree-ssa-loop-im.c
+++ b/gcc/tree-ssa-loop-im.c
@@ -1182,6 +1182,7 @@  move_computations_worker (basic_block bb)
 	{
 	  tree lhs = gimple_assign_lhs (new_stmt);
 	  SSA_NAME_RANGE_INFO (lhs) = NULL;
+	  SSA_NAME_NONZERO_BITS (lhs) = NULL;
 	}
       gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
       remove_phi_node (&bsi, false);
@@ -1251,6 +1252,7 @@  move_computations_worker (basic_block bb)
 	{
 	  tree lhs = gimple_get_lhs (stmt);
 	  SSA_NAME_RANGE_INFO (lhs) = NULL;
+	  SSA_NAME_NONZERO_BITS (lhs) = NULL;
 	}
       /* In case this is a stmt that is not unconditionally executed
          when the target loop header is executed and the stmt may
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index e67cd93..338efc4 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -225,7 +225,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);
@@ -347,8 +347,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))
@@ -368,7 +366,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) != NULL;
       /* 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))
@@ -376,12 +375,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;
 		}
@@ -395,7 +393,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;
 		    }
 		}
@@ -403,17 +401,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;
@@ -3140,7 +3138,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 (high, max))
 	base = wide_int_to_tree (unsigned_type, max);
@@ -3158,7 +3156,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, low))
 	base = wide_int_to_tree (unsigned_type, min);
@@ -4397,7 +4395,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;
@@ -4408,8 +4405,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
diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c
index b652361..43385a7 100644
--- a/gcc/tree-ssa-phiopt.c
+++ b/gcc/tree-ssa-phiopt.c
@@ -1063,13 +1063,14 @@  value_replacement (basic_block cond_bb, basic_block middle_bb,
 	     <bb 4>:
 	     # u_3 = PHI <u_6(3), 4294967295(2)>  */
 	  SSA_NAME_RANGE_INFO (lhs) = NULL;
+	  SSA_NAME_NONZERO_BITS (lhs) = NULL;
 	  /* If available, we can use VR of phi result at least.  */
 	  tree phires = gimple_phi_result (phi);
-	  struct range_info_def *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);
+	  if (irange *phires_range_info = SSA_NAME_RANGE_INFO (phires))
+	    {
+	      struct nonzero_bits_def *nzb = SSA_NAME_NONZERO_BITS (phires);
+	      duplicate_ssa_name_range_info (lhs, phires_range_info, nzb);
+	    }
 	}
       gimple_stmt_iterator gsi_from = gsi_for_stmt (assign);
       gsi_move_before (&gsi_from, &gsi);
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 2a431c9..5e16dfc 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -3107,12 +3107,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),
@@ -4326,8 +4325,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),
+					       VN_INFO_NONZERO_BITS (lhs));
 	    }
 
 	  /* Inhibit the use of an inserted PHI on a loop header when
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index c140c35..7e94172 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -3351,12 +3351,11 @@  set_ssa_val_to (tree from, tree to)
 		  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)->nonzero_bits = SSA_NAME_NONZERO_BITS (to);
 		    }
 		  /* Use that from the dominator.  */
 		  SSA_NAME_RANGE_INFO (to) = SSA_NAME_RANGE_INFO (from);
-		  SSA_NAME_ANTI_RANGE_P (to) = SSA_NAME_ANTI_RANGE_P (from);
+		  SSA_NAME_NONZERO_BITS (to) = SSA_NAME_NONZERO_BITS (from);
 		}
 	      else
 		{
@@ -3364,12 +3363,12 @@  set_ssa_val_to (tree from, tree to)
 		  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)->nonzero_bits = SSA_NAME_NONZERO_BITS (to);
 		    }
 		  /* Rather than allocating memory and unioning the info
 		     just clear it.  */
 		  SSA_NAME_RANGE_INFO (to) = NULL;
+		  SSA_NAME_NONZERO_BITS (to) = NULL;
 		}
 	    }
 	  else if (POINTER_TYPE_P (TREE_TYPE (to))
@@ -4618,8 +4617,7 @@  scc_vn_restore_ssa_info (void)
 		   && 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_NONZERO_BITS (name) = VN_INFO (name)->nonzero_bits;
 	    }
 	}
     }
diff --git a/gcc/tree-ssa-sccvn.h b/gcc/tree-ssa-sccvn.h
index 77d0183..4b1557d 100644
--- a/gcc/tree-ssa-sccvn.h
+++ b/gcc/tree-ssa-sccvn.h
@@ -182,6 +182,9 @@  typedef struct vn_ssa_aux
   /* Saved SSA name info.  */
   tree_ssa_name::ssa_name_info_type info;
 
+  /* Saved SSA name nonzero bits info.  */
+  struct nonzero_bits_def *nonzero_bits;
+
   /* Unique identifier that all expressions with the same value have. */
   unsigned int value_id;
 
@@ -201,9 +204,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 };
@@ -262,7 +262,7 @@  vn_valueize (tree name)
 
 /* Get at the original range info for NAME.  */
 
-inline range_info_def *
+inline irange *
 VN_INFO_RANGE_INFO (tree name)
 {
   return (VN_INFO (name)->info.range_info
@@ -270,22 +270,14 @@  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.  */
+/* Get at the original nonzero bits info for NAME.  */
 
-inline value_range_type
-VN_INFO_RANGE_TYPE (tree name)
+inline struct nonzero_bits_def *
+VN_INFO_NONZERO_BITS (tree name)
 {
-  return VN_INFO_ANTI_RANGE_P (name) ? VR_ANTI_RANGE : VR_RANGE;
+  return (VN_INFO (name)->nonzero_bits
+	  ? VN_INFO (name)->nonzero_bits
+	  : SSA_NAME_NONZERO_BITS (name));
 }
 
 /* Get at the original pointer info for NAME.  */
diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c
index 353c7b1..fd016d0 100644
--- a/gcc/tree-ssanames.c
+++ b/gcc/tree-ssanames.c
@@ -307,7 +307,10 @@  make_ssa_name_fn (struct function *fn, tree var, gimple *stmt,
   if (POINTER_TYPE_P (TREE_TYPE (t)))
     SSA_NAME_PTR_INFO (t) = NULL;
   else
-    SSA_NAME_RANGE_INFO (t) = NULL;
+    {
+      SSA_NAME_RANGE_INFO (t) = NULL;
+      SSA_NAME_NONZERO_BITS (t) = NULL;
+    }
 
   SSA_NAME_IN_FREE_LIST (t) = 0;
   SSA_NAME_IS_DEFAULT_DEF (t) = 0;
@@ -328,59 +331,66 @@  set_range_info (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 *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 = static_cast<irange *> (ggc_internal_alloc (sizeof (irange)));
       SSA_NAME_RANGE_INFO (name) = ri;
-      ri->set_nonzero_bits (wi::shwi (-1, precision));
+
+      size_t size = (sizeof (nonzero_bits_def)
+		     + trailing_wide_ints <1>::extra_size (precision));
+      SSA_NAME_NONZERO_BITS (name)
+	= static_cast<nonzero_bits_def *> (ggc_internal_alloc (size));
+      SSA_NAME_NONZERO_BITS (name)->ints.set_precision (precision);
+      SSA_NAME_NONZERO_BITS (name)->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);
+  gcc_assert (SSA_NAME_NONZERO_BITS (name) != NULL);
 
-  /* Set the values.  */
-  ri->set_min (min);
-  ri->set_max (max);
+  signop sign = TYPE_SIGN (TREE_TYPE (name));
+  ri->set_range (TREE_TYPE (name),
+		 wide_int::from (min, precision, sign),
+		 wide_int::from (max, precision, sign),
+		 range_type == VR_ANTI_RANGE ? RANGE_INVERT : RANGE_PLAIN);
 
   /* 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));
+      wide_int nzb = SSA_NAME_NONZERO_BITS (name)->get_nonzero_bits ();
+      SSA_NAME_NONZERO_BITS (name)->set_nonzero_bits (nzb & (min | xorv));
     }
 }
 
 
-/* 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 the range and sets MIN, MAX accordingly.  If no range
+   information is available, returns NULL and MIN, MAX is
+   untouched.  */
 
-enum value_range_type
+irange *
 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);
+  irange *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.  */
+  // FIXME: ?? Do we need this precision stuff ??
   if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name)))
 	      > 2 * HOST_BITS_PER_WIDE_INT))
-    return VR_VARYING;
+    return NULL;
 
-  *min = ri->get_min ();
-  *max = ri->get_max ();
-  return SSA_NAME_RANGE_TYPE (name);
+  gcc_assert (ri->valid_p ());
+  *min = ri->lower_bound ();
+  *max = ri->upper_bound ();
+  return ri;
 }
 
 /* Set nonnull attribute to pointer NAME.  */
@@ -422,8 +432,7 @@  set_nonzero_bits (tree name, const wide_int_ref &mask)
     set_range_info (name, VR_RANGE,
 		    TYPE_MIN_VALUE (TREE_TYPE (name)),
 		    TYPE_MAX_VALUE (TREE_TYPE (name)));
-  range_info_def *ri = SSA_NAME_RANGE_INFO (name);
-  ri->set_nonzero_bits (mask);
+  SSA_NAME_NONZERO_BITS (name)->set_nonzero_bits (mask);
 }
 
 /* Return a widest_int with potentially non-zero bits in SSA_NAME
@@ -442,11 +451,14 @@  get_nonzero_bits (const_tree name)
       return wi::shwi (-1, precision);
     }
 
-  range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+  irange *ri = SSA_NAME_RANGE_INFO (name);
   if (!ri)
-    return wi::shwi (-1, precision);
+    {
+      gcc_assert (!SSA_NAME_NONZERO_BITS (name));
+      return wi::shwi (-1, precision);
+    }
 
-  return ri->get_nonzero_bits ();
+  return SSA_NAME_NONZERO_BITS (name)->get_nonzero_bits ();
 }
 
 /* Return TRUE is OP, an SSA_NAME has a range of values [0..1], false
@@ -676,28 +688,44 @@  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 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 *range_info,
+			       struct nonzero_bits_def *nonzero_bits)
 {
-  struct range_info_def *new_range_info;
-
   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
   gcc_assert (!SSA_NAME_RANGE_INFO (name));
+  gcc_assert (!SSA_NAME_NONZERO_BITS (name));
 
   if (!range_info)
     return;
 
+  /* Copy the non-zero bits information over.  */
   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);
+  size_t size = (sizeof (nonzero_bits_def)
+		 + trailing_wide_ints <1>::extra_size (precision));
+  struct nonzero_bits_def *nzb
+    = static_cast<nonzero_bits_def *> (ggc_internal_alloc (size));
+  memcpy (nzb, nonzero_bits, size);
+  SSA_NAME_NONZERO_BITS (name) = nzb;
+
+  /* Copy the range info over.  */
+  size = sizeof (irange);
+  irange *new_range_info = static_cast<irange *> (ggc_internal_alloc (size));
+  *new_range_info = *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) != range_info->get_type ())
+    range_info->cast (TREE_TYPE (name));
 
-  gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE);
-  SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE);
   SSA_NAME_RANGE_INFO (name) = new_range_info;
 }
 
@@ -719,11 +747,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 *old_range_info = SSA_NAME_RANGE_INFO (name);
+      struct nonzero_bits_def *old_nzb = SSA_NAME_NONZERO_BITS (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, old_nzb);
     }
 
   return new_name;
@@ -743,7 +771,10 @@  reset_flow_sensitive_info (tree name)
 	mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (name));
     }
   else
-    SSA_NAME_RANGE_INFO (name) = NULL;
+    {
+      SSA_NAME_RANGE_INFO (name) = NULL;
+      SSA_NAME_NONZERO_BITS (name) = NULL;
+    }
 }
 
 /* Clear all flow sensitive data from all statements and PHI definitions
diff --git a/gcc/tree-ssanames.h b/gcc/tree-ssanames.h
index 9a18394..cdab953 100644
--- a/gcc/tree-ssanames.h
+++ b/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.  */
-
-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;
+/* Used bits information for SSA_NAMEs representing non-pointer variables.  */
+
+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;
 };
 
 
@@ -70,8 +68,8 @@  struct GTY ((variable_size)) range_info_def {
 extern void set_range_info (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 irange *get_range_info (const_tree, wide_int *,
+			       wide_int *);
 extern void set_nonzero_bits (tree, const wide_int_ref &);
 extern wide_int get_nonzero_bits (const_tree);
 extern bool ssa_name_has_boolean_range (tree);
@@ -95,8 +93,8 @@  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 *,
+					   struct nonzero_bits_def *);
 extern void reset_flow_sensitive_info (tree);
 extern void reset_flow_sensitive_info_in_bb (basic_block);
 extern void release_defs (gimple *);
diff --git a/gcc/tree-vect-patterns.c b/gcc/tree-vect-patterns.c
index 39f0133..05bf7a3 100644
--- a/gcc/tree-vect-patterns.c
+++ b/gcc/tree-vect-patterns.c
@@ -2894,7 +2894,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;
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 716a7c2..b187446 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -498,6 +498,69 @@  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)
+{
+  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_ranges () == 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 instnace, ipa-prop.c.  */
+
+enum value_range_type
+get_range_info_as_value_range (const_tree ssa, wide_int *min, wide_int *max)
+{
+  irange *ri = SSA_NAME_RANGE_INFO (ssa);
+  if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (ssa)))
+              > 2 * HOST_BITS_PER_WIDE_INT))
+    return VR_VARYING;
+
+  if (irange_is_anti_range (*ri))
+    {
+      irange tmp (*ri);
+      tmp.Not ();
+      gcc_assert (!tmp.overflow_p ());
+      if (tmp.num_ranges () != 1)
+       {
+         fprintf (stderr, "Inverse of anti range does not have 2 elements.\n");
+         fprintf (stderr, "Type: ");
+         debug_generic_stmt (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 value range information for VAR.
 
@@ -555,7 +618,8 @@  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),
@@ -637,7 +701,7 @@  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;
@@ -6887,9 +6951,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 (bb, var);
 		  }
 	      }
@@ -9903,7 +9968,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)));
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index ef2c68a..99750cd 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -57,3 +57,5 @@  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);
diff --git a/gcc/tree.c b/gcc/tree.c
index db31620..cd4ae68 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -14316,7 +14316,10 @@  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)
+  irange *ir;
+  while (!(ir = get_range_info (arg, &arg_min, &arg_max))
+	 || (ir->lower_bound () == TYPE_MIN_VALUE (TREE_TYPE (arg))
+	     && ir->upper_bound () == TYPE_MAX_VALUE (TREE_TYPE (arg))))
     {
       gimple *g = SSA_NAME_DEF_STMT (arg);
       if (is_gimple_assign (g)
@@ -14326,6 +14329,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;
diff --git a/gcc/tree.h b/gcc/tree.h
index c6e883c..1878f41 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -1740,18 +1740,19 @@  extern void protected_set_expr_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
 
+/* Known used bits for a non pointer-type variable.
+
+   Actual wide_int value is accessed with:
+     SSA_NAME_NONZERO_BITS(x)->get_nonzero_bits()
+   and set with:
+     SSA_NAME_NONZERO_BITS(x)->set_nonzero_bits().  */
+#define SSA_NAME_NONZERO_BITS(N) \
+  SSA_NAME_CHECK (N)->ssa_name.nonzero_bits
+
 /* Return the immediate_use information for an SSA_NAME. */
 #define SSA_NAME_IMM_USE_NODE(NODE) SSA_NAME_CHECK (NODE)->ssa_name.imm_uses