Merge pull request #710 from WebAssembly/autodrop-fix

Autodrop fixes

15 files changed, 390 insertions, 114 deletions

diff --git a/src/asm2wasm.h b/src/asm2wasm.h
index 1c528d7f3..e926e381f 100644
--- a/src/asm2wasm.h
+++ b/src/asm2wasm.h
@@ -797,13 +797,17 @@ void Asm2WasmBuilder::processAsm(Ref ast) {
           switch (curr->type) {
             case i32: replaceCurrent(parent->builder.makeUnary(TruncSFloat64ToInt32, curr)); break;
             case f32: replaceCurrent(parent->builder.makeUnary(DemoteFloat64, curr)); break;
-            case none: replaceCurrent(parent->builder.makeDrop(curr)); break;
+            case none: {
+              // this function returns a value, but we are not using it, so it must be dropped.
+              // autodrop will do that for us.
+              break;
+            }
             default: WASM_UNREACHABLE();
           }
         } else {
           assert(curr->type == none);
           // we don't want a return value here, but the import does provide one
-          replaceCurrent(parent->builder.makeDrop(curr));
+          // autodrop will do that for us.
         }
         curr->type = importResult;
       }
diff --git a/src/ast_utils.h b/src/ast_utils.h
index ff5d93e02..9741faa25 100644
--- a/src/ast_utils.h
+++ b/src/ast_utils.h
@@ -422,6 +422,32 @@ struct ExpressionAnalyzer {
     return func->result != none;
   }
 
+  // Checks if a value is dropped.
+  static bool isResultDropped(std::vector<Expression*> stack) {
+    for (int i = int(stack.size()) - 2; i >= 0; i--) {
+      auto* curr = stack[i];
+      auto* above = stack[i + 1];
+      if (curr->is<Block>()) {
+        auto* block = curr->cast<Block>();
+        for (size_t j = 0; j < block->list.size() - 1; j++) {
+          if (block->list[j] == above) return false;
+        }
+        assert(block->list.back() == above);
+        // continue down
+      } else if (curr->is<If>()) {
+        auto* iff = curr->cast<If>();
+        if (above == iff->condition) return false;
+        if (!iff->ifFalse) return false;
+        assert(above == iff->ifTrue || above == iff->ifFalse);
+        // continue down
+      } else {
+        if (curr->is<Drop>()) return true; // dropped
+        return false; // all other node types use the result
+      }
+    }
+    return false;
+  }
+
   // Checks if a break is a simple - no condition, no value, just a plain branching
   static bool isSimple(Break* curr) {
     return !curr->condition && !curr->value;
@@ -856,6 +882,34 @@ struct ExpressionAnalyzer {
   }
 };
 
