diff options
Diffstat (limited to 'vendor/github.com/tetratelabs/wazero/internal/engine/wazevo/ssa/builder.go')
-rw-r--r-- | vendor/github.com/tetratelabs/wazero/internal/engine/wazevo/ssa/builder.go | 104 |
1 files changed, 74 insertions, 30 deletions
diff --git a/vendor/github.com/tetratelabs/wazero/internal/engine/wazevo/ssa/builder.go b/vendor/github.com/tetratelabs/wazero/internal/engine/wazevo/ssa/builder.go index 1fc84d2ea..0b700c4b1 100644 --- a/vendor/github.com/tetratelabs/wazero/internal/engine/wazevo/ssa/builder.go +++ b/vendor/github.com/tetratelabs/wazero/internal/engine/wazevo/ssa/builder.go @@ -54,9 +54,6 @@ type Builder interface { // MustFindValue searches the latest definition of the given Variable and returns the result. MustFindValue(variable Variable) Value - // MustFindValueInBlk is the same as MustFindValue except it searches the latest definition from the given BasicBlock. - MustFindValueInBlk(variable Variable, blk BasicBlock) Value - // FindValueInLinearPath tries to find the latest definition of the given Variable in the linear path to the current BasicBlock. // If it cannot find the definition, or it's not sealed yet, it returns ValueInvalid. FindValueInLinearPath(variable Variable) Value @@ -127,7 +124,11 @@ type Builder interface { // Idom returns the immediate dominator of the given BasicBlock. Idom(blk BasicBlock) BasicBlock + // VarLengthPool returns the VarLengthPool of Value. VarLengthPool() *wazevoapi.VarLengthPool[Value] + + // InsertZeroValue inserts a zero value constant instruction of the given type. + InsertZeroValue(t Type) } // NewBuilder returns a new Builder implementation. @@ -135,10 +136,10 @@ func NewBuilder() Builder { return &builder{ instructionsPool: wazevoapi.NewPool[Instruction](resetInstruction), basicBlocksPool: wazevoapi.NewPool[basicBlock](resetBasicBlock), + varLengthBasicBlockPool: wazevoapi.NewVarLengthPool[BasicBlock](), varLengthPool: wazevoapi.NewVarLengthPool[Value](), valueAnnotations: make(map[ValueID]string), signatures: make(map[SignatureID]*Signature), - blkVisited: make(map[*basicBlock]int), valueIDAliases: make(map[ValueID]Value), redundantParameterIndexToValue: make(map[int]Value), returnBlk: &basicBlock{id: basicBlockIDReturnBlock}, @@ -177,12 +178,13 @@ type builder struct { dominators []*basicBlock sparseTree dominatorSparseTree + varLengthBasicBlockPool wazevoapi.VarLengthPool[BasicBlock] + // loopNestingForestRoots are the roots of the loop nesting forest. loopNestingForestRoots []BasicBlock // The followings are used for optimization passes/deterministic compilation. instStack []*Instruction - blkVisited map[*basicBlock]int valueIDToInstruction []*Instruction blkStack []*basicBlock blkStack2 []*basicBlock @@ -200,6 +202,32 @@ type builder struct { donePostBlockLayoutPasses bool currentSourceOffset SourceOffset + + // zeros are the zero value constants for each type. + zeros [typeEnd]Value +} + +// InsertZeroValue implements Builder.InsertZeroValue. +func (b *builder) InsertZeroValue(t Type) { + if b.zeros[t].Valid() { + return + } + zeroInst := b.AllocateInstruction() + switch t { + case TypeI32: + zeroInst.AsIconst32(0) + case TypeI64: + zeroInst.AsIconst64(0) + case TypeF32: + zeroInst.AsF32const(0) + case TypeF64: + zeroInst.AsF64const(0) + case TypeV128: + zeroInst.AsVconst(0, 0) + default: + panic("TODO: " + t.String()) + } + b.zeros[t] = zeroInst.Insert(b).Return() } func (b *builder) VarLengthPool() *wazevoapi.VarLengthPool[Value] { @@ -215,10 +243,12 @@ func (b *builder) ReturnBlock() BasicBlock { func (b *builder) Init(s *Signature) { b.nextVariable = 0 b.currentSignature = s + b.zeros = [typeEnd]Value{ValueInvalid, ValueInvalid, ValueInvalid, ValueInvalid, ValueInvalid, ValueInvalid} resetBasicBlock(b.returnBlk) b.instructionsPool.Reset() b.basicBlocksPool.Reset() b.varLengthPool.Reset() + b.varLengthBasicBlockPool.Reset() b.donePreBlockLayoutPasses = false b.doneBlockLayout = false b.donePostBlockLayoutPasses = false @@ -231,11 +261,6 @@ func (b *builder) Init(s *Signature) { b.blkStack2 = b.blkStack2[:0] b.dominators = b.dominators[:0] b.loopNestingForestRoots = b.loopNestingForestRoots[:0] - - for i := 0; i < b.basicBlocksPool.Allocated(); i++ { - blk := b.basicBlocksPool.View(i) - delete(b.blkVisited, blk) - } b.basicBlocksPool.Reset() for v := ValueID(0); v < b.nextValueID; v++ { @@ -448,11 +473,6 @@ func (b *builder) findValueInLinearPath(variable Variable, blk *basicBlock) Valu return ValueInvalid } -func (b *builder) MustFindValueInBlk(variable Variable, blk BasicBlock) Value { - typ := b.definedVariableType(variable) - return b.findValue(typ, variable, blk.(*basicBlock)) -} - // MustFindValue implements Builder.MustFindValue. func (b *builder) MustFindValue(variable Variable) Value { typ := b.definedVariableType(variable) @@ -482,6 +502,9 @@ func (b *builder) findValue(typ Type, variable Variable, blk *basicBlock) Value value: value, }) return value + } else if blk.EntryBlock() { + // If this is the entry block, we reach the uninitialized variable which has zero value. + return b.zeros[b.definedVariableType(variable)] } if pred := blk.singlePred; pred != nil { @@ -495,21 +518,42 @@ func (b *builder) findValue(typ Type, variable Variable, blk *basicBlock) Value // If this block has multiple predecessors, we have to gather the definitions, // and treat them as an argument to this block. // - // The first thing is to define a new parameter to this block which may or may not be redundant, but - // later we eliminate trivial params in an optimization pass. This must be done before finding the - // definitions in the predecessors so that we can break the cycle. - paramValue := blk.AddParam(b, typ) - b.DefineVariable(variable, paramValue, blk) - - // After the new param is added, we have to manipulate the original branching instructions - // in predecessors so that they would pass the definition of `variable` as the argument to - // the newly added PHI. + // But before that, we have to check if the possible definitions are the same Value. + tmpValue := b.allocateValue(typ) + // Break the cycle by defining the variable with the tmpValue. + b.DefineVariable(variable, tmpValue, blk) + // Check all the predecessors if they have the same definition. + uniqueValue := ValueInvalid for i := range blk.preds { - pred := &blk.preds[i] - value := b.findValue(typ, variable, pred.blk) - pred.branch.addArgumentBranchInst(b, value) + predValue := b.findValue(typ, variable, blk.preds[i].blk) + if uniqueValue == ValueInvalid { + uniqueValue = predValue + } else if uniqueValue != predValue { + uniqueValue = ValueInvalid + break + } + } + + if uniqueValue != ValueInvalid { + // If all the predecessors have the same definition, we can use that value. + b.DefineVariable(variable, uniqueValue, blk) + b.alias(tmpValue, uniqueValue) + return uniqueValue + } else { + // Otherwise, add the tmpValue to this block as a parameter which may or may not be redundant, but + // later we eliminate trivial params in an optimization pass. This must be done before finding the + // definitions in the predecessors so that we can break the cycle. + blk.addParamOn(tmpValue) + // After the new param is added, we have to manipulate the original branching instructions + // in predecessors so that they would pass the definition of `variable` as the argument to + // the newly added PHI. + for i := range blk.preds { + pred := &blk.preds[i] + value := b.findValue(typ, variable, pred.blk) + pred.branch.addArgumentBranchInst(b, value) + } + return tmpValue } - return paramValue } // Seal implements Builder.Seal. @@ -523,7 +567,7 @@ func (b *builder) Seal(raw BasicBlock) { for _, v := range blk.unknownValues { variable, phiValue := v.variable, v.value typ := b.definedVariableType(variable) - blk.addParamOn(typ, phiValue) + blk.addParamOn(phiValue) for i := range blk.preds { pred := &blk.preds[i] predValue := b.findValue(typ, variable, pred.blk) @@ -566,7 +610,7 @@ func (b *builder) Format() string { } for bb := iterBegin(); bb != nil; bb = iterNext() { str.WriteByte('\n') - str.WriteString(bb.FormatHeader(b)) + str.WriteString(bb.formatHeader(b)) str.WriteByte('\n') for cur := bb.Root(); cur != nil; cur = cur.Next() { |