| 1 |
package regalloc |
| 2 |
|
| 3 |
import "fmt" |
| 4 |
|
| 5 |
// These interfaces are implemented by ISA-specific backends to abstract away the details, and allow the register |
| 6 |
// allocators to work on any ISA. |
| 7 |
|
| 8 |
type ( |
| 9 |
// Function is the top-level interface to do register allocation, which corresponds to a CFG containing |
| 10 |
// Blocks(s). |
| 11 |
// |
| 12 |
// I is the type of the instruction, and B is the type of the basic block. |
| 13 |
Function[I Instr, B Block[I]] interface { |
| 14 |
// PostOrderBlockIteratorBegin returns the first block in the post-order traversal of the CFG. |
| 15 |
// In other words, the last blocks in the CFG will be returned first. |
| 16 |
PostOrderBlockIteratorBegin() B |
| 17 |
// PostOrderBlockIteratorNext returns the next block in the post-order traversal of the CFG. |
| 18 |
PostOrderBlockIteratorNext() B |
| 19 |
// ReversePostOrderBlockIteratorBegin returns the first block in the reverse post-order traversal of the CFG. |
| 20 |
// In other words, the first blocks in the CFG will be returned first. |
| 21 |
ReversePostOrderBlockIteratorBegin() B |
| 22 |
// ReversePostOrderBlockIteratorNext returns the next block in the reverse post-order traversal of the CFG. |
| 23 |
ReversePostOrderBlockIteratorNext() B |
| 24 |
// ClobberedRegisters tell the clobbered registers by this function. |
| 25 |
ClobberedRegisters([]VReg) |
| 26 |
// LoopNestingForestRoots returns the number of roots of the loop nesting forest in a function. |
| 27 |
LoopNestingForestRoots() int |
| 28 |
// LoopNestingForestRoot returns the i-th root of the loop nesting forest in a function. |
| 29 |
LoopNestingForestRoot(i int) B |
| 30 |
// LowestCommonAncestor returns the lowest common ancestor of two blocks in the dominator tree. |
| 31 |
LowestCommonAncestor(blk1, blk2 B) B |
| 32 |
// Idom returns the immediate dominator of the given block. |
| 33 |
Idom(blk B) B |
| 34 |
|
| 35 |
// LoopNestingForestChild returns the i-th child of the block in the loop nesting forest. |
| 36 |
LoopNestingForestChild(b B, i int) B |
| 37 |
// Pred returns the i-th predecessor of the block in the CFG. |
| 38 |
Pred(b B, i int) B |
| 39 |
// Succ returns the i-th successor of the block in the CFG. |
| 40 |
Succ(b B, i int) B |
| 41 |
// BlockParams returns the virtual registers used as the parameters of this block. |
| 42 |
BlockParams(B, *[]VReg) []VReg |
| 43 |
|
| 44 |
// Followings are for rewriting the function. |
| 45 |
|
| 46 |
// SwapBefore swaps the two virtual registers at the end of the given block. |
| 47 |
SwapBefore(x1, x2, tmp VReg, instr I) |
| 48 |
// StoreRegisterBefore inserts store instruction(s) before the given instruction for the given virtual register. |
| 49 |
StoreRegisterBefore(v VReg, instr I) |
| 50 |
// StoreRegisterAfter inserts store instruction(s) after the given instruction for the given virtual register. |
| 51 |
StoreRegisterAfter(v VReg, instr I) |
| 52 |
// ReloadRegisterBefore inserts reload instruction(s) before the given instruction for the given virtual register. |
| 53 |
ReloadRegisterBefore(v VReg, instr I) |
| 54 |
// ReloadRegisterAfter inserts reload instruction(s) after the given instruction for the given virtual register. |
| 55 |
ReloadRegisterAfter(v VReg, instr I) |
| 56 |
// InsertMoveBefore inserts move instruction(s) before the given instruction for the given virtual registers. |
| 57 |
InsertMoveBefore(dst, src VReg, instr I) |
| 58 |
} |
| 59 |
|
| 60 |
// Block is a basic block in the CFG of a function, and it consists of multiple instructions, and predecessor Block(s). |
| 61 |
// Right now, this corresponds to a ssa.BasicBlock lowered to the machine level. |
| 62 |
Block[I Instr] interface { |
| 63 |
comparable |
| 64 |
// ID returns the unique identifier of this block which is ordered in the reverse post-order traversal of the CFG. |
| 65 |
ID() int32 |
| 66 |
// InstrIteratorBegin returns the first instruction in this block. Instructions added after lowering must be skipped. |
| 67 |
// 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. |
| 68 |
InstrIteratorBegin() I |
| 69 |
// InstrIteratorNext returns the next instruction in this block. Instructions added after lowering must be skipped. |
| 70 |
// 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. |
| 71 |
InstrIteratorNext() I |
| 72 |
// InstrRevIteratorBegin is the same as InstrIteratorBegin, but in the reverse order. |
| 73 |
InstrRevIteratorBegin() I |
| 74 |
// InstrRevIteratorNext is the same as InstrIteratorNext, but in the reverse order. |
| 75 |
InstrRevIteratorNext() I |
| 76 |
// FirstInstr returns the fist instruction in this block where instructions will be inserted after it. |
| 77 |
FirstInstr() I |
| 78 |
// LastInstrForInsertion returns the last instruction in this block where instructions will be inserted before it. |
| 79 |
// Such insertions only happen when we need to insert spill/reload instructions to adjust the merge edges. |
| 80 |
// At the time of register allocation, all the critical edges are already split, so there is no need |
| 81 |
// to worry about the case where branching instruction has multiple successors. |
| 82 |
// Therefore, usually, it is the nop instruction, but if the block ends with an unconditional branching, then it returns |
| 83 |
// the unconditional branch, not the nop. In other words it is either nop or unconditional branch. |
| 84 |
LastInstrForInsertion() I |
| 85 |
// Preds returns the number of predecessors of this block in the CFG. |
| 86 |
Preds() int |
| 87 |
// Entry returns true if the block is for the entry block. |
| 88 |
Entry() bool |
| 89 |
// Succs returns the number of successors of this block in the CFG. |
| 90 |
Succs() int |
| 91 |
// LoopHeader returns true if this block is a loop header. |
| 92 |
LoopHeader() bool |
| 93 |
// LoopNestingForestChildren returns the number of children of this block in the loop nesting forest. |
| 94 |
LoopNestingForestChildren() int |
| 95 |
} |
| 96 |
|
| 97 |
// Instr is an instruction in a block, abstracting away the underlying ISA. |
| 98 |
Instr interface { |
| 99 |
comparable |
| 100 |
fmt.Stringer |
| 101 |
// Defs returns the virtual registers defined by this instruction. |
| 102 |
Defs(*[]VReg) []VReg |
| 103 |
// Uses returns the virtual registers used by this instruction. |
| 104 |
// Note: multiple returned []VReg will not be held at the same time, so it's safe to use the same slice for this. |
| 105 |
Uses(*[]VReg) []VReg |
| 106 |
// AssignUse assigns the RealReg-allocated virtual register used by this instruction at the given index. |
| 107 |
AssignUse(index int, v VReg) |
| 108 |
// AssignDef assigns a RealReg-allocated virtual register defined by this instruction. |
| 109 |
// This only accepts one register because we don't allocate registers for multi-def instructions (i.e. call instruction) |
| 110 |
AssignDef(VReg) |
| 111 |
// IsCopy returns true if this instruction is a move instruction between two registers. |
| 112 |
// If true, the instruction is of the form of dst = src, and if the src and dst do not interfere with each other, |
| 113 |
// we could coalesce them, and hence the copy can be eliminated from the final code. |
| 114 |
IsCopy() bool |
| 115 |
// IsCall returns true if this instruction is a call instruction. The result is used to insert |
| 116 |
// caller saved register spills and restores. |
| 117 |
IsCall() bool |
| 118 |
// IsIndirectCall returns true if this instruction is an indirect call instruction which calls a function pointer. |
| 119 |
// The result is used to insert caller saved register spills and restores. |
| 120 |
IsIndirectCall() bool |
| 121 |
// IsReturn returns true if this instruction is a return instruction. |
| 122 |
IsReturn() bool |
| 123 |
} |
| 124 |
) |