Brussels / 3 & 4 February 2018


Valgrind register allocator overhaul

Register allocator is a key component in Valgrind's VEX subsystem. Superficially it only translates virtual registers to the real ones. But is that really all? What actually happens under the covers, what algorithms are at play here and what are the constraints under which it operates?

Last year, a major overhaul of the Valgrind VEX register allocator has been done, resulting in a new version v3 which is now used by Valgrind. In addition to a new design, new register allocation algorithms have been also implemented, producing faster and smaller code.

A brief introduction to Valgrind VEX subsystem will be given, to put the register allocator component and its interfaces into context.

Then the operation of register allocator v3 will be presented in an illustrative way, including major data structures. Code snippets from amd64 and aarch64 architectures will be used for examples. Brief comparison with v2 will be also given.

After that, several algorithms will be described which contribute to the success of v3; again showing their operation on graphics.

Finally there will be some time for discussion and feedback gathering.


Ivo Raisr