summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/ir/numbering.h67
-rw-r--r--src/passes/RedundantSetElimination.cpp81
2 files changed, 100 insertions, 48 deletions
diff --git a/src/ir/numbering.h b/src/ir/numbering.h
new file mode 100644
index 000000000..e4b412664
--- /dev/null
+++ b/src/ir/numbering.h
@@ -0,0 +1,67 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef wasm_ir_numberings_h
+#define wasm_ir_numberings_h
+
+#include "wasm.h"
+
+namespace wasm {
+
+// General value numbering: Returns a number for an expression. Expressions with
+// the same number must be identical in value; expressions with different values
+// might happen to be identical at runtime.
+class ValueNumbering {
+public:
+ // Get the value numbering of an arbitrary expression.
+ Index getValue(Expression* expr) {
+ if (Properties::isConstantExpression(expr)) {
+ return getValue(Properties::getLiterals(expr));
+ } else {
+ auto iter = expressionValues.find(expr);
+ if (iter != expressionValues.end()) {
+ return iter->second;
+ }
+ // TODO: full GVN to check for different expressions with the same value.
+ return expressionValues[expr] = getUniqueValue();
+ }
+ }
+
+ // Get the value numbering of an arbitrary set of constants.
+ Index getValue(Literals lit) {
+ auto iter = literalValues.find(lit);
+ if (iter != literalValues.end()) {
+ return iter->second;
+ }
+ return literalValues[lit] = getUniqueValue();
+ }
+
+ // Return a new unique value. Normally this is called internally, but there
+ // are also use cases for the user of the class to call this, when they want
+ // to get a new value that will not collide with any others.
+ Index getUniqueValue() { return nextValue++; }
+
+private:
+ Index nextValue = 0;
+
+ // Cache the value numbers of literals and expressions.
+ std::unordered_map<Literals, Index> literalValues;
+ std::unordered_map<Expression*, Index> expressionValues;
+};
+
+} // namespace wasm
+
+#endif // wasm_ir_numberings_h
diff --git a/src/passes/RedundantSetElimination.cpp b/src/passes/RedundantSetElimination.cpp
index f42119a92..56fca4bee 100644
--- a/src/passes/RedundantSetElimination.cpp
+++ b/src/passes/RedundantSetElimination.cpp
@@ -35,6 +35,7 @@
#include <cfg/cfg-traversal.h>
#include <ir/literal-utils.h>
+#include <ir/numbering.h>
#include <ir/properties.h>
#include <ir/utils.h>
#include <pass.h>
@@ -44,11 +45,9 @@
namespace wasm {
-// We do a very simple numbering of local values, just a unique
-// number for constants so far, enough to see
-// trivial duplication. LocalValues maps each local index to
-// its current value
-typedef std::vector<Index> LocalValues;
+// Map each local index to its current value number (which is computed in
+// ValueNumbering).
+using LocalValues = std::vector<Index>;
namespace {
@@ -84,6 +83,10 @@ struct RedundantSetElimination
if (numLocals == 0) {
return; // nothing to do
}
+
+ // Create a unique value for use to mark unseen locations.
+ unseenValue = valueNumbering.getUniqueValue();
+
// create the CFG by walking the IR
CFGWalker<RedundantSetElimination, Visitor<RedundantSetElimination>, Info>::
doWalkFunction(func);
@@ -93,47 +96,30 @@ struct RedundantSetElimination
optimize();
}
- // numbering
+ // Use a value numbering for the values of expressions.
+ ValueNumbering valueNumbering;
- Index nextValue = 1; // 0 is reserved for the "unseen value"
- // each constant has a value
- std::unordered_map<Literals, Index> literalValues;
- // each value can have a value
- std::unordered_map<Expression*, Index> expressionValues;
- // each block has values for each merge
+ // In additon to valueNumbering, each block has values for each merge.
std::unordered_map<BasicBlock*, std::unordered_map<Index, Index>>
blockMergeValues;
- Index getUnseenValue() { // we haven't seen this location yet
- return 0;
- }
- Index getUniqueValue() {
-#ifdef RSE_DEBUG
- std::cout << "new unique value " << nextValue << '\n';
-#endif
- return nextValue++;
- }
+ // A value that indicates we haven't seen this location yet.
+ Index unseenValue;
- Index getLiteralValue(Literals lit) {
- auto iter = literalValues.find(lit);
- if (iter != literalValues.end()) {
- return iter->second;
- }
+ Index getUniqueValue() {
+ auto value = valueNumbering.getUniqueValue();
#ifdef RSE_DEBUG
- std::cout << "new literal value for " << lit << '\n';
+ std::cout << "new unique value " << value << '\n';
#endif
- return literalValues[lit] = getUniqueValue();
+ return value;
}
- Index getExpressionValue(Expression* expr) {
- auto iter = expressionValues.find(expr);
- if (iter != expressionValues.end()) {
- return iter->second;
- }
+ Index getValue(Literals lit) {
+ auto value = valueNumbering.getValue(lit);
#ifdef RSE_DEBUG
- std::cout << "new expr value for " << expr << '\n';
+ std::cout << "lit value " << value << '\n';
#endif
- return expressionValues[expr] = getUniqueValue();
+ return value;
}
Index getBlockMergeValue(BasicBlock* block, Index index) {
@@ -162,17 +148,16 @@ struct RedundantSetElimination
return value == iter2->second;
}
- Index getValue(Expression* value, LocalValues& currValues) {
- if (Properties::isConstantExpression(value)) {
- // a constant
- return getLiteralValue(Properties::getLiterals(value));
- } else if (auto* get = value->dynCast<LocalGet>()) {
+ Index getValue(Expression* expr, LocalValues& currValues) {
+ if (auto* get = expr->dynCast<LocalGet>()) {
// a copy of whatever that was
return currValues[get->index];
- } else {
- // get the value's own unique value
- return getExpressionValue(value);
}
+ auto value = valueNumbering.getValue(expr);
+#ifdef RSE_DEBUG
+ std::cout << "expr value " << value << '\n';
+#endif
+ return value;
}
// flowing
@@ -196,20 +181,20 @@ struct RedundantSetElimination
#endif
start[i] = getUniqueValue();
} else {
- start[i] = getLiteralValue(Literal::makeZeros(type));
+ start[i] = getValue(Literal::makeZeros(type));
}
}
} else {
// other blocks have all unseen values to begin with
for (Index i = 0; i < numLocals; i++) {
- start[i] = getUnseenValue();
+ start[i] = unseenValue;
}
}
// the ends all begin unseen
LocalValues& end = block->contents.end;
end.resize(numLocals);
for (Index i = 0; i < numLocals; i++) {
- end[i] = getUnseenValue();
+ end[i] = unseenValue;
}
}
// keep working while stuff is flowing. we use a unique deferred queue
@@ -280,9 +265,9 @@ struct RedundantSetElimination
iter++;
while (iter != in.end()) {
auto otherValue = (*iter)->contents.end[i];
- if (value == getUnseenValue()) {
+ if (value == unseenValue) {
value = otherValue;
- } else if (otherValue == getUnseenValue()) {
+ } else if (otherValue == unseenValue) {
// nothing to do, other has no information
} else if (value != otherValue) {
// 2 different values, this is a merged value
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-06 22:21:12 +0000