Register Spilling and Live-Range Splitting for SSA-Form Programs

Article attempts to adapt an algorithm that excels at scheduling registers in a single linear block, to a graph. It does this by putting lists of liveness requirements on each block, with variables sorted by the number of opcodes until their next use.

Spill code: moves data from a register to memory to free the register for use.

SSA form: single assignment form. a way to rewrite software so each temporary value is assigned exactly once. reassignment creates a new "version" of the value which is used going down.

In SSA form, register demand is equal to maximum register pressure.

Control flow graph: arranging code in to unique blocks; for example an if/else statement breaks in to two nodes and rejoins to one node after. An if block still breaks in to two nodes, with one edge skipping the IF and the other edge through it. Then both join the block afterward and so on. Loops cause a block of code to get split and an edge back to itself. Gotos can make the graph go to absolute hell in a handbasket.

Spill slot: determine how many variables in total will need to be spilled in a function. Give them a specific index in this array. When spilling a value you assign it to this memory address and reloading you copy out of it. (This process avoids having to do complex annoyances like stack simulation to figure out where the value is when you need it.)

Use of the "Min algorithm" gives very good register allocations on a chunk of linear code. It does this by preferring to spill values which have the furthest next use, since those will remain unused for the longest period of time.

Using this on control flow graphs is tricky. A value has an infinite next use if not used in the current block. But it might be used in the next block--so you have to check how far away in blocks the next use will be.

Each block maintains a list of values that must be "live" in a register. Any jumps in to the block must insert spill/reload code if they have scuffed a variable that is live in the block. If the variable was not live in the source or target block, though, no action must be taken.