wasm-metadce tool (#1320)

This adds a new tool for better dead code elimination. The problem this helps overcome is when the wasm module is part of something larger, like a wasm+JS combination, and therefore doing DCE in either one is not sufficient as it can't remove a cycle spanning the wasm and JS worlds. Concretely, when binaryen performs DCE by itself, it can never remove an export, because it considers those roots - but in the larger ("meta") space outside, they may actually be removable.

To solve that, this tool receives a description of the outside graph (in very abstract form), including which nodes are roots. It then adds to that graph nodes from the wasm, so that we have a single graph representing the entire space (the outside + wasm + connections between them). It then performs DCE, finding what is not reachable from the roots, and cleaning it up from the wasm. It of course can't clean up things from the outside, since all it has is the abstract representation of those things in the graph, but it prints out the ids of the removable nodes, which an outside tool can use.

This tool is written in as general a way as possible, hopefully it can have multiple uses. The use I have in mind is to write something in emscripten that uses this to DCE the JS+wasm combination that we emit.

1 files changed, 19 insertions, 1 deletions

diff --git a/check.py b/check.py
index b7c7cf3ed..64648b567 100755
--- a/check.py
+++ b/check.py
@@ -23,7 +23,7 @@ import sys
 from scripts.test.support import run_command, split_wast
 from scripts.test.shared import (
     BIN_DIR, EMCC, MOZJS, NATIVECC, NATIVEXX, NODEJS, S2WASM_EXE,
-    WASM_AS, WASM_CTOR_EVAL, WASM_OPT, WASM_SHELL, WASM_MERGE, WASM_SHELL_EXE,
+    WASM_AS, WASM_CTOR_EVAL, WASM_OPT, WASM_SHELL, WASM_MERGE, WASM_SHELL_EXE, WASM_METADCE,
     WASM_DIS, WASM_REDUCE, binary_format_check, delete_from_orbit, fail, fail_with_error,
     fail_if_not_identical, fail_if_not_contained, has_vanilla_emcc,
     has_vanilla_llvm, minify_check, num_failures, options, tests,
@@ -209,6 +209,23 @@ def run_ctor_eval_tests():
       with open(out) as f:
         fail_if_not_identical(f.read(), actual)
 
+def run_wasm_metadce_tests():
+  print '\n[ checking wasm-metadce ]\n'
+
+  for t in os.listdir(os.path.join('test', 'metadce')):
+    if t.endswith(('.wast', '.wasm')):
+      print '..', t
+      t = os.path.join('test', 'metadce', t)
+      graph = t + '.graph.txt'
+      cmd = WASM_METADCE + [t, '--graph-file=' + graph, '-o', 'a.wast', '-S']
+      stdout = run_command(cmd)
+      expected = t + '.dced'
+      with open('a.wast') as seen:
+        with open(expected) as correct:
+          fail_if_not_identical(seen.read(), correct.read())
+      with open(expected + '.stdout') as correct:
+        fail_if_not_identical(stdout, correct.read())
+
 def run_wasm_reduce_tests():
   print '\n[ checking wasm-reduce ]\n'
 
@@ -560,6 +577,7 @@ def main():
   run_wasm_dis_tests()
   run_wasm_merge_tests()
   run_ctor_eval_tests()
+  run_wasm_metadce_tests()
   if has_shell_timeout():
     run_wasm_reduce_tests()