diff options
22 files changed, 430 insertions, 49 deletions
diff --git a/src/tools/wasm-ctor-eval.cpp b/src/tools/wasm-ctor-eval.cpp index ef66aed35..d2364dcc7 100644 --- a/src/tools/wasm-ctor-eval.cpp +++ b/src/tools/wasm-ctor-eval.cpp @@ -29,7 +29,7 @@ #include "ir/import-utils.h" #include "ir/literal-utils.h" #include "ir/memory-utils.h" -#include "ir/module-utils.h" +#include "ir/names.h" #include "pass.h" #include "support/colors.h" #include "support/file.h" @@ -41,11 +41,17 @@ using namespace wasm; +namespace { + struct FailToEvalException { std::string why; FailToEvalException(std::string why) : why(why) {} }; +// The prefix for a recommendation, so it is aligned properly with the rest of +// the output. +#define RECOMMENDATION "\n recommendation: " + // We do not have access to imported globals class EvallingGlobalManager { // values of globals @@ -66,8 +72,9 @@ public: if (dangerousGlobals.count(name) > 0) { std::string extra; if (name == "___dso_handle") { - extra = "\nrecommendation: build with -s NO_EXIT_RUNTIME=1 so that " - "calls to atexit that use ___dso_handle are not emitted"; + extra = RECOMMENDATION + "build with -s NO_EXIT_RUNTIME=1 so that " + "calls to atexit that use ___dso_handle are not emitted"; } throw FailToEvalException( std::string( @@ -302,10 +309,10 @@ struct CtorEvalExternalInterface : EvallingModuleInstance::ExternalInterface { std::string extra; if (import->module == ENV && import->base == "___cxa_atexit") { - extra = "\nrecommendation: build with -s NO_EXIT_RUNTIME=1 so that calls " - "to atexit are not emitted"; + extra = RECOMMENDATION "build with -s NO_EXIT_RUNTIME=1 so that calls " + "to atexit are not emitted"; } else if (import->module == WASI && !ignoreExternalInput) { - extra = "\nrecommendation: consider --ignore-external-input"; + extra = RECOMMENDATION "consider --ignore-external-input"; } throw FailToEvalException(std::string("call import: ") + import->module.str + "." + import->base.str + @@ -475,6 +482,163 @@ private: } }; +// Eval a single ctor function. Returns whether we succeeded to completely +// evaluate the ctor, which means that the caller can proceed to try to eval +// further ctors if there are any. +bool evalCtor(EvallingModuleInstance& instance, + CtorEvalExternalInterface& interface, + Name funcName, + Name exportName) { + auto& wasm = instance.wasm; + auto* func = wasm.getFunction(funcName); + + // We don't know the values of parameters, so give up if there are any. + // TODO: Maybe use ignoreExternalInput? + if (func->getNumParams() > 0) { + std::cout << " ...stopping due to params\n"; + return false; + } + + // TODO: Handle a return value by emitting a proper constant. + if (func->getResults() != Type::none) { + std::cout << " ...stopping due to results\n"; + return false; + } + + // We want to handle the form of the global constructor function in LLVM. That + // looks like this: + // + // (func $__wasm_call_ctors + // (call $ctor.1) + // (call $ctor.2) + // (call $ctor.3) + // ) + // + // Some of those ctors may be inlined, however, which would mean that the + // function could have locals, control flow, etc. However, we assume for now + // that it does not have parameters at least (whose values we can't tell), + // or results. And for now we look for a toplevel block and process its + // children one at a time. This allows us to eval some of the $ctor.* + // functions (or their inlined contents) even if not all. + // + // TODO: Support complete partial evalling, that is, evaluate parts of an + // arbitrary function, and not just a sequence in a single toplevel + // block. + + if (auto* block = func->body->dynCast<Block>()) { + // Go through the items in the block and try to execute them. We do all this + // in a single function scope for all the executions. + EvallingModuleInstance::FunctionScope scope(func, LiteralList()); + + EvallingModuleInstance::RuntimeExpressionRunner expressionRunner( + instance, scope, instance.maxDepth); + + // After we successfully eval a line we will apply the changes here. This is + // the same idea as applyToModule() - we must only do it after an entire + // atomic "chunk" has been processed, we do not want partial updates from + // an item in the block that we only partially evalled. + EvallingModuleInstance::FunctionScope appliedScope(func, LiteralList()); + + Index successes = 0; + for (auto* curr : block->list) { + Flow flow; + try { + flow = expressionRunner.visit(curr); + } catch (FailToEvalException& fail) { + if (successes == 0) { + std::cout << " ...stopping (in block) since could not eval: " + << fail.why << "\n"; + } else { + std::cout << " ...partial evalling successful, but stopping since " + "could not eval: " + << fail.why << "\n"; + } + break; + } + + // So far so good! Apply the results. + interface.applyToModule(); + appliedScope = scope; + successes++; + + if (flow.breaking()) { + // We are returning out of the function (either via a return, or via a + // break to |block|, which has the same outcome. That means we don't + // need to execute any more lines, and can consider them to be executed. + std::cout << " ...stopping in block due to break\n"; + + // Mark us as having succeeded on the entire block, since we have: we + // are skipping the rest, which means there is no problem there. We must + // set this here so that lower down we realize that we've evalled + // everything. + successes = block->list.size(); + break; + } + } + + if (successes > 0 && successes < block->list.size()) { + // We managed to eval some but not all. That means we can't just remove + // the entire function, but need to keep parts of it - the parts we have + // not evalled - around. To do so, we create a copy of the function with + // the partially-evalled contents and make the export use that (as the + // function may be used in other places than the export, which we do not + // want to affect). + auto copyName = Names::getValidFunctionName(wasm, funcName); + auto* copyFunc = ModuleUtils::copyFunction(func, wasm, copyName); + wasm.getExport(exportName)->value = copyName; + + // Remove the items we've evalled. + Builder builder(wasm); + auto* copyBlock = copyFunc->body->cast<Block>(); + for (Index i = 0; i < successes; i++) { + copyBlock->list[i] = builder.makeNop(); + } + + // Write out the values of locals, that is the local state after evalling + // the things we've just nopped. For simplicity we just write out all of + // locals, and leave it to the optimizer to remove redundant or + // unnecessary operations. + std::vector<Expression*> localSets; + for (Index i = 0; i < copyFunc->getNumLocals(); i++) { + auto value = appliedScope.locals[i]; + localSets.push_back( + builder.makeLocalSet(i, builder.makeConstantExpression(value))); + } + + // Put the local sets at the front of the block. We know there must be a + // nop in that position (since we've evalled at least one item in the + // block, and replaced it with a nop), so we can overwrite it. + copyBlock->list[0] = builder.makeBlock(localSets); + + // Interesting optimizations may be possible both due to removing some but + // not all of the code, and due to the locals we just added. + PassRunner passRunner(&wasm, + PassOptions::getWithDefaultOptimizationOptions()); + passRunner.addDefaultFunctionOptimizationPasses(); + passRunner.runOnFunction(copyFunc); + } + + // Return true if we evalled the entire block. Otherwise, even if we evalled + // some of it, the caller must stop trying to eval further things. + return successes == block->list.size(); + } + + // Otherwise, we don't recognize a pattern that allows us to do partial + // evalling. So simply call the entire function at once and see if we can + // optimize that. + try { + instance.callFunction(funcName, LiteralList()); + } catch (FailToEvalException& fail) { + std::cout << " ...stopping since could not eval: " << fail.why << "\n"; + return false; + } + + // Success! Apply the results. + interface.applyToModule(); + return true; +} + +// Eval all ctors in a module. void evalCtors(Module& wasm, std::vector<std::string> ctors) { std::map<Name, std::shared_ptr<EvallingModuleInstance>> linkedInstances; @@ -505,26 +669,15 @@ void evalCtors(Module& wasm, std::vector<std::string> ctors) { if (!ex) { Fatal() << "export not found: " << ctor; } - try { - instance.callFunction(ex->value, LiteralList()); - } catch (FailToEvalException& fail) { - // that's it, we failed, so stop here, cleaning up partial - // memory changes first - std::cout << " ...stopping since could not eval: " << fail.why << "\n"; + auto funcName = ex->value; + if (!evalCtor(instance, interface, funcName, ctor)) { + std::cout << " ...stopping\n"; return; } - std::cout << " ...success on " << ctor << ".\n"; - // Success, the entire function was evalled! Apply the results of - // execution to the module. - interface.applyToModule(); - - // we can nop the function (which may be used elsewhere) - // and remove the export - auto* exp = wasm.getExport(ctor); - auto* func = wasm.getFunction(exp->value); - func->body = wasm.allocator.alloc<Nop>(); - wasm.removeExport(exp->name); + // Success! Remove the export, and continue. + std::cout << " ...success on " << ctor << ".\n"; + wasm.removeExport(ctor); } } catch (FailToEvalException& fail) { // that's it, we failed to even create the instance @@ -534,6 +687,8 @@ void evalCtors(Module& wasm, std::vector<std::string> ctors) { } } +} // anonymous namespace + // // main // @@ -629,6 +784,7 @@ int main(int argc, const char* argv[]) { { PassRunner passRunner(&wasm); passRunner.add("memory-packing"); // we flattened it, so re-optimize + // TODO: just do -Os for the one function passRunner.add("remove-unused-names"); passRunner.add("dce"); passRunner.add("merge-blocks"); diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h index 600310c9c..02710d4b3 100644 --- a/src/wasm-interpreter.h +++ b/src/wasm-interpreter.h @@ -2551,7 +2551,7 @@ public: private: // Keep a record of call depth, to guard against excessive recursion. - size_t callDepth; + size_t callDepth = 0; // Function name stack. We maintain this explicitly to allow printing of // stack traces. @@ -2653,6 +2653,7 @@ private: } } +public: class FunctionScope { public: std::vector<Literals> locals; @@ -3553,7 +3554,6 @@ private: } }; -public: // Call a function, starting an invocation. Literals callFunction(Name name, const LiteralList& arguments) { // if the last call ended in a jump up the stack, it might have left stuff @@ -3609,9 +3609,11 @@ public: return flow.values; } + // The maximum call stack depth to evaluate into. + static const Index maxDepth = 250; + protected: Address memorySize; // in pages - static const Index maxDepth = 250; void trapIfGt(uint64_t lhs, uint64_t rhs, const char* msg) { if (lhs > rhs) { diff --git a/test/ctor-eval/no_partial.wast b/test/ctor-eval/no_partial.wast deleted file mode 100644 index 18ef177b7..000000000 --- a/test/ctor-eval/no_partial.wast +++ /dev/null @@ -1,10 +0,0 @@ -(module - (memory 256 256) - (data (i32.const 10) "waka waka waka waka waka") - (export "test1" $test1) - (func $test1 - (i32.store8 (i32.const 12) (i32.const 115)) ;; a safe store, should alter memory - (unreachable) - (i32.store8 (i32.const 13) (i32.const 114)) ;; a safe store, should alter memory, but we trapped already, and so must roll back the first one too - ) -) diff --git a/test/ctor-eval/no_partial.wast.out b/test/ctor-eval/no_partial.wast.out deleted file mode 100644 index 0e941f3ac..000000000 --- a/test/ctor-eval/no_partial.wast.out +++ /dev/null @@ -1,13 +0,0 @@ -(module - (type $none_=>_none (func)) - (memory $0 256 256) - (data (i32.const 10) "waka waka waka waka waka") - (export "test1" (func $test1)) - (func $test1 - (i32.store8 - (i32.const 12) - (i32.const 115) - ) - (unreachable) - ) -) diff --git a/test/ctor-eval/params.wast b/test/ctor-eval/params.wast new file mode 100644 index 000000000..fb70debe5 --- /dev/null +++ b/test/ctor-eval/params.wast @@ -0,0 +1,7 @@ +(module + (func "test1" (param $x i32) + ;; The presence of params stops us from evalling this function (at least + ;; for now). + (nop) + ) +) diff --git a/test/ctor-eval/no_partial.wast.ctors b/test/ctor-eval/params.wast.ctors index a5bce3fd2..a5bce3fd2 100644 --- a/test/ctor-eval/no_partial.wast.ctors +++ b/test/ctor-eval/params.wast.ctors diff --git a/test/ctor-eval/params.wast.out b/test/ctor-eval/params.wast.out new file mode 100644 index 000000000..6e52bea89 --- /dev/null +++ b/test/ctor-eval/params.wast.out @@ -0,0 +1,7 @@ +(module + (type $i32_=>_none (func (param i32))) + (export "test1" (func $0)) + (func $0 (param $x i32) + (nop) + ) +) diff --git a/test/ctor-eval/partial-locals-tee.wast b/test/ctor-eval/partial-locals-tee.wast new file mode 100644 index 000000000..37dac176a --- /dev/null +++ b/test/ctor-eval/partial-locals-tee.wast @@ -0,0 +1,38 @@ +(module + (import "import" "import" (func $import (param i32 i32))) + + (memory 256 256) + (data (i32.const 10) "_________________") + + (export "test1" $test1) + + (func $test1 + (local $temp i32) + + ;; Increment $temp from 0 to 1, which we can eval. + (local.set $temp + (i32.add + (local.get $temp) + (i32.const 1) + ) + ) + + ;; A safe store that will be evalled and alter memory. + (i32.store8 (i32.const 12) (i32.const 115)) + + ;; A call to an import, which prevents evalling. We will stop here. The + ;; 'tee' instruction should *not* have any effect, that is, we should not + ;; partially eval this line in the block - we should eval none of it. + ;; TODO: We should support such partial line evalling, with more careful + ;; management of locals. + (call $import + (local.get $temp) ;; The value sent here should be '1'. + (local.tee $temp + (i32.const 50) + ) + ) + + ;; A safe store that we never reach + (i32.store8 (i32.const 13) (i32.const 115)) + ) +) diff --git a/test/ctor-eval/partial-locals-tee.wast.ctors b/test/ctor-eval/partial-locals-tee.wast.ctors new file mode 100644 index 000000000..a5bce3fd2 --- /dev/null +++ b/test/ctor-eval/partial-locals-tee.wast.ctors @@ -0,0 +1 @@ +test1 diff --git a/test/ctor-eval/partial-locals-tee.wast.out b/test/ctor-eval/partial-locals-tee.wast.out new file mode 100644 index 000000000..cb2653198 --- /dev/null +++ b/test/ctor-eval/partial-locals-tee.wast.out @@ -0,0 +1,18 @@ +(module + (type $i32_i32_=>_none (func (param i32 i32))) + (type $none_=>_none (func)) + (import "import" "import" (func $import (param i32 i32))) + (memory $0 256 256) + (data (i32.const 10) "__s______________") + (export "test1" (func $test1_0)) + (func $test1_0 + (call $import + (i32.const 1) + (i32.const 50) + ) + (i32.store8 + (i32.const 13) + (i32.const 115) + ) + ) +) diff --git a/test/ctor-eval/partial-locals.wast b/test/ctor-eval/partial-locals.wast new file mode 100644 index 000000000..b0304c2ea --- /dev/null +++ b/test/ctor-eval/partial-locals.wast @@ -0,0 +1,43 @@ +(module + (import "import" "import" (func $import)) + + (memory 256 256) + (data (i32.const 10) "_________________") + + (export "test1" $test1) + + (global $sp (mut i32) (i32.const 100)) + + (func $test1 + (local $temp-sp i32) + + ;; Save and bump the stack pointer. + (local.set $temp-sp + (global.get $sp) + ) + (global.set $sp + (i32.add + (global.get $sp) + (i32.const 4) + ) + ) + + ;; A safe store, should alter memory + (i32.store8 (i32.const 12) (i32.const 115)) + + ;; A call to an import, which prevents evalling. We will stop here. After + ;; optimization we'll serialize the value of $temp-sp so that when the + ;; code is run later it runs properly. + ;; + ;; (Also, the global $sp will contain 104, the value after the bump.) + (call $import) + + ;; A safe store that we never reach + (i32.store8 (i32.const 13) (i32.const 115)) + + ;; Restore the stack pointer. + (global.set $sp + (local.get $temp-sp) + ) + ) +) diff --git a/test/ctor-eval/partial-locals.wast.ctors b/test/ctor-eval/partial-locals.wast.ctors new file mode 100644 index 000000000..a5bce3fd2 --- /dev/null +++ b/test/ctor-eval/partial-locals.wast.ctors @@ -0,0 +1 @@ +test1 diff --git a/test/ctor-eval/partial-locals.wast.out b/test/ctor-eval/partial-locals.wast.out new file mode 100644 index 000000000..14f102b69 --- /dev/null +++ b/test/ctor-eval/partial-locals.wast.out @@ -0,0 +1,22 @@ +(module + (type $none_=>_none (func)) + (import "import" "import" (func $import)) + (global $sp (mut i32) (i32.const 104)) + (memory $0 256 256) + (data (i32.const 10) "__s______________") + (export "test1" (func $test1_0)) + (func $test1_0 + (local $0 i32) + (local.set $0 + (i32.const 100) + ) + (call $import) + (i32.store8 + (i32.const 13) + (i32.const 115) + ) + (global.set $sp + (local.get $0) + ) + ) +) diff --git a/test/ctor-eval/partial-return.wast b/test/ctor-eval/partial-return.wast new file mode 100644 index 000000000..8ca6eee75 --- /dev/null +++ b/test/ctor-eval/partial-return.wast @@ -0,0 +1,31 @@ +(module + (import "import" "import" (func $import)) + + (memory 256 256) + (data (i32.const 10) "_________________") + + (export "test1" $test1) + (export "memory" (memory $0)) + + (func $test1 + ;; A safe store, should alter memory + (i32.store8 (i32.const 12) (i32.const 115)) + + ;; Load the value we just saved, and return because of its value. (This way + ;; we could not see the return must execute without ctor-eval. At least, not + ;; without store-load forwarding.) + (if + (i32.load8_u + (i32.const 12) + ) + (return) + ) + + ;; This is unsafe to call, and would stop evalling here. But we exit due to + ;; the return before anyhow, so it doesn't matter. + (call $import) + + ;; A safe store that we never reach because of the return before us. + (i32.store8 (i32.const 13) (i32.const 115)) + ) +) diff --git a/test/ctor-eval/partial-return.wast.ctors b/test/ctor-eval/partial-return.wast.ctors new file mode 100644 index 000000000..a5bce3fd2 --- /dev/null +++ b/test/ctor-eval/partial-return.wast.ctors @@ -0,0 +1 @@ +test1 diff --git a/test/ctor-eval/partial-return.wast.out b/test/ctor-eval/partial-return.wast.out new file mode 100644 index 000000000..572a93bb0 --- /dev/null +++ b/test/ctor-eval/partial-return.wast.out @@ -0,0 +1,5 @@ +(module + (memory $0 256 256) + (data (i32.const 10) "__s______________") + (export "memory" (memory $0)) +) diff --git a/test/ctor-eval/partial.wast b/test/ctor-eval/partial.wast new file mode 100644 index 000000000..bbff880e7 --- /dev/null +++ b/test/ctor-eval/partial.wast @@ -0,0 +1,30 @@ +(module + (import "import" "import" (func $import)) + + (memory 256 256) + (data (i32.const 10) "_________________") + + (export "test1" $test1) + + ;; Use the function in an additional export. We should still get the same + ;; results if we call this one, so it should point to identical contents as + ;; earlier + (export "keepalive" $test1) + + (func $test1 + ;; A safe store, should alter memory + (i32.store8 (i32.const 12) (i32.const 115)) + + ;; A call to an import, which prevents evalling. + (call $import) + + ;; Another safe store, but the import call before us will stop our evalling. + ;; As a result we will only partially eval this function, applying only + ;; the first store. + ;; + ;; After optimization, the test1 export will point to a function that does + ;; not have the first store anymore. It will contain just the call to the + ;; import and then this second store. + (i32.store8 (i32.const 13) (i32.const 114)) + ) +) diff --git a/test/ctor-eval/partial.wast.ctors b/test/ctor-eval/partial.wast.ctors new file mode 100644 index 000000000..a5bce3fd2 --- /dev/null +++ b/test/ctor-eval/partial.wast.ctors @@ -0,0 +1 @@ +test1 diff --git a/test/ctor-eval/partial.wast.out b/test/ctor-eval/partial.wast.out new file mode 100644 index 000000000..4596a16a3 --- /dev/null +++ b/test/ctor-eval/partial.wast.out @@ -0,0 +1,26 @@ +(module + (type $none_=>_none (func)) + (import "import" "import" (func $import)) + (memory $0 256 256) + (data (i32.const 10) "__s______________") + (export "test1" (func $test1_0)) + (export "keepalive" (func $test1)) + (func $test1 + (i32.store8 + (i32.const 12) + (i32.const 115) + ) + (call $import) + (i32.store8 + (i32.const 13) + (i32.const 114) + ) + ) + (func $test1_0 + (call $import) + (i32.store8 + (i32.const 13) + (i32.const 114) + ) + ) +) diff --git a/test/ctor-eval/results.wast b/test/ctor-eval/results.wast new file mode 100644 index 000000000..83fc245fe --- /dev/null +++ b/test/ctor-eval/results.wast @@ -0,0 +1,7 @@ +(module + (func "test1" (result i32) + ;; The presence of a result stops us from evalling this function (at least + ;; for now). + (i32.const 42) + ) +) diff --git a/test/ctor-eval/results.wast.ctors b/test/ctor-eval/results.wast.ctors new file mode 100644 index 000000000..a5bce3fd2 --- /dev/null +++ b/test/ctor-eval/results.wast.ctors @@ -0,0 +1 @@ +test1 diff --git a/test/ctor-eval/results.wast.out b/test/ctor-eval/results.wast.out new file mode 100644 index 000000000..b9dc2cf57 --- /dev/null +++ b/test/ctor-eval/results.wast.out @@ -0,0 +1,7 @@ +(module + (type $none_=>_i32 (func (result i32))) + (export "test1" (func $0)) + (func $0 (result i32) + (i32.const 42) + ) +) |