Re: [patch] cse.c: Speed up cse_reg_info maintainance - Part 2

[Kazu Hirata <kazu at cs dot umass dot edu>]

Hi Bernd,

> 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
>    http://gcc.gnu.org/ml/gcc-patches/1999-03n/msg00806.html
> 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 
> sparse.

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.

Kazu Hirata