Fix value flowing in remove-unused-brs (#1639)

The fuzzer found a bug with flowing of values in that pass: when one arm of an if is none-typed, we can't flow a value through the other. Odd the fuzzer didn't find this earlier, as it's been a bug since the pass was written years ago, but in practice it seems you need a specific set of circumstances on the outside for it to be hit.

The fix is to stop flowing a value in that case. Also, I realized after fixing it that the valueCanFlow global state variable is entirely unneeded. Removing it makes the pass significantly simpler: at all times, flows contains branches and values that might be flowing, and if the flow stops we remove them, etc. - we don't need an extra state variable to say if flowing is possible. So when we want to use the flows, we just check what is there (and then for a flowing branch we can remove it, and for a flowing value we can replace the branch with the value, etc., as in both cases they flow to the right place anyhow).

3 files changed, 128 insertions, 27 deletions

diff --git a/src/passes/RemoveUnusedBrs.cpp b/src/passes/RemoveUnusedBrs.cpp
index 8a80cd3d2..5b6f0839b 100644
--- a/src/passes/RemoveUnusedBrs.cpp
+++ b/src/passes/RemoveUnusedBrs.cpp
@@ -47,10 +47,6 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> {
 
   bool anotherCycle;
 
-  // Whether a value can flow in the current path. If so, then a br with value
-  // can be turned into a value, which will flow through blocks/ifs to the right place
-  bool valueCanFlow;
-
   typedef std::vector<Expression**> Flows;
 
   // list of breaks that are currently flowing. if they reach their target without
@@ -73,14 +69,12 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> {
       if (!br->condition) { // TODO: optimize?
         // a break, let's see where it flows to
         flows.push_back(currp);
-        self->valueCanFlow = true; // start optimistic
       } else {
         self->stopValueFlow();
       }
     } else if (curr->is<Return>()) {
       flows.clear();
       flows.push_back(currp);
-      self->valueCanFlow = true; // start optimistic
     } else if (curr->is<If>()) {
       auto* iff = curr->cast<If>();
       if (iff->condition->type == unreachable) {
@@ -90,10 +84,20 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> {
       }
       if (iff->ifFalse) {
         assert(self->ifStack.size() > 0);
-        for (auto* flow : self->ifStack.back()) {
+        auto ifTrueFlows = std::move(self->ifStack.back());
+        self->ifStack.pop_back();
+        // we can flow values out in most cases, except if one arm
+        // has the none type - we will update the types later, but
+        // there is no way to emit a proper type for one arm being
+        // none and the other flowing a value; and there is no way
+        // to flow a value from a none.
+        if (iff->ifTrue->type == none || iff->ifFalse->type == none) {
+          self->removeValueFlow(ifTrueFlows);
+          self->stopValueFlow();
+        }
+        for (auto* flow : ifTrueFlows) {
           flows.push_back(flow);
         }
-        self->ifStack.pop_back();
       } else {
         // if without else stops the flow of values
         self->stopValueFlow();
@@ -108,17 +112,15 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> {
         for (size_t i = 0; i < size; i++) {
           auto* flow = (*flows[i])->dynCast<Break>();
           if (flow && flow->name == name) {
-            if (!flow->value || self->valueCanFlow) {
-              if (!flow->value) {
-                // br => nop
-                ExpressionManipulator::nop<Break>(flow);
-              } else {
-                // br with value => value
-                *flows[i] = flow->value;
-              }
-              skip++;
-              self->anotherCycle = true;
+            if (!flow->value) {
+              // br => nop
+              ExpressionManipulator::nop<Break>(flow);
+            } else {
+              // br with value => value
+              *flows[i] = flow->value;
             }
+            skip++;
+            self->anotherCycle = true;
           } else if (skip > 0) {
             flows[i - skip] = flows[i];
           }
@@ -148,18 +150,20 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> {
 
   void stopFlow() {
     flows.clear();
-    valueCanFlow = false;
   }
 
-  void stopValueFlow() {
-    flows.erase(std::remove_if(flows.begin(), flows.end(), [&](Expression** currp) {
+  void removeValueFlow(Flows& currFlows) {
+    currFlows.erase(std::remove_if(currFlows.begin(), currFlows.end(), [&](Expression** currp) {
       auto* curr = *currp;
       if (auto* ret = curr->dynCast<Return>()) {
         return ret->value;
       }
       return curr->cast<Break>()->value;
-    }), flows.end());
-    valueCanFlow = false;
+    }), currFlows.end());
+  }
+
+  void stopValueFlow() {
+    removeValueFlow(flows);
   }
 
   static void clear(RemoveUnusedBrs* self, Expression** currp) {
@@ -447,7 +451,7 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> {
           // return => nop
           ExpressionManipulator::nop(flow);
           anotherCycle = true;
-        } else if (valueCanFlow) {
+        } else {
           // return with value => value
           *flows[i] = flow->value;
           anotherCycle = true;
diff --git a/test/passes/remove-unused-brs.txt b/test/passes/remove-unused-brs.txt
index 378ee4812..5db42249d 100644
--- a/test/passes/remove-unused-brs.txt
+++ b/test/passes/remove-unused-brs.txt
@@ -741,9 +741,7 @@
    )
    (if (result i32)
     (i32.const 6)
-    (br $outval
-     (i32.const 7)
-    )
+    (i32.const 7)
     (i32.const 8)
    )
   )
@@ -1871,4 +1869,57 @@
   )
   (i32.const 0)
  )
+ (func $if-flow-1 (; 75 ;) (type $2) (result i32)
+  (if (result i32)
+   (i32.const 0)
+   (i32.const 1)
+   (i32.const 2)
+  )
+ )
+ (func $if-flow-2 (; 76 ;) (type $2) (result i32)
+  (if (result i32)
+   (i32.const 0)
+   (unreachable)
+   (i32.const 2)
+  )
+ )
+ (func $if-flow-3 (; 77 ;) (type $2) (result i32)
+  (if (result i32)
+   (i32.const 0)
+   (i32.const 1)
+   (unreachable)
+  )
+ )
+ (func $if-flow-4 (; 78 ;) (type $2) (result i32)
+  (if
+   (return
+    (i32.const 0)
+   )
+   (return
+    (i32.const 1)
+   )
+   (return
+    (i32.const 2)
+   )
+  )
+ )
+ (func $iff-flow-fuzz-bug (; 79 ;) (type $2) (result i32)
+  (loop $label$1
+   (br_if $label$1
+    (i32.eqz
+     (i32.const 1)
+    )
+   )
+   (loop $label$2
+    (unreachable)
+    (if
+     (i32.const 0)
+     (nop)
+     (return
+      (i32.const 0)
+     )
+    )
+   )
+  )
+ )
 )
diff --git a/test/passes/remove-unused-brs.wast b/test/passes/remove-unused-brs.wast
index dbb415deb..c63dc4689 100644
--- a/test/passes/remove-unused-brs.wast
+++ b/test/passes/remove-unused-brs.wast
@@ -1494,5 +1494,51 @@
    )
    (i32.const 0)
   )
+  (func $if-flow-1 (result i32)
+    (if
+      (i32.const 0)
+      (return (i32.const 1))
+      (return (i32.const 2))
+    )
+  )
+  (func $if-flow-2 (result i32)
+    (if
+      (i32.const 0)
+      (unreachable)
+      (return (i32.const 2))
+    )
+  )
+  (func $if-flow-3 (result i32)
+    (if
+      (i32.const 0)
+      (return (i32.const 1))
+      (unreachable)
+    )
+  )
+  (func $if-flow-4 (result i32)
+    (if
+      (return (i32.const 0))
+      (return (i32.const 1))
+      (return (i32.const 2))
+    )
+  )
+  (func $iff-flow-fuzz-bug (result i32)
+   (loop $label$1
+    (if
+     (i32.const 1)
+     (loop $label$2
+      (unreachable)
+      (if ;; a loop that is never reached at the end of a loop
+       (i32.const 0)
+       (nop)
+       (return
+        (i32.const 0)
+       )
+      )
+     )
+    )
+    (br $label$1)
+   )
+  )
 )