Bysyncify: async transform for wasm (#2172)

This adds a new pass, Bysyncify, which transforms code to allow unwind and rewinding the call stack and local state. This allows things like coroutines, turning synchronous code asynchronous, etc.

The new pass file itself has a large comment on top with docs.

So far the tests here seem to show this works, but this hasn't been tested heavily yet. My next step is to hook this up to emscripten as a replacement for asyncify/emterpreter, see emscripten-core/emscripten#8561

Note that this is completely usable by itself, so it could be useful for any language that needs coroutines etc., and not just ones using LLVM and/or emscripten. See docs on the ABI in the pass source.

3 files changed, 375 insertions, 0 deletions

diff --git a/test/unit/input/bysyncify.js b/test/unit/input/bysyncify.js
new file mode 100644
index 000000000..97d7a0da5
--- /dev/null
+++ b/test/unit/input/bysyncify.js
@@ -0,0 +1,155 @@
+
+function assert(x, y) {
+  if (!x) throw (y || 'assertion failed') + '\n' + new Error().stack;
+}
+
+var fs = require('fs');
+
+// Get and compile the wasm.
+
+var binary = fs.readFileSync('a.wasm');
+
+var module = new WebAssembly.Module(binary);
+
+var DATA_ADDR = 4;
+
+var sleeps = 0;
+
+var sleeping = false;
+
+var instance = new WebAssembly.Instance(module, {
+  env: {
+    sleep: function() {
+      logMemory();
+assert(view[0] == 0);
+      if (!sleeping) {
+        // We are called in order to start a sleep/unwind.
+        console.log('sleep...');
+        sleeps++;
+        // Unwinding.
+        exports.bysyncify_start_unwind(DATA_ADDR);
+        // Fill in the data structure. The first value has the stack location,
+        // which for simplicity we can start right after the data structure itself.
+        view[DATA_ADDR >> 2] = DATA_ADDR + 8;
+        // The end of the stack will not be reached here anyhow.
+        view[DATA_ADDR + 4 >> 2] = 1024;
+        sleeping = true;
+      } else {
+        // We are called as part of a resume/rewind. Stop sleeping.
+        console.log('resume...');
+        exports.bysyncify_stop_rewind();
+        // The stack should have been all used up, and so returned to the original state.
+        assert(view[DATA_ADDR >> 2] == DATA_ADDR + 8);
+        assert(view[DATA_ADDR + 4 >> 2] == 1024);
+        sleeping = false;
+      }
+      logMemory();
+    },
+    tunnel: function(x) {
+      console.log('tunneling, sleep == ' + sleeping);
+      return exports.end_tunnel(x);
+    }
+  }
+});
+
+var exports = instance.exports;
+var view = new Int32Array(exports.memory.buffer);
+
+function logMemory() {
+  // Log the relevant memory locations for debugging purposes.
+  console.log('memory: ', view[0 >> 2], view[4 >> 2], view[8 >> 2], view[12 >> 2], view[16 >> 2], view[20 >> 2], view[24 >> 2]);
+}
+
+function runTest(name, expectedSleeps, expectedResult, params) {
+  params = params || [];
+
+  console.log('\n==== testing ' + name + ' ====');
+
+  sleeps = 0;
+
+  logMemory();
+
+  // Run until the sleep.
+  var result = exports[name].apply(null, params);
+  logMemory();
+
+  if (expectedSleeps > 0) {
+    assert(!result, 'results during sleep are meaningless, just 0');
+
+    for (var i = 0; i < expectedSleeps - 1; i++) {
+      console.log('rewind, run until the next sleep');
+      exports.bysyncify_start_rewind(DATA_ADDR);
+      result = exports[name](); // no need for params on later times
+      assert(!result, 'results during sleep are meaningless, just 0');
+      assert(!result, 'bad first sleep result');
+      logMemory();
+    }
+
+    console.log('rewind and run til the end.');
+    exports.bysyncify_start_rewind(DATA_ADDR);
+    result = exports[name]();
+  }
+
+  console.log('final result: ' + result);
+  assert(result == expectedResult, 'bad final result');
+  logMemory();
+
+  assert(sleeps == expectedSleeps, 'expectedSleeps');
+}
+
+//================
+// Tests
+//================
+
+// A minimal single sleep.
+runTest('minimal', 1, 21);
+
+// Two sleeps.
+runTest('repeat', 2, 42);
+
+// A value in a local is preserved across a sleep.
+runTest('local', 1, 10);
+
+// A local with more operations done on it.
+runTest('local2', 1, 22);
+
+// A local with more operations done on it.
+runTest('params', 1, 18);
+runTest('params', 1, 21, [1, 2]);
+
+// Calls to multiple other functions, only one of whom
+// sleeps, and keep locals and globals valid throughout.
+runTest('deeper', 0, 27, [0]);
+runTest('deeper', 1,  3, [1]);
+
+// A recursive factorial, that sleeps on each iteration
+// above 1.
+runTest('factorial-recursive', 0,   1, [1]);
+runTest('factorial-recursive', 1,   2, [2]);
+runTest('factorial-recursive', 2,   6, [3]);
+runTest('factorial-recursive', 3,  24, [4]);
+runTest('factorial-recursive', 4, 120, [5]);
+
+// A looping factorial, that sleeps on each iteration
+// above 1.
+runTest('factorial-loop', 0,   1, [1]);
+runTest('factorial-loop', 1,   2, [2]);
+runTest('factorial-loop', 2,   6, [3]);
+runTest('factorial-loop', 3,  24, [4]);
+runTest('factorial-loop', 4, 120, [5]);
+
+// Test calling into JS in the middle (which can work if
+// the JS just forwards the call and has no side effects or
+// state of its own that needs to be saved).
+runTest('do_tunnel', 2, 72, [1]);
+
+// Test indirect function calls.
+runTest('call_indirect', 3, 432, [1, 2]);
+
+// Test indirect function calls.
+runTest('if_else', 3, 1460, [1, 1000]);
+runTest('if_else', 3, 2520, [2, 2000]);
+
+// All done.
+console.log('\ntests completed successfully');
+
diff --git a/test/unit/input/bysyncify.wast b/test/unit/input/bysyncify.wast
new file mode 100644
index 000000000..91fb5a327
--- /dev/null
+++ b/test/unit/input/bysyncify.wast
@@ -0,0 +1,200 @@
+(module
+  (memory 1 2)
+  (type $ii (func (param i32) (result i32)))
+  (import "env" "sleep" (func $sleep))
+  (import "env" "tunnel" (func $tunnel (param $x i32) (result i32)))
+  (export "memory" (memory 0))
+  (export "factorial-recursive" (func $factorial-recursive))
+  (global $temp (mut i32) (i32.const 0))
+  (table 10 funcref)
+  (elem (i32.const 5) $tablefunc)
+  (func "minimal" (result i32)
+    (call $sleep)
+    (i32.const 21)
+  )
+  (func "repeat" (result i32)
+    ;; sleep twice, then return 42
+    (call $sleep)
+    (call $sleep)
+    (i32.const 42)
+  )
+  (func "local" (result i32)
+    (local $x i32)
+    (local.set $x (i32.load (i32.const 0))) ;; a zero that the optimizer won't see
+    (local.set $x
+      (i32.add (local.get $x) (i32.const 10)) ;; add 10
+    )
+    (call $sleep)
+    (local.get $x)
+  )
+  (func "local2" (result i32)
+    (local $x i32)
+    (local.set $x (i32.load (i32.const 0))) ;; a zero that the optimizer won't see
+    (local.set $x
+      (i32.add (local.get $x) (i32.const 10)) ;; add 10
+    )
+    (call $sleep)
+    (local.set $x
+      (i32.add (local.get $x) (i32.const 12)) ;; add 12 more
+    )
+    (local.get $x)
+  )
+  (func "params" (param $x i32) (param $y i32) (result i32)
+    (local.set $x
+      (i32.add (local.get $x) (i32.const 17)) ;; add 10
+    )
+    (local.set $y
+      (i32.add (local.get $y) (i32.const 1)) ;; add 12 more
+    )
+    (call $sleep)
+    (i32.add (local.get $x) (local.get $y))
+  )
+  (func $pre
+    (global.set $temp (i32.const 1))
+  )
+  (func $inner (param $x i32)
+    (if (i32.eqz (local.get $x)) (call $post))
+    (if (local.get $x) (call $sleep))
+    (if (i32.eqz (local.get $x)) (call $post))
+  )
+  (func $post
+    (global.set $temp
+      (i32.mul
+        (global.get $temp)
+        (i32.const 3)
+      )
+    )
+  )
+  (func "deeper" (param $x i32) (result i32)
+    (call $pre)
+    (call $inner (local.get $x))
+    (call $post)
+    (global.get $temp)
+  )
+  (func $factorial-recursive (param $x i32) (result i32)
+    (if
+      (i32.eq
+        (local.get $x)
+        (i32.const 1)
+      )
+      (return (i32.const 1))
+    )
+    (call $sleep)
+    (return
+      (i32.mul
+        (local.get $x)
+        (call $factorial-recursive
+          (i32.sub
+            (local.get $x)
+            (i32.const 1)
+          )
+        )
+      )
+    )
+  )
+  (func "factorial-loop" (param $x i32) (result i32)
+    (local $i i32)
+    (local $ret i32)
+    (local.set $ret (i32.const 1))
+    (local.set $i (i32.const 2))
+    (loop $l
+      (if
+        (i32.gt_u
+          (local.get $i)
+          (local.get $x)
+        )
+        (return (local.get $ret))
+      )
+      (local.set $ret
+        (i32.mul
+          (local.get $ret)
+          (local.get $i)
+        )
+      )
+      (call $sleep)
+      (local.set $i
+        (i32.add
+          (local.get $i)
+          (i32.const 1)
+        )
+      )
+      (br $l)
+    )
+  )
+  (func "end_tunnel" (param $x i32) (result i32)
+    (local.set $x
+      (i32.add (local.get $x) (i32.const 22))
+    )
+    (call $sleep)
+    (i32.add (local.get $x) (i32.const 5))
+  )
+  (func "do_tunnel" (param $x i32) (result i32)
+    (local.set $x
+      (i32.add (local.get $x) (i32.const 11))
+    )
+    (local.set $x
+      (call $tunnel (local.get $x)) ;; calls js which calls back into wasm for end_tunnel
+    )
+    (call $sleep)
+    (i32.add (local.get $x) (i32.const 33))
+  )
+  (func $tablefunc (param $y i32) (result i32)
+    (local.set $y
+      (i32.add (local.get $y) (i32.const 10))
+    )
+    (call $sleep)
+    (i32.add (local.get $y) (i32.const 30))
+  )
+  (func "call_indirect" (param $x i32) (param $y i32) (result i32)
+    (local.set $x
+      (i32.add (local.get $x) (i32.const 1))
+    )
+    (call $sleep)
+    (local.set $x
+      (i32.add (local.get $x) (i32.const 3))
+    )
+    (local.set $y
+      (call_indirect (type $ii) (local.get $y) (local.get $x)) ;; call function pointer x + 4, which will be 5
+    )
+    (local.set $y
+      (i32.add (local.get $y) (i32.const 90))
+    )
+    (call $sleep)
+    (i32.add (local.get $y) (i32.const 300)) ;; total is 10+30+90+300=430 + y's original value
+  )
+  (func "if_else" (param $x i32) (param $y i32) (result i32)
+    (if (i32.eq (local.get $x) (i32.const 1))
+      (local.set $y
+        (i32.add (local.get $y) (i32.const 10))
+      )
+      (local.set $y
+        (i32.add (local.get $y) (i32.const 20))
+      )
+    )
+    (if (i32.eq (local.get $x) (i32.const 1))
+      (local.set $y
+        (i32.add (local.get $y) (i32.const 40))
+      )
+      (call $sleep)
+    )
+    (if (i32.eq (local.get $x) (i32.const 1))
+      (call $sleep)
+      (local.set $y
+        (i32.add (local.get $y) (i32.const 90))
+      )
+    )
+    (if (i32.eq (local.get $x) (i32.const 1))
+      (call $sleep)
+      (call $sleep)
+    )
+    (local.set $y
+      (i32.add (local.get $y) (i32.const 160))
+    )
+    (call $sleep)
+    (local.set $y
+      (i32.add (local.get $y) (i32.const 250))
+    )
+    (local.get $y)
+  )
+)
+
diff --git a/test/unit/test_bysyncify.py b/test/unit/test_bysyncify.py
new file mode 100644
index 000000000..5373a4def
--- /dev/null
+++ b/test/unit/test_bysyncify.py
@@ -0,0 +1,20 @@
+import os
+
+from scripts.test.shared import WASM_OPT, NODEJS, run_process
+from utils import BinaryenTestCase
+
+
+class BysyncifyTest(BinaryenTestCase):
+  def test_bysyncify(self):
+    def test(args):
+      print(args)
+      run_process(WASM_OPT + args + [self.input_path('bysyncify.wast'), '--bysyncify', '-o', 'a.wasm'])
+      print('  file size: %d' % os.path.getsize('a.wasm'))
+      run_process([NODEJS, self.input_path('bysyncify.js')])
+
+    test(['-g'])
+    test([])
+    test(['-O1'])
+    test(['--optimize-level=1'])
+    test(['-O3'])
+    test(['-Os', '-g'])