Bysyncify: add ignore-imports and ignore-indirect options (#2178)

ignore-imports makes it not assume that any import may unwind/rewind the stack. ignore-indirect makes it not assume any indirect call can reach an unwind/rewind (which means, it assumes there is not an indirect call on the stack while unwinding).

4 files changed, 317 insertions, 35 deletions

diff --git a/src/passes/Bysyncify.cpp b/src/passes/Bysyncify.cpp
index f9f679f2e..dcc543c5e 100644
--- a/src/passes/Bysyncify.cpp
+++ b/src/passes/Bysyncify.cpp
@@ -167,21 +167,30 @@
 // we are recreating the call stack. At that point you should call
 // bysyncify_stop_rewind and then execution can resume normally.
 //
-// By default this pass assumes that any import may call any of the
-// exported bysyncify methods, that is, any import may start an unwind/rewind.
-// To customize this, you can provide an argument to wasm-opt (or another
-// tool that can run this pass),
+// By default this pass is very carefuly: it assumes that any import and
+// any indirect call may start an unwind/rewind operation. If you know more
+// specific information you can inform bysyncify about that, which can reduce
+// a great deal of overhead, as it can instrument less code. The relevant
+// options to wasm-opt etc. are:
 //
 //   --pass-arg=bysyncify-imports@module1.base1,module2.base2,module3.base3
 //
-// Each module.base in that comma-separated list will be considered to
-// be an import that can unwind/rewind, and all others are assumed not to
-// (aside from the bysyncify.* imports, which are always assumed to). To
-// say that no import (aside from bysyncify.*) can do so (that is, the
-// opposite of the default behavior), you can simply provide an import
-// that doesn't exist, for example:
-
-// --pass-arg=bysyncify-imports@no.imports
+//      Each module.base in that comma-separated list will be considered to
+//      be an import that can unwind/rewind, and all others are assumed not to
+//      (aside from the bysyncify.* imports, which are always assumed to).
+//
+//   --pass-arg=bysyncify-ignore-imports
+//
+//      Ignore all imports (except for bynsyncify.*), that is, assume none of
+//      them can start an unwind/rewind. (This is effectively the same as
+//      providing bysyncify-imports with a list of non-existent imports.)
+//
+//   --pass-arg=bysyncify-ignore-indirect
+//
+//      Ignore all indirect calls. This implies that you know an call stack
+//      will never need to be unwound with an indirect call somewhere in it.
+//      If that is true for your codebase, then this can be extremely useful
+//      as otherwise it looks like any indirect call can go to a lot of places.
 //
 
 #include "ir/effects.h"
@@ -225,6 +234,7 @@ const auto STACK_ALIGN = 4;
 // by it.
 class ModuleAnalyzer {
   Module& module;
+  bool canIndirectChangeState;
 
   struct Info {
     bool canChangeState = false;
@@ -237,8 +247,9 @@ class ModuleAnalyzer {
 
 public:
   ModuleAnalyzer(Module& module,
-                 std::function<bool(Name, Name)> canImportChangeState)
-    : module(module) {
+                 std::function<bool(Name, Name)> canImportChangeState,
+                 bool canIndirectChangeState)
+    : module(module), canIndirectChangeState(canIndirectChangeState) {
     // Scan to see which functions can directly change the state.
     // Also handle the bysyncify imports, removing them (as we will implement
     // them later), and replace calls to them with calls to the later proper
@@ -281,15 +292,19 @@ public:
             info->callsTo.insert(target);
           }
           void visitCallIndirect(CallIndirect* curr) {
-            // TODO optimize
-            info->canChangeState = true;
+            if (canIndirectChangeState) {
+              info->canChangeState = true;
+            }
+            // TODO optimize the other case, at least by type
           }
           Info* info;
           Module* module;
+          bool canIndirectChangeState;
         };
         Walker walker;
         walker.info = &info;
         walker.module = &module;
+        walker.canIndirectChangeState = canIndirectChangeState;
         walker.walk(func->body);
       });
     map.swap(scanner.map);
@@ -357,16 +372,20 @@ public:
         }
       }
       void visitCallIndirect(CallIndirect* curr) {
-        // TODO optimize
-        canChangeState = true;
+        if (canIndirectChangeState) {
+          canChangeState = true;
+        }
+        // TODO optimize the other case, at least by type
       }
       Module* module;
       Map* map;
+      bool canIndirectChangeState;
       bool canChangeState = false;
     };
     Walker walker;
     walker.module = &module;
     walker.map = &map;
+    walker.canIndirectChangeState = canIndirectChangeState;
     walker.walk(curr);
     return walker.canChangeState;
   }
