Merge pull request #449 from WebAssembly/fuzz-relooper

Fuzz the relooper through the c api

8 files changed, 857 insertions, 29 deletions

diff --git a/scripts/fuzz_relooper.py b/scripts/fuzz_relooper.py
new file mode 100644
index 000000000..c8108da95
--- /dev/null
+++ b/scripts/fuzz_relooper.py
@@ -0,0 +1,282 @@
+#! /usr/bin/env python
+
+#   Copyright 2016 WebAssembly Community Group participants
+#
+#   Licensed under the Apache License, Version 2.0 (the "License");
+#   you may not use this file except in compliance with the License.
+#   You may obtain a copy of the License at
+#
+#       http://www.apache.org/licenses/LICENSE-2.0
+#
+#   Unless required by applicable law or agreed to in writing, software
+#   distributed under the License is distributed on an "AS IS" BASIS,
+#   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+#   See the License for the specific language governing permissions and
+#   limitations under the License.
+
+'''
+This fuzzes the relooper using the C API.
+'''
+
+import difflib
+import os
+import random
+import subprocess
+
+if os.environ.get('LD_LIBRARY_PATH'):
+  os.environ['LD_LIBRARY_PATH'] += os.pathsep + 'lib'
+else:
+  os.environ['LD_LIBRARY_PATH'] = 'lib'
+
+while True:
+  # Random decisions
+  num = random.randint(2, 100)  # TODO: 250+
+  density = random.random() * random.random()
+  decisions = [random.randint(1, num * 20) for x in range(num * 3)]
+  branches = [0] * num
+  defaults = [0] * num
+  for i in range(num):
+    b = set([])
+    bs = random.randint(1, max(1,
+                               round(density * random.random() * (num - 1))))
+    for j in range(bs):
+      b.add(random.randint(1, num - 1))
+    b = list(b)
+    defaults[i] = random.choice(b)
+    b.remove(defaults[i])
+    branches[i] = b
+  optimize = random.random() < 0.5
+  print num, density, optimize
+
+  for temp in ['fuzz.wasm', 'fuzz.wast', 'fast.txt', 'fuzz.slow.js',
+               'fuzz.cpp']:
+    try:
+      os.unlink(temp)
+    except:
+      pass
+
+  # parts
+  entry = '''
+var label = 0;
+var state;
+var decisions = %s;
+var index = 0;
+function check() {
+  if (index == decisions.length) throw 'HALT';
+  console.log('(i32.const ' + (-decisions[index]) + ')');
+  return decisions[index++];
+}
+''' % str(decisions)
+
+  slow = entry + '\n'
+  slow += 'label = 0;\n'
+
+  slow += '''
+while(1) switch(label) {
+'''
+
+  fast = '''
+
+#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,
+      BinaryenEq(),
+      BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(),
+                   BinaryenConst(module, BinaryenLiteralInt32(4))),
+      BinaryenConst(module, BinaryenLiteralInt32(4 * %d)) // jumps of 4 bytes
+    ),
+    BinaryenUnreachable(module),
+    NULL
+  );
+  // increment index
+  BinaryenExpressionRef incer = BinaryenStore(module,
+    4, 0, 0,
+    BinaryenConst(module, BinaryenLiteralInt32(4)),
+    BinaryenBinary(module,
+      BinaryenAdd(),
+      BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(),
+                   BinaryenConst(module, BinaryenLiteralInt32(4))),
+      BinaryenConst(module, BinaryenLiteralInt32(4))
+    )
+  );
+
+  // optionally, print the return value
+  BinaryenExpressionRef args[] = {
+    BinaryenBinary(module,
+      BinaryenSub(),
+      BinaryenConst(module, BinaryenLiteralInt32(0)),
+      BinaryenLoad(module,
+        4, 0, 4, 0, BinaryenInt32(),
+        BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(),
+                     BinaryenConst(module, BinaryenLiteralInt32(4)))
+      )
+    )
+  };
+  BinaryenExpressionRef debugger;
+  if (1) debugger = BinaryenCallImport(module, "print", args, 1,
+                                       BinaryenNone());
+  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, BinaryenInt32(),
+    BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(),
+    BinaryenConst(module, BinaryenLiteralInt32(4)))
+  );
+  BinaryenExpressionRef checkBodyList[] = { halter, incer, debugger,
+                                            returner };
+  BinaryenExpressionRef checkBody = BinaryenBlock(module,
+    NULL, checkBodyList, sizeof(checkBodyList) / sizeof(BinaryenExpressionRef)
+  );
+  BinaryenFunctionTypeRef i = BinaryenAddFunctionType(module, "i",
+                                                      BinaryenInt32(),
+                                                      NULL, 0);
+  BinaryenAddFunction(module, "check", i, NULL, 0, checkBody);
+
+  // contents of main() begin here
+
+  RelooperRef relooper = RelooperCreate();
+
+''' % len(decisions)
+
+  for i in range(0, num):
+    slow += '  case %d: console.log("(i32.const %d)"); state = check(); \n' % (
+            i, i)
+    b = branches[i]
+    for j in range(len(b)):
+      slow += '    if (state %% %d == %d) { label = %d; break }\n' % (
+              len(b) + 1, j, b[j])  # TODO: split range 1-n into these options
+    slow += '    label = %d; break\n' % defaults[i]
+
+  for i in range(num):
+    fast += '''
+  RelooperBlockRef b%d;
+  {
+    BinaryenExpressionRef args[] = {
+      BinaryenConst(module, BinaryenLiteralInt32(%d))
+    };
+    BinaryenExpressionRef list[] = {
+      BinaryenCallImport(module, "print", args, 1, BinaryenNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0,
+                                               BinaryenInt32()))
+    };
+    b%d = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2));
+  }
+''' % (i, i, i)
+
+  for i in range(num):
+    b = branches[i]
+    for j in range(len(b)):
+      fast += '''
+  RelooperAddBranch(b%d, b%d, BinaryenBinary(module,
+    BinaryenEq(),
+    BinaryenBinary(module,
+      BinaryenRemU(),
+      BinaryenGetLocal(module, 0, BinaryenInt32()),
+      BinaryenConst(module, BinaryenLiteralInt32(%d))
+    ),
+    BinaryenConst(module, BinaryenLiteralInt32(%d))
+  ), NULL);
+''' % (i, b[j], len(b) + 1, j)
+    fast += '''
+  RelooperAddBranch(b%d, b%d, NULL, NULL);
+''' % (i, defaults[i])
+
+  fast += '''
+  BinaryenExpressionRef body = RelooperRenderAndDispose(relooper, b0, 1,
+                                                        module);
+
+  int decisions[] = { %s };
+  int numDecisions = sizeof(decisions)/sizeof(int);
+
+  // write out all the decisions, then the body of the function
+  BinaryenExpressionRef full[numDecisions + 1];
+
+  for (int i = 0; i < numDecisions; i++) {
+    full[i] = BinaryenStore(module,
+      4, 0, 0,
+      BinaryenConst(module, BinaryenLiteralInt32(8 + 4 * i)),
+      BinaryenConst(module, BinaryenLiteralInt32(decisions[i]))
+    );
+  }
+  full[numDecisions] = body;
+  BinaryenExpressionRef all = BinaryenBlock(module, NULL, full,
+                                            numDecisions + 1);
+
+  BinaryenFunctionTypeRef v = BinaryenAddFunctionType(module, "v",
+                                                      BinaryenNone(),
+                                                      NULL, 0);
+  // locals: state, free-for-label
+  BinaryenType localTypes[] = { BinaryenInt32(), BinaryenInt32() };
+  BinaryenFunctionRef theMain = BinaryenAddFunction(module, "main", v,
+                                                    localTypes, 2, all);
+  BinaryenSetStart(module, theMain);
+
+  // import
+
+  BinaryenType iparams[] = { BinaryenInt32() };
+  BinaryenFunctionTypeRef vi = BinaryenAddFunctionType(module, "vi",
+                                                       BinaryenNone(),
+                                                       iparams, 1);
+  BinaryenAddImport(module, "print", "spectest", "print", vi);
+
+  // memory
+  BinaryenSetMemory(module, 1, 1, "mem", NULL, NULL, NULL, 0);
+
+  // optionally, optimize
+  if (%d) BinaryenModuleOptimize(module);
+
+  assert(BinaryenModuleValidate(module));
+
+  // write it out
+
+  BinaryenModulePrint(module);
+
+  BinaryenModuleDispose(module);
+
+  return 0;
+}
+''' % (', '.join(map(str, decisions)), optimize)
+
+  slow += '}'
+
+  open('fuzz.slow.js', 'w').write(slow)
+  open('fuzz.cpp', 'w').write(fast)
+
+  print '.'
+  cmd = ['g++', 'fuzz.cpp', '-Isrc', '-g', '-lbinaryen-c', '-lasmjs',
+         '-lsupport', '-Llib/.', '-pthread', '-o', 'fuzz', '-g']
+  subprocess.check_call(cmd)
+  print '^'
+  subprocess.check_call(['./fuzz'], stdout=open('fuzz.wast', 'w'))
+  print '*'
+  subprocess.call(['bin/binaryen-shell', 'fuzz.wast'],
+                  stdout=open('fast.txt', 'w'), stderr=subprocess.PIPE)
+  fast_out = open('fast.txt').read()
+  print '-'
+  slow_out = subprocess.Popen(['nodejs', 'fuzz.slow.js'],
+                              stdout=subprocess.PIPE,
+                              stderr=subprocess.PIPE).communicate()[0]
+  print '_'
+
+  if slow_out != fast_out:
+    print ''.join([a.rstrip() + '\n' for a in difflib.unified_diff(
+          slow_out.split('\n'),
+          fast_out.split('\n'),
+          fromfile='slow',
+          tofile='fast')])
+    assert False
diff --git a/src/binaryen-c.cpp b/src/binaryen-c.cpp
index d46125bb3..eca4ce5f1 100644
--- a/src/binaryen-c.cpp
+++ b/src/binaryen-c.cpp
@@ -209,21 +209,23 @@ BinaryenExpressionRef BinaryenSwitch(BinaryenModuleRef module, const char **name
   ret->finalize();
   return ret;
 }
