[ctor-eval] Partial evaluation (#4438)

This lets us eval part of a function but not all, which is necessary to handle
real-world things like __wasm_call_ctors in LLVM output, as that is the
single ctor that is exported and it has calls to the actual ctors.

To do so, we look for a toplevel block and execute its items one by one, in
a FunctionScope. If we stop in the middle, then we are performing a partial
eval. In that case, we only remove the parts of the function that we removed,
and we also serialize the locals whose values we read from the
FunctionScope.

For example, consider this:

function foo() {
  return 10;
}

function __wasm_call_ctors() {
  var x;
  x = foo();
  x++;
  // We stop evalling here.
  import1();
  import2(x);
}

We can eval x = foo() and x++, but we must stop evalling when
we reach the first of those imports. The partially-evalled function
then looks like this:

function __wasm_call_ctors() {
  var x;
  x = 11;
  import1();
  import2(x);
}

That is, we evalled two lines of executing code and simply removed
them, and then we wrote out the value of the local at that point, and then
the rest of the code in the function is as it used to be.

20 files changed, 246 insertions, 23 deletions

diff --git a/test/ctor-eval/no_partial.wast b/test/ctor-eval/no_partial.wast
deleted file mode 100644
index 18ef177b7..000000000
--- a/test/ctor-eval/no_partial.wast
+++ /dev/null
@@ -1,10 +0,0 @@
-(module
-  (memory 256 256)
-  (data (i32.const 10) "waka waka waka waka waka")
-  (export "test1" $test1)
-  (func $test1
-    (i32.store8 (i32.const 12) (i32.const 115)) ;; a safe store, should alter memory
-    (unreachable)
-    (i32.store8 (i32.const 13) (i32.const 114)) ;; a safe store, should alter memory, but we trapped already, and so must roll back the first one too
-  )
-)
diff --git a/test/ctor-eval/no_partial.wast.out b/test/ctor-eval/no_partial.wast.out
deleted file mode 100644
index 0e941f3ac..000000000
--- a/test/ctor-eval/no_partial.wast.out
+++ /dev/null
@@ -1,13 +0,0 @@
-(module
- (type $none_=>_none (func))
- (memory $0 256 256)
- (data (i32.const 10) "waka waka waka waka waka")
- (export "test1" (func $test1))
- (func $test1
-  (i32.store8
-   (i32.const 12)
-   (i32.const 115)
-  )
-  (unreachable)
- )
-)
diff --git a/test/ctor-eval/params.wast b/test/ctor-eval/params.wast
new file mode 100644
index 000000000..fb70debe5
--- /dev/null
+++ b/test/ctor-eval/params.wast
@@ -0,0 +1,7 @@
+(module
+  (func "test1" (param $x i32)
+    ;; The presence of params stops us from evalling this function (at least
+    ;; for now).
+    (nop)
+  )
+)
diff --git a/test/ctor-eval/no_partial.wast.ctors b/test/ctor-eval/params.wast.ctors
index a5bce3fd2..a5bce3fd2 100644
--- a/test/ctor-eval/no_partial.wast.ctors
+++ b/test/ctor-eval/params.wast.ctors
diff --git a/test/ctor-eval/params.wast.out b/test/ctor-eval/params.wast.out
new file mode 100644
index 000000000..6e52bea89
--- /dev/null
+++ b/test/ctor-eval/params.wast.out
@@ -0,0 +1,7 @@
+(module
+ (type $i32_=>_none (func (param i32)))
+ (export "test1" (func $0))
+ (func $0 (param $x i32)
+  (nop)
+ )
+)
diff --git a/test/ctor-eval/partial-locals-tee.wast b/test/ctor-eval/partial-locals-tee.wast
new file mode 100644
index 000000000..37dac176a
--- /dev/null
+++ b/test/ctor-eval/partial-locals-tee.wast
@@ -0,0 +1,38 @@
+(module
+  (import "import" "import" (func $import (param i32 i32)))
+
+  (memory 256 256)
+  (data (i32.const 10) "_________________")
+
+  (export "test1" $test1)
+
+  (func $test1
+    (local $temp i32)
+
+    ;; Increment $temp from 0 to 1, which we can eval.
+    (local.set $temp
+      (i32.add
+        (local.get $temp)
+        (i32.const 1)
+      )
+    )
+
+    ;; A safe store that will be evalled and alter memory.
+    (i32.store8 (i32.const 12) (i32.const 115))
+
+    ;; A call to an import, which prevents evalling. We will stop here. The
+    ;; 'tee' instruction should *not* have any effect, that is, we should not
+    ;; partially eval this line in the block - we should eval none of it.
+    ;; TODO: We should support such partial line evalling, with more careful
+    ;;       management of locals.
+    (call $import
+      (local.get $temp) ;; The value sent here should be '1'.
+      (local.tee $temp
+        (i32.const 50)
+      )
+    )
+
+    ;; A safe store that we never reach
+    (i32.store8 (i32.const 13) (i32.const 115))
+  )
+)
diff --git a/test/ctor-eval/partial-locals-tee.wast.ctors b/test/ctor-eval/partial-locals-tee.wast.ctors
new file mode 100644
index 000000000..a5bce3fd2
--- /dev/null
+++ b/test/ctor-eval/partial-locals-tee.wast.ctors
@@ -0,0 +1 @@
+test1
diff --git a/test/ctor-eval/partial-locals-tee.wast.out b/test/ctor-eval/partial-locals-tee.wast.out
new file mode 100644
index 000000000..cb2653198
--- /dev/null
+++ b/test/ctor-eval/partial-locals-tee.wast.out
@@ -0,0 +1,18 @@
+(module
+ (type $i32_i32_=>_none (func (param i32 i32)))
+ (type $none_=>_none (func))
+ (import "import" "import" (func $import (param i32 i32)))
+ (memory $0 256 256)
+ (data (i32.const 10) "__s______________")
+ (export "test1" (func $test1_0))
+ (func $test1_0
+  (call $import
+   (i32.const 1)
+   (i32.const 50)
+  )
+  (i32.store8
+   (i32.const 13)
+   (i32.const 115)
+  )
+ )
+)
diff --git a/test/ctor-eval/partial-locals.wast b/test/ctor-eval/partial-locals.wast
new file mode 100644
index 000000000..b0304c2ea
--- /dev/null
+++ b/test/ctor-eval/partial-locals.wast
@@ -0,0 +1,43 @@
+(module
+  (import "import" "import" (func $import))
+
+  (memory 256 256)
+  (data (i32.const 10) "_________________")
+
+  (export "test1" $test1)
+
+  (global $sp (mut i32) (i32.const 100))
+
+  (func $test1
+    (local $temp-sp i32)
+
+    ;; Save and bump the stack pointer.
+    (local.set $temp-sp
+      (global.get $sp)
+    )
+    (global.set $sp
+      (i32.add
+        (global.get $sp)
+        (i32.const 4)
+      )
+    )
+
+    ;; A safe store, should alter memory
+    (i32.store8 (i32.const 12) (i32.const 115))
+
+    ;; A call to an import, which prevents evalling. We will stop here. After
+    ;; optimization we'll serialize the value of $temp-sp so that when the
+    ;; code is run later it runs properly.
+    ;;
+    ;; (Also, the global $sp will contain 104, the value after the bump.)
+    (call $import)
+
+    ;; A safe store that we never reach
+    (i32.store8 (i32.const 13) (i32.const 115))
+
+    ;; Restore the stack pointer.
+    (global.set $sp
+      (local.get $temp-sp)
+    )
+  )
+)
diff --git a/test/ctor-eval/partial-locals.wast.ctors b/test/ctor-eval/partial-locals.wast.ctors
new file mode 100644
index 000000000..a5bce3fd2
--- /dev/null
+++ b/test/ctor-eval/partial-locals.wast.ctors
@@ -0,0 +1 @@
+test1
diff --git a/test/ctor-eval/partial-locals.wast.out b/test/ctor-eval/partial-locals.wast.out
new file mode 100644
index 000000000..14f102b69
--- /dev/null
+++ b/test/ctor-eval/partial-locals.wast.out
@@ -0,0 +1,22 @@
+(module
+ (type $none_=>_none (func))
+ (import "import" "import" (func $import))
+ (global $sp (mut i32) (i32.const 104))
+ (memory $0 256 256)
+ (data (i32.const 10) "__s______________")
+ (export "test1" (func $test1_0))
+ (func $test1_0
+  (local $0 i32)
+  (local.set $0
+   (i32.const 100)
+  )
+  (call $import)
+  (i32.store8
+   (i32.const 13)
+   (i32.const 115)
+  )
+  (global.set $sp
+   (local.get $0)
+  )
+ )
+)
diff --git a/test/ctor-eval/partial-return.wast b/test/ctor-eval/partial-return.wast
new file mode 100644
index 000000000..8ca6eee75
--- /dev/null
+++ b/test/ctor-eval/partial-return.wast
@@ -0,0 +1,31 @@
+(module
+  (import "import" "import" (func $import))
+
+  (memory 256 256)
+  (data (i32.const 10) "_________________")
+
+  (export "test1" $test1)
+  (export "memory" (memory $0))
+
+  (func $test1
+    ;; A safe store, should alter memory
+    (i32.store8 (i32.const 12) (i32.const 115))
+
+    ;; Load the value we just saved, and return because of its value. (This way
+    ;; we could not see the return must execute without ctor-eval. At least, not
+    ;; without store-load forwarding.)
+    (if
+      (i32.load8_u
+        (i32.const 12)
+      )
+      (return)
+    )
+
+    ;; This is unsafe to call, and would stop evalling here. But we exit due to
+    ;; the return before anyhow, so it doesn't matter.
+    (call $import)
+
+    ;; A safe store that we never reach because of the return before us.
+    (i32.store8 (i32.const 13) (i32.const 115))
+  )
+)
diff --git a/test/ctor-eval/partial-return.wast.ctors b/test/ctor-eval/partial-return.wast.ctors
new file mode 100644
index 000000000..a5bce3fd2
--- /dev/null
+++ b/test/ctor-eval/partial-return.wast.ctors
@@ -0,0 +1 @@
+test1
diff --git a/test/ctor-eval/partial-return.wast.out b/test/ctor-eval/partial-return.wast.out
new file mode 100644
index 000000000..572a93bb0
--- /dev/null
+++ b/test/ctor-eval/partial-return.wast.out
@@ -0,0 +1,5 @@
+(module
+ (memory $0 256 256)
+ (data (i32.const 10) "__s______________")
+ (export "memory" (memory $0))
+)
diff --git a/test/ctor-eval/partial.wast b/test/ctor-eval/partial.wast
new file mode 100644
index 000000000..bbff880e7
--- /dev/null
+++ b/test/ctor-eval/partial.wast
@@ -0,0 +1,30 @@
+(module
+  (import "import" "import" (func $import))
+
+  (memory 256 256)
+  (data (i32.const 10) "_________________")
+
+  (export "test1" $test1)
+
+  ;; Use the function in an additional export. We should still get the same
+  ;; results if we call this one, so it should point to identical contents as
+  ;; earlier
+  (export "keepalive" $test1)
+
+  (func $test1
+    ;; A safe store, should alter memory
+    (i32.store8 (i32.const 12) (i32.const 115))
+
+    ;; A call to an import, which prevents evalling.
+    (call $import)
+
+    ;; Another safe store, but the import call before us will stop our evalling.
+    ;; As a result we will only partially eval this function, applying only
+    ;; the first store.
+    ;;
+    ;; After optimization, the test1 export will point to a function that does
+    ;; not have the first store anymore. It will contain just the call to the
+    ;; import and then this second store.
+    (i32.store8 (i32.const 13) (i32.const 114))
+  )
+)
diff --git a/test/ctor-eval/partial.wast.ctors b/test/ctor-eval/partial.wast.ctors
new file mode 100644
index 000000000..a5bce3fd2
--- /dev/null
+++ b/test/ctor-eval/partial.wast.ctors
@@ -0,0 +1 @@
+test1
diff --git a/test/ctor-eval/partial.wast.out b/test/ctor-eval/partial.wast.out
new file mode 100644
index 000000000..4596a16a3
--- /dev/null
+++ b/test/ctor-eval/partial.wast.out
@@ -0,0 +1,26 @@
+(module
+ (type $none_=>_none (func))
+ (import "import" "import" (func $import))
+ (memory $0 256 256)
+ (data (i32.const 10) "__s______________")
+ (export "test1" (func $test1_0))
+ (export "keepalive" (func $test1))
+ (func $test1
+  (i32.store8
+   (i32.const 12)
+   (i32.const 115)
+  )
+  (call $import)
+  (i32.store8
+   (i32.const 13)
+   (i32.const 114)
+  )
+ )
+ (func $test1_0
+  (call $import)
+  (i32.store8
+   (i32.const 13)
+   (i32.const 114)
+  )
+ )
+)
diff --git a/test/ctor-eval/results.wast b/test/ctor-eval/results.wast
new file mode 100644
index 000000000..83fc245fe
--- /dev/null
+++ b/test/ctor-eval/results.wast
@@ -0,0 +1,7 @@
+(module
+  (func "test1" (result i32)
+    ;; The presence of a result stops us from evalling this function (at least
+    ;; for now).
+    (i32.const 42)
+  )
+)
diff --git a/test/ctor-eval/results.wast.ctors b/test/ctor-eval/results.wast.ctors
new file mode 100644
index 000000000..a5bce3fd2
--- /dev/null
+++ b/test/ctor-eval/results.wast.ctors
@@ -0,0 +1 @@
+test1
diff --git a/test/ctor-eval/results.wast.out b/test/ctor-eval/results.wast.out
new file mode 100644
index 000000000..b9dc2cf57
--- /dev/null
+++ b/test/ctor-eval/results.wast.out
@@ -0,0 +1,7 @@
+(module
+ (type $none_=>_i32 (func (result i32)))
+ (export "test1" (func $0))
+ (func $0 (result i32)
+  (i32.const 42)
+ )
+)