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.
