diff options
| -rw-r--r-- | src/passes/hash-stringify-walker.cpp | 2 | ||||
| -rw-r--r-- | src/passes/stringify-walker-impl.h | 47 | ||||
| -rw-r--r-- | src/passes/stringify-walker.h | 101 | ||||
| -rw-r--r-- | test/gtest/stringify.cpp | 106 |
4 files changed, 185 insertions, 71 deletions
diff --git a/src/passes/hash-stringify-walker.cpp b/src/passes/hash-stringify-walker.cpp index 9a7cee08f..43cc3d544 100644 --- a/src/passes/hash-stringify-walker.cpp +++ b/src/passes/hash-stringify-walker.cpp @@ -52,7 +52,7 @@ bool StringifyEquator::operator()(Expression* lhs, Expression* rhs) const { return ExpressionAnalyzer::shallowEqual(lhs, rhs); } -void HashStringifyWalker::addUniqueSymbol() { +void HashStringifyWalker::addUniqueSymbol(SeparatorReason reason) { // Use a negative value to distinguish symbols for separators from symbols // for Expressions assert((uint32_t)nextSeparatorVal >= nextVal); diff --git a/src/passes/stringify-walker-impl.h b/src/passes/stringify-walker-impl.h index e856773c9..8ed166d75 100644 --- a/src/passes/stringify-walker-impl.h +++ b/src/passes/stringify-walker-impl.h @@ -31,28 +31,12 @@ inline void StringifyWalker<SubType>::doWalkModule(Module* module) { template<typename SubType> inline void StringifyWalker<SubType>::doWalkFunction(Function* func) { - walk(func->body); - /* - * We add a unique symbol after walking the function body to separate the - * string generated from visiting the function body as a single unit from the - * subsequent strings that will be generated from visiting the sub-expressions - * of the function body. If we did not add this unique symbol and a program - * had two functions with the same instructions, we would incorrectly create a - * new function with the instructions repeated twice. - * - * It might be helpful to think of the function body as a block that needs to - * be separated from subsequent instructions. - */ - addUniqueSymbol(); -} - -template<typename SubType> -inline void StringifyWalker<SubType>::walk(Expression* curr) { - Super::walk(curr); - do { - addUniqueSymbol(); + addUniqueSymbol(SeparatorReason::makeFuncStart(func)); + Super::walk(func->body); + addUniqueSymbol(SeparatorReason::makeEnd()); + while (!controlFlowQueue.empty()) { dequeueControlFlow(); - } while (!controlFlowQueue.empty()); + } } template<typename SubType> @@ -76,10 +60,6 @@ inline void StringifyWalker<SubType>::scan(SubType* self, Expression** currp) { // of control flow. template<typename SubType> void StringifyWalker<SubType>::dequeueControlFlow() { auto& queue = controlFlowQueue; - if (queue.empty()) { - return; - } - Expression** currp = queue.front(); queue.pop(); Expression* curr = *currp; @@ -88,32 +68,41 @@ template<typename SubType> void StringifyWalker<SubType>::dequeueControlFlow() { switch (curr->_id) { case Expression::Id::BlockId: { auto* block = curr->cast<Block>(); + addUniqueSymbol(SeparatorReason::makeBlockStart(block)); for (auto& child : block->list) { Super::walk(child); } + addUniqueSymbol(SeparatorReason::makeEnd()); break; } case Expression::Id::IfId: { auto* iff = curr->cast<If>(); + addUniqueSymbol(SeparatorReason::makeIfStart(iff)); Super::walk(iff->ifTrue); if (iff->ifFalse) { - addUniqueSymbol(); + addUniqueSymbol(SeparatorReason::makeElseStart(iff)); Super::walk(iff->ifFalse); } + addUniqueSymbol(SeparatorReason::makeEnd()); break; } case Expression::Id::TryId: { auto* tryy = curr->cast<Try>(); + addUniqueSymbol(SeparatorReason::makeTryBodyStart()); Super::walk(tryy->body); + addUniqueSymbol(SeparatorReason::makeEnd()); for (auto& child : tryy->catchBodies) { - addUniqueSymbol(); + addUniqueSymbol(SeparatorReason::makeTryCatchStart()); Super::walk(child); + addUniqueSymbol(SeparatorReason::makeEnd()); } break; } case Expression::Id::LoopId: { auto* loop = curr->cast<Loop>(); + addUniqueSymbol(SeparatorReason::makeLoopStart(loop)); Super::walk(loop->body); + addUniqueSymbol(SeparatorReason::makeEnd()); break; } default: { @@ -131,13 +120,13 @@ void StringifyWalker<SubType>::doVisitExpression(SubType* self, } template<typename SubType> -inline void StringifyWalker<SubType>::addUniqueSymbol() { +inline void StringifyWalker<SubType>::addUniqueSymbol(SeparatorReason reason) { // TODO: Add the following static_assert when the compilers running our GitHub // actions are updated enough to know that this is a constant condition: // static_assert(&StringifyWalker<SubType>::addUniqueSymbol != // &SubType::addUniqueSymbol); auto self = static_cast<SubType*>(this); - self->addUniqueSymbol(); + self->addUniqueSymbol(reason); } } // namespace wasm diff --git a/src/passes/stringify-walker.h b/src/passes/stringify-walker.h index c20d250ec..129021bc4 100644 --- a/src/passes/stringify-walker.h +++ b/src/passes/stringify-walker.h @@ -66,6 +66,103 @@ struct StringifyWalker using Super = PostWalker<SubType, UnifiedExpressionVisitor<SubType>>; + struct SeparatorReason { + struct FuncStart { + Function* func; + }; + + struct BlockStart { + Block* curr; + }; + + struct IfStart { + If* iff; + }; + + struct ElseStart { + If* iff; + }; + + struct LoopStart { + Loop* loop; + }; + + struct TryBodyStart {}; + + struct TryCatchStart {}; + + struct End { + Expression* curr; + }; + using Separator = std::variant<FuncStart, + BlockStart, + IfStart, + ElseStart, + LoopStart, + TryBodyStart, + TryCatchStart, + End>; + + Separator reason; + + SeparatorReason(Separator reason) : reason(reason) {} + + static SeparatorReason makeFuncStart(Function* func) { + return SeparatorReason(FuncStart{func}); + } + static SeparatorReason makeBlockStart(Block* block) { + return SeparatorReason(BlockStart{block}); + } + static SeparatorReason makeIfStart(If* iff) { + return SeparatorReason(IfStart{iff}); + } + static SeparatorReason makeElseStart(If* iff) { + return SeparatorReason(ElseStart{iff}); + } + static SeparatorReason makeLoopStart(Loop* loop) { + return SeparatorReason(LoopStart{loop}); + } + static SeparatorReason makeTryCatchStart() { + return SeparatorReason(TryCatchStart{}); + } + static SeparatorReason makeTryBodyStart() { + 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); } + }; + + friend std::ostream& + operator<<(std::ostream& o, + typename StringifyWalker::SeparatorReason reason) { + if (reason.isFuncStart()) { + return o << "Func Start"; + } else if (reason.isBlockStart()) { + return o << "Block Start"; + } else if (reason.isIfStart()) { + return o << "If Start"; + } else if (reason.isElseStart()) { + return o << "Else Start"; + } else if (reason.isLoopStart()) { + return o << "Loop Start"; + } else if (reason.isTryBodyStart()) { + return o << "Try Body Start"; + } else if (reason.isTryCatchStart()) { + return o << "Try Catch Start"; + } else if (reason.isEnd()) { + return o << "End"; + } + + return o << "~~~Undefined in operator<< overload~~~"; + } + std::queue<Expression**> controlFlowQueue; /* @@ -77,7 +174,7 @@ struct StringifyWalker * appropriate points during the walk and should be implemented by subclasses. */ void visitExpression(Expression* curr); - void addUniqueSymbol(); + void addUniqueSymbol(SeparatorReason reason); void doWalkModule(Module* module); void doWalkFunction(Function* func); @@ -130,7 +227,7 @@ struct HashStringifyWalker : public StringifyWalker<HashStringifyWalker> { std::unordered_map<Expression*, uint32_t, StringifyHasher, StringifyEquator> exprToCounter; - void addUniqueSymbol(); + void addUniqueSymbol(SeparatorReason reason); void visitExpression(Expression* curr); }; diff --git a/test/gtest/stringify.cpp b/test/gtest/stringify.cpp index 01d7ad7af..22b194484 100644 --- a/test/gtest/stringify.cpp +++ b/test/gtest/stringify.cpp @@ -56,50 +56,64 @@ TEST_F(StringifyTest, Print) { ) )wasm"; - auto stringifyText = R"stringify(in visitExpression for block -adding unique symbol + auto stringifyText = R"stringify(adding unique symbol for Func Start +in visitExpression for block +adding unique symbol for End +adding unique symbol for Block Start in visitExpression for block $block_a in visitExpression for block $block_b in visitExpression for block $block_c in visitExpression for block $block_d in visitExpression for block $block_e -adding unique symbol +adding unique symbol for End +adding unique symbol for Block Start in visitExpression for i32.const 20 in visitExpression for drop in visitExpression for i32.const 10 in visitExpression for drop -adding unique symbol +adding unique symbol for End +adding unique symbol for Block Start in visitExpression for i32.const 0 in visitExpression for if in visitExpression for drop -adding unique symbol +adding unique symbol for End +adding unique symbol for Block Start in visitExpression for i32.const 1 in visitExpression for if in visitExpression for drop -adding unique symbol +adding unique symbol for End +adding unique symbol for Block Start in visitExpression for try $try_a -adding unique symbol +adding unique symbol for End +adding unique symbol for Block Start in visitExpression for try $try_b -adding unique symbol +adding unique symbol for End +adding unique symbol for If Start in visitExpression for i32.const 40 -adding unique symbol +adding unique symbol for Else Start in visitExpression for i32.const 5 -adding unique symbol +adding unique symbol for End +adding unique symbol for If Start in visitExpression for i32.const 30 -adding unique symbol +adding unique symbol for End +adding unique symbol for Try Body Start in visitExpression for nop -adding unique symbol +adding unique symbol for End +adding unique symbol for Try Catch Start in visitExpression for i32.const 8 in visitExpression for drop -adding unique symbol +adding unique symbol for End +adding unique symbol for Try Catch Start in visitExpression for i32.const 15 in visitExpression for drop -adding unique symbol +adding unique symbol for End +adding unique symbol for Try Body Start in visitExpression for nop -adding unique symbol +adding unique symbol for End +adding unique symbol for Try Catch Start in visitExpression for i32.const 33 in visitExpression for drop -adding unique symbol +adding unique symbol for End )stringify"; struct TestStringifyWalker : public StringifyWalker<TestStringifyWalker> { @@ -107,7 +121,9 @@ adding unique symbol TestStringifyWalker(std::ostream& os) : os(os){}; - void addUniqueSymbol() { os << "adding unique symbol\n"; } + void addUniqueSymbol(SeparatorReason reason) { + os << "adding unique symbol for " << reason << "\n"; + } void visitExpression(Expression* curr) { os << "in visitExpression for " << ShallowExpression{curr, getModule()} @@ -174,51 +190,63 @@ TEST_F(StringifyTest, Stringify) { EXPECT_EQ(hashString, (std::vector<uint32_t>{ + (uint32_t)-1, // function start 0, // function block evaluated as a whole - (uint32_t)-1, // separate function block from function contents + (uint32_t)-2, // end + (uint32_t)-3, // block start 1, // block_a evaluated as a whole 2, // block_b evaluated as a whole 3, // block_c evaluated as a whole 1, // block_d has the same contents as block_a 3, // block_e has the same contents as block_c 4, // block_f evaluated as a whole - (uint32_t)-2, // separate blocks from block contents + (uint32_t)-4, // end + (uint32_t)-5, // block start for block_a 5, // i32.const 20 6, // drop, all drops will be the same symbol 7, // i32.const 10 6, // drop - (uint32_t)-3, // separate block_a contents + (uint32_t)-6, // end + (uint32_t)-7, // block start for block_b 8, // i32.const 0, if condition 9, // block_b's if evaluated as a whole 6, // drop - (uint32_t)-4, // separate block_b contents + (uint32_t)-8, // end + (uint32_t)-9, // block start for block_c 10, // i32.const 1, if condition 11, // block_c's if evaluated as a whole 6, // drop - (uint32_t)-5, // separate block_c contents + (uint32_t)-10, // end + (uint32_t)-11, // block start for block_d 5, // i32.const 20 6, // drop 7, // i32.const 10 6, // drop - (uint32_t)-6, // separate block_d contents + (uint32_t)-12, // end + (uint32_t)-13, // block start for block_e 10, // i32.const 1, if condition 11, // block_e if evaluated as a whole 6, // drop - (uint32_t)-7, // separate block_e contents + (uint32_t)-14, // end + (uint32_t)-15, // block start for block_f 8, // i32.const 0, if condition 11, // block_f's if evaluated as a whole 6, // drop - (uint32_t)-8, // separate block_f contents + (uint32_t)-16, // end + (uint32_t)-17, // if start in block_b 12, // i32.const 40 - (uint32_t)-9, // separate block_b if-true + (uint32_t)-18, // else start in block_b 13, // i32.const 5 - (uint32_t)-10, // separate block_b if-false + (uint32_t)-19, // end + (uint32_t)-20, // if start in block_c 14, // i32.const 30 - (uint32_t)-11, // separate block_c if-true + (uint32_t)-21, // end + (uint32_t)-22, // if start in block_e 14, // i32.const 30 - (uint32_t)-12, // separate block_e if-true + (uint32_t)-23, // end + (uint32_t)-24, // if start in block_f 14, // i32.const 30 - (uint32_t)-13 // separate block_f if-true + (uint32_t)-25, // end })); } @@ -251,15 +279,15 @@ TEST_F(StringifyTest, Substrings) { substrings, (std::vector<SuffixTree::RepeatedSubstring>{ // 5, 6, 7, 6 appears at idx 9 and again at 22 - SuffixTree::RepeatedSubstring{4u, (std::vector<unsigned>{9, 22})}, + SuffixTree::RepeatedSubstring{4u, (std::vector<unsigned>{12, 28})}, // 6, 7, 6 appears at idx 10 and again at 23 - SuffixTree::RepeatedSubstring{3u, (std::vector<unsigned>{10, 23})}, + SuffixTree::RepeatedSubstring{3u, (std::vector<unsigned>{13, 29})}, // 10, 11, 6 appears at idx 18 and again at 27 - SuffixTree::RepeatedSubstring{3u, (std::vector<unsigned>{18, 27})}, + SuffixTree::RepeatedSubstring{3u, (std::vector<unsigned>{23, 34})}, // 11, 6 appears at idx 32, 19 and again at 28 - SuffixTree::RepeatedSubstring{2u, (std::vector<unsigned>{32, 19, 28})}, + SuffixTree::RepeatedSubstring{2u, (std::vector<unsigned>{40, 24, 35})}, // 7, 6 appears at idx 11 and again at 24 - SuffixTree::RepeatedSubstring{2u, (std::vector<unsigned>{11, 24})}})); + SuffixTree::RepeatedSubstring{2u, (std::vector<unsigned>{14, 30})}})); } TEST_F(StringifyTest, DedupeSubstrings) { @@ -273,8 +301,8 @@ TEST_F(StringifyTest, DedupeSubstrings) { EXPECT_EQ( result, (std::vector<SuffixTree::RepeatedSubstring>{ - // 5, 6, 7, 6 appears at idx 9 and again at 22 - SuffixTree::RepeatedSubstring{4u, (std::vector<unsigned>{9, 22})}, - // 10, 11, 6 appears at idx 18 and again at 27 - SuffixTree::RepeatedSubstring{3u, (std::vector<unsigned>{18, 27})}})); + // 5, 6, 7, 6 appears at idx 12 and again at 28 + SuffixTree::RepeatedSubstring{4u, (std::vector<unsigned>{12, 28})}, + // 10, 11, 6 appears at idx 23 and again at 34 + SuffixTree::RepeatedSubstring{3u, (std::vector<unsigned>{23, 34})}})); } |