3 files changed, 79 insertions, 3 deletions

diff --git a/src/passes/hash-stringify-walker.cpp b/src/passes/hash-stringify-walker.cpp
index 43cc3d544..beae3bf44 100644
--- a/src/passes/hash-stringify-walker.cpp
+++ b/src/passes/hash-stringify-walker.cpp
@@ -58,11 +58,13 @@ void HashStringifyWalker::addUniqueSymbol(SeparatorReason reason) {
   assert((uint32_t)nextSeparatorVal >= nextVal);
   hashString.push_back((uint32_t)nextSeparatorVal);
   nextSeparatorVal--;
+  exprs.push_back(nullptr);
 }
 
 void HashStringifyWalker::visitExpression(Expression* curr) {
   auto [it, inserted] = exprToCounter.insert({curr, nextVal});
   hashString.push_back(it->second);
+  exprs.push_back(curr);
   if (inserted) {
     nextVal++;
   }
@@ -80,7 +82,7 @@ void HashStringifyWalker::visitExpression(Expression* curr) {
 // repeats come first and 2) these are more worthwhile to keep than subsequent
 // substrings of substrings, even if they appear more times.
 std::vector<SuffixTree::RepeatedSubstring> StringifyProcessor::dedupe(
-  const std::vector<SuffixTree::RepeatedSubstring> substrings) {
+  const std::vector<SuffixTree::RepeatedSubstring>&& substrings) {
   std::unordered_set<uint32_t> seen;
   std::vector<SuffixTree::RepeatedSubstring> result;
   for (auto substring : substrings) {
@@ -108,4 +110,60 @@ std::vector<SuffixTree::RepeatedSubstring> StringifyProcessor::dedupe(
   return result;
 }
 
+std::vector<SuffixTree::RepeatedSubstring> StringifyProcessor::filter(
+  const std::vector<SuffixTree::RepeatedSubstring>&& substrings,
+  const std::vector<Expression*> exprs,
+  std::function<bool(const Expression*)> condition) {
+
+  struct FilterStringifyWalker : public StringifyWalker<FilterStringifyWalker> {
+    bool hasFilterValue = false;
+    std::function<bool(const Expression*)> condition;
+
+    FilterStringifyWalker(std::function<bool(const Expression*)> condition)
+      : condition(condition){};
+
+    void walk(Expression* curr) {
+      hasFilterValue = false;
+      Super::walk(curr);
+    }
+
+    void addUniqueSymbol(SeparatorReason reason) {}
+
+    void visitExpression(Expression* curr) {
+      if (condition(curr)) {
+        hasFilterValue = true;
+      }
+    }
+  };
+
+  FilterStringifyWalker walker(condition);
+
+  std::vector<SuffixTree::RepeatedSubstring> result;
+  for (auto substring : substrings) {
+    bool hasFilterValue = false;
+    for (auto idx = substring.StartIndices[0],
+              endIdx = substring.StartIndices[0] + substring.Length;
+         idx < endIdx;
+         idx++) {
+      Expression* curr = exprs[idx];
+      if (Properties::isControlFlowStructure(curr)) {
+        walker.walk(curr);
+        if (walker.hasFilterValue) {
+          hasFilterValue = true;
+          break;
+        }
+      }
+      if (condition(curr)) {
+        hasFilterValue = true;
+        break;
+      }
+    }
+    if (!hasFilterValue) {
+      result.push_back(substring);
+    }
+  }
+
+  return result;
+}
+
 } // namespace wasm
diff --git a/src/passes/stringify-walker.h b/src/passes/stringify-walker.h
index 129021bc4..55aa26940 100644
--- a/src/passes/stringify-walker.h
+++ b/src/passes/stringify-walker.h
@@ -178,7 +178,6 @@ struct StringifyWalker
 
   void doWalkModule(Module* module);
   void doWalkFunction(Function* func);
-  void walk(Expression* curr);
   static void scan(SubType* self, Expression** currp);
   static void doVisitExpression(SubType* self, Expression** currp);
 
@@ -226,6 +225,7 @@ struct HashStringifyWalker : public StringifyWalker<HashStringifyWalker> {
   // when evaluating if expressions.
   std::unordered_map<Expression*, uint32_t, StringifyHasher, StringifyEquator>
     exprToCounter;
+  std::vector<Expression*> exprs;
 
   void addUniqueSymbol(SeparatorReason reason);
   void visitExpression(Expression* curr);
@@ -234,7 +234,11 @@ struct HashStringifyWalker : public StringifyWalker<HashStringifyWalker> {
 // Functions that filter vectors of SuffixTree::RepeatedSubstring
 struct StringifyProcessor {
   static std::vector<SuffixTree::RepeatedSubstring>
-  dedupe(const std::vector<SuffixTree::RepeatedSubstring>);
+  dedupe(const std::vector<SuffixTree::RepeatedSubstring>&& substrings);
+  static std::vector<SuffixTree::RepeatedSubstring>
+  filter(const std::vector<SuffixTree::RepeatedSubstring>&& substrings,
+         const std::vector<Expression*> exprs,
+         std::function<bool(const Expression*)> condition);
 };
 
 } // namespace wasm
diff --git a/src/support/suffix_tree.h b/src/support/suffix_tree.h
index 4ce61767d..6aa9c2f20 100644
--- a/src/support/suffix_tree.h
+++ b/src/support/suffix_tree.h
@@ -38,6 +38,7 @@
 #include "llvm/Support/Allocator.h"
 #include <cassert>
 #include <cstddef>
+#include <ostream>
 #include <vector>
 
 #include "support/suffix_tree_node.h"
@@ -64,6 +65,19 @@ public:
     }
   };
 
+  friend std::ostream& operator<<(std::ostream& os,
+                                  RepeatedSubstring substring) {
+    os << "SuffixTree::RepeatedSubstring{" << substring.Length
+       << "u, (std::vector<unsigned>{";
+    for (unsigned idx = 0; idx < substring.StartIndices.size(); idx++) {
+      os << substring.StartIndices[idx];
+      if (idx != substring.StartIndices.size() - 1) {
+        os << ", ";
+      }
+    }
+    return os << "})}";
+  }
+
 private:
   /// Maintains internal nodes in the tree.
   SpecificBumpPtrAllocator<SuffixTreeInternalNode> InternalNodeAllocator;