diff options
| -rw-r--r-- | src/ir/LocalGraph.cpp | 206 | ||||
| -rw-r--r-- | src/ir/local-graph.h | 38 | ||||
| -rw-r--r-- | test/gtest/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | test/gtest/local-graph.cpp | 347 |
4 files changed, 551 insertions, 41 deletions
diff --git a/src/ir/LocalGraph.cpp b/src/ir/LocalGraph.cpp index 7e877e65e..33055ad49 100644 --- a/src/ir/LocalGraph.cpp +++ b/src/ir/LocalGraph.cpp @@ -16,10 +16,11 @@ #include <iterator> -#include <cfg/cfg-traversal.h> -#include <ir/find_all.h> -#include <ir/local-graph.h> -#include <wasm-builder.h> +#include "cfg/cfg-traversal.h" +#include "ir/find_all.h" +#include "ir/local-graph.h" +#include "support/unique_deferring_queue.h" +#include "wasm-builder.h" namespace wasm { @@ -42,21 +43,27 @@ struct Info { // flow helper class. flows the gets to their sets struct LocalGraphFlower - : public CFGWalker<LocalGraphFlower, Visitor<LocalGraphFlower>, Info> { + : public CFGWalker<LocalGraphFlower, + UnifiedExpressionVisitor<LocalGraphFlower>, + Info> { LocalGraph::GetSetsMap& getSetsMap; LocalGraph::Locations& locations; Function* func; + std::optional<Expression::Id> queryClass; LocalGraphFlower(LocalGraph::GetSetsMap& getSetsMap, LocalGraph::Locations& locations, Function* func, - Module* module) - : getSetsMap(getSetsMap), locations(locations), func(func) { + Module* module, + std::optional<Expression::Id> queryClass = std::nullopt) + : getSetsMap(getSetsMap), locations(locations), func(func), + queryClass(queryClass) { setFunction(func); setModule(module); // create the CFG by walking the IR - CFGWalker<LocalGraphFlower, Visitor<LocalGraphFlower>, Info>:: - doWalkFunction(func); + CFGWalker<LocalGraphFlower, + UnifiedExpressionVisitor<LocalGraphFlower>, + Info>::doWalkFunction(func); } BasicBlock* makeBasicBlock() { return new BasicBlock(); } @@ -67,25 +74,22 @@ struct LocalGraphFlower // cfg traversal work - static void doVisitLocalGet(LocalGraphFlower* self, Expression** currp) { - auto* curr = (*currp)->cast<LocalGet>(); - // if in unreachable code, skip - if (!self->currBasicBlock) { + void visitExpression(Expression* curr) { + // If in unreachable code, skip. + if (!currBasicBlock) { return; } - self->currBasicBlock->contents.actions.emplace_back(curr); - self->locations[curr] = currp; - } - static void doVisitLocalSet(LocalGraphFlower* self, Expression** currp) { - auto* curr = (*currp)->cast<LocalSet>(); - // if in unreachable code, skip - if (!self->currBasicBlock) { - return; + // If this is a relevant action (a get or set, or there is a query class + // and this is an instance of it) then note it. + if (curr->is<LocalGet>() || curr->is<LocalSet>() || + (queryClass && curr->_id == *queryClass)) { + currBasicBlock->contents.actions.emplace_back(curr); + locations[curr] = getCurrentPointer(); + if (auto* set = curr->dynCast<LocalSet>()) { + currBasicBlock->contents.lastSets[set->index] = set; + } } - self->currBasicBlock->contents.actions.emplace_back(curr); - self->currBasicBlock->contents.lastSets[curr->index] = curr; - self->locations[curr] = currp; } // Each time we flow a get (or set of gets) to find its sets, we mark a @@ -203,9 +207,8 @@ struct LocalGraphFlower auto* action = actions[i]; if (auto* get = action->dynCast<LocalGet>()) { allGets[get->index].push_back(get); - } else { + } else if (auto* set = action->dynCast<LocalSet>()) { // This set is the only set for all those gets. - auto* set = action->cast<LocalSet>(); auto& gets = allGets[set->index]; for (auto* get : gets) { getSetsMap[get].insert(set); @@ -302,12 +305,8 @@ struct LocalGraphFlower // initially, but instead fill in these data structures that let us do so // later for individual gets. Specifically we need to find the location of a // local.get in the CFG. - struct BlockLocation { - // The basic block an item is in. - FlowBlock* block = nullptr; - // The index in that block that the item is at. - Index index; - }; + using BlockLocation = std::pair<FlowBlock*, Index>; + std::unordered_map<LocalGet*, BlockLocation> getLocations; // In lazy mode we also need to categorize gets and sets by their index. @@ -331,8 +330,6 @@ struct LocalGraphFlower getsByIndex[get->index].push_back(get); } else if (auto* set = actions[i]->dynCast<LocalSet>()) { setsByIndex[set->index].push_back(set); - } else { - WASM_UNREACHABLE("bad action"); } } } @@ -391,9 +388,8 @@ struct LocalGraphFlower // It will have the same sets as us. gets.push_back(otherGet); } - } else { + } else if (auto* set = curr->dynCast<LocalSet>()) { // This is a set. - auto* set = curr->cast<LocalSet>(); if (set->index == index) { // This is the only set writing to our gets. for (auto* get : gets) { @@ -444,6 +440,86 @@ struct LocalGraphFlower } } } + + // Given a bunch of gets, see if any of them are reached by the given set + // despite the obstacle expression stopping the flow whenever it is reached. + // That is, the obstacle is considered as if it was a set of the same index, + // which would trample the value and stop the set from influencing it. + LocalGraphBase::SetInfluences + getSetInfluencesGivenObstacle(LocalSet* set, + const LocalGraphBase::SetInfluences& gets, + Expression* obstacle) { + LocalGraphBase::SetInfluences ret; + // Normally flowing backwards is faster, as we start from actual gets (and + // so we avoid flowing past all the gets to large swaths of the program that + // we don't care about; and in reverse, we might go all the way to the + // entry in a wasteful manner, but most gets have an actual set, and do not + // read the default value). The situation here is a bit different, though, + // in that we might expect that going forward from the set would quickly + // reach the obstacle and stop. Still, a single branch away would cause us + // to scan lots of blocks potentially, and might not be that rare in + // general, so go backwards. (Many uninteresting branches away, that reach + // no relevant gets, are common when exceptions are enabled, as every call + // gets a branch.) + for (auto* get : gets) { + auto [block, index] = getLocations[get]; + if (!block) { + // We did not find location info for this get, which means it is + // unreachable. + continue; + } + + // Use a work queue of block locations to scan backwards from. + // Specifically we must scan the first index above it (i.e., the original + // location has a local.get there, so we start one before it). + UniqueNonrepeatingDeferredQueue<BlockLocation> work; + work.push(BlockLocation{block, index}); + auto foundSet = false; + // Flow while there is stuff to flow, and while we haven't found the set + // (once we find it, we add the get and can move on to the next get). + while (!work.empty() && !foundSet) { + auto [block, index] = work.pop(); + + // Scan backwards through this block. + while (1) { + // If we finished scanning this block (we reached the top), flow to + // predecessors. + if (index == 0) { + for (auto* pred : block->in) { + // We will scan pred from its very end. + work.push(BlockLocation{pred, Index(pred->actions.size())}); + } + break; + } + + // Continue onwards. + index--; + auto* action = block->actions[index]; + if (auto* otherSet = action->dynCast<LocalSet>()) { + if (otherSet == set) { + // We arrived at the set: add this get and stop flowing it. + ret.insert(get); + foundSet = true; + break; + } + if (otherSet->index == set->index) { + // This is another set of the same index, which halts the flow. + break; + } + } else if (action == obstacle) { + // We ran into the obstacle. Halt this flow. + break; + } + // TODO: If the action is one of the gets we are scanning, then + // either we have processed it already, or will do so later, and we + // can halt. As an optimization, we could check if we've processed + // it already and act accordingly. + } + } + } + + return ret; + } }; // LocalGraph implementation @@ -559,16 +635,18 @@ bool LocalGraph::isSSA(Index x) { return SSAIndexes.count(x); } // LazyLocalGraph -LazyLocalGraph::LazyLocalGraph(Function* func, Module* module) - : LocalGraphBase(func, module) {} +LazyLocalGraph::LazyLocalGraph(Function* func, + Module* module, + std::optional<Expression::Id> queryClass) + : LocalGraphBase(func, module), queryClass(queryClass) {} void LazyLocalGraph::makeFlower() const { // |locations| is set here and filled in by |flower|. assert(!locations); locations.emplace(); - flower = - std::make_unique<LocalGraphFlower>(getSetsMap, *locations, func, module); + flower = std::make_unique<LocalGraphFlower>( + getSetsMap, *locations, func, module, queryClass); flower->prepareLaziness(); @@ -670,4 +748,52 @@ void LazyLocalGraph::computeLocations() const { } } +LocalGraphBase::SetInfluences LazyLocalGraph::canMoveSet(LocalSet* set, + Expression* to) { + // We must have been initialized with the proper query class, so that we + // prepared the flower (if it was computed before) with that class in the + // graph. + assert(queryClass && to->_id == *queryClass); + + if (!flower) { + makeFlower(); + } + + // To compute this property, we'll do a flow from the gets that the set + // originally reaches. No other get is relevant. + auto originalGets = getSetInfluences(set); + + // To see which gets pose a problem, see which gets are still influenced by + // the set, if we consider |to| to be another set of that index, that is, an + // obstacle on the way, that tramples that local index's value. Any such + // influenced get is a problem, for example: + // + // 1. set + // 2. get + // 3. call + // 4. get + // + // The set can still influence the get on line 2, if we consider the call to + // be an obstacle. Looking at it another way, any get that is no longer + // influenced, given the obstacle, is a get that is only influenced by the + // obstacle itself, meaning that moving the set to the obstacle is valid. This + // is a slight simplification, though, since other sets may be involved: + // + // if (..) { + // x = ..; + // a(x) + // b(); + // c(x); + // } + // d(x); + // + // Say we consider moving the set of x to b(). a(x) uses x in a manner that + // will notice that, but not c(x) or d(x). c(x) is dominated by the set, but + // d(x) is not. That is, moving the set to b() leaves the set's influence + // unchanged on c(x), where that influence is full, and also on d(x), where it + // is only partial (shared with whatever value is present in x before the if). + // (But moving the set to b() does alter the set's influence on a(x)). + return flower->getSetInfluencesGivenObstacle(set, originalGets, to); +} + } // namespace wasm diff --git a/src/ir/local-graph.h b/src/ir/local-graph.h index 7b8001be6..e582751fa 100644 --- a/src/ir/local-graph.h +++ b/src/ir/local-graph.h @@ -178,7 +178,11 @@ private: struct LocalGraphFlower; struct LazyLocalGraph : public LocalGraphBase { - LazyLocalGraph(Function* func, Module* module = nullptr); + // We optionally receive an expression class to consider relevant for queries, + // see below. (Only expressions of this class can be queried later.) + LazyLocalGraph(Function* func, + Module* module = nullptr, + std::optional<Expression::Id> queryClass = std::nullopt); ~LazyLocalGraph(); // Similar APIs as in LocalGraph, but lazy versions. Each of them does a @@ -228,7 +232,39 @@ struct LazyLocalGraph : public LocalGraphBase { return *locations; } + // Query whether it is valid to move a LocalSet to a new position, that is, + // that moving it will not alter observable behavior. That means that no + // Localget is able to observe a different value than before. This returns the + // set of LocalGets that may do so, that is, the gets for which we detected a + // problem, hence if the set is empty, the set is valid to move. + // + // For example: + // + // 1. set + // 2. get + // 3. call + // 4. get + // + // If we move the set to the call, then the get on line 2 could observe a + // different value (the pre-existing value in that local, before line 1), and + // we'd return that get here. + // + // |to| must be of the class |queryClass| that is defined during construction. + // That is, we must decide ahead of time which places we want to query about + // moving LocalSets to, and can then issue queries on any of those, in an + // efficient manner. + // + // This assumes that |to| is in a position dominated by |set|, that is we are + // moving the set "forward". (In particular, that implies that the new + // position will have monotonically *less* influence than before - we don't + // need to scan all possible gets of that index in the entire function, we can + // look only on the gets influenced by the set, and see how the new position + // behaves regarding them.) + SetInfluences canMoveSet(LocalSet* set, Expression* to); + private: + std::optional<Expression::Id> queryClass; + // These data structures are mutable so that we can memoize. mutable GetSetsMap getSetsMap; diff --git a/test/gtest/CMakeLists.txt b/test/gtest/CMakeLists.txt index 7ef72db13..9b648fb65 100644 --- a/test/gtest/CMakeLists.txt +++ b/test/gtest/CMakeLists.txt @@ -8,6 +8,7 @@ set(unittest_SOURCES disjoint_sets.cpp json.cpp lattices.cpp + local-graph.cpp possible-contents.cpp printing.cpp scc.cpp diff --git a/test/gtest/local-graph.cpp b/test/gtest/local-graph.cpp new file mode 100644 index 000000000..5360813ce --- /dev/null +++ b/test/gtest/local-graph.cpp @@ -0,0 +1,347 @@ +#include "ir/local-graph.h" +#include "parser/wat-parser.h" +#include "wasm.h" + +#include "gtest/gtest.h" + +using LocalGraphTest = ::testing::Test; + +using namespace wasm; + +TEST_F(LocalGraphTest, ObstacleBasics) { + auto moduleText = R"wasm( + (module + (func $foo (result i32) + ;; A local with a set and a get, and some nops in between. + (local $x i32) + (nop) + (local.set $x + (i32.const 10) + ) + (nop) + (local.get $x) + ) + ) + )wasm"; + + Module wasm; + WATParser::parseModule(wasm, moduleText); + + // Get access to the contents of the wasm. + auto* func = wasm.functions[0].get(); + auto* block = func->body->cast<Block>(); + auto* nopA = block->list[0]->cast<Nop>(); + auto* set = block->list[1]->cast<LocalSet>(); + auto* nopB = block->list[2]->cast<Nop>(); + auto* get = block->list[3]->cast<LocalGet>(); + + { + LazyLocalGraph graph(func, &wasm); + // The set has one get. + EXPECT_EQ(graph.getSetInfluences(set).size(), 1U); + } + + { + // Construct the graph with an obstacle class, Nop. + LazyLocalGraph graph(func, &wasm, Nop::SpecificId); + // The set has one get, like before. + EXPECT_EQ(graph.getSetInfluences(set).size(), 1U); + // If the first nop is an obstacle, nothing changes: the path between the + // set and get does not include it. + EXPECT_EQ(graph.canMoveSet(set, nopA).size(), 1U); + EXPECT_EQ(*graph.canMoveSet(set, nopA).begin(), get); + // But if the second one is an obstacle, it severs the connection. + EXPECT_EQ(graph.canMoveSet(set, nopB).size(), 0U); + } +} + +TEST_F(LocalGraphTest, ObstacleMultiblock) { + auto moduleText = R"wasm( + (module + (func $foo (result i32) + ;; An if between the set and get. + (local $x i32) + (local.set $x + (i32.const 10) + ) + (if + (i32.const 42) + (then + (nop) + ) + (else + (nop) + ) + ) + (nop) + (local.get $x) + ) + ) + )wasm"; + Module wasm; + WATParser::parseModule(wasm, moduleText); + auto* func = wasm.functions[0].get(); + auto* block = func->body->cast<Block>(); + auto* set = block->list[0]->cast<LocalSet>(); + auto* iff = block->list[1]->cast<If>(); + auto* nopA = iff->ifTrue->cast<Nop>(); + auto* nopB = iff->ifTrue->cast<Nop>(); + auto* nopC = block->list[2]->cast<Nop>(); + + LazyLocalGraph graph(func, &wasm, Nop::SpecificId); + // No matter which if arm is an obstacle, we still connect. + EXPECT_EQ(graph.canMoveSet(set, nopA).size(), 1U); + EXPECT_EQ(graph.canMoveSet(set, nopB).size(), 1U); + // But the nop after the if stops us. + EXPECT_EQ(graph.canMoveSet(set, nopC).size(), 0U); +} + +TEST_F(LocalGraphTest, ObstacleUnreachable) { + auto moduleText = R"wasm( + (module + (func $foo (result i32) + ;; An unreachable between the set and get. + (local $x i32) + (local.set $x + (i32.const 10) + ) + (nop) + (unreachable) + (nop) + (local.get $x) + ) + ) + )wasm"; + Module wasm; + WATParser::parseModule(wasm, moduleText); + auto* func = wasm.functions[0].get(); + auto* block = func->body->cast<Block>(); + auto* set = block->list[0]->cast<LocalSet>(); + auto* nopA = block->list[1]->cast<Nop>(); + auto* nopB = block->list[3]->cast<Nop>(); + + LazyLocalGraph graph(func, &wasm, Nop::SpecificId); + // The get is unreachable, and the set has no gets. + EXPECT_EQ(graph.getSetInfluences(set).size(), 0U); + EXPECT_EQ(graph.canMoveSet(set, nopA).size(), 0U); + EXPECT_EQ(graph.canMoveSet(set, nopB).size(), 0U); +} + +TEST_F(LocalGraphTest, ObstacleMultiGet) { + auto moduleText = R"wasm( + (module + (func $foo + ;; A set with multiple gets. + (local $x i32) + (local.set $x + (i32.const 10) + ) + (nop) + (drop + (local.get $x) + ) + (nop) + (drop + (local.get $x) + ) + (nop) + ) + ) + )wasm"; + Module wasm; + WATParser::parseModule(wasm, moduleText); + auto* func = wasm.functions[0].get(); + auto* block = func->body->cast<Block>(); + auto* set = block->list[0]->cast<LocalSet>(); + auto* nopA = block->list[1]->cast<Nop>(); + auto* nopB = block->list[3]->cast<Nop>(); + auto* nopC = block->list[5]->cast<Nop>(); + + LazyLocalGraph graph(func, &wasm, Nop::SpecificId); + // The first nop blocks them both, but not the second, and the third blocks + // nothing. + EXPECT_EQ(graph.canMoveSet(set, nopA).size(), 0U); + EXPECT_EQ(graph.canMoveSet(set, nopB).size(), 1U); + EXPECT_EQ(graph.canMoveSet(set, nopC).size(), 2U); +} + +TEST_F(LocalGraphTest, ObstacleMultiSet) { + auto moduleText = R"wasm( + (module + (func $foo + ;; Two sets. + (local $x i32) + (local.set $x + (i32.const 10) + ) + (local.set $x + (i32.const 20) + ) + (nop) + (drop + (local.get $x) + ) + ) + ) + )wasm"; + Module wasm; + WATParser::parseModule(wasm, moduleText); + auto* func = wasm.functions[0].get(); + auto* block = func->body->cast<Block>(); + auto* setA = block->list[0]->cast<LocalSet>(); + auto* setB = block->list[1]->cast<LocalSet>(); + auto* nop = block->list[2]->cast<Nop>(); + + LazyLocalGraph graph(func, &wasm, Nop::SpecificId); + // The first set has no gets, the second has one. + EXPECT_EQ(graph.getSetInfluences(setA).size(), 0U); + EXPECT_EQ(graph.getSetInfluences(setB).size(), 1U); + // The nop blocks on the second (and the first, but it had none anyhow). + EXPECT_EQ(graph.canMoveSet(setA, nop).size(), 0U); + EXPECT_EQ(graph.canMoveSet(setB, nop).size(), 0U); +} + +TEST_F(LocalGraphTest, ObstacleMultiSetIndexes) { + auto moduleText = R"wasm( + (module + (func $foo + ;; Two sets of different indexes. + (local $x i32) + (local $y i32) + (local.set $x + (i32.const 10) + ) + (local.set $y + (i32.const 20) + ) + (nop) + (drop + (local.get $x) + ) + (nop) + (drop + (local.get $y) + ) + (nop) + ) + ) + )wasm"; + Module wasm; + WATParser::parseModule(wasm, moduleText); + auto* func = wasm.functions[0].get(); + auto* block = func->body->cast<Block>(); + auto* setA = block->list[0]->cast<LocalSet>(); + auto* setB = block->list[1]->cast<LocalSet>(); + auto* nopA = block->list[2]->cast<Nop>(); + auto* nopB = block->list[4]->cast<Nop>(); + auto* nopC = block->list[6]->cast<Nop>(); + + LazyLocalGraph graph(func, &wasm, Nop::SpecificId); + // The first nop blocks them both. + EXPECT_EQ(graph.canMoveSet(setA, nopA).size(), 0U); + EXPECT_EQ(graph.canMoveSet(setB, nopA).size(), 0U); + // The second nop only blocks one. + EXPECT_EQ(graph.canMoveSet(setA, nopB).size(), 1U); + EXPECT_EQ(graph.canMoveSet(setB, nopB).size(), 0U); + // The last nop blocks nothing. + EXPECT_EQ(graph.canMoveSet(setA, nopC).size(), 1U); + EXPECT_EQ(graph.canMoveSet(setB, nopC).size(), 1U); +} + +TEST_F(LocalGraphTest, ObstacleMultiSetIf) { + auto moduleText = R"wasm( + (module + (func $foo + ;; Two sets in an if. + (local $x i32) + (if + (i32.const 42) + (then + (local.set $x + (i32.const 10) + ) + ) + (else + (local.set $x + (i32.const 20) + ) + ) + ) + (nop) + (drop + (local.get $x) + ) + (nop) + ) + ) + )wasm"; + Module wasm; + WATParser::parseModule(wasm, moduleText); + auto* func = wasm.functions[0].get(); + auto* block = func->body->cast<Block>(); + auto* iff = block->list[0]->cast<If>(); + auto* setA = iff->ifTrue->cast<LocalSet>(); + auto* setB = iff->ifFalse->cast<LocalSet>(); + auto* nopA = block->list[1]->cast<Nop>(); + auto* nopB = block->list[3]->cast<Nop>(); + + LazyLocalGraph graph(func, &wasm, Nop::SpecificId); + // Both sets have a get. + EXPECT_EQ(graph.getSetInfluences(setA).size(), 1U); + EXPECT_EQ(graph.getSetInfluences(setB).size(), 1U); + // The first nop blocks both. + EXPECT_EQ(graph.canMoveSet(setA, nopA).size(), 0U); + EXPECT_EQ(graph.canMoveSet(setB, nopA).size(), 0U); + // The first nop blocks neither. + EXPECT_EQ(graph.canMoveSet(setA, nopB).size(), 1U); + EXPECT_EQ(graph.canMoveSet(setB, nopB).size(), 1U); +} + +TEST_F(LocalGraphTest, ObstacleStructSet) { + // Use something other than a nop to obstruct. Here we show a realistic + // situation using GC. + auto moduleText = R"wasm( + (module + (type $struct (struct (field (mut i32)))) + + (func $test + (local $struct (ref null $struct)) + (block $label + ;; A struct.set that may be skipped by the br in the if. + (struct.set $struct 0 + (local.tee $struct + (struct.new_default $struct) + ) + (if (result i32) + (i32.const 1) + (then + (br $label) + ) + (else + (i32.const 0) + ) + ) + ) + ) + (drop + (struct.get $struct 0 + (local.get $struct) + ) + ) + ) + ) + )wasm"; + Module wasm; + WATParser::parseModule(wasm, moduleText); + auto* func = wasm.functions[0].get(); + auto* outerBlock = func->body->cast<Block>(); + auto* block = outerBlock->list[0]->cast<Block>(); + auto* structSet = block->list[0]->cast<StructSet>(); + auto* tee = structSet->ref->cast<LocalSet>(); + + LazyLocalGraph graph(func, &wasm, StructSet::SpecificId); + // The tee has one get. + EXPECT_EQ(graph.getSetInfluences(tee).size(), 1U); + // The struct.set blocks one path, but not the path that skips it via the br. + EXPECT_EQ(graph.canMoveSet(tee, structSet).size(), 1U); +} |