Re: [PATCH] irange_pool class

[Andrew MacLeod <amacleod@redhat.com>]

On 9/19/20 4:32 PM, Martin Sebor wrote:
> On 9/18/20 3:09 PM, Andrew MacLeod wrote:
>> On 9/18/20 4:35 PM, Martin Sebor wrote:
>> Do you really need 6 or 10 subranges to find out the answer to the 
>> questions you are looking for?  most of the time, 2 or 3 pairs 
>> carries all the information anyone needs and its efficient switches 
>> are the biggest beneficiary of the multiple ranges, allowing us to be 
>> quite precise on what reaches the interior of a case or the default.
>>
>> the next question is, how many of these do you need?  The range is 
>> doing it with there allocator because it could in theory have #BB * 
>> #SSA_NAMES, which could be a lot.    if you have just a single or 2 
>> vectors over ssa-names, and that is sparsley filled, just use 
>> int-range-max.
>
> The use case I'm thinking of would have an irange of some size for
> every decl or result of an allocation call accessed in a function,
> plus another irange for every SSA_NAME that's an object pointer.
> The size of the first irange would be that of the allocation
> argument in the first case.  In the second case it would be
> the combined range of the offsets the pointer from whatever it
> points to (e.g., in p0 = &x; p1 = p0 + i; p2 = p1 + j; p2's
> offset range would be Ri + Rj where R is the value range of i
> or j.
>
> It probably doesn't makes sense to keep track of 255 subranges
> (or even many more than 5) but in compliance with the guidance
> in the irange best practices document to write code for [as if]
> infinite subranges, the data structures should be free of any
> hardwired limit.  So I envision I might have something like
> a pair of dynamic_range members in each of these objects (along
> with the SSA_NAME and other stuff), and some runtime parameter
> to cap the number of subranges to some reasonable limit, merging
> those in excess of it.
>

Furthermore, there are 2 other things at play.

1)  The nature of the ranger is that it stores everything, and you just 
need to ask for the range.  if its an ssa_name, unless you are adjusting 
the range somehow, the ranger is already storing it, so all you need to 
do is ask for it when you want it, and its readily available any time.
    Given this, *most* of the time passes shouldn't need to actually 
store a range.. you just retrieve it when you want it.  I do not believe 
any of the passes Aldy converted required storing ranges. However, I do 
recognize there are going to be times when a pass may need to store or 
associate something else with  a range, thus we exposed the 
functionality earlier than i was going to.

2) We have taken a significant performance hit by converting irange to 
be represented with trees rather than the original wide_int 
implementation.  At some point (maybe sooner than later) , Id like to go 
back to the wide int internal representation.  When we do so, storage 
needs will go up considerably.  Up until the "merge" of value_range and 
irange to trees, we actually had another object called irange_storage 
which was a memory efficient representation of ranges for longer term 
storage.
   If/when we were to switch back to wide_int, the pool allocator would 
then return an irange_storage object rather than a irange *...    It 
would not be ideal  for an irange * or any kind of int_range<N> to be 
kept in memory by any pass.. but rather stored to memory thru  the 
irange_storage class.

the basic principle we used was was to use int_range_max to load the 
range from storage, manipulate and get results, than store back thru the 
irange storage class. We have for the moment dropped the irange_storage 
class since it would simply be a typedef of an "irange *" today... and 
so it just looked like noise with no way to enforce a behaviour.

so I would encourage use of the allocator for any kind of longer term 
storage if its really needed, as it will be a much simpler translation 
if/when we make the switch back.

Most passes that need storage should surely be able to create an 
allocator for the pass and make use of it.   The pass has to create a 
ranger, so it'd have the same scope as the ranger.   we could 
potentially  expose allocation from the rangers own allocator, but that 
shouldnt be necessary,. if you can create a ranger, you can create an 
allocator if it is needed

Andrew