Debian Codegraph @

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

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