Involved Source Filesapi.goreg.go Package regalloc performs register allocation. The algorithm can work on any ISA by implementing the interfaces in
api.go.
References:
- https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/17/Slides17.pdf
- https://en.wikipedia.org/wiki/Chaitin%27s_algorithm
- https://llvm.org/ProjectsWithLLVM/2004-Fall-CS426-LS.pdf
- https://pfalcon.github.io/ssabook/latest/book-full.pdf: Chapter 9. for liveness analysis.
- https://github.com/golang/go/blob/release-branch.go1.21/src/cmd/compile/internal/ssa/regalloc.goregset.go
Package-Level Type Names (total 10)
/* sort by: | */
Type Parameters:
I: Instr
B: Block[I]
F: Function[I, B]
Allocator is a register allocator. DoAllocation performs register allocation on the given Function. Reset resets the allocator's internal state so that it can be reused.
func NewAllocator[I, B, F](allocatableRegs *RegisterInfo) Allocator[I, B, F]
Type Parameters:
I: Instr Block is a basic block in the CFG of a function, and it consists of multiple instructions, and predecessor Block(s).
Right now, this corresponds to a ssa.BasicBlock lowered to the machine level. Entry returns true if the block is for the entry block. FirstInstr returns the fist instruction in this block where instructions will be inserted after it. ID returns the unique identifier of this block which is ordered in the reverse post-order traversal of the CFG. InstrIteratorBegin returns the first instruction in this block. Instructions added after lowering must be skipped.
Note: multiple Instr(s) will not be held at the same time, so it's safe to use the same impl for the return Instr. InstrIteratorNext returns the next instruction in this block. Instructions added after lowering must be skipped.
Note: multiple Instr(s) will not be held at the same time, so it's safe to use the same impl for the return Instr. InstrRevIteratorBegin is the same as InstrIteratorBegin, but in the reverse order. InstrRevIteratorNext is the same as InstrIteratorNext, but in the reverse order. LastInstrForInsertion returns the last instruction in this block where instructions will be inserted before it.
Such insertions only happen when we need to insert spill/reload instructions to adjust the merge edges.
At the time of register allocation, all the critical edges are already split, so there is no need
to worry about the case where branching instruction has multiple successors.
Therefore, usually, it is the nop instruction, but if the block ends with an unconditional branching, then it returns
the unconditional branch, not the nop. In other words it is either nop or unconditional branch. LoopHeader returns true if this block is a loop header. LoopNestingForestChildren returns the number of children of this block in the loop nesting forest. Preds returns the number of predecessors of this block in the CFG. Succs returns the number of successors of this block in the CFG.
Type Parameters:
I: Instr
B: Block[I]
Function is the top-level interface to do register allocation, which corresponds to a CFG containing
Blocks(s).
I is the type of the instruction, and B is the type of the basic block. BlockParams returns the virtual registers used as the parameters of this block. ClobberedRegisters tell the clobbered registers by this function. Idom returns the immediate dominator of the given block. InsertMoveBefore inserts move instruction(s) before the given instruction for the given virtual registers. LoopNestingForestChild returns the i-th child of the block in the loop nesting forest. LoopNestingForestRoot returns the i-th root of the loop nesting forest in a function. LoopNestingForestRoots returns the number of roots of the loop nesting forest in a function. LowestCommonAncestor returns the lowest common ancestor of two blocks in the dominator tree. PostOrderBlockIteratorBegin returns the first block in the post-order traversal of the CFG.
In other words, the last blocks in the CFG will be returned first. PostOrderBlockIteratorNext returns the next block in the post-order traversal of the CFG. Pred returns the i-th predecessor of the block in the CFG. ReloadRegisterAfter inserts reload instruction(s) after the given instruction for the given virtual register. ReloadRegisterBefore inserts reload instruction(s) before the given instruction for the given virtual register. ReversePostOrderBlockIteratorBegin returns the first block in the reverse post-order traversal of the CFG.
In other words, the first blocks in the CFG will be returned first. ReversePostOrderBlockIteratorNext returns the next block in the reverse post-order traversal of the CFG. StoreRegisterAfter inserts store instruction(s) after the given instruction for the given virtual register. StoreRegisterBefore inserts store instruction(s) before the given instruction for the given virtual register. Succ returns the i-th successor of the block in the CFG. SwapBefore swaps the two virtual registers at the end of the given block.
Instr is an instruction in a block, abstracting away the underlying ISA. AssignDef assigns a RealReg-allocated virtual register defined by this instruction.
This only accepts one register because we don't allocate registers for multi-def instructions (i.e. call instruction) AssignUse assigns the RealReg-allocated virtual register used by this instruction at the given index. Defs returns the virtual registers defined by this instruction. IsCall returns true if this instruction is a call instruction. The result is used to insert
caller saved register spills and restores. IsCopy returns true if this instruction is a move instruction between two registers.
If true, the instruction is of the form of dst = src, and if the src and dst do not interfere with each other,
we could coalesce them, and hence the copy can be eliminated from the final code. IsIndirectCall returns true if this instruction is an indirect call instruction which calls a function pointer.
The result is used to insert caller saved register spills and restores. IsReturn returns true if this instruction is a return instruction.( Instr) String() string Uses returns the virtual registers used by this instruction.
Note: multiple returned []VReg will not be held at the same time, so it's safe to use the same slice for this.
Instr : expvar.Var
Instr : fmt.Stringer
RegisterInfo holds the statically-known ISA-specific register information. AllocatableRegisters is a 2D array of allocatable RealReg, indexed by regTypeNum and regNum.
The order matters: the first element is the most preferred one when allocating.CalleeSavedRegistersRegSetCallerSavedRegistersRegSet RealRegName returns the name of the given RealReg for debugging.RealRegToVReg[]VRegRealRegTypefunc(r RealReg) RegType
func NewAllocator[I, B, F](allocatableRegs *RegisterInfo) Allocator[I, B, F]
RegSet represents a set of registers.( RegSet) Range(f func(allocatedRealReg RealReg))
func NewRegSet(regs ...RealReg) RegSet
The pages are generated with Goldsv0.8.2. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @zigo_101 (reachable from the left QR code) to get the latest news of Golds.
