diff options
| author | Alon Zakai <azakai@google.com> | 2021-04-29 12:57:10 -0700 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2021-04-29 12:57:10 -0700 |
| commit | b9c7497d1caae695ac5582590d73ad61abd7850f (patch) | |
| tree | bb3d6f90608a884b3c23a234cfd5b3cf6e5b3a34 /src/ir/LocalGraph.cpp | |
| parent | 59cc7e3d0a25051177a5c98d8c8bbe5f68c51da8 (diff) | |
| download | binaryen-b9c7497d1caae695ac5582590d73ad61abd7850f.tar.gz binaryen-b9c7497d1caae695ac5582590d73ad61abd7850f.tar.bz2 binaryen-b9c7497d1caae695ac5582590d73ad61abd7850f.zip | |
Add LocalGraph::equivalent (#3848)
This compares two local.gets and checks whether we are sure they are
equivalent, that is, they contain the same value.
This does not solve the general problem, but uses the existing info to get
a positive answer for the common case where two gets only receive values
by a single set, like
(local.set $x ..)
(a use.. (local.get $x))
(another use.. (local.get $x))
If they only receive values from the same single set, then we know it must
dominate them. The only risk is that the set is "in between" the gets, that is,
that the set occurs after one get and before the other. That can happen in
a loop in theory,
(loop $loop
(use (local.get $x))
(local.set $x ..some new value each iteration..)
(use (local.get $x))
(br_if $loop ..)
)
Both of those gets receive a value from the set, and they may be different
values, from different loop iterations. But as mentioned in the source code,
this is not a problem since wasm always has a zero-initialization value, and
so the first local.get in that loop would have another set from which it can
receive a value, the function entry. (The only way to avoid that is for this
entire code to be unreachable, in which case nothing matters.)
This will be useful in dead store elimination, which has to use this to reason
about references and pointers in order to be able to do anything useful with
GC and memory.
Diffstat (limited to 'src/ir/LocalGraph.cpp')
| -rw-r--r-- | src/ir/LocalGraph.cpp | 39 |
1 files changed, 38 insertions, 1 deletions
diff --git a/src/ir/LocalGraph.cpp b/src/ir/LocalGraph.cpp index bf1f7e576..2fdf1e4a4 100644 --- a/src/ir/LocalGraph.cpp +++ b/src/ir/LocalGraph.cpp @@ -227,7 +227,7 @@ struct Flower : public CFGWalker<Flower, Visitor<Flower>, Info> { // LocalGraph implementation -LocalGraph::LocalGraph(Function* func) { +LocalGraph::LocalGraph(Function* func) : func(func) { LocalGraphInternal::Flower flower(getSetses, locations, func); #ifdef LOCAL_GRAPH_DEBUG @@ -244,6 +244,43 @@ LocalGraph::LocalGraph(Function* func) { #endif } +bool LocalGraph::equivalent(LocalGet* a, LocalGet* b) { + auto& aSets = getSetses[a]; + auto& bSets = getSetses[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 + // there would definitely be another set for that get, the zero initialization + // at the function entry, if nothing else.) + if (aSets.size() != 1 || bSets.size() != 1) { + // TODO: use a LinearExecutionWalker to find trivially equal gets in basic + // blocks. that plus the above should handle 80% of cases. + // TODO: handle chains, merges and other situations + return false; + } + auto* aSet = *aSets.begin(); + auto* bSet = *bSets.begin(); + if (aSet != bSet) { + return false; + } + if (!aSet) { + // They are both nullptr, indicating the implicit value for a parameter + // or the zero for a local. + if (func->isParam(a->index)) { + // For parameters to be equivalent they must have the exact same + // index. + return a->index == b->index; + } else { + // As locals, they are both of value zero, but must have the right + // type as well. + return func->getLocalType(a->index) == func->getLocalType(b->index); + } + } else { + // They are both the same actual set. + return true; + } +} + void LocalGraph::computeInfluences() { for (auto& pair : locations) { auto* curr = pair.first; |