@@ -788,23 +807,31 @@ private:
 struct Bysyncify : public Pass {
   void run(PassRunner* runner, Module* module) override {
     bool optimize = runner->options.optimizeLevel > 0;
-    // Find which imports can change the state.
-    const char* ALL_IMPORTS_CAN_CHANGE_STATE = "__bysyncify_all_imports";
-    auto stateChangingImports = runner->options.getArgumentOrDefault(
-      "bysyncify-imports", ALL_IMPORTS_CAN_CHANGE_STATE);
-    bool allImportsCanChangeState =
-      stateChangingImports == ALL_IMPORTS_CAN_CHANGE_STATE;
+    // Find which things can change the state.
+    auto stateChangingImports =
+      runner->options.getArgumentOrDefault("bysyncify-imports", "");
     std::string separator = ",";
-    stateChangingImports = separator + stateChangingImports + separator;
+    auto ignoreImports =
+      runner->options.getArgumentOrDefault("bysyncify-ignore-imports", "");
+    bool allImportsCanChangeState =
+      stateChangingImports == "" && ignoreImports == "";
+    if (!allImportsCanChangeState) {
+      stateChangingImports = separator + stateChangingImports + separator;
+    }
+    auto ignoreIndirect =
+      runner->options.getArgumentOrDefault("bysyncify-ignore-indirect", "");
 
     // Scan the module.
-    ModuleAnalyzer analyzer(*module, [&](Name module, Name base) {
-      if (allImportsCanChangeState) {
-        return true;
-      }
-      std::string full = separator + module.str + '.' + base.str + separator;
-      return stateChangingImports.find(full) != std::string::npos;
-    });
+    ModuleAnalyzer analyzer(
+      *module,
+      [&](Name module, Name base) {
+        if (allImportsCanChangeState) {
+          return true;
+        }
+        std::string full = separator + module.str + '.' + base.str + separator;
+        return stateChangingImports.find(full) != std::string::npos;
+      },
+      ignoreIndirect == "");
 
     // Add necessary globals before we emit code to use them.
     addGlobals(module);
diff --git a/src/tools/optimization-options.h b/src/tools/optimization-options.h
index a07e585bd..9d8259077 100644
--- a/src/tools/optimization-options.h
+++ b/src/tools/optimization-options.h
@@ -187,12 +187,15 @@ struct OptimizationOptions : public ToolOptions {
            "in the form KEY@VALUE",
            Options::Arguments::N,
            [this](Options*, const std::string& argument) {
+             std::string key, value;
              auto colon = argument.find('@');
              if (colon == std::string::npos) {
-               Fatal() << "--pass-arg value must be in the form of KEY@VALUE";
+               key = argument;
+               value = "1";
+             } else {
+               key = argument.substr(0, colon);
+               value = argument.substr(colon + 1);
              }
-             auto key = argument.substr(0, colon);
-             auto value = argument.substr(colon + 1);
              passOptions.arguments[key] = value;
            });
     // add passes in registry
diff --git a/test/passes/bysyncify_pass-arg=bysyncify-ignore-imports.txt b/test/passes/bysyncify_pass-arg=bysyncify-ignore-imports.txt
new file mode 100644
index 000000000..adfaf6df7
--- /dev/null
+++ b/test/passes/bysyncify_pass-arg=bysyncify-ignore-imports.txt
@@ -0,0 +1,226 @@
+(module
+ (type $f (func))
+ (type $FUNCSIG$i (func (result i32)))
+ (type $FUNCSIG$vi (func (param i32)))
+ (import "env" "import" (func $import))
+ (import "env" "import2" (func $import2 (result i32)))
+ (import "env" "import3" (func $import3 (param i32)))
+ (memory $0 1 2)
+ (table $0 2 2 funcref)
+ (elem (i32.const 0) $calls-import2-drop $calls-import2-drop)
+ (global $__bysyncify_state (mut i32) (i32.const 0))
+ (global $__bysyncify_data (mut i32) (i32.const 0))
+ (export "bysyncify_start_unwind" (func $bysyncify_start_unwind))
+ (export "bysyncify_stop_unwind" (func $bysyncify_stop_unwind))
+ (export "bysyncify_start_rewind" (func $bysyncify_start_rewind))
+ (export "bysyncify_stop_rewind" (func $bysyncify_stop_rewind))
+ (func $calls-import (; 3 ;) (type $f)
+  (call $import)
+ )
+ (func $calls-import2-drop (; 4 ;) (type $f)
+  (local $0 i32)
+  (local.set $0
+   (call $import2)
+  )
+ )
+ (func $calls-import2-if-else (; 5 ;) (type $FUNCSIG$vi) (param $x i32)
+  (local $1 i32)
+  (if
+   (local.get $x)
+   (call $import3
+    (i32.const 1)
+   )
+   (call $import3
+    (i32.const 2)
+   )
+  )
+ )
+ (func $calls-indirect (; 6 ;) (type $FUNCSIG$vi) (param $x i32)
+  (local $1 i32)
+  (local $2 i32)
+  (local $3 i32)
+  (local $4 i32)
+  (local $5 i32)
+  (if
+   (i32.eq
+    (global.get $__bysyncify_state)
+    (i32.const 2)
+   )
+   (block
+    (i32.store
+     (global.get $__bysyncify_data)
+     (i32.add
+      (i32.load
+       (global.get $__bysyncify_data)
+      )
+      (i32.const -8)
+     )
+    )
+    (local.set $4
+     (i32.load
+      (global.get $__bysyncify_data)
+     )
+    )
+    (local.set $x
+     (i32.load
+      (local.get $4)
+     )
+    )
+    (local.set $1
+     (i32.load offset=4
+      (local.get $4)
+     )
+    )
+   )
+  )
+  (local.set $2
+   (block $__bysyncify_unwind (result i32)
+    (block
+     (block
+      (if
+       (i32.eq
+        (global.get $__bysyncify_state)
+        (i32.const 2)
+       )
+       (block
+        (i32.store
+         (global.get $__bysyncify_data)
+         (i32.add
+          (i32.load
+           (global.get $__bysyncify_data)
+          )
+          (i32.const -4)
+         )
+        )
+        (local.set $3
+         (i32.load
+          (i32.load
+           (global.get $__bysyncify_data)
+          )
+         )
+        )
+       )
+      )
+      (if
+       (if (result i32)
+        (i32.eq
+         (global.get $__bysyncify_state)
+         (i32.const 0)
+        )
+        (i32.const 1)
+        (i32.eq
+         (local.get $3)
+         (i32.const 0)
+        )
+       )
+       (block
+        (call_indirect (type $f)
+         (local.get $x)
+        )
+        (if
+         (i32.eq
+          (global.get $__bysyncify_state)
+          (i32.const 1)
+         )
+         (br $__bysyncify_unwind
+          (i32.const 0)
+         )
+        )
+       )
+      )
+     )
+     (return)
+    )
+   )
+  )
+  (block
+   (i32.store
+    (i32.load
+     (global.get $__bysyncify_data)
+    )
+    (local.get $2)
+   )
+   (i32.store
+    (global.get $__bysyncify_data)
+    (i32.add
+     (i32.load
+      (global.get $__bysyncify_data)
+     )
+     (i32.const 4)
+    )
+   )
+  )
+  (block
+   (local.set $5
+    (i32.load
+     (global.get $__bysyncify_data)
+    )
+   )
+   (i32.store
+    (local.get $5)
+    (local.get $x)
+   )
+   (i32.store offset=4
+    (local.get $5)
+    (local.get $1)
+   )
+   (i32.store
+    (global.get $__bysyncify_data)
+    (i32.add
+     (i32.load
+      (global.get $__bysyncify_data)
+     )
+     (i32.const 8)
+    )
+   )
+  )
+ )
+ (func $bysyncify_start_unwind (; 7 ;) (param $0 i32)
+  (if
+   (i32.gt_u
+    (i32.load
+     (local.get $0)
+    )
+    (i32.load offset=4
+     (local.get $0)
+    )
+   )
+   (unreachable)
+  )
+  (global.set $__bysyncify_state
+   (i32.const 1)
+  )
+  (global.set $__bysyncify_data
+   (local.get $0)
+  )
+ )
+ (func $bysyncify_stop_unwind (; 8 ;)
+  (global.set $__bysyncify_state
+   (i32.const 0)
+  )
+ )
+ (func $bysyncify_start_rewind (; 9 ;) (param $0 i32)
+  (if
+   (i32.gt_u
+    (i32.load
+     (local.get $0)
+    )
+    (i32.load offset=4
+     (local.get $0)
+    )
+   )
+   (unreachable)
+  )
+  (global.set $__bysyncify_state
+   (i32.const 2)
+  )
+  (global.set $__bysyncify_data
+   (local.get $0)
+  )
+ )
+ (func $bysyncify_stop_rewind (; 10 ;)
+  (global.set $__bysyncify_state
+   (i32.const 0)
+  )
+ )
+)
diff --git a/test/passes/bysyncify_pass-arg=bysyncify-ignore-imports.wast b/test/passes/bysyncify_pass-arg=bysyncify-ignore-imports.wast
new file mode 100644
index 000000000..33500baba
--- /dev/null
+++ b/test/passes/bysyncify_pass-arg=bysyncify-ignore-imports.wast
@@ -0,0 +1,26 @@
+(module
+  (memory 1 2)
+  (type $f (func))
+  (import "env" "import" (func $import))
+  (import "env" "import2" (func $import2 (result i32)))
+  (import "env" "import3" (func $import3 (param i32)))
+  (table 1 1)
+  (func $calls-import
+    (call $import)
+  )
+  (func $calls-import2-drop
+    (drop (call $import2))
+  )
+  (func $calls-import2-if-else (param $x i32)
+    (if (local.get $x)
+      (call $import3 (i32.const 1))
+      (call $import3 (i32.const 2))
+    )
+  )
+  (func $calls-indirect (param $x i32)
+    (call_indirect (type $f)
+      (local.get $x)
+    )
+  )
+)
+