Debian Codegraph @

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

raw
1 package arm64
2
3 import (
4 "context"
5 "fmt"
6 "math"
7 "strings"
8
9 "github.com/tetratelabs/wazero/internal/engine/wazevo/backend"
10 "github.com/tetratelabs/wazero/internal/engine/wazevo/backend/regalloc"
11 "github.com/tetratelabs/wazero/internal/engine/wazevo/ssa"
12 "github.com/tetratelabs/wazero/internal/engine/wazevo/wazevoapi"
13 )
14
15 type (
16 // machine implements backend.Machine.
17 machine struct {
18 compiler backend.Compiler
19 currentABI *backend.FunctionABI
20 instrPool wazevoapi.Pool[instruction]
21 // labelPositionPool is the pool of labelPosition. The id is the label where
22 // if the label is less than the maxSSABlockID, it's the ssa.BasicBlockID.
23 labelPositionPool wazevoapi.IDedPool[labelPosition]
24
25 // nextLabel is the next label to be allocated. The first free label comes after maxSSABlockID
26 // so that we can have an identical label for the SSA block ID, which is useful for debugging.
27 nextLabel label
28 // rootInstr is the first instruction of the function.
29 rootInstr *instruction
30 // currentLabelPos is the currently-compiled ssa.BasicBlock's labelPosition.
31 currentLabelPos *labelPosition
32 // orderedSSABlockLabelPos is the ordered list of labelPosition in the generated code for each ssa.BasicBlock.
33 orderedSSABlockLabelPos []*labelPosition
34 // returnLabelPos is the labelPosition for the return block.
35 returnLabelPos labelPosition
36 // perBlockHead and perBlockEnd are the head and tail of the instruction list per currently-compiled ssa.BasicBlock.
37 perBlockHead, perBlockEnd *instruction
38 // pendingInstructions are the instructions which are not yet emitted into the instruction list.
39 pendingInstructions []*instruction
40 // maxSSABlockID is the maximum ssa.BasicBlockID in the current function.
41 maxSSABlockID label
42
43 regAlloc regalloc.Allocator[*instruction, *labelPosition, *regAllocFn]
44 regAllocFn regAllocFn
45
46 amodePool wazevoapi.Pool[addressMode]
47
48 // addendsWorkQueue is used during address lowering, defined here for reuse.
49 addendsWorkQueue wazevoapi.Queue[ssa.Value]
50 addends32 wazevoapi.Queue[addend32]
51 // addends64 is used during address lowering, defined here for reuse.
52 addends64 wazevoapi.Queue[regalloc.VReg]
53 unresolvedAddressModes []*instruction
54
55 // condBrRelocs holds the conditional branches which need offset relocation.
56 condBrRelocs []condBrReloc
57
58 // jmpTableTargets holds the labels of the jump table targets.
59 jmpTableTargets [][]uint32
60 // jmpTableTargetNext is the index to the jmpTableTargets slice to be used for the next jump table.
61 jmpTableTargetsNext int
62
63 // spillSlotSize is the size of the stack slot in bytes used for spilling registers.
64 // During the execution of the function, the stack looks like:
65 //
66 //
67 // (high address)
68 // +-----------------+
69 // | ....... |
70 // | ret Y |
71 // | ....... |
72 // | ret 0 |
73 // | arg X |
74 // | ....... |
75 // | arg 1 |
76 // | arg 0 |
77 // | xxxxx |
78 // | ReturnAddress |
79 // +-----------------+ <<-|
80 // | ........... | |
81 // | spill slot M | | <--- spillSlotSize
82 // | ............ | |
83 // | spill slot 2 | |
84 // | spill slot 1 | <<-+
85 // | clobbered N |
86 // | ........... |
87 // | clobbered 1 |
88 // | clobbered 0 |
89 // SP---> +-----------------+
90 // (low address)
91 //
92 // and it represents the size of the space between FP and the first spilled slot. This must be a multiple of 16.
93 // Also note that this is only known after register allocation.
94 spillSlotSize int64
95 spillSlots map[regalloc.VRegID]int64 // regalloc.VRegID to offset.
96 // clobberedRegs holds real-register backed VRegs saved at the function prologue, and restored at the epilogue.
97 clobberedRegs []regalloc.VReg
98
99 maxRequiredStackSizeForCalls int64
100 stackBoundsCheckDisabled bool
101
102 regAllocStarted bool
103 }
104
105 addend32 struct {
106 r regalloc.VReg
107 ext extendOp
108 }
109
110 condBrReloc struct {
111 cbr *instruction
112 // currentLabelPos is the labelPosition within which condBr is defined.
113 currentLabelPos *labelPosition
114 // Next block's labelPosition.
115 nextLabel label
116 offset int64
117 }
118 )
119
120 type (
121 // label represents a position in the generated code which is either
122 // a real instruction or the constant InstructionPool (e.g. jump tables).
123 //
124 // This is exactly the same as the traditional "label" in assembly code.
125 label uint32
126
127 // labelPosition represents the regions of the generated code which the label represents.
128 // This implements regalloc.Block.
129 labelPosition struct {
130 // sb is not nil if this corresponds to a ssa.BasicBlock.
131 sb ssa.BasicBlock
132 // cur is used to walk through the instructions in the block during the register allocation.
133 cur,
134 // begin and end are the first and last instructions of the block.
135 begin, end *instruction
136 // binaryOffset is the offset in the binary where the label is located.
137 binaryOffset int64
138 }
139 )
140
141 const (
142 labelReturn label = math.MaxUint32
143 labelInvalid = labelReturn - 1
144 )
145
146 // String implements backend.Machine.
147 func (l label) String() string {
148 return fmt.Sprintf("L%d", l)
149 }
150
151 func resetLabelPosition(l *labelPosition) {
152 *l = labelPosition{}
153 }
154
155 // NewBackend returns a new backend for arm64.
156 func NewBackend() backend.Machine {
157 m := &machine{
158 spillSlots: make(map[regalloc.VRegID]int64),
159 regAlloc: regalloc.NewAllocator[*instruction, *labelPosition, *regAllocFn](regInfo),
160 amodePool: wazevoapi.NewPool[addressMode](resetAddressMode),
161 instrPool: wazevoapi.NewPool[instruction](resetInstruction),
162 labelPositionPool: wazevoapi.NewIDedPool[labelPosition](resetLabelPosition),
163 }
164 m.regAllocFn.m = m
165 return m
166 }
167
168 func ssaBlockLabel(sb ssa.BasicBlock) label {
169 if sb.ReturnBlock() {
170 return labelReturn
171 }
172 return label(sb.ID())
173 }
174
175 // getOrAllocateSSABlockLabelPosition returns the labelPosition for the given basic block.
176 func (m *machine) getOrAllocateSSABlockLabelPosition(sb ssa.BasicBlock) *labelPosition {
177 if sb.ReturnBlock() {
178 m.returnLabelPos.sb = sb
179 return &m.returnLabelPos
180 }
181
182 l := ssaBlockLabel(sb)
183 pos := m.labelPositionPool.GetOrAllocate(int(l))
184 pos.sb = sb
185 return pos
186 }
187
188 // LinkAdjacentBlocks implements backend.Machine.
189 func (m *machine) LinkAdjacentBlocks(prev, next ssa.BasicBlock) {
190 prevPos, nextPos := m.getOrAllocateSSABlockLabelPosition(prev), m.getOrAllocateSSABlockLabelPosition(next)
191 prevPos.end.next = nextPos.begin
192 }
193
194 // StartBlock implements backend.Machine.
195 func (m *machine) StartBlock(blk ssa.BasicBlock) {
196 m.currentLabelPos = m.getOrAllocateSSABlockLabelPosition(blk)
197 labelPos := m.currentLabelPos
198 end := m.allocateNop()
199 m.perBlockHead, m.perBlockEnd = end, end
200 labelPos.begin, labelPos.end = end, end
201 m.orderedSSABlockLabelPos = append(m.orderedSSABlockLabelPos, labelPos)
202 }
203
204 // EndBlock implements ExecutableContext.
205 func (m *machine) EndBlock() {
206 // Insert nop0 as the head of the block for convenience to simplify the logic of inserting instructions.
207 m.insertAtPerBlockHead(m.allocateNop())
208
209 m.currentLabelPos.begin = m.perBlockHead
210
211 if m.currentLabelPos.sb.EntryBlock() {
212 m.rootInstr = m.perBlockHead
213 }
214 }
215
216 func (m *machine) insertAtPerBlockHead(i *instruction) {
217 if m.perBlockHead == nil {
218 m.perBlockHead = i
219 m.perBlockEnd = i
220 return
221 }
222
223 i.next = m.perBlockHead
224 m.perBlockHead.prev = i
225 m.perBlockHead = i
226 }
227
228 // FlushPendingInstructions implements backend.Machine.
229 func (m *machine) FlushPendingInstructions() {
230 l := len(m.pendingInstructions)
231 if l == 0 {
232 return
233 }
234 for i := l - 1; i >= 0; i-- { // reverse because we lower instructions in reverse order.
235 m.insertAtPerBlockHead(m.pendingInstructions[i])
236 }
237 m.pendingInstructions = m.pendingInstructions[:0]
238 }
239
240 // RegAlloc implements backend.Machine Function.
241 func (m *machine) RegAlloc() {
242 m.regAllocStarted = true
243 m.regAlloc.DoAllocation(&m.regAllocFn)
244 // Now that we know the final spill slot size, we must align spillSlotSize to 16 bytes.
245 m.spillSlotSize = (m.spillSlotSize + 15) &^ 15
246 }
247
248 // Reset implements backend.Machine.
249 func (m *machine) Reset() {
250 m.clobberedRegs = m.clobberedRegs[:0]
251 for key := range m.spillSlots {
252 m.clobberedRegs = append(m.clobberedRegs, regalloc.VReg(key))
253 }
254 for _, key := range m.clobberedRegs {
255 delete(m.spillSlots, regalloc.VRegID(key))
256 }
257 m.clobberedRegs = m.clobberedRegs[:0]
258 m.regAllocStarted = false
259 m.regAlloc.Reset()
260 m.spillSlotSize = 0
261 m.unresolvedAddressModes = m.unresolvedAddressModes[:0]
262 m.maxRequiredStackSizeForCalls = 0
263 m.jmpTableTargetsNext = 0
264 m.amodePool.Reset()
265 m.instrPool.Reset()
266 m.labelPositionPool.Reset()
267 m.pendingInstructions = m.pendingInstructions[:0]
268 m.perBlockHead, m.perBlockEnd, m.rootInstr = nil, nil, nil
269 m.orderedSSABlockLabelPos = m.orderedSSABlockLabelPos[:0]
270 }
271
272 // StartLoweringFunction implements backend.Machine StartLoweringFunction.
273 func (m *machine) StartLoweringFunction(maxBlockID ssa.BasicBlockID) {
274 m.maxSSABlockID = label(maxBlockID)
275 m.nextLabel = label(maxBlockID) + 1
276 }
277
278 // SetCurrentABI implements backend.Machine SetCurrentABI.
279 func (m *machine) SetCurrentABI(abi *backend.FunctionABI) {
280 m.currentABI = abi
281 }
282
283 // DisableStackCheck implements backend.Machine DisableStackCheck.
284 func (m *machine) DisableStackCheck() {
285 m.stackBoundsCheckDisabled = true
286 }
287
288 // SetCompiler implements backend.Machine.
289 func (m *machine) SetCompiler(ctx backend.Compiler) {
290 m.compiler = ctx
291 m.regAllocFn.ssaB = ctx.SSABuilder()
292 }
293
294 func (m *machine) insert(i *instruction) {
295 m.pendingInstructions = append(m.pendingInstructions, i)
296 }
297
298 func (m *machine) insertBrTargetLabel() label {
299 nop, l := m.allocateBrTarget()
300 m.insert(nop)
301 return l
302 }
303
304 func (m *machine) allocateBrTarget() (nop *instruction, l label) {
305 l = m.nextLabel
306 m.nextLabel++
307 nop = m.allocateInstr()
308 nop.asNop0WithLabel(l)
309 pos := m.labelPositionPool.GetOrAllocate(int(l))
310 pos.begin, pos.end = nop, nop
311 return
312 }
313
314 // allocateInstr allocates an instruction.
315 func (m *machine) allocateInstr() *instruction {
316 instr := m.instrPool.Allocate()
317 if !m.regAllocStarted {
318 instr.addedBeforeRegAlloc = true
319 }
320 return instr
321 }
322
323 func resetInstruction(i *instruction) {
324 *i = instruction{}
325 }
326
327 func (m *machine) allocateNop() *instruction {
328 instr := m.allocateInstr()
329 instr.asNop0()
330 return instr
331 }
332
333 func (m *machine) resolveAddressingMode(arg0offset, ret0offset int64, i *instruction) {
334 amode := i.getAmode()
335 switch amode.kind {
336 case addressModeKindResultStackSpace:
337 amode.imm += ret0offset
338 case addressModeKindArgStackSpace:
339 amode.imm += arg0offset
340 default:
341 panic("BUG")
342 }
343
344 var sizeInBits byte
345 switch i.kind {
346 case store8, uLoad8:
347 sizeInBits = 8
348 case store16, uLoad16:
349 sizeInBits = 16
350 case store32, fpuStore32, uLoad32, fpuLoad32:
351 sizeInBits = 32
352 case store64, fpuStore64, uLoad64, fpuLoad64:
353 sizeInBits = 64
354 case fpuStore128, fpuLoad128:
355 sizeInBits = 128
356 default:
357 panic("BUG")
358 }
359
360 if offsetFitsInAddressModeKindRegUnsignedImm12(sizeInBits, amode.imm) {
361 amode.kind = addressModeKindRegUnsignedImm12
362 } else {
363 // This case, we load the offset into the temporary register,
364 // and then use it as the index register.
365 newPrev := m.lowerConstantI64AndInsert(i.prev, tmpRegVReg, amode.imm)
366 linkInstr(newPrev, i)
367 *amode = addressMode{kind: addressModeKindRegReg, rn: amode.rn, rm: tmpRegVReg, extOp: extendOpUXTX /* indicates rm reg is 64-bit */}
368 }
369 }
370
371 // resolveRelativeAddresses resolves the relative addresses before encoding.
372 func (m *machine) resolveRelativeAddresses(ctx context.Context) {
373 if len(m.unresolvedAddressModes) > 0 {
374 arg0offset, ret0offset := m.arg0OffsetFromSP(), m.ret0OffsetFromSP()
375 for _, i := range m.unresolvedAddressModes {
376 m.resolveAddressingMode(arg0offset, ret0offset, i)
377 }
378 m.unresolvedAddressModes = m.unresolvedAddressModes[:0]
379 }
380 for {
381 // Reuse the slice to gather the unresolved conditional branches.
382 m.condBrRelocs = m.condBrRelocs[:0]
383
384 var fn string
385 var fnIndex int
386 var labelPosToLabel map[*labelPosition]label
387 if wazevoapi.PerfMapEnabled {
388 labelPosToLabel = make(map[*labelPosition]label)
389 for i := 0; i <= m.labelPositionPool.MaxIDEncountered(); i++ {
390 labelPosToLabel[m.labelPositionPool.Get(i)] = label(i)
391 }
392
393 fn = wazevoapi.GetCurrentFunctionName(ctx)
394 fnIndex = wazevoapi.GetCurrentFunctionIndex(ctx)
395 }
396
397 // Next, in order to determine the offsets of relative jumps, we have to calculate the size of each label.
398 var offset int64
399 for i, pos := range m.orderedSSABlockLabelPos {
400 pos.binaryOffset = offset
401 var size int64
402 for cur := pos.begin; ; cur = cur.next {
403 switch cur.kind {
404 case nop0:
405 l := cur.nop0Label()
406 if pos := m.labelPositionPool.Get(int(l)); pos != nil {
407 pos.binaryOffset = offset + size
408 }
409 case condBr:
410 if !cur.condBrOffsetResolved() {
411 var nextLabel label
412 if i < len(m.orderedSSABlockLabelPos)-1 {
413 // Note: this is only used when the block ends with fallthrough,
414 // therefore can be safely assumed that the next block exists when it's needed.
415 nextLabel = ssaBlockLabel(m.orderedSSABlockLabelPos[i+1].sb)
416 }
417 m.condBrRelocs = append(m.condBrRelocs, condBrReloc{
418 cbr: cur, currentLabelPos: pos, offset: offset + size,
419 nextLabel: nextLabel,
420 })
421 }
422 }
423 size += cur.size()
424 if cur == pos.end {
425 break
426 }
427 }
428
429 if wazevoapi.PerfMapEnabled {
430 if size > 0 {
431 wazevoapi.PerfMap.AddModuleEntry(fnIndex, offset, uint64(size), fmt.Sprintf("%s:::::%s", fn, labelPosToLabel[pos]))
432 }
433 }
434 offset += size
435 }
436
437 // Before resolving any offsets, we need to check if all the conditional branches can be resolved.
438 var needRerun bool
439 for i := range m.condBrRelocs {
440 reloc := &m.condBrRelocs[i]
441 cbr := reloc.cbr
442 offset := reloc.offset
443
444 target := cbr.condBrLabel()
445 offsetOfTarget := m.labelPositionPool.Get(int(target)).binaryOffset
446 diff := offsetOfTarget - offset
447 if divided := diff >> 2; divided < minSignedInt19 || divided > maxSignedInt19 {
448 // This case the conditional branch is too huge. We place the trampoline instructions at the end of the current block,
449 // and jump to it.
450 m.insertConditionalJumpTrampoline(cbr, reloc.currentLabelPos, reloc.nextLabel)
451 // Then, we need to recall this function to fix up the label offsets
452 // as they have changed after the trampoline is inserted.
453 needRerun = true
454 }
455 }
456 if needRerun {
457 if wazevoapi.PerfMapEnabled {
458 wazevoapi.PerfMap.Clear()
459 }
460 } else {
461 break
462 }
463 }
464
465 var currentOffset int64
466 for cur := m.rootInstr; cur != nil; cur = cur.next {
467 switch cur.kind {
468 case br:
469 target := cur.brLabel()
470 offsetOfTarget := m.labelPositionPool.Get(int(target)).binaryOffset
471 diff := offsetOfTarget - currentOffset
472 divided := diff >> 2
473 if divided < minSignedInt26 || divided > maxSignedInt26 {
474 // This means the currently compiled single function is extremely large.
475 panic("too large function that requires branch relocation of large unconditional branch larger than 26-bit range")
476 }
477 cur.brOffsetResolve(diff)
478 case condBr:
479 if !cur.condBrOffsetResolved() {
480 target := cur.condBrLabel()
481 offsetOfTarget := m.labelPositionPool.Get(int(target)).binaryOffset
482 diff := offsetOfTarget - currentOffset
483 if divided := diff >> 2; divided < minSignedInt19 || divided > maxSignedInt19 {
484 panic("BUG: branch relocation for large conditional branch larger than 19-bit range must be handled properly")
485 }
486 cur.condBrOffsetResolve(diff)
487 }
488 case brTableSequence:
489 tableIndex := cur.u1
490 targets := m.jmpTableTargets[tableIndex]
491 for i := range targets {
492 l := label(targets[i])
493 offsetOfTarget := m.labelPositionPool.Get(int(l)).binaryOffset
494 diff := offsetOfTarget - (currentOffset + brTableSequenceOffsetTableBegin)
495 targets[i] = uint32(diff)
496 }
497 cur.brTableSequenceOffsetsResolved()
498 case emitSourceOffsetInfo:
499 m.compiler.AddSourceOffsetInfo(currentOffset, cur.sourceOffsetInfo())
500 }
501 currentOffset += cur.size()
502 }
503 }
504
505 const (
506 maxSignedInt26 = 1<<25 - 1
507 minSignedInt26 = -(1 << 25)
508
509 maxSignedInt19 = 1<<18 - 1
510 minSignedInt19 = -(1 << 18)
511 )
512
513 func (m *machine) insertConditionalJumpTrampoline(cbr *instruction, currentBlk *labelPosition, nextLabel label) {
514 cur := currentBlk.end
515 originalTarget := cbr.condBrLabel()
516 endNext := cur.next
517
518 if cur.kind != br {
519 // If the current block ends with a conditional branch, we can just insert the trampoline after it.
520 // Otherwise, we need to insert "skip" instruction to skip the trampoline instructions.
521 skip := m.allocateInstr()
522 skip.asBr(nextLabel)
523 cur = linkInstr(cur, skip)
524 }
525
526 cbrNewTargetInstr, cbrNewTargetLabel := m.allocateBrTarget()
527 cbr.setCondBrTargets(cbrNewTargetLabel)
528 cur = linkInstr(cur, cbrNewTargetInstr)
529
530 // Then insert the unconditional branch to the original, which should be possible to get encoded
531 // as 26-bit offset should be enough for any practical application.
532 br := m.allocateInstr()
533 br.asBr(originalTarget)
534 cur = linkInstr(cur, br)
535
536 // Update the end of the current block.
537 currentBlk.end = cur
538
539 linkInstr(cur, endNext)
540 }
541
542 // Format implements backend.Machine.
543 func (m *machine) Format() string {
544 begins := map[*instruction]label{}
545 for l := label(0); l < m.nextLabel; l++ {
546 pos := m.labelPositionPool.Get(int(l))
547 if pos != nil {
548 begins[pos.begin] = l
549 }
550 }
551
552 var lines []string
553 for cur := m.rootInstr; cur != nil; cur = cur.next {
554 if l, ok := begins[cur]; ok {
555 var labelStr string
556 if l <= m.maxSSABlockID {
557 labelStr = fmt.Sprintf("%s (SSA Block: blk%d):", l, int(l))
558 } else {
559 labelStr = fmt.Sprintf("%s:", l)
560 }
561 lines = append(lines, labelStr)
562 }
563 if cur.kind == nop0 {
564 continue
565 }
566 lines = append(lines, "\t"+cur.String())
567 }
568 return "\n" + strings.Join(lines, "\n") + "\n"
569 }
570
571 // InsertReturn implements backend.Machine.
572 func (m *machine) InsertReturn() {
573 i := m.allocateInstr()
574 i.asRet()
575 m.insert(i)
576 }
577
578 func (m *machine) getVRegSpillSlotOffsetFromSP(id regalloc.VRegID, size byte) int64 {
579 offset, ok := m.spillSlots[id]
580 if !ok {
581 offset = m.spillSlotSize
582 // TODO: this should be aligned depending on the `size` to use Imm12 offset load/store as much as possible.
583 m.spillSlots[id] = offset
584 m.spillSlotSize += int64(size)
585 }
586 return offset + 16 // spill slot starts above the clobbered registers and the frame size.
587 }
588
589 func (m *machine) clobberedRegSlotSize() int64 {
590 return int64(len(m.clobberedRegs) * 16)
591 }
592
593 func (m *machine) arg0OffsetFromSP() int64 {
594 return m.frameSize() +
595 16 + // 16-byte aligned return address
596 16 // frame size saved below the clobbered registers.
597 }
598
599 func (m *machine) ret0OffsetFromSP() int64 {
600 return m.arg0OffsetFromSP() + m.currentABI.ArgStackSize
601 }
602
603 func (m *machine) requiredStackSize() int64 {
604 return m.maxRequiredStackSizeForCalls +
605 m.frameSize() +
606 16 + // 16-byte aligned return address.
607 16 // frame size saved below the clobbered registers.
608 }
609
610 func (m *machine) frameSize() int64 {
611 s := m.clobberedRegSlotSize() + m.spillSlotSize
612 if s&0xf != 0 {
613 panic(fmt.Errorf("BUG: frame size %d is not 16-byte aligned", s))
614 }
615 return s
616 }
617
618 func (m *machine) addJmpTableTarget(targets ssa.Values) (index int) {
619 if m.jmpTableTargetsNext == len(m.jmpTableTargets) {
620 m.jmpTableTargets = append(m.jmpTableTargets, make([]uint32, 0, len(targets.View())))
621 }
622
623 index = m.jmpTableTargetsNext
624 m.jmpTableTargetsNext++
625 m.jmpTableTargets[index] = m.jmpTableTargets[index][:0]
626 for _, targetBlockID := range targets.View() {
627 target := m.compiler.SSABuilder().BasicBlock(ssa.BasicBlockID(targetBlockID))
628 m.jmpTableTargets[index] = append(m.jmpTableTargets[index], uint32(target.ID()))
629 }
630 return
631 }