Debian Codegraph @

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

raw
1 package arm64
2
3 import (
4 "fmt"
5
6 "github.com/tetratelabs/wazero/internal/engine/wazevo/backend/regalloc"
7 "github.com/tetratelabs/wazero/internal/engine/wazevo/ssa"
8 "github.com/tetratelabs/wazero/internal/engine/wazevo/wazevoapi"
9 )
10
11 type (
12 // addressMode represents an ARM64 addressing mode.
13 //
14 // https://developer.arm.com/documentation/102374/0101/Loads-and-stores---addressing
15 // TODO: use the bit-packed layout like operand struct.
16 addressMode struct {
17 kind addressModeKind
18 rn, rm regalloc.VReg
19 extOp extendOp
20 imm int64
21 }
22
23 // addressModeKind represents the kind of ARM64 addressing mode.
24 addressModeKind byte
25 )
26
27 func resetAddressMode(a *addressMode) {
28 a.kind = 0
29 a.rn = 0
30 a.rm = 0
31 a.extOp = 0
32 a.imm = 0
33 }
34
35 const (
36 // addressModeKindRegExtended takes a base register and an index register. The index register is sign/zero-extended,
37 // and then scaled by bits(type)/8.
38 //
39 // e.g.
40 // - ldrh w1, [x2, w3, SXTW #1] ;; sign-extended and scaled by 2 (== LSL #1)
41 // - strh w1, [x2, w3, UXTW #1] ;; zero-extended and scaled by 2 (== LSL #1)
42 // - ldr w1, [x2, w3, SXTW #2] ;; sign-extended and scaled by 4 (== LSL #2)
43 // - str x1, [x2, w3, UXTW #3] ;; zero-extended and scaled by 8 (== LSL #3)
44 //
45 // See the following pages:
46 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/LDRH--register---Load-Register-Halfword--register--
47 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/LDR--register---Load-Register--register--
48 addressModeKindRegScaledExtended addressModeKind = iota
49
50 // addressModeKindRegScaled is the same as addressModeKindRegScaledExtended, but without extension factor.
51 addressModeKindRegScaled
52
53 // addressModeKindRegScaled is the same as addressModeKindRegScaledExtended, but without scale factor.
54 addressModeKindRegExtended
55
56 // addressModeKindRegReg takes a base register and an index register. The index register is not either scaled or extended.
57 addressModeKindRegReg
58
59 // addressModeKindRegSignedImm9 takes a base register and a 9-bit "signed" immediate offset (-256 to 255).
60 // The immediate will be sign-extended, and be added to the base register.
61 // This is a.k.a. "unscaled" since the immediate is not scaled.
62 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/LDUR--Load-Register--unscaled--
63 addressModeKindRegSignedImm9
64
65 // addressModeKindRegUnsignedImm12 takes a base register and a 12-bit "unsigned" immediate offset. scaled by
66 // the size of the type. In other words, the actual offset will be imm12 * bits(type)/8.
67 // See "Unsigned offset" in the following pages:
68 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/LDRB--immediate---Load-Register-Byte--immediate--
69 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/LDRH--immediate---Load-Register-Halfword--immediate--
70 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/LDR--immediate---Load-Register--immediate--
71 addressModeKindRegUnsignedImm12
72
73 // addressModePostIndex takes a base register and a 9-bit "signed" immediate offset.
74 // After the load/store, the base register will be updated by the offset.
75 //
76 // Note that when this is used for pair load/store, the offset will be 7-bit "signed" immediate offset.
77 //
78 // See "Post-index" in the following pages for examples:
79 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/LDRB--immediate---Load-Register-Byte--immediate--
80 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/LDRH--immediate---Load-Register-Halfword--immediate--
81 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/LDR--immediate---Load-Register--immediate--
82 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/LDP--Load-Pair-of-Registers-
83 addressModeKindPostIndex
84
85 // addressModePostIndex takes a base register and a 9-bit "signed" immediate offset.
86 // Before the load/store, the base register will be updated by the offset.
87 //
88 // Note that when this is used for pair load/store, the offset will be 7-bit "signed" immediate offset.
89 //
90 // See "Pre-index" in the following pages for examples:
91 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/LDRB--immediate---Load-Register-Byte--immediate--
92 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/LDRH--immediate---Load-Register-Halfword--immediate--
93 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/LDR--immediate---Load-Register--immediate--
94 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/LDP--Load-Pair-of-Registers-
95 addressModeKindPreIndex
96
97 // addressModeKindArgStackSpace is used to resolve the address of the argument stack space
98 // exiting right above the stack pointer. Since we don't know the exact stack space needed for a function
99 // at a compilation phase, this is used as a placeholder and further lowered to a real addressing mode like above.
100 addressModeKindArgStackSpace
101
102 // addressModeKindResultStackSpace is used to resolve the address of the result stack space
103 // exiting right above the stack pointer. Since we don't know the exact stack space needed for a function
104 // at a compilation phase, this is used as a placeholder and further lowered to a real addressing mode like above.
105 addressModeKindResultStackSpace
106 )
107
108 func (a addressMode) format(dstSizeBits byte) (ret string) {
109 base := formatVRegSized(a.rn, 64)
110 if rn := a.rn; rn.RegType() != regalloc.RegTypeInt {
111 panic("invalid base register type: " + a.rn.RegType().String())
112 } else if rn.IsRealReg() && v0 <= a.rn.RealReg() && a.rn.RealReg() <= v30 {
113 panic("BUG: likely a bug in reg alloc or reset behavior")
114 }
115
116 switch a.kind {
117 case addressModeKindRegScaledExtended:
118 amount := a.sizeInBitsToShiftAmount(dstSizeBits)
119 ret = fmt.Sprintf("[%s, %s, %s #%#x]", base, formatVRegSized(a.rm, a.indexRegBits()), a.extOp, amount)
120 case addressModeKindRegScaled:
121 amount := a.sizeInBitsToShiftAmount(dstSizeBits)
122 ret = fmt.Sprintf("[%s, %s, lsl #%#x]", base, formatVRegSized(a.rm, a.indexRegBits()), amount)
123 case addressModeKindRegExtended:
124 ret = fmt.Sprintf("[%s, %s, %s]", base, formatVRegSized(a.rm, a.indexRegBits()), a.extOp)
125 case addressModeKindRegReg:
126 ret = fmt.Sprintf("[%s, %s]", base, formatVRegSized(a.rm, a.indexRegBits()))
127 case addressModeKindRegSignedImm9:
128 if a.imm != 0 {
129 ret = fmt.Sprintf("[%s, #%#x]", base, a.imm)
130 } else {
131 ret = fmt.Sprintf("[%s]", base)
132 }
133 case addressModeKindRegUnsignedImm12:
134 if a.imm != 0 {
135 ret = fmt.Sprintf("[%s, #%#x]", base, a.imm)
136 } else {
137 ret = fmt.Sprintf("[%s]", base)
138 }
139 case addressModeKindPostIndex:
140 ret = fmt.Sprintf("[%s], #%#x", base, a.imm)
141 case addressModeKindPreIndex:
142 ret = fmt.Sprintf("[%s, #%#x]!", base, a.imm)
143 case addressModeKindArgStackSpace:
144 ret = fmt.Sprintf("[#arg_space, #%#x]", a.imm)
145 case addressModeKindResultStackSpace:
146 ret = fmt.Sprintf("[#ret_space, #%#x]", a.imm)
147 }
148 return
149 }
150
151 func addressModePreOrPostIndex(m *machine, rn regalloc.VReg, imm int64, preIndex bool) *addressMode {
152 if !offsetFitsInAddressModeKindRegSignedImm9(imm) {
153 panic(fmt.Sprintf("BUG: offset %#x does not fit in addressModeKindRegSignedImm9", imm))
154 }
155 mode := m.amodePool.Allocate()
156 if preIndex {
157 *mode = addressMode{kind: addressModeKindPreIndex, rn: rn, imm: imm}
158 } else {
159 *mode = addressMode{kind: addressModeKindPostIndex, rn: rn, imm: imm}
160 }
161 return mode
162 }
163
164 func offsetFitsInAddressModeKindRegUnsignedImm12(dstSizeInBits byte, offset int64) bool {
165 divisor := int64(dstSizeInBits) / 8
166 return 0 < offset && offset%divisor == 0 && offset/divisor < 4096
167 }
168
169 func offsetFitsInAddressModeKindRegSignedImm9(offset int64) bool {
170 return -256 <= offset && offset <= 255
171 }
172
173 func (a addressMode) indexRegBits() byte {
174 bits := a.extOp.srcBits()
175 if bits != 32 && bits != 64 {
176 panic("invalid index register for address mode. it must be either 32 or 64 bits")
177 }
178 return bits
179 }
180
181 func (a addressMode) sizeInBitsToShiftAmount(sizeInBits byte) (lsl byte) {
182 switch sizeInBits {
183 case 8:
184 lsl = 0
185 case 16:
186 lsl = 1
187 case 32:
188 lsl = 2
189 case 64:
190 lsl = 3
191 }
192 return
193 }
194
195 func extLoadSignSize(op ssa.Opcode) (size byte, signed bool) {
196 switch op {
197 case ssa.OpcodeUload8:
198 size, signed = 8, false
199 case ssa.OpcodeUload16:
200 size, signed = 16, false
201 case ssa.OpcodeUload32:
202 size, signed = 32, false
203 case ssa.OpcodeSload8:
204 size, signed = 8, true
205 case ssa.OpcodeSload16:
206 size, signed = 16, true
207 case ssa.OpcodeSload32:
208 size, signed = 32, true
209 default:
210 panic("BUG")
211 }
212 return
213 }
214
215 func (m *machine) lowerExtLoad(op ssa.Opcode, ptr ssa.Value, offset uint32, ret regalloc.VReg) {
216 size, signed := extLoadSignSize(op)
217 amode := m.lowerToAddressMode(ptr, offset, size)
218 load := m.allocateInstr()
219 if signed {
220 load.asSLoad(ret, amode, size)
221 } else {
222 load.asULoad(ret, amode, size)
223 }
224 m.insert(load)
225 }
226
227 func (m *machine) lowerLoad(ptr ssa.Value, offset uint32, typ ssa.Type, ret ssa.Value) {
228 amode := m.lowerToAddressMode(ptr, offset, typ.Bits())
229
230 dst := m.compiler.VRegOf(ret)
231 load := m.allocateInstr()
232 switch typ {
233 case ssa.TypeI32, ssa.TypeI64:
234 load.asULoad(dst, amode, typ.Bits())
235 case ssa.TypeF32, ssa.TypeF64:
236 load.asFpuLoad(dst, amode, typ.Bits())
237 case ssa.TypeV128:
238 load.asFpuLoad(dst, amode, 128)
239 default:
240 panic("TODO")
241 }
242 m.insert(load)
243 }
244
245 func (m *machine) lowerLoadSplat(ptr ssa.Value, offset uint32, lane ssa.VecLane, ret ssa.Value) {
246 // vecLoad1R has offset address mode (base+imm) only for post index, so we simply add the offset to the base.
247 base := m.getOperand_NR(m.compiler.ValueDefinition(ptr), extModeNone).nr()
248 offsetReg := m.compiler.AllocateVReg(ssa.TypeI64)
249 m.lowerConstantI64(offsetReg, int64(offset))
250 addedBase := m.addReg64ToReg64(base, offsetReg)
251
252 rd := m.compiler.VRegOf(ret)
253
254 ld1r := m.allocateInstr()
255 ld1r.asVecLoad1R(rd, operandNR(addedBase), ssaLaneToArrangement(lane))
256 m.insert(ld1r)
257 }
258
259 func (m *machine) lowerStore(si *ssa.Instruction) {
260 // TODO: merge consecutive stores into a single pair store instruction.
261 value, ptr, offset, storeSizeInBits := si.StoreData()
262 amode := m.lowerToAddressMode(ptr, offset, storeSizeInBits)
263
264 valueOp := m.getOperand_NR(m.compiler.ValueDefinition(value), extModeNone)
265 store := m.allocateInstr()
266 store.asStore(valueOp, amode, storeSizeInBits)
267 m.insert(store)
268 }
269
270 // lowerToAddressMode converts a pointer to an addressMode that can be used as an operand for load/store instructions.
271 func (m *machine) lowerToAddressMode(ptr ssa.Value, offsetBase uint32, size byte) (amode *addressMode) {
272 // TODO: currently the instruction selection logic doesn't support addressModeKindRegScaledExtended and
273 // addressModeKindRegScaled since collectAddends doesn't take ssa.OpcodeIshl into account. This should be fixed
274 // to support more efficient address resolution.
275
276 a32s, a64s, offset := m.collectAddends(ptr)
277 offset += int64(offsetBase)
278 return m.lowerToAddressModeFromAddends(a32s, a64s, size, offset)
279 }
280
281 // lowerToAddressModeFromAddends creates an addressMode from a list of addends collected by collectAddends.
282 // During the construction, this might emit additional instructions.
283 //
284 // Extracted as a separate function for easy testing.
285 func (m *machine) lowerToAddressModeFromAddends(a32s *wazevoapi.Queue[addend32], a64s *wazevoapi.Queue[regalloc.VReg], size byte, offset int64) (amode *addressMode) {
286 amode = m.amodePool.Allocate()
287 switch a64sExist, a32sExist := !a64s.Empty(), !a32s.Empty(); {
288 case a64sExist && a32sExist:
289 var base regalloc.VReg
290 base = a64s.Dequeue()
291 var a32 addend32
292 a32 = a32s.Dequeue()
293 *amode = addressMode{kind: addressModeKindRegExtended, rn: base, rm: a32.r, extOp: a32.ext}
294 case a64sExist && offsetFitsInAddressModeKindRegUnsignedImm12(size, offset):
295 var base regalloc.VReg
296 base = a64s.Dequeue()
297 *amode = addressMode{kind: addressModeKindRegUnsignedImm12, rn: base, imm: offset}
298 offset = 0
299 case a64sExist && offsetFitsInAddressModeKindRegSignedImm9(offset):
300 var base regalloc.VReg
301 base = a64s.Dequeue()
302 *amode = addressMode{kind: addressModeKindRegSignedImm9, rn: base, imm: offset}
303 offset = 0
304 case a64sExist:
305 var base regalloc.VReg
306 base = a64s.Dequeue()
307 if !a64s.Empty() {
308 index := a64s.Dequeue()
309 *amode = addressMode{kind: addressModeKindRegReg, rn: base, rm: index, extOp: extendOpUXTX /* indicates index reg is 64-bit */}
310 } else {
311 *amode = addressMode{kind: addressModeKindRegUnsignedImm12, rn: base, imm: 0}
312 }
313 case a32sExist:
314 base32 := a32s.Dequeue()
315
316 // First we need 64-bit base.
317 base := m.compiler.AllocateVReg(ssa.TypeI64)
318 baseExt := m.allocateInstr()
319 var signed bool
320 if base32.ext == extendOpSXTW {
321 signed = true
322 }
323 baseExt.asExtend(base, base32.r, 32, 64, signed)
324 m.insert(baseExt)
325
326 if !a32s.Empty() {
327 index := a32s.Dequeue()
328 *amode = addressMode{kind: addressModeKindRegExtended, rn: base, rm: index.r, extOp: index.ext}
329 } else {
330 *amode = addressMode{kind: addressModeKindRegUnsignedImm12, rn: base, imm: 0}
331 }
332 default: // Only static offsets.
333 tmpReg := m.compiler.AllocateVReg(ssa.TypeI64)
334 m.lowerConstantI64(tmpReg, offset)
335 *amode = addressMode{kind: addressModeKindRegUnsignedImm12, rn: tmpReg, imm: 0}
336 offset = 0
337 }
338
339 baseReg := amode.rn
340 if offset > 0 {
341 baseReg = m.addConstToReg64(baseReg, offset) // baseReg += offset
342 }
343
344 for !a64s.Empty() {
345 a64 := a64s.Dequeue()
346 baseReg = m.addReg64ToReg64(baseReg, a64) // baseReg += a64
347 }
348
349 for !a32s.Empty() {
350 a32 := a32s.Dequeue()
351 baseReg = m.addRegToReg64Ext(baseReg, a32.r, a32.ext) // baseReg += (a32 extended to 64-bit)
352 }
353 amode.rn = baseReg
354 return
355 }
356
357 var addendsMatchOpcodes = [4]ssa.Opcode{ssa.OpcodeUExtend, ssa.OpcodeSExtend, ssa.OpcodeIadd, ssa.OpcodeIconst}
358
359 func (m *machine) collectAddends(ptr ssa.Value) (addends32 *wazevoapi.Queue[addend32], addends64 *wazevoapi.Queue[regalloc.VReg], offset int64) {
360 m.addendsWorkQueue.Reset()
361 m.addends32.Reset()
362 m.addends64.Reset()
363 m.addendsWorkQueue.Enqueue(ptr)
364
365 for !m.addendsWorkQueue.Empty() {
366 v := m.addendsWorkQueue.Dequeue()
367
368 def := m.compiler.ValueDefinition(v)
369 switch op := m.compiler.MatchInstrOneOf(def, addendsMatchOpcodes[:]); op {
370 case ssa.OpcodeIadd:
371 // If the addend is an add, we recursively collect its operands.
372 x, y := def.Instr.Arg2()
373 m.addendsWorkQueue.Enqueue(x)
374 m.addendsWorkQueue.Enqueue(y)
375 def.Instr.MarkLowered()
376 case ssa.OpcodeIconst:
377 // If the addend is constant, we just statically merge it into the offset.
378 ic := def.Instr
379 u64 := ic.ConstantVal()
380 if ic.Return().Type().Bits() == 32 {
381 offset += int64(int32(u64)) // sign-extend.
382 } else {
383 offset += int64(u64)
384 }
385 def.Instr.MarkLowered()
386 case ssa.OpcodeUExtend, ssa.OpcodeSExtend:
387 input := def.Instr.Arg()
388 if input.Type().Bits() != 32 {
389 panic("illegal size: " + input.Type().String())
390 }
391
392 var ext extendOp
393 if op == ssa.OpcodeUExtend {
394 ext = extendOpUXTW
395 } else {
396 ext = extendOpSXTW
397 }
398
399 inputDef := m.compiler.ValueDefinition(input)
400 constInst := inputDef.IsFromInstr() && inputDef.Instr.Constant()
401 switch {
402 case constInst && ext == extendOpUXTW:
403 // Zero-extension of a 32-bit constant can be merged into the offset.
404 offset += int64(uint32(inputDef.Instr.ConstantVal()))
405 case constInst && ext == extendOpSXTW:
406 // Sign-extension of a 32-bit constant can be merged into the offset.
407 offset += int64(int32(inputDef.Instr.ConstantVal())) // sign-extend!
408 default:
409 m.addends32.Enqueue(addend32{r: m.getOperand_NR(inputDef, extModeNone).nr(), ext: ext})
410 }
411 def.Instr.MarkLowered()
412 continue
413 default:
414 // If the addend is not one of them, we simply use it as-is (without merging!), optionally zero-extending it.
415 m.addends64.Enqueue(m.getOperand_NR(def, extModeZeroExtend64 /* optional zero ext */).nr())
416 }
417 }
418 return &m.addends32, &m.addends64, offset
419 }
420
421 func (m *machine) addConstToReg64(r regalloc.VReg, c int64) (rd regalloc.VReg) {
422 rd = m.compiler.AllocateVReg(ssa.TypeI64)
423 alu := m.allocateInstr()
424 if imm12Op, ok := asImm12Operand(uint64(c)); ok {
425 alu.asALU(aluOpAdd, rd, operandNR(r), imm12Op, true)
426 } else if imm12Op, ok = asImm12Operand(uint64(-c)); ok {
427 alu.asALU(aluOpSub, rd, operandNR(r), imm12Op, true)
428 } else {
429 tmp := m.compiler.AllocateVReg(ssa.TypeI64)
430 m.load64bitConst(c, tmp)
431 alu.asALU(aluOpAdd, rd, operandNR(r), operandNR(tmp), true)
432 }
433 m.insert(alu)
434 return
435 }
436
437 func (m *machine) addReg64ToReg64(rn, rm regalloc.VReg) (rd regalloc.VReg) {
438 rd = m.compiler.AllocateVReg(ssa.TypeI64)
439 alu := m.allocateInstr()
440 alu.asALU(aluOpAdd, rd, operandNR(rn), operandNR(rm), true)
441 m.insert(alu)
442 return
443 }
444
445 func (m *machine) addRegToReg64Ext(rn, rm regalloc.VReg, ext extendOp) (rd regalloc.VReg) {
446 rd = m.compiler.AllocateVReg(ssa.TypeI64)
447 alu := m.allocateInstr()
448 alu.asALU(aluOpAdd, rd, operandNR(rn), operandER(rm, ext, 64), true)
449 m.insert(alu)
450 return
451 }