1package regalloc
2
3import "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
8type (
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)