Souper integration + DataFlow optimizations (#1638)

Background: google/souper#323

This adds a --souperify pass, which emits Souper IR in text format. That can then be read by Souper which can emit superoptimization rules. We hope that eventually we can integrate those rules into Binaryen.

How this works is we emit an internal "DataFlow IR", which is an SSA-based IR, and then write that out into Souper text.

This also adds a --dfo pass, which stands for data-flow optimizations. A DataFlow IR is generated, like in souperify, and then performs some trivial optimizations using it. There are very few things that can do that our other optimizations can't already, but this is also good testing for the DataFlow IR, plus it is good preparation for using Souper's superoptimization output (which would also construct DataFlow IR, like here, but then do some matching on the Souper rules).

1 files changed, 14 insertions, 0 deletions

diff --git a/src/ir/utils.h b/src/ir/utils.h
index 92bfcdab3..61d8917be 100644
--- a/src/ir/utils.h
+++ b/src/ir/utils.h
@@ -58,6 +58,7 @@ struct ExpressionAnalyzer {
   using ExprComparer = std::function<bool(Expression*, Expression*)>;
   static bool flexibleEqual(Expression* left, Expression* right, ExprComparer comparer);
 
+  // Compares two expressions for equivalence.
   static bool equal(Expression* left, Expression* right) {
     auto comparer = [](Expression* left, Expression* right) {
       return false;
@@ -65,6 +66,19 @@ struct ExpressionAnalyzer {
     return flexibleEqual(left, right, comparer);
   }
 
+  // A shallow comparison, ignoring child nodes.
+  static bool shallowEqual(Expression* left, Expression* right) {
+    auto comparer = [left, right](Expression* currLeft, Expression* currRight) {
+      if (currLeft == left && currRight == right) {
+        // these are the ones we want to compare
+        return false;
+      }
+      // otherwise, don't do the comparison, we don't care
+      return true;
+    };
+    return flexibleEqual(left, right, comparer);
+  }
+
   // hash an expression, ignoring superficial details like specific internal names
   static uint32_t hash(Expression* curr);
 };