summaryrefslogtreecommitdiff
path: root/vendor/github.com/tetratelabs/wazero/internal/engine/wazevo/ssa/builder.go
diff options
context:
space:
mode:
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.go104
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() {