summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/analysis/reaching-definitions-transfer-function.h10
-rw-r--r--src/ir/LocalGraph.cpp26
-rw-r--r--src/ir/local-graph.h47
-rw-r--r--src/ir/possible-contents.cpp9
-rw-r--r--src/passes/AvoidReinterprets.cpp2
-rw-r--r--src/passes/Heap2Local.cpp4
-rw-r--r--src/passes/LoopInvariantCodeMotion.cpp2
-rw-r--r--src/passes/MergeLocals.cpp14
-rw-r--r--src/passes/OptimizeAddedConstants.cpp2
-rw-r--r--src/passes/Precompute.cpp2
-rw-r--r--src/passes/SSAify.cpp4
-rw-r--r--src/tools/wasm-fuzz-lattices.cpp4
-rw-r--r--src/wasm/wasm-stack-opts.cpp2
-rw-r--r--test/gtest/cfg.cpp24
14 files changed, 84 insertions, 68 deletions
diff --git a/src/analysis/reaching-definitions-transfer-function.h b/src/analysis/reaching-definitions-transfer-function.h
index dcf04e377..7a4fe1afc 100644
--- a/src/analysis/reaching-definitions-transfer-function.h
+++ b/src/analysis/reaching-definitions-transfer-function.h
@@ -42,7 +42,7 @@ class ReachingDefinitionsTransferFunction
std::unordered_map<Index, SmallVector<LocalSet*, 2>> indexSetses;
// LocalGraph members we need to update.
- LocalGraph::GetSetses& getSetses;
+ LocalGraph::GetSetsMap& getSetsMap;
// Fictitious LocalSet objects to reprsent a local index obtaining its value
// from its default initial value or parameter value.
@@ -86,9 +86,9 @@ public:
// are working with doesn't contain the correct Expression**s, but this is
// left in for future improvements. TODO.
ReachingDefinitionsTransferFunction(Function* func,
- LocalGraph::GetSetses& getSetses,
+ LocalGraph::GetSetsMap& getSetsMap,
LocalGraph::Locations& locations)
- : numLocals(func->getNumLocals()), getSetses(getSetses),
+ : numLocals(func->getNumLocals()), getSetsMap(getSetsMap),
lattice(listLocalSets(func, fakeInitialValueSets, fakeSetPtrs)) {
// Map every local index to a set of all the local sets which affect it.
@@ -129,9 +129,9 @@ public:
if (lattice.exists(currState, setInstance)) {
// If a pointer to a real LocalSet, add it, otherwise add a nullptr.
if (fakeSetPtrs.find(setInstance) == fakeSetPtrs.end()) {
- getSetses[curr].insert(setInstance);
+ getSetsMap[curr].insert(setInstance);
} else {
- getSetses[curr].insert(nullptr);
+ getSetsMap[curr].insert(nullptr);
}
}
}
diff --git a/src/ir/LocalGraph.cpp b/src/ir/LocalGraph.cpp
index beef635b1..e1876f6d2 100644
--- a/src/ir/LocalGraph.cpp
+++ b/src/ir/LocalGraph.cpp
@@ -40,14 +40,14 @@ struct Info {
// flow helper class. flows the gets to their sets
struct Flower : public CFGWalker<Flower, Visitor<Flower>, Info> {
- LocalGraph::GetSetses& getSetses;
+ LocalGraph::GetSetsMap& getSetsMap;
LocalGraph::Locations& locations;
- Flower(LocalGraph::GetSetses& getSetses,
+ Flower(LocalGraph::GetSetsMap& getSetsMap,
LocalGraph::Locations& locations,
Function* func,
Module* module)
- : getSetses(getSetses), locations(locations) {
+ : getSetsMap(getSetsMap), locations(locations) {
setFunction(func);
setModule(module);
// create the CFG by walking the IR
@@ -183,7 +183,7 @@ struct Flower : public CFGWalker<Flower, Visitor<Flower>, Info> {
auto* set = action->cast<LocalSet>();
auto& gets = allGets[set->index];
for (auto* get : gets) {
- getSetses[get].insert(set);
+ getSetsMap[get].insert(set);
}
gets.clear();
}
@@ -206,7 +206,7 @@ struct Flower : public CFGWalker<Flower, Visitor<Flower>, Info> {
// confusing when debugging, but it does not have any downside for
// optimization (since unreachable code should be removed anyhow).
for (auto* get : gets) {
- getSetses[get].insert(nullptr);
+ getSetsMap[get].insert(nullptr);
}
continue;
}
@@ -222,7 +222,7 @@ struct Flower : public CFGWalker<Flower, Visitor<Flower>, Info> {
if (curr == entryFlowBlock) {
// These receive a param or zero init value.
for (auto* get : gets) {
- getSetses[get].insert(nullptr);
+ getSetsMap[get].insert(nullptr);
}
}
} else {
@@ -241,7 +241,7 @@ struct Flower : public CFGWalker<Flower, Visitor<Flower>, Info> {
if (lastSet != pred->lastSets.end()) {
// There is a set here, apply it, and stop the flow.
for (auto* get : gets) {
- getSetses[get].insert(lastSet->second);
+ getSetsMap[get].insert(lastSet->second);
}
} else {
// Keep on flowing.
@@ -261,11 +261,11 @@ struct Flower : public CFGWalker<Flower, Visitor<Flower>, Info> {
// LocalGraph implementation
LocalGraph::LocalGraph(Function* func, Module* module) : func(func) {
- LocalGraphInternal::Flower flower(getSetses, locations, func, module);
+ LocalGraphInternal::Flower flower(getSetsMap, locations, func, module);
#ifdef LOCAL_GRAPH_DEBUG
std::cout << "LocalGraph::dump\n";
- for (auto& [get, sets] : getSetses) {
+ for (auto& [get, sets] : getSetsMap) {
std::cout << "GET\n" << get << " is influenced by\n";
for (auto* set : sets) {
std::cout << set << '\n';
@@ -276,8 +276,8 @@ LocalGraph::LocalGraph(Function* func, Module* module) : func(func) {
}
bool LocalGraph::equivalent(LocalGet* a, LocalGet* b) {
- auto& aSets = getSetses[a];
- auto& bSets = getSetses[b];
+ auto& aSets = getSetsMap[a];
+ auto& bSets = getSetsMap[b];
// The simple case of one set dominating two gets easily proves that they must
// have the same value. (Note that we can infer dominance from the fact that
// there is a single set: if the set did not dominate one of the gets then
@@ -315,7 +315,7 @@ bool LocalGraph::equivalent(LocalGet* a, LocalGet* b) {
void LocalGraph::computeSetInfluences() {
for (auto& [curr, _] : locations) {
if (auto* get = curr->dynCast<LocalGet>()) {
- for (auto* set : getSetses[get]) {
+ for (auto* set : getSetsMap[get]) {
setInfluences[set].insert(get);
}
}
@@ -335,7 +335,7 @@ void LocalGraph::computeGetInfluences() {
void LocalGraph::computeSSAIndexes() {
std::unordered_map<Index, std::set<LocalSet*>> indexSets;
- for (auto& [get, sets] : getSetses) {
+ for (auto& [get, sets] : getSetsMap) {
for (auto* set : sets) {
indexSets[get->index].insert(set);
}
diff --git a/src/ir/local-graph.h b/src/ir/local-graph.h
index fd9306d5c..1a674de86 100644
--- a/src/ir/local-graph.h
+++ b/src/ir/local-graph.h
@@ -39,37 +39,42 @@ namespace wasm {
// code will be removed anyhow).
//
struct LocalGraph {
- // main API
-
- // The constructor computes getSetses, the sets affecting each get.
- //
// If a module is passed in, it is used to find which features are needed in
// the computation (for example, if exception handling is disabled, then we
// can generate a simpler CFG, as calls cannot throw).
LocalGraph(Function* func, Module* module = nullptr);
- // The local.sets relevant for an index or a get. The most common case is to
- // have a single set; after that, to be a phi of 2 items, so we use a small
- // set of size 2 to avoid allocations there.
+ // Get the sets relevant for a local.get.
+ //
+ // A nullptr set means there is no local.set for that value, which means it is
+ // the initial value from the function entry: 0 for a var, the received value
+ // for a param.
+ //
+ // Often there is a single set, or a phi or two items, so we use a small set.
using Sets = SmallSet<LocalSet*, 2>;
+ const Sets& getSets(LocalGet* get) const {
+ // When we return an empty result, use a canonical constant empty set to
+ // avoid allocation.
+ static const Sets empty;
+ auto iter = getSetsMap.find(get);
+ if (iter == getSetsMap.end()) {
+ return empty;
+ }
+ return iter->second;
+ }
- using GetSetses = std::unordered_map<LocalGet*, Sets>;
-
+ // Where each get and set is. We compute this while doing the main computation
+ // and make it accessible for users, for easy replacing of things without
+ // extra work.
using Locations = std::map<Expression*, Expression**>;
-
- // externally useful information
- GetSetses getSetses; // the sets affecting each get. a nullptr set means the
- // initial value (0 for a var, the received value for a
- // param)
- Locations locations; // where each get and set is (for easy replacing)
+ Locations locations;
// Checks if two gets are equivalent, that is, definitely have the same
// value.
bool equivalent(LocalGet* a, LocalGet* b);
- // Optional: compute the influence graphs between sets and gets
- // (useful for algorithms that propagate changes).
-
+ // Optional: compute the influence graphs between sets and gets (useful for
+ // algorithms that propagate changes).
void computeSetInfluences();
void computeGetInfluences();
@@ -109,9 +114,15 @@ struct LocalGraph {
bool isSSA(Index x);
+ // Defined publicly as other utilities need similar data layouts.
+ using GetSetsMap = std::unordered_map<LocalGet*, Sets>;
+
private:
Function* func;
std::set<Index> SSAIndexes;
+
+ // A map of each get to the sets relevant to it.
+ GetSetsMap getSetsMap;
};
} // namespace wasm
diff --git a/src/ir/possible-contents.cpp b/src/ir/possible-contents.cpp
index e5e6cf659..aa6564653 100644
--- a/src/ir/possible-contents.cpp
+++ b/src/ir/possible-contents.cpp
@@ -1245,7 +1245,12 @@ struct InfoCollector
// the type must be the same for all gets of that local.)
LocalGraph localGraph(func, getModule());
- for (auto& [get, setsForGet] : localGraph.getSetses) {
+ for (auto& [curr, _] : localGraph.locations) {
+ auto* get = curr->dynCast<LocalGet>();
+ if (!get) {
+ continue;
+ }
+
auto index = get->index;
auto type = func->getLocalType(index);
if (!isRelevant(type)) {
@@ -1253,7 +1258,7 @@ struct InfoCollector
}
// Each get reads from its relevant sets.
- for (auto* set : setsForGet) {
+ for (auto* set : localGraph.getSets(get)) {
for (Index i = 0; i < type.size(); i++) {
Location source;
if (set) {
diff --git a/src/passes/AvoidReinterprets.cpp b/src/passes/AvoidReinterprets.cpp
index 3f4795303..94ae42b61 100644
--- a/src/passes/AvoidReinterprets.cpp
+++ b/src/passes/AvoidReinterprets.cpp
@@ -44,7 +44,7 @@ static Load* getSingleLoad(LocalGraph* localGraph,
std::set<LocalGet*> seen;
seen.insert(get);
while (1) {
- auto& sets = localGraph->getSetses[get];
+ auto& sets = localGraph->getSets(get);
if (sets.size() != 1) {
return nullptr;
}
diff --git a/src/passes/Heap2Local.cpp b/src/passes/Heap2Local.cpp
index 0531ebf9a..270741e6c 100644
--- a/src/passes/Heap2Local.cpp
+++ b/src/passes/Heap2Local.cpp
@@ -517,9 +517,7 @@ struct EscapeAnalyzer {
// Check that the gets can only read from the specific known sets.
for (auto* get : gets) {
- auto iter = localGraph.getSetses.find(get);
- assert(iter != localGraph.getSetses.end());
- for (auto* set : iter->second) {
+ for (auto* set : localGraph.getSets(get)) {
if (sets.count(set) == 0) {
return false;
}
diff --git a/src/passes/LoopInvariantCodeMotion.cpp b/src/passes/LoopInvariantCodeMotion.cpp
index 4239e39c3..321267e8e 100644
--- a/src/passes/LoopInvariantCodeMotion.cpp
+++ b/src/passes/LoopInvariantCodeMotion.cpp
@@ -228,7 +228,7 @@ struct LoopInvariantCodeMotion
bool hasGetDependingOnLoopSet(Expression* curr, LoopSets& loopSets) {
FindAll<LocalGet> gets(curr);
for (auto* get : gets.list) {
- auto& sets = localGraph->getSetses[get];
+ auto& sets = localGraph->getSets(get);
for (auto* set : sets) {
// nullptr means a parameter or zero-init value;
// no danger to us.
diff --git a/src/passes/MergeLocals.cpp b/src/passes/MergeLocals.cpp
index c43ec8534..b04215d73 100644
--- a/src/passes/MergeLocals.cpp
+++ b/src/passes/MergeLocals.cpp
@@ -123,9 +123,10 @@ struct MergeLocals
// however, it may depend on other writes too, if there is a
// merge/phi, and in that case we can't do anything
assert(influencedGet->index == trivial->index);
- if (preGraph.getSetses[influencedGet].size() == 1) {
+ auto& sets = preGraph.getSets(influencedGet);
+ if (sets.size() == 1) {
// this is ok
- assert(*preGraph.getSetses[influencedGet].begin() == trivial);
+ assert(*sets.begin() == trivial);
// If local types are different (when one is a subtype of the
// other), don't optimize
if (func->getLocalType(copy->index) != influencedGet->type) {
@@ -161,9 +162,10 @@ struct MergeLocals
for (auto* influencedGet : copyInfluences) {
// as above, avoid merges/phis
assert(influencedGet->index == copy->index);
- if (preGraph.getSetses[influencedGet].size() == 1) {
+ auto& sets = preGraph.getSets(influencedGet);
+ if (sets.size() == 1) {
// this is ok
- assert(*preGraph.getSetses[influencedGet].begin() == copy);
+ assert(*sets.begin() == copy);
// If local types are different (when one is a subtype of the
// other), don't optimize
if (func->getLocalType(trivial->index) != influencedGet->type) {
@@ -199,7 +201,7 @@ struct MergeLocals
auto& trivialInfluences = preGraph.setInfluences[trivial];
for (auto* influencedGet : trivialInfluences) {
// verify the set
- auto& sets = postGraph.getSetses[influencedGet];
+ auto& sets = postGraph.getSets(influencedGet);
if (sets.size() != 1 || *sets.begin() != copy) {
// not good, undo all the changes for this copy
for (auto* undo : trivialInfluences) {
@@ -213,7 +215,7 @@ struct MergeLocals
auto& copyInfluences = preGraph.setInfluences[copy];
for (auto* influencedGet : copyInfluences) {
// verify the set
- auto& sets = postGraph.getSetses[influencedGet];
+ auto& sets = postGraph.getSets(influencedGet);
if (sets.size() != 1 || *sets.begin() != trivial) {
// not good, undo all the changes for this copy
for (auto* undo : copyInfluences) {
diff --git a/src/passes/OptimizeAddedConstants.cpp b/src/passes/OptimizeAddedConstants.cpp
index 934fe8be8..af5d48be7 100644
--- a/src/passes/OptimizeAddedConstants.cpp
+++ b/src/passes/OptimizeAddedConstants.cpp
@@ -79,7 +79,7 @@ public:
//
// This is only valid if y does not change in the middle!
if (auto* get = curr->ptr->template dynCast<LocalGet>()) {
- auto& sets = localGraph->getSetses[get];
+ auto& sets = localGraph->getSets(get);
if (sets.size() == 1) {
auto* set = *sets.begin();
// May be a zero-init (in which case, we can ignore it). Must also be
diff --git a/src/passes/Precompute.cpp b/src/passes/Precompute.cpp
index 6e0d7535f..61220ece8 100644
--- a/src/passes/Precompute.cpp
+++ b/src/passes/Precompute.cpp
@@ -814,7 +814,7 @@ private:
// for this get to have constant value, all sets must agree
Literals values;
bool first = true;
- for (auto* set : localGraph.getSetses[get]) {
+ for (auto* set : localGraph.getSets(get)) {
Literals curr;
if (set == nullptr) {
if (getFunction()->isVar(get->index)) {
diff --git a/src/passes/SSAify.cpp b/src/passes/SSAify.cpp
index 547b9cb53..0a9c6891d 100644
--- a/src/passes/SSAify.cpp
+++ b/src/passes/SSAify.cpp
@@ -121,7 +121,7 @@ struct SSAify : public Pass {
bool hasMerges(LocalSet* set, LocalGraph& graph) {
for (auto* get : graph.setInfluences[set]) {
- if (graph.getSetses[get].size() > 1) {
+ if (graph.getSets(get).size() > 1) {
return true;
}
}
@@ -131,7 +131,7 @@ struct SSAify : public Pass {
void computeGetsAndPhis(LocalGraph& graph) {
FindAll<LocalGet> gets(func->body);
for (auto* get : gets.list) {
- auto& sets = graph.getSetses[get];
+ auto& sets = graph.getSets(get);
if (sets.size() == 0) {
continue; // unreachable, ignore
}
diff --git a/src/tools/wasm-fuzz-lattices.cpp b/src/tools/wasm-fuzz-lattices.cpp
index 551ddbaf1..a6231cd42 100644
--- a/src/tools/wasm-fuzz-lattices.cpp
+++ b/src/tools/wasm-fuzz-lattices.cpp
@@ -829,7 +829,7 @@ struct LivenessChecker {
// Struct to set up and check reaching definitions analysis lattice and transfer
// function.
struct ReachingDefinitionsChecker {
- LocalGraph::GetSetses getSetses;
+ LocalGraph::GetSetsMap getSetsMap;
LocalGraph::Locations locations;
ReachingDefinitionsTransferFunction txfn;
AnalysisChecker<FinitePowersetLattice<LocalSet*>,
@@ -838,7 +838,7 @@ struct ReachingDefinitionsChecker {
ReachingDefinitionsChecker(Function* func,
uint64_t latticeElementSeed,
Name funcName)
- : txfn(func, getSetses, locations),
+ : txfn(func, getSetsMap, locations),
checker(txfn.lattice,
txfn,
"FinitePowersetLattice<LocalSet*>",
diff --git a/src/wasm/wasm-stack-opts.cpp b/src/wasm/wasm-stack-opts.cpp
index cf4c094b5..5902b40a5 100644
--- a/src/wasm/wasm-stack-opts.cpp
+++ b/src/wasm/wasm-stack-opts.cpp
@@ -225,7 +225,7 @@ void StackIROptimizer::local2Stack() {
if (set->index == get->index) {
// This might be a proper set-get pair, where the set is
// used by this get and nothing else, check that.
- auto& sets = localGraph.getSetses[get];
+ auto& sets = localGraph.getSets(get);
if (sets.size() == 1 && *sets.begin() == set) {
auto& setInfluences = localGraph.setInfluences[set];
// If this has the proper value of 1, also do the potentially-
diff --git a/test/gtest/cfg.cpp b/test/gtest/cfg.cpp
index e72341b32..b8d26caa4 100644
--- a/test/gtest/cfg.cpp
+++ b/test/gtest/cfg.cpp
@@ -298,10 +298,10 @@ TEST_F(CFGTest, LinearReachingDefinitions) {
Function* func = wasm.getFunction("bar");
CFG cfg = CFG::fromFunction(func);
- LocalGraph::GetSetses getSetses;
+ LocalGraph::GetSetsMap getSetsMap;
LocalGraph::Locations locations;
ReachingDefinitionsTransferFunction transferFunction(
- func, getSetses, locations);
+ func, getSetsMap, locations);
MonotoneCFGAnalyzer<FinitePowersetLattice<LocalSet*>,
ReachingDefinitionsTransferFunction>
@@ -320,12 +320,12 @@ TEST_F(CFGTest, LinearReachingDefinitions) {
LocalGet* getC = foundGets.list[2];
LocalSet* setA1 = foundSets.list[0];
- LocalGraph::GetSetses expectedResult;
+ LocalGraph::GetSetsMap expectedResult;
expectedResult[getA1].insert(setA1);
expectedResult[getA2].insert(setA1);
expectedResult[getC].insert(nullptr);
- EXPECT_EQ(expectedResult, getSetses);
+ EXPECT_EQ(expectedResult, getSetsMap);
}
TEST_F(CFGTest, ReachingDefinitionsIf) {
@@ -369,10 +369,10 @@ TEST_F(CFGTest, ReachingDefinitionsIf) {
Function* func = wasm.getFunction("bar");
CFG cfg = CFG::fromFunction(func);
- LocalGraph::GetSetses getSetses;
+ LocalGraph::GetSetsMap getSetsMap;
LocalGraph::Locations locations;
ReachingDefinitionsTransferFunction transferFunction(
- func, getSetses, locations);
+ func, getSetsMap, locations);
MonotoneCFGAnalyzer<FinitePowersetLattice<LocalSet*>,
ReachingDefinitionsTransferFunction>
@@ -390,14 +390,14 @@ TEST_F(CFGTest, ReachingDefinitionsIf) {
LocalSet* setB = foundSets.list[1];
LocalSet* setA2 = foundSets.list[2];
- LocalGraph::GetSetses expectedResult;
+ LocalGraph::GetSetsMap expectedResult;
expectedResult[getA1].insert(setA1);
expectedResult[getB].insert(nullptr);
expectedResult[getB].insert(setB);
expectedResult[getA2].insert(setA1);
expectedResult[getA2].insert(setA2);
- EXPECT_EQ(expectedResult, getSetses);
+ EXPECT_EQ(expectedResult, getSetsMap);
}
TEST_F(CFGTest, ReachingDefinitionsLoop) {
@@ -437,10 +437,10 @@ TEST_F(CFGTest, ReachingDefinitionsLoop) {
Function* func = wasm.getFunction("bar");
CFG cfg = CFG::fromFunction(func);
- LocalGraph::GetSetses getSetses;
+ LocalGraph::GetSetsMap getSetsMap;
LocalGraph::Locations locations;
ReachingDefinitionsTransferFunction transferFunction(
- func, getSetses, locations);
+ func, getSetsMap, locations);
MonotoneCFGAnalyzer<FinitePowersetLattice<LocalSet*>,
ReachingDefinitionsTransferFunction>
@@ -458,7 +458,7 @@ TEST_F(CFGTest, ReachingDefinitionsLoop) {
LocalGet* getA4 = foundGets.list[4];
LocalSet* setA = foundSets.list[0];
- LocalGraph::GetSetses expectedResult;
+ LocalGraph::GetSetsMap expectedResult;
expectedResult[getA1].insert(nullptr);
expectedResult[getA1].insert(setA);
expectedResult[getA2].insert(nullptr);
@@ -467,5 +467,5 @@ TEST_F(CFGTest, ReachingDefinitionsLoop) {
expectedResult[getB].insert(nullptr);
expectedResult[getA4].insert(setA);
- EXPECT_EQ(expectedResult, getSetses);
+ EXPECT_EQ(expectedResult, getSetsMap);
}
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-08 13:59:46 +0000