Register allocation in the Go compiler (2024)
a day ago
- #compiler
- #Go
- #register-allocation
- The Go compiler's register allocator (RA) operates on SSA (Static Single Assignment) form, similar to other optimization passes in the compiler.
- Key components of the Go RA include critical edge elimination, flagalloc for conditional code value allocation, live analysis for garbage collection, regalloc, and stackalloc.
- Regalloc is the most complex part, processing basic blocks (BBs) in CFG preorder and tracking live values in registers or memory.
- The RA uses heuristics like longest distance to next use for spilling values when registers are unavailable, with distances influenced by BB layout.
- Phi values and their operands must occupy the same location (register or stack), requiring significant handling and potential copies.
- Stack slot allocation optimizes stack usage by sharing slots between non-overlapping SSA values, using a conflict graph for optimization.
- The RA maintains SSA form with special operations (StoreReg, LoadReg, Copy) but produces invalid SSA post-allocation, limiting further optimizations.
- The RA algorithm resembles second-chance bin-packing rather than linear scan, focusing on CFG merge points and spill placement.
- Call ABI assumes all registers are clobbered by calls, leading to inefficient code; using call-saved registers could improve performance.
- Advantages of Go RA include a small codebase, speed, and efficient stack slot sharing, while drawbacks include lack of global view and complex Phi handling.