Re: Optimal Register Allocators in Use?

Vladimir Makarov <vmakarov@redhat.com>
13 Sep 2004 10:47:51 -0400

          From comp.compilers

Related articles
Optimal Register Allocators in Use? koes@cmu.edu (2004-09-03)
Re: Optimal Register Allocators in Use? vmakarov@redhat.com (Vladimir Makarov) (2004-09-13)
| List of all articles for this month |

From: Vladimir Makarov <vmakarov@redhat.com>
Newsgroups: comp.compilers
Date: 13 Sep 2004 10:47:51 -0400
Organization: Red Hat, Inc.
References: 04-09-022
Keywords: registers, optimize
Posted-Date: 13 Sep 2004 10:47:51 EDT

David Koes wrote:
> Hi, I'm doing some research on register allocation and was wondering
> if anyone is familiar with optimal register allocators being used
> outside of academia.
>
> By optimal register allocator I'm thinking along the lines of:
>
> Register allocation for irregular architectures
> http://portal.acm.org/citation.cfm?id=513854


This approach tries to describe register allocation as a solution of
PBQP (partitioned boolean quadratic optimization problem). This is a
specific form of the quadratic assignment problem (QAP). This
approach describes adequately register assignment for two-operand
insns of irregular register file architectures and register
coalescing. As an integer linear programming (non-integer linear
programming was proven to be a polynomial time task more 25 years ago
by a russian mathematician) QAP is NP-complete task. But in reality
QAP is much more complex than ILP of the same size.


I've tried approach described in the article in gcc recently. Optimal
solution is not acceptable (with compilation time point of view) even
for small tests. The heuristic for solving PBQP proposed in the
article (I worked long time and implemented many tricks to speed it
up) is also too slow to be used in an industrial compiler even for
small register file architectures (like x86). The compilation time
increases enourmously for architectures with modest (powerpc) or big
(itanium) register files. The problem is that the PBQP solution needs
to work on register basis not register class basis.


I had practically the same result as gcc original register allocator
(which has very constrained coalsecing, rematereliazation, and live
range spliting) on SPECINT (although the problem could be in reload
pass of gcc which reconsiders the decision of gcc register allocator).
Even so QAP (or PBQP) does not describe the following tasks solved by
a modern register allocator:


1. Register live range splitting


2. Good (or optimal) placement of spill/restore code.


3. More than two-operand constraints for register classes (gcc model
of insn description permits to describe any combination of possible
register classes for insn with any number of operands).


4. Register rematerialization.


> Precise register allocation for irregular architectures
> http://portal.acm.org/citation.cfm?id=291002
>
> Has anyone used such an approach to compile code for a shipping
> product? When is the compile-time/code-quality tradeoff worthwhile?




This approach is more fast to solve the task optimally than QAP. But
even the best commercial LP solvers are too slow for moderate
benchmarks. Although ILP describes adequately placement of
spill/restore code, it can not describe the rest of tasks mentioned
above plus register coalescing.


There is also an interesting register allocation task which could
solved optimally during polynomial time. It is a interprocedural
register allocation (that is what register allocator should do for
architectures with big register files like itanium). This task could
be transformed into a known combinatorial problem (finding maximum
weight k-antichain sequence in graph). You can read it in
Kurlander/Fisher's article "Minimal cost interprocedural register
allocation".


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.