[PATCH][RFC] Sparse on entry cache for Ranger.

Andrew MacLeod amacleod@redhat.com
Wed Jun 2 21:15:53 GMT 2021


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.



-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-Implement-quad-bit-accessors-in-bitmap-for-sparse-ar.patch
Type: text/x-patch
Size: 4560 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20210602/91d0e2e2/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0003-Implement-a-sparse-bitmap-represenation-for-Rangers-.patch
Type: text/x-patch
Size: 7362 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20210602/91d0e2e2/attachment-0001.bin>


More information about the Gcc-patches mailing list