* [PATCH] irange_pool class @ 2020-09-17 10:36 Aldy Hernandez 2020-09-17 18:02 ` Martin Sebor 2020-09-18 1:43 ` David Malcolm 0 siblings, 2 replies; 18+ messages in thread From: Aldy Hernandez @ 2020-09-17 10:36 UTC (permalink / raw) To: gcc-patches, Andrew MacLeod 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 &src); +private: + struct obstack irange_obstack; +}; + +inline +irange_pool::irange_pool () +{ + obstack_init (&irange_obstack); +} + +inline +irange_pool::~irange_pool () +{ + obstack_free (&irange_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 (&irange_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 &src) +{ + irange *r = allocate (src.num_pairs ()); + *r = src; + return r; +} + #endif // GCC_VALUE_RANGE_H -- 2.26.2 ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-17 10:36 [PATCH] irange_pool class Aldy Hernandez @ 2020-09-17 18:02 ` Martin Sebor 2020-09-18 6:17 ` Aldy Hernandez 2020-09-18 1:43 ` David Malcolm 1 sibling, 1 reply; 18+ messages in thread From: Martin Sebor @ 2020-09-17 18:02 UTC (permalink / raw) To: Aldy Hernandez, gcc-patches, Andrew MacLeod 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 &src); > +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 (&irange_obstack); > +} > + > +inline > +irange_pool::~irange_pool () > +{ > + obstack_free (&irange_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 (&irange_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 (&irange_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 &src) > +{ > + irange *r = allocate (src.num_pairs ()); > + *r = src; > + return r; > +} > + > #endif // GCC_VALUE_RANGE_H ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-17 18:02 ` Martin Sebor @ 2020-09-18 6:17 ` Aldy Hernandez 0 siblings, 0 replies; 18+ messages in thread From: Aldy Hernandez @ 2020-09-18 6:17 UTC (permalink / raw) To: Martin Sebor, gcc-patches, Andrew MacLeod, David Malcolm 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 &src); >> +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 (&irange_obstack); >> +} >> + >> +inline >> +irange_pool::~irange_pool () >> +{ >> + obstack_free (&irange_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 (&irange_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 (&irange_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 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). That's true by design. Ranges start their life as the empty set. I've incorporated your suggestions and some of David's below. Thanks. Aldy 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_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); --- gcc/value-range.h | 65 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 65 insertions(+) diff --git a/gcc/value-range.h b/gcc/value-range.h index 8497791c7b3..a4b5df4f89d 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,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_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 &src); +private: + DISABLE_COPY_AND_ASSIGN (irange_pool); + struct obstack m_obstack; +}; + +inline +irange_pool::irange_pool () +{ + obstack_init (&m_obstack); +} + +inline +irange_pool::~irange_pool () +{ + obstack_free (&m_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]; + }; + size_t nbytes = (sizeof (newir) + sizeof (tree) * 2 * (num_pairs - 1)); + struct newir *r = (newir *) obstack_alloc (&m_obstack, nbytes); + return new (r) irange (r->mem, num_pairs); +} + +inline irange * +irange_pool::allocate (const irange &src) +{ + irange *r = allocate (src.num_pairs ()); + *r = src; + return r; +} + #endif // GCC_VALUE_RANGE_H -- 2.26.2 ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-17 10:36 [PATCH] irange_pool class Aldy Hernandez 2020-09-17 18:02 ` Martin Sebor @ 2020-09-18 1:43 ` David Malcolm 2020-09-18 5:49 ` Aldy Hernandez 1 sibling, 1 reply; 18+ messages in thread From: David Malcolm @ 2020-09-18 1:43 UTC (permalink / raw) To: Aldy Hernandez, gcc-patches, Andrew MacLeod 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 &src); > +private: > + struct obstack irange_obstack; ...and thus to rename this field to "m_obstack" or similar. [...] Hope this is constructive Dave ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-18 1:43 ` David Malcolm @ 2020-09-18 5:49 ` Aldy Hernandez 2020-09-18 12:28 ` David Malcolm 0 siblings, 1 reply; 18+ messages in thread From: Aldy Hernandez @ 2020-09-18 5:49 UTC (permalink / raw) To: David Malcolm, gcc-patches, Andrew MacLeod 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 &src); >> +private: >> + struct obstack irange_obstack; > > ...and thus to rename this field to "m_obstack" or similar. Will do. Thanks. Aldy ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-18 5:49 ` Aldy Hernandez @ 2020-09-18 12:28 ` David Malcolm 2020-09-18 14:10 ` Aldy Hernandez 2020-09-18 16:42 ` Andrew MacLeod 0 siblings, 2 replies; 18+ messages in thread From: David Malcolm @ 2020-09-18 12:28 UTC (permalink / raw) To: Aldy Hernandez, gcc-patches, Andrew MacLeod 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 ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-18 12:28 ` David Malcolm @ 2020-09-18 14:10 ` Aldy Hernandez 2020-09-18 17:07 ` Martin Sebor 2020-09-18 16:42 ` Andrew MacLeod 1 sibling, 1 reply; 18+ messages in thread From: Aldy Hernandez @ 2020-09-18 14:10 UTC (permalink / raw) To: David Malcolm, gcc-patches, Andrew MacLeod 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 > ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-18 14:10 ` Aldy Hernandez @ 2020-09-18 17:07 ` Martin Sebor 2020-09-18 17:36 ` Andrew MacLeod 0 siblings, 1 reply; 18+ messages in thread From: Martin Sebor @ 2020-09-18 17:07 UTC (permalink / raw) To: Aldy Hernandez, David Malcolm, gcc-patches, Andrew MacLeod 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 >> > ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-18 17:07 ` Martin Sebor @ 2020-09-18 17:36 ` Andrew MacLeod 2020-09-18 20:35 ` Martin Sebor 0 siblings, 1 reply; 18+ messages in thread From: Andrew MacLeod @ 2020-09-18 17:36 UTC (permalink / raw) To: Martin Sebor, Aldy Hernandez, David Malcolm, gcc-patches 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 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? 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.. It currently based on an obstack, and it works exactly like an obstack does... provide hunks of memory with a specific known lifetime. nothing more, nothing less. Andrew ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-18 17:36 ` Andrew MacLeod @ 2020-09-18 20:35 ` Martin Sebor 2020-09-18 21:09 ` Andrew MacLeod 0 siblings, 1 reply; 18+ messages in thread From: Martin Sebor @ 2020-09-18 20:35 UTC (permalink / raw) To: Andrew MacLeod, Aldy Hernandez, David Malcolm, gcc-patches 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 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. > > 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 > > It currently based on an obstack, and it works exactly like an obstack > does... provide hunks of memory with a specific known lifetime. nothing > more, nothing less. > > > Andrew > ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-18 20:35 ` Martin Sebor @ 2020-09-18 21:09 ` Andrew MacLeod 2020-09-19 20:32 ` Martin Sebor 0 siblings, 1 reply; 18+ messages in thread From: Andrew MacLeod @ 2020-09-18 21:09 UTC (permalink / raw) To: Martin Sebor, Aldy Hernandez, David Malcolm, gcc-patches 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 ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-18 21:09 ` Andrew MacLeod @ 2020-09-19 20:32 ` Martin Sebor 2020-09-20 0:40 ` Andrew MacLeod ` (2 more replies) 0 siblings, 3 replies; 18+ messages in thread From: Martin Sebor @ 2020-09-19 20:32 UTC (permalink / raw) To: Andrew MacLeod, Aldy Hernandez, David Malcolm, gcc-patches 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<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. >> [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<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. 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. Martin > 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. ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-19 20:32 ` Martin Sebor @ 2020-09-20 0:40 ` Andrew MacLeod 2020-09-20 7:01 ` Aldy Hernandez 2020-09-21 14:14 ` Andrew MacLeod 2 siblings, 0 replies; 18+ messages in thread From: Andrew MacLeod @ 2020-09-20 0:40 UTC (permalink / raw) To: Martin Sebor, Aldy Hernandez, David Malcolm, gcc-patches 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<N> 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 = &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 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 int_range<2> or <3> and see if you miss something you expect. Thats what I started with within internally the ranger, and 95% (made up stat) of ranges in the compiler are represented by a int_range_<3>. remove switches and we're at 98.5% (another made up number) Perhaps we should rework that part of the document.. I think maybe the exuberance of being able to work in infinite subranges is over-stated. Its probably worth reintroducing the dynamic version at some point, but I really dont think you need it. > 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. > If you pass in an int_range<3>, internally the ranger will work with infinite ranges, but it will compress the result automatically to an int_range<3> when it returns the result for you. there wont be any loss of precision during calculations, only what is passed back to you. Perhaps that information is not clear either. And i think you mostly care about the upper and lower limits? (and overflow, but thats different story) int_range<2> is probably sufficient, maybe even int_range<1>... Andrew ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-19 20:32 ` Martin Sebor 2020-09-20 0:40 ` Andrew MacLeod @ 2020-09-20 7:01 ` Aldy Hernandez 2020-09-21 14:14 ` Andrew MacLeod 2 siblings, 0 replies; 18+ messages in thread From: Aldy Hernandez @ 2020-09-20 7:01 UTC (permalink / raw) To: Martin Sebor, Andrew MacLeod, David Malcolm, gcc-patches 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<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. >>> > > [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<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. Once upon a time I gathered stats on how many ranges were actually used in practice. I ran ranger assuming infinite precision and recorded how often we needed what. I don't remember the exact numbers, but I seem to recall that > 95% needed 2 or 3 sub-ranges. Anything greater than that was a mere anomaly (likely a switch as Andrew mentioned). So I don't think we should bend over backwards trying to come up with a dynamic irange. As Andrew mentioned, we had a dynamic irange earlier this year that worked similarly to auto_vec, but we decided it wasn't worth the hassle for all the reasons discussed. >> >> 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. If needed, I'd be happy to revive the dynamic int_range_max we had, but it doesn't seem like you have that many that would warrant anything else. It looks like you're dominated by the number of allocation calls in a function, which surely can't be that many? Even in a worst case scenario, I think you could probably get away with an int_range<5>, probably even an int_range_max?? sizeof int_range<2> = 48 sizeof int_range<3> = 64 sizeof int_range<5> = 96 sizeof int_range_max = 4096 > > 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 We may need to clarify that. What I meant to say was that calls into the API should assume that you have infinite sub-ranges. For example, that instead of looking at kind() and VR_ANTI_RANGE, etc, you should be looking at num_pairs() and lower/upper_bound(), making your code agnostic to the number of pairs in a given range: for (i = 0; i < range.num_pairs (); ++i) do stuff with range.lower_bound(i) do stuff with range.upper_bound(i) instead of: if (range.kind () == VR_ANTI_RANGE) do stuff with range.min (); or instead of: void foo (int_range<3> &range) { ... do stuff with hardcoded range.lower_bound (2); } If your functions take in the base irange class, you're already coding as if infinite ranges :). Well, assuming you don't use the methods in the deprecated API. > 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. > > Martin > >> 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. Yeah, I think we had bits in irange to discriminate between a dynamic range and a static one, and had code throughout that would resize the underlying tree blob if needed. We would like to avoid this complexity if possible. Aldy ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-19 20:32 ` Martin Sebor 2020-09-20 0:40 ` Andrew MacLeod 2020-09-20 7:01 ` Aldy Hernandez @ 2020-09-21 14:14 ` Andrew MacLeod 2 siblings, 0 replies; 18+ messages in thread From: Andrew MacLeod @ 2020-09-21 14:14 UTC (permalink / raw) To: Martin Sebor, Aldy Hernandez, David Malcolm, gcc-patches 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 ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-18 12:28 ` David Malcolm 2020-09-18 14:10 ` Aldy Hernandez @ 2020-09-18 16:42 ` Andrew MacLeod 2020-09-18 17:03 ` Aldy Hernandez 1 sibling, 1 reply; 18+ messages in thread From: Andrew MacLeod @ 2020-09-18 16:42 UTC (permalink / raw) To: David Malcolm, Aldy Hernandez, gcc-patches 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 ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-18 16:42 ` Andrew MacLeod @ 2020-09-18 17:03 ` Aldy Hernandez 2020-09-28 15:56 ` Andrew MacLeod 0 siblings, 1 reply; 18+ messages in thread From: Aldy Hernandez @ 2020-09-18 17:03 UTC (permalink / raw) To: Andrew MacLeod, David Malcolm, gcc-patches [-- Attachment #1: Type: text/plain, Size: 1407 bytes --] 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 [-- Attachment #2: curr.patch --] [-- Type: text/x-patch, Size: 3026 bytes --] commit 343463f8887ab510503d9e230268963a299a84ef Author: Aldy Hernandez <aldyh@redhat.com> 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 &src); +private: + DISABLE_COPY_AND_ASSIGN (irange_allocator); + struct obstack m_obstack; +}; + +inline +irange_allocator::irange_allocator () +{ + obstack_init (&m_obstack); +} + +inline +irange_allocator::~irange_allocator () +{ + obstack_free (&m_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 (&m_obstack, nbytes); + return new (r) irange (r->mem, num_pairs); +} + +inline irange * +irange_allocator::allocate (const irange &src) +{ + irange *r = allocate (src.num_pairs ()); + *r = src; + return r; +} + #endif // GCC_VALUE_RANGE_H ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH] irange_pool class 2020-09-18 17:03 ` Aldy Hernandez @ 2020-09-28 15:56 ` Andrew MacLeod 0 siblings, 0 replies; 18+ messages in thread From: Andrew MacLeod @ 2020-09-28 15:56 UTC (permalink / raw) To: Aldy Hernandez, David Malcolm, gcc-patches 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 ^ permalink raw reply [flat|nested] 18+ messages in thread
end of thread, other threads:[~2020-09-28 15:56 UTC | newest] Thread overview: 18+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-09-17 10:36 [PATCH] irange_pool class Aldy Hernandez 2020-09-17 18:02 ` Martin Sebor 2020-09-18 6:17 ` Aldy Hernandez 2020-09-18 1:43 ` David Malcolm 2020-09-18 5:49 ` Aldy Hernandez 2020-09-18 12:28 ` David Malcolm 2020-09-18 14:10 ` Aldy Hernandez 2020-09-18 17:07 ` Martin Sebor 2020-09-18 17:36 ` Andrew MacLeod 2020-09-18 20:35 ` Martin Sebor 2020-09-18 21:09 ` Andrew MacLeod 2020-09-19 20:32 ` Martin Sebor 2020-09-20 0:40 ` Andrew MacLeod 2020-09-20 7:01 ` Aldy Hernandez 2020-09-21 14:14 ` Andrew MacLeod 2020-09-18 16:42 ` Andrew MacLeod 2020-09-18 17:03 ` Aldy Hernandez 2020-09-28 15:56 ` Andrew MacLeod
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).