Relooper CFG optimizations (#1759)

Previously the relooper would do some optimizations when deciding when to use an if vs a switch, how to group blocks, etc. This PR adds an additional pre-optimization phase with some basic but useful simplify-cfg style passes,

* Skip empty blocks when they have just one exit.
* Merge exiting branches when they are equivalent.
* Canonicalize block contents to make such comparisons more useful.
* Turn a trivial one-target switch into a simple branch.

This can help in noticeable ways when running the rereloop pass, e.g. on LLVM wasm backend output.

Also:

* Binaryen C API changes to the relooper, which now gets a Module for its constructor. It needs it for the optimizations, as it may construct new nodes.
* Many relooper-fuzzer improvements.
* Clean up HashType usage.

1 files changed, 223 insertions, 0 deletions

diff --git a/test/example/relooper-merge2.c b/test/example/relooper-merge2.c
new file mode 100644
index 000000000..852e75842
--- /dev/null
+++ b/test/example/relooper-merge2.c
@@ -0,0 +1,223 @@
+
+
+#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, target blocks have identical contents (print 1),
+  // and branches have identical phis.
+  {
+    BinaryenIndex indexes[] = { 1, 4, 9 };
+    RelooperAddBranchForSwitch(b0, b1, indexes, 3,
+      BinaryenDrop(module,
+        BinaryenConst(module, BinaryenLiteralInt32(4))
+      )
+    );
+  }
+  {
+    BinaryenIndex indexes[] = { 3, 6 };
+    RelooperAddBranchForSwitch(b0, b2, indexes, 2,
+      BinaryenDrop(module,
+        BinaryenConst(module, BinaryenLiteralInt32(4))
+      )
+    );
+  }
+  {
+    BinaryenIndex indexes[] = { 5, 25, 125 };
+    RelooperAddBranchForSwitch(b0, b3, indexes, 3,
+      BinaryenDrop(module,
+        BinaryenConst(module, BinaryenLiteralInt32(4))
+      )
+    );
+  }
+  RelooperAddBranchForSwitch(b0, b4, NULL, 0, NULL);
+
+  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;
+}