+// Finalizes a node
+
+struct ReFinalize : public WalkerPass<PostWalker<ReFinalize, Visitor<ReFinalize>>> {
+  void visitBlock(Block *curr) { curr->finalize(); }
+  void visitIf(If *curr) { curr->finalize(); }
+  void visitLoop(Loop *curr) { curr->finalize(); }
+  void visitBreak(Break *curr) { curr->finalize(); }
+  void visitSwitch(Switch *curr) { curr->finalize(); }
+  void visitCall(Call *curr) { curr->finalize(); }
+  void visitCallImport(CallImport *curr) { curr->finalize(); }
+  void visitCallIndirect(CallIndirect *curr) { curr->finalize(); }
+  void visitGetLocal(GetLocal *curr) { curr->finalize(); }
+  void visitSetLocal(SetLocal *curr) { curr->finalize(); }
+  void visitGetGlobal(GetGlobal *curr) { curr->finalize(); }
+  void visitSetGlobal(SetGlobal *curr) { curr->finalize(); }
+  void visitLoad(Load *curr) { curr->finalize(); }
+  void visitStore(Store *curr) { curr->finalize(); }
+  void visitConst(Const *curr) { curr->finalize(); }
+  void visitUnary(Unary *curr) { curr->finalize(); }
+  void visitBinary(Binary *curr) { curr->finalize(); }
+  void visitSelect(Select *curr) { curr->finalize(); }
+  void visitDrop(Drop *curr) { curr->finalize(); }
+  void visitReturn(Return *curr) { curr->finalize(); }
+  void visitHost(Host *curr) { curr->finalize(); }
+  void visitNop(Nop *curr) { curr->finalize(); }
+  void visitUnreachable(Unreachable *curr) { curr->finalize(); }
+};
+
 // Adds drop() operations where necessary. This lets you not worry about adding drop when
 // generating code.
 struct AutoDrop : public WalkerPass<ExpressionStackWalker<AutoDrop, Visitor<AutoDrop>>> {
@@ -863,6 +917,26 @@ struct AutoDrop : public WalkerPass<ExpressionStackWalker<AutoDrop, Visitor<Auto
 
   Pass* create() override { return new AutoDrop; }
 
+  bool maybeDrop(Expression*& child) {
+    bool acted = false;
+    if (isConcreteWasmType(child->type)) {
+      expressionStack.push_back(child);
+      if (!ExpressionAnalyzer::isResultUsed(expressionStack, getFunction()) && !ExpressionAnalyzer::isResultDropped(expressionStack)) {
+        child = Builder(*getModule()).makeDrop(child);
+        acted = true;
+      }
+      expressionStack.pop_back();
+    }
+    return acted;
+  }
+
+  void reFinalize() {
+    for (int i = int(expressionStack.size()) - 1; i >= 0; i--) {
+      auto* curr = expressionStack[i];
+      ReFinalize().visit(curr);
+    }
+  }
+
   void visitBlock(Block* curr) {
     if (curr->list.size() == 0) return;
     for (Index i = 0; i < curr->list.size() - 1; i++) {
@@ -871,31 +945,21 @@ struct AutoDrop : public WalkerPass<ExpressionStackWalker<AutoDrop, Visitor<Auto
         curr->list[i] = Builder(*getModule()).makeDrop(child);
       }
     }
-    auto* last = curr->list.back();
-    expressionStack.push_back(last);
-    if (isConcreteWasmType(last->type) && !ExpressionAnalyzer::isResultUsed(expressionStack, getFunction())) {
-      curr->list.back() = Builder(*getModule()).makeDrop(last);
+    if (maybeDrop(curr->list.back())) {
+      reFinalize();
+      assert(curr->type == none);
     }
-    expressionStack.pop_back();
-    curr->finalize(); // we may have changed our type
   }
 
   void visitIf(If* curr) {
+    bool acted = false;
+    if (maybeDrop(curr->ifTrue)) acted = true;
     if (curr->ifFalse) {
-      if (!isConcreteWasmType(curr->type)) {
-        // if either side of an if-else not returning a value is concrete, drop it
-        if (isConcreteWasmType(curr->ifTrue->type)) {
-          curr->ifTrue = Builder(*getModule()).makeDrop(curr->ifTrue);
-        }
-        if (isConcreteWasmType(curr->ifFalse->type)) {
-          curr->ifFalse = Builder(*getModule()).makeDrop(curr->ifFalse);
-        }
-      }
-    } else {
-      // if without else does not return a value, so the body must be dropped if it is concrete
-      if (isConcreteWasmType(curr->ifTrue->type)) {
-        curr->ifTrue = Builder(*getModule()).makeDrop(curr->ifTrue);
-      }
+      if (maybeDrop(curr->ifFalse)) acted = true;
+    }
+    if (acted) {
+      reFinalize();
+      assert(curr->type == none);
     }
   }
 
@@ -906,34 +970,6 @@ struct AutoDrop : public WalkerPass<ExpressionStackWalker<AutoDrop, Visitor<Auto
   }
 };
 
