summaryrefslogtreecommitdiff
path: root/src/passes/CoalesceLocals.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/passes/CoalesceLocals.cpp')
-rw-r--r--src/passes/CoalesceLocals.cpp48
1 files changed, 23 insertions, 25 deletions
diff --git a/src/passes/CoalesceLocals.cpp b/src/passes/CoalesceLocals.cpp
index f58e57e72..ba9b87527 100644
--- a/src/passes/CoalesceLocals.cpp
+++ b/src/passes/CoalesceLocals.cpp
@@ -35,6 +35,7 @@
#include "pass.h"
#include "support/learning.h"
#include "support/permutations.h"
+#include "support/sparse_square_matrix.h"
#include "wasm.h"
#ifdef CFG_PROFILE
#include "support/timing.h"
@@ -76,34 +77,31 @@ struct CoalesceLocals
// interference state
// canonicalized - accesses should check (low, high)
- std::vector<bool> interferences;
+ sparse_square_matrix<bool> interferences;
void interfere(Index i, Index j) {
if (i == j) {
return;
}
- interferences[std::min(i, j) * numLocals + std::max(i, j)] = 1;
+ interferences.set(std::min(i, j), std::max(i, j), true);
}
// optimized version where you know that low < high
void interfereLowHigh(Index low, Index high) {
assert(low < high);
- interferences[low * numLocals + high] = 1;
+ interferences.set(low, high, true);
}
void unInterfere(Index i, Index j) {
- interferences[std::min(i, j) * numLocals + std::max(i, j)] = 0;
+ interferences.set(std::min(i, j), std::max(i, j), false);
}
bool interferes(Index i, Index j) {
- return interferences[std::min(i, j) * numLocals + std::max(i, j)];
+ return interferences.get(std::min(i, j), std::max(i, j));
}
};
void CoalesceLocals::doWalkFunction(Function* func) {
- if (!canRun(func)) {
- return;
- }
super::doWalkFunction(func);
// prioritize back edges
increaseBackEdgePriorities();
@@ -145,8 +143,7 @@ void CoalesceLocals::increaseBackEdgePriorities() {
}
void CoalesceLocals::calculateInterferences() {
- interferences.resize(numLocals * numLocals);
- std::fill(interferences.begin(), interferences.end(), false);
+ interferences.recreate(numLocals);
// We will track the values in each local, using a numbering where each index
// represents a unique different value. This array maps a local index to the
@@ -379,17 +376,19 @@ void CoalesceLocals::pickIndicesFromOrder(std::vector<Index>& order,
// registers, for gzip)
std::vector<Type> types;
// new index * numLocals => list of all interferences of locals merged to it
- std::vector<bool> newInterferences;
+ sparse_square_matrix<bool> newInterferences;
+
// new index * numLocals => list of all copies of locals merged to it
- std::vector<uint8_t> newCopies;
+ sparse_square_matrix<uint8_t> newCopies;
+
indices.resize(numLocals);
types.resize(numLocals);
- newInterferences.resize(numLocals * numLocals);
- std::fill(newInterferences.begin(), newInterferences.end(), false);
+
auto numParams = getFunction()->getNumParams();
- // start with enough room for the params
- newCopies.resize(numParams * numLocals);
- std::fill(newCopies.begin(), newCopies.end(), 0);
+
+ newInterferences.recreate(numLocals);
+ newCopies.recreate(numLocals);
+
Index nextFree = 0;
removedCopies = 0;
// we can't reorder parameters, they are fixed in order, and cannot coalesce
@@ -399,8 +398,8 @@ void CoalesceLocals::pickIndicesFromOrder(std::vector<Index>& order,
indices[i] = i;
types[i] = getFunction()->getLocalType(i);
for (Index j = numParams; j < numLocals; j++) {
- newInterferences[numLocals * i + j] = interferes(i, j);
- newCopies[numLocals * i + j] = getCopies(i, j);
+ newInterferences.set(i, j, interferes(i, j));
+ newCopies.set(i, j, getCopies(i, j));
}
nextFree++;
}
@@ -409,13 +408,13 @@ void CoalesceLocals::pickIndicesFromOrder(std::vector<Index>& order,
Index found = -1;
uint8_t foundCopies = -1;
for (Index j = 0; j < nextFree; j++) {
- if (!newInterferences[j * numLocals + actual] &&
+ if (!newInterferences.get(j, actual) &&
getFunction()->getLocalType(actual) == types[j]) {
// this does not interfere, so it might be what we want. but pick the
// one eliminating the most copies (we could stop looking forward when
// there are no more items that have copies anyhow, but it doesn't seem
// to help)
- auto currCopies = newCopies[j * numLocals + actual];
+ auto currCopies = newCopies.get(j, actual);
if (found == Index(-1) || currCopies > foundCopies) {
indices[actual] = found = j;
foundCopies = currCopies;
@@ -427,7 +426,6 @@ void CoalesceLocals::pickIndicesFromOrder(std::vector<Index>& order,
types[found] = getFunction()->getLocalType(actual);
nextFree++;
removedCopies += getCopies(found, actual);
- newCopies.resize(nextFree * numLocals);
} else {
removedCopies += foundCopies;
}
@@ -438,9 +436,9 @@ void CoalesceLocals::pickIndicesFromOrder(std::vector<Index>& order,
for (Index k = i + 1; k < numLocals; k++) {
// go in the order, we only need to update for those we will see later
auto j = order[k];
- newInterferences[found * numLocals + j] =
- newInterferences[found * numLocals + j] || interferes(actual, j);
- newCopies[found * numLocals + j] += getCopies(actual, j);
+ newInterferences.set(
+ found, j, newInterferences.get(found, j) || interferes(actual, j));
+ newCopies.set(found, j, newCopies.get(found, j) + getCopies(actual, j));
}
}
}