From 1462c0dbfa9980481058e17d2aac317420e45acc Mon Sep 17 00:00:00 2001 From: "Alon Zakai (kripken)" Date: Sat, 20 May 2017 11:55:30 -0700 Subject: use TypeUpdater in vacuum --- src/passes/Vacuum.cpp | 63 +++++++++++++++++++++++++++------------------------ src/wasm-validator.h | 21 ++++++++++++----- 2 files changed, 48 insertions(+), 36 deletions(-) (limited to 'src') diff --git a/src/passes/Vacuum.cpp b/src/passes/Vacuum.cpp index 1f820ec9d..4e47ad9a3 100644 --- a/src/passes/Vacuum.cpp +++ b/src/passes/Vacuum.cpp @@ -23,6 +23,7 @@ #include #include #include +#include namespace wasm { @@ -31,7 +32,20 @@ struct Vacuum : public WalkerPass> { Pass* create() override { return new Vacuum; } - bool needRefinalize = false; + TypeUpdater typeUpdater; + + Expression* replaceCurrent(Expression* expression) { + auto* old = getCurrent(); + WalkerPass>::replaceCurrent(expression); + // also update the type updater + typeUpdater.noteReplacement(old, expression); + return expression; + } + + void doWalkFunction(Function* func) { + typeUpdater.walk(func->body); + walk(func->body); + } // returns nullptr if curr is dead, curr if it must stay as is, or another node if it can be replaced Expression* optimize(Expression* curr, bool resultUsed) { @@ -143,40 +157,39 @@ struct Vacuum : public WalkerPass> { int skip = 0; auto& list = curr->list; size_t size = list.size(); - bool needResize = false; for (size_t z = 0; z < size; z++) { - auto* optimized = optimize(list[z], z == size - 1 && isConcreteWasmType(curr->type)); + auto* child = list[z]; + auto* optimized = optimize(child, z == size - 1 && isConcreteWasmType(curr->type)); if (!optimized) { + typeUpdater.noteRecursiveRemoval(child); skip++; - needResize = true; } else { - if (optimized != list[z]) { + if (optimized != child) { + typeUpdater.noteReplacement(child, optimized); list[z] = optimized; } if (skip > 0) { list[z - skip] = list[z]; + list[z] = nullptr; } - // if this is an unconditional br, the rest is dead code - Break* br = list[z - skip]->dynCast(); - Switch* sw = list[z - skip]->dynCast(); - if ((br && !br->condition) || sw) { - auto* last = list.back(); - list.resize(z - skip + 1); - // if we removed the last one, and it was a return value, it must be returned - if (list.back() != last && isConcreteWasmType(last->type)) { - list.push_back(last); + // if this is unreachable, the rest is dead code + if (list[z - skip]->type == unreachable && z < size - 1) { + for (Index i = z - skip + 1; i < list.size(); i++) { + auto* remove = list[i]; + if (remove) { + typeUpdater.noteRecursiveRemoval(remove); + } } - needResize = false; - needRefinalize = true; + list.resize(z - skip + 1); + typeUpdater.maybeUpdateTypeToUnreachable(curr); + skip = 0; // nothing more to do on the list break; } } } - if (needResize) { + if (skip > 0) { list.resize(size - skip); - // resizing means we drop elements, which may include breaks, which may - // render blocks unreachable now - needRefinalize = true; + typeUpdater.maybeUpdateTypeToUnreachable(curr); } // the block may now be a trivial one that we can get rid of and just leave its contents replaceCurrent(BlockUtils::simplifyToContents(curr, this)); @@ -198,13 +211,6 @@ struct Vacuum : public WalkerPass> { } } replaceCurrent(child); - if (curr->type != child->type) { - // e.g., if (1) unreachable is none => unreachable - // or if i32 (1) unreachable else 10 is i32 => unreachable - // in which cases we must update our parents. - // we must do this now, so that our parents see valid data - ReFinalize().walk(getFunction()->body); - } return; } if (curr->ifFalse) { @@ -307,9 +313,6 @@ struct Vacuum : public WalkerPass> { } void visitFunction(Function* curr) { - if (needRefinalize) { - ReFinalize().walk(curr->body); - } auto* optimized = optimize(curr->body, curr->result != none); if (optimized) { curr->body = optimized; diff --git a/src/wasm-validator.h b/src/wasm-validator.h index 699e5910a..aa404099e 100644 --- a/src/wasm-validator.h +++ b/src/wasm-validator.h @@ -408,17 +408,26 @@ public: switch (curr->op) { case ClzInt32: case CtzInt32: - case PopcntInt32: + case PopcntInt32: { + shouldBeEqual(curr->value->type, i32, curr, "i32 unary value type must be correct"); + break; + } + case ClzInt64: + case CtzInt64: + case PopcntInt64: { + shouldBeEqual(curr->value->type, i64, curr, "i64 unary value type must be correct"); + break; + } case NegFloat32: case AbsFloat32: case CeilFloat32: case FloorFloat32: case TruncFloat32: case NearestFloat32: - case SqrtFloat32: - case ClzInt64: - case CtzInt64: - case PopcntInt64: + case SqrtFloat32: { + shouldBeEqual(curr->value->type, f32, curr, "f32 unary value type must be correct"); + break; + } case NegFloat64: case AbsFloat64: case CeilFloat64: @@ -426,7 +435,7 @@ public: case TruncFloat64: case NearestFloat64: case SqrtFloat64: { - shouldBeEqual(curr->value->type, curr->type, curr, "non-conversion unaries must return the same type"); + shouldBeEqual(curr->value->type, f64, curr, "f64 unary value type must be correct"); break; } case EqZInt32: { -- cgit v1.2.3 From 2f3bcb914b55f469426418fed1d85e00d0e4db1b Mon Sep 17 00:00:00 2001 From: "Alon Zakai (kripken)" Date: Sat, 20 May 2017 14:38:23 -0700 Subject: relooper improvements --- src/cfg/Relooper.cpp | 7 +++++- src/passes/ReReloop.cpp | 3 +++ test/example/c-api-kitchen-sink.c | 3 +++ test/passes/rereloop.txt | 47 +++++++++++++++++++++++++++++++++++---- test/passes/rereloop.wast | 21 +++++++++++++++++ 5 files changed, 76 insertions(+), 5 deletions(-) (limited to 'src') diff --git a/src/cfg/Relooper.cpp b/src/cfg/Relooper.cpp index 9fcc9c8be..b326d761d 100644 --- a/src/cfg/Relooper.cpp +++ b/src/cfg/Relooper.cpp @@ -328,7 +328,12 @@ wasm::Expression* Block::Render(RelooperBuilder& Builder, bool InLoop) { NextOuter->list.push_back(Outer); Outer->name = CurrName; // breaking on Outer leads to the content in NextOuter NextOuter->list.push_back(CurrContent); - NextOuter->list.push_back(Builder.makeBreak(SwitchLeave)); + // if this is not a dead end, also need to break to the outside + // this is both an optimization, and avoids incorrectness as adding + // a brak in unreachable code can make a place look reachable that isn't + if (CurrContent->type != wasm::unreachable) { + NextOuter->list.push_back(Builder.makeBreak(SwitchLeave)); + } // prepare for more nesting Outer = NextOuter; } else { diff --git a/src/passes/ReReloop.cpp b/src/passes/ReReloop.cpp index 6bdc0eb06..db2ec5698 100644 --- a/src/passes/ReReloop.cpp +++ b/src/passes/ReReloop.cpp @@ -28,6 +28,7 @@ #include "wasm-traversal.h" #include "pass.h" #include "cfg/Relooper.h" +#include "ast_utils.h" namespace wasm { @@ -314,6 +315,8 @@ struct ReReloop : public Pass { CFG::RelooperBuilder builder(*module, temp); function->body = relooper.Render(builder); } + // TODO: should this be in the relooper itself? + ReFinalize().walk(function->body); } }; diff --git a/test/example/c-api-kitchen-sink.c b/test/example/c-api-kitchen-sink.c index 5935e9993..b2218993c 100644 --- a/test/example/c-api-kitchen-sink.c +++ b/test/example/c-api-kitchen-sink.c @@ -427,6 +427,9 @@ void test_relooper() { RelooperRef relooper = RelooperCreate(); BinaryenExpressionRef temp = makeInt32(module, -99); RelooperBlockRef block0 = RelooperAddBlockWithSwitch(relooper, makeCallCheck(module, 0), temp); + // TODO: this example is not very good, the blocks should end in a |return| as otherwise they + // fall through to each other. A relooper block should end in something that stops control + // flow, if it doesn't have branches going out RelooperBlockRef block1 = RelooperAddBlock(relooper, makeCallCheck(module, 1)); RelooperBlockRef block2 = RelooperAddBlock(relooper, makeCallCheck(module, 2)); RelooperBlockRef block3 = RelooperAddBlock(relooper, makeCallCheck(module, 3)); diff --git a/test/passes/rereloop.txt b/test/passes/rereloop.txt index c15934c0b..17a084395 100644 --- a/test/passes/rereloop.txt +++ b/test/passes/rereloop.txt @@ -541,7 +541,6 @@ (block (br $block$3$break) ) - (br $switch$1$leave) ) (block (block @@ -552,7 +551,6 @@ ) ) ) - (br $switch$1$leave) ) ) (block @@ -572,7 +570,6 @@ (block (br $block$6$break) ) - (br $switch$3$leave) ) (block (block @@ -586,7 +583,6 @@ ) ) ) - (br $switch$3$leave) ) ) (block @@ -704,4 +700,47 @@ ) ) ) + (func $switcher-to-nowhere (type $2) (param $0 i32) (result i32) + (local $1 i32) + (block + ) + (block $switch$1$leave + (block $switch$1$default + (block $switch$1$case$3 + (block $switch$1$case$4 + (br_table $switch$1$case$4 $switch$1$case$3 $switch$1$default + (get_local $0) + ) + ) + (block + (block + (block + (return + (i32.const 1) + ) + ) + ) + ) + ) + (block + (block + (block + (return + (i32.const 2) + ) + ) + ) + ) + ) + (block + (block + (block + (return + (i32.const 3) + ) + ) + ) + ) + ) + ) ) diff --git a/test/passes/rereloop.wast b/test/passes/rereloop.wast index 38c74ff56..0680c97fe 100644 --- a/test/passes/rereloop.wast +++ b/test/passes/rereloop.wast @@ -175,5 +175,26 @@ (i32.const 3) ) ) + + (func $switcher-to-nowhere (param $0 i32) (result i32) + (block $switch + (block $switch-case0 + (block $switch-case + (br_table $switch-case $switch-case0 $switch + (get_local $0) + ) + ) + (return + (i32.const 1) + ) + ) + (return + (i32.const 2) + ) + ) + (return + (i32.const 3) + ) + ) ) -- cgit v1.2.3 From 026accbe55dde6b9d769292195c3ad1ac0a3b8b0 Mon Sep 17 00:00:00 2001 From: "Alon Zakai (kripken)" Date: Sat, 20 May 2017 21:13:52 -0700 Subject: add --fuzz-exec option to wasm-opt, which (when possible) executes results before and after optimizations are run, checking for changes. this can be used when fuzzing --- src/tools/wasm-opt.cpp | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 73 insertions(+) (limited to 'src') diff --git a/src/tools/wasm-opt.cpp b/src/tools/wasm-opt.cpp index bf79cb31d..468f3ce93 100644 --- a/src/tools/wasm-opt.cpp +++ b/src/tools/wasm-opt.cpp @@ -28,9 +28,64 @@ #include "wasm-s-parser.h" #include "wasm-validator.h" #include "wasm-io.h" +#include "wasm-interpreter.h" +#include "shell-interface.h" using namespace wasm; +// gets execution results from a wasm module. this is useful for fuzzing +// +// we can only get results when there are no imports. we then call each method +// that has a result, with some values +struct ExecutionResults { + std::map results; + + void get(Module& wasm) { + if (wasm.imports.size() > 0) { + std::cout << "[fuzz-exec] imports, so quitting\n"; + return; + } + for (auto& func : wasm.functions) { + if (func->result != none) { + // this is good + results[func->name] = run(func.get(), wasm); + } + } + std::cout << "[fuzz-exec] " << results.size() << " results noted\n"; + } + + bool operator==(ExecutionResults& other) { + for (auto& iter : results) { + auto name = iter.first; + if (other.results.find(name) != other.results.end()) { + if (results[name] != other.results[name]) { + return false; + } + } + } + return true; + } + + bool operator!=(ExecutionResults& other) { + return !((*this) == other); + } + + Literal run(Function* func, Module& wasm) { + ShellExternalInterface interface; + ModuleInstance instance(wasm, &interface); + LiteralList arguments; + for (WasmType param : func->params) { + // zeros in arguments TODO: more? + arguments.push_back(Literal(param)); + } + try { + return instance.callFunctionInternal(func->name, arguments); + } catch (const TrapException&) { + return Literal(); + } + } +}; + // // main // @@ -42,6 +97,7 @@ int main(int argc, const char* argv[]) { PassOptions passOptions; bool emitBinary = true; bool debugInfo = false; + bool fuzzExec = false; Options options("wasm-opt", "Optimize .wast files"); options @@ -58,6 +114,9 @@ int main(int argc, const char* argv[]) { .add("--debuginfo", "-g", "Emit names section and debug info", Options::Arguments::Zero, [&](Options *o, const std::string &arguments) { debugInfo = true; }) + .add("--fuzz-exec", "-fe", "Execute functions before and after optimization, helping fuzzing find bugs", + Options::Arguments::Zero, + [&](Options *o, const std::string &arguments) { fuzzExec = true; }) .add_positional("INFILE", Options::Arguments::One, [](Options* o, const std::string& argument) { o->extra["infile"] = argument; @@ -99,6 +158,11 @@ int main(int argc, const char* argv[]) { Fatal() << "error in validating input"; } + ExecutionResults results; + if (fuzzExec) { + results.get(wasm); + } + if (passes.size() > 0) { if (options.debug) std::cerr << "running passes...\n"; PassRunner passRunner(&wasm, passOptions); @@ -114,6 +178,15 @@ int main(int argc, const char* argv[]) { assert(WasmValidator().validate(wasm)); } + if (fuzzExec) { + ExecutionResults optimizedResults; + optimizedResults.get(wasm); + if (optimizedResults != results) { + Fatal() << "[fuzz-exec] optimization passes changed execution results"; + } + std::cout << "[fuzz-exec] results match\n"; + } + if (options.extra.count("output") > 0) { if (options.debug) std::cerr << "writing..." << std::endl; ModuleWriter writer; -- cgit v1.2.3