[RFC] Sparse on entry cache for Ranger.

As mentioned earlier, I abstracted the on-entry cache at the beginning 
of stage1. This was to make it easier to port future changes back to 
GCC11 so we could provide alternate representations to deal with memory 
issues, or what have you.

This patch introduces a sparse representation of the cache which is 
used  when the number of basic blocks gets too large.

I commandeered the bitmap code since its efficient and has been working 
a long time, and added 2 routines to get and set 4 bits (quads) at a 
time.  This allows me to use a bitmap like its a sparse array which can 
contain a value between 0 and 15, and is conveniently pre-initialized to 
values of 0 at no cost :-)   This is then used as an index into a small 
local table to store ranges for the name.  Its limiting in that an 
ssa-name will not be able to have more than 15 unique ranges, but this 
happens in less than 8% of all cases in the data I collected, and most 
of those are switches.. any ranges after the 15 slots are full revert to 
VARYING.  The values for VARYING and UNDEFINED are pre-populated, and 
for pointers, I also pre-populate [0,0] and ~[0, 0].

This also adds --param=evrp-sparse-threshold=  which allows the 
threshold between the full vector and this new sparse representation to 
be changed. It defaults to a value of 800. I've done various performance 
runs, and this seems to be a reasonably balanced number. In fact its a 
28% improvement in EVRP compile time over 390 files from a gcc bootstrap 
with minimal impact on missed opportunities.

I've also tried to see if using less than 15 values has any significant 
effect (The lookup is linear when setting), but it does not appear to.

I've also bootstrapped with the sparse threshold at 0 to ensure there 
aren't any issues.

My thoughts are I would put this into trunk, and assuming nothing comes 
up  over the next couple of days, port it back to GCC11 to resolve 
100299 and other excessive memory consumption PRs there as well. given 
that its reusing bitmap code for the sparse representation, it seems 
like it would be low risk.

Are we OK with the addition of the bitmap_get_quad and bitmap_set_quad 
routines in bitmap.c?  It seems like they might be useful to others.  
They are simple tweaks of bitmap_set_bit and bitmap_bit_p.. just dealing 
with 4 bits at a time.  I could make them local if this is a problem, 
but i don't have access to the bitmap internals there.

Bootstraps on x86_64-pc-linux-gnu with no regressions.

Andrew

PS in PR10299 we spend a fraction of a second in EVRP now.

On Wed, Jun 2, 2021 at 11:15 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> As mentioned earlier, I abstracted the on-entry cache at the beginning
> of stage1. This was to make it easier to port future changes back to
> GCC11 so we could provide alternate representations to deal with memory
> issues, or what have you.
>
> This patch introduces a sparse representation of the cache which is
> used  when the number of basic blocks gets too large.
>
> I commandeered the bitmap code since its efficient and has been working
> a long time, and added 2 routines to get and set 4 bits (quads) at a
> time.  This allows me to use a bitmap like its a sparse array which can
> contain a value between 0 and 15, and is conveniently pre-initialized to
> values of 0 at no cost :-)   This is then used as an index into a small
> local table to store ranges for the name.  Its limiting in that an
> ssa-name will not be able to have more than 15 unique ranges, but this
> happens in less than 8% of all cases in the data I collected, and most
> of those are switches.. any ranges after the 15 slots are full revert to
> VARYING.  The values for VARYING and UNDEFINED are pre-populated, and
> for pointers, I also pre-populate [0,0] and ~[0, 0].
>
> This also adds --param=evrp-sparse-threshold=  which allows the
> threshold between the full vector and this new sparse representation to
> be changed. It defaults to a value of 800. I've done various performance
> runs, and this seems to be a reasonably balanced number. In fact its a
> 28% improvement in EVRP compile time over 390 files from a gcc bootstrap
> with minimal impact on missed opportunities.
>
> I've also tried to see if using less than 15 values has any significant
> effect (The lookup is linear when setting), but it does not appear to.
>
> I've also bootstrapped with the sparse threshold at 0 to ensure there
> aren't any issues.
>
> My thoughts are I would put this into trunk, and assuming nothing comes
> up  over the next couple of days, port it back to GCC11 to resolve
> 100299 and other excessive memory consumption PRs there as well. given
> that its reusing bitmap code for the sparse representation, it seems
> like it would be low risk.
>
> Are we OK with the addition of the bitmap_get_quad and bitmap_set_quad
> routines in bitmap.c?  It seems like they might be useful to others.
> They are simple tweaks of bitmap_set_bit and bitmap_bit_p.. just dealing
> with 4 bits at a time.  I could make them local if this is a problem,
> but i don't have access to the bitmap internals there.

I think _quad is a bit too specific - it's aligned chunks so maybe

