summaryrefslogtreecommitdiff
path: root/src/ir/ExpressionAnalyzer.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/ir/ExpressionAnalyzer.cpp')
-rw-r--r--src/ir/ExpressionAnalyzer.cpp220
1 files changed, 105 insertions, 115 deletions
diff --git a/src/ir/ExpressionAnalyzer.cpp b/src/ir/ExpressionAnalyzer.cpp
index fcbd29665..aaab9050c 100644
--- a/src/ir/ExpressionAnalyzer.cpp
+++ b/src/ir/ExpressionAnalyzer.cpp
@@ -14,19 +14,19 @@
* limitations under the License.
*/
-#include "support/hash.h"
-#include "support/small_vector.h"
-#include "wasm.h"
-#include "wasm-traversal.h"
#include "ir/iteration.h"
#include "ir/load-utils.h"
#include "ir/utils.h"
+#include "support/hash.h"
+#include "support/small_vector.h"
+#include "wasm-traversal.h"
+#include "wasm.h"
namespace wasm {
// Given a stack of expressions, checks if the topmost is used as a result.
-// For example, if the parent is a block and the node is before the last position,
-// it is not used.
+// For example, if the parent is a block and the node is before the last
+// position, it is not used.
bool ExpressionAnalyzer::isResultUsed(ExpressionStack& stack, Function* func) {
for (int i = int(stack.size()) - 2; i >= 0; i--) {
auto* curr = stack[i];
@@ -35,18 +35,22 @@ bool ExpressionAnalyzer::isResultUsed(ExpressionStack& stack, Function* func) {
if (curr->is<Block>()) {
auto* block = curr->cast<Block>();
for (size_t j = 0; j < block->list.size() - 1; j++) {
- if (block->list[j] == above) return false;
+ if (block->list[j] == above)
+ return false;
}
assert(block->list.back() == above);
// continue down
} else if (curr->is<If>()) {
auto* iff = curr->cast<If>();
- if (above == iff->condition) return true;
- if (!iff->ifFalse) return false;
+ if (above == iff->condition)
+ return true;
+ if (!iff->ifFalse)
+ return false;
assert(above == iff->ifTrue || above == iff->ifFalse);
// continue down
} else {
- if (curr->is<Drop>()) return false;
+ if (curr->is<Drop>())
+ return false;
return true; // all other node types use the result
}
}
@@ -62,19 +66,23 @@ bool ExpressionAnalyzer::isResultDropped(ExpressionStack& stack) {
if (curr->is<Block>()) {
auto* block = curr->cast<Block>();
for (size_t j = 0; j < block->list.size() - 1; j++) {
- if (block->list[j] == above) return false;
+ if (block->list[j] == above)
+ return false;
}
assert(block->list.back() == above);
// continue down
} else if (curr->is<If>()) {
auto* iff = curr->cast<If>();
- if (above == iff->condition) return false;
- if (!iff->ifFalse) return false;
+ if (above == iff->condition)
+ return false;
+ if (!iff->ifFalse)
+ return false;
assert(above == iff->ifTrue || above == iff->ifFalse);
// continue down
} else {
- if (curr->is<Drop>()) return true; // dropped
- return false; // all other node types use the result
+ if (curr->is<Drop>())
+ return true; // dropped
+ return false; // all other node types use the result
}
}
return false;
@@ -98,8 +106,7 @@ bool ExpressionAnalyzer::isResultDropped(ExpressionStack& stack) {
namespace {
-template<typename T>
-void visitImmediates(Expression* curr, T& visitor) {
+template<typename T> void visitImmediates(Expression* curr, T& visitor) {
struct ImmediateVisitor : public OverriddenVisitor<ImmediateVisitor> {
T& visitor;
@@ -107,35 +114,22 @@ void visitImmediates(Expression* curr, T& visitor) {
this->visit(curr);
}
- void visitBlock(Block* curr) {
- visitor.visitScopeName(curr->name);
- }
- void visitIf(If* curr) {
- }
- void visitLoop(Loop* curr) {
- visitor.visitScopeName(curr->name);
- }
- void visitBreak(Break* curr) {
- visitor.visitScopeName(curr->name);
- }
+ void visitBlock(Block* curr) { visitor.visitScopeName(curr->name); }
+ void visitIf(If* curr) {}
+ void visitLoop(Loop* curr) { visitor.visitScopeName(curr->name); }
+ void visitBreak(Break* curr) { visitor.visitScopeName(curr->name); }
void visitSwitch(Switch* curr) {
for (auto target : curr->targets) {
visitor.visitScopeName(target);
}
visitor.visitScopeName(curr->default_);
}
- void visitCall(Call* curr) {
- visitor.visitNonScopeName(curr->target);
- }
+ void visitCall(Call* curr) { visitor.visitNonScopeName(curr->target); }
void visitCallIndirect(CallIndirect* curr) {
visitor.visitNonScopeName(curr->fullType);
}
- void visitGetLocal(GetLocal* curr) {
- visitor.visitIndex(curr->index);
- }
- void visitSetLocal(SetLocal* curr) {
- visitor.visitIndex(curr->index);
- }
+ void visitGetLocal(GetLocal* curr) { visitor.visitIndex(curr->index); }
+ void visitSetLocal(SetLocal* curr) { visitor.visitIndex(curr->index); }
void visitGetGlobal(GetGlobal* curr) {
visitor.visitNonScopeName(curr->name);
}
@@ -187,52 +181,37 @@ void visitImmediates(Expression* curr, T& visitor) {
visitor.visitInt(x);
}
}
- void visitSIMDBitselect(SIMDBitselect* curr) {
- }
- void visitSIMDShift(SIMDShift* curr) {
- visitor.visitInt(curr->op);
- }
+ void visitSIMDBitselect(SIMDBitselect* curr) {}
+ void visitSIMDShift(SIMDShift* curr) { visitor.visitInt(curr->op); }
void visitMemoryInit(MemoryInit* curr) {
visitor.visitIndex(curr->segment);
}
- void visitDataDrop(DataDrop* curr) {
- visitor.visitIndex(curr->segment);
- }
- void visitMemoryCopy(MemoryCopy* curr) {
- }
- void visitMemoryFill(MemoryFill* curr) {
- }
- void visitConst(Const* curr) {
- visitor.visitLiteral(curr->value);
- }
- void visitUnary(Unary* curr) {
- visitor.visitInt(curr->op);
- }
- void visitBinary(Binary* curr) {
- visitor.visitInt(curr->op);
- }
- void visitSelect(Select* curr) {
- }
- void visitDrop(Drop* curr) {
- }
- void visitReturn(Return* curr) {
- }
+ void visitDataDrop(DataDrop* curr) { visitor.visitIndex(curr->segment); }
+ void visitMemoryCopy(MemoryCopy* curr) {}
+ void visitMemoryFill(MemoryFill* curr) {}
+ void visitConst(Const* curr) { visitor.visitLiteral(curr->value); }
+ void visitUnary(Unary* curr) { visitor.visitInt(curr->op); }
+ void visitBinary(Binary* curr) { visitor.visitInt(curr->op); }
+ void visitSelect(Select* curr) {}
+ void visitDrop(Drop* curr) {}
+ void visitReturn(Return* curr) {}
void visitHost(Host* curr) {
visitor.visitInt(curr->op);
visitor.visitNonScopeName(curr->nameOperand);
}
- void visitNop(Nop* curr) {
- }
- void visitUnreachable(Unreachable* curr) {
- }
+ void visitNop(Nop* curr) {}
+ void visitUnreachable(Unreachable* curr) {}
} singleton(curr, visitor);
}
} // namespace
-bool ExpressionAnalyzer::flexibleEqual(Expression* left, Expression* right, ExprComparer comparer) {
+bool ExpressionAnalyzer::flexibleEqual(Expression* left,
+ Expression* right,
+ ExprComparer comparer) {
struct Comparer {
- std::map<Name, Name> rightNames; // for each name on the left, the corresponding name on the right
+ // for each name on the left, the corresponding name on the right
+ std::map<Name, Name> rightNames;
std::vector<Expression*> leftStack;
std::vector<Expression*> rightStack;
@@ -259,13 +238,15 @@ bool ExpressionAnalyzer::flexibleEqual(Expression* left, Expression* right, Expr
// Comparison is by value, except for names, which must match.
bool operator==(const Immediates& other) {
- if (scopeNames.size() != other.scopeNames.size()) return false;
+ if (scopeNames.size() != other.scopeNames.size())
+ return false;
for (Index i = 0; i < scopeNames.size(); i++) {
auto leftName = scopeNames[i];
auto rightName = other.scopeNames[i];
auto iter = parent.rightNames.find(leftName);
- // If it's not found, that means it was defined out of the expression being compared,
- // in which case we can just treat it literally - it must be exactly identical.
+ // If it's not found, that means it was defined out of the expression
+ // being compared, in which case we can just treat it literally - it
+ // must be exactly identical.
if (iter != parent.rightNames.end()) {
leftName = iter->second;
}
@@ -273,18 +254,22 @@ bool ExpressionAnalyzer::flexibleEqual(Expression* left, Expression* right, Expr
return false;
}
}
- if (nonScopeNames != other.nonScopeNames) return false;
- if (ints != other.ints) return false;
- if (literals != other.literals) return false;
- if (types != other.types) return false;
- if (indexes != other.indexes) return false;
- if (addresses != other.addresses) return false;
+ if (nonScopeNames != other.nonScopeNames)
+ return false;
+ if (ints != other.ints)
+ return false;
+ if (literals != other.literals)
+ return false;
+ if (types != other.types)
+ return false;
+ if (indexes != other.indexes)
+ return false;
+ if (addresses != other.addresses)
+ return false;
return true;
}
- bool operator!=(const Immediates& other) {
- return !(*this == other);
- }
+ bool operator!=(const Immediates& other) { return !(*this == other); }
void clear() {
scopeNames.clear();
@@ -298,7 +283,8 @@ bool ExpressionAnalyzer::flexibleEqual(Expression* left, Expression* right, Expr
};
bool noteNames(Name left, Name right) {
- if (left.is() != right.is()) return false;
+ if (left.is() != right.is())
+ return false;
if (left.is()) {
assert(rightNames.find(left) == rightNames.end());
rightNames[left] = right;
@@ -307,8 +293,7 @@ bool ExpressionAnalyzer::flexibleEqual(Expression* left, Expression* right, Expr
}
bool compare(Expression* left, Expression* right, ExprComparer comparer) {
- Immediates leftImmediates(*this),
- rightImmediates(*this);
+ Immediates leftImmediates(*this), rightImmediates(*this);
// The empty name is the same on both sides.
rightNames[Name()] = Name();
@@ -321,21 +306,28 @@ bool ExpressionAnalyzer::flexibleEqual(Expression* left, Expression* right, Expr
leftStack.pop_back();
right = rightStack.back();
rightStack.pop_back();
- if (!left != !right) return false;
- if (!left) continue;
- if (comparer(left, right)) continue; // comparison hook, before all the rest
+ if (!left != !right)
+ return false;
+ if (!left)
+ continue;
+ if (comparer(left, right))
+ continue; // comparison hook, before all the rest
// continue with normal structural comparison
- if (left->_id != right->_id) return false;
+ if (left->_id != right->_id)
+ return false;
// Blocks and loops introduce scoping.
if (auto* block = left->dynCast<Block>()) {
- if (!noteNames(block->name, right->cast<Block>()->name)) return false;
+ if (!noteNames(block->name, right->cast<Block>()->name))
+ return false;
} else if (auto* loop = left->dynCast<Loop>()) {
- if (!noteNames(loop->name, right->cast<Loop>()->name)) return false;
+ if (!noteNames(loop->name, right->cast<Loop>()->name))
+ return false;
} else {
// For all other nodes, compare their immediate values
visitImmediates(left, leftImmediates);
visitImmediates(right, rightImmediates);
- if (leftImmediates != rightImmediates) return false;
+ if (leftImmediates != rightImmediates)
+ return false;
leftImmediates.clear();
rightImmediates.clear();
}
@@ -349,10 +341,13 @@ bool ExpressionAnalyzer::flexibleEqual(Expression* left, Expression* right, Expr
rightStack.push_back(child);
counter--;
}
- // The number of child nodes must match (e.g. return has an optional one).
- if (counter != 0) return false;
+ // The number of child nodes must match (e.g. return has an optional
+ // one).
+ if (counter != 0)
+ return false;
}
- if (leftStack.size() > 0 || rightStack.size() > 0) return false;
+ if (leftStack.size() > 0 || rightStack.size() > 0)
+ return false;
return true;
}
};
@@ -366,7 +361,8 @@ HashType ExpressionAnalyzer::hash(Expression* curr) {
HashType digest = 0;
Index internalCounter = 0;
- std::map<Name, Index> internalNames; // for each internal name, its unique id
+ // for each internal name, its unique id
+ std::map<Name, Index> internalNames;
ExpressionStack stack;
void noteScopeName(Name curr) {
@@ -381,7 +377,8 @@ HashType ExpressionAnalyzer::hash(Expression* curr) {
while (stack.size() > 0) {
curr = stack.back();
stack.pop_back();
- if (!curr) continue;
+ if (!curr)
+ continue;
hash(curr->_id);
// we often don't need to hash the type, as it is tied to other values
// we are hashing anyhow, but there are exceptions: for example, a
@@ -413,9 +410,7 @@ HashType ExpressionAnalyzer::hash(Expression* curr) {
}
}
- void hash(HashType hash) {
- digest = rehash(digest, hash);
- }
+ void hash(HashType hash) { digest = rehash(digest, hash); }
void hash64(uint64_t hash) {
digest = rehash(rehash(digest, HashType(hash >> 32)), HashType(hash));
}
@@ -424,28 +419,23 @@ HashType ExpressionAnalyzer::hash(Expression* curr) {
// Names are relative, we give the same hash for
// (block $x (br $x))
// (block $y (br $y))
- static_assert(sizeof(Index) == sizeof(int32_t), "wasm64 will need changes here");
+ static_assert(sizeof(Index) == sizeof(int32_t),
+ "wasm64 will need changes here");
assert(internalNames.find(curr) != internalNames.end());
return hash(internalNames[curr]);
}
- void visitNonScopeName(Name curr) {
- return hash64(uint64_t(curr.str));
- }
- void visitInt(int32_t curr) {
- hash(curr);
- }
- void visitLiteral(Literal curr) {
- hash(std::hash<Literal>()(curr));
- }
- void visitType(Type curr) {
- hash(int32_t(curr));
- }
+ void visitNonScopeName(Name curr) { return hash64(uint64_t(curr.str)); }
+ void visitInt(int32_t curr) { hash(curr); }
+ void visitLiteral(Literal curr) { hash(std::hash<Literal>()(curr)); }
+ void visitType(Type curr) { hash(int32_t(curr)); }
void visitIndex(Index curr) {
- static_assert(sizeof(Index) == sizeof(int32_t), "wasm64 will need changes here");
+ static_assert(sizeof(Index) == sizeof(int32_t),
+ "wasm64 will need changes here");
hash(int32_t(curr));
}
void visitAddress(Address curr) {
- static_assert(sizeof(Address) == sizeof(int32_t), "wasm64 will need changes here");
+ static_assert(sizeof(Address) == sizeof(int32_t),
+ "wasm64 will need changes here");
hash(int32_t(curr));
}
};
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-19 12:46:54 +0000