Re: [new-regalloc] What is the status on current sources

[Michael Matz <matzmich at cs dot tu-berlin dot de>]

Hi,


On Fri, 9 Feb 2001, Daniel Berlin wrote:
> 
> This reminds me, I have a compressed bitvectors class i implemened to
> fix the huge memory usage problem for the interference graph.
> [.. description of it ...]

I once (looong ago, as I wrote still DOS demos ;) ) had something similar
(although in Pascal).  We could very well use such a thing.  I guess,
we'll want to conditionalize it's use on max_reg_no being too big (as,
say, 1000 pseudos are taking only 122 KB in the interference graph, which
is acceptable IMHO).  To test for membership more quickly we could even
employ a small hash-table mapping from (0..max_regno-1) to
(0..small_number), and a [small_number] bitset (so that, if bit[hash(i)]
is _not_ set, than i is not in the list; if bit[has(i)] is set, nothing is
known, and it must be searched)

> The only operation that i slower than uncompresssed bitvectors is
> testing/setting individual bts.
> (pardon my spelling, i'm being murdered by latency here.)
> And this is actually not true if you have very large bitvectors, since
> iterating through a short list of integers is faster than iterating
> through an array of thousands of wordrs.

For testing in bit-vectors no iteration is needed ;)  You may mean an
operation like do_for_all_bits_set(), for which the above is very true ;)
(Note, that for that we have the conflicts[] arrays.  We'll need some
experiments, may be we can exclusively use the better bitset above).


Ciao,
Michael.