summaryrefslogtreecommitdiff
path: root/src/tools/wasm-metadce.cpp
diff options
context:
space:
mode:
authorAlon Zakai <alonzakai@gmail.com>2017-12-07 21:33:47 -0800
committerGitHub <noreply@github.com>2017-12-07 21:33:47 -0800
commit9c51f2b51ecc57dfad1478bbc6932ec2795b1374 (patch)
treeb0ded3086e10dd776fa20d8a4b45e2fb54b60a8e /src/tools/wasm-metadce.cpp
parent22f1ce86e48173e9e55a021350c1ec9ca046080f (diff)
downloadbinaryen-9c51f2b51ecc57dfad1478bbc6932ec2795b1374.tar.gz
binaryen-9c51f2b51ecc57dfad1478bbc6932ec2795b1374.tar.bz2
binaryen-9c51f2b51ecc57dfad1478bbc6932ec2795b1374.zip
metadce fixes (#1329)
* ignore missing imports (the wasm may have already had them optimized out) * handle segments that hold on to globals (root them, for now, as we can't remove segments) * run reorder-functions, as the optimal order may have changed after we dce * fix global, global init, and segment offset reachability * fix import rooting and processing - imports may be imported more than once
Diffstat (limited to 'src/tools/wasm-metadce.cpp')
-rw-r--r--src/tools/wasm-metadce.cpp151
1 files changed, 114 insertions, 37 deletions
diff --git a/src/tools/wasm-metadce.cpp b/src/tools/wasm-metadce.cpp
index b6447f58a..c5d12775d 100644
--- a/src/tools/wasm-metadce.cpp
+++ b/src/tools/wasm-metadce.cpp
@@ -51,16 +51,31 @@ struct MetaDCEGraph {
std::unordered_map<Name, DCENode> nodes;
std::unordered_set<Name> roots;
- std::unordered_map<Name, Name> importToDCENode; // import internal name => DCE name
std::unordered_map<Name, Name> exportToDCENode; // export exported name => DCE name
std::unordered_map<Name, Name> functionToDCENode; // function name => DCE name
std::unordered_map<Name, Name> globalToDCENode; // global name => DCE name
- std::unordered_map<Name, Name> DCENodeToImport; // reverse maps
- std::unordered_map<Name, Name> DCENodeToExport;
+ std::unordered_map<Name, Name> DCENodeToExport; // reverse maps
std::unordered_map<Name, Name> DCENodeToFunction;
std::unordered_map<Name, Name> DCENodeToGlobal;
+ // imports are not mapped 1:1 to DCE nodes in the wasm, since env.X might
+ // be imported twice, for example. So we don't map a DCE node to an Import,
+ // but rather the module.base pair ("id") for the import.
+ // TODO: implement this in a safer way, not a string with a magic separator
+ typedef Name ImportId;
+
+ ImportId getImportId(Name module, Name base) {
+ return std::string(module.str) + " (*) " + std::string(base.str);
+ }
+
+ ImportId getImportId(Name name) {
+ auto* imp = wasm.getImport(name);
+ return getImportId(imp->module, imp->base);
+ }
+
+ std::unordered_map<Name, Name> importIdToDCENode; // import module.base => DCE name
+
Module& wasm;
MetaDCEGraph(Module& wasm) : wasm(wasm) {}
@@ -84,11 +99,13 @@ struct MetaDCEGraph {
nodes[dceName] = DCENode(dceName);
}
for (auto& imp : wasm.imports) {
- if (importToDCENode.find(imp->name) == importToDCENode.end()) {
- auto dceName = getName("import", imp->name.str);
- DCENodeToImport[dceName] = imp->name;
- importToDCENode[imp->name] = dceName;
- nodes[dceName] = DCENode(dceName);
+ // only process function and global imports - the table and memory are always there
+ if (imp->kind == ExternalKind::Function || imp->kind == ExternalKind::Global) {
+ auto id = getImportId(imp->module, imp->base);
+ if (importIdToDCENode.find(id) == importIdToDCENode.end()) {
+ auto dceName = getName("importId", imp->name.str);
+ importIdToDCENode[id] = dceName;
+ }
}
}
for (auto& exp : wasm.exports) {
@@ -104,16 +121,72 @@ struct MetaDCEGraph {
if (wasm.getFunctionOrNull(exp->value)) {
node.reaches.push_back(functionToDCENode[exp->value]);
} else {
- node.reaches.push_back(importToDCENode[exp->value]);
+ node.reaches.push_back(importIdToDCENode[getImportId(exp->value)]);
}
} else if (exp->kind == ExternalKind::Global) {
if (wasm.getGlobalOrNull(exp->value)) {
node.reaches.push_back(globalToDCENode[exp->value]);
} else {
- node.reaches.push_back(importToDCENode[exp->value]);
+ node.reaches.push_back(importIdToDCENode[getImportId(exp->value)]);
}
}
}
+ // Add initializer dependencies
+ // if we provide a parent DCE name, that is who can reach what we see
+ // if none is provided, then it is something we must root
+ struct InitScanner : public PostWalker<InitScanner> {
+ InitScanner(MetaDCEGraph* parent, Name parentDceName) : parent(parent), parentDceName(parentDceName) {}
+
+ void visitGetGlobal(GetGlobal* curr) {
+ handleGlobal(curr->name);
+ }
+ void visitSetGlobal(SetGlobal* curr) {
+ handleGlobal(curr->name);
+ }
+
+ private:
+ MetaDCEGraph* parent;
+ Name parentDceName;
+
+ void handleGlobal(Name name) {
+ Name dceName;
+ if (getModule()->getGlobalOrNull(name)) {
+ // its a global
+ dceName = parent->globalToDCENode[name];
+ } else {
+ // it's an import.
+ dceName = parent->importIdToDCENode[parent->getImportId(name)];
+ }
+ if (parentDceName.isNull()) {
+ parent->roots.insert(parentDceName);
+ } else {
+ parent->nodes[parentDceName].reaches.push_back(dceName);
+ }
+ }
+ };
+ for (auto& global : wasm.globals) {
+ InitScanner scanner(this, globalToDCENode[global->name]);
+ scanner.setModule(&wasm);
+ scanner.walk(global->init);
+ }
+ // we can't remove segments, so root what they need
+ InitScanner rooter(this, Name());
+ rooter.setModule(&wasm);
+ for (auto& segment : wasm.table.segments) {
+ // TODO: currently, all functions in the table are roots, but we
+ // should add an option to refine that
+ for (auto& name : segment.data) {
+ if (wasm.getFunctionOrNull(name)) {
+ roots.insert(functionToDCENode[name]);
+ } else {
+ roots.insert(importIdToDCENode[getImportId(name)]);
+ }
+ }
+ rooter.walk(segment.offset);
+ }
+ for (auto& segment : wasm.memory.segments) {
+ rooter.walk(segment.offset);
+ }
// A parallel scanner for function bodies
struct Scanner : public WalkerPass<PostWalker<Scanner>> {
@@ -133,7 +206,7 @@ struct MetaDCEGraph {
void visitCallImport(CallImport* curr) {
assert(parent->functionToDCENode.count(getFunction()->name) > 0);
parent->nodes[parent->functionToDCENode[getFunction()->name]].reaches.push_back(
- parent->importToDCENode[curr->target]
+ parent->importIdToDCENode[parent->getImportId(curr->target)]
);
}
void visitGetGlobal(GetGlobal* curr) {
@@ -147,11 +220,16 @@ struct MetaDCEGraph {
MetaDCEGraph* parent;
void handleGlobal(Name name) {
- if (getModule()->getGlobalOrNull(name)) return;
- // it's an import
- parent->nodes[parent->functionToDCENode[getFunction()->name]].reaches.push_back(
- parent->importToDCENode[name]
- );
+ if (!getFunction()) return; // non-function stuff (initializers) are handled separately
+ Name dceName;
+ if (getModule()->getGlobalOrNull(name)) {
+ // its a global
+ dceName = parent->globalToDCENode[name];
+ } else {
+ // it's an import.
+ dceName = parent->importIdToDCENode[parent->getImportId(name)];
+ }
+ parent->nodes[parent->functionToDCENode[getFunction()->name]].reaches.push_back(dceName);
}
};
@@ -159,21 +237,6 @@ struct MetaDCEGraph {
runner.setIsNested(true);
runner.add<Scanner>(this);
runner.run();
-
- // also scan segment offsets
- Scanner scanner(this);
- scanner.setModule(&wasm);
- for (auto& segment : wasm.table.segments) {
- scanner.walk(segment.offset);
- // TODO: currently, all functions in the table are roots, but we
- // should add an option to refine that
- for (auto& name : segment.data) {
- roots.insert(functionToDCENode[name]);
- }
- }
- for (auto& segment : wasm.memory.segments) {
- scanner.walk(segment.offset);
- }
}
private:
@@ -229,6 +292,7 @@ public:
// Now they are gone, standard optimization passes can do the rest!
PassRunner passRunner(&wasm);
passRunner.add("remove-unused-module-elements");
+ passRunner.add("reorder-functions"); // removing functions may alter the optimum order, as # of calls can change
passRunner.run();
}
@@ -253,13 +317,18 @@ public:
for (auto root : roots) {
std::cout << "root: " << root.str << '\n';
}
+ std::map<Name, ImportId> importMap;
+ for (auto& pair : importIdToDCENode) {
+ auto& id = pair.first;
+ auto dceName = pair.second;
+ importMap[dceName] = id;
+ }
for (auto& pair : nodes) {
auto name = pair.first;
auto& node = pair.second;
std::cout << "node: " << name.str << '\n';
- if (DCENodeToImport.find(name) != DCENodeToImport.end()) {
- auto* imp = wasm.getImport(DCENodeToImport[name]);
- std::cout << " is import " << DCENodeToImport[name] << ", " << imp->module.str << '.' << imp->base.str << '\n';
+ if (importMap.find(name) != importMap.end()) {
+ std::cout << " is import " << importMap[name] << '\n';
}
if (DCENodeToExport.find(name) != DCENodeToExport.end()) {
std::cout << " is export " << DCENodeToExport[name].str << ", " << wasm.getExport(DCENodeToExport[name])->value << '\n';
@@ -288,6 +357,7 @@ int main(int argc, const char* argv[]) {
bool emitBinary = true;
bool debugInfo = false;
std::string graphFile;
+ bool dump = false;
Options options("wasm-metadce", "This tool performs dead code elimination (DCE) on a larger space "
"that the wasm module is just a part of. For example, if you have "
@@ -350,6 +420,9 @@ int main(int argc, const char* argv[]) {
[&](Options* o, const std::string& argument) {
graphFile = argument;
})
+ .add("--dump", "-d", "Dump the combined graph file (useful for debugging)",
+ Options::Arguments::Zero,
+ [&](Options *o, const std::string &arguments) { dump = true; })
.add_positional("INFILE", Options::Arguments::One,
[](Options* o, const std::string& argument) {
o->extra["infile"] = argument;
@@ -439,9 +512,8 @@ int main(int argc, const char* argv[]) {
if (!imp->isArray() || imp->size() != 2 || !imp[0]->isString() || !imp[1]->isString()) {
Fatal() << "node.import, if it exists, must be an array of two strings. see --help for the form";
}
- auto importName = ImportUtils::getImport(wasm, imp[0]->getIString(), imp[1]->getIString())->name;
- graph.importToDCENode[importName] = node.name;
- graph.DCENodeToImport[node.name] = importName;
+ auto id = graph.getImportId(imp[0]->getIString(), imp[1]->getIString());
+ graph.importIdToDCENode[id] = node.name;
}
// TODO: optimize this copy with a clever move
graph.nodes[node.name] = node;
@@ -450,6 +522,11 @@ int main(int argc, const char* argv[]) {
// The external graph is now populated. Scan the module
graph.scanWebAssembly();
+ // Debug dump the graph, if requested
+ if (dump) {
+ graph.dump();
+ }
+
// Perform the DCE
graph.deadCodeElimination();
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-06 04:09:47 +0000