From f45207e02f3f703ef96b23957538a935856cf874 Mon Sep 17 00:00:00 2001
From: Ashley Nelson <nashley@google.com>
Date: Tue, 17 Oct 2023 17:12:26 -0700
Subject: [Outlining] Filter Local Set (#6018)

Adds a general purpose walker named FilterStringifyWalker, intended to walk control flow and take note of whether any of the expressions satisfy the condition.

Also includes an << overload for SuffixTree::RepeatedSubstring to make debugging easier.
---
 src/passes/hash-stringify-walker.cpp | 60 +++++++++++++++++++++++++++++++++++-
 1 file changed, 59 insertions(+), 1 deletion(-)

(limited to 'src/passes/hash-stringify-walker.cpp')

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
-- 
cgit v1.2.3