Re: [PATCH] irange_pool class
On 9/18/20 1:03 PM, Aldy Hernandez wrote: On 9/18/20 6:42 PM, Andrew MacLeod wrote: On 9/18/20 8:28 AM, David Malcolm wrote:I think of a "pool allocator" as something that makes a small number of large allocation under the covers, and then uses that to serve large numbers of fixed sized small allocations and deallocations with O(1) using a free list. Ah, I didn't know pool had a different meaning. See e.g. gcc/alloc-pool.h The name originated when the original v1 version was based on using alloc-pool.h. when we went to varying sizes, we switched to and obstack implementation and never changed the name. <...> I think it would be clearer to name this "irange_obstack", or somesuch. I'd prefer something more generic. We don't want to tie the name of the allocator to the underlying implementation. What if we later change to malloc? We'd have to change the name to irange_malloc. irange_allocator? Or is there something more generically appropriate here? How about "irange_bump_allocator?" Rather long, but it expresses the "irange_allocator" is sufficient . The consumer should not care what the implementation is, and we may decide to implement it differently down the road. So I don't want to imply something specific in the name or we'd have to change it again. Updated patch attached. Aldy This is OK btw, Andrew
Re: [PATCH] irange_pool class
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 = 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 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
Re: [PATCH] irange_pool class
On 9/19/20 10: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:
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 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 where N is
a runtime value. There's no class like that.
[Just to be clear, I don't meant for this discussion to hold up
the patch if you need the pool internally. Anothert class like
the one I propose can be added later if necessary.]
no, but that doesnt serve a lot of purpose either. you can call
allocator.allocate(N) which is effectively that... ?
Yes, but the allocator object isn't always conveniently accessible.
Imagine needing to allocate a dynamically sized irange is in a copy
ctor of some class that's stored in a vec, as the vec is being
resized. The allocator would need to be a global pointer. That's
of course possible but not the most elegant design.
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
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 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 )
: irange (new tree[rhs.m_max_ranges], rhs.m_num_ranges)
{ irange::operator= (rhs); }
dynamic_irange (dynamic_irange &)
: irange (rhs.m_base, rhs.m_max_ranges)
{ rhs.m_base = 0; }
dynamic_irange& operator= (const dynamic_irange )
{
if (this != )
{
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
Re: [PATCH] irange_pool class
On 9/19/20 4:32 PM, Martin Sebor wrote: On 9/18/20 3:09 PM, Andrew MacLeod wrote: O What I meant by proxy is a substitute class each of whose objects stands in for a single instance of int_range where N is a runtime value. There's no class like that. [Just to be clear, I don't meant for this discussion to hold up the patch if you need the pool internally. Anothert class like the one I propose can be added later if necessary.] It won't :-) no, but that doesnt serve a lot of purpose either. you can call allocator.allocate(N) which is effectively that... ? Yes, but the allocator object isn't always conveniently accessible. Imagine needing to allocate a dynamically sized irange is in a copy ctor of some class that's stored in a vec, as the vec is being resized. The allocator would need to be a global pointer. That's of course possible but not the most elegant design. I am now imagining an overly complex c++ system that doesnt really fit with GCC:-) I dont think GCCs vec could deal with that model. when thats a reality, we'll deal with it. for now, Im not overly concerned. If we reintroduce a dynamic object, we'll worry about it then, and make sure a dynamic object can be associated with an allocation object.. <> 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. 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 = 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 I think you are interpreting that guidance too literally. It would perhaps be better to word it more in line with what is practical . If what you are interested in is the upper and lower limit, then 1 or 2 sub-ranges is plenty. you really dont care about the middle ranges if you are a switch operation, then infinite might be appropriate. pointers tracking null and non-null? int_range<1> is likely enough. you are dealing with offsets.. you really dont care about those middle sub-ranges. really. I see little benefit for you from that. You benefit for you is the more accurate/easy to use ranges. for now, i would simply use an
Re: [PATCH] irange_pool class
On 9/18/20 3:09 PM, Andrew MacLeod wrote:
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 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 where N is
a runtime value. There's no class like that.
[Just to be clear, I don't meant for this discussion to hold up
the patch if you need the pool internally. Anothert class like
the one I propose can be added later if necessary.]
no, but that doesnt serve a lot of purpose either. you can call
allocator.allocate(N) which is effectively that... ?
Yes, but the allocator object isn't always conveniently accessible.
Imagine needing to allocate a dynamically sized irange is in a copy
ctor of some class that's stored in a vec, as the vec is being
resized. The allocator would need to be a global pointer. That's
of course possible but not the most elegant design.
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
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 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 )
: irange (new tree[rhs.m_max_ranges], rhs.m_num_ranges)
{ irange::operator= (rhs); }
dynamic_irange (dynamic_irange &)
: irange (rhs.m_base, rhs.m_max_ranges)
{ rhs.m_base = 0; }
dynamic_irange& operator= (const dynamic_irange )
{
if (this != )
{
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
Re: [PATCH] irange_pool class
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 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 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
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 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 )
: irange (new tree[rhs.m_max_ranges], rhs.m_num_ranges)
{ irange::operator= (rhs); }
dynamic_irange (dynamic_irange &)
: irange (rhs.m_base, rhs.m_max_ranges)
{ rhs.m_base = 0; }
dynamic_irange& operator= (const dynamic_irange )
{
if (this != )
{
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
Re: [PATCH] irange_pool class
On 9/18/20 11:36 AM, Andrew MacLeod wrote: On 9/18/20 1:07 PM, Martin Sebor wrote: On 9/18/20 8:10 AM, Aldy Hernandez via Gcc-patches wrote: On 9/18/20 2:28 PM, David Malcolm wrote: On Fri, 2020-09-18 at 07:49 +0200, Aldy Hernandez wrote: On 9/18/20 3:43 AM, David Malcolm wrote: On Thu, 2020-09-17 at 12:36 +0200, Aldy Hernandez via Gcc-patches wrote: This is the irange storage class. It is used to allocate the minimum amount of storage needed for a given irange. Storage is automatically freed at destruction. It is meant for long term storage, as opposed to int_range_max which is meant for intermediate temporary results on the stack. The general gist is: irange_pool pool; // Allocate an irange of 5 sub-ranges. irange *p = pool.allocate (5); // Allocate an irange of 3 sub-ranges. irange *q = pool.allocate (3); // Allocate an irange with as many sub-ranges as are currently // used in "some_other_range". irange *r = pool.allocate (some_other_range); FWIW my first thoughts reading this example were - "how do I deallocate these iranges?" and "do I need to call pool.deallocate on them, or is that done for me by the irange dtor?" Thus the description front and center of the header file: "Storage is automatically freed at destruction..." I think of a "pool allocator" as something that makes a small number of large allocation under the covers, and then uses that to serve large numbers of fixed sized small allocations and deallocations with O(1) using a free list. Ah, I didn't know pool had a different meaning. See e.g. gcc/alloc-pool.h [...] +// This is the irange storage class. It is used to allocate the +// minimum amount of storage needed for a given irange. Storage is +// automatically freed at destruction. "at destruction" of what object - the irange or the irange_pool? Reading the code, it turns out to be "at destruction of the irange_pool", and it turns out that irange_pool is an obstack under the covers (also called a "bump allocator") and thus, I believe, the lifetime of the irange instances is that of the storage instance. The sentence is talking about the storage class, so I thought it was obvious that the destruction we talk about is the storage class itself. I suppose if it isn't clear we could say: "Storage is automatically freed at destruction of the storage class." I think it would be clearer to name this "irange_obstack", or somesuch. I'd prefer something more generic. We don't want to tie the name of the allocator to the underlying implementation. What if we later change to malloc? We'd have to change the name to irange_malloc. irange_allocator? Or is there something more generically appropriate here? How about "irange_bump_allocator?" Rather long, but it expresses the key point that the irange instances coming out of it don't have independent lifetimes - their lifetimes are those of the allocator; the client code doesn't need to find and clean up all of those individual iranges, right? (assuming I'm reading the code correctly) (That name also avoids mentioning the implementation detail that it uses obstack). I'm sorry, but that's _really_ ugly. Surely irange_allocator can't be that confusing. A casual look at the header file would dispel all doubts. David's point abut different strategies was also in the back my mind but it took me a bit to formulate a question about the design. Is a pool of ranges with a fixed allocation policy the right design for long-term storage of irange objects? What are some example use cases? Here's one that comes to mind based on what I want to do in gimple-ssa-isolate-paths.c. I need to store irange instances as members of my own class, but I don't know how many subranges each instance might need to store (it depends on the IL). I store objects of this class a container (e.g., hash_map or set). I don't want to use int_range_max because that would be wasteful but I can't use the pool as a proxy because it's not copyable. So I either have to dynamically allocate the pool and store a pointer to it instead, in addition to the instances, or derive my own class from irange and manage the tree arrays myself. In both cases I'm adding a layer of memory management on top of what that the pool is there to provide. So the design doesn't seem very well suited for my use case. I don't mean this as an objection to the patch (I'm sure there's a use case I'm not thinking of), but more as a question. Martin I don't know why this is confusing... 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
Re: [PATCH] irange_pool class
On 9/18/20 1:07 PM, Martin Sebor wrote: On 9/18/20 8:10 AM, Aldy Hernandez via Gcc-patches wrote: On 9/18/20 2:28 PM, David Malcolm wrote: On Fri, 2020-09-18 at 07:49 +0200, Aldy Hernandez wrote: On 9/18/20 3:43 AM, David Malcolm wrote: On Thu, 2020-09-17 at 12:36 +0200, Aldy Hernandez via Gcc-patches wrote: This is the irange storage class. It is used to allocate the minimum amount of storage needed for a given irange. Storage is automatically freed at destruction. It is meant for long term storage, as opposed to int_range_max which is meant for intermediate temporary results on the stack. The general gist is: irange_pool pool; // Allocate an irange of 5 sub-ranges. irange *p = pool.allocate (5); // Allocate an irange of 3 sub-ranges. irange *q = pool.allocate (3); // Allocate an irange with as many sub-ranges as are currently // used in "some_other_range". irange *r = pool.allocate (some_other_range); FWIW my first thoughts reading this example were - "how do I deallocate these iranges?" and "do I need to call pool.deallocate on them, or is that done for me by the irange dtor?" Thus the description front and center of the header file: "Storage is automatically freed at destruction..." I think of a "pool allocator" as something that makes a small number of large allocation under the covers, and then uses that to serve large numbers of fixed sized small allocations and deallocations with O(1) using a free list. Ah, I didn't know pool had a different meaning. See e.g. gcc/alloc-pool.h [...] +// This is the irange storage class. It is used to allocate the +// minimum amount of storage needed for a given irange. Storage is +// automatically freed at destruction. "at destruction" of what object - the irange or the irange_pool? Reading the code, it turns out to be "at destruction of the irange_pool", and it turns out that irange_pool is an obstack under the covers (also called a "bump allocator") and thus, I believe, the lifetime of the irange instances is that of the storage instance. The sentence is talking about the storage class, so I thought it was obvious that the destruction we talk about is the storage class itself. I suppose if it isn't clear we could say: "Storage is automatically freed at destruction of the storage class." I think it would be clearer to name this "irange_obstack", or somesuch. I'd prefer something more generic. We don't want to tie the name of the allocator to the underlying implementation. What if we later change to malloc? We'd have to change the name to irange_malloc. irange_allocator? Or is there something more generically appropriate here? How about "irange_bump_allocator?" Rather long, but it expresses the key point that the irange instances coming out of it don't have independent lifetimes - their lifetimes are those of the allocator; the client code doesn't need to find and clean up all of those individual iranges, right? (assuming I'm reading the code correctly) (That name also avoids mentioning the implementation detail that it uses obstack). I'm sorry, but that's _really_ ugly. Surely irange_allocator can't be that confusing. A casual look at the header file would dispel all doubts. David's point abut different strategies was also in the back my mind but it took me a bit to formulate a question about the design. Is a pool of ranges with a fixed allocation policy the right design for long-term storage of irange objects? What are some example use cases? Here's one that comes to mind based on what I want to do in gimple-ssa-isolate-paths.c. I need to store irange instances as members of my own class, but I don't know how many subranges each instance might need to store (it depends on the IL). I store objects of this class a container (e.g., hash_map or set). I don't want to use int_range_max because that would be wasteful but I can't use the pool as a proxy because it's not copyable. So I either have to dynamically allocate the pool and store a pointer to it instead, in addition to the instances, or derive my own class from irange and manage the tree arrays myself. In both cases I'm adding a layer of memory management on top of what that the pool is there to provide. So the design doesn't seem very well suited for my use case. I don't mean this as an objection to the patch (I'm sure there's a use case I'm not thinking of), but more as a question. Martin I don't know why this is confusing... 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
Re: [PATCH] irange_pool class
On 9/18/20 8:10 AM, Aldy Hernandez via Gcc-patches wrote: On 9/18/20 2:28 PM, David Malcolm wrote: On Fri, 2020-09-18 at 07:49 +0200, Aldy Hernandez wrote: On 9/18/20 3:43 AM, David Malcolm wrote: On Thu, 2020-09-17 at 12:36 +0200, Aldy Hernandez via Gcc-patches wrote: This is the irange storage class. It is used to allocate the minimum amount of storage needed for a given irange. Storage is automatically freed at destruction. It is meant for long term storage, as opposed to int_range_max which is meant for intermediate temporary results on the stack. The general gist is: irange_pool pool; // Allocate an irange of 5 sub-ranges. irange *p = pool.allocate (5); // Allocate an irange of 3 sub-ranges. irange *q = pool.allocate (3); // Allocate an irange with as many sub-ranges as are currently // used in "some_other_range". irange *r = pool.allocate (some_other_range); FWIW my first thoughts reading this example were - "how do I deallocate these iranges?" and "do I need to call pool.deallocate on them, or is that done for me by the irange dtor?" Thus the description front and center of the header file: "Storage is automatically freed at destruction..." I think of a "pool allocator" as something that makes a small number of large allocation under the covers, and then uses that to serve large numbers of fixed sized small allocations and deallocations with O(1) using a free list. Ah, I didn't know pool had a different meaning. See e.g. gcc/alloc-pool.h [...] +// This is the irange storage class. It is used to allocate the +// minimum amount of storage needed for a given irange. Storage is +// automatically freed at destruction. "at destruction" of what object - the irange or the irange_pool? Reading the code, it turns out to be "at destruction of the irange_pool", and it turns out that irange_pool is an obstack under the covers (also called a "bump allocator") and thus, I believe, the lifetime of the irange instances is that of the storage instance. The sentence is talking about the storage class, so I thought it was obvious that the destruction we talk about is the storage class itself. I suppose if it isn't clear we could say: "Storage is automatically freed at destruction of the storage class." I think it would be clearer to name this "irange_obstack", or somesuch. I'd prefer something more generic. We don't want to tie the name of the allocator to the underlying implementation. What if we later change to malloc? We'd have to change the name to irange_malloc. irange_allocator? Or is there something more generically appropriate here? How about "irange_bump_allocator?" Rather long, but it expresses the key point that the irange instances coming out of it don't have independent lifetimes - their lifetimes are those of the allocator; the client code doesn't need to find and clean up all of those individual iranges, right? (assuming I'm reading the code correctly) (That name also avoids mentioning the implementation detail that it uses obstack). I'm sorry, but that's _really_ ugly. Surely irange_allocator can't be that confusing. A casual look at the header file would dispel all doubts. David's point abut different strategies was also in the back my mind but it took me a bit to formulate a question about the design. Is a pool of ranges with a fixed allocation policy the right design for long-term storage of irange objects? What are some example use cases? Here's one that comes to mind based on what I want to do in gimple-ssa-isolate-paths.c. I need to store irange instances as members of my own class, but I don't know how many subranges each instance might need to store (it depends on the IL). I store objects of this class a container (e.g., hash_map or set). I don't want to use int_range_max because that would be wasteful but I can't use the pool as a proxy because it's not copyable. So I either have to dynamically allocate the pool and store a pointer to it instead, in addition to the instances, or derive my own class from irange and manage the tree arrays myself. In both cases I'm adding a layer of memory management on top of what that the pool is there to provide. So the design doesn't seem very well suited for my use case. I don't mean this as an objection to the patch (I'm sure there's a use case I'm not thinking of), but more as a question. Martin Aldy Sorry if I'm nitpicking; I think my high level thought here is that we have various memory management strategies inside GCC (in no particular order): - garbage collection - explicit malloc/free - explicit new/delete - explicit new/delete backed by allocation pools - RAII - bump allocators aka obstacks and I like to be clear about what "owns" each object (responsibility for cleanup, lifetimes, etc) Hope this is constructive Dave
Re: [PATCH] irange_pool class
On 9/18/20 6:42 PM, Andrew MacLeod wrote:
On 9/18/20 8:28 AM, David Malcolm wrote:I think of a "pool allocator" as
something that makes a small
number of
large allocation under the covers, and then uses that to serve
large
numbers of fixed sized small allocations and deallocations with
O(1)
using a free list.
Ah, I didn't know pool had a different meaning.
See e.g. gcc/alloc-pool.h
The name originated when the original v1 version was based on using
alloc-pool.h. when we went to varying sizes, we switched to and obstack
implementation and never changed the name.
<...>
I think it would be clearer to name this "irange_obstack", or
somesuch.
I'd prefer something more generic. We don't want to tie the name of
the
allocator to the underlying implementation. What if we later change
to
malloc? We'd have to change the name to irange_malloc.
irange_allocator? Or is there something more generically appropriate
here?
How about "irange_bump_allocator?" Rather long, but it expresses the
"irange_allocator" is sufficient . The consumer should not care
what the implementation is, and we may decide to implement it
differently down the road. So I don't want to imply something specific
in the name or we'd have to change it again.
Updated patch attached.
Aldy
commit 343463f8887ab510503d9e230268963a299a84ef
Author: Aldy Hernandez
Date: Fri Sep 11 10:15:12 2020 +0200
irange_allocator class
This is the irange storage class. It is used to allocate the
minimum amount of storage needed for a given irange. Storage is
automatically freed at destruction of the storage class.
It is meant for long term storage, as opposed to int_range_max
which is meant for intermediate temporary results on the stack.
The general gist is:
irange_allocator alloc;
// Allocate an irange of 5 sub-ranges.
irange *p = alloc.allocate (5);
// Allocate an irange of 3 sub-ranges.
irange *q = alloc.allocate (3);
// Allocate an irange with as many sub-ranges as are currently
// used in "some_other_range".
irange *r = alloc.allocate (some_other_range);
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 8497791c7b3..c875e713d65 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -43,6 +43,7 @@ enum value_range_kind
class irange
{
+ friend class irange_allocator;
public:
// In-place setters.
void set (tree, tree, value_range_kind = VR_RANGE);
@@ -619,4 +620,68 @@ vrp_val_min (const_tree type)
return NULL_TREE;
}
+// This is the irange storage class. It is used to allocate the
+// minimum amount of storage needed for a given irange. Storage is
+// automatically freed at destruction of the storage class.
+//
+// It is meant for long term storage, as opposed to int_range_max
+// which is meant for intermediate temporary results on the stack.
+//
+// The newly allocated irange is initialized to the empty set
+// (undefined_p() is true).
+
+class irange_allocator
+{
+public:
+ irange_allocator ();
+ ~irange_allocator ();
+ // Return a new range with NUM_PAIRS.
+ irange *allocate (unsigned num_pairs);
+ // Return a copy of SRC with the minimum amount of sub-ranges needed
+ // to represent it.
+ irange *allocate (const irange );
+private:
+ DISABLE_COPY_AND_ASSIGN (irange_allocator);
+ struct obstack m_obstack;
+};
+
+inline
+irange_allocator::irange_allocator ()
+{
+ obstack_init (_obstack);
+}
+
+inline
+irange_allocator::~irange_allocator ()
+{
+ obstack_free (_obstack, NULL);
+}
+
+// Return a new range with NUM_PAIRS.
+
+inline irange *
+irange_allocator::allocate (unsigned num_pairs)
+{
+ // Never allocate 0 pairs.
+ // Don't allocate 1 either, or we get legacy value_range's.
+ if (num_pairs < 2)
+num_pairs = 2;
+
+ struct newir {
+irange range;
+tree mem[1];
+ };
+ size_t nbytes = (sizeof (newir) + sizeof (tree) * 2 * (num_pairs - 1));
+ struct newir *r = (newir *) obstack_alloc (_obstack, nbytes);
+ return new (r) irange (r->mem, num_pairs);
+}
+
+inline irange *
+irange_allocator::allocate (const irange )
+{
+ irange *r = allocate (src.num_pairs ());
+ *r = src;
+ return r;
+}
+
#endif // GCC_VALUE_RANGE_H
Re: [PATCH] irange_pool class
On 9/18/20 8:28 AM, David Malcolm wrote:I think of a "pool allocator" as something that makes a small number of large allocation under the covers, and then uses that to serve large numbers of fixed sized small allocations and deallocations with O(1) using a free list. Ah, I didn't know pool had a different meaning. See e.g. gcc/alloc-pool.h The name originated when the original v1 version was based on using alloc-pool.h. when we went to varying sizes, we switched to and obstack implementation and never changed the name. <...> I think it would be clearer to name this "irange_obstack", or somesuch. I'd prefer something more generic. We don't want to tie the name of the allocator to the underlying implementation. What if we later change to malloc? We'd have to change the name to irange_malloc. irange_allocator? Or is there something more generically appropriate here? How about "irange_bump_allocator?" Rather long, but it expresses the "irange_allocator" is sufficient . The consumer should not care what the implementation is, and we may decide to implement it differently down the road. So I don't want to imply something specific in the name or we'd have to change it again. Andrew
Re: [PATCH] irange_pool class
On 9/18/20 2:28 PM, David Malcolm wrote: On Fri, 2020-09-18 at 07:49 +0200, Aldy Hernandez wrote: On 9/18/20 3:43 AM, David Malcolm wrote: On Thu, 2020-09-17 at 12:36 +0200, Aldy Hernandez via Gcc-patches wrote: This is the irange storage class. It is used to allocate the minimum amount of storage needed for a given irange. Storage is automatically freed at destruction. It is meant for long term storage, as opposed to int_range_max which is meant for intermediate temporary results on the stack. The general gist is: irange_pool pool; // Allocate an irange of 5 sub-ranges. irange *p = pool.allocate (5); // Allocate an irange of 3 sub-ranges. irange *q = pool.allocate (3); // Allocate an irange with as many sub-ranges as are currently // used in "some_other_range". irange *r = pool.allocate (some_other_range); FWIW my first thoughts reading this example were - "how do I deallocate these iranges?" and "do I need to call pool.deallocate on them, or is that done for me by the irange dtor?" Thus the description front and center of the header file: "Storage is automatically freed at destruction..." I think of a "pool allocator" as something that makes a small number of large allocation under the covers, and then uses that to serve large numbers of fixed sized small allocations and deallocations with O(1) using a free list. Ah, I didn't know pool had a different meaning. See e.g. gcc/alloc-pool.h [...] +// This is the irange storage class. It is used to allocate the +// minimum amount of storage needed for a given irange. Storage is +// automatically freed at destruction. "at destruction" of what object - the irange or the irange_pool? Reading the code, it turns out to be "at destruction of the irange_pool", and it turns out that irange_pool is an obstack under the covers (also called a "bump allocator") and thus, I believe, the lifetime of the irange instances is that of the storage instance. The sentence is talking about the storage class, so I thought it was obvious that the destruction we talk about is the storage class itself. I suppose if it isn't clear we could say: "Storage is automatically freed at destruction of the storage class." I think it would be clearer to name this "irange_obstack", or somesuch. I'd prefer something more generic. We don't want to tie the name of the allocator to the underlying implementation. What if we later change to malloc? We'd have to change the name to irange_malloc. irange_allocator? Or is there something more generically appropriate here? How about "irange_bump_allocator?" Rather long, but it expresses the key point that the irange instances coming out of it don't have independent lifetimes - their lifetimes are those of the allocator; the client code doesn't need to find and clean up all of those individual iranges, right? (assuming I'm reading the code correctly) (That name also avoids mentioning the implementation detail that it uses obstack). I'm sorry, but that's _really_ ugly. Surely irange_allocator can't be that confusing. A casual look at the header file would dispel all doubts. Aldy Sorry if I'm nitpicking; I think my high level thought here is that we have various memory management strategies inside GCC (in no particular order): - garbage collection - explicit malloc/free - explicit new/delete - explicit new/delete backed by allocation pools - RAII - bump allocators aka obstacks and I like to be clear about what "owns" each object (responsibility for cleanup, lifetimes, etc) Hope this is constructive Dave
Re: [PATCH] irange_pool class
On Fri, 2020-09-18 at 07:49 +0200, Aldy Hernandez wrote: > > On 9/18/20 3:43 AM, David Malcolm wrote: > > On Thu, 2020-09-17 at 12:36 +0200, Aldy Hernandez via Gcc-patches > > wrote: > > > This is the irange storage class. It is used to allocate the > > > minimum > > > amount of storage needed for a given irange. Storage is > > > automatically > > > freed at destruction. > > > > > > It is meant for long term storage, as opposed to int_range_max > > > which > > > is > > > meant for intermediate temporary results on the stack. > > > > > > The general gist is: > > > > > > irange_pool pool; > > > > > > // Allocate an irange of 5 sub-ranges. > > > irange *p = pool.allocate (5); > > > > > > // Allocate an irange of 3 sub-ranges. > > > irange *q = pool.allocate (3); > > > > > > // Allocate an irange with as many sub-ranges as are currently > > > // used in "some_other_range". > > > irange *r = pool.allocate (some_other_range); > > > > FWIW my first thoughts reading this example were - "how do I > > deallocate > > these iranges?" and "do I need to call pool.deallocate on them, or > > is > > that done for me by the irange dtor?" > > Thus the description front and center of the header file: > > "Storage is automatically freed at destruction..." > > > I think of a "pool allocator" as something that makes a small > > number of > > large allocation under the covers, and then uses that to serve > > large > > numbers of fixed sized small allocations and deallocations with > > O(1) > > using a free list. > > Ah, I didn't know pool had a different meaning. See e.g. gcc/alloc-pool.h > > [...] > > > > > +// This is the irange storage class. It is used to allocate the > > > +// minimum amount of storage needed for a given irange. Storage > > > is > > > +// automatically freed at destruction. > > > > "at destruction" of what object - the irange or the irange_pool? > > Reading the code, it turns out to be "at destruction of the > > irange_pool", and it turns out that irange_pool is an obstack under > > the > > covers (also called a "bump allocator") and thus, I believe, the > > lifetime of the irange instances is that of the storage instance. > > The sentence is talking about the storage class, so I thought it was > obvious that the destruction we talk about is the storage class > itself. > I suppose if it isn't clear we could say: > > "Storage is automatically freed at destruction of the storage class." > > I think it would be clearer to name this "irange_obstack", or > > somesuch. > > I'd prefer something more generic. We don't want to tie the name of > the > allocator to the underlying implementation. What if we later change > to > malloc? We'd have to change the name to irange_malloc. > irange_allocator? Or is there something more generically appropriate > here? How about "irange_bump_allocator?" Rather long, but it expresses the key point that the irange instances coming out of it don't have independent lifetimes - their lifetimes are those of the allocator; the client code doesn't need to find and clean up all of those individual iranges, right? (assuming I'm reading the code correctly) (That name also avoids mentioning the implementation detail that it uses obstack). Sorry if I'm nitpicking; I think my high level thought here is that we have various memory management strategies inside GCC (in no particular order): - garbage collection - explicit malloc/free - explicit new/delete - explicit new/delete backed by allocation pools - RAII - bump allocators aka obstacks and I like to be clear about what "owns" each object (responsibility for cleanup, lifetimes, etc) Hope this is constructive Dave
Re: [PATCH] irange_pool class
On 9/17/20 8:02 PM, Martin Sebor wrote:
> On 9/17/20 4:36 AM, Aldy Hernandez via Gcc-patches wrote:
>> This is the irange storage class. It is used to allocate the minimum
>> amount of storage needed for a given irange. Storage is automatically
>> freed at destruction.
>>
>> It is meant for long term storage, as opposed to int_range_max which
>> is meant for intermediate temporary results on the stack.
>>
>> The general gist is:
>>
>> irange_pool pool;
>>
>> // Allocate an irange of 5 sub-ranges.
>> irange *p = pool.allocate (5);
>>
>> // Allocate an irange of 3 sub-ranges.
>> irange *q = pool.allocate (3);
>>
>> // Allocate an irange with as many sub-ranges as are currently
>> // used in "some_other_range".
>> irange *r = pool.allocate (some_other_range);
>
> I used this as an opportunity to learn more about the irange classes,
> so I have more to say than this little change alone might justify.
>
>>
>> OK?
>> Aldy
>> ---
>> gcc/value-range.h | 63 +++
>> 1 file changed, 63 insertions(+)
>>
>> diff --git a/gcc/value-range.h b/gcc/value-range.h
>> index 8497791c7b3..88cb3075bf0 100644
>> --- a/gcc/value-range.h
>> +++ b/gcc/value-range.h
>> @@ -43,6 +43,7 @@ enum value_range_kind
>>
>> class irange
>> {
>> + friend class irange_pool;
>> public:
>> // In-place setters.
>> void set (tree, tree, value_range_kind = VR_RANGE);
>> @@ -619,4 +620,66 @@ vrp_val_min (const_tree type)
>> return NULL_TREE;
>> }
>>
>> +// This is the irange storage class. It is used to allocate the
>> +// minimum amount of storage needed for a given irange. Storage is
>> +// automatically freed at destruction.
>> +//
>> +// It is meant for long term storage, as opposed to int_range_max
>> +// which is meant for intermediate temporary results on the stack.
>> +
>> +class irange_pool
>> +{
>> +public:
>> + irange_pool ();
>> + ~irange_pool ();
>> + // Return a new range with NUM_PAIRS.
>> + irange *allocate (unsigned num_pairs);
>> + // Return a copy of SRC with the minimum amount of sub-ranges needed
>> + // to represent it.
>> + irange *allocate (const irange );
>> +private:
>> + struct obstack irange_obstack;
>> +};
>
> Since the class owns a resource, its copy ctor and assignment should
> either transfer it or copy it between instances, or be disabled if
> copying isn't intended.
But that would be silly. Who would ever think of copying the allocator
object? :-). But it makes perfect sense. I've disabled copy and
assignment.
>
> I don't know much about the obstack APIs but if it's anything like
> malloc/free or new/delete I'm guessing the class isn't meant to be
> copied or assigned. If that's correct, I would suggest to make it
> an error by making its copy ctor and copy assignment operator
> private or deleted, e.g., by making use of DISABLE_COPY_AND_ASSIGN.
>
> Otherwise, if the implicitly provided copy ctor and assignment work
> correctly, I'd suggest to add a comment to the class making it clear
> that copying and assignment are in fact safe.
>
>
>> +
>> +inline
>> +irange_pool::irange_pool ()
>> +{
>> + obstack_init (_obstack);
>> +}
>> +
>> +inline
>> +irange_pool::~irange_pool ()
>> +{
>> + obstack_free (_obstack, NULL);
>> +}
>> +
>> +// Return a new range with NUM_PAIRS.
>> +
>> +inline irange *
>> +irange_pool::allocate (unsigned num_pairs)
>> +{
>> + // Never allocate 0 pairs.
>> + // Don't allocate 1 either, or we get legacy value_range's.
>> + if (num_pairs < 2)
>> +num_pairs = 2;
>> +
>> + struct newir {
>> +irange range;
>> +tree mem[1];
>> + };
>> + struct newir *r
>> += (struct newir *) obstack_alloc (_obstack,
>> + sizeof (struct newir)
>> + + sizeof (tree) * 2 * (num_pairs - 1));
>> + return new ((irange *) r) irange (&(r->mem[0]), num_pairs);
>
> FWIW, it took me a minute before I understood what this dense code
> does. Rewriting it like this helped:
Yeah. We need the newir object to get the alignment right.
>
>size_t nbytes
> = (sizeof (newir) + sizeof (tree) * 2 * (num_pairs - 1));
>
>struct newir *r
> = (newir *) obstack_alloc (_obstack, nbytes);
>
>return new (r) irange (r->mem, num_pairs);
Indeed. I find splitting things up easier to read. FWIW, the original
code had it split up, and then it got munged up in one of our many
iterations. I blame Andrew :).
>
> The non-member placement new takes a void* argument so the cast from
> r's type to irange* isn't necessary. &(r->mem[0]) is the same as
> r->mem which also reads a little clearer to me. In C++, the class-
Same here :).
> id ("struct" or "class") can be omitted when there's no ambiguity.
I always thought common usage was to put the struct, but avoid the
class. I'm fine either way though.
>
> The allocated memory is passed to the irange ctor uninitialized but
> the ctor doesn't access it, and (AFAICS) neither do any
Re: [PATCH] irange_pool class
On 9/18/20 3:43 AM, David Malcolm wrote:
On Thu, 2020-09-17 at 12:36 +0200, Aldy Hernandez via Gcc-patches
wrote:
This is the irange storage class. It is used to allocate the
minimum
amount of storage needed for a given irange. Storage is
automatically
freed at destruction.
It is meant for long term storage, as opposed to int_range_max which
is
meant for intermediate temporary results on the stack.
The general gist is:
irange_pool pool;
// Allocate an irange of 5 sub-ranges.
irange *p = pool.allocate (5);
// Allocate an irange of 3 sub-ranges.
irange *q = pool.allocate (3);
// Allocate an irange with as many sub-ranges as are currently
// used in "some_other_range".
irange *r = pool.allocate (some_other_range);
FWIW my first thoughts reading this example were - "how do I deallocate
these iranges?" and "do I need to call pool.deallocate on them, or is
that done for me by the irange dtor?"
Thus the description front and center of the header file:
"Storage is automatically freed at destruction..."
I think of a "pool allocator" as something that makes a small number of
large allocation under the covers, and then uses that to serve large
numbers of fixed sized small allocations and deallocations with O(1)
using a free list.
Ah, I didn't know pool had a different meaning.
[...]
+// This is the irange storage class. It is used to allocate the
+// minimum amount of storage needed for a given irange. Storage is
+// automatically freed at destruction.
"at destruction" of what object - the irange or the irange_pool?
Reading the code, it turns out to be "at destruction of the
irange_pool", and it turns out that irange_pool is an obstack under the
covers (also called a "bump allocator") and thus, I believe, the
lifetime of the irange instances is that of the storage instance.
The sentence is talking about the storage class, so I thought it was
obvious that the destruction we talk about is the storage class itself.
I suppose if it isn't clear we could say:
"Storage is automatically freed at destruction of the storage class."
I think it would be clearer to name this "irange_obstack", or somesuch.
I'd prefer something more generic. We don't want to tie the name of the
allocator to the underlying implementation. What if we later change to
malloc? We'd have to change the name to irange_malloc.
irange_allocator? Or is there something more generically appropriate here?
+//
+// It is meant for long term storage, as opposed to int_range_max
+// which is meant for intermediate temporary results on the stack.
+
+class irange_pool
+{
+public:
+ irange_pool ();
+ ~irange_pool ();
+ // Return a new range with NUM_PAIRS.
+ irange *allocate (unsigned num_pairs);
+ // Return a copy of SRC with the minimum amount of sub-ranges
needed
+ // to represent it.
+ irange *allocate (const irange );
+private:
+ struct obstack irange_obstack;
...and thus to rename this field to "m_obstack" or similar.
Will do.
Thanks.
Aldy
Re: [PATCH] irange_pool class
On Thu, 2020-09-17 at 12:36 +0200, Aldy Hernandez via Gcc-patches
wrote:
> This is the irange storage class. It is used to allocate the
> minimum
> amount of storage needed for a given irange. Storage is
> automatically
> freed at destruction.
>
> It is meant for long term storage, as opposed to int_range_max which
> is
> meant for intermediate temporary results on the stack.
>
> The general gist is:
>
> irange_pool pool;
>
> // Allocate an irange of 5 sub-ranges.
> irange *p = pool.allocate (5);
>
> // Allocate an irange of 3 sub-ranges.
> irange *q = pool.allocate (3);
>
> // Allocate an irange with as many sub-ranges as are currently
> // used in "some_other_range".
> irange *r = pool.allocate (some_other_range);
FWIW my first thoughts reading this example were - "how do I deallocate
these iranges?" and "do I need to call pool.deallocate on them, or is
that done for me by the irange dtor?"
I think of a "pool allocator" as something that makes a small number of
large allocation under the covers, and then uses that to serve large
numbers of fixed sized small allocations and deallocations with O(1)
using a free list.
[...]
> +// This is the irange storage class. It is used to allocate the
> +// minimum amount of storage needed for a given irange. Storage is
> +// automatically freed at destruction.
"at destruction" of what object - the irange or the irange_pool?
Reading the code, it turns out to be "at destruction of the
irange_pool", and it turns out that irange_pool is an obstack under the
covers (also called a "bump allocator") and thus, I believe, the
lifetime of the irange instances is that of the storage instance.
I think it would be clearer to name this "irange_obstack", or somesuch.
> +//
> +// It is meant for long term storage, as opposed to int_range_max
> +// which is meant for intermediate temporary results on the stack.
> +
> +class irange_pool
> +{
> +public:
> + irange_pool ();
> + ~irange_pool ();
> + // Return a new range with NUM_PAIRS.
> + irange *allocate (unsigned num_pairs);
> + // Return a copy of SRC with the minimum amount of sub-ranges
> needed
> + // to represent it.
> + irange *allocate (const irange );
> +private:
> + struct obstack irange_obstack;
...and thus to rename this field to "m_obstack" or similar.
[...]
Hope this is constructive
Dave
Re: [PATCH] irange_pool class
On 9/17/20 4:36 AM, Aldy Hernandez via Gcc-patches wrote:
This is the irange storage class. It is used to allocate the minimum
amount of storage needed for a given irange. Storage is automatically
freed at destruction.
It is meant for long term storage, as opposed to int_range_max which is
meant for intermediate temporary results on the stack.
The general gist is:
irange_pool pool;
// Allocate an irange of 5 sub-ranges.
irange *p = pool.allocate (5);
// Allocate an irange of 3 sub-ranges.
irange *q = pool.allocate (3);
// Allocate an irange with as many sub-ranges as are currently
// used in "some_other_range".
irange *r = pool.allocate (some_other_range);
I used this as an opportunity to learn more about the irange classes,
so I have more to say than this little change alone might justify.
OK?
Aldy
---
gcc/value-range.h | 63 +++
1 file changed, 63 insertions(+)
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 8497791c7b3..88cb3075bf0 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -43,6 +43,7 @@ enum value_range_kind
class irange
{
+ friend class irange_pool;
public:
// In-place setters.
void set (tree, tree, value_range_kind = VR_RANGE);
@@ -619,4 +620,66 @@ vrp_val_min (const_tree type)
return NULL_TREE;
}
+// This is the irange storage class. It is used to allocate the
+// minimum amount of storage needed for a given irange. Storage is
+// automatically freed at destruction.
+//
+// It is meant for long term storage, as opposed to int_range_max
+// which is meant for intermediate temporary results on the stack.
+
+class irange_pool
+{
+public:
+ irange_pool ();
+ ~irange_pool ();
+ // Return a new range with NUM_PAIRS.
+ irange *allocate (unsigned num_pairs);
+ // Return a copy of SRC with the minimum amount of sub-ranges needed
+ // to represent it.
+ irange *allocate (const irange );
+private:
+ struct obstack irange_obstack;
+};
Since the class owns a resource, its copy ctor and assignment should
either transfer it or copy it between instances, or be disabled if
copying isn't intended.
I don't know much about the obstack APIs but if it's anything like
malloc/free or new/delete I'm guessing the class isn't meant to be
copied or assigned. If that's correct, I would suggest to make it
an error by making its copy ctor and copy assignment operator
private or deleted, e.g., by making use of DISABLE_COPY_AND_ASSIGN.
Otherwise, if the implicitly provided copy ctor and assignment work
correctly, I'd suggest to add a comment to the class making it clear
that copying and assignment are in fact safe.
+
+inline
+irange_pool::irange_pool ()
+{
+ obstack_init (_obstack);
+}
+
+inline
+irange_pool::~irange_pool ()
+{
+ obstack_free (_obstack, NULL);
+}
+
+// Return a new range with NUM_PAIRS.
+
+inline irange *
+irange_pool::allocate (unsigned num_pairs)
+{
+ // Never allocate 0 pairs.
+ // Don't allocate 1 either, or we get legacy value_range's.
+ if (num_pairs < 2)
+ num_pairs = 2;
+
+ struct newir {
+ irange range;
+ tree mem[1];
+ };
+ struct newir *r
+ = (struct newir *) obstack_alloc (_obstack,
+ sizeof (struct newir)
+ + sizeof (tree) * 2 * (num_pairs - 1));
+ return new ((irange *) r) irange (&(r->mem[0]), num_pairs);
FWIW, it took me a minute before I understood what this dense code
does. Rewriting it like this helped:
size_t nbytes
= (sizeof (newir) + sizeof (tree) * 2 * (num_pairs - 1));
struct newir *r
= (newir *) obstack_alloc (_obstack, nbytes);
return new (r) irange (r->mem, num_pairs);
The non-member placement new takes a void* argument so the cast from
r's type to irange* isn't necessary. &(r->mem[0]) is the same as
r->mem which also reads a little clearer to me. In C++, the class-
id ("struct" or "class") can be omitted when there's no ambiguity.
The allocated memory is passed to the irange ctor uninitialized but
the ctor doesn't access it, and (AFAICS) neither do any other irange
members, so that's fine. I like that the irange class is safe to
use even when the array it manages is uninitialized. In fact, it
might be a helpful comment to add to the irange and int_range ctors:
that the array of trees passed to irange doesn't have to be
initialized and the classes work correctly and treat a newly default
constructed range as empty (undefined_p() is true).
Martin
+}
+
+inline irange *
+irange_pool::allocate (const irange )
+{
+ irange *r = allocate (src.num_pairs ());
+ *r = src;
+ return r;
+}
+
#endif // GCC_VALUE_RANGE_H
[PATCH] irange_pool class
This is the irange storage class. It is used to allocate the minimum
amount of storage needed for a given irange. Storage is automatically
freed at destruction.
It is meant for long term storage, as opposed to int_range_max which is
meant for intermediate temporary results on the stack.
The general gist is:
irange_pool pool;
// Allocate an irange of 5 sub-ranges.
irange *p = pool.allocate (5);
// Allocate an irange of 3 sub-ranges.
irange *q = pool.allocate (3);
// Allocate an irange with as many sub-ranges as are currently
// used in "some_other_range".
irange *r = pool.allocate (some_other_range);
OK?
Aldy
---
gcc/value-range.h | 63 +++
1 file changed, 63 insertions(+)
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 8497791c7b3..88cb3075bf0 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -43,6 +43,7 @@ enum value_range_kind
class irange
{
+ friend class irange_pool;
public:
// In-place setters.
void set (tree, tree, value_range_kind = VR_RANGE);
@@ -619,4 +620,66 @@ vrp_val_min (const_tree type)
return NULL_TREE;
}
+// This is the irange storage class. It is used to allocate the
+// minimum amount of storage needed for a given irange. Storage is
+// automatically freed at destruction.
+//
+// It is meant for long term storage, as opposed to int_range_max
+// which is meant for intermediate temporary results on the stack.
+
+class irange_pool
+{
+public:
+ irange_pool ();
+ ~irange_pool ();
+ // Return a new range with NUM_PAIRS.
+ irange *allocate (unsigned num_pairs);
+ // Return a copy of SRC with the minimum amount of sub-ranges needed
+ // to represent it.
+ irange *allocate (const irange );
+private:
+ struct obstack irange_obstack;
+};
+
+inline
+irange_pool::irange_pool ()
+{
+ obstack_init (_obstack);
+}
+
+inline
+irange_pool::~irange_pool ()
+{
+ obstack_free (_obstack, NULL);
+}
+
+// Return a new range with NUM_PAIRS.
+
+inline irange *
+irange_pool::allocate (unsigned num_pairs)
+{
+ // Never allocate 0 pairs.
+ // Don't allocate 1 either, or we get legacy value_range's.
+ if (num_pairs < 2)
+num_pairs = 2;
+
+ struct newir {
+irange range;
+tree mem[1];
+ };
+ struct newir *r
+= (struct newir *) obstack_alloc (_obstack,
+ sizeof (struct newir)
+ + sizeof (tree) * 2 * (num_pairs - 1));
+ return new ((irange *) r) irange (&(r->mem[0]), num_pairs);
+}
+
+inline irange *
+irange_pool::allocate (const irange )
+{
+ irange *r = allocate (src.num_pairs ());
+ *r = src;
+ return r;
+}
+
#endif // GCC_VALUE_RANGE_H
--
2.26.2
