Google Git
Sign in
chromium/external/github.com/WebAssembly/binaryen/refs/heads/stats^!/.
commit
9851898b6375adf18ebe36d1c8007abf9029a0b0
[log] [tgz]
author
Ashley Nelson <nashley@google.com>
Thu Sep 28 04:34:10 2023
committer
Ashley Nelson <nashley@google.com>
Wed Oct 18 21:39:39 2023
tree
f88dbd770890b4d3176df04feb51471ee5848bfb
parent
45f5bd2f440d6db5737947434cecdc4ffa37f567 [diff]
outlining eval pass

diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index bd1dd85..25750bb 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt

@@ -45,6 +45,7 @@
   GlobalTypeOptimization.cpp
   GUFA.cpp
   hash-stringify-walker.cpp
+  outlining.cpp
   Heap2Local.cpp
   I64ToI32Lowering.cpp
   Inlining.cpp

diff --git a/src/passes/hash-stringify-walker.cpp b/src/passes/hash-stringify-walker.cpp
index abcd071..fc60727 100644
--- a/src/passes/hash-stringify-walker.cpp
+++ b/src/passes/hash-stringify-walker.cpp

@@ -70,6 +70,25 @@
   }
 }
 
+std::vector<SuffixTree::RepeatedSubstring>
+StringifyProcessor::repeatSubstrings(const std::vector<uint32_t>& hashString) {
+  SuffixTree st(hashString);
+  std::vector<SuffixTree::RepeatedSubstring> substrings =
+    std::vector(st.begin(), st.end());
+  std::sort(
+    substrings.begin(),
+    substrings.end(),
+    [](SuffixTree::RepeatedSubstring a, SuffixTree::RepeatedSubstring b) {
+      size_t aWeight = a.Length * a.StartIndices.size();
+      size_t bWeight = b.Length * b.StartIndices.size();
+      if (aWeight == bWeight) {
+        return a.StartIndices[0] < b.StartIndices[0];
+      }
+      return aWeight > bWeight;
+    });
+  return substrings;
+}
+
 // Deduplicate substrings by iterating through the list of substrings, keeping
 // only those whose list of end indices is disjoint from the set of end indices
 // for all substrings kept so far. Substrings that are contained within other
@@ -112,7 +131,7 @@
 
 std::vector<SuffixTree::RepeatedSubstring> StringifyProcessor::filter(
   const std::vector<SuffixTree::RepeatedSubstring>& substrings,
-  const std::vector<Expression*> exprs,
+  const std::vector<Expression*>& exprs,
   std::function<bool(const Expression*)> condition) {
 
   struct FilterStringifyWalker : public StringifyWalker<FilterStringifyWalker> {
@@ -168,7 +187,7 @@
 
 std::vector<SuffixTree::RepeatedSubstring> StringifyProcessor::filterLocalSets(
   const std::vector<SuffixTree::RepeatedSubstring>& substrings,
-  const std::vector<Expression*> exprs) {
+  const std::vector<Expression*>& exprs) {
   return StringifyProcessor::filter(
     substrings, exprs, [](const Expression* curr) {
       return curr->is<LocalSet>();
@@ -177,10 +196,11 @@
 
 std::vector<SuffixTree::RepeatedSubstring> StringifyProcessor::filterBranches(
   const std::vector<SuffixTree::RepeatedSubstring>& substrings,
-  const std::vector<Expression*> exprs) {
+  const std::vector<Expression*>& exprs) {
   return StringifyProcessor::filter(
     substrings, exprs, [](const Expression* curr) {
       return Properties::isBranch(curr) || curr->is<Return>();
     });
 }
+
 } // namespace wasm

diff --git a/src/passes/outlining.cpp b/src/passes/outlining.cpp
new file mode 100644
index 0000000..30433e4
--- /dev/null
+++ b/src/passes/outlining.cpp

@@ -0,0 +1,42 @@
+#include "ir/utils.h"
+#include "pass.h"
+#include "passes/stringify-walker.h"
+#include "support/suffix_tree.h"
+#include "wasm.h"
+
+namespace wasm {
+
+struct OutliningEval : public Pass {
+  void run(Module* module) {
+    HashStringifyWalker stringify = HashStringifyWalker();
+    stringify.walkModule(module);
+    auto substrings =
+      StringifyProcessor::repeatSubstrings(stringify.hashString);
+    auto result = StringifyProcessor::dedupe(substrings);
+    result = StringifyProcessor::filterBranches(result, stringify.exprs);
+    result = StringifyProcessor::filterLocalSets(result, stringify.exprs);
+    printStats(substrings, result, &stringify);
+  }
+
+  void printStats(std::vector<SuffixTree::RepeatedSubstring> substrings,
+                  std::vector<SuffixTree::RepeatedSubstring> result,
+                  HashStringifyWalker* stringify) {
+    std::cout << substrings.size() << " substrings found, ";
+    std::cout << "reduced to " << result.size() << std::endl;
+    for (auto rs : result) {
+      size_t startIndex = rs.StartIndices[0];
+      std::cout << rs.StartIndices.size() << "x, ~"
+                << rs.StartIndices.size() * rs.Length * Measurer::BytesPerExpr
+                << " size:";
+      for (size_t i = startIndex; i < startIndex + rs.Length; i++) {
+        std::cout << stringify->hashString[i] << " ("
+                  << ShallowExpression{stringify->exprs[i]} << "), ";
+      }
+      std::cout << std::endl;
+    }
+  }
+};
+
+Pass* createOutliningEvalPass() { return new OutliningEval(); }
+
+} // namespace wasm

diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index 35085c2..804b0fc 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp

@@ -311,6 +311,9 @@
                createOptimizeInstructionsPass);
   registerPass(
     "optimize-stack-ir", "optimize Stack IR", createOptimizeStackIRPass);
+  registerPass("outlining-eval",
+               "evaluate outlining feasibility",
+               createOutliningEvalPass);
   registerPass("pick-load-signs",
                "pick load signs based on their uses",
                createPickLoadSignsPass);

diff --git a/src/passes/passes.h b/src/passes/passes.h
index 2bace5b..c94d398 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h

@@ -99,6 +99,7 @@
 Pass* createOptimizeCastsPass();
 Pass* createOptimizeForJSPass();
 Pass* createOptimizeStackIRPass();
+Pass* createOutliningEvalPass();
 Pass* createPickLoadSignsPass();
 Pass* createModAsyncifyAlwaysOnlyUnwindPass();
 Pass* createModAsyncifyNeverUnwindPass();

diff --git a/src/passes/stringify-walker.h b/src/passes/stringify-walker.h
index 6095eb7..d2e5134 100644
--- a/src/passes/stringify-walker.h
+++ b/src/passes/stringify-walker.h

@@ -234,20 +234,22 @@
 // Functions that filter vectors of SuffixTree::RepeatedSubstring
 struct StringifyProcessor {
   static std::vector<SuffixTree::RepeatedSubstring>
+  repeatSubstrings(const std::vector<uint32_t>& hashString);
+  static std::vector<SuffixTree::RepeatedSubstring>
   dedupe(const std::vector<SuffixTree::RepeatedSubstring>& substrings);
   // Filter is the general purpose function backing subsequent filter functions.
   // It can be used directly, but generally prefer a wrapper function
   // to encapsulate your condition and make it available for tests
   static std::vector<SuffixTree::RepeatedSubstring>
   filter(const std::vector<SuffixTree::RepeatedSubstring>& substrings,
-         const std::vector<Expression*> exprs,
+         const std::vector<Expression*>& exprs,
          std::function<bool(const Expression*)> condition);
   static std::vector<SuffixTree::RepeatedSubstring>
   filterLocalSets(const std::vector<SuffixTree::RepeatedSubstring>& substrings,
-                  const std::vector<Expression*> exprs);
+                  const std::vector<Expression*>& exprs);
   static std::vector<SuffixTree::RepeatedSubstring>
   filterBranches(const std::vector<SuffixTree::RepeatedSubstring>& substrings,
-                 const std::vector<Expression*> exprs);
+                 const std::vector<Expression*>& exprs);
 };
 
 } // namespace wasm

