irange_pool class

This is the irange storage class.  It is used to allocate the minimum 
amount of storage needed for a given irange.  Storage is automatically 
freed at destruction.

It is meant for long term storage, as opposed to int_range_max which is 
meant for intermediate temporary results on the stack.

The general gist is:

	irange_pool pool;

	// Allocate an irange of 5 sub-ranges.
	irange *p = pool.allocate (5);

	// Allocate an irange of 3 sub-ranges.
	irange *q = pool.allocate (3);

	// Allocate an irange with as many sub-ranges as are currently
	// used in "some_other_range".
	irange *r = pool.allocate (some_other_range);

OK?
Aldy
---
  gcc/value-range.h | 63 +++++++++++++++++++++++++++++++++++++++++++++++
  1 file changed, 63 insertions(+)

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

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

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

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

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

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
>

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

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

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

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

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
>

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

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.

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

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

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

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