This is the mail archive of the
mailing list for the GCC project.
Re: [patch] cse.c: Speed up cse_reg_info maintainance - Part 2
> Funny. This is more or less what this code looked like in older
> versions of gcc, except it was using several arrays instead of a
> structure. Then, in
> Mark changed it to use a splay tree for speed reasons, and subsequently
> that got changed to a hash table.
> Mark's reason for his change was overhead in new_basic_block, where we
> had an O(max_reg) operation to reset these vectors. That problem is
> also addressed by the sequence number trick you are using in your patch,
> so your change should not reintroduce the problem Mark was seeing.
Huh. I might add that if we are using a fixed-sized hash table, we
would have long collision chains when we have a huge number of
registers, causing look-ups to slow down.
> Uhh, can't we just allocate the array once at the start of cse_main
> (where we know the highest current register number, NREGS) and
> deallocate it when we're done? That shouldn't be too much overhead, and
> we wouldn't keep stuff allocated while we're not using it.
I could do that, but can I try it after this patch is installed? (I
am not going to go away after this patch is installed. :-)
Technically, if we have n functions in a module, each of which uses n
registers, the total cost of array initialization would be quadratic
in n. IMHO, as long as I am making the compiler monitonically faster,
people should be happy.
> Also, since we're currently not freeing cse_reg_info entries, total
> memory usage should not be much (if at all) increased, if the assumption
> is correct that the register numbers which are actually used aren't too
Yes, the increase should be at most twice in terms of the number of
entries because I am doubling the array size, but note that each entry
is smaller. On 32-bit machines, the size of each entry was 28 bytes,
but my patch makes it 20 bytes.