diff options
| -rw-r--r-- | src/ir/module-utils.h | 90 | ||||
| -rw-r--r-- | src/passes/Asyncify.cpp | 74 |
2 files changed, 103 insertions, 61 deletions
diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h index 16ecd54b0..52765035c 100644 --- a/src/ir/module-utils.h +++ b/src/ir/module-utils.h @@ -20,6 +20,7 @@ #include "ir/find_all.h" #include "ir/manipulation.h" #include "pass.h" +#include "support/unique_deferring_queue.h" #include "wasm.h" namespace wasm { @@ -288,22 +289,33 @@ template<typename T> inline void iterDefinedEvents(Module& wasm, T visitor) { } } -// Performs a parallel map on function in the module, emitting a map object -// of function => result. -// TODO: use in inlining and elsewhere -template<typename T> struct ParallelFunctionMap { +// Helper class for analyzing the call graph. +// +// Provides hooks for running some initial calculation on each function (which +// is done in parallel), writing to a FunctionInfo structure for each function. +// Then you can call propagateBack() to propagate a property of interest to the +// calling functions, transitively. +// +// For example, if some functions are known to call an import "foo", then you +// can use this to find which functions call something that might eventually +// reach foo, by initially marking the direct callers as "calling foo" and +// propagating that backwards. +template<typename T> struct CallGraphPropertyAnalysis { + Module& wasm; + + // The basic information for each function about whom it calls and who is + // called by it. + struct FunctionInfo { + std::set<Function*> callsTo; + std::set<Function*> calledBy; + }; typedef std::map<Function*, T> Map; Map map; typedef std::function<void(Function*, T&)> Func; - struct Info { - Map* map; - Func work; - }; - - ParallelFunctionMap(Module& wasm, Func work) { + CallGraphPropertyAnalysis(Module& wasm, Func work) : wasm(wasm) { // Fill in map, as we operate on it in parallel (each function to its own // entry). for (auto& func : wasm.functions) { @@ -317,27 +329,65 @@ template<typename T> struct ParallelFunctionMap { } } - // Run on the implemented functions. struct Mapper : public WalkerPass<PostWalker<Mapper>> { bool isFunctionParallel() override { return true; } - Mapper(Info* info) : info(info) {} + Mapper(Module* module, Map* map, Func work) + : module(module), map(map), work(work) {} + + Mapper* create() override { return new Mapper(module, map, work); } - Mapper* create() override { return new Mapper(info); } + void visitCall(Call* curr) { + (*map)[this->getFunction()].callsTo.insert( + module->getFunction(curr->target)); + } - void doWalkFunction(Function* curr) { - assert((*info->map).count(curr)); - info->work(curr, (*info->map)[curr]); + void visitFunction(Function* curr) { + assert((*map).count(curr)); + work(curr, (*map)[curr]); } private: - Info* info; + Module* module; + Map* map; + Func work; }; - Info info = {&map, work}; - PassRunner runner(&wasm); - Mapper(&info).run(&runner, &wasm); + Mapper(&wasm, &map, work).run(&runner, &wasm); + + // Find what is called by what. + for (auto& pair : map) { + auto* func = pair.first; + auto& info = pair.second; + for (auto* target : info.callsTo) { + map[target].calledBy.insert(func); + } + } + } + + // Propagate a property from a function to those that call it. + void propagateBack(std::function<bool(const T&)> hasProperty, + std::function<bool(const T&)> canHaveProperty, + std::function<void(T&)> addProperty) { + // The work queue contains items we just learned can change the state. + UniqueDeferredQueue<Function*> work; + for (auto& func : wasm.functions) { + if (hasProperty(map[func.get()])) { + work.push(func.get()); + } + } + while (!work.empty()) { + auto* func = work.pop(); + for (auto* caller : map[func].calledBy) { + // If we don't already have the property, and we are not forbidden + // from getting it, then it propagates back to us now. + if (!hasProperty(map[caller]) && canHaveProperty(map[caller])) { + addProperty(map[caller]); + work.push(caller); + } + } + } } }; diff --git a/src/passes/Asyncify.cpp b/src/passes/Asyncify.cpp index c4e1c58bd..dd8845577 100644 --- a/src/passes/Asyncify.cpp +++ b/src/passes/Asyncify.cpp @@ -261,7 +261,6 @@ #include "pass.h" #include "support/file.h" #include "support/string.h" -#include "support/unique_deferring_queue.h" #include "wasm-builder.h" #include "wasm.h" @@ -405,7 +404,8 @@ class ModuleAnalyzer { Module& module; bool canIndirectChangeState; - struct Info { + struct Info + : public ModuleUtils::CallGraphPropertyAnalysis<Info>::FunctionInfo { // If this function can start an unwind/rewind. bool canChangeState = false; // If this function is part of the runtime that receives an unwinding @@ -419,8 +419,7 @@ class ModuleAnalyzer { // the top-most part is still marked as changing the state; so things // that call it are instrumented. This is not done for the bottom. bool isTopMostRuntime = false; - std::set<Function*> callsTo; - std::set<Function*> calledBy; + bool inBlacklist = false; }; typedef std::map<Function*, Info> Map; @@ -443,7 +442,7 @@ public: // Also handle the asyncify imports, removing them (as we will implement // them later), and replace calls to them with calls to the later proper // name. - ModuleUtils::ParallelFunctionMap<Info> scanner( + ModuleUtils::CallGraphPropertyAnalysis<Info> scanner( module, [&](Function* func, Info& info) { if (func->imported()) { // The relevant asyncify imports can definitely change the state. @@ -482,9 +481,7 @@ public: Fatal() << "call to unidenfied asyncify import: " << target->base; } - return; } - info->callsTo.insert(target); } void visitCallIndirect(CallIndirect* curr) { if (curr->isReturn) { @@ -515,52 +512,47 @@ public: } }); - map.swap(scanner.map); - // Functions in the blacklist are assumed to not change the state. - for (auto& name : blacklist.names) { - if (auto* func = module.getFunctionOrNull(name)) { - map[func].canChangeState = false; + for (auto& pair : scanner.map) { + auto* func = pair.first; + auto& info = pair.second; + if (blacklist.match(func->name)) { + info.inBlacklist = true; + info.canChangeState = false; } } - // Remove the asyncify imports, if any. - for (auto& pair : map) { + // Remove the asyncify imports, if any, and any calls to them. + std::vector<Name> funcsToDelete; + for (auto& pair : scanner.map) { auto* func = pair.first; + auto& callsTo = pair.second.callsTo; if (func->imported() && func->module == ASYNCIFY) { - module.removeFunction(func->name); + funcsToDelete.push_back(func->name); } - } - - // Find what is called by what. - for (auto& pair : map) { - auto* func = pair.first; - auto& info = pair.second; - for (auto* target : info.callsTo) { - map[target].calledBy.insert(func); + std::vector<Function*> callersToDelete; + for (auto* target : callsTo) { + if (target->imported() && target->module == ASYNCIFY) { + callersToDelete.push_back(target); + } } - } - - // Close over, finding all functions that can reach something that can - // change the state. - // The work queue contains an item we just learned can change the state. - UniqueDeferredQueue<Function*> work; - for (auto& func : module.functions) { - if (map[func.get()].canChangeState) { - work.push(func.get()); + for (auto* target : callersToDelete) { + callsTo.erase(target); } } - while (!work.empty()) { - auto* func = work.pop(); - for (auto* caller : map[func].calledBy) { - if (!map[caller].canChangeState && !map[caller].isBottomMostRuntime && - !blacklist.match(caller->name)) { - map[caller].canChangeState = true; - work.push(caller); - } - } + for (auto name : funcsToDelete) { + module.removeFunction(name); } + scanner.propagateBack([](const Info& info) { return info.canChangeState; }, + [](const Info& info) { + return !info.isBottomMostRuntime && + !info.inBlacklist; + }, + [](Info& info) { info.canChangeState = true; }); + + map.swap(scanner.map); + if (!whitelistInput.empty()) { // Only the functions in the whitelist can change the state. for (auto& func : module.functions) { |