summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/passes/CMakeLists.txt2
-rw-r--r--src/passes/Outlining.cpp329
-rw-r--r--src/passes/hash-stringify-walker.cpp55
-rw-r--r--src/passes/pass.cpp5
-rw-r--r--src/passes/passes.h5
-rw-r--r--src/passes/stringify-walker.h94
-rw-r--r--src/wasm/wasm-ir-builder.cpp3
7 files changed, 455 insertions, 38 deletions
diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index ec57f108d..53f52e23f 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -45,6 +45,7 @@ set(passes_SOURCES
GlobalTypeOptimization.cpp
GUFA.cpp
hash-stringify-walker.cpp
+ Outlining.cpp
Heap2Local.cpp
I64ToI32Lowering.cpp
Inlining.cpp
@@ -131,5 +132,6 @@ if(EMSCRIPTEN)
list(REMOVE_ITEM passes_SOURCES ${CMAKE_CURRENT_BINARY_DIR}/stringify-walker.h)
list(REMOVE_ITEM passes_SOURCES ${CMAKE_CURRENT_BINARY_DIR}/stringify-walker-impl.h)
list(REMOVE_ITEM passes_SOURCES "hash-stringify-walker.cpp")
+ list(REMOVE_ITEM passes_SOURCES "Outlining.cpp")
endif()
add_library(passes OBJECT ${passes_SOURCES})
diff --git a/src/passes/Outlining.cpp b/src/passes/Outlining.cpp
new file mode 100644
index 000000000..4bb883187
--- /dev/null
+++ b/src/passes/Outlining.cpp
@@ -0,0 +1,329 @@
+#include "ir/names.h"
+#include "ir/utils.h"
+#include "pass.h"
+#include "passes/stringify-walker.h"
+#include "support/suffix_tree.h"
+#include "wasm.h"
+
+#define OUTLINING_DEBUG 0
+
+#if OUTLINING_DEBUG
+#define DBG(statement) statement
+#else
+#define DBG(statement)
+#endif
+
+// Check a Result or MaybeResult for error and call Fatal() if the error exists.
+#define ASSERT_OK(val) \
+ if (auto _val = (val); auto err = _val.getErr()) { \
+ Fatal() << err->msg; \
+ }
+
+namespace wasm {
+
+// Instances of this walker are intended to walk a function at a time, at the
+// behest of the owner of the instance.
+struct ReconstructStringifyWalker
+ : public StringifyWalker<ReconstructStringifyWalker> {
+
+ ReconstructStringifyWalker(Module* wasm)
+ : existingBuilder(*wasm), outlinedBuilder(*wasm) {
+ this->setModule(wasm);
+ DBG(std::cout << "\n\nexistingBuilder: " << &existingBuilder
+ << " outlinedBuilder: " << &outlinedBuilder);
+ }
+
+ // As we reconstruct the IR during outlining, we need to know what
+ // state we're in to determine which IRBuilder to send the instruction to.
+ enum ReconstructState {
+ NotInSeq = 0, // Will not be outlined into a new function.
+ InSeq = 1, // Currently being outlined into a new function.
+ InSkipSeq = 2, // A sequence that has already been outlined.
+ };
+ // We begin with the assumption that we are not currently in a sequence that
+ // will be outlined.
+ ReconstructState state = ReconstructState::NotInSeq;
+
+ // The list of sequences that will be outlined, contained in the function
+ // currently being walked.
+ std::vector<OutliningSequence> sequences;
+ // Tracks the OutliningSequence the walker is about to outline or is currently
+ // outlining.
+ uint32_t seqCounter = 0;
+ // Counts the number of instructions visited since the function began,
+ // corresponds to the indices in the sequences.
+ uint32_t instrCounter = 0;
+ // A reusable builder for reconstructing the function that will have sequences
+ // of instructions removed to be placed into an outlined function. The removed
+ // sequences will be replaced by a call to the outlined function.
+ IRBuilder existingBuilder;
+ // A reusable builder for constructing the outlined functions that will
+ // contain repeat sequences found in the program.
+ IRBuilder outlinedBuilder;
+
+ void addUniqueSymbol(SeparatorReason reason) {
+ if (auto curr = reason.getFuncStart()) {
+ startExistingFunction(curr->func);
+ return;
+ }
+
+ // instrCounter is managed manually and incremented at the beginning of
+ // addUniqueSymbol() and visitExpression(), except for the case where we are
+ // starting a new function, as that resets the counters back to 0.
+ instrCounter++;
+
+ DBG(std::string desc);
+ if (auto curr = reason.getBlockStart()) {
+ ASSERT_OK(existingBuilder.visitBlockStart(curr->block));
+ DBG(desc = "Block Start for ");
+ } else if (auto curr = reason.getIfStart()) {
+ ASSERT_OK(existingBuilder.visitIfStart(curr->iff));
+ DBG(desc = "If Start for ");
+ } else if (reason.getEnd()) {
+ ASSERT_OK(existingBuilder.visitEnd());
+ DBG(desc = "End for ");
+ } else {
+ DBG(desc = "addUniqueSymbol for unimplemented control flow ");
+ WASM_UNREACHABLE("unimplemented control flow");
+ }
+ DBG(printAddUniqueSymbol(desc));
+ }
+
+ void visitExpression(Expression* curr) {
+ maybeBeginSeq();
+
+ IRBuilder* builder = state == InSeq ? &outlinedBuilder
+ : state == NotInSeq ? &existingBuilder
+ : nullptr;
+ if (builder) {
+ ASSERT_OK(builder->visit(curr));
+ }
+ DBG(printVisitExpression(curr));
+
+ if (state == InSeq || state == InSkipSeq) {
+ maybeEndSeq();
+ }
+ }
+
+ // Helpers
+ void startExistingFunction(Function* func) {
+ ASSERT_OK(existingBuilder.build());
+ ASSERT_OK(existingBuilder.visitFunctionStart(func));
+ instrCounter = 0;
+ seqCounter = 0;
+ state = NotInSeq;
+ DBG(std::cout << "\n\n$" << func->name << " Func Start "
+ << &existingBuilder);
+ }
+
+ ReconstructState getCurrState() {
+ // We are either in a sequence or not in a sequence. If we are in a sequence
+ // and have already created the body of the outlined function that will be
+ // called, then we will skip instructions, otherwise we add the instructions
+ // to the outlined function. If we are not in a sequence, then the
+ // instructions are sent to the existing function.
+ if (seqCounter < sequences.size() &&
+ instrCounter >= sequences[seqCounter].startIdx &&
+ instrCounter < sequences[seqCounter].endIdx) {
+ return getModule()->getFunction(sequences[seqCounter].func)->body
+ ? InSkipSeq
+ : InSeq;
+ }
+ return NotInSeq;
+ }
+
+ void maybeBeginSeq() {
+ instrCounter++;
+ auto currState = getCurrState();
+ if (currState != state) {
+ switch (currState) {
+ case NotInSeq:
+ break;
+ case InSeq:
+ transitionToInSeq();
+ break;
+ case InSkipSeq:
+ transitionToInSkipSeq();
+ break;
+ }
+ }
+ state = currState;
+ }
+
+ void transitionToInSeq() {
+ Function* outlinedFunc =
+ getModule()->getFunction(sequences[seqCounter].func);
+ ASSERT_OK(outlinedBuilder.visitFunctionStart(outlinedFunc));
+
+ // Add a local.get instruction for every parameter of the outlined function.
+ Signature sig = outlinedFunc->type.getSignature();
+ for (Index i = 0; i < sig.params.size(); i++) {
+ ASSERT_OK(outlinedBuilder.makeLocalGet(i));
+ }
+
+ // Make a call from the existing function to the outlined function. This
+ // call will replace the instructions moved to the outlined function.
+ ASSERT_OK(existingBuilder.makeCall(outlinedFunc->name, false));
+ DBG(std::cout << "\ncreated outlined fn: " << outlinedFunc->name);
+ }
+
+ void transitionToInSkipSeq() {
+ Function* outlinedFunc =
+ getModule()->getFunction(sequences[seqCounter].func);
+ ASSERT_OK(existingBuilder.makeCall(outlinedFunc->name, false));
+ DBG(std::cout << "\n\nstarting to skip instructions "
+ << sequences[seqCounter].startIdx << " - "
+ << sequences[seqCounter].endIdx - 1 << " to "
+ << sequences[seqCounter].func
+ << " and adding call() instead");
+ }
+
+ void maybeEndSeq() {
+ if (instrCounter + 1 == sequences[seqCounter].endIdx) {
+ transitionToNotInSeq();
+ state = NotInSeq;
+ }
+ }
+
+ void transitionToNotInSeq() {
+ if (state == InSeq) {
+ ASSERT_OK(outlinedBuilder.visitEnd());
+ DBG(std::cout << "\n\nEnd of sequence to " << &outlinedBuilder);
+ }
+ // Completed a sequence so increase the seqCounter and reset the state.
+ seqCounter++;
+ }
+
+#if OUTLINING_DEBUG
+ void printAddUniqueSymbol(std::string desc) {
+ std::cout << "\n"
+ << desc << std::to_string(instrCounter) << " to "
+ << &existingBuilder;
+ }
+
+ void printVisitExpression(Expression* curr) {
+ auto* builder = state == InSeq ? &outlinedBuilder
+ : state == NotInSeq ? &existingBuilder
+ : nullptr;
+ auto verb = state == InSkipSeq ? "skipping " : "adding ";
+ std::cout << "\n"
+ << verb << std::to_string(instrCounter) << ": "
+ << ShallowExpression{curr} << " to " << builder;
+ }
+#endif
+};
+
+struct Outlining : public Pass {
+ void run(Module* module) {
+ HashStringifyWalker stringify;
+ // Walk the module and create a "string representation" of the program.
+ stringify.walkModule(module);
+ // Collect all of the substrings of the string representation that appear
+ // more than once in the program.
+ auto substrings =
+ StringifyProcessor::repeatSubstrings(stringify.hashString);
+ DBG(printHashString(stringify.hashString, stringify.exprs));
+ // Remove substrings that are substrings of longer repeat substrings.
+ substrings = StringifyProcessor::dedupe(substrings);
+ // Remove substrings with branch and return instructions until an analysis
+ // is performed to see if the intended destination of the branch is included
+ // in the substring to be outlined.
+ substrings =
+ StringifyProcessor::filterBranches(substrings, stringify.exprs);
+ // Remove substrings with local.set instructions until Outlining is extended
+ // to support arranging for the written values to be returned from the
+ // outlined function and written back to the original locals.
+ substrings =
+ StringifyProcessor::filterLocalSets(substrings, stringify.exprs);
+ // Remove substrings with local.get instructions until Outlining is extended
+ // to support passing the local values as additional arguments to the
+ // outlined function.
+ substrings =
+ StringifyProcessor::filterLocalGets(substrings, stringify.exprs);
+ // Convert substrings to sequences that are more easily outlineable as we
+ // walk the functions in a module. Sequences contain indices that
+ // are relative to the enclosing function while substrings have indices
+ // relative to the entire program.
+ auto sequences = makeSequences(module, substrings, stringify);
+ outline(module, sequences);
+ }
+
+ Name addOutlinedFunction(Module* module,
+ const SuffixTree::RepeatedSubstring& substring,
+ const std::vector<Expression*>& exprs) {
+ auto startIdx = substring.StartIndices[0];
+ // The outlined functions can be named anything.
+ Name outlinedFunc =
+ Names::getValidFunctionName(*module, std::string("outline$"));
+ // Calculate the function signature for the outlined sequence.
+ StackSignature sig;
+ for (uint32_t exprIdx = startIdx; exprIdx < startIdx + substring.Length;
+ exprIdx++) {
+ sig += StackSignature(exprs[exprIdx]);
+ }
+ module->addFunction(Builder::makeFunction(
+ outlinedFunc, Signature(sig.params, sig.results), {}));
+ return outlinedFunc;
+ }
+
+ using Sequences =
+ std::unordered_map<Name, std::vector<wasm::OutliningSequence>>;
+
+ // Converts an array of SuffixTree::RepeatedSubstring to a mapping of original
+ // functions to repeated sequences they contain. These sequences are ordered
+ // by start index by construction because the substring's start indices are
+ // ordered.
+ Sequences makeSequences(Module* module,
+ const Substrings& substrings,
+ const HashStringifyWalker& stringify) {
+ Sequences seqByFunc;
+ for (auto& substring : substrings) {
+ Name outlinedFunc =
+ addOutlinedFunction(module, substring, stringify.exprs);
+ for (auto seqIdx : substring.StartIndices) {
+ // seqIdx is relative to the entire program; making the idx of the
+ // sequence relative to its function is better for outlining because we
+ // walk functions.
+ auto [relativeIdx, existingFunc] = stringify.makeRelative(seqIdx);
+ auto seq = OutliningSequence(
+ relativeIdx, relativeIdx + substring.Length, outlinedFunc);
+ seqByFunc[existingFunc].push_back(seq);
+ }
+ }
+ return seqByFunc;
+ }
+
+ void outline(Module* module, Sequences seqByFunc) {
+ // TODO: Make this a function-parallel sub-pass.
+ ReconstructStringifyWalker reconstruct(module);
+ std::vector<Name> keys(seqByFunc.size());
+ std::transform(seqByFunc.begin(),
+ seqByFunc.end(),
+ keys.begin(),
+ [](auto pair) { return pair.first; });
+ for (auto func : keys) {
+ reconstruct.sequences = std::move(seqByFunc[func]);
+ reconstruct.doWalkFunction(module->getFunction(func));
+ }
+ }
+
+#if OUTLINING_DEBUG
+ void printHashString(const std::vector<uint32_t>& hashString,
+ const std::vector<Expression*>& exprs) {
+ std::cout << "\n\n";
+ for (Index idx = 0; idx < hashString.size(); idx++) {
+ Expression* expr = exprs[idx];
+ if (expr) {
+ std::cout << idx << " - " << hashString[idx] << ": "
+ << ShallowExpression{expr} << "\n";
+ } else {
+ std::cout << idx << ": unique symbol\n";
+ }
+ }
+ }
+#endif
+};
+
+Pass* createOutliningPass() { return new Outlining(); }
+
+} // namespace wasm
diff --git a/src/passes/hash-stringify-walker.cpp b/src/passes/hash-stringify-walker.cpp
index abcd07162..5afd50ef4 100644
--- a/src/passes/hash-stringify-walker.cpp
+++ b/src/passes/hash-stringify-walker.cpp
@@ -56,6 +56,9 @@ void HashStringifyWalker::addUniqueSymbol(SeparatorReason reason) {
// Use a negative value to distinguish symbols for separators from symbols
// for Expressions
assert((uint32_t)nextSeparatorVal >= nextVal);
+ if (auto funcStart = reason.getFuncStart()) {
+ idxToFuncName.insert({hashString.size(), funcStart->func->name});
+ }
hashString.push_back((uint32_t)nextSeparatorVal);
nextSeparatorVal--;
exprs.push_back(nullptr);
@@ -70,6 +73,42 @@ void HashStringifyWalker::visitExpression(Expression* curr) {
}
}
+std::pair<uint32_t, Name>
+HashStringifyWalker::makeRelative(uint32_t idx) const {
+ // The upper_bound function returns an iterator to the first value in the set
+ // that is true for idx < value. We subtract one from this returned value to
+ // tell us which function actually contains the the idx.
+ auto [funcIdx, func] = *--idxToFuncName.upper_bound(idx);
+ return {idx - funcIdx, func};
+}
+
+std::vector<SuffixTree::RepeatedSubstring>
+StringifyProcessor::repeatSubstrings(std::vector<uint32_t>& hashString) {
+ SuffixTree st(hashString);
+ std::vector<SuffixTree::RepeatedSubstring> substrings(st.begin(), st.end());
+ for (auto substring : substrings) {
+ // Sort by increasing start index to ensure determinism.
+ std::sort(substring.StartIndices.begin(),
+ substring.StartIndices.end(),
+ [](uint32_t a, uint32_t b) { return a < b; });
+ }
+ // Substrings are sorted so that the longest substring that repeats the most
+ // times is ordered first. This is done so that we can assume the most
+ // worthwhile substrings to outline come first.
+ 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 +151,7 @@ std::vector<SuffixTree::RepeatedSubstring> StringifyProcessor::dedupe(
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,19 +207,29 @@ std::vector<SuffixTree::RepeatedSubstring> StringifyProcessor::filter(
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>();
});
}
+std::vector<SuffixTree::RepeatedSubstring> StringifyProcessor::filterLocalGets(
+ const std::vector<SuffixTree::RepeatedSubstring>& substrings,
+ const std::vector<Expression*>& exprs) {
+ return StringifyProcessor::filter(
+ substrings, exprs, [](const Expression* curr) {
+ return curr->is<LocalGet>();
+ });
+}
+
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/pass.cpp b/src/passes/pass.cpp
index b2b9551c9..c18f47ac7 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -311,6 +311,11 @@ void PassRegistry::registerPasses() {
createOptimizeInstructionsPass);
registerPass(
"optimize-stack-ir", "optimize Stack IR", createOptimizeStackIRPass);
+// Outlining currently relies on LLVM's SuffixTree, which we can't rely upon
+// when building Binaryen for Emscripten.
+#ifndef __EMSCRIPTEN__
+ registerPass("outlining", "outline instructions", createOutliningPass);
+#endif
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 3ce2af4fd..3d1aa0bfd 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -99,6 +99,11 @@ Pass* createOptimizeInstructionsPass();
Pass* createOptimizeCastsPass();
Pass* createOptimizeForJSPass();
Pass* createOptimizeStackIRPass();
+// Outlining currently relies on LLVM's SuffixTree, which we can't rely upon
+// when building Binaryen for Emscripten.
+#ifndef __EMSCRIPTEN__
+Pass* createOutliningPass();
+#endif
Pass* createPickLoadSignsPass();
Pass* createModAsyncifyAlwaysOnlyUnwindPass();
Pass* createModAsyncifyNeverUnwindPass();
diff --git a/src/passes/stringify-walker.h b/src/passes/stringify-walker.h
index 6095eb7ad..eb4a4482b 100644
--- a/src/passes/stringify-walker.h
+++ b/src/passes/stringify-walker.h
@@ -19,8 +19,10 @@
#include "ir/iteration.h"
#include "ir/module-utils.h"
+#include "ir/stack-utils.h"
#include "ir/utils.h"
#include "support/suffix_tree.h"
+#include "wasm-ir-builder.h"
#include "wasm-traversal.h"
#include <queue>
@@ -51,13 +53,14 @@ namespace wasm {
*
* Of note:
* - The visits to if-True on line 4 and if-False on line 5 are deferred until
- * after the rest of the siblings of the if expression on line 2 are visited
+ * after the rest of the siblings of the if expression on line 2 are
+ * visited.
* - The if-condition (i32.const 0) on line 3 is visited before the if
* expression on line 2. Similarly, the if-condition (i32.const 1) on line
* 11 is visited before the if expression on line 10.
* - The add (line 7) binary operator's left and right children (lines 8 - 9)
* are visited first as they need to be on the stack before the add
- * operation is executed
+ * operation is executed.
*/
template<typename SubType>
@@ -72,7 +75,7 @@ struct StringifyWalker
};
struct BlockStart {
- Block* curr;
+ Block* block;
};
struct IfStart {
@@ -129,34 +132,38 @@ struct StringifyWalker
return SeparatorReason(TryBodyStart{});
}
static SeparatorReason makeEnd() { return SeparatorReason(End{}); }
- bool isFuncStart() { return std::get_if<FuncStart>(&reason); }
- bool isBlockStart() { return std::get_if<BlockStart>(&reason); }
- bool isIfStart() { return std::get_if<IfStart>(&reason); }
- bool isElseStart() { return std::get_if<ElseStart>(&reason); }
- bool isLoopStart() { return std::get_if<LoopStart>(&reason); }
- bool isTryBodyStart() { return std::get_if<TryBodyStart>(&reason); }
- bool isTryCatchStart() { return std::get_if<TryCatchStart>(&reason); }
- bool isEnd() { return std::get_if<End>(&reason); }
+ FuncStart* getFuncStart() { return std::get_if<FuncStart>(&reason); }
+ BlockStart* getBlockStart() { return std::get_if<BlockStart>(&reason); }
+ IfStart* getIfStart() { return std::get_if<IfStart>(&reason); }
+ ElseStart* getElseStart() { return std::get_if<ElseStart>(&reason); }
+ LoopStart* getLoopStart() { return std::get_if<LoopStart>(&reason); }
+ TryBodyStart* getTryBodyStart() {
+ return std::get_if<TryBodyStart>(&reason);
+ }
+ TryCatchStart* getTryCatchStart() {
+ return std::get_if<TryCatchStart>(&reason);
+ }
+ End* getEnd() { return std::get_if<End>(&reason); }
};
friend std::ostream&
operator<<(std::ostream& o,
typename StringifyWalker::SeparatorReason reason) {
- if (reason.isFuncStart()) {
+ if (reason.getFuncStart()) {
return o << "Func Start";
- } else if (reason.isBlockStart()) {
+ } else if (reason.getBlockStart()) {
return o << "Block Start";
- } else if (reason.isIfStart()) {
+ } else if (reason.getIfStart()) {
return o << "If Start";
- } else if (reason.isElseStart()) {
+ } else if (reason.getElseStart()) {
return o << "Else Start";
- } else if (reason.isLoopStart()) {
+ } else if (reason.getLoopStart()) {
return o << "Loop Start";
- } else if (reason.isTryBodyStart()) {
+ } else if (reason.getTryBodyStart()) {
return o << "Try Body Start";
- } else if (reason.isTryCatchStart()) {
+ } else if (reason.getTryCatchStart()) {
return o << "Try Catch Start";
- } else if (reason.isEnd()) {
+ } else if (reason.getEnd()) {
return o << "End";
}
@@ -214,10 +221,10 @@ struct HashStringifyWalker : public StringifyWalker<HashStringifyWalker> {
// Expression or a separator to mark the end of control flow.
std::vector<uint32_t> hashString;
// A monotonic counter used to ensure that unique expressions in the
- // module are assigned a unique value in the hashString
+ // module are assigned a unique value in the hashString.
uint32_t nextVal = 0;
// A monotonic counter used to ensure that each separator in the
- // module is assigned a unique value in the hashString
+ // module is assigned a unique value in the hashString.
int32_t nextSeparatorVal = -1;
// Contains a mapping of expression pointer to value to ensure we
// use the same value for matching expressions. A custom hasher and
@@ -229,25 +236,44 @@ struct HashStringifyWalker : public StringifyWalker<HashStringifyWalker> {
void addUniqueSymbol(SeparatorReason reason);
void visitExpression(Expression* curr);
+ // Converts the idx from relative to the beginning of the program to
+ // relative to its enclosing function, and returns the name of its function.
+ std::pair<uint32_t, Name> makeRelative(uint32_t idx) const;
+
+private:
+ // Contains the indices that mark the start of each function.
+ std::set<uint32_t> funcIndices;
+ // Maps the start idx of each function to the function name.
+ std::map<uint32_t, Name> idxToFuncName;
};
+struct OutliningSequence {
+ unsigned startIdx;
+ unsigned endIdx;
+ Name func;
+
+ OutliningSequence(unsigned startIdx, unsigned endIdx, Name func)
+ : startIdx(startIdx), endIdx(endIdx), func(func) {}
+};
+
+using Substrings = std::vector<SuffixTree::RepeatedSubstring>;
+
// Functions that filter vectors of SuffixTree::RepeatedSubstring
struct StringifyProcessor {
- static std::vector<SuffixTree::RepeatedSubstring>
- dedupe(const std::vector<SuffixTree::RepeatedSubstring>& substrings);
+ static Substrings repeatSubstrings(std::vector<uint32_t>& hashString);
+ static Substrings dedupe(const Substrings& 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,
- std::function<bool(const Expression*)> condition);
- static std::vector<SuffixTree::RepeatedSubstring>
- filterLocalSets(const std::vector<SuffixTree::RepeatedSubstring>& substrings,
- const std::vector<Expression*> exprs);
- static std::vector<SuffixTree::RepeatedSubstring>
- filterBranches(const std::vector<SuffixTree::RepeatedSubstring>& substrings,
- const std::vector<Expression*> exprs);
+ // to encapsulate your condition and make it available for tests.
+ static Substrings filter(const Substrings& substrings,
+ const std::vector<Expression*>& exprs,
+ std::function<bool(const Expression*)> condition);
+ static Substrings filterLocalSets(const Substrings& substrings,
+ const std::vector<Expression*>& exprs);
+ static Substrings filterLocalGets(const Substrings& substrings,
+ const std::vector<Expression*>& exprs);
+ static Substrings filterBranches(const Substrings& substrings,
+ const std::vector<Expression*>& exprs);
};
} // namespace wasm
diff --git a/src/wasm/wasm-ir-builder.cpp b/src/wasm/wasm-ir-builder.cpp
index 255683fbc..c866cce20 100644
--- a/src/wasm/wasm-ir-builder.cpp
+++ b/src/wasm/wasm-ir-builder.cpp
@@ -186,7 +186,8 @@ Result<Expression*> IRBuilder::build() {
}
Result<> IRBuilder::visit(Expression* curr) {
- UnifiedExpressionVisitor<IRBuilder, Result<>>::visit(curr);
+ auto val = UnifiedExpressionVisitor<IRBuilder, Result<>>::visit(curr);
+ CHECK_ERR(val);
if (auto* block = curr->dynCast<Block>()) {
block->finalize(block->type);
} else {
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-08 02:43:47 +0000