Re: IRA for GCC 4.4

[Peter Bergner <bergner at vnet dot ibm dot com>]

On Mon, 2008-04-28 at 16:01 -0400, Vladimir Makarov wrote:
> Thanks, Peter.  That was clever and email is very enlightening.  I have 
> analogous idea for more compact conflict matrix representation.  IRA 
> builds allocno live ranges first (they are ranges of program points 
> where the allocno lives).  I can use this information for fast searching 
> potential conflicts to sort the allocnos.  Probably the matrix will be 
> even more compact because live ranges contain more detail info than 
> basic blocks where the local allocnos live.  For example, the ranges 
> even can show that allocnos local in the same block will never 
> conflicts.  It means that matrix even for fppp can be compressed.

You say you use your analogous idea now?  Can you point me to the code?
I thought I heard you (maybe someone else?) that your conflict information
was much bigger than old mainline.  If this is true and you are compacting
the bit matrix like I am, why is it so big?


> I tried to use sparsets for the same purposes (only for maintaining and 
> processing allocnos currently living).  But usage of sparsets for this 
> purposes gave practically nothing (I had to use valgrind lackey to see 
> the difference).  Therefore I decided not to introduce the additional 
> data and use just bitmaps for this.
> 
> Sparsets already exists in a compiler.  I am thinking about their usage 
> too.  May be you have a benchmark where the sparsets give a visible 
> compiler speed improvement (my favorite was combine.i).  I'd appreciate 
> if you point me such benchmark.  It could help me to make a decision to 
> use sparsets.

Yes, I added the sparseset implementation that has been in since gcc 4.3.
Did you use my sparseset implementation or did you write your own for your
tests?  I don't recall which file(s) I saw the difference on.  All I recall
is I tried it both ways, saw a difference somewhere and promptly threw the
slower code away along with which file(s) I saw the difference on.  Sorry I
can't be of more help.

Given how sparsesets are implemented, I cannot see how they could ever be
slower than bitmaps for the use of "live", but I can see how they might be
faster.  That said, if your allocator is spending enough time elsewhere,
then I can easily imagine the difference being swamped such that you don't
see any difference at all.


Peter