Understanding IRA

[Vladimir Makarov]

Ian Bolton wrote:
> Hi Jeff and Vladimir.
>
> Jeff: I'd be interested in trying the patch if you can send it my way.
>
> Vladimir: Today I have seen reasonable improvements on
> progressively-trimmed-down versions of a *single* test case by applying
> some cost adjustments in the case when an operand wants one of our
> bottom registers and IRA is considering giving it an alternative
> register or memory.  I will be experimenting with different values for
> these two new costs and some more test cases tomorrow.
>
> I wonder if the optimal register allocator will just end up being one
> that tries all the algorithms and picks the best output for a given
> case?  When it comes to optimisation, I prefer to bend the rules if at
> all possible!
>
>   
  I did not try progressive register allocator (in which I have some 
doubts) but I did a lot of experiments recently (last year) with ILP 
based register allocators: from simple spill model (which pseudos should 
be spilled) to RA with coalescing, live range splitting, 
rematerialization, and code selection (it needs  models on hard reg 
levels) including some models closed to Apel's and two Wilken's approaches.

  The simplest model can be only used to solve medium-size functions in 
reasonable time (about 10 minutes).  But even this model can not be used 
for function like reload.c::find_reloads.  More complex model problems 
can not be solved even for many tiny benchmarks (like heapsort) in 
reasonable time.  Although I used GLPK which is much slower than the 
best package (CPLEX).  Other algorithms for soliving ILP (like Balas' 
one) are even much worse.  The improvement for the simplest model was 
not significant unless profiling was used (in this case some SPECInt2000 
benchmarks were improved upto 20% on x86).

  In any case, I did not find optimal RA based on ILP is practical.  
About 4 years ago, I tried QAP (quadratic assignment problem) model 
approaches with the same conclusion.  Although I did not try multi 
commodity flow network approach for which there are better specialized 
algorithms because there are no good GPL-based packages for this 
(unfortunately the best one MCF has no such license). It could be an 
interesting research.