-// Finalizes a node
-
-struct ReFinalize : public WalkerPass<PostWalker<ReFinalize, Visitor<ReFinalize>>> {
-  void visitBlock(Block *curr) { curr->finalize(); }
-  void visitIf(If *curr) { curr->finalize(); }
-  void visitLoop(Loop *curr) { curr->finalize(); }
-  void visitBreak(Break *curr) { curr->finalize(); }
-  void visitSwitch(Switch *curr) { curr->finalize(); }
-  void visitCall(Call *curr) { curr->finalize(); }
-  void visitCallImport(CallImport *curr) { curr->finalize(); }
-  void visitCallIndirect(CallIndirect *curr) { curr->finalize(); }
-  void visitGetLocal(GetLocal *curr) { curr->finalize(); }
-  void visitSetLocal(SetLocal *curr) { curr->finalize(); }
-  void visitGetGlobal(GetGlobal *curr) { curr->finalize(); }
-  void visitSetGlobal(SetGlobal *curr) { curr->finalize(); }
-  void visitLoad(Load *curr) { curr->finalize(); }
-  void visitStore(Store *curr) { curr->finalize(); }
-  void visitConst(Const *curr) { curr->finalize(); }
-  void visitUnary(Unary *curr) { curr->finalize(); }
-  void visitBinary(Binary *curr) { curr->finalize(); }
-  void visitSelect(Select *curr) { curr->finalize(); }
-  void visitDrop(Drop *curr) { curr->finalize(); }
-  void visitReturn(Return *curr) { curr->finalize(); }
-  void visitHost(Host *curr) { curr->finalize(); }
-  void visitNop(Nop *curr) { curr->finalize(); }
-  void visitUnreachable(Unreachable *curr) { curr->finalize(); }
-};
-
 } // namespace wasm
 
 #endif // wasm_ast_utils_h
diff --git a/src/passes/SimplifyLocals.cpp b/src/passes/SimplifyLocals.cpp
index e032acc77..acc6860be 100644
--- a/src/passes/SimplifyLocals.cpp
+++ b/src/passes/SimplifyLocals.cpp
@@ -351,9 +351,8 @@ struct SimplifyLocals : public WalkerPass<LinearExecutionWalker<SimplifyLocals,
   // optimize set_locals from both sides of an if into a return value
   void optimizeIfReturn(If* iff, Expression** currp, Sinkables& ifTrue) {
     assert(iff->ifFalse);
-    // if this if already has a result that is used, we can't do anything
-    assert(expressionStack.back() == iff);
-    if (ExpressionAnalyzer::isResultUsed(expressionStack, getFunction())) return;
+    // if this if already has a result, we can't do anything
+    if (isConcreteWasmType(iff->type)) return;
     // We now have the sinkables from both sides of the if.
     Sinkables& ifFalse = sinkables;
     Index sharedIndex = -1;
diff --git a/src/passes/Vacuum.cpp b/src/passes/Vacuum.cpp
index 0fdd12dec..03becb04c 100644
--- a/src/passes/Vacuum.cpp
+++ b/src/passes/Vacuum.cpp
@@ -193,9 +193,14 @@ struct Vacuum : public WalkerPass<ExpressionStackWalker<Vacuum, Visitor<Vacuum>>
         curr->ifTrue = curr->ifFalse;
         curr->ifFalse = nullptr;
         curr->condition = Builder(*getModule()).makeUnary(EqZInt32, curr->condition);
+      } else if (curr->ifTrue->is<Drop>() && curr->ifFalse->is<Drop>()) {
+        // instead of dropping both sides, drop the if
+        curr->ifTrue = curr->ifTrue->cast<Drop>()->value;
+        curr->ifFalse = curr->ifFalse->cast<Drop>()->value;
+        curr->finalize();
+        replaceCurrent(Builder(*getModule()).makeDrop(curr));
       }
