[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