IRA for GCC 4.4

[Vladimir Makarov]

Peter Bergner wrote:
> On Thu, 2008-04-24 at 20:23 -0400, Vladimir Makarov wrote:
>   
>> Hi, Peter.  The last time I looked at the conflict builder 
>> (ra-conflict.c), I did not see the compressed matrix.  Is it in the 
>> trunk?  What should I look at?
>>     
>
> Yes, the compressed bit matrix was committed as revision 129037 on
> October 5th, so it's been there a while.  Note that the old square
> bit matrix was used not only for testing for conflicts, but also for
> visiting an allocno's neighbors.  The new code (and all compilers I've
> worked on/with), use a {,compressed} upper triangular bit matrix for
> testing for conflicts and an adjacency list for visiting neighbors.
>
>   
IRA also uses an adjacency lists for visiting conflict graph neighbors 
(they contain conflict allocnos only of the same cover classes).
> The code that allocates and initializes the compressed bit matrix is in
> global.c.  If you remember how a upper triangular bit matrix works, it's
> just one big bit vector, where the bit number that represents the conflict
> between allocnos LOW and HIGH is given by either of these two functions:
> ...
>   

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.
>  
>   
>> I have also another question.  I saw that sparset was used for the 
>> conflict builder.  I tried that too when I worked on YARA project.  I 
>> even wanted to contribute a generic sparset implementation.  But I found 
>> that in general case bitmaps are not worse the sparse sets and much 
>> better if we take  a needed space into account.  May be you have another 
>> impression?  It would be very interesting for me to hear it.  I found 
>> that bitmaps have more advanced design than sparsets.  I always wanted 
>> to find inventors the bitmaps but never tracked them down.
>>     
>
> The sparseset representation is only used for the allocnos_live set.
> The old version was a bit vector to match up with the square bit matrix.
> Since I changed that to save space, I had to reimplement allocnos_live.
> Danny suggested I use a bitmap for that set and I tried it, but I found
> for the particular usage of allocnos_live, a sparseset was noticeably
> faster than bitmaps.  I'll note that the main operations on allocnos_live
> are to add allocnos to the set, remove allonos to the set and iterate over
> the members of the set and occasionally clear the entire set.  These are
> all O(1) operations for the sparseset with fairly low constant factors
> too.  I didn't look too closely, but I'm guessing that the main problem
> with bitmaps for this type of usage was the slower iterating over all
> of the members of the set versus the sparseset.
>
> Obviously, bitmaps are much better than sparsesets wrt space usage, so
> you have to use them sparingly.  You wouldn't want an array of these
> things! :)  But there are use cases where they work very very well.
> The currently "live" set is one such use.  Another use I have found
> where they work well is in the needLoad set used by Briggs' allocator.
>
> Whether you want/should use a sparseset really depends on the number
> and type of set operations your particular usage will see.  I'm sure
> there are many usage cases where bitmaps are superior to sparsesets,
> just like there are usage cases where sparsesets are superior.  I know
> that sounds like a cop-out, but it really does depend on how you're
> going to use it.
>
>   

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.