-    }
-    if (!curr->ifFalse) {
+    } else {
       // no else
       if (curr->ifTrue->is<Nop>()) {
         // no nothing
diff --git a/test/example/c-api-kitchen-sink.txt b/test/example/c-api-kitchen-sink.txt
index 28d7b759b..b7b4821ac 100644
--- a/test/example/c-api-kitchen-sink.txt
+++ b/test/example/c-api-kitchen-sink.txt
@@ -399,10 +399,12 @@ BinaryenFloat64: 4
             )
             (block
             )
-            (drop
-              (if
-                (i32.const 1)
+            (if
+              (i32.const 1)
+              (drop
                 (i32.const 2)
+              )
+              (drop
                 (i32.const 3)
               )
             )
@@ -1992,10 +1994,12 @@ int main() {
             )
             (block
             )
-            (drop
-              (if
-                (i32.const 1)
+            (if
+              (i32.const 1)
+              (drop
                 (i32.const 2)
+              )
+              (drop
                 (i32.const 3)
               )
             )
diff --git a/test/example/c-api-kitchen-sink.txt.txt b/test/example/c-api-kitchen-sink.txt.txt
index f66b714eb..a6f6e0853 100644
--- a/test/example/c-api-kitchen-sink.txt.txt
+++ b/test/example/c-api-kitchen-sink.txt.txt
@@ -394,10 +394,12 @@
             )
             (block
             )
-            (drop
-              (if
-                (i32.const 1)
+            (if
+              (i32.const 1)
+              (drop
                 (i32.const 2)
+              )
+              (drop
                 (i32.const 3)
               )
             )
diff --git a/test/passes/simplify-locals.txt b/test/passes/simplify-locals.txt
index f2aa8d0d9..f12054887 100644
--- a/test/passes/simplify-locals.txt
+++ b/test/passes/simplify-locals.txt
@@ -9,6 +9,7 @@
   (type $6 (func (param i32 i32 i32 i32 i32 i32)))
   (type $FUNCSIG$iii (func (param i32 i32) (result i32)))
   (type $8 (func (param i32 i32)))
+  (type $9 (func (param i32 i32 i32) (result i32)))
   (import "env" "waka" (func $waka))
   (import "env" "waka_int" (func $waka_int (result i32)))
   (import "env" "i64sub" (func $_i64Subtract (param i32 i32 i32 i32) (result i32)))
@@ -735,4 +736,32 @@
     )
     (get_local $a)
   )
+  (func $drop-if-value (type $9) (param $x i32) (param $y i32) (param $z i32) (result i32)
+    (local $temp i32)
+    (drop
+      (if
+        (get_local $x)
+        (block $block53 i32
+          (nop)
+          (set_local $temp
+            (get_local $y)
+          )
+          (get_local $z)
+        )
+        (block $block54 i32
+          (nop)
+          (set_local $temp
+            (get_local $y)
+          )
+          (get_local $z)
+        )
+      )
+    )
+    (drop
+      (get_local $temp)
+    )
+    (return
+      (i32.const 0)
+    )
+  )
 )
diff --git a/test/passes/simplify-locals.wast b/test/passes/simplify-locals.wast
index 4fa345770..a998daf5f 100644
--- a/test/passes/simplify-locals.wast
+++ b/test/passes/simplify-locals.wast
@@ -775,4 +775,30 @@
     )
     (get_local $a)
   )
+  (func $drop-if-value (param $x i32) (param $y i32) (param $z i32) (result i32)
+    (local $temp i32)
+    (drop
+      (if
+        (get_local $x)
+        (block $block53 i32
+          (nop)
+          (set_local $temp
+            (get_local $y)
+          )
+          (get_local $z)
+        )
+        (block $block54 i32
+          (nop)
+          (set_local $temp
+            (get_local $y)
+          )
+          (get_local $z)
+        )
+      )
+    )
+    (drop (get_local $temp))
+    (return
+      (i32.const 0)
+    )
+  )
 )
diff --git a/test/passes/vacuum.txt b/test/passes/vacuum.txt
index c2fb9fc29..6b5d63b2a 100644
--- a/test/passes/vacuum.txt
+++ b/test/passes/vacuum.txt
@@ -207,4 +207,14 @@
   (func $relooperJumpThreading3 (type $0)
     (nop)
   )
+  (func $if2drops (type $3) (result i32)
+    (drop
+      (if
+        (i32.const 1)
+        (call $if2drops)
+        (call $if2drops)
+      )
+    )
+    (i32.const 2)
+  )
 )
diff --git a/test/passes/vacuum.wast b/test/passes/vacuum.wast
index ecc176385..3584df3ff 100644
--- a/test/passes/vacuum.wast
+++ b/test/passes/vacuum.wast
@@ -412,4 +412,16 @@
       )
     )
   )
+  (func $if2drops (result i32)
+    (if
+      (i32.const 1)
+      (drop
+        (call $if2drops)
+      )
+      (drop
+        (call $if2drops)
+      )
+    )
+    (i32.const 2)
+  )
 )
