[LLVMdev] PBQP allocator progress.

[Lang Hames]

Hi everyone,

This is a quick status update regarding the PBQP (Partitioned Boolean
Quadratic Programming) register allocator. A quick overview of the
project: PBQP is a heavyweight allocation technique intended for
native code compilation, and compilation of performance critical
sections. It works by modeling register allocation problems as PBQP
problems, solving these using a generic solver, and mapping the result
back to an allocation. More details can be found in papers [1] and [2]
listed at the end of this email.

As of the most recent patch this allocator is able to compile all
SingleSource, MultiSource and CINT2006 benchmarks which can be
compiled with the linear scan allocator (at least on my Linux/AMD64
box). Coalescing between vregs of the same class is now supported, as
is stack slot coloring. Performance of native code generated is about
the same as for linear scan, compile times are currently much longer.
It's early days for this allocator though, and I'll be looking to
improve on both these aspects in the coming months. (Experiments
conducted by Fernando Magno Quinto Pereira and Jens Palsberg at UCLA,
published in [3], using an earlier prototype of this allocator showed
an average of 5% runtime speedup for the SPEC2000 benchmarks when
compared to Linear Scan (under LLVM 1.9). Hopefully we can get back to
that, and beyond.)

So to anyone who wants to tinker, improve or help out with testing -
please do. Questions, comments and bug reports are most welcome (I'm
especially keen to know how this allocator holds up on other
architectures). You can invoke this allocator by passing
"-regalloc=pbqp" to llc or lli.

Cheers,
Lang.

Papers:

[1] Hames, L. and Scholz, B. 2006. Nearly optimal register allocation
with PBQP. In Proceedings of the 7th Joint Modular Languages
Conference (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA.
346-361.

[2] Scholz, B., Eckstein, E. 2002. Register allocation for irregular
architectures. In Proceedings of the Joint Conference on Languages,
Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New
York, NY, USA, 139-148.

[3] Quintão Pereira, F. M. and Palsberg, J. 2008. Register allocation
by puzzle solving. In Proceedings of the 2008 ACM SIGPLAN Conference
on Programming Language Design and Implementation (Tucson, AZ, USA,
June 07 - 13, 2008). PLDI '08. ACM, New York, NY, 216-226.