Re: [dataflow][patch] Convert conflict graph to lower triangular bit matrix

[Joern RENNECKE <joern dot rennecke at st dot com>]

Michael Matz wrote:

> I also never tried implementing the conflicts as hashed lists (so that the 
> bitmaps for fast existence tests wouldn't be needed), because removing 
> conflicts from that structure is harder,
You could replace an entry for a conflict with a special 'deleted' 
entry; when
for the existence of an entry, the deleted entry would be handled like 
an ordinary
one (i.e. a potential collision), but it could be re-used when 
allocating a new entry
at that hash location.

Something to keep in mind, though, is that registers tend to have good 
locality after
register generation, i.e. there are lots of temporaries that live only 
in one basic block.
This should make bitmaps well-suited to operate on these regsets.
We probably loose some of that locality when optimizers add new 
registers and
make other registers unused.  There are possible way to improve that, 
e.g. reserving
some registers in each basic block for future allocations by optimizers 
(the number
is probably best determined as a ratio of originally allocated registers 
to reserved
registers), or re-using registers where the usage count has reached zero 
- with a possible
mode change - in an optimization that operates on the basic block for 
with the
register has been allocated initially.