diff --git a/test/unit.asm.js b/test/unit.asm.js
index d4426bd90..7b4b2a96f 100644
--- a/test/unit.asm.js
+++ b/test/unit.asm.js
@@ -572,6 +572,35 @@ function asm(global, env, buffer) {
     return temp | 0;
   }
 
+  function dropIgnoredImportInIf($0,$1,$2) {
+   $0 = $0|0;
+   $1 = $1|0;
+   $2 = $2|0;
+   do {
+    if ($0) {
+     $0 = 1;
+     lb($2 | 0) | 0;
+    } else {
+     break;
+    }
+   } while(0);
+   return;
+  }
+
+  function dropIgnoredImportsInIf($0,$1,$2) {
+   $0 = $0|0;
+   $1 = $1|0;
+   $2 = $2|0;
+   do {
+    if ($0) {
+     lb($1 | 0) | 0;
+    } else {
+     lb($2 | 0) | 0;
+    }
+   } while(0);
+   return;
+  }
+
   var FUNCTION_TABLE_a = [ z, big_negative, z, z ];
   var FUNCTION_TABLE_b = [ w, w, importedDoubles, w ];
   var FUNCTION_TABLE_c = [ z, cneg ];
diff --git a/test/unit.fromasm b/test/unit.fromasm
index fb9f239da..123e087e6 100644
--- a/test/unit.fromasm
+++ b/test/unit.fromasm
@@ -508,13 +508,11 @@
     )
   )
   (func $smallIf
-    (block $do-once$0
-      (if
-        (i32.const 2)
-        (drop
-          (call $lb
-            (i32.const 3)
-          )
+    (if
+      (i32.const 2)
+      (drop
+        (call $lb
+          (i32.const 3)
         )
       )
     )
@@ -1023,4 +1021,27 @@
     )
     (get_local $0)
   )
+  (func $dropIgnoredImportInIf (param $0 i32) (param $1 i32) (param $2 i32)
+    (if
+      (get_local $0)
+      (drop
+        (call $lb
+          (get_local $2)
+        )
+      )
+    )
+  )
+  (func $dropIgnoredImportsInIf (param $0 i32) (param $1 i32) (param $2 i32)
+    (drop
+      (if
+        (get_local $0)
+        (call $lb
+          (get_local $1)
+        )
+        (call $lb
+          (get_local $2)
+        )
+      )
+    )
+  )
 )
diff --git a/test/unit.fromasm.imprecise b/test/unit.fromasm.imprecise
index ad130ea82..b170c8b82 100644
--- a/test/unit.fromasm.imprecise
+++ b/test/unit.fromasm.imprecise
@@ -489,13 +489,11 @@
     )
   )
   (func $smallIf
-    (block $do-once$0
-      (if
-        (i32.const 2)
-        (drop
-          (call $lb
-            (i32.const 3)
-          )
+    (if
+      (i32.const 2)
+      (drop
+        (call $lb
+          (i32.const 3)
         )
       )
     )
@@ -1004,4 +1002,27 @@
     )
     (get_local $0)
   )
+  (func $dropIgnoredImportInIf (param $0 i32) (param $1 i32) (param $2 i32)
+    (if
+      (get_local $0)
+      (drop
+        (call $lb
+          (get_local $2)
+        )
+      )
+    )
+  )
+  (func $dropIgnoredImportsInIf (param $0 i32) (param $1 i32) (param $2 i32)
+    (drop
+      (if
+        (get_local $0)
+        (call $lb
+          (get_local $1)
+        )
+        (call $lb
+          (get_local $2)
+        )
+      )
+    )
+  )
 )
diff --git a/test/unit.fromasm.imprecise.no-opts b/test/unit.fromasm.imprecise.no-opts
index 636238f17..913920f8b 100644
--- a/test/unit.fromasm.imprecise.no-opts
+++ b/test/unit.fromasm.imprecise.no-opts
@@ -856,14 +856,14 @@
   )
   (func $smallIf
     (block $do-once$0
-      (drop
-        (if
-          (i32.const 2)
+      (if
+        (i32.const 2)
+        (drop
           (call $lb
             (i32.const 3)
           )
-          (br $do-once$0)
         )
+        (br $do-once$0)
       )
       (nop)
     )
@@ -930,23 +930,23 @@
   )
   (func $breakThroughMany (param $$s i32)
     (block $label$break$L1
-      (drop
-        (if
-          (get_local $$s)
-          (loop $while-in$2
-            (block $while-out$1
-              (if
-                (i32.eqz
-                  (get_local $$s)
-                )
-                (br $label$break$L1)
-              )
-              (call $zeroInit
-                (i32.const 0)
+      (if
+        (get_local $$s)
+        (loop $while-in$2
+          (block $while-out$1
+            (if
+              (i32.eqz
+                (get_local $$s)
               )
-              (br $while-in$2)
+              (br $label$break$L1)
+            )
+            (call $zeroInit
+              (i32.const 0)
             )
+            (br $while-in$2)
           )
+        )
+        (drop
           (i32.const 1337)
         )
       )
@@ -1624,4 +1624,43 @@
       (get_local $temp)
     )
   )
+  (func $dropIgnoredImportInIf (param $$0 i32) (param $$1 i32) (param $$2 i32)
+    (block $do-once$0
+      (if
+        (get_local $$0)
+        (block
+          (set_local $$0
+            (i32.const 1)
+          )
+          (drop
+            (call $lb
+              (get_local $$2)
+            )
+          )
+        )
+        (br $do-once$0)
+      )
+      (nop)
+    )
+    (return)
+  )
+  (func $dropIgnoredImportsInIf (param $$0 i32) (param $$1 i32) (param $$2 i32)
+    (block $do-once$0
+      (if
+        (get_local $$0)
+        (drop
+          (call $lb
+            (get_local $$1)
+          )
+        )
+        (drop
+          (call $lb
+            (get_local $$2)
+          )
+        )
+      )
+      (nop)
+    )
+    (return)
+  )
 )
diff --git a/test/unit.fromasm.no-opts b/test/unit.fromasm.no-opts
index 0684c1464..21e7ea79e 100644
--- a/test/unit.fromasm.no-opts
+++ b/test/unit.fromasm.no-opts
@@ -862,14 +862,14 @@
   )
   (func $smallIf
     (block $do-once$0
-      (drop
-        (if
-          (i32.const 2)
+      (if
+        (i32.const 2)
+        (drop
           (call $lb
             (i32.const 3)
           )
-          (br $do-once$0)
         )
+        (br $do-once$0)
       )
       (nop)
     )
@@ -936,23 +936,23 @@
   )
   (func $breakThroughMany (param $$s i32)
     (block $label$break$L1
-      (drop
-        (if
-          (get_local $$s)
-          (loop $while-in$2
-            (block $while-out$1
-              (if
-                (i32.eqz
-                  (get_local $$s)
-                )
-                (br $label$break$L1)
-              )
-              (call $zeroInit
-                (i32.const 0)
+      (if
+        (get_local $$s)
+        (loop $while-in$2
+          (block $while-out$1
+            (if
+              (i32.eqz
+                (get_local $$s)
               )
-              (br $while-in$2)
+              (br $label$break$L1)
+            )
+            (call $zeroInit
+              (i32.const 0)
             )
+            (br $while-in$2)
           )
+        )
+        (drop
           (i32.const 1337)
         )
       )
@@ -1630,4 +1630,43 @@
       (get_local $temp)
     )
   )
+  (func $dropIgnoredImportInIf (param $$0 i32) (param $$1 i32) (param $$2 i32)
+    (block $do-once$0
+      (if
+        (get_local $$0)
+        (block
+          (set_local $$0
+            (i32.const 1)
+          )
+          (drop
+            (call $lb
+              (get_local $$2)
+            )
+          )
+        )
+        (br $do-once$0)
+      )
+      (nop)
+    )
+    (return)
+  )
+  (func $dropIgnoredImportsInIf (param $$0 i32) (param $$1 i32) (param $$2 i32)
+    (block $do-once$0
+      (if
+        (get_local $$0)
+        (drop
+          (call $lb
+            (get_local $$1)
+          )
+        )
+        (drop
+          (call $lb
+            (get_local $$2)
+          )
+        )
+      )
+      (nop)
+    )
+    (return)
+  )
 )