1package ssa
2
3import (
4 "fmt"
5 "sort"
6 "strings"
7
8 "github.com/tetratelabs/wazero/internal/engine/wazevo/wazevoapi"
9)
10
11// Builder is used to builds SSA consisting of Basic Blocks per function.
12type Builder interface {
13 // Init must be called to reuse this builder for the next function.
14 Init(typ *Signature)
15
16 // Signature returns the Signature of the currently-compiled function.
17 Signature() *Signature
18
19 // BlockIDMax returns the maximum value of BasicBlocksID existing in the currently-compiled function.
20 BlockIDMax() BasicBlockID
21
22 // AllocateBasicBlock creates a basic block in SSA function.
23 AllocateBasicBlock() BasicBlock
24
25 // CurrentBlock returns the currently handled BasicBlock which is set by the latest call to SetCurrentBlock.
26 CurrentBlock() BasicBlock
27
28 // EntryBlock returns the entry BasicBlock of the currently-compiled function.
29 EntryBlock() BasicBlock
30
31 // SetCurrentBlock sets the instruction insertion target to the BasicBlock `b`.
32 SetCurrentBlock(b BasicBlock)
33
34 // DeclareVariable declares a Variable of the given Type.
35 DeclareVariable(Type) Variable
36
37 // DefineVariable defines a variable in the `block` with value.
38 // The defining instruction will be inserted into the `block`.
39 DefineVariable(variable Variable, value Value, block BasicBlock)
40
41 // DefineVariableInCurrentBB is the same as DefineVariable except the definition is
42 // inserted into the current BasicBlock. Alias to DefineVariable(x, y, CurrentBlock()).
43 DefineVariableInCurrentBB(variable Variable, value Value)
44
45 // AllocateInstruction returns a new Instruction.
46 AllocateInstruction() *Instruction
47
48 // InsertInstruction executes BasicBlock.InsertInstruction for the currently handled basic block.
49 InsertInstruction(raw *Instruction)
50
51 // allocateValue allocates an unused Value.
52 allocateValue(typ Type) Value
53
54 // MustFindValue searches the latest definition of the given Variable and returns the result.
55 MustFindValue(variable Variable) Value
56
57 // FindValueInLinearPath tries to find the latest definition of the given Variable in the linear path to the current BasicBlock.
58 // If it cannot find the definition, or it's not sealed yet, it returns ValueInvalid.
59 FindValueInLinearPath(variable Variable) Value
60
61 // Seal declares that we've known all the predecessors to this block and were added via AddPred.
62 // After calling this, AddPred will be forbidden.
63 Seal(blk BasicBlock)
64
65 // AnnotateValue is for debugging purpose.
66 AnnotateValue(value Value, annotation string)
67
68 // DeclareSignature appends the *Signature to be referenced by various instructions (e.g. OpcodeCall).
69 DeclareSignature(signature *Signature)
70
71 // Signatures returns the slice of declared Signatures.
72 Signatures() []*Signature
73
74 // ResolveSignature returns the Signature which corresponds to SignatureID.
75 ResolveSignature(id SignatureID) *Signature
76
77 // RunPasses runs various passes on the constructed SSA function.
78 RunPasses()
79
80 // Format returns the debugging string of the SSA function.
81 Format() string
82
83 // BlockIteratorBegin initializes the state to iterate over all the valid BasicBlock(s) compiled.
84 // Combined with BlockIteratorNext, we can use this like:
85 //
86 // for blk := builder.BlockIteratorBegin(); blk != nil; blk = builder.BlockIteratorNext() {
87 // // ...
88 // }
89 //
90 // The returned blocks are ordered in the order of AllocateBasicBlock being called.
91 BlockIteratorBegin() BasicBlock
92
93 // BlockIteratorNext advances the state for iteration initialized by BlockIteratorBegin.
94 // Returns nil if there's no unseen BasicBlock.
95 BlockIteratorNext() BasicBlock
96
97 // ValuesInfo returns the data per Value used to lower the SSA in backend.
98 // This is indexed by ValueID.
99 ValuesInfo() []ValueInfo
100
101 // BlockIteratorReversePostOrderBegin is almost the same as BlockIteratorBegin except it returns the BasicBlock in the reverse post-order.
102 // This is available after RunPasses is run.
103 BlockIteratorReversePostOrderBegin() BasicBlock
104
105 // BlockIteratorReversePostOrderNext is almost the same as BlockIteratorPostOrderNext except it returns the BasicBlock in the reverse post-order.
106 // This is available after RunPasses is run.
107 BlockIteratorReversePostOrderNext() BasicBlock
108
109 // ReturnBlock returns the BasicBlock which is used to return from the function.
110 ReturnBlock() BasicBlock
111
112 // InsertUndefined inserts an undefined instruction at the current position.
113 InsertUndefined()
114
115 // SetCurrentSourceOffset sets the current source offset. The incoming instruction will be annotated with this offset.
116 SetCurrentSourceOffset(line SourceOffset)
117
118 // LoopNestingForestRoots returns the roots of the loop nesting forest.
119 LoopNestingForestRoots() []BasicBlock
120
121 // LowestCommonAncestor returns the lowest common ancestor in the dominator tree of the given BasicBlock(s).
122 LowestCommonAncestor(blk1, blk2 BasicBlock) BasicBlock
123
124 // Idom returns the immediate dominator of the given BasicBlock.
125 Idom(blk BasicBlock) BasicBlock
126
127 // VarLengthPool returns the VarLengthPool of Value.
128 VarLengthPool() *wazevoapi.VarLengthPool[Value]
129
130 // InsertZeroValue inserts a zero value constant instruction of the given type.
131 InsertZeroValue(t Type)
132
133 // BasicBlock returns the BasicBlock of the given ID.
134 BasicBlock(id BasicBlockID) BasicBlock
135
136 // InstructionOfValue returns the Instruction that produces the given Value or nil if the Value is not produced by any Instruction.
137 InstructionOfValue(v Value) *Instruction
138}
139
140// NewBuilder returns a new Builder implementation.
141func NewBuilder() Builder {
142 return &builder{
143 instructionsPool: wazevoapi.NewPool[Instruction](resetInstruction),
144 basicBlocksPool: wazevoapi.NewPool[basicBlock](resetBasicBlock),
145 varLengthBasicBlockPool: wazevoapi.NewVarLengthPool[BasicBlock](),
146 varLengthPool: wazevoapi.NewVarLengthPool[Value](),
147 valueAnnotations: make(map[ValueID]string),
148 signatures: make(map[SignatureID]*Signature),
149 returnBlk: &basicBlock{id: basicBlockIDReturnBlock},
150 }
151}
152
153// builder implements Builder interface.
154type builder struct {
155 basicBlocksPool wazevoapi.Pool[basicBlock]
156 instructionsPool wazevoapi.Pool[Instruction]
157 varLengthPool wazevoapi.VarLengthPool[Value]
158 signatures map[SignatureID]*Signature
159 currentSignature *Signature
160
161 // reversePostOrderedBasicBlocks are the BasicBlock(s) ordered in the reverse post-order after passCalculateImmediateDominators.
162 reversePostOrderedBasicBlocks []*basicBlock
163 currentBB *basicBlock
164 returnBlk *basicBlock
165
166 // nextValueID is used by builder.AllocateValue.
167 nextValueID ValueID
168 // nextVariable is used by builder.AllocateVariable.
169 nextVariable Variable
170
171 // valueAnnotations contains the annotations for each Value, only used for debugging.
172 valueAnnotations map[ValueID]string
173
174 // valuesInfo contains the data per Value used to lower the SSA in backend. This is indexed by ValueID.
175 valuesInfo []ValueInfo
176
177 // dominators stores the immediate dominator of each BasicBlock.
178 // The index is blockID of the BasicBlock.
179 dominators []*basicBlock
180 sparseTree dominatorSparseTree
181
182 varLengthBasicBlockPool wazevoapi.VarLengthPool[BasicBlock]
183
184 // loopNestingForestRoots are the roots of the loop nesting forest.
185 loopNestingForestRoots []BasicBlock
186
187 // The followings are used for optimization passes/deterministic compilation.
188 instStack []*Instruction
189 blkStack []*basicBlock
190 blkStack2 []*basicBlock
191 redundantParams []redundantParam
192
193 // blockIterCur is used to implement blockIteratorBegin and blockIteratorNext.
194 blockIterCur int
195
196 // donePreBlockLayoutPasses is true if all the passes before LayoutBlocks are called.
197 donePreBlockLayoutPasses bool
198 // doneBlockLayout is true if LayoutBlocks is called.
199 doneBlockLayout bool
200 // donePostBlockLayoutPasses is true if all the passes after LayoutBlocks are called.
201 donePostBlockLayoutPasses bool
202
203 currentSourceOffset SourceOffset
204
205 // zeros are the zero value constants for each type.
206 zeros [typeEnd]Value
207}
208
209// ValueInfo contains the data per Value used to lower the SSA in backend.
210type ValueInfo struct {
211 // RefCount is the reference count of the Value.
212 RefCount uint32
213 alias Value
214}
215
216// redundantParam is a pair of the index of the redundant parameter and the Value.
217// This is used to eliminate the redundant parameters in the optimization pass.
218type redundantParam struct {
219 // index is the index of the redundant parameter in the basicBlock.
220 index int
221 // uniqueValue is the Value which is passed to the redundant parameter.
222 uniqueValue Value
223}
224
225// BasicBlock implements Builder.BasicBlock.
226func (b *builder) BasicBlock(id BasicBlockID) BasicBlock {
227 return b.basicBlock(id)
228}
229
230func (b *builder) basicBlock(id BasicBlockID) *basicBlock {
231 if id == basicBlockIDReturnBlock {
232 return b.returnBlk
233 }
234 return b.basicBlocksPool.View(int(id))
235}
236
237// InsertZeroValue implements Builder.InsertZeroValue.
238func (b *builder) InsertZeroValue(t Type) {
239 if b.zeros[t].Valid() {
240 return
241 }
242 zeroInst := b.AllocateInstruction()
243 switch t {
244 case TypeI32:
245 zeroInst.AsIconst32(0)
246 case TypeI64:
247 zeroInst.AsIconst64(0)
248 case TypeF32:
249 zeroInst.AsF32const(0)
250 case TypeF64:
251 zeroInst.AsF64const(0)
252 case TypeV128:
253 zeroInst.AsVconst(0, 0)
254 default:
255 panic("TODO: " + t.String())
256 }
257 b.zeros[t] = zeroInst.Insert(b).Return()
258}
259
260func (b *builder) VarLengthPool() *wazevoapi.VarLengthPool[Value] {
261 return &b.varLengthPool
262}
263
264// ReturnBlock implements Builder.ReturnBlock.
265func (b *builder) ReturnBlock() BasicBlock {
266 return b.returnBlk
267}
268
269// Init implements Builder.Reset.
270func (b *builder) Init(s *Signature) {
271 b.nextVariable = 0
272 b.currentSignature = s
273 b.zeros = [typeEnd]Value{ValueInvalid, ValueInvalid, ValueInvalid, ValueInvalid, ValueInvalid, ValueInvalid}
274 resetBasicBlock(b.returnBlk)
275 b.instructionsPool.Reset()
276 b.basicBlocksPool.Reset()
277 b.varLengthPool.Reset()
278 b.varLengthBasicBlockPool.Reset()
279 b.donePreBlockLayoutPasses = false
280 b.doneBlockLayout = false
281 b.donePostBlockLayoutPasses = false
282 for _, sig := range b.signatures {
283 sig.used = false
284 }
285
286 b.redundantParams = b.redundantParams[:0]
287 b.blkStack = b.blkStack[:0]
288 b.blkStack2 = b.blkStack2[:0]
289 b.dominators = b.dominators[:0]
290 b.loopNestingForestRoots = b.loopNestingForestRoots[:0]
291 b.basicBlocksPool.Reset()
292
293 for v := ValueID(0); v < b.nextValueID; v++ {
294 delete(b.valueAnnotations, v)
295 b.valuesInfo[v] = ValueInfo{alias: ValueInvalid}
296 }
297 b.nextValueID = 0
298 b.reversePostOrderedBasicBlocks = b.reversePostOrderedBasicBlocks[:0]
299 b.doneBlockLayout = false
300 b.currentSourceOffset = sourceOffsetUnknown
301}
302
303// Signature implements Builder.Signature.
304func (b *builder) Signature() *Signature {
305 return b.currentSignature
306}
307
308// AnnotateValue implements Builder.AnnotateValue.
309func (b *builder) AnnotateValue(value Value, a string) {
310 b.valueAnnotations[value.ID()] = a
311}
312
313// AllocateInstruction implements Builder.AllocateInstruction.
314func (b *builder) AllocateInstruction() *Instruction {
315 instr := b.instructionsPool.Allocate()
316 instr.id = b.instructionsPool.Allocated()
317 return instr
318}
319
320// DeclareSignature implements Builder.AnnotateValue.
321func (b *builder) DeclareSignature(s *Signature) {
322 b.signatures[s.ID] = s
323 s.used = false
324}
325
326// Signatures implements Builder.Signatures.
327func (b *builder) Signatures() (ret []*Signature) {
328 for _, sig := range b.signatures {
329 ret = append(ret, sig)
330 }
331 sort.Slice(ret, func(i, j int) bool {
332 return ret[i].ID < ret[j].ID
333 })
334 return
335}
336
337// SetCurrentSourceOffset implements Builder.SetCurrentSourceOffset.
338func (b *builder) SetCurrentSourceOffset(l SourceOffset) {
339 b.currentSourceOffset = l
340}
341
342func (b *builder) usedSignatures() (ret []*Signature) {
343 for _, sig := range b.signatures {
344 if sig.used {
345 ret = append(ret, sig)
346 }
347 }
348 sort.Slice(ret, func(i, j int) bool {
349 return ret[i].ID < ret[j].ID
350 })
351 return
352}
353
354// ResolveSignature implements Builder.ResolveSignature.
355func (b *builder) ResolveSignature(id SignatureID) *Signature {
356 return b.signatures[id]
357}
358
359// AllocateBasicBlock implements Builder.AllocateBasicBlock.
360func (b *builder) AllocateBasicBlock() BasicBlock {
361 return b.allocateBasicBlock()
362}
363
364// allocateBasicBlock allocates a new basicBlock.
365func (b *builder) allocateBasicBlock() *basicBlock {
366 id := BasicBlockID(b.basicBlocksPool.Allocated())
367 blk := b.basicBlocksPool.Allocate()
368 blk.id = id
369 return blk
370}
371
372// Idom implements Builder.Idom.
373func (b *builder) Idom(blk BasicBlock) BasicBlock {
374 return b.dominators[blk.ID()]
375}
376
377// InsertInstruction implements Builder.InsertInstruction.
378func (b *builder) InsertInstruction(instr *Instruction) {
379 b.currentBB.insertInstruction(b, instr)
380
381 if l := b.currentSourceOffset; l.Valid() {
382 // Emit the source offset info only when the instruction has side effect because
383 // these are the only instructions that are accessed by stack unwinding.
384 // This reduces the significant amount of the offset info in the binary.
385 if instr.sideEffect() != sideEffectNone {
386 instr.annotateSourceOffset(l)
387 }
388 }
389
390 resultTypesFn := instructionReturnTypes[instr.opcode]
391 if resultTypesFn == nil {
392 panic("TODO: " + instr.Format(b))
393 }
394
395 t1, ts := resultTypesFn(b, instr)
396 if t1.invalid() {
397 return
398 }
399
400 r1 := b.allocateValue(t1)
401 instr.rValue = r1.setInstructionID(instr.id)
402
403 tsl := len(ts)
404 if tsl == 0 {
405 return
406 }
407
408 rValues := b.varLengthPool.Allocate(tsl)
409 for i := 0; i < tsl; i++ {
410 rn := b.allocateValue(ts[i])
411 rValues = rValues.Append(&b.varLengthPool, rn.setInstructionID(instr.id))
412 }
413 instr.rValues = rValues
414}
415
416// DefineVariable implements Builder.DefineVariable.
417func (b *builder) DefineVariable(variable Variable, value Value, block BasicBlock) {
418 bb := block.(*basicBlock)
419 bb.lastDefinitions[variable] = value
420}
421
422// DefineVariableInCurrentBB implements Builder.DefineVariableInCurrentBB.
423func (b *builder) DefineVariableInCurrentBB(variable Variable, value Value) {
424 b.DefineVariable(variable, value, b.currentBB)
425}
426
427// SetCurrentBlock implements Builder.SetCurrentBlock.
428func (b *builder) SetCurrentBlock(bb BasicBlock) {
429 b.currentBB = bb.(*basicBlock)
430}
431
432// CurrentBlock implements Builder.CurrentBlock.
433func (b *builder) CurrentBlock() BasicBlock {
434 return b.currentBB
435}
436
437// EntryBlock implements Builder.EntryBlock.
438func (b *builder) EntryBlock() BasicBlock {
439 return b.entryBlk()
440}
441
442// DeclareVariable implements Builder.DeclareVariable.
443func (b *builder) DeclareVariable(typ Type) Variable {
444 v := b.nextVariable
445 b.nextVariable++
446 return v.setType(typ)
447}
448
449// allocateValue implements Builder.AllocateValue.
450func (b *builder) allocateValue(typ Type) (v Value) {
451 v = Value(b.nextValueID)
452 v = v.setType(typ)
453 b.nextValueID++
454 return
455}
456
457// FindValueInLinearPath implements Builder.FindValueInLinearPath.
458func (b *builder) FindValueInLinearPath(variable Variable) Value {
459 return b.findValueInLinearPath(variable, b.currentBB)
460}
461
462func (b *builder) findValueInLinearPath(variable Variable, blk *basicBlock) Value {
463 if val, ok := blk.lastDefinitions[variable]; ok {
464 return val
465 } else if !blk.sealed {
466 return ValueInvalid
467 }
468
469 if pred := blk.singlePred; pred != nil {
470 // If this block is sealed and have only one predecessor,
471 // we can use the value in that block without ambiguity on definition.
472 return b.findValueInLinearPath(variable, pred)
473 }
474 if len(blk.preds) == 1 {
475 panic("BUG")
476 }
477 return ValueInvalid
478}
479
480// MustFindValue implements Builder.MustFindValue.
481func (b *builder) MustFindValue(variable Variable) Value {
482 return b.findValue(variable.getType(), variable, b.currentBB)
483}
484
485// findValue recursively tries to find the latest definition of a `variable`. The algorithm is described in
486// the section 2 of the paper https://link.springer.com/content/pdf/10.1007/978-3-642-37051-9_6.pdf.
487//
488// TODO: reimplement this in iterative, not recursive, to avoid stack overflow.
489func (b *builder) findValue(typ Type, variable Variable, blk *basicBlock) Value {
490 if val, ok := blk.lastDefinitions[variable]; ok {
491 // The value is already defined in this block!
492 return val
493 } else if !blk.sealed { // Incomplete CFG as in the paper.
494 // If this is not sealed, that means it might have additional unknown predecessor later on.
495 // So we temporarily define the placeholder value here (not add as a parameter yet!),
496 // and record it as unknown.
497 // The unknown values are resolved when we call seal this block via BasicBlock.Seal().
498 value := b.allocateValue(typ)
499 if wazevoapi.SSALoggingEnabled {
500 fmt.Printf("adding unknown value placeholder for %s at %d\n", variable, blk.id)
501 }
502 blk.lastDefinitions[variable] = value
503 blk.unknownValues = append(blk.unknownValues, unknownValue{
504 variable: variable,
505 value: value,
506 })
507 return value
508 } else if blk.EntryBlock() {
509 // If this is the entry block, we reach the uninitialized variable which has zero value.
510 return b.zeros[variable.getType()]
511 }
512
513 if pred := blk.singlePred; pred != nil {
514 // If this block is sealed and have only one predecessor,
515 // we can use the value in that block without ambiguity on definition.
516 return b.findValue(typ, variable, pred)
517 } else if len(blk.preds) == 0 {
518 panic("BUG: value is not defined for " + variable.String())
519 }
520
521 // If this block has multiple predecessors, we have to gather the definitions,
522 // and treat them as an argument to this block.
523 //
524 // But before that, we have to check if the possible definitions are the same Value.
525 tmpValue := b.allocateValue(typ)
526 // Break the cycle by defining the variable with the tmpValue.
527 b.DefineVariable(variable, tmpValue, blk)
528 // Check all the predecessors if they have the same definition.
529 uniqueValue := ValueInvalid
530 for i := range blk.preds {
531 predValue := b.findValue(typ, variable, blk.preds[i].blk)
532 if uniqueValue == ValueInvalid {
533 uniqueValue = predValue
534 } else if uniqueValue != predValue {
535 uniqueValue = ValueInvalid
536 break
537 }
538 }
539
540 if uniqueValue != ValueInvalid {
541 // If all the predecessors have the same definition, we can use that value.
542 b.alias(tmpValue, uniqueValue)
543 return uniqueValue
544 } else {
545 // Otherwise, add the tmpValue to this block as a parameter which may or may not be redundant, but
546 // later we eliminate trivial params in an optimization pass. This must be done before finding the
547 // definitions in the predecessors so that we can break the cycle.
548 blk.addParamOn(b, tmpValue)
549 // After the new param is added, we have to manipulate the original branching instructions
550 // in predecessors so that they would pass the definition of `variable` as the argument to
551 // the newly added PHI.
552 for i := range blk.preds {
553 pred := &blk.preds[i]
554 value := b.findValue(typ, variable, pred.blk)
555 pred.branch.addArgumentBranchInst(b, value)
556 }
557 return tmpValue
558 }
559}
560
561// Seal implements Builder.Seal.
562func (b *builder) Seal(raw BasicBlock) {
563 blk := raw.(*basicBlock)
564 if len(blk.preds) == 1 {
565 blk.singlePred = blk.preds[0].blk
566 }
567 blk.sealed = true
568
569 for _, v := range blk.unknownValues {
570 variable, phiValue := v.variable, v.value
571 typ := variable.getType()
572 blk.addParamOn(b, phiValue)
573 for i := range blk.preds {
574 pred := &blk.preds[i]
575 predValue := b.findValue(typ, variable, pred.blk)
576 if !predValue.Valid() {
577 panic("BUG: value is not defined anywhere in the predecessors in the CFG")
578 }
579 pred.branch.addArgumentBranchInst(b, predValue)
580 }
581 }
582}
583
584// Format implements Builder.Format.
585func (b *builder) Format() string {
586 str := strings.Builder{}
587 usedSigs := b.usedSignatures()
588 if len(usedSigs) > 0 {
589 str.WriteByte('\n')
590 str.WriteString("signatures:\n")
591 for _, sig := range usedSigs {
592 str.WriteByte('\t')
593 str.WriteString(sig.String())
594 str.WriteByte('\n')
595 }
596 }
597
598 var iterBegin, iterNext func() *basicBlock
599 if b.doneBlockLayout {
600 iterBegin, iterNext = b.blockIteratorReversePostOrderBegin, b.blockIteratorReversePostOrderNext
601 } else {
602 iterBegin, iterNext = b.blockIteratorBegin, b.blockIteratorNext
603 }
604 for bb := iterBegin(); bb != nil; bb = iterNext() {
605 str.WriteByte('\n')
606 str.WriteString(bb.formatHeader(b))
607 str.WriteByte('\n')
608
609 for cur := bb.Root(); cur != nil; cur = cur.Next() {
610 str.WriteByte('\t')
611 str.WriteString(cur.Format(b))
612 str.WriteByte('\n')
613 }
614 }
615 return str.String()
616}
617
618// BlockIteratorNext implements Builder.BlockIteratorNext.
619func (b *builder) BlockIteratorNext() BasicBlock {
620 if blk := b.blockIteratorNext(); blk == nil {
621 return nil // BasicBlock((*basicBlock)(nil)) != BasicBlock(nil)
622 } else {
623 return blk
624 }
625}
626
627// BlockIteratorNext implements Builder.BlockIteratorNext.
628func (b *builder) blockIteratorNext() *basicBlock {
629 index := b.blockIterCur
630 for {
631 if index == b.basicBlocksPool.Allocated() {
632 return nil
633 }
634 ret := b.basicBlocksPool.View(index)
635 index++
636 if !ret.invalid {
637 b.blockIterCur = index
638 return ret
639 }
640 }
641}
642
643// BlockIteratorBegin implements Builder.BlockIteratorBegin.
644func (b *builder) BlockIteratorBegin() BasicBlock {
645 return b.blockIteratorBegin()
646}
647
648// BlockIteratorBegin implements Builder.BlockIteratorBegin.
649func (b *builder) blockIteratorBegin() *basicBlock {
650 b.blockIterCur = 0
651 return b.blockIteratorNext()
652}
653
654// BlockIteratorReversePostOrderBegin implements Builder.BlockIteratorReversePostOrderBegin.
655func (b *builder) BlockIteratorReversePostOrderBegin() BasicBlock {
656 return b.blockIteratorReversePostOrderBegin()
657}
658
659// BlockIteratorBegin implements Builder.BlockIteratorBegin.
660func (b *builder) blockIteratorReversePostOrderBegin() *basicBlock {
661 b.blockIterCur = 0
662 return b.blockIteratorReversePostOrderNext()
663}
664
665// BlockIteratorReversePostOrderNext implements Builder.BlockIteratorReversePostOrderNext.
666func (b *builder) BlockIteratorReversePostOrderNext() BasicBlock {
667 if blk := b.blockIteratorReversePostOrderNext(); blk == nil {
668 return nil // BasicBlock((*basicBlock)(nil)) != BasicBlock(nil)
669 } else {
670 return blk
671 }
672}
673
674// BlockIteratorNext implements Builder.BlockIteratorNext.
675func (b *builder) blockIteratorReversePostOrderNext() *basicBlock {
676 if b.blockIterCur >= len(b.reversePostOrderedBasicBlocks) {
677 return nil
678 } else {
679 ret := b.reversePostOrderedBasicBlocks[b.blockIterCur]
680 b.blockIterCur++
681 return ret
682 }
683}
684
685// ValuesInfo implements Builder.ValuesInfo.
686func (b *builder) ValuesInfo() []ValueInfo {
687 return b.valuesInfo
688}
689
690// alias records the alias of the given values. The alias(es) will be
691// eliminated in the optimization pass via resolveArgumentAlias.
692func (b *builder) alias(dst, src Value) {
693 did := int(dst.ID())
694 if did >= len(b.valuesInfo) {
695 l := did + 1 - len(b.valuesInfo)
696 b.valuesInfo = append(b.valuesInfo, make([]ValueInfo, l)...)
697 view := b.valuesInfo[len(b.valuesInfo)-l:]
698 for i := range view {
699 view[i].alias = ValueInvalid
700 }
701 }
702 b.valuesInfo[did].alias = src
703}
704
705// resolveArgumentAlias resolves the alias of the arguments of the given instruction.
706func (b *builder) resolveArgumentAlias(instr *Instruction) {
707 if instr.v.Valid() {
708 instr.v = b.resolveAlias(instr.v)
709 }
710
711 if instr.v2.Valid() {
712 instr.v2 = b.resolveAlias(instr.v2)
713 }
714
715 if instr.v3.Valid() {
716 instr.v3 = b.resolveAlias(instr.v3)
717 }
718
719 view := instr.vs.View()
720 for i, v := range view {
721 view[i] = b.resolveAlias(v)
722 }
723}
724
725// resolveAlias resolves the alias of the given value.
726func (b *builder) resolveAlias(v Value) Value {
727 info := b.valuesInfo
728 l := ValueID(len(info))
729 // Some aliases are chained, so we need to resolve them recursively.
730 for {
731 vid := v.ID()
732 if vid < l && info[vid].alias.Valid() {
733 v = info[vid].alias
734 } else {
735 break
736 }
737 }
738 return v
739}
740
741// entryBlk returns the entry block of the function.
742func (b *builder) entryBlk() *basicBlock {
743 return b.basicBlocksPool.View(0)
744}
745
746// isDominatedBy returns true if the given block `n` is dominated by the given block `d`.
747// Before calling this, the builder must pass by passCalculateImmediateDominators.
748func (b *builder) isDominatedBy(n *basicBlock, d *basicBlock) bool {
749 if len(b.dominators) == 0 {
750 panic("BUG: passCalculateImmediateDominators must be called before calling isDominatedBy")
751 }
752 ent := b.entryBlk()
753 doms := b.dominators
754 for n != d && n != ent {
755 n = doms[n.id]
756 }
757 return n == d
758}
759
760// BlockIDMax implements Builder.BlockIDMax.
761func (b *builder) BlockIDMax() BasicBlockID {
762 return BasicBlockID(b.basicBlocksPool.Allocated())
763}
764
765// InsertUndefined implements Builder.InsertUndefined.
766func (b *builder) InsertUndefined() {
767 instr := b.AllocateInstruction()
768 instr.opcode = OpcodeUndefined
769 b.InsertInstruction(instr)
770}
771
772// LoopNestingForestRoots implements Builder.LoopNestingForestRoots.
773func (b *builder) LoopNestingForestRoots() []BasicBlock {
774 return b.loopNestingForestRoots
775}
776
777// LowestCommonAncestor implements Builder.LowestCommonAncestor.
778func (b *builder) LowestCommonAncestor(blk1, blk2 BasicBlock) BasicBlock {
779 return b.sparseTree.findLCA(blk1.ID(), blk2.ID())
780}
781
782// InstructionOfValue returns the instruction that produces the given Value, or nil
783// if the Value is not produced by any instruction.
784func (b *builder) InstructionOfValue(v Value) *Instruction {
785 instrID := v.instructionID()
786 if instrID <= 0 {
787 return nil
788 }
789 return b.instructionsPool.View(instrID - 1)
790}