[LLVMdev] The PBQP Allocator: Status update, and who might want to use it.

[Lang Hames]

Hi Duncan,

>> New PBQP solver.
>
> nice!  Any chance of a quick summary of the state of the pbqp allocator and
> who might want to use it?

Sure. Here's an update, broken into three handy sections:


Summary for LLVM users:
---

PBQP is a heavyweight register allocator. A quick, not-at-all
scientific look at SPEC2006 shows that compiling with -regalloc=pbqp
increased runtime speed over the entire suite by 1% (vs LLVM's
"linear" scan), at a cost of 35% longer compile time (yes - total
compile time).

The PBQP allocator seems reasonably solid. It compiles all benchmarks
in the llvm test-suite project on my x86-64 system, and has compiled
all benchmarks on x86-32 when I've tested it. Other architectures are
less tested, but should be supported as well.

If anyone wants to try for an extra few percent speedup and doesn't
mind longer compiles, I'd recommend giving the -regalloc=pbqp option a
try. I'd really welcome any feedback on successes, failures, bugs and
other issues.


Summary for backend implementers:
---

The other target audience for PBQP is people who want to implement a
backend for an architecture with an unusual register file. If you've
got an odd architectural feature to model (one that's not currently
handled by LLVM) then the easiest way to get up and running with it is
probably to hack up RegAllocPBQP.cpp to introduce your feature into
the cost model. For examples on modeling different features I'd check
the papers referenced in RegAllocPBQP.cpp:

(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.


Details for the curious:
---

Partitioned Boolean Quadratic Problems (PBQP) are a form of Quadratic
Assignment Problem. The PBQP allocator (lib/CodeGen/RegAllocPBQP.cpp)
works by constructing PBQP instances representing register allocation
problems, passing these instances to LLVM's PBQP solver to get a
solution, then mapping the solution back to a register allocation. The
cost model available in PBQP facilitates easy modeling of a wide range
of architectural features and irregularities (e.g. Multiple classes,
complex aliasing, register pairing).

This recent commit leaves the allocator (PBQP<->regalloc mapping)
essentially unchanged, but makes significant changes to the solver.

The main features of the new solver are:
1) It's significantly less memory hungry.
2) It fixes a corner case discovered by the PIC16 team. See the "Crash
in the PBQP Allocator" thread in the mailing list.
3) It's a lot easier to understand and extend.

I'll be working to further improve the speed and memory overhead of
the solver. I also hope to introducing a splitting mechanism, either
as a pass before register allocation or a component of PBQP, to free
the allocator to find better quality allocations.

I'll post to the list as these features are implemented.

Cheers,
Lang.