IRA for GCC 4.4

[Vladimir Makarov]

Kenneth Zadeck wrote:
> Vladimir Makarov wrote:
>> Peter Bergner wrote:
>>> 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 am currently working on bit matrix compression.  It is not 
>> implemented yet.  I hope it will be ready in a week.
>>
> vlad, this seems like the wrong way to go.   i understand that you 
> feel that it is a sign of weakness to use someone else's fully 
> debugged and functional code rather than writing it from scratch, but 
> every one else feels that (a) you could better spend your time working 
> on the other issues that will be relevant to getting this thing in and 
> (b) none of the other reviewers looks forward to just seeing a lot of 
> the same code only different.
Ken, I am far from feeling this way.  I think you persistence to use 
Peter's code is probably from bad knowledge of IRA specifics.  I'll try 
to explain reasons why I am not just using Peter's code:

o number of allocnos in IRA is changed (new allocnos can be added after 
live range splitting, some allocnos can be removed and other allocnos 
can inherent their conflicts during transformation of regional IR into 
plain IR).

o Adding conflicts is done not on just one step.  After building 
conflicts for allocnos, in some time there is a step where conflicts 
from low level region allocnos results in adding conflicts on 
corresponding upper level region allocnos.

o I have info about program points where allocno lives and it can be 
used for building more compressed bit matrix than Peter's one because 
he  uses only bb where local allocnos live.  Using this info permits to 
define in some cases that even two global allocnos or two allocnos local 
in the same BB will never conflict.

o I see a bigger picture how intermediate data used to build compressed 
bit vectors help me to solve -O0 IRA slowness problem (using just the 
reload without any allocation is not a solution).

o IRA uses a bit different approach to traverse all conflicting allocnos 
than Peter's code for adjacency lists.  Instead of bit vector matrix, 
IRA uses bit vectors attached to allocnos.  If the bit vector is smaller 
than adjacency list (some criteria for smallness is used), the adjacency 
list is not formed and the bit vector is used to visit conflicting 
allocnos.  It permits save memory.  On the other hand, it means no 
triangular bit matrix.  And this code was written long before Peter's one.

Taking all this into account, I see much more work and modifications to 
integrate Peter's code into IRA than just compressing bit vectors in 
existing IRA infrastructure.

I hope that this email will help to understand why I am not just using 
Peter's code which I do really like.  It is just code for a different 
allocator.