Debian Codegraph @

internal/engine/wazevo/backend/isa/arm64/machine_regalloc.go

raw
1 package arm64
2
3 // This file implements the interfaces required for register allocations. See backend.RegAllocFunctionMachine.
4
5 import (
6 "github.com/tetratelabs/wazero/internal/engine/wazevo/backend/regalloc"
7 "github.com/tetratelabs/wazero/internal/engine/wazevo/ssa"
8 )
9
10 // regAllocFn implements regalloc.Function.
11 type regAllocFn struct {
12 ssaB ssa.Builder
13 m *machine
14 loopNestingForestRoots []ssa.BasicBlock
15 blockIter int
16 }
17
18 // PostOrderBlockIteratorBegin implements regalloc.Function.
19 func (f *regAllocFn) PostOrderBlockIteratorBegin() *labelPosition {
20 f.blockIter = len(f.m.orderedSSABlockLabelPos) - 1
21 return f.PostOrderBlockIteratorNext()
22 }
23
24 // PostOrderBlockIteratorNext implements regalloc.Function.
25 func (f *regAllocFn) PostOrderBlockIteratorNext() *labelPosition {
26 if f.blockIter < 0 {
27 return nil
28 }
29 b := f.m.orderedSSABlockLabelPos[f.blockIter]
30 f.blockIter--
31 return b
32 }
33
34 // ReversePostOrderBlockIteratorBegin implements regalloc.Function.
35 func (f *regAllocFn) ReversePostOrderBlockIteratorBegin() *labelPosition {
36 f.blockIter = 0
37 return f.ReversePostOrderBlockIteratorNext()
38 }
39
40 // ReversePostOrderBlockIteratorNext implements regalloc.Function.
41 func (f *regAllocFn) ReversePostOrderBlockIteratorNext() *labelPosition {
42 if f.blockIter >= len(f.m.orderedSSABlockLabelPos) {
43 return nil
44 }
45 b := f.m.orderedSSABlockLabelPos[f.blockIter]
46 f.blockIter++
47 return b
48 }
49
50 // ClobberedRegisters implements regalloc.Function.
51 func (f *regAllocFn) ClobberedRegisters(regs []regalloc.VReg) {
52 f.m.clobberedRegs = append(f.m.clobberedRegs[:0], regs...)
53 }
54
55 // LoopNestingForestRoots implements regalloc.Function.
56 func (f *regAllocFn) LoopNestingForestRoots() int {
57 f.loopNestingForestRoots = f.ssaB.LoopNestingForestRoots()
58 return len(f.loopNestingForestRoots)
59 }
60
61 // LoopNestingForestRoot implements regalloc.Function.
62 func (f *regAllocFn) LoopNestingForestRoot(i int) *labelPosition {
63 root := f.loopNestingForestRoots[i]
64 pos := f.m.getOrAllocateSSABlockLabelPosition(root)
65 return pos
66 }
67
68 // LowestCommonAncestor implements regalloc.Function.
69 func (f *regAllocFn) LowestCommonAncestor(blk1, blk2 *labelPosition) *labelPosition {
70 sb := f.ssaB.LowestCommonAncestor(blk1.sb, blk2.sb)
71 pos := f.m.getOrAllocateSSABlockLabelPosition(sb)
72 return pos
73 }
74
75 // Idom implements regalloc.Function.
76 func (f *regAllocFn) Idom(blk *labelPosition) *labelPosition {
77 sb := f.ssaB.Idom(blk.sb)
78 pos := f.m.getOrAllocateSSABlockLabelPosition(sb)
79 return pos
80 }
81
82 // SwapBefore implements regalloc.Function.
83 func (f *regAllocFn) SwapBefore(x1, x2, tmp regalloc.VReg, instr *instruction) {
84 f.m.swap(instr.prev, x1, x2, tmp)
85 }
86
87 // StoreRegisterBefore implements regalloc.Function.
88 func (f *regAllocFn) StoreRegisterBefore(v regalloc.VReg, instr *instruction) {
89 m := f.m
90 m.insertStoreRegisterAt(v, instr, false)
91 }
92
93 // StoreRegisterAfter implements regalloc.Function.
94 func (f *regAllocFn) StoreRegisterAfter(v regalloc.VReg, instr *instruction) {
95 m := f.m
96 m.insertStoreRegisterAt(v, instr, true)
97 }
98
99 // ReloadRegisterBefore implements regalloc.Function.
100 func (f *regAllocFn) ReloadRegisterBefore(v regalloc.VReg, instr *instruction) {
101 m := f.m
102 m.insertReloadRegisterAt(v, instr, false)
103 }
104
105 // ReloadRegisterAfter implements regalloc.Function.
106 func (f *regAllocFn) ReloadRegisterAfter(v regalloc.VReg, instr *instruction) {
107 m := f.m
108 m.insertReloadRegisterAt(v, instr, true)
109 }
110
111 // InsertMoveBefore implements regalloc.Function.
112 func (f *regAllocFn) InsertMoveBefore(dst, src regalloc.VReg, instr *instruction) {
113 f.m.insertMoveBefore(dst, src, instr)
114 }
115
116 // LoopNestingForestChild implements regalloc.Function.
117 func (f *regAllocFn) LoopNestingForestChild(pos *labelPosition, i int) *labelPosition {
118 childSB := pos.sb.LoopNestingForestChildren()[i]
119 return f.m.getOrAllocateSSABlockLabelPosition(childSB)
120 }
121
122 // Succ implements regalloc.Block.
123 func (f *regAllocFn) Succ(pos *labelPosition, i int) *labelPosition {
124 succSB := pos.sb.Succ(i)
125 if succSB.ReturnBlock() {
126 return nil
127 }
128 return f.m.getOrAllocateSSABlockLabelPosition(succSB)
129 }
130
131 // Pred implements regalloc.Block.
132 func (f *regAllocFn) Pred(pos *labelPosition, i int) *labelPosition {
133 predSB := pos.sb.Pred(i)
134 return f.m.getOrAllocateSSABlockLabelPosition(predSB)
135 }
136
137 // BlockParams implements regalloc.Function.
138 func (f *regAllocFn) BlockParams(pos *labelPosition, regs *[]regalloc.VReg) []regalloc.VReg {
139 c := f.m.compiler
140 *regs = (*regs)[:0]
141 for i := 0; i < pos.sb.Params(); i++ {
142 v := c.VRegOf(pos.sb.Param(i))
143 *regs = append(*regs, v)
144 }
145 return *regs
146 }
147
148 // ID implements regalloc.Block.
149 func (pos *labelPosition) ID() int32 {
150 return int32(pos.sb.ID())
151 }
152
153 // InstrIteratorBegin implements regalloc.Block.
154 func (pos *labelPosition) InstrIteratorBegin() *instruction {
155 ret := pos.begin
156 pos.cur = ret
157 return ret
158 }
159
160 // InstrIteratorNext implements regalloc.Block.
161 func (pos *labelPosition) InstrIteratorNext() *instruction {
162 for {
163 if pos.cur == pos.end {
164 return nil
165 }
166 instr := pos.cur.next
167 pos.cur = instr
168 if instr == nil {
169 return nil
170 } else if instr.addedBeforeRegAlloc {
171 // Only concerned about the instruction added before regalloc.
172 return instr
173 }
174 }
175 }
176
177 // InstrRevIteratorBegin implements regalloc.Block.
178 func (pos *labelPosition) InstrRevIteratorBegin() *instruction {
179 pos.cur = pos.end
180 return pos.cur
181 }
182
183 // InstrRevIteratorNext implements regalloc.Block.
184 func (pos *labelPosition) InstrRevIteratorNext() *instruction {
185 for {
186 if pos.cur == pos.begin {
187 return nil
188 }
189 instr := pos.cur.prev
190 pos.cur = instr
191 if instr == nil {
192 return nil
193 } else if instr.addedBeforeRegAlloc {
194 // Only concerned about the instruction added before regalloc.
195 return instr
196 }
197 }
198 }
199
200 // FirstInstr implements regalloc.Block.
201 func (pos *labelPosition) FirstInstr() *instruction { return pos.begin }
202
203 // LastInstrForInsertion implements regalloc.Block.
204 func (pos *labelPosition) LastInstrForInsertion() *instruction {
205 return lastInstrForInsertion(pos.begin, pos.end)
206 }
207
208 // Preds implements regalloc.Block.
209 func (pos *labelPosition) Preds() int { return pos.sb.Preds() }
210
211 // Entry implements regalloc.Block.
212 func (pos *labelPosition) Entry() bool { return pos.sb.EntryBlock() }
213
214 // Succs implements regalloc.Block.
215 func (pos *labelPosition) Succs() int { return pos.sb.Succs() }
216
217 // LoopHeader implements regalloc.Block.
218 func (pos *labelPosition) LoopHeader() bool { return pos.sb.LoopHeader() }
219
220 // LoopNestingForestChildren implements regalloc.Block.
221 func (pos *labelPosition) LoopNestingForestChildren() int {
222 return len(pos.sb.LoopNestingForestChildren())
223 }
224
225 func (m *machine) swap(cur *instruction, x1, x2, tmp regalloc.VReg) {
226 prevNext := cur.next
227 var mov1, mov2, mov3 *instruction
228 if x1.RegType() == regalloc.RegTypeInt {
229 if !tmp.Valid() {
230 tmp = tmpRegVReg
231 }
232 mov1 = m.allocateInstr().asMove64(tmp, x1)
233 mov2 = m.allocateInstr().asMove64(x1, x2)
234 mov3 = m.allocateInstr().asMove64(x2, tmp)
235 cur = linkInstr(cur, mov1)
236 cur = linkInstr(cur, mov2)
237 cur = linkInstr(cur, mov3)
238 linkInstr(cur, prevNext)
239 } else {
240 if !tmp.Valid() {
241 r2 := x2.RealReg()
242 // Temporarily spill x1 to stack.
243 cur = m.insertStoreRegisterAt(x1, cur, true).prev
244 // Then move x2 to x1.
245 cur = linkInstr(cur, m.allocateInstr().asFpuMov128(x1, x2))
246 linkInstr(cur, prevNext)
247 // Then reload the original value on x1 from stack to r2.
248 m.insertReloadRegisterAt(x1.SetRealReg(r2), cur, true)
249 } else {
250 mov1 = m.allocateInstr().asFpuMov128(tmp, x1)
251 mov2 = m.allocateInstr().asFpuMov128(x1, x2)
252 mov3 = m.allocateInstr().asFpuMov128(x2, tmp)
253 cur = linkInstr(cur, mov1)
254 cur = linkInstr(cur, mov2)
255 cur = linkInstr(cur, mov3)
256 linkInstr(cur, prevNext)
257 }
258 }
259 }
260
261 func (m *machine) insertMoveBefore(dst, src regalloc.VReg, instr *instruction) {
262 typ := src.RegType()
263 if typ != dst.RegType() {
264 panic("BUG: src and dst must have the same type")
265 }
266
267 mov := m.allocateInstr()
268 if typ == regalloc.RegTypeInt {
269 mov.asMove64(dst, src)
270 } else {
271 mov.asFpuMov128(dst, src)
272 }
273
274 cur := instr.prev
275 prevNext := cur.next
276 cur = linkInstr(cur, mov)
277 linkInstr(cur, prevNext)
278 }
279
280 func (m *machine) insertStoreRegisterAt(v regalloc.VReg, instr *instruction, after bool) *instruction {
281 if !v.IsRealReg() {
282 panic("BUG: VReg must be backed by real reg to be stored")
283 }
284
285 typ := m.compiler.TypeOf(v)
286
287 var prevNext, cur *instruction
288 if after {
289 cur, prevNext = instr, instr.next
290 } else {
291 cur, prevNext = instr.prev, instr
292 }
293
294 offsetFromSP := m.getVRegSpillSlotOffsetFromSP(v.ID(), typ.Size())
295 var amode *addressMode
296 cur, amode = m.resolveAddressModeForOffsetAndInsert(cur, offsetFromSP, typ.Bits(), spVReg, true)
297 store := m.allocateInstr()
298 store.asStore(operandNR(v), amode, typ.Bits())
299
300 cur = linkInstr(cur, store)
301 return linkInstr(cur, prevNext)
302 }
303
304 func (m *machine) insertReloadRegisterAt(v regalloc.VReg, instr *instruction, after bool) *instruction {
305 if !v.IsRealReg() {
306 panic("BUG: VReg must be backed by real reg to be stored")
307 }
308
309 typ := m.compiler.TypeOf(v)
310
311 var prevNext, cur *instruction
312 if after {
313 cur, prevNext = instr, instr.next
314 } else {
315 cur, prevNext = instr.prev, instr
316 }
317
318 offsetFromSP := m.getVRegSpillSlotOffsetFromSP(v.ID(), typ.Size())
319 var amode *addressMode
320 cur, amode = m.resolveAddressModeForOffsetAndInsert(cur, offsetFromSP, typ.Bits(), spVReg, true)
321 load := m.allocateInstr()
322 switch typ {
323 case ssa.TypeI32, ssa.TypeI64:
324 load.asULoad(v, amode, typ.Bits())
325 case ssa.TypeF32, ssa.TypeF64:
326 load.asFpuLoad(v, amode, typ.Bits())
327 case ssa.TypeV128:
328 load.asFpuLoad(v, amode, 128)
329 default:
330 panic("TODO")
331 }
332
333 cur = linkInstr(cur, load)
334 return linkInstr(cur, prevNext)
335 }
336
337 func lastInstrForInsertion(begin, end *instruction) *instruction {
338 cur := end
339 for cur.kind == nop0 {
340 cur = cur.prev
341 if cur == begin {
342 return end
343 }
344 }
345 switch cur.kind {
346 case br:
347 return cur
348 default:
349 return end
350 }
351 }