| 1 |
package backend |
| 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 |
// Lower implements Compiler.Lower. |
| 9 |
func (c *compiler) Lower() { |
| 10 |
c.assignVirtualRegisters() |
| 11 |
c.mach.SetCurrentABI(c.GetFunctionABI(c.ssaBuilder.Signature())) |
| 12 |
c.mach.StartLoweringFunction(c.ssaBuilder.BlockIDMax()) |
| 13 |
c.lowerBlocks() |
| 14 |
} |
| 15 |
|
| 16 |
// lowerBlocks lowers each block in the ssa.Builder. |
| 17 |
func (c *compiler) lowerBlocks() { |
| 18 |
builder := c.ssaBuilder |
| 19 |
for blk := builder.BlockIteratorReversePostOrderBegin(); blk != nil; blk = builder.BlockIteratorReversePostOrderNext() { |
| 20 |
c.lowerBlock(blk) |
| 21 |
} |
| 22 |
|
| 23 |
// After lowering all blocks, we need to link adjacent blocks to layout one single instruction list. |
| 24 |
var prev ssa.BasicBlock |
| 25 |
for next := builder.BlockIteratorReversePostOrderBegin(); next != nil; next = builder.BlockIteratorReversePostOrderNext() { |
| 26 |
if prev != nil { |
| 27 |
c.mach.LinkAdjacentBlocks(prev, next) |
| 28 |
} |
| 29 |
prev = next |
| 30 |
} |
| 31 |
} |
| 32 |
|
| 33 |
func (c *compiler) lowerBlock(blk ssa.BasicBlock) { |
| 34 |
mach := c.mach |
| 35 |
mach.StartBlock(blk) |
| 36 |
|
| 37 |
// We traverse the instructions in reverse order because we might want to lower multiple |
| 38 |
// instructions together. |
| 39 |
cur := blk.Tail() |
| 40 |
|
| 41 |
// First gather the branching instructions at the end of the blocks. |
| 42 |
var br0, br1 *ssa.Instruction |
| 43 |
if cur.IsBranching() { |
| 44 |
br0 = cur |
| 45 |
cur = cur.Prev() |
| 46 |
if cur != nil && cur.IsBranching() { |
| 47 |
br1 = cur |
| 48 |
cur = cur.Prev() |
| 49 |
} |
| 50 |
} |
| 51 |
|
| 52 |
if br0 != nil { |
| 53 |
c.lowerBranches(br0, br1) |
| 54 |
} |
| 55 |
|
| 56 |
if br1 != nil && br0 == nil { |
| 57 |
panic("BUG? when a block has conditional branch but doesn't end with an unconditional branch?") |
| 58 |
} |
| 59 |
|
| 60 |
// Now start lowering the non-branching instructions. |
| 61 |
for ; cur != nil; cur = cur.Prev() { |
| 62 |
c.setCurrentGroupID(cur.GroupID()) |
| 63 |
if cur.Lowered() { |
| 64 |
continue |
| 65 |
} |
| 66 |
|
| 67 |
switch cur.Opcode() { |
| 68 |
case ssa.OpcodeReturn: |
| 69 |
rets := cur.ReturnVals() |
| 70 |
if len(rets) > 0 { |
| 71 |
c.mach.LowerReturns(rets) |
| 72 |
} |
| 73 |
c.mach.InsertReturn() |
| 74 |
default: |
| 75 |
mach.LowerInstr(cur) |
| 76 |
} |
| 77 |
mach.FlushPendingInstructions() |
| 78 |
} |
| 79 |
|
| 80 |
// Finally, if this is the entry block, we have to insert copies of arguments from the real location to the VReg. |
| 81 |
if blk.EntryBlock() { |
| 82 |
c.lowerFunctionArguments(blk) |
| 83 |
} |
| 84 |
|
| 85 |
mach.EndBlock() |
| 86 |
} |
| 87 |
|
| 88 |
// lowerBranches is called right after StartBlock and before any LowerInstr call if |
| 89 |
// there are branches to the given block. br0 is the very end of the block and b1 is the before the br0 if it exists. |
| 90 |
// At least br0 is not nil, but br1 can be nil if there's no branching before br0. |
| 91 |
// |
| 92 |
// See ssa.Instruction IsBranching, and the comment on ssa.BasicBlock. |
| 93 |
func (c *compiler) lowerBranches(br0, br1 *ssa.Instruction) { |
| 94 |
mach := c.mach |
| 95 |
|
| 96 |
c.setCurrentGroupID(br0.GroupID()) |
| 97 |
c.mach.LowerSingleBranch(br0) |
| 98 |
mach.FlushPendingInstructions() |
| 99 |
if br1 != nil { |
| 100 |
c.setCurrentGroupID(br1.GroupID()) |
| 101 |
c.mach.LowerConditionalBranch(br1) |
| 102 |
mach.FlushPendingInstructions() |
| 103 |
} |
| 104 |
|
| 105 |
if br0.Opcode() == ssa.OpcodeJump { |
| 106 |
_, args, targetBlockID := br0.BranchData() |
| 107 |
argExists := len(args) != 0 |
| 108 |
if argExists && br1 != nil { |
| 109 |
panic("BUG: critical edge split failed") |
| 110 |
} |
| 111 |
target := c.ssaBuilder.BasicBlock(targetBlockID) |
| 112 |
if argExists && target.ReturnBlock() { |
| 113 |
if len(args) > 0 { |
| 114 |
c.mach.LowerReturns(args) |
| 115 |
} |
| 116 |
} else if argExists { |
| 117 |
c.lowerBlockArguments(args, target) |
| 118 |
} |
| 119 |
} |
| 120 |
mach.FlushPendingInstructions() |
| 121 |
} |
| 122 |
|
| 123 |
func (c *compiler) lowerFunctionArguments(entry ssa.BasicBlock) { |
| 124 |
mach := c.mach |
| 125 |
|
| 126 |
c.tmpVals = c.tmpVals[:0] |
| 127 |
data := c.ssaBuilder.ValuesInfo() |
| 128 |
for i := 0; i < entry.Params(); i++ { |
| 129 |
p := entry.Param(i) |
| 130 |
if data[p.ID()].RefCount > 0 { |
| 131 |
c.tmpVals = append(c.tmpVals, p) |
| 132 |
} else { |
| 133 |
// If the argument is not used, we can just pass an invalid value. |
| 134 |
c.tmpVals = append(c.tmpVals, ssa.ValueInvalid) |
| 135 |
} |
| 136 |
} |
| 137 |
mach.LowerParams(c.tmpVals) |
| 138 |
mach.FlushPendingInstructions() |
| 139 |
} |
| 140 |
|
| 141 |
// lowerBlockArguments lowers how to pass arguments to the given successor block. |
| 142 |
func (c *compiler) lowerBlockArguments(args []ssa.Value, succ ssa.BasicBlock) { |
| 143 |
if len(args) != succ.Params() { |
| 144 |
panic("BUG: mismatched number of arguments") |
| 145 |
} |
| 146 |
|
| 147 |
c.varEdges = c.varEdges[:0] |
| 148 |
c.varEdgeTypes = c.varEdgeTypes[:0] |
| 149 |
c.constEdges = c.constEdges[:0] |
| 150 |
for i := 0; i < len(args); i++ { |
| 151 |
dst := succ.Param(i) |
| 152 |
src := args[i] |
| 153 |
|
| 154 |
dstReg := c.VRegOf(dst) |
| 155 |
srcInstr := c.ssaBuilder.InstructionOfValue(src) |
| 156 |
if srcInstr != nil && srcInstr.Constant() { |
| 157 |
c.constEdges = append(c.constEdges, struct { |
| 158 |
cInst *ssa.Instruction |
| 159 |
dst regalloc.VReg |
| 160 |
}{cInst: srcInstr, dst: dstReg}) |
| 161 |
} else { |
| 162 |
srcReg := c.VRegOf(src) |
| 163 |
// Even when the src=dst, insert the move so that we can keep such registers keep-alive. |
| 164 |
c.varEdges = append(c.varEdges, [2]regalloc.VReg{srcReg, dstReg}) |
| 165 |
c.varEdgeTypes = append(c.varEdgeTypes, src.Type()) |
| 166 |
} |
| 167 |
} |
| 168 |
|
| 169 |
// Check if there's an overlap among the dsts and srcs in varEdges. |
| 170 |
c.vRegIDs = c.vRegIDs[:0] |
| 171 |
for _, edge := range c.varEdges { |
| 172 |
src := edge[0].ID() |
| 173 |
if int(src) >= len(c.vRegSet) { |
| 174 |
c.vRegSet = append(c.vRegSet, make([]bool, src+1)...) |
| 175 |
} |
| 176 |
c.vRegSet[src] = true |
| 177 |
c.vRegIDs = append(c.vRegIDs, src) |
| 178 |
} |
| 179 |
separated := true |
| 180 |
for _, edge := range c.varEdges { |
| 181 |
dst := edge[1].ID() |
| 182 |
if int(dst) >= len(c.vRegSet) { |
| 183 |
c.vRegSet = append(c.vRegSet, make([]bool, dst+1)...) |
| 184 |
} else { |
| 185 |
if c.vRegSet[dst] { |
| 186 |
separated = false |
| 187 |
break |
| 188 |
} |
| 189 |
} |
| 190 |
} |
| 191 |
for _, id := range c.vRegIDs { |
| 192 |
c.vRegSet[id] = false // reset for the next use. |
| 193 |
} |
| 194 |
|
| 195 |
if separated { |
| 196 |
// If there's no overlap, we can simply move the source to destination. |
| 197 |
for i, edge := range c.varEdges { |
| 198 |
src, dst := edge[0], edge[1] |
| 199 |
c.mach.InsertMove(dst, src, c.varEdgeTypes[i]) |
| 200 |
} |
| 201 |
} else { |
| 202 |
// Otherwise, we allocate a temporary registers and move the source to the temporary register, |
| 203 |
// |
| 204 |
// First move all of them to temporary registers. |
| 205 |
c.tempRegs = c.tempRegs[:0] |
| 206 |
for i, edge := range c.varEdges { |
| 207 |
src := edge[0] |
| 208 |
typ := c.varEdgeTypes[i] |
| 209 |
temp := c.AllocateVReg(typ) |
| 210 |
c.tempRegs = append(c.tempRegs, temp) |
| 211 |
c.mach.InsertMove(temp, src, typ) |
| 212 |
} |
| 213 |
// Then move the temporary registers to the destination. |
| 214 |
for i, edge := range c.varEdges { |
| 215 |
temp := c.tempRegs[i] |
| 216 |
dst := edge[1] |
| 217 |
c.mach.InsertMove(dst, temp, c.varEdgeTypes[i]) |
| 218 |
} |
| 219 |
} |
| 220 |
|
| 221 |
// Finally, move the constants. |
| 222 |
for _, edge := range c.constEdges { |
| 223 |
cInst, dst := edge.cInst, edge.dst |
| 224 |
c.mach.InsertLoadConstantBlockArg(cInst, dst) |
| 225 |
} |
| 226 |
} |