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