Vacuum unused values (#1918)

Checks if a value is being dropped higher up, like

```
(drop
  (block i32
    (block i32
      (i32.const 1)
    )
  )
)
```
Handling this forces us to be careful in that pass about whether a value is used, and whether the type matters (for example, we can't replace a unary with its child in all cases, if the return value matters).

3 files changed, 305 insertions, 9 deletions

diff --git a/src/passes/Vacuum.cpp b/src/passes/Vacuum.cpp
index f59fb287a..08581a3eb 100644
--- a/src/passes/Vacuum.cpp
+++ b/src/passes/Vacuum.cpp
@@ -23,11 +23,13 @@
 #include <wasm-builder.h>
 #include <ir/block-utils.h>
 #include <ir/effects.h>
+#include <ir/literal-utils.h>
 #include <ir/type-updating.h>
+#include <ir/utils.h>
 
 namespace wasm {
 
-struct Vacuum : public WalkerPass<PostWalker<Vacuum>> {
+struct Vacuum : public WalkerPass<ExpressionStackWalker<Vacuum>> {
   bool isFunctionParallel() override { return true; }
 
   Pass* create() override { return new Vacuum; }
@@ -47,11 +49,21 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> {
     walk(func->body);
   }
 
-  // returns nullptr if curr is dead, curr if it must stay as is, or another node if it can be replaced
-  Expression* optimize(Expression* curr, bool resultUsed) {
-    // an unreachable node must not be changed
-    if (curr->type == unreachable) return curr;
+  // Returns nullptr if curr is dead, curr if it must stay as is, or another node if it can be replaced.
+  // Takes into account:
+  //  * The result may be used or unused.
+  //  * The type may or may not matter (a drop can drop anything, for example).
+  Expression* optimize(Expression* curr, bool resultUsed, bool typeMatters) {
+    auto type = curr->type;
+    // An unreachable node must not be changed.
+    if (type == unreachable) return curr;
+    // We iterate on possible replacements. If a replacement changes the type, stop and go back.
+    auto* prev = curr;
     while (1) {
+      if (typeMatters && curr->type != type) {
+        return prev;
+      }
+      prev = curr;
       switch (curr->_id) {
         case Expression::Id::NopId: return nullptr; // never needed
 
@@ -173,7 +185,22 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> {
     size_t size = list.size();
     for (size_t z = 0; z < size; z++) {
       auto* child = list[z];
-      auto* optimized = optimize(child, z == size - 1 && isConcreteType(curr->type));
+      // The last element may be used.
+      bool used = z == size - 1 &&
+                  isConcreteType(curr->type) &&
+                  ExpressionAnalyzer::isResultUsed(expressionStack, getFunction());
+      auto* optimized = optimize(child, used, true);
+      if (!optimized) {
+        if (isConcreteType(child->type)) {
+          // We can't just skip a final concrete element, even if it isn't used. Instead,
+          // replace it with something that's easy to optimize out (for example, code-folding
+          // can merge out identical zeros at the end of if arms).
+          optimized = LiteralUtils::makeZero(child->type, *getModule());
+        } else if (child->type == unreachable) {
+          // Don't try to optimize out an unreachable child (dce can do that properly).
+          optimized = child;
+        }
+      }
       if (!optimized) {
         typeUpdater.noteRecursiveRemoval(child);
         skip++;
@@ -275,7 +302,7 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> {
 
   void visitDrop(Drop* curr) {
     // optimize the dropped value, maybe leaving nothing
-    curr->value = optimize(curr->value, false);
+    curr->value = optimize(curr->value, false, false);
     if (curr->value == nullptr) {
       ExpressionManipulator::nop(curr);
       return;
@@ -294,7 +321,7 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> {
       // block has an unreachable element in the middle, making the block unreachable
       // despite later elements and in particular the last
       if (isConcreteType(last->type) && block->type == last->type) {
-        last = optimize(last, false);
+        last = optimize(last, false, false);
         if (!last) {
           // we may be able to remove this, if there are no brs
           bool canPop = true;
@@ -343,7 +370,7 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> {
   }
 
   void visitFunction(Function* curr) {
-    auto* optimized = optimize(curr->body, curr->result != none);
+    auto* optimized = optimize(curr->body, curr->result != none, true);
     if (optimized) {
       curr->body = optimized;
     } else {
diff --git a/test/passes/vacuum.txt b/test/passes/vacuum.txt
index 3b2c4bfbb..9f106cd89 100644
--- a/test/passes/vacuum.txt
+++ b/test/passes/vacuum.txt
@@ -305,3 +305,138 @@
   (nop)
  )
 )
+(module
+ (type $0 (func (param i64)))
+ (type $1 (func (param f32 i32) (result i32)))
+ (func $0 (; 0 ;) (type $0) (param $0 i64)
+  (nop)
+ )
+ (func $1 (; 1 ;) (type $1) (param $0 f32) (param $1 i32) (result i32)
+  (drop
+   (block $label$2 (result i64)
+    (call $0
+     (br_if $label$2
+      (i64.const -137438953472)
+      (i32.const 1)
+     )
+    )
+    (unreachable)
+   )
+  )
+  (unreachable)
+ )
+)
+(module
+ (type $0 (func (param i32) (result i32)))
+ (type $1 (func (param i32 i32 i32)))
+ (global $global$1 (mut i32) (i32.const 0))
+ (export "compress" (func $3))
+ (func $_deflate (; 0 ;) (type $0) (param $0 i32) (result i32)
+  (call $_deflate
+   (local.get $0)
+  )
+ )
+ (func $_deflateInit2_ (; 1 ;) (type $0) (param $0 i32) (result i32)
+  (call $_deflateInit2_
+   (local.get $0)
+  )
+ )
+ (func $_deflateEnd (; 2 ;) (type $0) (param $0 i32) (result i32)
+  (call $_deflateEnd
+   (local.get $0)
+  )
+ )
+ (func $3 (; 3 ;) (type $1) (param $0 i32) (param $1 i32) (param $2 i32)
+  (local $3 i32)
+  (local.set $3
+   (global.get $global$1)
+  )
+  (global.set $global$1
+   (i32.sub
+    (global.get $global$1)
+    (i32.const -64)
+   )
+  )
+  (i32.store
+   (local.get $3)
+   (local.get $2)
+  )
+  (i32.store offset=4
+   (local.get $3)
+   (i32.const 100000)
+  )
+  (i32.store offset=12
+   (local.get $3)
+   (local.get $0)
+  )
+  (i32.store offset=16
+   (local.get $3)
+   (i32.load
+    (local.get $1)
+   )
+  )
+  (i32.store offset=32
+   (local.get $3)
+   (i32.const 0)
+  )
+  (i32.store offset=36
+   (local.get $3)
+   (i32.const 0)
+  )
+  (i32.store offset=40
+   (local.get $3)
+   (i32.const 0)
+  )
+  (if
+   (call $_deflateInit2_
+    (local.get $3)
+   )
+   (block $block
+    (global.set $global$1
+     (local.get $3)
+    )
+    (return)
+   )
+  )
+  (drop
+   (if (result i32)
+    (i32.eq
+     (local.tee $0
+      (call $_deflate
+       (local.get $3)
+      )
+     )
+     (i32.const 1)
+    )
+    (block $block1 (result i32)
+     (i32.store
+      (local.get $1)
+      (i32.load offset=20
+       (local.get $3)
+      )
+     )
+     (local.set $0
+      (call $_deflateEnd
+       (local.get $3)
+      )
+     )
+     (global.set $global$1
+      (local.get $3)
+     )
+     (i32.const 0)
+    )
+    (block $block2 (result i32)
+     (drop
+      (call $_deflateEnd
+       (local.get $3)
+      )
+     )
+     (global.set $global$1
+      (local.get $3)
+     )
+     (i32.const 0)
+    )
+   )
+  )
+ )
+)
diff --git a/test/passes/vacuum.wast b/test/passes/vacuum.wast
index a2dc58950..0e15c76ad 100644
--- a/test/passes/vacuum.wast
+++ b/test/passes/vacuum.wast
@@ -660,3 +660,137 @@
    )
   )
 )
+(module ;; a child with a different type, cannot simply replace the parent with it
+ (type $0 (func (param i64)))
+ (type $1 (func (param f32 i32) (result i32)))
+ (func $0 (; 0 ;) (type $0) (param $0 i64)
+  (nop)
+ )
+ (func $1 (; 1 ;) (type $1) (param $0 f32) (param $1 i32) (result i32)
+  (drop
+   (block $label$1 (result i32)
+    (i32.wrap_i64
+     (block $label$2 (result i64)
+      (call $0
+       (br_if $label$2
+        (i64.const -137438953472)
+        (i32.const 1)
+       )
+      )
+      (unreachable)
+     )
+    )
+   )
+  )
+  (unreachable)
+ )
+)
+(module ;; vacuum away a drop on an if where both arms can be vacuumed
+ (global $global$1 (mut i32) (i32.const 0))
+ (func $_deflate (param i32) (result i32)
+  (call $_deflate (local.get $0))
+ )
+ (func $_deflateInit2_ (param i32) (result i32)
+  (call $_deflateInit2_ (local.get $0))
+ )
+ (func $_deflateEnd (param i32) (result i32)
+  (call $_deflateEnd (local.get $0))
+ )
+ (func "compress" (param $0 i32) (param $1 i32) (param $2 i32)
+  (local $3 i32)
+  (local.set $3
+   (global.get $global$1)
+  )
+  (global.set $global$1
+   (i32.sub
+    (global.get $global$1)
+    (i32.const -64)
+   )
+  )
+  (i32.store
+   (local.get $3)
+   (local.get $2)
+  )
+  (i32.store offset=4
+   (local.get $3)
+   (i32.const 100000)
+  )
+  (i32.store offset=12
+   (local.get $3)
+   (local.get $0)
+  )
+  (i32.store offset=16
+   (local.get $3)
+   (i32.load
+    (local.get $1)
+   )
+  )
+  (i32.store offset=32
+   (local.get $3)
+   (i32.const 0)
+  )
+  (i32.store offset=36
+   (local.get $3)
+   (i32.const 0)
+  )
+  (i32.store offset=40
+   (local.get $3)
+   (i32.const 0)
+  )
+  (if
+   (call $_deflateInit2_
+    (local.get $3)
+   )
+   (block
+    (global.set $global$1
+     (local.get $3)
+    )
+    (return)
+   )
+  )
+  (drop
+   (if (result i32)
+    (i32.eq
+     (local.tee $0
+      (call $_deflate
+       (local.get $3)
+      )
+     )
+     (i32.const 1)
+    )
+    (block (result i32)
+     (i32.store
+      (local.get $1)
+      (i32.load offset=20
+       (local.get $3)
+      )
+     )
+     (local.set $0
+      (call $_deflateEnd
+       (local.get $3)
+      )
+     )
+     (global.set $global$1
+      (local.get $3)
+     )
+     (local.get $0)
+    )
+    (block (result i32)
+     (drop
+      (call $_deflateEnd
+       (local.get $3)
+      )
+     )
+     (global.set $global$1
+      (local.get $3)
+     )
+     (select
+      (local.get $0)
+      (i32.const -5)
+      (local.get $0)
+     )
+    )
+   )
+  )
+ )
+)