void bitmap_set_aligned_chunk (bitmap, unsigned int chunk, unsigned
int chunk_size, BITMAP_WORD chunk_value);

and

BITMAP_WORD bitmap_get_aligned_chunk (bitmap, unsigned int chunk,
unsigned chunk_size);

and assert that chunk_size is power-of-two and fits in BITMAP_WORD?

(also note using unsigned ints and BITMAP_WORD for the data type)

I've been using two-bit representations in a few places (but mostly
setting/testing the
respective bits independently), I suppose for example

static dep_state
query_loop_dependence (class loop *loop, im_mem_ref *ref, dep_kind kind)
{
  unsigned first_bit = 6 * loop->num + kind * 2;
  if (bitmap_bit_p (&ref->dep_loop, first_bit))
    return dep_independent;
  else if (bitmap_bit_p (&ref->dep_loop, first_bit + 1))
    return dep_dependent;

could use a chunk size of 2 and a single bitmap query.  Incidentially this
specific code uses 6 bits, so it's not fully aligned ...

/* We use six bits per loop in the ref->dep_loop bitmap to record
   the dep_kind x dep_state combinations.  */

enum dep_kind { lim_raw, sm_war, sm_waw };
enum dep_state { dep_unknown, dep_independent, dep_dependent };

... but there's also at most a single bit set.

Anyway, I'm OK with adding API to access aligned power-of-two sized chunks.
Even not power-of-two sized unaligned chunks should be quite straight
forward to implement if we limit the chunk size to BITMAP_WORD by
simply advancing to the next bitmap word / element when necessary.

An alternative low-level API would provide accesses to whole BITMAP_WORD
entries and the quads could be implemented on top of that
(bitmap_set_word/_get_word)

Richard.

> Bootstraps on x86_64-pc-linux-gnu with no regressions.
>
> Andrew
>
> PS in PR10299 we spend a fraction of a second in EVRP now.
>
>
>

On 6/7/21 4:40 AM, Richard Biener wrote:
> On Wed, Jun 2, 2021 at 11:15 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>>
>> My thoughts are I would put this into trunk, and assuming nothing comes
>> up  over the next couple of days, port it back to GCC11 to resolve
>> 100299 and other excessive memory consumption PRs there as well. given
>> that its reusing bitmap code for the sparse representation, it seems
>> like it would be low risk.
>>
>> Are we OK with the addition of the bitmap_get_quad and bitmap_set_quad
>> routines in bitmap.c?  It seems like they might be useful to others.
>> They are simple tweaks of bitmap_set_bit and bitmap_bit_p.. just dealing
>> with 4 bits at a time.  I could make them local if this is a problem,
>> but i don't have access to the bitmap internals there.
> I think _quad is a bit too specific - it's aligned chunks so maybe
>
> void bitmap_set_aligned_chunk (bitmap, unsigned int chunk, unsigned
> int chunk_size, BITMAP_WORD chunk_value);
>
> and
>
> BITMAP_WORD bitmap_get_aligned_chunk (bitmap, unsigned int chunk,
> unsigned chunk_size);
>
> and assert that chunk_size is power-of-two and fits in BITMAP_WORD?
>
> (also note using unsigned ints and BITMAP_WORD for the data type)
>
> I've been using two-bit representations in a few places (but mostly
> setting/testing the
> respective bits independently), I suppose for example

That's exactly how this started.. I was using a pair of bits for 
pointers. UNDEFINED, zero, non-zero and varying... and checking the bits 
independently. when I decided I needed 3 bits, the whole quad thing 
evolved since picking up 3 or 4 consecutive bits one at a time seemed 
too inefficient.

>
> static dep_state
> query_loop_dependence (class loop *loop, im_mem_ref *ref, dep_kind kind)
> {
>    unsigned first_bit = 6 * loop->num + kind * 2;
>    if (bitmap_bit_p (&ref->dep_loop, first_bit))
>      return dep_independent;
>    else if (bitmap_bit_p (&ref->dep_loop, first_bit + 1))
>      return dep_dependent;
>
> could use a chunk size of 2 and a single bitmap query.  Incidentially this
> specific code uses 6 bits, so it's not fully aligned ...
>
> /* We use six bits per loop in the ref->dep_loop bitmap to record
>     the dep_kind x dep_state combinations.  */
>
> enum dep_kind { lim_raw, sm_war, sm_waw };
> enum dep_state { dep_unknown, dep_independent, dep_dependent };
>
> ... but there's also at most a single bit set.
>
> Anyway, I'm OK with adding API to access aligned power-of-two sized chunks.
> Even not power-of-two sized unaligned chunks should be quite straight
> forward to implement if we limit the chunk size to BITMAP_WORD by
> simply advancing to the next bitmap word / element when necessary.
>
> An alternative low-level API would provide accesses to whole BITMAP_WORD
> entries and the quads could be implemented on top of that
> (bitmap_set_word/_get_word)
>
> Richard.
>
I think I'll stick to the power of 2 limitation for now.  If someone 
finds a pressing need or desire, they can enhance it :-)

