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(