diff --git a/test/gtest/stringify.cpp b/test/gtest/stringify.cpp
index 8e854ee..59b7db6 100644
--- a/test/gtest/stringify.cpp
+++ b/test/gtest/stringify.cpp

@@ -250,29 +250,11 @@
             }));
 }
 
-std::vector<SuffixTree::RepeatedSubstring>
-repeatSubstrings(std::vector<uint32_t> hashString) {
-  SuffixTree st(hashString);
-  std::vector<SuffixTree::RepeatedSubstring> substrings(st.begin(), st.end());
-  std::sort(
-    substrings.begin(),
-    substrings.end(),
-    [](SuffixTree::RepeatedSubstring a, SuffixTree::RepeatedSubstring b) {
-      size_t aWeight = a.Length * a.StartIndices.size();
-      size_t bWeight = b.Length * b.StartIndices.size();
-      if (aWeight == bWeight) {
-        return a.StartIndices[0] < b.StartIndices[0];
-      }
-      return aWeight > bWeight;
-    });
-  return substrings;
-}
-
 TEST_F(StringifyTest, Substrings) {
   Module wasm;
   parseWast(wasm, dupModuleText);
   auto hashString = hashStringifyModule(&wasm);
-  auto substrings = repeatSubstrings(hashString);
+  auto substrings = StringifyProcessor::repeatSubstrings(hashString);
 
   EXPECT_EQ(
     substrings,
@@ -294,7 +276,7 @@
   parseWast(wasm, dupModuleText);
   auto hashString = hashStringifyModule(&wasm);
   std::vector<SuffixTree::RepeatedSubstring> substrings =
-    repeatSubstrings(hashString);
+    StringifyProcessor::repeatSubstrings(hashString);
   auto result = StringifyProcessor::dedupe(substrings);
 
   EXPECT_EQ(
@@ -332,10 +314,9 @@
   parseWast(wasm, localSetModuleText);
   HashStringifyWalker stringify = HashStringifyWalker();
   stringify.walkModule(&wasm);
-  auto substrings = repeatSubstrings(stringify.hashString);
-  auto result = StringifyProcessor::dedupe(substrings);
-
-  result = StringifyProcessor::filterLocalSets(substrings, stringify.exprs);
+  auto substrings = StringifyProcessor::repeatSubstrings(stringify.hashString);
+  auto result =
+    StringifyProcessor::filterLocalSets(substrings, stringify.exprs);
 
   EXPECT_EQ(
     result,
@@ -375,8 +356,7 @@
   parseWast(wasm, branchesModuleText);
   HashStringifyWalker stringify = HashStringifyWalker();
   stringify.walkModule(&wasm);
-
-  auto substrings = repeatSubstrings(stringify.hashString);
+  auto substrings = StringifyProcessor::repeatSubstrings(stringify.hashString);
   auto result = StringifyProcessor::filterBranches(substrings, stringify.exprs);
 
   EXPECT_EQ(