SSA range class and removal of VR_ANTI_RANGEs

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.

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

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

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

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

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

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

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

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

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

>> --- /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

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

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

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.

..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

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
>

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

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.

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.

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.

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

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.

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

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

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

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

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

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

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

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.

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

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

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
>