-BinaryenExpressionRef BinaryenCall(BinaryenModuleRef module, const char *target, BinaryenExpressionRef* operands, BinaryenIndex numOperands) {
+BinaryenExpressionRef BinaryenCall(BinaryenModuleRef module, const char *target, BinaryenExpressionRef* operands, BinaryenIndex numOperands, BinaryenType returnType) {
   auto* ret = ((Module*)module)->allocator.alloc<Call>();
   ret->target = target;
   for (BinaryenIndex i = 0; i < numOperands; i++) {
     ret->operands.push_back((Expression*)operands[i]);
   }
+  ret->type = WasmType(returnType);
   ret->finalize();
   return ret;
 }
-BinaryenExpressionRef BinaryenCallImport(BinaryenModuleRef module, const char *target, BinaryenExpressionRef* operands, BinaryenIndex numOperands) {
+BinaryenExpressionRef BinaryenCallImport(BinaryenModuleRef module, const char *target, BinaryenExpressionRef* operands, BinaryenIndex numOperands, BinaryenType returnType) {
   auto* ret = ((Module*)module)->allocator.alloc<CallImport>();
   ret->target = target;
   for (BinaryenIndex i = 0; i < numOperands; i++) {
     ret->operands.push_back((Expression*)operands[i]);
   }
+  ret->type = WasmType(returnType);
   ret->finalize();
   return ret;
 }
diff --git a/src/binaryen-c.h b/src/binaryen-c.h
index da445dfb2..583454a9f 100644
--- a/src/binaryen-c.h
+++ b/src/binaryen-c.h
@@ -199,8 +199,12 @@ BinaryenExpressionRef BinaryenLoop(BinaryenModuleRef module, const char* out, co
 BinaryenExpressionRef BinaryenBreak(BinaryenModuleRef module, const char* name, BinaryenExpressionRef condition, BinaryenExpressionRef value);
 // Switch: value can be NULL
 BinaryenExpressionRef BinaryenSwitch(BinaryenModuleRef module, const char **names, BinaryenIndex numNames, const char* defaultName, BinaryenExpressionRef condition, BinaryenExpressionRef value);
-BinaryenExpressionRef BinaryenCall(BinaryenModuleRef module, const char *target, BinaryenExpressionRef* operands, BinaryenIndex numOperands);
-BinaryenExpressionRef BinaryenCallImport(BinaryenModuleRef module, const char *target, BinaryenExpressionRef* operands, BinaryenIndex numOperands);
+// Call, CallImport: Note the 'returnType' parameter. You must declare the
+//                   type returned by the function being called, as that
+//                   function might not have been created yet, so we don't
+//                   know what it is.
+BinaryenExpressionRef BinaryenCall(BinaryenModuleRef module, const char *target, BinaryenExpressionRef* operands, BinaryenIndex numOperands, BinaryenType returnType);
+BinaryenExpressionRef BinaryenCallImport(BinaryenModuleRef module, const char *target, BinaryenExpressionRef* operands, BinaryenIndex numOperands, BinaryenType returnType);
 BinaryenExpressionRef BinaryenCallIndirect(BinaryenModuleRef module, BinaryenExpressionRef target, BinaryenExpressionRef* operands, BinaryenIndex numOperands, BinaryenFunctionTypeRef type);
 // GetLocal: Note the 'type' parameter. It might seem redundant, since the
 //           local at that index must have a type. However, this API lets you
@@ -214,7 +218,9 @@ BinaryenExpressionRef BinaryenCallIndirect(BinaryenModuleRef module, BinaryenExp
 //           begins.)
 BinaryenExpressionRef BinaryenGetLocal(BinaryenModuleRef module, BinaryenIndex index, BinaryenType type);
 BinaryenExpressionRef BinaryenSetLocal(BinaryenModuleRef module, BinaryenIndex index, BinaryenExpressionRef value);
+// Load: align can be 0, in which case it will be the natural alignment (equal to bytes)
 BinaryenExpressionRef BinaryenLoad(BinaryenModuleRef module, uint32_t bytes, int8_t signed_, uint32_t offset, uint32_t align, BinaryenType type, BinaryenExpressionRef ptr);
+// Store: align can be 0, in which case it will be the natural alignment (equal to bytes)
 BinaryenExpressionRef BinaryenStore(BinaryenModuleRef module, uint32_t bytes, uint32_t offset, uint32_t align, BinaryenExpressionRef ptr, BinaryenExpressionRef value);
 BinaryenExpressionRef BinaryenConst(BinaryenModuleRef module, struct BinaryenLiteral value);
 BinaryenExpressionRef BinaryenUnary(BinaryenModuleRef module, BinaryenOp op, BinaryenExpressionRef value);
@@ -302,10 +308,10 @@ RelooperBlockRef RelooperAddBlock(RelooperRef relooper, BinaryenExpressionRef co
 void RelooperAddBranch(RelooperBlockRef from, RelooperBlockRef to, BinaryenExpressionRef condition, BinaryenExpressionRef code);
 
 // Create a basic block that ends a switch on a condition
-RelooperBlockRef RelooperAddBlockWithSwitch(RelooperRef relooper, BinaryenExpressionRef code, BinaryenExpressionRef condition);
+// TODO RelooperBlockRef RelooperAddBlockWithSwitch(RelooperRef relooper, BinaryenExpressionRef code, BinaryenExpressionRef condition);
 
 // Create a switch-style branch to another basic block. The block's switch table will have an index for this branch
-void RelooperAddBranchForSwitch(RelooperBlockRef from, RelooperBlockRef to, BinaryenIndex index, BinaryenExpressionRef code);
+// TODO void RelooperAddBranchForSwitch(RelooperBlockRef from, RelooperBlockRef to, BinaryenIndex index, BinaryenExpressionRef code);
 
 // Generate structed wasm control flow from the CFG of blocks and branches that were created
 // on this relooper instance. This returns the rendered output, and also disposes of the
diff --git a/src/wasm.h b/src/wasm.h
index dff0bcd5a..049dc2e30 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -1022,6 +1022,10 @@ public:
   ExpressionList operands;
   FunctionType *fullType;
   Expression *target;
+
+  void finalize() {
+    type = fullType->result;
+  }
 };
 
 class GetLocal : public SpecificExpression<Expression::GetLocalId> {
diff --git a/test/example/c-api-kitchen-sink.c b/test/example/c-api-kitchen-sink.c
index 4a63e931d..db1903cfd 100644
--- a/test/example/c-api-kitchen-sink.c
+++ b/test/example/c-api-kitchen-sink.c
@@ -165,9 +165,15 @@ void test_core() {
     BinaryenBreak(module, "the-body", NULL, NULL),
     BinaryenSwitch(module, switchValueNames, 1, "the-value", makeInt32(module, 0), makeInt32(module, 1)),
     BinaryenSwitch(module, switchBodyNames, 1, "the-body", makeInt32(module, 2), NULL),
-    BinaryenCall(module, "kitchen-sinker", callOperands4, 4),
-    BinaryenCallImport(module, "an-imported", callOperands2, 2),
-    BinaryenCallIndirect(module, makeInt32(module, 2449), callOperands4, 4, iiIfF),
+    BinaryenUnary(module, BinaryenEqZ(), // check the output type of the call node
+      BinaryenCall(module, "kitchen-sinker", callOperands4, 4, BinaryenInt32())
+    ),
+    BinaryenUnary(module, BinaryenEqZ(), // check the output type of the call node
+      BinaryenCallImport(module, "an-imported", callOperands2, 2, BinaryenFloat32())
+    ),
+    BinaryenUnary(module, BinaryenEqZ(), // check the output type of the call node
+      BinaryenCallIndirect(module, makeInt32(module, 2449), callOperands4, 4, iiIfF)
+    ),
     BinaryenGetLocal(module, 0, BinaryenInt32()),
     BinaryenSetLocal(module, 0, makeInt32(module, 101)),
     BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(), makeInt32(module, 1)),
@@ -195,8 +201,8 @@ void test_core() {
   // Imports
 
   BinaryenType iparams[2] = { BinaryenInt32(), BinaryenFloat64() };
-  BinaryenFunctionTypeRef viF = BinaryenAddFunctionType(module, "viF", BinaryenNone(), iparams, 2);
-  BinaryenAddImport(module, "an-imported", "module", "base", viF);
+  BinaryenFunctionTypeRef fiF = BinaryenAddFunctionType(module, "fiF", BinaryenFloat32(), iparams, 2);
+  BinaryenAddImport(module, "an-imported", "module", "base", fiF);
 
   // Exports
 
diff --git a/test/example/c-api-kitchen-sink.txt b/test/example/c-api-kitchen-sink.txt
index cb037d80c..7a1366888 100644
--- a/test/example/c-api-kitchen-sink.txt
+++ b/test/example/c-api-kitchen-sink.txt
@@ -10,9 +10,9 @@ BinaryenFloat64: 4
   (export "mem" memory)
   (start $starter)
   (type $iiIfF (func (param i32 i64 f32 f64) (result i32)))
-  (type $viF (func (param i32 f64)))
+  (type $fiF (func (param i32 f64) (result f32)))
   (type $v (func))
-  (import $an-imported "module" "base" (param i32 f64))
+  (import $an-imported "module" "base" (param i32 f64) (result f32))
   (export "kitchen_sinker" $kitchen-sinker)
   (table $kitchen-sinker)
   (func $kitchen-sinker (type $iiIfF) (param $0 i32) (param $1 i64) (param $2 f32) (param $3 f64) (result i32)
@@ -293,22 +293,28 @@ BinaryenFloat64: 4
         (br_table $the-body $the-body
           (i32.const 2)
         )
-        (call $kitchen-sinker
-          (i32.const 13)
-          (i64.const 37)
-          (f32.const 1.2999999523162842)
-          (f64.const 3.7)
-        )
-        (call_import $an-imported
-          (i32.const 13)
-          (f64.const 3.7)
-        )
-        (call_indirect $iiIfF
-          (i32.const 2449)
-          (i32.const 13)
-          (i64.const 37)
-          (f32.const 1.2999999523162842)
-          (f64.const 3.7)
+        (i32.eqz
+          (call $kitchen-sinker
+            (i32.const 13)
+            (i64.const 37)
+            (f32.const 1.2999999523162842)
+            (f64.const 3.7)
+          )
+        )
+        (f32.eqz
+          (call_import $an-imported
+            (i32.const 13)
+            (f64.const 3.7)
+          )
+        )
+        (i32.eqz
+          (call_indirect $iiIfF
+            (i32.const 2449)
+            (i32.const 13)
+            (i64.const 37)
+            (f32.const 1.2999999523162842)
+            (f64.const 3.7)
+          )
         )
         (get_local $0)
         (set_local $0
diff --git a/test/example/relooper-fuzz.c b/test/example/relooper-fuzz.c
new file mode 100644
index 000000000..ba9bcb3ed
--- /dev/null
+++ b/test/example/relooper-fuzz.c
@@ -0,0 +1,267 @@
+
+
+#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,
+      BinaryenEq(),
+      BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(), BinaryenConst(module, BinaryenLiteralInt32(4))),
+      BinaryenConst(module, BinaryenLiteralInt32(4 * 27)) // jumps of 4 bytes
+    ),
+    BinaryenUnreachable(module),
+    NULL
+  );
+  // increment index
+  BinaryenExpressionRef incer = BinaryenStore(module,
+    4, 0, 0,
+    BinaryenConst(module, BinaryenLiteralInt32(4)),
+    BinaryenBinary(module,
+      BinaryenAdd(),
+      BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(), BinaryenConst(module, BinaryenLiteralInt32(4))),
+      BinaryenConst(module, BinaryenLiteralInt32(4))
+    )
+  );
+
+  // optionally, print the return value
+  BinaryenExpressionRef args[] = {
+    BinaryenBinary(module,
+      BinaryenSub(),
+      BinaryenConst(module, BinaryenLiteralInt32(0)),
+      BinaryenLoad(module,
+        4, 0, 4, 0, BinaryenInt32(),
+        BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(), BinaryenConst(module, BinaryenLiteralInt32(4)))
+      )
+    )
+  };
+  BinaryenExpressionRef debugger;
+  if (1) debugger = BinaryenCallImport(module, "print", args, 1, BinaryenNone());
+  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, BinaryenInt32(),
+    BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(), BinaryenConst(module, BinaryenLiteralInt32(4)))
+  );
+  BinaryenExpressionRef checkBodyList[] = { halter, incer, debugger, returner };
+  BinaryenExpressionRef checkBody = BinaryenBlock(module, NULL, checkBodyList, sizeof(checkBodyList) / sizeof(BinaryenExpressionRef));
+  BinaryenFunctionTypeRef i = BinaryenAddFunctionType(module, "i", BinaryenInt32(), NULL, 0);
+  BinaryenAddFunction(module, "check", i, NULL, 0, checkBody);
+
+  // contents of main() begin here
+
+  RelooperRef relooper = RelooperCreate();
+
+
+  RelooperBlockRef b0;
+  {
+    BinaryenExpressionRef args[] = { BinaryenConst(module, BinaryenLiteralInt32(0)) };
+    BinaryenExpressionRef list[] = {
+      BinaryenCallImport(module, "print", args, 1, BinaryenNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0, BinaryenInt32()))
+    };
+    b0 = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2));
+  }
+
+  RelooperBlockRef b1;
+  {
+    BinaryenExpressionRef args[] = { BinaryenConst(module, BinaryenLiteralInt32(1)) };
+    BinaryenExpressionRef list[] = {
+      BinaryenCallImport(module, "print", args, 1, BinaryenNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0, BinaryenInt32()))
+    };
+    b1 = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2));
+  }
+
+  RelooperBlockRef b2;
+  {
+    BinaryenExpressionRef args[] = { BinaryenConst(module, BinaryenLiteralInt32(2)) };
+    BinaryenExpressionRef list[] = {
+      BinaryenCallImport(module, "print", args, 1, BinaryenNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0, BinaryenInt32()))
+    };
+    b2 = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2));
+  }
+
+  RelooperBlockRef b3;
+  {
+    BinaryenExpressionRef args[] = { BinaryenConst(module, BinaryenLiteralInt32(3)) };
+    BinaryenExpressionRef list[] = {
+      BinaryenCallImport(module, "print", args, 1, BinaryenNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0, BinaryenInt32()))
+    };
+    b3 = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2));
+  }
+
+  RelooperBlockRef b4;
+  {
+    BinaryenExpressionRef args[] = { BinaryenConst(module, BinaryenLiteralInt32(4)) };
+    BinaryenExpressionRef list[] = {
+      BinaryenCallImport(module, "print", args, 1, BinaryenNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0, BinaryenInt32()))
+    };
+    b4 = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2));
+  }
+
+  RelooperBlockRef b5;
+  {
+    BinaryenExpressionRef args[] = { BinaryenConst(module, BinaryenLiteralInt32(5)) };
+    BinaryenExpressionRef list[] = {
+      BinaryenCallImport(module, "print", args, 1, BinaryenNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0, BinaryenInt32()))
+    };
+    b5 = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2));
+  }
+
+  RelooperBlockRef b6;
+  {
+    BinaryenExpressionRef args[] = { BinaryenConst(module, BinaryenLiteralInt32(6)) };
+    BinaryenExpressionRef list[] = {
+      BinaryenCallImport(module, "print", args, 1, BinaryenNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0, BinaryenInt32()))
+    };
+    b6 = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2));
+  }
+
+  RelooperBlockRef b7;
+  {
+    BinaryenExpressionRef args[] = { BinaryenConst(module, BinaryenLiteralInt32(7)) };
+    BinaryenExpressionRef list[] = {
+      BinaryenCallImport(module, "print", args, 1, BinaryenNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0, BinaryenInt32()))
+    };
+    b7 = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2));
+  }
+
+  RelooperBlockRef b8;
+  {
+    BinaryenExpressionRef args[] = { BinaryenConst(module, BinaryenLiteralInt32(8)) };
+    BinaryenExpressionRef list[] = {
+      BinaryenCallImport(module, "print", args, 1, BinaryenNone()),
+      BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0, BinaryenInt32()))
+    };
+    b8 = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2));
+  }
+
+  RelooperAddBranch(b0, b5, BinaryenBinary(module,
+    BinaryenEq(),
+    BinaryenBinary(module,
+      BinaryenRemU(),
+      BinaryenGetLocal(module, 0, BinaryenInt32()),
+      BinaryenConst(module, BinaryenLiteralInt32(2))
+    ),
+    BinaryenConst(module, BinaryenLiteralInt32(0))
+  ), NULL);
+
+  RelooperAddBranch(b0, b8, NULL, NULL);
+
+  RelooperAddBranch(b1, b5, NULL, NULL);
+
+  RelooperAddBranch(b2, b5, NULL, NULL);
+
+  RelooperAddBranch(b3, b5, BinaryenBinary(module,
+    BinaryenEq(),
+    BinaryenBinary(module,
+      BinaryenRemU(),
+      BinaryenGetLocal(module, 0, BinaryenInt32()),
+      BinaryenConst(module, BinaryenLiteralInt32(2))
+    ),
+    BinaryenConst(module, BinaryenLiteralInt32(0))
+  ), NULL);
+
+  RelooperAddBranch(b3, b8, NULL, NULL);
+
+  RelooperAddBranch(b4, b4, BinaryenBinary(module,
+    BinaryenEq(),
+    BinaryenBinary(module,
+      BinaryenRemU(),
+      BinaryenGetLocal(module, 0, BinaryenInt32()),
+      BinaryenConst(module, BinaryenLiteralInt32(3))
+    ),
+    BinaryenConst(module, BinaryenLiteralInt32(0))
+  ), NULL);
+
+  RelooperAddBranch(b4, b5, BinaryenBinary(module,
+    BinaryenEq(),
+    BinaryenBinary(module,
+      BinaryenRemU(),
+      BinaryenGetLocal(module, 0, BinaryenInt32()),
+      BinaryenConst(module, BinaryenLiteralInt32(3))
+    ),
+    BinaryenConst(module, BinaryenLiteralInt32(1))
+  ), NULL);
+
+  RelooperAddBranch(b4, b2, NULL, NULL);
+
+  RelooperAddBranch(b5, b4, BinaryenBinary(module,
+    BinaryenEq(),
+    BinaryenBinary(module,
+      BinaryenRemU(),
+      BinaryenGetLocal(module, 0, BinaryenInt32()),
+      BinaryenConst(module, BinaryenLiteralInt32(2))
+    ),
+    BinaryenConst(module, BinaryenLiteralInt32(0))
+  ), NULL);
+
+  RelooperAddBranch(b5, b5, NULL, NULL);
+
+  RelooperAddBranch(b6, b6, NULL, NULL);
+
+  RelooperAddBranch(b7, b8, NULL, NULL);
+
+  RelooperAddBranch(b8, b4, NULL, NULL);
+
+  BinaryenExpressionRef body = RelooperRenderAndDispose(relooper, b0, 1, module);
+
+  int decisions[] = { 89, 12, 78, 149, 118, 179, 127, 80, 21, 34, 119, 98, 38, 29, 36, 147, 13, 55, 166, 16, 143, 52, 130, 150, 176, 91, 34 };
+  int numDecisions = sizeof(decisions)/sizeof(int);
+
+  BinaryenExpressionRef full[numDecisions + 1]; // write out all the decisions, then the body of the function
+
+  for (int i = 0; i < numDecisions; i++) {
+    full[i] = BinaryenStore(module,
+      4, 0, 0,
+      BinaryenConst(module, BinaryenLiteralInt32(8 + 4 * i)),
+      BinaryenConst(module, BinaryenLiteralInt32(decisions[i]))
+    );
+  }
+  full[numDecisions] = body;
+  BinaryenExpressionRef all = BinaryenBlock(module, NULL, full, numDecisions + 1);
+
+  BinaryenFunctionTypeRef v = BinaryenAddFunctionType(module, "v", BinaryenNone(), NULL, 0);
+  BinaryenType localTypes[] = { BinaryenInt32(), BinaryenInt32() }; // state, free-for-label
+  BinaryenFunctionRef theMain = BinaryenAddFunction(module, "main", v, localTypes, 2, all);
+  BinaryenSetStart(module, theMain);
+
+  // import
+
+  BinaryenType iparams[] = { BinaryenInt32() };
+  BinaryenFunctionTypeRef vi = BinaryenAddFunctionType(module, "vi", BinaryenNone(), iparams, 1);
+  BinaryenAddImport(module, "print", "spectest", "print", vi);
+
+  // memory
+  BinaryenSetMemory(module, 1, 1, "mem", NULL, NULL, NULL, 0);
+
+  BinaryenModuleOptimize(module);
+
+  assert(BinaryenModuleValidate(module));
+
+  // write it out
+
+  BinaryenModulePrint(module);
+
+  BinaryenModuleDispose(module);
+
+  return 0;
+}
diff --git a/test/example/relooper-fuzz.txt b/test/example/relooper-fuzz.txt
new file mode 100644
index 000000000..7dab4c5be
--- /dev/null
+++ b/test/example/relooper-fuzz.txt
@@ -0,0 +1,255 @@
+(module
+  (memory 1 1)
+  (export "mem" memory)
+  (start $main)
+  (type $i (func (result i32)))
+  (type $v (func))
+  (type $vi (func (param i32)))
+  (import $print "spectest" "print" (param i32))
+  (func $check (type $i) (result i32)
+    (if
+      (i32.eq
+        (i32.load
+          (i32.const 4)
+        )
+        (i32.const 108)
+      )
+      (unreachable)
+    )
+    (i32.store
+      (i32.const 4)
+      (i32.add
+        (i32.load
+          (i32.const 4)
+        )
+        (i32.const 4)
+      )
+    )
+    (call_import $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 (type $v)
+    (local $0 i32)
+    (local $1 i32)
+    (i32.store
+      (i32.const 8)
+      (i32.const 89)
+    )
+    (i32.store
+      (i32.const 12)
+      (i32.const 12)
+    )
+    (i32.store
+      (i32.const 16)
+      (i32.const 78)
+    )
+    (i32.store
+      (i32.const 20)
+      (i32.const 149)
+    )
+    (i32.store
+      (i32.const 24)
+      (i32.const 118)
+    )
+    (i32.store
+      (i32.const 28)
+      (i32.const 179)
+    )
+    (i32.store
+      (i32.const 32)
+      (i32.const 127)
+    )
+    (i32.store
+      (i32.const 36)
+      (i32.const 80)
+    )
+    (i32.store
+      (i32.const 40)
+      (i32.const 21)
+    )
+    (i32.store
+      (i32.const 44)
+      (i32.const 34)
+    )
+    (i32.store
+      (i32.const 48)
+      (i32.const 119)
+    )
+    (i32.store
+      (i32.const 52)
+      (i32.const 98)
+    )
+    (i32.store
+      (i32.const 56)
+      (i32.const 38)
+    )
+    (i32.store
+      (i32.const 60)
+      (i32.const 29)
+    )
+    (i32.store
+      (i32.const 64)
+      (i32.const 36)
+    )
+    (i32.store
+      (i32.const 68)
+      (i32.const 147)
+    )
+    (i32.store
+      (i32.const 72)
+      (i32.const 13)
+    )
+    (i32.store
+      (i32.const 76)
+      (i32.const 55)
+    )
+    (i32.store
+      (i32.const 80)
+      (i32.const 166)
+    )
+    (i32.store
+      (i32.const 84)
+      (i32.const 16)
+    )
+    (i32.store
+      (i32.const 88)
+      (i32.const 143)
+    )
+    (i32.store
+      (i32.const 92)
+      (i32.const 52)
+    )
+    (i32.store
+      (i32.const 96)
+      (i32.const 130)
+    )
+    (i32.store
+      (i32.const 100)
+      (i32.const 150)
+    )
+    (i32.store
+      (i32.const 104)
+      (i32.const 176)
+    )
+    (i32.store
+      (i32.const 108)
+      (i32.const 91)
+    )
+    (i32.store
+      (i32.const 112)
+      (i32.const 34)
+    )
+    (call_import $print
+      (i32.const 0)
+    )
+    (if
+      (i32.eq
+        (i32.rem_u
+          (set_local $0
+            (call $check)
+          )
+          (i32.const 2)
+        )
+        (i32.const 0)
+      )
+      (set_local $1
+        (i32.const 6)
+      )
+      (block
+        (call_import $print
+          (i32.const 8)
+        )
+        (set_local $0
+          (call $check)
+        )
+      )
+    )
+    (loop $shape$3$break $shape$3$continue
+      (if
+        (i32.eq
+          (get_local $1)
+          (i32.const 6)
+        )
+        (block
+          (set_local $1
+            (i32.const 0)
+          )
+          (call_import $print
+            (i32.const 5)
+          )
+          (if
+            (i32.eq
+              (i32.rem_u
+                (set_local $0
+                  (call $check)
+                )
+                (i32.const 2)
+              )
+              (i32.const 0)
+            )
+            (br $shape$3$continue)
+            (block
+              (set_local $1
+                (i32.const 6)
+              )
+              (br $shape$3$continue)
+            )
+          )
+        )
+      )
+      (call_import $print
+        (i32.const 4)
+      )
+      (if
+        (i32.eq
+          (i32.rem_u
+            (set_local $0
+              (call $check)
+            )
+            (i32.const 3)
+          )
+          (i32.const 0)
+        )
+        (br $shape$3$continue)
+        (if
+          (i32.eq
+            (i32.rem_u
+              (get_local $0)
+              (i32.const 3)
+            )
+            (i32.const 1)
+          )
+          (block
+            (set_local $1
+              (i32.const 6)
+            )
+            (br $shape$3$continue)
+          )
+        )
+      )
+      (call_import $print
+        (i32.const 2)
+      )
+      (set_local $0
+        (call $check)
+      )
+      (set_local $1
+        (i32.const 6)
+      )
+      (br $shape$3$continue)
+    )
+  )
+)