[Outlining] HashStringifyWalker (#5810)

This PR is part of the effort to bring Outlining to Binaryen.

HashStringifyWalker is a subclass of StringifyWalker #5772, and used to encode a wasm module as a "string". Our "string" is a vector and each symbol is a uint64_t, providing us with a capacity of 2^64 symbols.

1 files changed, 42 insertions, 1 deletions

diff --git a/src/passes/stringify-walker.h b/src/passes/stringify-walker.h
index a7fa02b0b..a56a033d6 100644
--- a/src/passes/stringify-walker.h
+++ b/src/passes/stringify-walker.h
@@ -3,6 +3,7 @@
 
 #include "ir/iteration.h"
 #include "ir/module-utils.h"
+#include "ir/utils.h"
 #include "wasm-traversal.h"
 #include <queue>
 
@@ -36,7 +37,7 @@ namespace wasm {
  *     after the rest of the siblings of the if expression on line 2 are visited
  *   - The if-condition (i32.const 0) on line 3 is visited before the if
  *     expression on line 2. Similarly, the if-condition (i32.const 1) on line
- *     11 is visisted before the if expression on line 10.
+ *     11 is visited before the if expression on line 10.
  *   - The add (line 7) binary operator's left and right children (lines 8 - 9)
  *     are visited first as they need to be on the stack before the add
  *     operation is executed
@@ -75,4 +76,44 @@ private:
 
 #include "stringify-walker-impl.h"
 
+namespace wasm {
+
+// This custom hasher conforms to std::hash<Key>. Its purpose is to provide
+// a custom hash for if expressions, so the if-condition of the if expression is
+// not included in the hash for the if expression. This is needed because in the
+// binary format, the if-condition comes before and is consumed by the if. To
+// match the binary format, we hash the if condition before and separately from
+// the rest of the if expression.
+struct StringifyHasher {
+  size_t operator()(Expression* curr) const;
+};
+
+// This custom equator conforms to std::equal_to<Key>. Similar to
+// StringifyHasher, it's purpose is to not include the if-condition when
+// evaluating the equality of two if expressions.
+struct StringifyEquator {
+  bool operator()(Expression* lhs, Expression* rhs) const;
+};
+
+struct HashStringifyWalker : public StringifyWalker<HashStringifyWalker> {
+  // After calling walkModule, this vector contains the result of encoding a
+  // wasm module as a string of uint64_t values. Each value represents either an
+  // Expression or a separator to mark the end of control flow.
+  std::vector<uint64_t> hashString;
+  // A monotonic counter used to ensure that unique expressions in the
+  // module are assigned a unique value in the hashString
+  uint64_t nextVal = 0;
+  // Contains a mapping of expression pointer to value to ensure we
+  // use the same value for matching expressions. A custom hasher and
+  // equator is provided in order to separate out evaluation of the if-condition
+  // when evaluating if expressions.
+  std::unordered_map<Expression*, uint64_t, StringifyHasher, StringifyEquator>
+    exprToCounter;
+
+  void addUniqueSymbol();
+  void visitExpression(Expression* curr);
+};
+
+} // namespace wasm
+
 #endif // wasm_passes_stringify_walker_h