From eee81f13cf8e7652cd9733d03de57bd9e9e7def7 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Wed, 6 Apr 2016 13:20:15 -0700 Subject: refactor wasm traversal code into separate file --- src/ast_utils.h | 1 + 1 file changed, 1 insertion(+) (limited to 'src/ast_utils.h') diff --git a/src/ast_utils.h b/src/ast_utils.h index df2ffe578..44a4bcc21 100644 --- a/src/ast_utils.h +++ b/src/ast_utils.h @@ -18,6 +18,7 @@ #define wasm_ast_utils_h #include "wasm.h" +#include "wasm-traversal.h" namespace wasm { -- cgit v1.2.3 From 53f4c97487e90baa226614e63867add700ed12e5 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Wed, 6 Apr 2016 20:51:08 -0700 Subject: EffectsAnalyzer --- src/ast_utils.h | 42 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+) (limited to 'src/ast_utils.h') diff --git a/src/ast_utils.h b/src/ast_utils.h index 44a4bcc21..598081342 100644 --- a/src/ast_utils.h +++ b/src/ast_utils.h @@ -39,6 +39,48 @@ struct BreakSeeker : public WasmWalker { } }; +// Look for side effects, including control flow +// TODO: look at individual locals + +struct EffectAnalyzer : public WasmWalker { + bool branches = false; + bool calls = false; + bool readsLocal = false; + bool writesLocal = false; + bool readsMemory = false; + bool writesMemory = false; + + bool accessesLocal() { return readsLocal || writesLocal; } + bool accessesMemory() { return calls || readsMemory || writesMemory; } + bool hasSideEffects() { return calls || writesLocal || writesMemory; } + + // checks if these effects would invalidate another set (e.g., if we write, we invalidate someone that reads, they can't be moved past us) + bool invalidates(EffectAnalyzer& other) { + return branches || ((writesMemory || calls) && other.accessesMemory()) || (writesLocal && other.accessesLocal()); + } + + void visitIf(If *curr) { branches = true; } + void visitBreak(Break *curr) { branches = true; } + void visitSwitch(Switch *curr) { branches = true; } + void visitCall(Call *curr) { calls = true; } + void visitCallImport(CallImport *curr) { calls = true; } + void visitCallIndirect(CallIndirect *curr) { calls = true; } + void visitGetLocal(GetLocal *curr) { readsLocal = true; } + void visitSetLocal(SetLocal *curr) { writesLocal = true; } + void visitLoad(Load *curr) { readsMemory = true; } + void visitStore(Store *curr) { writesMemory = true; } + void visitReturn(Return *curr) { branches = true; } + void visitHost(Host *curr) { calls = true; } + void visitUnreachable(Unreachable *curr) { branches = true; } +}; + +struct ExpressionManipulator { + // Nop is the smallest node, so we can always nop-ify another node in our arena + static void nop(Expression* target) { + *static_cast(target) = Nop(); + } +}; + } // namespace wasm #endif // wasm_ast_utils_h -- cgit v1.2.3 From 6279be0fb7013db1bc89755f9bc8db4befef2ddf Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Thu, 7 Apr 2016 12:03:11 -0700 Subject: fix effect invalidation logic --- src/ast_utils.h | 4 +++- test/passes/simplify-locals.txt | 42 ++++++++++++++++++++--------------------- 2 files changed, 24 insertions(+), 22 deletions(-) (limited to 'src/ast_utils.h') diff --git a/src/ast_utils.h b/src/ast_utils.h index 598081342..190b2876e 100644 --- a/src/ast_utils.h +++ b/src/ast_utils.h @@ -56,7 +56,9 @@ struct EffectAnalyzer : public WasmWalker { // checks if these effects would invalidate another set (e.g., if we write, we invalidate someone that reads, they can't be moved past us) bool invalidates(EffectAnalyzer& other) { - return branches || ((writesMemory || calls) && other.accessesMemory()) || (writesLocal && other.accessesLocal()); + return branches || other.branches + || ((writesMemory || calls) && other.accessesMemory()) || (writesLocal && other.accessesLocal()) + || (accessesMemory() && (other.writesMemory || other.calls)) || (accessesLocal() && other.writesLocal); } void visitIf(If *curr) { branches = true; } diff --git a/test/passes/simplify-locals.txt b/test/passes/simplify-locals.txt index 59e400dd7..477d95250 100644 --- a/test/passes/simplify-locals.txt +++ b/test/passes/simplify-locals.txt @@ -50,11 +50,11 @@ (set_local $a (i32.const 1) ) - (nop) - (get_local $a) (set_local $b (i32.const 2) ) + (get_local $a) + (get_local $b) (set_local $a (i32.const 3) ) @@ -78,12 +78,12 @@ (set_local $a (i32.const 9) ) - (nop) - (call_import $waka) - (get_local $a) (set_local $b (i32.const 10) ) + (call_import $waka) + (get_local $a) + (get_local $b) (set_local $a (i32.const 11) ) @@ -93,14 +93,14 @@ (set_local $a (i32.const 13) ) - (nop) + (set_local $b + (i32.const 14) + ) (i32.load (i32.const 24) ) (get_local $a) - (set_local $b - (i32.const 14) - ) + (get_local $b) (set_local $a (i32.const 15) ) @@ -110,15 +110,15 @@ (set_local $a (i32.const 17) ) - (nop) + (set_local $b + (i32.const 18) + ) (i32.store (i32.const 48) (i32.const 96) ) (get_local $a) - (set_local $b - (i32.const 18) - ) + (get_local $b) ) (block $block3 (nop) @@ -132,13 +132,13 @@ (call_import $waka) (get_local $a) (call_import $waka) - (nop) - (i32.load - (i32.const 1) - ) (set_local $a (call_import $waka_int) ) + (i32.load + (i32.const 1) + ) + (get_local $a) (call_import $waka) (set_local $a (call_import $waka_int) @@ -202,16 +202,16 @@ (call_import $waka) (get_local $a) (call_import $waka) - (nop) - (i32.load - (i32.const 1) - ) (set_local $a (i32.store (i32.const 108) (i32.const 109) ) ) + (i32.load + (i32.const 1) + ) + (get_local $a) (call_import $waka) (set_local $a (i32.store -- cgit v1.2.3 From 0a03aacd4ea32476714066eebe0cded77c87ca66 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Thu, 7 Apr 2016 19:09:05 -0700 Subject: blocks must mark as branching in effects analyzer, as control flow can join there if the end of the block was branched to --- src/ast_utils.h | 1 + test/emcc_hello_world.fromasm | 19 ++++++++++--------- test/emcc_hello_world.fromasm.imprecise | 19 ++++++++++--------- test/passes/simplify-locals.txt | 14 ++++++++++++++ test/passes/simplify-locals.wast | 10 ++++++++++ 5 files changed, 45 insertions(+), 18 deletions(-) (limited to 'src/ast_utils.h') diff --git a/src/ast_utils.h b/src/ast_utils.h index 190b2876e..bf42d10e1 100644 --- a/src/ast_utils.h +++ b/src/ast_utils.h @@ -61,6 +61,7 @@ struct EffectAnalyzer : public WasmWalker { || (accessesMemory() && (other.writesMemory || other.calls)) || (accessesLocal() && other.writesLocal); } + void visitBlock(Block *curr) { branches = true; } void visitIf(If *curr) { branches = true; } void visitBreak(Break *curr) { branches = true; } void visitSwitch(Switch *curr) { branches = true; } diff --git a/test/emcc_hello_world.fromasm b/test/emcc_hello_world.fromasm index 6c877aa3b..be7a45cec 100644 --- a/test/emcc_hello_world.fromasm +++ b/test/emcc_hello_world.fromasm @@ -299,9 +299,9 @@ ) ) (func $_frexp (param $$x f64) (param $$e i32) (result f64) + (local $$retval$0 f64) (local $$x$addr$0 f64) (local $$storemerge i32) - (local $$retval$0 f64) (local $$1 i32) (local $$0 i32) (local $$sub8 i32) @@ -463,19 +463,20 @@ ) (get_local $$6) ) - ) - ) - (return - (set_local $$retval$0 - (set_local $$7 - (f64.load - (i32.load - (i32.const 24) + (set_local $$retval$0 + (set_local $$7 + (f64.load + (i32.load + (i32.const 24) + ) ) ) ) ) ) + (return + (get_local $$retval$0) + ) ) (func $_frexpl (param $$x f64) (param $$e i32) (result f64) (local $sp i32) diff --git a/test/emcc_hello_world.fromasm.imprecise b/test/emcc_hello_world.fromasm.imprecise index 343ab13a6..fc4418930 100644 --- a/test/emcc_hello_world.fromasm.imprecise +++ b/test/emcc_hello_world.fromasm.imprecise @@ -297,9 +297,9 @@ ) ) (func $_frexp (param $$x f64) (param $$e i32) (result f64) + (local $$retval$0 f64) (local $$x$addr$0 f64) (local $$storemerge i32) - (local $$retval$0 f64) (local $$1 i32) (local $$0 i32) (local $$sub8 i32) @@ -461,19 +461,20 @@ ) (get_local $$6) ) - ) - ) - (return - (set_local $$retval$0 - (set_local $$7 - (f64.load - (i32.load - (i32.const 24) + (set_local $$retval$0 + (set_local $$7 + (f64.load + (i32.load + (i32.const 24) + ) ) ) ) ) ) + (return + (get_local $$retval$0) + ) ) (func $_frexpl (param $$x f64) (param $$e i32) (result f64) (local $sp i32) diff --git a/test/passes/simplify-locals.txt b/test/passes/simplify-locals.txt index 477d95250..88c00dbe9 100644 --- a/test/passes/simplify-locals.txt +++ b/test/passes/simplify-locals.txt @@ -226,5 +226,19 @@ (get_local $a) (call_import $waka) ) + (block $out-of-block + (set_local $a + (i32.const 1337) + ) + (block $b + (block $c + (br $b) + ) + (set_local $a + (i32.const 9876) + ) + ) + (get_local $a) + ) ) ) diff --git a/test/passes/simplify-locals.wast b/test/passes/simplify-locals.wast index 6f33db4e2..5b1db2d12 100644 --- a/test/passes/simplify-locals.wast +++ b/test/passes/simplify-locals.wast @@ -126,6 +126,16 @@ (get_local $a) ;; no (call_import $waka) ) + (block $out-of-block + (set_local $a (i32.const 1337)) + (block $b + (block $c + (br $b) + ) + (set_local $a (i32.const 9876)) + ) + (get_local $a) + ) ) ) -- cgit v1.2.3 From e444aefddd6e491e193e5eb53beae0c3f9252422 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Thu, 7 Apr 2016 19:16:37 -0700 Subject: handle loops in effect analyzer --- src/ast_utils.h | 17 +++++++++++++++++ src/passes/SimplifyLocals.cpp | 27 +++++++++++++++++++-------- test/passes/simplify-locals.txt | 12 ++++++++++++ test/passes/simplify-locals.wast | 8 ++++++++ 4 files changed, 56 insertions(+), 8 deletions(-) (limited to 'src/ast_utils.h') diff --git a/src/ast_utils.h b/src/ast_utils.h index bf42d10e1..5ab427178 100644 --- a/src/ast_utils.h +++ b/src/ast_utils.h @@ -53,6 +53,7 @@ struct EffectAnalyzer : public WasmWalker { bool accessesLocal() { return readsLocal || writesLocal; } bool accessesMemory() { return calls || readsMemory || writesMemory; } bool hasSideEffects() { return calls || writesLocal || writesMemory; } + bool hasAnything() { return branches || calls || readsLocal || writesLocal || readsMemory || writesMemory; } // checks if these effects would invalidate another set (e.g., if we write, we invalidate someone that reads, they can't be moved past us) bool invalidates(EffectAnalyzer& other) { @@ -61,7 +62,23 @@ struct EffectAnalyzer : public WasmWalker { || (accessesMemory() && (other.writesMemory || other.calls)) || (accessesLocal() && other.writesLocal); } + // the checks above happen after the node's children were processed, in the order of execution + // we must also check for control flow that happens before the children, i.e., loops + bool checkPre(Expression* curr) { + if (curr->is()) { + branches = true; + return true; + } + return false; + } + + bool checkPost(Expression* curr) { + visit(curr); + return hasAnything(); + } + void visitBlock(Block *curr) { branches = true; } + void visitLoop(Loop *curr) { branches = true; } void visitIf(If *curr) { branches = true; } void visitBreak(Break *curr) { branches = true; } void visitSwitch(Switch *curr) { branches = true; } diff --git a/src/passes/SimplifyLocals.cpp b/src/passes/SimplifyLocals.cpp index a0f843bbd..cd6cb2ca7 100644 --- a/src/passes/SimplifyLocals.cpp +++ b/src/passes/SimplifyLocals.cpp @@ -78,14 +78,7 @@ struct SimplifyLocals : public WalkerPass> { } } - void walk(Expression*& curr) override { - if (!curr) return; - - FastExecutionWalker::walk(curr); - - // invalidations TODO: this is O(n^2) in sinkables - EffectAnalyzer effects; - effects.visit(curr); + void checkInvalidations(EffectAnalyzer& effects) { std::vector invalidated; for (auto& sinkable : sinkables) { if (effects.invalidates(sinkable.second.effects)) { @@ -96,6 +89,24 @@ struct SimplifyLocals : public WalkerPass> { sinkables.erase(name); } } + + void walk(Expression*& curr) override { + if (!curr) return; + + EffectAnalyzer effects; + + if (effects.checkPre(curr)) { + checkInvalidations(effects); + } + + FastExecutionWalker::walk(curr); + + // TODO: this is O(n^2) in sinkables + + if (effects.checkPost(curr)) { + checkInvalidations(effects); + } + } }; static RegisterPass registerPass("simplify-locals", "miscellaneous locals-related optimizations"); diff --git a/test/passes/simplify-locals.txt b/test/passes/simplify-locals.txt index 88c00dbe9..880639f79 100644 --- a/test/passes/simplify-locals.txt +++ b/test/passes/simplify-locals.txt @@ -240,5 +240,17 @@ ) (get_local $a) ) + (block $loopey + (set_local $a + (i32.const 1337) + ) + (loop $loop-out4 $loop-in5 + (get_local $a) + (set_local $a + (i32.const 9876) + ) + ) + (get_local $a) + ) ) ) diff --git a/test/passes/simplify-locals.wast b/test/passes/simplify-locals.wast index 5b1db2d12..db17c5533 100644 --- a/test/passes/simplify-locals.wast +++ b/test/passes/simplify-locals.wast @@ -136,6 +136,14 @@ ) (get_local $a) ) + (block $loopey + (set_local $a (i32.const 1337)) + (loop + (get_local $a) + (set_local $a (i32.const 9876)) + ) + (get_local $a) + ) ) ) -- cgit v1.2.3