fix re-reloop fuzz bug, we need to ensure a terminator in all relooper blocks (#1214)

5 files changed, 118 insertions, 2 deletions

diff --git a/src/cfg/Relooper.h b/src/cfg/Relooper.h
index 50f40fd88..f12ed2945 100644
--- a/src/cfg/Relooper.h
+++ b/src/cfg/Relooper.h
@@ -136,6 +136,7 @@ struct InsertOrderedSet
   }
 
   size_t size() const { return Map.size(); }
+  bool empty() const { return Map.empty(); }
 
   void clear() {
     Map.clear();
@@ -194,6 +195,7 @@ struct InsertOrderedMap
   }
 
   size_t size() const { return Map.size(); }
+  bool empty() const { return Map.empty(); }
   size_t count(const Key& k) const { return Map.count(k); }
 
   InsertOrderedMap() {}
diff --git a/src/passes/ReReloop.cpp b/src/passes/ReReloop.cpp
index 7e202b002..c36363ba9 100644
--- a/src/passes/ReReloop.cpp
+++ b/src/passes/ReReloop.cpp
@@ -30,6 +30,10 @@
 #include "cfg/Relooper.h"
 #include "ast_utils.h"
 
+#ifdef RERELOOP_DEBUG
+#include <wasm-printing.h>
+#endif
+
 namespace wasm {
 
 struct ReReloop final : public Pass {
@@ -307,6 +311,33 @@ struct ReReloop final : public Pass {
     }
     // finish the current block
     finishBlock();
+    // blocks that do not have any exits are dead ends in the relooper. we need
+    // to make sure that are in fact dead ends, and do not flow control anywhere.
+    // add a return as needed
+    for (auto* cfgBlock : relooper.Blocks) {
+      auto* block = cfgBlock->Code->cast<Block>();
+      if (cfgBlock->BranchesOut.empty() && block->type != unreachable) {
+        block->list.push_back(
+          function->result == none ? (Expression*)builder->makeReturn()
+                                   : (Expression*)builder->makeUnreachable()
+        );
+        block->finalize();
+      }
+    }
+#ifdef RERELOOP_DEBUG
+    std::cout << "rerelooping " << function->name << '\n';
+    for (auto* block : relooper.Blocks) {
+      std::cout << block << " block:\n" << block->Code << '\n';
+      for (auto& pair : block->BranchesOut) {
+        auto* target = pair.first;
+        auto* branch = pair.second;
+        std::cout << "branch to " << target << "\n";
+        if (branch->Condition) {
+          std::cout << "  with condition\n" << branch->Condition << '\n';
+        }
+      }
+    }
+#endif
     // run the relooper to recreate control flow
     relooper.Calculate(entry);
     // render
diff --git a/test/passes/rereloop.txt b/test/passes/rereloop.txt
index 17a084395..7a70098c0 100644
--- a/test/passes/rereloop.txt
+++ b/test/passes/rereloop.txt
@@ -8,6 +8,7 @@
   (local $0 i32)
   (block
    (nop)
+   (return)
   )
  )
  (func $trivial2 (type $0)
@@ -15,6 +16,7 @@
   (block
    (call $trivial)
    (call $trivial)
+   (return)
   )
  )
  (func $return-void (type $0)
@@ -161,6 +163,7 @@
       )
       (block
        (block
+        (return)
        )
       )
      )
@@ -182,6 +185,7 @@
   )
   (block
    (block
+    (return)
    )
   )
  )
@@ -206,6 +210,7 @@
      )
      (block
       (block
+       (return)
       )
      )
     )
@@ -254,6 +259,7 @@
    )
    (block
     (block
+     (return)
     )
    )
   )
@@ -509,6 +515,7 @@
                   (call $before-and-after
                    (i32.const 25)
                   )
+                  (return)
                  )
                 )
                )
@@ -598,6 +605,7 @@
     )
     (block
      (block
+      (return)
      )
     )
    )
@@ -634,6 +642,7 @@
   )
   (block
    (block
+    (return)
    )
   )
  )
@@ -697,6 +706,7 @@
     (call $if-br-wat
      (i32.const 3)
     )
+    (return)
    )
   )
  )
@@ -744,3 +754,52 @@
   )
  )
 )
+(module
+ (type $0 (func))
+ (type $1 (func (result i32)))
+ (global $global$0 (mut i32) (i32.const 1))
+ (memory $0 0)
+ (export "one" (func $0))
+ (export "two" (func $1))
+ (func $0 (type $0)
+  (local $0 i32)
+  (block $block$4$break
+   (block
+   )
+   (if
+    (i32.const 1)
+    (block
+     (block
+      (return)
+     )
+    )
+    (br $block$4$break)
+   )
+  )
+  (block
+   (block $block$3$break
+    (block
+     (set_global $global$0
+      (i32.const 0)
+     )
+    )
+    (block
+     (br $block$3$break)
+    )
+   )
+   (block
+    (block
+     (unreachable)
+    )
+   )
+  )
+ )
+ (func $1 (type $1) (result i32)
+  (local $0 i32)
+  (block
+   (return
+    (get_global $global$0)
+   )
+  )
+ )
+)
diff --git a/test/passes/rereloop.wast b/test/passes/rereloop.wast
index 0680c97fe..36057566a 100644
--- a/test/passes/rereloop.wast
+++ b/test/passes/rereloop.wast
@@ -197,4 +197,25 @@
   )
  )
 )
+(module
+ (global $global$0 (mut i32) (i32.const 1))
+ (export "one" (func $0))
+ (export "two" (func $1))
+ (func $0
+  (block $outer
+   (block
+    (br_if $outer ;; taken - do not modify the global, stay it at 1
+     (i32.const 1)
+    )
+    (set_global $global$0 ;; never get here!
+     (i32.const 0)
+    )
+   )
+   (unreachable)
+  )
+ )
+ (func $1 (result i32)
+  (return (get_global $global$0))
+ )
+)
 
diff --git a/test/passes/rereloop_dce_remove-unused-brs_remove-unused-names_coalesce-locals_simplify-locals_reorder-locals_remove-unused-brs_merge-blocks_vacuum.txt b/test/passes/rereloop_dce_remove-unused-brs_remove-unused-names_coalesce-locals_simplify-locals_reorder-locals_remove-unused-brs_merge-blocks_vacuum.txt
index 9a49f3891..e7aa9097b 100644
--- a/test/passes/rereloop_dce_remove-unused-brs_remove-unused-names_coalesce-locals_simplify-locals_reorder-locals_remove-unused-brs_merge-blocks_vacuum.txt
+++ b/test/passes/rereloop_dce_remove-unused-brs_remove-unused-names_coalesce-locals_simplify-locals_reorder-locals_remove-unused-brs_merge-blocks_vacuum.txt
@@ -68,8 +68,11 @@
    (i32.eqz
     (get_local $0)
    )
-   (call $unreachable
-    (i32.const 5)
+   (block
+    (call $unreachable
+     (i32.const 5)
+    )
+    (return)
    )
   )
   (if