Calling Conventions as Precolored Constraints on the Graph

An allocator that knows nothing about the ABI produces code that works until the first call. The convention partitions the register file into three sets with different lifetimes and different owners: registers that carry arguments in, registers that carry results out, and registers that a callee must preserve across the call. Each partition becomes a constraint on the interference graph, and the constraints are not uniform: some are hard edges that make an assignment impossible, others are costs that make an assignment expensive. Distinguishing the two is what keeps the allocator from spilling values it did not need to spill.

The three sets and who pays for them

On the System V AMD64 convention, integer arguments go in rdi, rsi, rdx, rcx, r8, r9 in that order, and the return value comes back in rax with a second value in rdx. Registers rbx, rbp, r12 through r15 are callee-saved: a function that uses one must restore the caller’s value before returning. Everything else, namely rax, rcx, rdx, rsi, rdi, and r8 through r11, is caller-saved, meaning the callee may destroy it freely and the caller must not assume it survives a call. AArch64 has the same structure with different names: x0 through x7 carry arguments and x0 carries the first return value, x19 through x28 are callee-saved, and the rest are caller-saved.

The asymmetry is deliberate and is the whole point of the split. Making every register callee-saved would force every function to save and restore the ones it touches, which costs two memory operations per register per call. Making every register caller-saved would force every caller to save anything it needs across a call, which costs the same. The convention splits the difference: a few registers are cheap for the caller (it can keep values across calls in the callee-saved set), a few are cheap for the callee (it can use scratch registers without saving), and leaf functions, which make no calls, pay nothing at all.

From the allocator’s perspective the split appears as a cost. A value assigned to a callee-saved register requires a save in the prologue and a restore in the epilogue, unless the function is a leaf and the register is never live across a call. The cost comparison is the same one that drives spill decisions, and the two costs are often traded against each other directly. A value assigned to a caller-saved register requires a save and restore around every call at which it is live. The two costs pull in opposite directions, and the allocator places each value where its lifetime pattern makes it cheapest: values live across many calls belong in callee-saved registers, values that die before the next call belong in caller-saved ones.

Precolored nodes and the edges they create

Physical registers enter the graph as precolored nodes, as described in the construction step, and the ABI adds edges to them in three places.

The first is at the call instruction itself. A call implicitly defines every caller-saved register, because the callee may write them. The live-out set of the call therefore includes every value live after it, and the definition rule adds an edge from each caller-saved register to each such value. The effect is that any value live across a call interferes with all caller-saved registers, which forces it into a callee-saved register or into memory. This is not an over-approximation to be optimized away; it is the correct model of a call whose callee is unknown. A compiler with whole-program knowledge can refine it for direct calls to functions whose clobber sets are known, and link-time optimization does exactly that.

The second is at argument passing. Before a call, the argument values must be in specific registers. The instruction sequence that moves them there is a parallel copy, and the allocator must either arrange for the argument values to already be in those registers by assigning them there, or insert moves. Assigning them there is the better outcome and is achieved by coalescing the argument value with the precolored argument register, using the asymmetric form of the George test: the virtual register can adopt the fixed color, but the fixed register cannot be renamed.

The third is at the function boundary. Incoming argument registers are live on entry, and they interfere with everything live at the entry point. The return register is defined at each return, and it interferes with everything live at the return, which in a well-formed function is nothing except the values needed to compute the return value itself. Return sites are therefore cheap in the graph, and the expensive site is the call in the middle of a long live range.

The parallel copy at the call boundary

Arguments are not independent moves. f(a, b) with a in rsi and b in rdi requires swapping the two registers, and a sequential implementation of the swap destroys one of the values. The allocator must recognize that the set of moves before a call is a parallel copy and schedule it correctly: moves whose destinations are not sources can be emitted in any order, and cycles require a temporary.

The scheduling problem is a graph problem in its own right. Each move is an edge from source register to destination register; the edges form paths and cycles. A path is emitted from its end backward: the move whose destination is not any other move’s source goes first, then the move that writes its source, and so on. A cycle needs one register broken out into a temporary, and the cycle is then a path. On x86-64, xchg can swap two registers without a temporary, but it is not free and the allocator usually prefers a scratch register when one is available.

The same problem appears at the return boundary when a function returns a value computed in a register other than rax. The move into rax is a single move, not a parallel copy, but it must happen before the epilogue restores the callee-saved registers, because the restore would overwrite a register the return value is still being computed in. Ordering constraints of this kind are why the allocator’s output feeds a final scheduling pass rather than being the last word on instruction order.

Modeling the callee-saved cost