Wanna eyeball this an make sure I'm not doing something unportable.. I 
just used your original 2 function names, and swapped out the 4 and a 
couple of constants for computed values. Works fine for me.

I also made the self test process 2, 4 and 8 bit quantities.

Its going thru a test cycle now.

Andrew

On Mon, Jun 7, 2021 at 7:26 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> On 6/7/21 4:40 AM, Richard Biener wrote:
> > On Wed, Jun 2, 2021 at 11:15 PM Andrew MacLeod <amacleod@redhat.com> wrote:
> >>
> >> My thoughts are I would put this into trunk, and assuming nothing comes
> >> up  over the next couple of days, port it back to GCC11 to resolve
> >> 100299 and other excessive memory consumption PRs there as well. given
> >> that its reusing bitmap code for the sparse representation, it seems
> >> like it would be low risk.
> >>
> >> Are we OK with the addition of the bitmap_get_quad and bitmap_set_quad
> >> routines in bitmap.c?  It seems like they might be useful to others.
> >> They are simple tweaks of bitmap_set_bit and bitmap_bit_p.. just dealing
> >> with 4 bits at a time.  I could make them local if this is a problem,
> >> but i don't have access to the bitmap internals there.
> > I think _quad is a bit too specific - it's aligned chunks so maybe
> >
> > void bitmap_set_aligned_chunk (bitmap, unsigned int chunk, unsigned
> > int chunk_size, BITMAP_WORD chunk_value);
> >
> > and
> >
> > BITMAP_WORD bitmap_get_aligned_chunk (bitmap, unsigned int chunk,
> > unsigned chunk_size);
> >
> > and assert that chunk_size is power-of-two and fits in BITMAP_WORD?
> >
> > (also note using unsigned ints and BITMAP_WORD for the data type)
> >
> > I've been using two-bit representations in a few places (but mostly
> > setting/testing the
> > respective bits independently), I suppose for example
>
> That's exactly how this started.. I was using a pair of bits for
> pointers. UNDEFINED, zero, non-zero and varying... and checking the bits
> independently. when I decided I needed 3 bits, the whole quad thing
> evolved since picking up 3 or 4 consecutive bits one at a time seemed
> too inefficient.
>
> >
> > static dep_state
> > query_loop_dependence (class loop *loop, im_mem_ref *ref, dep_kind kind)
> > {
> >    unsigned first_bit = 6 * loop->num + kind * 2;
> >    if (bitmap_bit_p (&ref->dep_loop, first_bit))
> >      return dep_independent;
> >    else if (bitmap_bit_p (&ref->dep_loop, first_bit + 1))
> >      return dep_dependent;
> >
> > could use a chunk size of 2 and a single bitmap query.  Incidentially this
> > specific code uses 6 bits, so it's not fully aligned ...
> >
> > /* We use six bits per loop in the ref->dep_loop bitmap to record
> >     the dep_kind x dep_state combinations.  */
> >
> > enum dep_kind { lim_raw, sm_war, sm_waw };
> > enum dep_state { dep_unknown, dep_independent, dep_dependent };
> >
> > ... but there's also at most a single bit set.
> >
> > Anyway, I'm OK with adding API to access aligned power-of-two sized chunks.
> > Even not power-of-two sized unaligned chunks should be quite straight
> > forward to implement if we limit the chunk size to BITMAP_WORD by
> > simply advancing to the next bitmap word / element when necessary.
> >
> > An alternative low-level API would provide accesses to whole BITMAP_WORD
> > entries and the quads could be implemented on top of that
> > (bitmap_set_word/_get_word)
> >
> > Richard.
> >
> I think I'll stick to the power of 2 limitation for now.  If someone
> finds a pressing need or desire, they can enhance it :-)
>
> Wanna eyeball this an make sure I'm not doing something unportable.. I
> just used your original 2 function names, and swapped out the 4 and a
> couple of constants for computed values. Works fine for me.
>
> I also made the self test process 2, 4 and 8 bit quantities.
>
> Its going thru a test cycle now.

+  gcc_checking_assert (__builtin_popcount (chunk_size) == 1);

please use pow2p_hwi (chunk_size) instead, __builtin_popcount might
not be available with non-GCC host compilers.

Otherwise looks good to me.

Thanks,
Richard.

> Andrew
>
>