Re: [PATCH] irange_pool class

[Andrew MacLeod <amacleod@redhat.com>]

On 9/18/20 4:35 PM, Martin Sebor wrote:
> On 9/18/20 11:36 AM, Andrew MacLeod wrote:
>> On
>>
>> it works exactly like one would expect a simple allocator to work.. 
>> as long as the allcoator is "live", its allocations are live.  once 
>> it is destructed, all the memory it manages is freed..    It purpose 
>> is to avoid having to walk/find everything that was allocated so it 
>> can be freed.
>>
>> I'll give you the use case from the ranger. in fact, it *is* the 
>> ranger's allocator, exposed for other passes to use.
>>
>> Ranger uses the allocator to store the live-on-entry ranges for 
>> ssa-names.  Each basic block has a vec<irange *> allocated as needed 
>> which is indexed by ssa-name.
>>
>> int_range_max is passed to range_on_entry() to go off and find the 
>> range..  when it comes back, it could have 0-255 subranges,. it 
>> doesnt matter.
>> we call allocate(range) to get a pointer to an efficent copy and 
>> store it in the vector for the ssa name in that block.
>> If the updater later discovers that the range can be made more 
>> accurate, it checks if the new range fits in the memory allocated and 
>> if it does, simply copies.  if it doesnt fit, then it frees the old 
>> hunk, and allocates  a new one and stores that.
>>
>> The ranger creates an allocator when it starts up, and then frees it 
>> when its being destructed.  Thats the life of the on-entry cache, so 
>> thats matches the life of the allocator..
>>
>> I don't understand the proxy comment, or why one would ever want to 
>> copy the allocator itself? or why would you derive from irange? why 
>> cant you just create an allocator when the pass starts, use it when 
>> you need to store a range, and then let it go at the end of the pass 
>> with the other memory?
>
> The int_range template is derived from irange and provides the array
> of trees that the irange works with.  The pool also provides memory
> for iranges and effectively returns objects "derived" from irange
> (they're bigger than it is).
>
> What I meant by proxy is a substitute class each of whose objects
> stands in for a single instance of int_range<N> where N is
> a runtime value.   There's no class like that.
>

no, but that doesnt serve a lot of purpose either.     you can call    
allocator.allocate(N) which is effectively that... ?

>>
>> its mean to be a convenient way to get a range allocated to store via 
>> a pointer. nothing more.  if you have more complex needs,then you 
>> need to manage those needs.  The ranger manages the live on entry 
>> vectors separately from the ranges..
>
> What I'm thinking of is actually more basic than that: an irange
> class with a runtime number of subranges, one that can be either
> directly stored in a container like vec:
>
>   vec<dynamic_irange>
>
> where dynamic_range is such a class, or that can be a member of
> a class that's stored in it.  I expect that will be the default
> use case for the passes that walk the IL looking for the sizes
> and offsets into the objects, accesses to which they validate.
> This can be done with int_range<N> for constant N but not with
> irange because it doesn't own the memory it works with).
>
> To illustrate what I mean here's a completely untested outline
> of a plain-Jane dynamic_irange class (it won't compile because
> it accesses private and protected members of irange, but it
> should give you the idea):
>
>   class dynamic_irange: public irange
>   {
>   public:
>     dynamic_irange (unsigned num_pairs)
>       : irange (new tree[num_pairs], num_pairs) { }
>
>     dynamic_irange (const dynamic_irange &rhs)
>       : irange (new tree[rhs.m_max_ranges], rhs.m_num_ranges)
>     { irange::operator= (rhs); }
>
>     dynamic_irange (dynamic_irange &&rhs)
>       : irange (rhs.m_base, rhs.m_max_ranges)
>     { rhs.m_base = 0; }
>
>     dynamic_irange& operator= (const dynamic_irange &rhs)
>     {
>       if (this != &rhs)
>         {
>           delete[] m_base;
>           m_base = new tree[rhs.m_max_ranges];
>           m_num_ranges = rhs.m_num_ranges;
>           irange::operator= (rhs);
>         }
>       return *this;
>     }
>     ~dynamic_irange () { delete[] m_base; }
>   };
>
> A more fancy class would be parameterized on an Allocator policy
> that it would allocate memory with, much like C++ standard classes
> do.  That would let you define an obstack-based allocator class to
> use the way you need, as well and any others.  (Providing
> the allocator as a template argument to just the ctor as opposed
> to the whole class itself would make different "instances"
> interchangeable for one another.)
>
> Martin

  We had a dynamic sized irange, I told aldy to kill it off and we 
replaced it with int_range_max with 255 ranges because the combo of 
int_range_max for calculating and allocation to store seemed to solve 
all the problems with far less allocation overhead, and wasnt 
particularly onerous.

int_range_max use to have a small vector of something like 5 pairs. If  
a range was being created and we needed more by accessing elements 
higher than that, , it would allocate a hunk of memory to be able to 
handle it, plus a little extra buffer space, and point to that instead.  
So it was a dynamically size  int_range_max that managed it own memory.  
we found that in practice, the pairing of the current int_range-max and 
the allocation pool was far more efficient 99% of the time.  so we just 
eliminated it.

Something like that could certainly be revived...  but most of the time 
it doesnt seem necessary.  Generally, you need to ask for a range and 
then store it.  Ask for it with int_range_max, and store it with the 
allocator if you are goignto need a lot fo them.  so instead of

range_of_expr (vec[x], name..)

you do

int_range_max m;
range_of_expr (m, name)
vec[x] = allocato(m);

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.

Doesnt mean we cant reproduce the dynamically sized one, but it requires 
either  a) some hacking of the irange class to know about the derived 
dynamically sized one so it can do a resize,  or b) introduction of 
virtual functions to the class so it can automatically check if it needs 
to grow.   neither thrills me which is why we are with int_range_max and 
an allocator.

Andfrew