The cost of deciding to use a callee-saved register is a step function rather than a per-value charge. Saving rbx costs two memory operations in the prologue and epilogue, and those two operations cover every value assigned to rbx for the whole function. A function that uses four callee-saved registers pays eight memory operations total, not eight per value. The first value moved into the callee-saved set therefore pays the whole save, and any further value placed in a register already saved pays nothing extra; that non-linearity is what the flat graph model cannot represent.

The standard approximation is to treat the prologue and epilogue saves as a fixed cost charged to the function rather than to individual values, and to let the allocator use callee-saved registers freely once it has decided to use one. A refinement charges the save to the values that are live across calls, on the theory that those are the ones that forced the register’s use, and lets the allocator compare that cost against the cost of spilling. Neither model is exact; both are better than treating callee-saved registers as unavailable, which is what a naive allocator does when it precolors them and adds edges to everything.

The prologue itself is a constraint on the allocator’s output. The saves must happen before any value is written to the register, and the restores must happen after the last read. If the allocator assigns a value to rbx and the value is live from the first instruction, the save must precede the first instruction, which means the prologue is not a fixed sequence but a sequence whose length depends on the allocation. Backends handle this by allocating the prologue after the register assignment is known, which is why the frame layout and the register assignment are computed together.

Registers the convention reserves

Three registers are effectively unavailable for general values on AMD64, and each for a different reason.

A value assigned to rsp would be destroyed by the next push or call. The allocator models this by precoloring rsp as a node that never takes part in simplification and by recording a definition of rsp at every instruction that writes it, so every value live out of such an instruction gains an edge to it. In practice that means every value live across a call, because the call writes the return address to the stack. The result is that rsp is unavailable to any value with a nontrivial lifetime, and treating it this way is correct rather than conservative.

The frame pointer rbp is callee-saved and is used as the base for frame-relative addressing when the frame size is dynamic or when the debug information requires a stable frame. When it is used as a frame pointer, the allocator cannot assign values to it; when the frame is static and unwinding is not needed, it is a general callee-saved register. The choice is a function-level flag, and it is why the same code can spill differently depending on whether frame pointers are enabled.

The flags register is defined by every comparison and arithmetic instruction and is not addressable as a general operand. Values that need to survive across a flag-setting instruction cannot live in it, which is automatic, since the flags are not a value the allocator can assign, but the interaction matters for instruction selection, which must schedule comparisons so that the flags are consumed before being overwritten.

Vector and floating-point files

The same structure repeats in the vector register file, with a separate argument sequence and a separate callee-saved set. On AMD64 the first eight vector arguments go in xmm0 through xmm7, and every vector register is caller-saved in the ABI, so a value live across a call must be spilled or held in a callee-saved general-purpose register. The allocator therefore treats the vector file as a second, independent coloring problem with its own K, and the two problems are coupled only at the points where a value must move between files, as in an integer-to-float conversion, which requires a destination register in the vector file.

The coupling is a source of spills that are easy to miss. A conversion instruction reads one integer register and writes one vector register, so the source value must be live in the integer file at the instruction and the result is born in the vector file there; a value from the other file that is live across that instruction is competing for registers at the same point, which the graph sees as an edge only if both files share one graph. Allocators that colour the files independently and then insert moves handle this correctly but produce extra moves; allocators that build a single graph with cross-file edges handle it exactly and pay a larger graph.

A constraint table for the AMD64 integer file

Register	Role	Preserved by callee
rax	return value, scratch	no
rbx	general	yes
rcx	4th argument, scratch	no
rdx	3rd argument, 2nd return	no
rsi	2nd argument	no
rdi	1st argument	no
rbp	frame pointer or general	yes
rsp	stack pointer	yes
r8	5th argument	no
r9	6th argument	no
r10, r11	scratch	no
r12–r15	general	yes

The table is the allocator’s view of the ABI, and the two facts it encodes are that nine registers are unavailable as long-lived storage across calls (rax, rcx, rdx, rsi, rdi, r8 through r11) and that five are available at the price of a prologue save (rbx and r12 through r15, with rbp usable as a sixth only when it is not the frame pointer). A function that needs more than five values live across calls must spill regardless of how good the coloring is, because the constraint lives in the convention rather than in the algorithm. That is the practical argument for passing arguments in registers rather than on the stack and for keeping the callee-saved set as large as the encoding allows: every additional callee-saved register raises the ceiling on how much state a function can keep live across a call without touching memory.

Alignment is the last constraint the convention imposes and the one least visible in the graph. The stack must be 16-byte aligned at the call boundary on AMD64, which means the prologue’s subtraction from rsp must account for the return address and for any pushes, and the allocator’s spill slots must not disturb the alignment. A frame whose layout leaves an odd number of 8-byte slots unpadded would break that requirement, so the frame is padded, and the padding is not a value the allocator can color; it is a frame-layout decision made after the assignment, which is why frame layout and register assignment are computed together rather than strictly in sequence.