summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/ir/LocalGraph.cpp39
-rw-r--r--src/ir/local-graph.h5
-rw-r--r--test/example/local-graph.cpp118
-rw-r--r--test/example/local-graph.txt1
4 files changed, 162 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;
diff --git a/src/ir/local-graph.h b/src/ir/local-graph.h
index 42a560c61..9e63bb3a8 100644
--- a/src/ir/local-graph.h
+++ b/src/ir/local-graph.h
@@ -48,6 +48,10 @@ struct LocalGraph {
// param)
Locations locations; // where each get and set is (for easy replacing)
+ // 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).
@@ -84,6 +88,7 @@ struct LocalGraph {
bool isSSA(Index x);
private:
+ Function* func;
std::set<Index> SSAIndexes;
};
diff --git a/test/example/local-graph.cpp b/test/example/local-graph.cpp
new file mode 100644
index 000000000..0ac435883
--- /dev/null
+++ b/test/example/local-graph.cpp
@@ -0,0 +1,118 @@
+#include <iostream>
+
+#include <ir/local-graph.h>
+#include <wasm-builder.h>
+#include <wasm.h>
+
+using namespace wasm;
+
+int main() {
+ Module wasm;
+ Builder builder(wasm);
+
+ {
+ Function foo;
+ foo.vars = {Type::i32};
+ auto* get1 = builder.makeLocalGet(0, Type::i32);
+ auto* get2 = builder.makeLocalGet(0, Type::i32);
+ foo.body = builder.makeBlock({
+ builder.makeLocalSet(0, builder.makeConst(Literal(int32_t(0)))),
+ // two equivalent gets, as both are preceded by the same single set
+ builder.makeDrop(get1),
+ builder.makeDrop(get2),
+ });
+ LocalGraph graph(&foo);
+ assert(graph.equivalent(get1, get2));
+ }
+
+ {
+ Function foo;
+ foo.vars = {Type::i32};
+ auto* get1 = builder.makeLocalGet(0, Type::i32);
+ auto* get2 = builder.makeLocalGet(0, Type::i32);
+ foo.body = builder.makeBlock({
+ // two non-equivalent gets, as there is a set in between them
+ builder.makeDrop(get1),
+ builder.makeLocalSet(0, builder.makeConst(Literal(int32_t(0)))),
+ builder.makeDrop(get2),
+ });
+ LocalGraph graph(&foo);
+ assert(!graph.equivalent(get1, get2));
+ }
+
+ {
+ Function foo;
+ foo.sig = Signature({Type::i32}, Type::none);
+ auto* get1 = builder.makeLocalGet(0, Type::i32);
+ auto* get2 = builder.makeLocalGet(0, Type::i32);
+ foo.body = builder.makeBlock({
+ // two equivalent gets of the same parameter
+ builder.makeDrop(get1),
+ builder.makeDrop(get2),
+ });
+ LocalGraph graph(&foo);
+ assert(graph.equivalent(get1, get2));
+ }
+
+ {
+ Function foo;
+ foo.sig = Signature({Type::i32}, Type::none);
+ auto* get1 = builder.makeLocalGet(0, Type::i32);
+ auto* get2 = builder.makeLocalGet(0, Type::i32);
+ foo.body = builder.makeBlock({
+ // two non-equivalent gets of the same parameter, as there is a set
+ builder.makeDrop(get1),
+ builder.makeLocalSet(0, builder.makeConst(Literal(int32_t(0)))),
+ builder.makeDrop(get2),
+ });
+ LocalGraph graph(&foo);
+ assert(!graph.equivalent(get1, get2));
+ }
+
+ {
+ Function foo;
+ foo.sig = Signature({Type::i32, Type::i32}, Type::none);
+ auto* get1 = builder.makeLocalGet(0, Type::i32);
+ auto* get2 = builder.makeLocalGet(1, Type::i32);
+ foo.body = builder.makeBlock({
+ // two non-equivalent gets as they are of different parameters
+ builder.makeDrop(get1),
+ builder.makeDrop(get2),
+ });
+ LocalGraph graph(&foo);
+ assert(!graph.equivalent(get1, get2));
+ }
+
+ {
+ Function foo;
+ foo.vars = {Type::i32, Type::i32};
+ auto* get1 = builder.makeLocalGet(0, Type::i32);
+ auto* get2 = builder.makeLocalGet(1, Type::i32);
+ foo.body = builder.makeBlock({
+ // two equivalent gets, even though they have a different index, as both
+ // use the zero initialized value
+ builder.makeDrop(get1),
+ builder.makeDrop(get2),
+ });
+ LocalGraph graph(&foo);
+ assert(graph.equivalent(get1, get2));
+ }
+
+ {
+ Function foo;
+ foo.vars = {Type::i32, Type::f64};
+ auto* get1 = builder.makeLocalGet(0, Type::i32);
+ auto* get2 = builder.makeLocalGet(1, Type::f64);
+ foo.body = builder.makeBlock({
+ // two non-equivalent gets as their zero-init value is different
+ builder.makeDrop(get1),
+ builder.makeDrop(get2),
+ });
+ LocalGraph graph(&foo);
+ assert(!graph.equivalent(get1, get2));
+ }
+
+ std::cout << "Success." << std::endl;
+
+ return 0;
+}
diff --git a/test/example/local-graph.txt b/test/example/local-graph.txt
new file mode 100644
index 000000000..a9d787cc5
--- /dev/null
+++ b/test/example/local-graph.txt
@@ -0,0 +1 @@
+Success.
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-08 09:36:50 +0000