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

[Daniel Berlin <dberlin at redhat dot com>]

On Fri, 9 Feb 2001, Michael Matz wrote:

> Hi,
>
> On Thu, 8 Feb 2001, Geert Bosch wrote:
> >   It's been about a week in trying to get them merged properly, work out
> >   problems, etc.
> >
> >   Michael can successfully bootstrap on x86, and make check shows we are in
> >   *very* good shape (over 14000 passes).
> >
> >   I can successfully bootstrap on PPC.
> >
> >   So just hold on a little longer.
> >
> > Thanks for the update, great news! I'll hold my breath... :-)
>
> But at the first time don't expect any performance improvements.  Not in
> compile time, which might get horrible,

This reminds me, I have a compressed bitvectors class i implemened to
fix the huge memory usage problem for the interference graph.


It was based on a comprssed bitvector class someone else implemented
for a control depdence algorithm.

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.


The compression is staggering. An interference graph that would normally
take up 300 meg takes up about 100k.
The bitvector is implemented as a list of integers.
The first integer
in the list is 0 or 1, indicating whether the bitvector starts
with a 0 bit or a 1 bit.  The other integers in the list are the
lengths of the consecutive platforms of equal bits.  For example,
figure 3(a) shows how a simple bitvector of length 16 can be
compactly represented.  Note that the sum of all the numbers after the
initial '0' is 16.  In fact, since the length of the bitvector is known,
we can even forget the last integer in the list, which saves another 4
bytes for every row.  Figure 3(b) shows the result.

A bitvector of all 0's (or all 1's) is simply represented by a list
containing only a 0 (or 1) at the start.

   ---
   Figure 3:

   a) Example bitvector of length 16.

      ...*...***.*****
      compressed form: 0 3 1 3 3 1 5

      (Read it like this: start with 3 zeros, then 1 one,
      then 3 zeros, then 3 ones, then 1 zero, then 5 ones.)

   b) Knowing the bitvector's length allows us to strip off
      the final integer.

      ...*...***.*****
      compressed form: 0 3 1 3 3 1

   c) Finding the value of bit number 8 requires iteration
      through the vector.  Bit numbers start at 0.

      First, 3 zeros.  Since 8 > 3, we continue.
      Then,  1 one.    Since 8 > (3+1), we continue.
      Then,  3 zeros.  Since 8 > (3+1+3), we continue.
      Then,  3 ones.   Since 8 <= (3+1+3+3), the bit's value is 1.



As lon gas you have long rows of 1's and 0's, which interference graphs do
(because hings ten to interfere with their neighbors, and maybe a few
globals, but nothing else), it'll be faster to perform the various
operations (and, or, negate.  negate is O(1), just switching the first
bit. and is O(the number of integers in the list) as is or.) on the list
than the entire uncompressed  bitvector you would normally use.

So it's a win win situation.

  >and in situations with lot
> spilling (x86 comes to mind) also not in run time, as currently the spill
> code is in no way optimized, coalesced moves are not deleted, sometimes
> multiple spills/reloads are inserted for the same register, sometimes dead
> spills into stack slots just overwritten one insn later happen and so on
> ;)  I just want to give you a warning ;)  These problems will of course be
> fixed, it just takes a little time; at least it basically works.
>
>
> Ciao,
> Michael.
>