diff options
| -rw-r--r-- | src/ir/properties.cpp | 45 | ||||
| -rw-r--r-- | src/ir/properties.h | 5 | ||||
| -rw-r--r-- | src/passes/LocalCSE.cpp | 50 | ||||
| -rw-r--r-- | src/passes/OptimizeInstructions.cpp | 2 | ||||
| -rw-r--r-- | test/lit/passes/local-cse.wast | 43 |
5 files changed, 116 insertions, 29 deletions
diff --git a/src/ir/properties.cpp b/src/ir/properties.cpp index 05dae897e..1346f6cad 100644 --- a/src/ir/properties.cpp +++ b/src/ir/properties.cpp @@ -19,27 +19,40 @@ namespace wasm::Properties { -bool isGenerative(Expression* curr, FeatureSet features) { - struct Scanner : public PostWalker<Scanner> { - bool generative = false; +namespace { - void visitCall(Call* curr) { - // TODO: We could in principle look at the called function to see if it is - // generative. To do that we'd need to compute generativity like we - // compute global effects (we can't just peek from here, as the - // other function might be modified in parallel). - generative = true; - } - void visitCallIndirect(CallIndirect* curr) { generative = true; } - void visitCallRef(CallRef* curr) { generative = true; } - void visitStructNew(StructNew* curr) { generative = true; } - void visitArrayNew(ArrayNew* curr) { generative = true; } - void visitArrayNewFixed(ArrayNewFixed* curr) { generative = true; } - } scanner; +struct GenerativityScanner : public PostWalker<GenerativityScanner> { + bool generative = false; + + void visitCall(Call* curr) { + // TODO: We could in principle look at the called function to see if it is + // generative. To do that we'd need to compute generativity like we + // compute global effects (we can't just peek from here, as the + // other function might be modified in parallel). + generative = true; + } + void visitCallIndirect(CallIndirect* curr) { generative = true; } + void visitCallRef(CallRef* curr) { generative = true; } + void visitStructNew(StructNew* curr) { generative = true; } + void visitArrayNew(ArrayNew* curr) { generative = true; } + void visitArrayNewFixed(ArrayNewFixed* curr) { generative = true; } +}; + +} // anonymous namespace + +bool isGenerative(Expression* curr) { + GenerativityScanner scanner; scanner.walk(curr); return scanner.generative; } +// As above, but only checks |curr| and not children. +bool isShallowlyGenerative(Expression* curr) { + GenerativityScanner scanner; + scanner.visit(curr); + return scanner.generative; +} + // Checks an expression in a shallow manner (i.e., does not check children) as // to whether it is valid in a wasm constant expression. static bool isValidInConstantExpression(Module& wasm, Expression* expr) { diff --git a/src/ir/properties.h b/src/ir/properties.h index 301f15e16..4b73b7211 100644 --- a/src/ir/properties.h +++ b/src/ir/properties.h @@ -527,7 +527,10 @@ inline bool canEmitSelectWithArms(Expression* ifTrue, Expression* ifFalse) { // the latter because calls are already handled best in other manners (using // EffectAnalyzer). // -bool isGenerative(Expression* curr, FeatureSet features); +bool isGenerative(Expression* curr); + +// As above, but only checks |curr| and not children. +bool isShallowlyGenerative(Expression* curr); // Whether this expression is valid in a context where WebAssembly requires a // constant expression, such as a global initializer. diff --git a/src/passes/LocalCSE.cpp b/src/passes/LocalCSE.cpp index 52346030c..bb017e938 100644 --- a/src/passes/LocalCSE.cpp +++ b/src/passes/LocalCSE.cpp @@ -330,6 +330,40 @@ struct Scanner return false; } + // We will fully compute effects later, but consider shallow effects at this + // early time to ignore things that cannot be optimized later, because we + // use a greedy algorithm. Specifically, imagine we see this: + // + // (call + // (i32.add + // .. + // ) + // ) + // + // If we considered the call relevant then we'd start to look for that + // larger pattern that contains the add, but then when we find that it + // cannot be optimized later it is too late for the add. (Instead of + // checking effects here we could perhaps add backtracking, but that sounds + // more complex.) + // + // We use |hasNonTrapSideEffects| because if a trap occurs the optimization + // remains valid: both this and the copy of it would trap, which means the + // first traps and the second isn't reached anyhow. + // + // (We don't stash these effects because we may compute many of them here, + // and only need the few for those patterns that repeat.) + if (ShallowEffectAnalyzer(options, *getModule(), curr) + .hasNonTrapSideEffects()) { + return false; + } + + // We also cannot optimize away something that is intrinsically + // nondeterministic: even if it has no side effects, if it may return a + // different result each time, and then we cannot optimize away repeats. + if (Properties::isShallowlyGenerative(curr)) { + return false; + } + // If the size is at least 3, then if we have two of them we have 6, // and so adding one set+one get and removing one of the items itself // is not detrimental, and may be beneficial. @@ -438,16 +472,12 @@ struct Checker // none of them.) effects.trap = false; - // We also cannot optimize away something that is intrinsically - // nondeterministic: even if it has no side effects, if it may return a - // different result each time, then we cannot optimize away repeats. - if (effects.hasSideEffects() || - Properties::isGenerative(curr, getModule()->features)) { - requestInfos.erase(curr); - } else { - activeOriginals.emplace( - curr, ActiveOriginalInfo{info.requests, std::move(effects)}); - } + // Note that we've already checked above that this has no side effects or + // generativity: if we got here, then it is good to go from the + // perspective of this expression itself (but may be invalidated by other + // code in between, see above). + activeOriginals.emplace( + curr, ActiveOriginalInfo{info.requests, std::move(effects)}); } else if (info.original) { // The original may have already been invalidated. If so, remove our info // as well. diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index 3486fe82a..1a474be2c 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -2508,7 +2508,7 @@ private: // To be equal, they must also be known to return the same result // deterministically. - return !Properties::isGenerative(left, getModule()->features); + return !Properties::isGenerative(left); } // Similar to areConsecutiveInputsEqual() but also checks if we can remove diff --git a/test/lit/passes/local-cse.wast b/test/lit/passes/local-cse.wast index c38ca243a..8b0f51a7c 100644 --- a/test/lit/passes/local-cse.wast +++ b/test/lit/passes/local-cse.wast @@ -9,7 +9,9 @@ ;; CHECK: (type $1 (func (param i32) (result i32))) - ;; CHECK: (type $2 (func (result i64))) + ;; CHECK: (type $2 (func (param i32))) + + ;; CHECK: (type $3 (func (result i64))) ;; CHECK: (memory $0 100 100) @@ -315,6 +317,45 @@ (i32.const 10) ) + ;; CHECK: (func $in-calls (param $x i32) + ;; CHECK-NEXT: (local $1 i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (call $calls + ;; CHECK-NEXT: (local.tee $1 + ;; CHECK-NEXT: (i32.add + ;; CHECK-NEXT: (i32.const 10) + ;; CHECK-NEXT: (i32.const 20) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (call $calls + ;; CHECK-NEXT: (local.get $1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $in-calls (param $x i32) + ;; The side effects of calls prevent optimization, but expressions nested in + ;; calls can be optimized. + (drop + (call $calls + (i32.add + (i32.const 10) + (i32.const 20) + ) + ) + ) + (drop + (call $calls + (i32.add + (i32.const 10) + (i32.const 20) + ) + ) + ) + ) + ;; CHECK: (func $many-sets (result i64) ;; CHECK-NEXT: (local $temp i64) ;; CHECK-NEXT: (local $1 i64) |