Poppify pass (#3541)

Adds a Poppify ("--poppify") pass for converting normal Binaryen IR to Poppy IR.
Like the existing construction of Stacky IR, Poppify depends on the
BinaryenIRWriter to drive the emitting of instructions in correct stack machine
order. As instructions are "emitted," Poppify replaces their children with pops
and collects them in a list. At the end of each scope, Poppify creates a block
containing all the collected instructions for that scope and injects that block
into the enclosing scope. All tuple globals and instructions dealing with tuples
are also expanded to remove all tuples from the program.

The validator currently fails to validate many valid Poppy IR patterns produced
in the tests, but fixing that is left as follow-on work to keep this PR focused
on the Poppify pass itself. For now the tests simply skip validation.

2 files changed, 489 insertions, 0 deletions

diff --git a/test/lit/passes/poppify-globals.wast b/test/lit/passes/poppify-globals.wast
new file mode 100644
index 000000000..ccdb025c0
--- /dev/null
+++ b/test/lit/passes/poppify-globals.wast
@@ -0,0 +1,55 @@
+;; TODO: enable validation
+;; RUN: wasm-opt %s --poppify --no-validation -all -S -o - | filecheck %s
+
+(module
+  ;; CHECK: (global $foo (mut i32) (i32.const 0))
+  (global $foo (mut i32) (i32.const 0))
+
+  ;; CHECK: (global $tuple$1 f64 (f64.const 0))
+  (global $tuple$1 f64 (f64.const 0)) ;; interfering name!
+
+  ;; CHECK: (global $tuple$2 (mut f32) (f32.const 2))
+  ;; CHECK: (global $tuple$1_0 (mut i64) (i64.const 1))
+  ;; CHECK: (global $tuple$0 (mut i32) (global.get $foo))
+  (global $tuple (mut (i32 i64 f32))
+    (tuple.make (global.get $foo) (i64.const 1) (f32.const 2))
+  )
+
+  ;; CHECK: (global $other-tuple$2 f32 (global.get $tuple$2))
+  ;; CHECK: (global $other-tuple$1 i64 (global.get $tuple$1_0))
+  ;; CHECK: (global $other-tuple$0 i32 (global.get $tuple$0))
+  (global $other-tuple (i32 i64 f32) (global.get $tuple))
+
+  ;; CHECK:      (func $global-get-tuple
+  ;; CHECK-NEXT:  (global.get $tuple$0)
+  ;; CHECK-NEXT:  (global.get $tuple$1_0)
+  ;; CHECK-NEXT:  (global.get $tuple$2)
+  ;; CHECK-NEXT: )
+  (func $global-get-tuple (result i32 i64 f32)
+    (global.get $tuple)
+  )
+
+  ;; CHECK:      (func $global-set-tuple
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT:  (i64.const 1)
+  ;; CHECK-NEXT:  (f32.const 2)
+  ;; CHECK-NEXT:  (global.set $tuple$2
+  ;; CHECK-NEXT:   (pop f32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (global.set $tuple$1_0
+  ;; CHECK-NEXT:   (pop i64)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (global.set $tuple$0
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $global-set-tuple
+    (global.set $tuple
+      (tuple.make
+        (i32.const 0)
+        (i64.const 1)
+        (f32.const 2)
+      )
+    )
+  )
+)
diff --git a/test/lit/passes/poppify.wast b/test/lit/passes/poppify.wast
new file mode 100644
index 000000000..1b9ba1fb3
--- /dev/null
+++ b/test/lit/passes/poppify.wast
@@ -0,0 +1,434 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited.
+;; TODO: enable validation
+;; RUN: wasm-opt %s --poppify --no-validation -all -S -o - | filecheck %s
+
+(module
+  (event $e (attr 0) (param i32))
+
+  ;; CHECK:      (func $id (param $x i32) (result i32)
+  ;; CHECK-NEXT:  (local.get $x)
+  ;; CHECK-NEXT: )
+  (func $id (param $x i32) (result i32)
+    (local.get $x)
+  )
+
+  ;; CHECK:      (func $add (param $x i32) (param $y i32) (result i32)
+  ;; CHECK-NEXT:  (local.get $x)
+  ;; CHECK-NEXT:  (local.get $y)
+  ;; CHECK-NEXT:  (i32.add
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $add (param $x i32) (param $y i32) (result i32)
+    (i32.add
+      (local.get $x)
+      (local.get $y)
+    )
+  )
+
+  ;; CHECK:      (func $expr-tree (result i32)
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT:  (i32.const 1)
+  ;; CHECK-NEXT:  (i32.mul
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (i32.const 2)
+  ;; CHECK-NEXT:  (i32.const 3)
+  ;; CHECK-NEXT:  (i32.mul
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (i32.add
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $expr-tree (result i32)
+    (i32.add
+      (i32.mul
+        (i32.const 0)
+        (i32.const 1)
+      )
+      (i32.mul
+        (i32.const 2)
+        (i32.const 3)
+      )
+    )
+  )
+
+  ;; CHECK:      (func $block (result i32)
+  ;; CHECK-NEXT:  (block $block (result i32)
+  ;; CHECK-NEXT:   (nop)
+  ;; CHECK-NEXT:   (i32.const 0)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $block (result i32)
+    (block i32
+      (nop)
+      (i32.const 0)
+    )
+  )
+
+  ;; CHECK:      (func $nested (result i32)
+  ;; CHECK-NEXT:  (block $block (result i32)
+  ;; CHECK-NEXT:   (block $block0 (result i32)
+  ;; CHECK-NEXT:    (block $block1 (result i32)
+  ;; CHECK-NEXT:     (i32.const 0)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $nested (result i32)
+    (block i32
+      (block i32
+        (block i32
+          (i32.const 0)
+        )
+      )
+    )
+  )
+
+  ;; CHECK:      (func $child-blocks (result i32)
+  ;; CHECK-NEXT:  (block $block (result i32)
+  ;; CHECK-NEXT:   (block $block2 (result i32)
+  ;; CHECK-NEXT:    (i32.const 0)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (block $block3 (result i32)
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (i32.add
+  ;; CHECK-NEXT:    (pop i32)
+  ;; CHECK-NEXT:    (pop i32)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $child-blocks (result i32)
+    (block (result i32)
+      (i32.add
+        (block (result i32)
+          (i32.const 0)
+        )
+        (block (result i32)
+          (i32.const 1)
+        )
+      )
+    )
+  )
+
+  ;; CHECK:      (func $block-br (result i32)
+  ;; CHECK-NEXT:  (block $l (result i32)
+  ;; CHECK-NEXT:   (nop)
+  ;; CHECK-NEXT:   (i32.const 0)
+  ;; CHECK-NEXT:   (br $l
+  ;; CHECK-NEXT:    (pop i32)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $block-br (result i32)
+    (block $l i32
+      (nop)
+      (br $l
+        (i32.const 0)
+      )
+    )
+  )
+
+  ;; CHECK:      (func $loop
+  ;; CHECK-NEXT:  (loop $l
+  ;; CHECK-NEXT:   (br $l)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  (func $loop
+    (loop $l
+      (br $l)
+    )
+  )
+
+  ;; CHECK:      (func $if
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT:  (if
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:   (nop)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $if
+    (if
+      (i32.const 0)
+      (nop)
+    )
+  )
+
+  ;; CHECK:      (func $if-else (result i32)
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT:  (if (result i32)
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:   (i32.const 2)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $if-else (result i32)
+    (if i32
+      (i32.const 0)
+      (i32.const 1)
+      (i32.const 2)
+    )
+  )
+
+  ;; CHECK:      (func $try-catch (result i32)
+  ;; CHECK-NEXT:  (try (result i32)
+  ;; CHECK-NEXT:   (do
+  ;; CHECK-NEXT:    (i32.const 0)
+  ;; CHECK-NEXT:    (throw $e
+  ;; CHECK-NEXT:     (pop i32)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (catch $e
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (catch_all
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $try-catch (result i32)
+    (try i32
+      (do
+        (throw $e
+          (i32.const 0)
+        )
+      )
+      (catch $e
+        (pop i32)
+      )
+      (catch_all
+        (i32.const 1)
+      )
+    )
+  )
+
+  ;; CHECK:      (func $tuple (result i32 i64)
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT:  (i64.const 1)
+  ;; CHECK-NEXT: )
+  (func $tuple (result i32 i64)
+    (tuple.make
+      (i32.const 0)
+      (i64.const 1)
+    )
+  )
+
+  ;; CHECK:      (func $extract-first (result i32)
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT:  (i64.const 1)
+  ;; CHECK-NEXT:  (f32.const 2)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (pop f32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (pop i64)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $extract-first (result i32)
+    (tuple.extract 0
+      (tuple.make
+        (i32.const 0)
+        (i64.const 1)
+        (f32.const 2)
+      )
+    )
+  )
+
+  ;; CHECK:      (func $extract-middle (result i64)
+  ;; CHECK-NEXT:  (local $0 i64)
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT:  (i64.const 1)
+  ;; CHECK-NEXT:  (f32.const 2)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (pop f32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (local.set $0
+  ;; CHECK-NEXT:   (pop i64)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (local.get $0)
+  ;; CHECK-NEXT: )
+  (func $extract-middle (result i64)
+    (tuple.extract 1
+      (tuple.make
+        (i32.const 0)
+        (i64.const 1)
+        (f32.const 2)
+      )
+    )
+  )
+
+  ;; CHECK:      (func $extract-last (result f32)
+  ;; CHECK-NEXT:  (local $0 f32)
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT:  (i64.const 1)
+  ;; CHECK-NEXT:  (f32.const 2)
+  ;; CHECK-NEXT:  (local.set $0
+  ;; CHECK-NEXT:   (pop f32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (pop i64)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (local.get $0)
+  ;; CHECK-NEXT: )
+  (func $extract-last (result f32)
+    (tuple.extract 2
+      (tuple.make
+        (i32.const 0)
+        (i64.const 1)
+        (f32.const 2)
+      )
+    )
+  )
+
+  ;; CHECK:      (func $drop
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $drop
+    (drop
+      (i32.const 0)
+    )
+  )
+
+  ;; CHECK:      (func $drop-tuple
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT:  (i64.const 1)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (pop i64)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $drop-tuple
+    (drop
+      (tuple.make
+        (i32.const 0)
+        (i64.const 1)
+      )
+    )
+  )
+
+  ;; CHECK:      (func $local-get-tuple (result i32 i64)
+  ;; CHECK-NEXT:  (local $x (i32 i64))
+  ;; CHECK-NEXT:  (local $1 i32)
+  ;; CHECK-NEXT:  (local $2 i64)
+  ;; CHECK-NEXT:  (local.get $1)
+  ;; CHECK-NEXT:  (local.get $2)
+  ;; CHECK-NEXT: )
+  (func $local-get-tuple (result i32 i64)
+    (local $x (i32 i64))
+    (local.get $x)
+  )
+
+  ;; CHECK:      (func $local-set
+  ;; CHECK-NEXT:  (local $x i32)
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT:  (local.set $x
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $local-set
+    (local $x i32)
+    (local.set $x
+      (i32.const 0)
+    )
+  )
+
+  ;; CHECK:      (func $local-set-tuple
+  ;; CHECK-NEXT:  (local $x (i32 i64))
+  ;; CHECK-NEXT:  (local $1 i32)
+  ;; CHECK-NEXT:  (local $2 i64)
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT:  (i64.const 1)
+  ;; CHECK-NEXT:  (local.set $2
+  ;; CHECK-NEXT:   (pop i64)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (local.set $1
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $local-set-tuple
+    (local $x (i32 i64))
+    (local.set $x
+      (tuple.make
+        (i32.const 0)
+        (i64.const 1)
+      )
+    )
+  )
+
+  ;; CHECK:      (func $local-tee-tuple (result i32 i64)
+  ;; CHECK-NEXT:  (local $x (i32 i64))
+  ;; CHECK-NEXT:  (local $1 i32)
+  ;; CHECK-NEXT:  (local $2 i64)
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT:  (i64.const 1)
+  ;; CHECK-NEXT:  (local.set $2
+  ;; CHECK-NEXT:   (pop i64)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (local.tee $1
+  ;; CHECK-NEXT:   (pop i32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (local.get $2)
+  ;; CHECK-NEXT: )
+  (func $local-tee-tuple (result i32 i64)
+    (local $x (i32 i64))
+    (local.tee $x
+      (tuple.make
+        (i32.const 0)
+        (i64.const 1)
+      )
+    )
+  )
+
+  ;; CHECK:      (func $break-tuple (result i32 i64)
+  ;; CHECK-NEXT:  (block $l (result i32 i64)
+  ;; CHECK-NEXT:   (i32.const 0)
+  ;; CHECK-NEXT:   (i64.const 1)
+  ;; CHECK-NEXT:   (br $l
+  ;; CHECK-NEXT:    (pop i32 i64)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $break-tuple (result i32 i64)
+    (block $l (result i32 i64)
+      (br $l
+        (tuple.make
+          (i32.const 0)
+          (i64.const 1)
+        )
+      )
+    )
+  )
+
+  ;; CHECK:      (func $return-tuple (result i32 i64)
+  ;; CHECK-NEXT:  (i32.const 0)
+  ;; CHECK-NEXT:  (i64.const 1)
+  ;; CHECK-NEXT:  (return
+  ;; CHECK-NEXT:   (pop i32 i64)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $return-tuple (result i32 i64)
+    (return
+      (tuple.make
+        (i32.const 0)
+        (i64.const 1)
+      )
+    )
+  )
+)