[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, 93 insertions, 2 deletions

diff --git a/test/gtest/stringify.cpp b/test/gtest/stringify.cpp
index b96235cb6..06d5ccb0c 100644
--- a/test/gtest/stringify.cpp
+++ b/test/gtest/stringify.cpp
@@ -1,8 +1,6 @@
 #include "ir/utils.h"
 #include "passes/stringify-walker.h"
 #include "print-test.h"
-#include "wasm.h"
-#include "gtest/gtest.h"
 
 using namespace wasm;
 
@@ -125,3 +123,96 @@ adding unique symbol
 
   EXPECT_EQ(ss.str(), stringifyText);
 }
+
+TEST_F(StringifyTest, Stringify) {
+  auto moduleText = R"wasm(
+    (module
+    (func $a
+      (block $block_a
+        (drop (i32.const 20))
+        (drop (i32.const 10))
+      )
+      (block $block_b
+        (drop (if (i32.const 0)
+          (i32.const 40)
+          (i32.const 5)
+        ))
+      )
+      (block $block_c
+        (drop (if (i32.const 1)
+          (i32.const 30)
+        ))
+      )
+      (block $block_d
+        (drop (i32.const 20))
+        (drop (i32.const 10))
+      )
+      (block $block_e
+        (drop (if (i32.const 1)
+          (i32.const 30)
+        ))
+      )
+      (block $block_f
+        (drop (if (i32.const 0)
+          (i32.const 30)
+        ))
+      )
+    )
+   )
+  )wasm";
+
+  Module wasm;
+  parseWast(wasm, moduleText);
+
+  HashStringifyWalker stringify = HashStringifyWalker();
+  stringify.walkModule(&wasm);
+
+  EXPECT_EQ(stringify.hashString,
+            (std::vector<uint64_t>{
+              0,             // function block evaluated as a whole
+              (uint64_t)-1,  // separate function block from function contents
+              2,             // block_a evaluated as a whole
+              3,             // block_b evaluated as a whole
+              4,             // block_c evaluated as a whole
+              2,             // block_d has the same contents as block_a
+              4,             // block_e has the same contents as block_c
+              5,             // block_f evaluated as a whole
+              (uint64_t)-6,  // separate blocks from block contents
+              7,             // i32.const 20
+              8,             // drop, all drops will be the same symbol
+              9,             // i32.const 10
+              8,             // drop
+              (uint64_t)-10, // separate block_a contents
+              11,            // i32.const 0, if condition
+              12,            // block_b's if evaluated as a whole
+              8,             // drop
+              (uint64_t)-13, // separate block_b contents
+              14,            // i32.const 1, if condition
+              15,            // block_c's if evaluated as a whole
+              8,             // drop
+              (uint64_t)-16, // separate block_c contents
+              7,             // i32.const 20
+              8,             // drop
+              9,             // i32.const 10
+              8,             // drop
+              (uint64_t)-17, // separate block_d contents
+              14,            // i32.const 1, if condition
+              15,            // block_e if evaluated as a whole
+              8,             // drop
+              (uint64_t)-18, // separate block_e contents
+              11,            // i32.const 0, if condition
+              15,            // block_f's if evaluated as a whole
+              8,             // drop
+              (uint64_t)-19, // separate block_f contents
+              20,            // i32.const 40
+              (uint64_t)-21, // separate block_b if-true
+              22,            // i32.const 5
+              (uint64_t)-23, // separate block_b if-false
+              24,            // i32.const 30
+              (uint64_t)-25, // separate block_c if-true
+              24,            // i32.const 30
+              (uint64_t)-26, // separate block_e if-true
+              24,            // i32.const 30
+              (uint64_t)-27  // separate block_f if-true
+            }));
+}