1package ssa
2
3import (
4 "fmt"
5 "strconv"
6 "strings"
7
8 "github.com/tetratelabs/wazero/internal/engine/wazevo/wazevoapi"
9)
10
11// BasicBlock represents the Basic Block of an SSA function.
12// Each BasicBlock always ends with branching instructions (e.g. Branch, Return, etc.),
13// and at most two branches are allowed. If there's two branches, these two are placed together at the end of the block.
14// In other words, there's no branching instruction in the middle of the block.
15//
16// Note: we use the "block argument" variant of SSA, instead of PHI functions. See the package level doc comments.
17//
18// Note: we use "parameter/param" as a placeholder which represents a variant of PHI, and "argument/arg" as an actual
19// Value passed to that "parameter/param".
20type BasicBlock interface {
21 // ID returns the unique ID of this block.
22 ID() BasicBlockID
23
24 // Name returns the unique string ID of this block. e.g. blk0, blk1, ...
25 Name() string
26
27 // AddParam adds the parameter to the block whose type specified by `t`.
28 AddParam(b Builder, t Type) Value
29
30 // Params returns the number of parameters to this block.
31 Params() int
32
33 // Param returns (Variable, Value) which corresponds to the i-th parameter of this block.
34 // The returned Value is the definition of the param in this block.
35 Param(i int) Value
36
37 // Root returns the root instruction of this block.
38 Root() *Instruction
39
40 // Tail returns the tail instruction of this block.
41 Tail() *Instruction
42
43 // EntryBlock returns true if this block represents the function entry.
44 EntryBlock() bool
45
46 // ReturnBlock returns ture if this block represents the function return.
47 ReturnBlock() bool
48
49 // Valid is true if this block is still valid even after optimizations.
50 Valid() bool
51
52 // Sealed is true if this block has been sealed.
53 Sealed() bool
54
55 // Preds returns the number of predecessors of this block.
56 Preds() int
57
58 // Pred returns the i-th predecessor of this block.
59 Pred(i int) BasicBlock
60
61 // Succs returns the number of successors of this block.
62 Succs() int
63
64 // Succ returns the i-th successor of this block.
65 Succ(i int) BasicBlock
66
67 // LoopHeader returns true if this block is a loop header.
68 LoopHeader() bool
69
70 // LoopNestingForestChildren returns the children of this block in the loop nesting forest.
71 LoopNestingForestChildren() []BasicBlock
72}
73
74type (
75 // basicBlock is a basic block in a SSA-transformed function.
76 basicBlock struct {
77 id BasicBlockID
78 rootInstr, currentInstr *Instruction
79 // params are Values that represent parameters to a basicBlock.
80 // Each parameter can be considered as an output of PHI instruction in traditional SSA.
81 params Values
82 preds []basicBlockPredecessorInfo
83 success []*basicBlock
84 // singlePred is the alias to preds[0] for fast lookup, and only set after Seal is called.
85 singlePred *basicBlock
86 // lastDefinitions maps Variable to its last definition in this block.
87 lastDefinitions map[Variable]Value
88 // unknownsValues are used in builder.findValue. The usage is well-described in the paper.
89 unknownValues []unknownValue
90 // invalid is true if this block is made invalid during optimizations.
91 invalid bool
92 // sealed is true if this is sealed (all the predecessors are known).
93 sealed bool
94 // loopHeader is true if this block is a loop header:
95 //
96 // > A loop header (sometimes called the entry point of the loop) is a dominator that is the target
97 // > of a loop-forming back edge. The loop header dominates all blocks in the loop body.
98 // > A block may be a loop header for more than one loop. A loop may have multiple entry points,
99 // > in which case it has no "loop header".
100 //
101 // See https://en.wikipedia.org/wiki/Control-flow_graph for more details.
102 //
103 // This is modified during the subPassLoopDetection pass.
104 loopHeader bool
105
106 // loopNestingForestChildren holds the children of this block in the loop nesting forest.
107 // Non-empty if and only if this block is a loop header (i.e. loopHeader=true)
108 loopNestingForestChildren wazevoapi.VarLength[BasicBlock]
109
110 // reversePostOrder is used to sort all the blocks in the function in reverse post order.
111 // This is used in builder.LayoutBlocks.
112 reversePostOrder int32
113
114 // visited is used during various traversals.
115 visited int32
116
117 // child and sibling are the ones in the dominator tree.
118 child, sibling *basicBlock
119 }
120 // BasicBlockID is the unique ID of a basicBlock.
121 BasicBlockID uint32
122
123 unknownValue struct {
124 // variable is the variable that this unknownValue represents.
125 variable Variable
126 // value is the value that this unknownValue represents.
127 value Value
128 }
129)
130
131// basicBlockVarLengthNil is the default nil value for basicBlock.loopNestingForestChildren.
132var basicBlockVarLengthNil = wazevoapi.NewNilVarLength[BasicBlock]()
133
134const basicBlockIDReturnBlock = 0xffffffff
135
136// Name implements BasicBlock.Name.
137func (bb *basicBlock) Name() string {
138 if bb.id == basicBlockIDReturnBlock {
139 return "blk_ret"
140 } else {
141 return fmt.Sprintf("blk%d", bb.id)
142 }
143}
144
145// String implements fmt.Stringer for debugging.
146func (bid BasicBlockID) String() string {
147 if bid == basicBlockIDReturnBlock {
148 return "blk_ret"
149 } else {
150 return fmt.Sprintf("blk%d", bid)
151 }
152}
153
154// ID implements BasicBlock.ID.
155func (bb *basicBlock) ID() BasicBlockID {
156 return bb.id
157}
158
159// basicBlockPredecessorInfo is the information of a predecessor of a basicBlock.
160// predecessor is determined by a pair of block and the branch instruction used to jump to the successor.
161type basicBlockPredecessorInfo struct {
162 blk *basicBlock
163 branch *Instruction
164}
165
166// EntryBlock implements BasicBlock.EntryBlock.
167func (bb *basicBlock) EntryBlock() bool {
168 return bb.id == 0
169}
170
171// ReturnBlock implements BasicBlock.ReturnBlock.
172func (bb *basicBlock) ReturnBlock() bool {
173 return bb.id == basicBlockIDReturnBlock
174}
175
176// AddParam implements BasicBlock.AddParam.
177func (bb *basicBlock) AddParam(b Builder, typ Type) Value {
178 paramValue := b.allocateValue(typ)
179 bb.params = bb.params.Append(&b.(*builder).varLengthPool, paramValue)
180 return paramValue
181}
182
183// addParamOn adds a parameter to this block whose value is already allocated.
184func (bb *basicBlock) addParamOn(b *builder, value Value) {
185 bb.params = bb.params.Append(&b.varLengthPool, value)
186}
187
188// Params implements BasicBlock.Params.
189func (bb *basicBlock) Params() int {
190 return len(bb.params.View())
191}
192
193// Param implements BasicBlock.Param.
194func (bb *basicBlock) Param(i int) Value {
195 return bb.params.View()[i]
196}
197
198// Valid implements BasicBlock.Valid.
199func (bb *basicBlock) Valid() bool {
200 return !bb.invalid
201}
202
203// Sealed implements BasicBlock.Sealed.
204func (bb *basicBlock) Sealed() bool {
205 return bb.sealed
206}
207
208// insertInstruction implements BasicBlock.InsertInstruction.
209func (bb *basicBlock) insertInstruction(b *builder, next *Instruction) {
210 current := bb.currentInstr
211 if current != nil {
212 current.next = next
213 next.prev = current
214 } else {
215 bb.rootInstr = next
216 }
217 bb.currentInstr = next
218
219 switch next.opcode {
220 case OpcodeJump, OpcodeBrz, OpcodeBrnz:
221 target := BasicBlockID(next.rValue)
222 b.basicBlock(target).addPred(bb, next)
223 case OpcodeBrTable:
224 for _, _target := range next.rValues.View() {
225 target := BasicBlockID(_target)
226 b.basicBlock(target).addPred(bb, next)
227 }
228 }
229}
230
231// NumPreds implements BasicBlock.NumPreds.
232func (bb *basicBlock) NumPreds() int {
233 return len(bb.preds)
234}
235
236// Preds implements BasicBlock.Preds.
237func (bb *basicBlock) Preds() int {
238 return len(bb.preds)
239}
240
241// Pred implements BasicBlock.Pred.
242func (bb *basicBlock) Pred(i int) BasicBlock {
243 return bb.preds[i].blk
244}
245
246// Succs implements BasicBlock.Succs.
247func (bb *basicBlock) Succs() int {
248 return len(bb.success)
249}
250
251// Succ implements BasicBlock.Succ.
252func (bb *basicBlock) Succ(i int) BasicBlock {
253 return bb.success[i]
254}
255
256// Root implements BasicBlock.Root.
257func (bb *basicBlock) Root() *Instruction {
258 return bb.rootInstr
259}
260
261// Tail implements BasicBlock.Tail.
262func (bb *basicBlock) Tail() *Instruction {
263 return bb.currentInstr
264}
265
266// reset resets the basicBlock to its initial state so that it can be reused for another function.
267func resetBasicBlock(bb *basicBlock) {
268 bb.params = ValuesNil
269 bb.rootInstr, bb.currentInstr = nil, nil
270 bb.preds = bb.preds[:0]
271 bb.success = bb.success[:0]
272 bb.invalid, bb.sealed = false, false
273 bb.singlePred = nil
274 bb.unknownValues = bb.unknownValues[:0]
275 bb.lastDefinitions = wazevoapi.ResetMap(bb.lastDefinitions)
276 bb.reversePostOrder = -1
277 bb.visited = 0
278 bb.loopNestingForestChildren = basicBlockVarLengthNil
279 bb.loopHeader = false
280 bb.sibling = nil
281 bb.child = nil
282}
283
284// addPred adds a predecessor to this block specified by the branch instruction.
285func (bb *basicBlock) addPred(blk BasicBlock, branch *Instruction) {
286 if bb.sealed {
287 panic("BUG: trying to add predecessor to a sealed block: " + bb.Name())
288 }
289
290 pred := blk.(*basicBlock)
291 for i := range bb.preds {
292 existingPred := &bb.preds[i]
293 if existingPred.blk == pred && existingPred.branch != branch {
294 // If the target is already added, then this must come from the same BrTable,
295 // otherwise such redundant branch should be eliminated by the frontend. (which should be simpler).
296 panic(fmt.Sprintf("BUG: redundant non BrTable jumps in %s whose targes are the same", bb.Name()))
297 }
298 }
299
300 bb.preds = append(bb.preds, basicBlockPredecessorInfo{
301 blk: pred,
302 branch: branch,
303 })
304
305 pred.success = append(pred.success, bb)
306}
307
308// formatHeader returns the string representation of the header of the basicBlock.
309func (bb *basicBlock) formatHeader(b Builder) string {
310 ps := make([]string, len(bb.params.View()))
311 for i, p := range bb.params.View() {
312 ps[i] = p.formatWithType(b)
313 }
314
315 if len(bb.preds) > 0 {
316 preds := make([]string, 0, len(bb.preds))
317 for _, pred := range bb.preds {
318 if pred.blk.invalid {
319 continue
320 }
321 preds = append(preds, fmt.Sprintf("blk%d", pred.blk.id))
322
323 }
324 return fmt.Sprintf("blk%d: (%s) <-- (%s)",
325 bb.id, strings.Join(ps, ","), strings.Join(preds, ","))
326 } else {
327 return fmt.Sprintf("blk%d: (%s)", bb.id, strings.Join(ps, ", "))
328 }
329}
330
331// validates validates the basicBlock for debugging purpose.
332func (bb *basicBlock) validate(b *builder) {
333 if bb.invalid {
334 panic("BUG: trying to validate an invalid block: " + bb.Name())
335 }
336 if len(bb.preds) > 0 {
337 for _, pred := range bb.preds {
338 if pred.branch.opcode != OpcodeBrTable {
339 blockID := int(pred.branch.rValue)
340 target := b.basicBlocksPool.View(blockID)
341 if target != bb {
342 panic(fmt.Sprintf("BUG: '%s' is not branch to %s, but to %s",
343 pred.branch.Format(b), bb.Name(), target.Name()))
344 }
345 }
346
347 var exp int
348 if bb.ReturnBlock() {
349 exp = len(b.currentSignature.Results)
350 } else {
351 exp = len(bb.params.View())
352 }
353
354 if len(pred.branch.vs.View()) != exp {
355 panic(fmt.Sprintf(
356 "BUG: len(argument at %s) != len(params at %s): %d != %d: %s",
357 pred.blk.Name(), bb.Name(),
358 len(pred.branch.vs.View()), len(bb.params.View()), pred.branch.Format(b),
359 ))
360 }
361
362 }
363 }
364}
365
366// String implements fmt.Stringer for debugging purpose only.
367func (bb *basicBlock) String() string {
368 return strconv.Itoa(int(bb.id))
369}
370
371// LoopNestingForestChildren implements BasicBlock.LoopNestingForestChildren.
372func (bb *basicBlock) LoopNestingForestChildren() []BasicBlock {
373 return bb.loopNestingForestChildren.View()
374}
375
376// LoopHeader implements BasicBlock.LoopHeader.
377func (bb *basicBlock) LoopHeader() bool {
378 return bb.loopHeader
379}