Florent Bouchez Tichadou - Compilation : the good, the bad and the ugly

Short abstract : In this presentation, a novel vision of the register allocation problem, and an intermediate representation taken from Jurassic Park.

Somewhat longer abstract : The goal of register allocation is to assign the variables of a program to registers or to memory. Registers are preferred because they are much faster, but whenever there are more variables alive at the same time than R, the number of registers, it is mandatory to spill some of them, i.e., allocate them to memory. Conjointly, coalescing variables, i.e., allocating variables linked by copy instructions to the same register, saves those instructions. For nearly 25 years, the problems of spilling and coalescing have been considered in a single phase of register allocation because they both interact with each other : spilling a variable prevents its coalescing with other variables, but coalescing two variables increases their chances of being spilled.

I will show that it is possible to cleanly separate register allocation into two phases without loss of quality : first spill variables so that the number of variables simultaneously alive is at most R everywhere on the program ; then, allocate all remaining variables to the registers while performing coalescing. This was made possible by the observation that under a special form (the Static Single Assignment (SSA) form) the interference graph of the variables of a program is chordal and not general anymore. Since only spilling can reduce the coloring number of this graph, it can be done first. Then, register allocation is known to be possible and coalescing is performed carefully in order not to increase the coloring number again.

I will then present Tirex, a Textual Intermediate Representation for EXchanging target-level information between compiler optimizers. This allows to factor target-specific compiler optimizations into a single component from multiple compilers. Expressed at a target level, Tirex reduces the run-time cost of JIT compilation and of mixed mode execution, since the program to compile is already in a representation lowered to the level of the target processor. I will briefly outlines how Tirex is a powerful tool that opens research directions in program specialization for VLIW architectures.

The allocation of the "good," "bad," and "ugly" adjectives to their corresponding compilation components are left as an exercise to the attendees.