As a maintainer of the GCC register allocator (RA), I naturally have a keen interest in the register allocators used in various industrial compilers. For some compilers, like LLVM and Cranelift, there is sufficient documentation, including papers and presentations, to gain a deep understanding of their register allocators (RAs).
Unfortunately, this is not the case for the Go compiler. To gather information about the RA in the Go compiler, I had to delve into its source code. This article outlines my findings.
Go’s register allocator: A high-level view
In summary, the current Go register allocator operates on SSA (Static Single Assignment). The entire Go compiler optimization pipeline operates on SSA.
Taking a broader view, the current Go register allocator comprises the following components (passes), shown in Figure 1 and described below.
Figure 1: Components within the current Go register allocator. Critical edge elimination in the control flow graph (CFG) is a prerequisite for Go’s register allocator. During its operation, the Go RA needs to insert various instructions on CFG edges. In the final program, there are no CFG edges, so the instructions must be placed at the start of the basic block (BB) that is the edge destination or at the end of the BB that is the edge source.
To ensure the correctness of the result code, we need to split a critical edge, creating a BB with one input and one output edge, as shown in Figure 2.
Figure 2: Basic blocks with one input and one output edge. Flagalloc deals with conditional code value allocation, which is not crucial for performance. Live analysis generates data for Go garbage collection based on register allocation result.
Here, our focus is on regalloc and stackalloc.
Regalloc
... continue reading