Relooper: Merge consecutive blocks (#1770)

That is, A -> B where no other branches go to B. In that case we are guaranteed to not increase code size.

10 files changed, 630 insertions, 441 deletions

diff --git a/src/cfg/Relooper.cpp b/src/cfg/Relooper.cpp
index 74fe8e7b5..17bccc451 100644
--- a/src/cfg/Relooper.cpp
+++ b/src/cfg/Relooper.cpp
@@ -493,6 +493,7 @@ struct Optimizer : public RelooperRecursor {
       More = SkipEmptyBlocks() || More;
       More = MergeEquivalentBranches() || More;
       More = UnSwitch() || More;
+      More = MergeConsecutiveBlocks() || More;
       // TODO: Merge identical blocks. This would avoid taking into account their
       // position / how they are reached, which means that the merging
       // may add overhead, so we do it carefully:
@@ -648,6 +649,45 @@ struct Optimizer : public RelooperRecursor {
     return Worked;
   }
 
+  // Merge consecutive blocks, that is, A -> B where no other branches go to B.
+  // In that case we are guaranteed to not increase code size.
+  bool MergeConsecutiveBlocks() {
+    bool Worked = false;
+    // First, count predecessors.
+    std::map<Block*, size_t> NumPredecessors;
+    for (auto* CurrBlock : Parent->Blocks) {
+      for (auto& iter : CurrBlock->BranchesOut) {
+        auto* NextBlock = iter.first;
+        NumPredecessors[NextBlock]++;
+      }
+    }
+    for (auto* CurrBlock : Parent->Blocks) {
+      if (CurrBlock->BranchesOut.size() == 1) {
+        auto iter = CurrBlock->BranchesOut.begin();
+        auto* NextBlock = iter->first;
+        auto* NextBranch = iter->second;
+        assert(NumPredecessors[NextBlock] > 0);
+        if (NextBlock != CurrBlock && NumPredecessors[NextBlock] == 1) {
+          // Good to merge!
+          wasm::Builder Builder(*Parent->Module);
+          // Merge in code on the branch as well, if any.
+          if (NextBranch->Code) {
+            CurrBlock->Code = Builder.makeSequence(CurrBlock->Code, NextBranch->Code);
+          }
+          CurrBlock->Code = Builder.makeSequence(CurrBlock->Code, NextBlock->Code);
+          // Use the next block's branching behavior
+          CurrBlock->BranchesOut.swap(NextBlock->BranchesOut);
+          NextBlock->BranchesOut.clear();
+          CurrBlock->SwitchCondition = NextBlock->SwitchCondition;
+          // The next block now has no predecessors.
+          NumPredecessors[NextBlock] = 0;
+          Worked = true;
+        }
+      }
+    }
+    return Worked;
+  }
+
   // Removes unneeded switches - if only one branch is left, the default, then
   // no switch is needed.
   bool UnSwitch() {
diff --git a/test/binaryen.js/kitchen-sink.js.txt b/test/binaryen.js/kitchen-sink.js.txt
index 2612f42b8..f5ad2814e 100644
--- a/test/binaryen.js/kitchen-sink.js.txt
+++ b/test/binaryen.js/kitchen-sink.js.txt
@@ -586,15 +586,10 @@ raw:
  )
  (func $two-blocks (; 2 ;) (type $v)
   (local $0 i32)
-  (block $block$2$break
+  (block
    (call $check
     (i32.const 0)
    )
-   (block
-    (br $block$2$break)
-   )
-  )
-  (block
    (call $check
     (i32.const 1)
    )
@@ -602,18 +597,15 @@ raw:
  )
  (func $two-blocks-plus-code (; 3 ;) (type $v)
   (local $0 i32)
-  (block $block$2$break
-   (call $check
-    (i32.const 0)
-   )
+  (block
    (block
+    (call $check
+     (i32.const 0)
+    )
     (drop
      (i32.const 77)
     )
-    (br $block$2$break)
    )
-  )
-  (block
    (call $check
     (i32.const 1)
    )
@@ -622,48 +614,40 @@ raw:
  (func $loop (; 4 ;) (type $v)
   (local $0 i32)
   (loop $shape$0$continue
-   (block $block$2$break
+   (block
     (call $check
      (i32.const 0)
     )
-    (block
-     (br $block$2$break)
-    )
-   )
-   (block
     (call $check
      (i32.const 1)
     )
-    (block
-     (br $shape$0$continue)
-    )
+   )
+   (block
+    (br $shape$0$continue)
    )
   )
  )
  (func $loop-plus-code (; 5 ;) (type $v)
   (local $0 i32)
   (loop $shape$0$continue
-   (block $block$2$break
-    (call $check
-     (i32.const 0)
-    )
+   (block
     (block
+     (call $check
+      (i32.const 0)
+     )
      (drop
       (i32.const 33)
      )
-     (br $block$2$break)
     )
-   )
-   (block
     (call $check
      (i32.const 1)
     )
-    (block
-     (drop
-      (i32.const -66)
-     )
-     (br $shape$0$continue)
+   )
+   (block
+    (drop
+     (i32.const -66)
     )
+    (br $shape$0$continue)
    )
   )
  )
@@ -814,23 +798,18 @@ raw:
   (local $0 i32)
   (block $block$3$break
    (loop $shape$0$continue
-    (block $block$2$break
+    (block
      (call $check
       (i32.const 0)
      )
-     (block
-      (br $block$2$break)
-     )
-    )
-    (block
      (call $check
       (i32.const 1)
      )
-     (if
-      (i32.const 10)
-      (br $shape$0$continue)
-      (br $block$3$break)
-     )
+    )
+    (if
+     (i32.const 10)
+     (br $shape$0$continue)
+     (br $block$3$break)
     )
    )
   )
@@ -2504,15 +2483,10 @@ raw:
  )
  (func $two-blocks (; 2 ;) (type $v)
   (local $0 i32)
-  (block $block$2$break
+  (block
    (call $check
     (i32.const 0)
    )
-   (block
-    (br $block$2$break)
-   )
-  )
-  (block
    (call $check
     (i32.const 1)
    )
@@ -2520,18 +2494,15 @@ raw:
  )
  (func $two-blocks-plus-code (; 3 ;) (type $v)
   (local $0 i32)
-  (block $block$2$break
-   (call $check
-    (i32.const 0)
-   )
+  (block
    (block
+    (call $check
+     (i32.const 0)
+    )
     (drop
      (i32.const 77)
     )
-    (br $block$2$break)
    )
-  )
-  (block
    (call $check
     (i32.const 1)
    )
@@ -2540,48 +2511,40 @@ raw:
  (func $loop (; 4 ;) (type $v)
   (local $0 i32)
   (loop $shape$0$continue
-   (block $block$2$break
+   (block
     (call $check
      (i32.const 0)
     )
-    (block
-     (br $block$2$break)
-    )
-   )
-   (block
     (call $check
      (i32.const 1)
     )
-    (block
-     (br $shape$0$continue)
-    )
+   )
+   (block
+    (br $shape$0$continue)
    )
   )
  )
  (func $loop-plus-code (; 5 ;) (type $v)
   (local $0 i32)
   (loop $shape$0$continue
-   (block $block$2$break
-    (call $check
-     (i32.const 0)
-    )
+   (block
     (block
+     (call $check
+      (i32.const 0)
+     )
      (drop
       (i32.const 33)
      )
-     (br $block$2$break)
     )
-   )
-   (block
     (call $check
      (i32.const 1)
     )
-    (block
-     (drop
-      (i32.const -66)
-     )
-     (br $shape$0$continue)
+   )
+   (block
+    (drop
+     (i32.const -66)
     )
+    (br $shape$0$continue)
    )
   )
  )
@@ -2732,23 +2695,18 @@ raw:
   (local $0 i32)
   (block $block$3$break
    (loop $shape$0$continue
-    (block $block$2$break
+    (block
      (call $check
       (i32.const 0)
      )
-     (block
-      (br $block$2$break)
-     )
-    )
-    (block
      (call $check
       (i32.const 1)
      )
-     (if
-      (i32.const 10)
-      (br $shape$0$continue)
-      (br $block$3$break)
-     )
+    )
+    (if
+     (i32.const 10)
+     (br $shape$0$continue)
+     (br $block$3$break)
     )
    )
   )
diff --git a/test/example/c-api-kitchen-sink.txt b/test/example/c-api-kitchen-sink.txt
index b7ee4b8b7..90c26c3ae 100644
--- a/test/example/c-api-kitchen-sink.txt
+++ b/test/example/c-api-kitchen-sink.txt
@@ -563,15 +563,10 @@ raw:
  )
  (func $two-blocks (; 2 ;) (type $v)
   (local $0 i32)
-  (block $block$2$break
+  (block
    (call $check
     (i32.const 0)
    )
-   (block
-    (br $block$2$break)
-   )
-  )
-  (block
    (call $check
     (i32.const 1)
    )
@@ -579,18 +574,15 @@ raw:
  )
  (func $two-blocks-plus-code (; 3 ;) (type $v)
   (local $0 i32)
-  (block $block$2$break
-   (call $check
-    (i32.const 0)
-   )
+  (block
    (block
+    (call $check
+     (i32.const 0)
+    )
     (drop
      (i32.const 77)
     )
-    (br $block$2$break)
    )
-  )
-  (block
    (call $check
     (i32.const 1)
    )
@@ -599,48 +591,40 @@ raw:
  (func $loop (; 4 ;) (type $v)
   (local $0 i32)
   (loop $shape$0$continue
-   (block $block$2$break
+   (block
     (call $check
      (i32.const 0)
     )
-    (block
-     (br $block$2$break)
-    )
-   )
-   (block
     (call $check
      (i32.const 1)
     )
-    (block
-     (br $shape$0$continue)
-    )
+   )
+   (block
+    (br $shape$0$continue)
    )
   )
  )
  (func $loop-plus-code (; 5 ;) (type $v)
   (local $0 i32)
   (loop $shape$0$continue
-   (block $block$2$break
-    (call $check
-     (i32.const 0)
-    )
+   (block
     (block
+     (call $check
+      (i32.const 0)
+     )
      (drop
       (i32.const 33)
      )
-     (br $block$2$break)
     )
-   )
-   (block
     (call $check
      (i32.const 1)
     )
-    (block
-     (drop
-      (i32.const -66)
-     )
-     (br $shape$0$continue)
+   )
+   (block
+    (drop
+     (i32.const -66)
     )
+    (br $shape$0$continue)
    )
   )
  )
@@ -791,23 +775,18 @@ raw:
   (local $0 i32)
   (block $block$3$break
    (loop $shape$0$continue
-    (block $block$2$break
+    (block
      (call $check
       (i32.const 0)
      )
-     (block
-      (br $block$2$break)
-     )
-    )
-    (block
      (call $check
       (i32.const 1)
      )
-     (if
-      (i32.const 10)
-      (br $shape$0$continue)
-      (br $block$3$break)
-     )
+    )
+    (if
+     (i32.const 10)
+     (br $shape$0$continue)
+     (br $block$3$break)
     )
    )
   )
@@ -2438,15 +2417,10 @@ raw:
  )
  (func $two-blocks (; 2 ;) (type $v)
   (local $0 i32)
-  (block $block$2$break
+  (block
    (call $check
     (i32.const 0)
    )
-   (block
-    (br $block$2$break)
-   )
-  )
-  (block
    (call $check
     (i32.const 1)
    )
@@ -2454,18 +2428,15 @@ raw:
  )
  (func $two-blocks-plus-code (; 3 ;) (type $v)
   (local $0 i32)
-  (block $block$2$break
-   (call $check
-    (i32.const 0)
-   )
+  (block
    (block
+    (call $check
+     (i32.const 0)
+    )
     (drop
      (i32.const 77)
     )
-    (br $block$2$break)
    )
-  )
-  (block
    (call $check
     (i32.const 1)
    )
@@ -2474,48 +2445,40 @@ raw:
  (func $loop (; 4 ;) (type $v)
   (local $0 i32)
   (loop $shape$0$continue
-   (block $block$2$break
+   (block
     (call $check
      (i32.const 0)
     )
-    (block
-     (br $block$2$break)
-    )
-   )
-   (block
     (call $check
      (i32.const 1)
     )
-    (block
-     (br $shape$0$continue)
-    )
+   )
+   (block
+    (br $shape$0$continue)
    )
   )
  )
  (func $loop-plus-code (; 5 ;) (type $v)
   (local $0 i32)
   (loop $shape$0$continue
-   (block $block$2$break
-    (call $check
-     (i32.const 0)
-    )
+   (block
     (block
+     (call $check
+      (i32.const 0)
+     )
      (drop
       (i32.const 33)
      )
-     (br $block$2$break)
     )
-   )
-   (block
     (call $check
      (i32.const 1)
     )
-    (block
-     (drop
-      (i32.const -66)
-     )
-     (br $shape$0$continue)
+   )
+   (block
+    (drop
+     (i32.const -66)
     )
+    (br $shape$0$continue)
    )
   )
  )
@@ -2666,23 +2629,18 @@ raw:
   (local $0 i32)
   (block $block$3$break
    (loop $shape$0$continue
-    (block $block$2$break
+    (block
      (call $check
       (i32.const 0)
      )
-     (block
-      (br $block$2$break)
-     )
-    )
-    (block
      (call $check
       (i32.const 1)
      )
-     (if
-      (i32.const 10)
-      (br $shape$0$continue)
-      (br $block$3$break)
-     )
+    )
+    (if
+     (i32.const 10)
+     (br $shape$0$continue)
+     (br $block$3$break)
     )
    )
   )
diff --git a/test/example/c-api-kitchen-sink.txt.txt b/test/example/c-api-kitchen-sink.txt.txt
index c2d518020..d23e109b5 100644
--- a/test/example/c-api-kitchen-sink.txt.txt
+++ b/test/example/c-api-kitchen-sink.txt.txt
@@ -546,15 +546,10 @@
  )
  (func $two-blocks (; 2 ;) (type $v)
   (local $0 i32)
-  (block $block$2$break
+  (block
    (call $check
     (i32.const 0)
    )
-   (block
-    (br $block$2$break)
-   )
-  )
-  (block
    (call $check
     (i32.const 1)
    )
@@ -562,18 +557,15 @@
  )
  (func $two-blocks-plus-code (; 3 ;) (type $v)
   (local $0 i32)
-  (block $block$2$break
-   (call $check
-    (i32.const 0)
-   )
+  (block
    (block
+    (call $check
+     (i32.const 0)
+    )
     (drop
      (i32.const 77)
     )
-    (br $block$2$break)
    )
-  )
-  (block
    (call $check
     (i32.const 1)
    )
@@ -582,48 +574,40 @@
  (func $loop (; 4 ;) (type $v)
   (local $0 i32)
   (loop $shape$0$continue
-   (block $block$2$break
+   (block
     (call $check
      (i32.const 0)
     )
-    (block
-     (br $block$2$break)
-    )
-   )
-   (block
     (call $check
      (i32.const 1)
     )
-    (block
-     (br $shape$0$continue)
-    )
+   )
+   (block
+    (br $shape$0$continue)
    )
   )
  )
  (func $loop-plus-code (; 5 ;) (type $v)
   (local $0 i32)
   (loop $shape$0$continue
-   (block $block$2$break
-    (call $check
-     (i32.const 0)
-    )
+   (block
     (block
+     (call $check
+      (i32.const 0)
+     )
      (drop
       (i32.const 33)
      )
-     (br $block$2$break)
     )
-   )
-   (block
     (call $check
      (i32.const 1)
     )
-    (block
-     (drop
-      (i32.const -66)
-     )
-     (br $shape$0$continue)
+   )
+   (block
+    (drop
+     (i32.const -66)
     )
+    (br $shape$0$continue)
    )
   )
  )
@@ -774,23 +758,18 @@
   (local $0 i32)
   (block $block$3$break
    (loop $shape$0$continue
-    (block $block$2$break
+    (block
      (call $check
       (i32.const 0)
      )
-     (block
-      (br $block$2$break)
-     )
-    )
-    (block
      (call $check
       (i32.const 1)
      )
-     (if
-      (i32.const 10)
-      (br $shape$0$continue)
-      (br $block$3$break)
-     )
+    )
+    (if
+     (i32.const 10)
+     (br $shape$0$continue)
+     (br $block$3$break)
     )
    )
   )
diff --git a/test/example/relooper-merge1.txt b/test/example/relooper-merge1.txt
index b6d1f49f1..66153770c 100644
--- a/test/example/relooper-merge1.txt
+++ b/test/example/relooper-merge1.txt
@@ -44,7 +44,7 @@
  (func $main (; 2 ;) (type $v)
   (local $0 i32)
   (local $1 i32)
-  (block $block$2$break
+  (block
    (block
     (call $print
      (i32.const 0)
@@ -54,11 +54,6 @@
     )
    )
    (block
-    (br $block$2$break)
-   )
-  )
-  (block
-   (block
     (call $print
      (i32.const 1)
     )
diff --git a/test/example/relooper-merge6.c b/test/example/relooper-merge6.c
new file mode 100644
index 000000000..25004c9df
--- /dev/null
+++ b/test/example/relooper-merge6.c
@@ -0,0 +1,201 @@
+
+
+#include <assert.h>
+#include <stdio.h>
+
+#include "binaryen-c.h"
+
+// globals: address 4 is index
+// decisions are at address 8+
+
+int main() {
+  BinaryenModuleRef module = BinaryenModuleCreate();
+
+  // check()
+
+  // if the end, halt
+  BinaryenExpressionRef halter = BinaryenIf(module,
+    BinaryenBinary(module,
+      BinaryenGeUInt32(),
+      BinaryenLoad(module, 4, 0, 0, 0, BinaryenTypeInt32(),
+                   BinaryenConst(module, BinaryenLiteralInt32(4))),
+      BinaryenConst(module, BinaryenLiteralInt32(4 * 12)) // jumps of 4 bytes
+    ),
+    BinaryenUnreachable(module),
+    NULL
+  );
+  // increment index
+  BinaryenExpressionRef incer = BinaryenStore(module,
+    4, 0, 0,
+    BinaryenConst(module, BinaryenLiteralInt32(4)),
+    BinaryenBinary(module,
+      BinaryenAddInt32(),
+      BinaryenLoad(module, 4, 0, 0, 0, BinaryenTypeInt32(),
+                   BinaryenConst(module, BinaryenLiteralInt32(4))),
+      BinaryenConst(module, BinaryenLiteralInt32(4))
+    ),
+    BinaryenTypeInt32()
+  );
+
+  // optionally, print the return value
+  BinaryenExpressionRef args[] = {
+    BinaryenBinary(module,
+      BinaryenSubInt32(),
+      BinaryenConst(module, BinaryenLiteralInt32(0)),
+      BinaryenLoad(module,
+        4, 0, 4, 0, BinaryenTypeInt32(),
+        BinaryenLoad(module, 4, 0, 0, 0, BinaryenTypeInt32(),
+                     BinaryenConst(module, BinaryenLiteralInt32(4)))
+      )
+    )
+  };
+  BinaryenExpressionRef debugger;
+  if (1) debugger = BinaryenCall(module, "print", args, 1,
+                                 BinaryenTypeNone());
+  else debugger = BinaryenNop(module);
+
+  // return the decision. need to subtract 4 that we just added,
+  // and add 8 since that's where we start, so overall offset 4
+  BinaryenExpressionRef returner = BinaryenLoad(module,
+    4, 0, 4, 0, BinaryenTypeInt32(),
+    BinaryenLoad(module, 4, 0, 0, 0, BinaryenTypeInt32(),
+    BinaryenConst(module, BinaryenLiteralInt32(4)))
+  );
+  BinaryenExpressionRef checkBodyList[] = { halter, incer, debugger,
+                                            returner };
+  BinaryenExpressionRef checkBody = BinaryenBlock(module,
+    NULL, checkBodyList, sizeof(checkBodyList) / sizeof(BinaryenExpressionRef),
+    BinaryenTypeInt32()
+  );
+  BinaryenFunctionTypeRef i = BinaryenAddFunctionType(module, "i",
+                                                      BinaryenTypeInt32(),
+                                                      NULL, 0);
+  BinaryenAddFunction(module, "check", i, NULL, 0, checkBody);
+
+  // contents of main() begin here
+
+  RelooperRef relooper = RelooperCreate(module);
+
+
+  RelooperBlockRef b0;
+  {
+    BinaryenExpressionRef args[] = {
+      BinaryenConst(module, BinaryenLiteralInt32(0))
+    };
+    BinaryenExpressionRef list[] = {
+      BinaryenCall(module, "print", args, 1, BinaryenTypeNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0,
+                                               BinaryenTypeInt32()))
+    };
+
+    b0 = RelooperAddBlockWithSwitch(relooper,
+      BinaryenBlock(module, NULL, list, 2, BinaryenTypeNone()),
+      BinaryenBinary(module,
+        BinaryenRemUInt32(),
+        BinaryenGetLocal(module, 0, BinaryenTypeInt32()),
+        BinaryenConst(module, BinaryenLiteralInt32(1))
+      )
+    );
+
+  }
+
+  RelooperBlockRef b1;
+  {
+    BinaryenExpressionRef args[] = {
+      BinaryenConst(module, BinaryenLiteralInt32(1))
+    };
+    BinaryenExpressionRef list[] = {
+      BinaryenCall(module, "print", args, 1, BinaryenTypeNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0,
+                                               BinaryenTypeInt32()))
+    };
+
+    b1 = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2, BinaryenTypeNone()));
+
+  }
+
+  RelooperBlockRef b2;
+  {
+    BinaryenExpressionRef args[] = {
+      BinaryenConst(module, BinaryenLiteralInt32(1))
+    };
+    BinaryenExpressionRef list[] = {
+      BinaryenCall(module, "print", args, 1, BinaryenTypeNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0,
+                                               BinaryenTypeInt32()))
+    };
+
+    b2 = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2, BinaryenTypeNone()));
+
+  }
+
+  RelooperBlockRef b3;
+  {
+    BinaryenExpressionRef args[] = {
+      BinaryenConst(module, BinaryenLiteralInt32(1))
+    };
+    BinaryenExpressionRef list[] = {
+      BinaryenCall(module, "print", args, 1, BinaryenTypeNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0,
+                                               BinaryenTypeInt32()))
+    };
+
+    b3 = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2, BinaryenTypeNone()));
+  }
+
+  RelooperBlockRef b4;
+  {
+    BinaryenExpressionRef args[] = {
+      BinaryenConst(module, BinaryenLiteralInt32(1))
+    };
+    BinaryenExpressionRef list[] = {
+      BinaryenCall(module, "print", args, 1, BinaryenTypeNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0,
+                                               BinaryenTypeInt32()))
+    };
+
+    b4 = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2, BinaryenTypeNone()));
+  }
+
+  // Separate branch for each.
+  // In this testcase, we can merge multiple consecutive blocks with phis.
+  RelooperAddBranch(b0, b1, NULL, BinaryenDrop(module, BinaryenConst(module, BinaryenLiteralInt32(10))));
+  RelooperAddBranch(b1, b2, NULL, BinaryenDrop(module, BinaryenConst(module, BinaryenLiteralInt32(11))));
+  RelooperAddBranch(b2, b3, NULL, NULL);
+  RelooperAddBranch(b3, b4, NULL, BinaryenDrop(module, BinaryenConst(module, BinaryenLiteralInt32(12))));
+
+  BinaryenExpressionRef body = RelooperRenderAndDispose(relooper, b0, 1);
+
+  BinaryenFunctionTypeRef v = BinaryenAddFunctionType(module, "v",
+                                                      BinaryenTypeNone(),
+                                                      NULL, 0);
+  // locals: state, free-for-label
+  BinaryenType localTypes[] = { BinaryenTypeInt32(), BinaryenTypeInt32() };
+  BinaryenFunctionRef theMain = BinaryenAddFunction(module, "main", v,
+                                                    localTypes, 2, body);
+  BinaryenSetStart(module, theMain);
+
+  // import
+
+  BinaryenType iparams[] = { BinaryenTypeInt32() };
+  BinaryenFunctionTypeRef vi = BinaryenAddFunctionType(module, "vi",
+                                                       BinaryenTypeNone(),
+                                                       iparams, 1);
+  BinaryenAddFunctionImport(module, "print", "spectest", "print", vi);
+
+  // memory
+  BinaryenSetMemory(module, 1, 1, "mem", NULL, NULL, NULL, 0, 0);
+
+  // optionally, optimize
+  if (0) BinaryenModuleOptimize(module);
+
+  assert(BinaryenModuleValidate(module));
+
+  // write it out
+
+  BinaryenModulePrint(module);
+
+  BinaryenModuleDispose(module);
+
+  return 0;
+}
diff --git a/test/example/relooper-merge6.txt b/test/example/relooper-merge6.txt
new file mode 100644
index 000000000..d79aabe3d
--- /dev/null
+++ b/test/example/relooper-merge6.txt
@@ -0,0 +1,111 @@
+(module
+ (type $i (func (result i32)))
+ (type $v (func))
+ (type $vi (func (param i32)))
+ (import "spectest" "print" (func $print (param i32)))
+ (memory $0 1 1)
+ (export "mem" (memory $0))
+ (start $main)
+ (func $check (; 1 ;) (type $i) (result i32)
+  (if
+   (i32.ge_u
+    (i32.load
+     (i32.const 4)
+    )
+    (i32.const 48)
+   )
+   (unreachable)
+  )
+  (i32.store
+   (i32.const 4)
+   (i32.add
+    (i32.load
+     (i32.const 4)
+    )
+    (i32.const 4)
+   )
+  )
+  (call $print
+   (i32.sub
+    (i32.const 0)
+    (i32.load offset=4
+     (i32.load
+      (i32.const 4)
+     )
+    )
+   )
+  )
+  (i32.load offset=4
+   (i32.load
+    (i32.const 4)
+   )
+  )
+ )
+ (func $main (; 2 ;) (type $v)
+  (local $0 i32)
+  (local $1 i32)
+  (block
+   (block
+    (block
+     (block
+      (block
+       (block
+        (block
+         (call $print
+          (i32.const 0)
+         )
+         (set_local $0
+          (call $check)
+         )
+        )
+        (drop
+         (i32.const 10)
+        )
+       )
+       (block
+        (call $print
+         (i32.const 1)
+        )
+        (set_local $0
+         (call $check)
+        )
+       )
+      )
+      (drop
+       (i32.const 11)
+      )
+     )
+     (block
+      (block
+       (call $print
+        (i32.const 1)
+       )
+       (set_local $0
+        (call $check)
+       )
+      )
+      (block
+       (call $print
+        (i32.const 1)
+       )
+       (set_local $0
+        (call $check)
+       )
+      )
+     )
+    )
+    (drop
+     (i32.const 12)
+    )
+   )
+   (block
+    (call $print
+     (i32.const 1)
+    )
+    (set_local $0
+     (call $check)
+    )
+   )
+  )
+ )
+)
diff --git a/test/passes/1.txt b/test/passes/1.txt
index 3fc55487a..7b6f4f249 100644
--- a/test/passes/1.txt
+++ b/test/passes/1.txt
@@ -115,11 +115,11 @@
   (call $before-and-after
    (i32.const 8)
   )
-  (loop $shape$7$continue
+  (loop $shape$4$continue
    (call $before-and-after
     (i32.const 9)
    )
-   (br_if $shape$7$continue
+   (br_if $shape$4$continue
     (get_local $0)
    )
   )
diff --git a/test/passes/flatten_rereloop.txt b/test/passes/flatten_rereloop.txt
index c25505ec9..c7bf7507d 100644
--- a/test/passes/flatten_rereloop.txt
+++ b/test/passes/flatten_rereloop.txt
@@ -216,14 +216,9 @@
  )
  (func $merging (; 7 ;) (type $2)
   (local $0 i32)
-  (block $block$2$break
-   (block
-   )
+  (block
    (block
-    (br $block$2$break)
    )
-  )
-  (block
    (return)
   )
  )
@@ -266,32 +261,27 @@
   (local $0 i32)
   (local $1 i32)
   (local $2 i32)
-  (block $block$2$break
+  (block
    (block
    )
    (block
-    (br $block$2$break)
    )
   )
-  (block
+  (if
+   (i32.const 1)
    (block
+    (unreachable)
    )
-   (if
-    (i32.const 1)
-    (block
-     (unreachable)
-    )
+   (block
     (block
-     (block
-      (set_local $0
-       (i32.const 0)
-      )
-      (set_local $1
-       (get_local $0)
-      )
-      (return
-       (get_local $1)
-      )
+     (set_local $0
+      (i32.const 0)
+     )
+     (set_local $1
+      (get_local $0)
+     )
+     (return
+      (get_local $1)
      )
     )
    )
@@ -309,16 +299,11 @@
    (if
     (i32.const 0)
     (block
-     (block $block$3$break
+     (block
       (set_local $0
        (f32.const 9223372036854775808)
       )
       (block
-       (br $block$3$break)
-      )
-     )
-     (block
-      (block
        (set_local $1
         (get_local $0)
        )
@@ -326,9 +311,9 @@
         (get_local $1)
        )
       )
-      (block
-       (br $block$7$break)
-      )
+     )
+     (block
+      (br $block$7$break)
      )
     )
     (block
diff --git a/test/passes/rereloop.txt b/test/passes/rereloop.txt
index fc4d5151e..51ec694d7 100644
--- a/test/passes/rereloop.txt
+++ b/test/passes/rereloop.txt
@@ -187,21 +187,16 @@
  )
  (func $before-and-after (; 9 ;) (type $3) (param $x i32)
   (local $1 i32)
-  (block $block$2$break
+  (block $block$3$break
    (block
-    (call $before-and-after
-     (i32.const 1)
-    )
-    (call $before-and-after
-     (i32.const 2)
+    (block
+     (call $before-and-after
+      (i32.const 1)
+     )
+     (call $before-and-after
+      (i32.const 2)
+     )
     )
-   )
-   (block
-    (br $block$2$break)
-   )
-  )
-  (block
-   (block $block$3$break
     (block
      (call $before-and-after
       (i32.const 3)
@@ -210,189 +205,169 @@
       (i32.const 4)
      )
     )
-    (if
-     (get_local $x)
-     (br $block$3$break)
+   )
+   (if
+    (get_local $x)
+    (br $block$3$break)
+    (block
+     (call $before-and-after
+      (i32.const 5)
+     )
+     (block
+      (br $block$3$break)
+     )
+    )
+   )
+  )
+  (block
+   (block $block$7$break
+    (block
      (block
       (call $before-and-after
-       (i32.const 5)
+       (i32.const 6)
       )
-      (block
-       (br $block$3$break)
+      (call $before-and-after
+       (i32.const 7)
       )
      )
-    )
-   )
-   (block
-    (block $block$5$break
      (call $before-and-after
-      (i32.const 6)
-     )
-     (block
-      (br $block$5$break)
+      (i32.const 8)
      )
     )
     (block
-     (block $block$6$break
+     (br $block$7$break)
+    )
+   )
+   (block
+    (block $block$8$break
+     (loop $shape$4$continue
       (call $before-and-after
-       (i32.const 7)
+       (i32.const 9)
       )
-      (block
-       (br $block$6$break)
+      (if
+       (get_local $x)
+       (br $shape$4$continue)
+       (br $block$8$break)
       )
      )
-     (block
-      (block $block$7$break
+    )
+    (block
+     (block $block$10$break
+      (block
+       (call $before-and-after
+        (i32.const 10)
+       )
        (call $before-and-after
-        (i32.const 8)
+        (i32.const 11)
        )
+      )
+      (if
+       (get_local $x)
        (block
-        (br $block$7$break)
+        (call $before-and-after
+         (i32.const 12)
+        )
+        (block
+         (br $block$10$break)
+        )
        )
+       (br $block$10$break)
       )
-      (block
-       (block $block$8$break
-        (loop $shape$7$continue
+     )
+     (block
+      (block $block$13$break
+       (call $before-and-after
+        (i32.const 13)
+       )
+       (if
+        (get_local $x)
+        (block
+         (call $before-and-after
+          (i32.const 14)
+         )
+         (block
+          (br $block$13$break)
+         )
+        )
+        (block
          (call $before-and-after
-          (i32.const 9)
+          (i32.const 15)
          )
-         (if
-          (get_local $x)
-          (br $shape$7$continue)
-          (br $block$8$break)
+         (block
+          (br $block$13$break)
          )
         )
        )
-       (block
-        (block $block$10$break
+      )
+      (block
+       (block $block$16$break
+        (block
+        )
+        (if
+         (get_local $x)
          (block
           (call $before-and-after
-           (i32.const 10)
-          )
-          (call $before-and-after
-           (i32.const 11)
+           (i32.const 16)
           )
-         )
-         (if
-          (get_local $x)
           (block
-           (call $before-and-after
-            (i32.const 12)
-           )
-           (block
-            (br $block$10$break)
-           )
+           (br $block$16$break)
           )
-          (br $block$10$break)
          )
+         (br $block$16$break)
         )
-        (block
-         (block $block$13$break
-          (call $before-and-after
-           (i32.const 13)
-          )
-          (if
-           (get_local $x)
+       )
+       (block
+        (block $block$19$break
+         (block
+          (block
            (block
             (call $before-and-after
-             (i32.const 14)
-            )
-            (block
-             (br $block$13$break)
+             (i32.const 17)
             )
-           )
-           (block
             (call $before-and-after
-             (i32.const 15)
+             (i32.const 18)
             )
-            (block
-             (br $block$13$break)
+            (call $before-and-after
+             (i32.const 19)
             )
            )
+           (call $before-and-after
+            (i32.const 20)
+           )
+          )
+          (block
+           (call $before-and-after
+            (i32.const 21)
+           )
+           (call $before-and-after
+            (i32.const 22)
+           )
           )
          )
          (block
-          (block $block$16$break
-           (block
+          (br $block$19$break)
+         )
+        )
+        (block
+         (block $block$21$break
+          (block
+           (call $before-and-after
+            (i32.const 23)
            )
-           (if
-            (get_local $x)
-            (block
-             (call $before-and-after
-              (i32.const 16)
-             )
-             (block
-              (br $block$16$break)
-             )
-            )
-            (br $block$16$break)
+           (call $before-and-after
+            (i32.const 24)
            )
           )
           (block
-           (block $block$18$break
-            (block
-             (call $before-and-after
-              (i32.const 17)
-             )
-             (call $before-and-after
-              (i32.const 18)
-             )
-             (call $before-and-after
-              (i32.const 19)
-             )
-            )
-            (block
-             (br $block$18$break)
-            )
-           )
-           (block
-            (block $block$17$break
-             (call $before-and-after
-              (i32.const 20)
-             )
-             (block
-              (br $block$17$break)
-             )
-            )
-            (block
-             (block $block$19$break
-              (block
-               (call $before-and-after
-                (i32.const 21)
-               )
-               (call $before-and-after
-                (i32.const 22)
-               )
-              )
-              (block
-               (br $block$19$break)
-              )
-             )
-             (block
-              (block $block$21$break
-               (block
-                (call $before-and-after
-                 (i32.const 23)
-                )
-                (call $before-and-after
-                 (i32.const 24)
-                )
-               )
-               (block
-                (br $block$21$break)
-               )
-              )
-              (block
-               (block
-                (call $before-and-after
-                 (i32.const 25)
-                )
-                (return)
-               )
-              )
-             )
-            )
+           (br $block$21$break)
+          )
+         )
+         (block
+          (block
+           (call $before-and-after
+            (i32.const 25)
            )
+           (return)
           )
          )
         )
@@ -441,15 +416,10 @@
     )
    )
    (block
-    (block $block$2$break
+    (block
      (call $switch
       (i32.const 3)
      )
-     (block
-      (br $block$2$break)
-     )
-    )
-    (block
      (return)
     )
    )
@@ -579,29 +549,21 @@
  (export "two" (func $1))
  (func $0 (; 0 ;) (type $0)
   (local $0 i32)
-  (block $block$4$break
+  (block
+  )
+  (if
+   (i32.const 1)
    (block
+    (return)
    )
-   (if
-    (i32.const 1)
-    (block
-     (return)
-    )
-    (br $block$4$break)
-   )
-  )
-  (block
-   (block $block$3$break
-    (set_global $global$0
-     (i32.const 0)
-    )
+   (block
     (block
-     (br $block$3$break)
+     (set_global $global$0
+      (i32.const 0)
+     )
+     (unreachable)
     )
    )
-   (block
-    (unreachable)
-   )
   )
  )
  (func $1 (; 1 ;) (type $1) (result i32)