summaryrefslogtreecommitdiff
path: root/src/passes/OptimizeCasts.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/passes/OptimizeCasts.cpp')
-rw-r--r--src/passes/OptimizeCasts.cpp340
1 files changed, 324 insertions, 16 deletions
diff --git a/src/passes/OptimizeCasts.cpp b/src/passes/OptimizeCasts.cpp
index 8f13981bf..e4d7b1647 100644
--- a/src/passes/OptimizeCasts.cpp
+++ b/src/passes/OptimizeCasts.cpp
@@ -72,14 +72,32 @@
// sense in new pass anyhow, and things should be simpler overall to keep such
// casts all in one pass, here.
//
-// TODO: 1. Move casts earlier in a basic block as well, at least in
-// traps-never-happen mode where we can assume they never fail, and
-// perhaps in other situations too.
-// TODO: 2. Look past individual basic blocks? This may be worth considering
+// Also, we can move more refined casts earlier in a basic block before applying
+// the above optimization. This may allow more refined casts to be used by the
+// optimization earlier and allow trapping casts to trap earlier. For instance,
+// the below example:
+//
+// (some.operation
+// (local.get $ref)
+// (ref.cast .. (local.get $ref))
+// )
+//
+// could be converted to:
+//
+// (some.operation
+// (ref.cast (local.get $ref))
+// (ref.cast .. (local.get $ref))
+// )
+//
+// Note that right now, we only consider RefAs with op RefAsNonNull as a cast.
+// RefAs with ExternInternalize and ExternExternalize are not considered casts
+// when obtaining fallthroughs, and so are ignored.
+//
+// TODO: 1. Look past individual basic blocks? This may be worth considering
// given the pattern of a cast appearing in an if condition that is
// then used in an if arm, for example, where simple dominance shows
// the cast can be reused.
-// TODO: 3. Look at LocalSet as well and not just Get. That would add some
+// TODO: 2. Look at LocalSet as well and not just Get. That would add some
// overlap with the other passes mentioned above (SimplifyLocals and
// RedundantSetElimination also track sets and can switch a get to use
// a better set's index when that refines the type). But once we do the
@@ -91,6 +109,7 @@
// make them operate "backwards" and/or past basic blocks).
//
+#include "ir/effects.h"
#include "ir/linear-execution.h"
#include "ir/properties.h"
#include "ir/utils.h"
@@ -102,6 +121,284 @@ namespace wasm {
namespace {
+// Contains information about a RefCast we want to move to a target LocalGet.
+struct RefCastInfo {
+ LocalGet* target = nullptr;
+ RefCast* bestCast = nullptr;
+};
+
+// Contains information about a RefAs we want to move to a target LocalGet.
+// Currently only RefAsNonNull will be moved.
+struct RefAsInfo {
+ LocalGet* target = nullptr;
+ RefAs* bestCast = nullptr;
+};
+
+// Find a cast to move earlier to another local.get. More refined subtypes are
+// chosen over less refined ones.
+struct EarlyCastFinder
+ : public LinearExecutionWalker<EarlyCastFinder,
+ UnifiedExpressionVisitor<EarlyCastFinder>> {
+ PassOptions options;
+ size_t numLocals;
+
+ // For each local index, tracks the current earliest local.get that we can
+ // move a cast to without side-effects, and the most refined cast that we can
+ // move to it (could be already at the earliest local.get).
+ //
+ // Note that we track a cast already on the get since we only want to move
+ // better casts to it: if the best cast is already on the get, there is no
+ // work to do.
+ std::vector<RefCastInfo> currRefCastMove;
+ std::vector<RefAsInfo> currRefAsMove;
+
+ // Used to analyze expressions to see if casts can be moved past them.
+ EffectAnalyzer testRefCast;
+ EffectAnalyzer testRefAs;
+
+ // Maps LocalGets to the most refined RefCast to move to it, to be used by the
+ // EarlyCastApplier. If the most refined RefCast is already at the desired
+ // LocalGet, it does not appear here. In the normal case, only one RefCast
+ // needs to be moved to a LocalGet; if a LocalGet is cast to multiple types
+ // which are not subtypes of each other then a trap is inevitable, and we
+ // assume this would already be optimized away beforehand, so we don't care
+ // about this special case.
+ std::unordered_map<LocalGet*, RefCast*> refCastToApply;
+
+ // Maps LocalGets to a RefAs to move to it, to be used by the
+ // EarlyCastApplier. As of right now RefAsNonNull is the only non-extern cast,
+ // so we only have one type of RefAs cast to move.
+ std::unordered_map<LocalGet*, RefAs*> refAsToApply;
+
+ EarlyCastFinder(PassOptions options, Module* module, Function* func)
+ : options(options), numLocals(func->getNumLocals()),
+ currRefCastMove(func->getNumLocals()),
+ currRefAsMove(func->getNumLocals()), testRefCast(options, *module),
+ testRefAs(options, *module) {
+
+ // TODO: generalize this when we handle more than RefAsNonNull.
+ RefCast dummyRefCast(module->allocator);
+ RefAs dummyRefAs(module->allocator);
+ dummyRefAs.op = RefAsNonNull;
+
+ testRefCast.visit(&dummyRefCast);
+ testRefAs.visit(&dummyRefAs);
+ }
+
+ // We track information as we go, looking for the best cast to move backwards,
+ // and when we hit a barrier - a position we can't optimize past - then we
+ // flush/finalize the work we've done so far, since nothing better can appear
+ // later. We ignore the best cast if it is already at the desired location.
+ void flushRefCastResult(size_t index, Module& module) {
+ auto& target = currRefCastMove[index].target;
+ if (target) {
+ auto& bestCast = currRefCastMove[index].bestCast;
+ if (bestCast) {
+ // If the fallthrough is equal to the target, this means the cast is
+ // already at the target local.get and doesn't need to be duplicated
+ // again.
+ auto* fallthrough =
+ Properties::getFallthrough(bestCast, options, module);
+ if (fallthrough != target) {
+ refCastToApply[target] = bestCast;
+ }
+ bestCast = nullptr;
+ }
+ target = nullptr;
+ }
+ }
+
+ // Does the same as above function, but for RefAs instead of RefCast.
+ void flushRefAsResult(size_t index, Module& module) {
+ auto& target = currRefAsMove[index].target;
+ if (target) {
+ auto& bestCast = currRefAsMove[index].bestCast;
+ if (bestCast) {
+ // As in flushRefCastResult, we need to check if the cast is already at
+ // the target and thus does not need to be moved.
+ auto* fallthrough =
+ Properties::getFallthrough(bestCast, options, module);
+ if (fallthrough != target) {
+ refAsToApply[target] = bestCast;
+ }
+ bestCast = nullptr;
+ }
+ target = nullptr;
+ }
+ }
+
+ inline void flushAll() {
+ for (size_t i = 0; i < numLocals; i++) {
+ flushRefCastResult(i, *getModule());
+ flushRefAsResult(i, *getModule());
+ }
+ }
+
+ static void doNoteNonLinear(EarlyCastFinder* self, Expression** currp) {
+ self->flushAll();
+ }
+
+ void visitFunction(Function* curr) { flushAll(); }
+
+ void visitExpression(Expression* curr) {
+ // A new one is instantiated for each expression to determine
+ // if a cast can be moved past it.
+ ShallowEffectAnalyzer currAnalyzer(options, *getModule(), curr);
+
+ if (testRefCast.invalidates(currAnalyzer)) {
+ for (size_t i = 0; i < numLocals; i++) {
+ flushRefCastResult(i, *getModule());
+ }
+ }
+
+ if (testRefAs.invalidates(currAnalyzer)) {
+ for (size_t i = 0; i < numLocals; i++) {
+ flushRefAsResult(i, *getModule());
+ }
+ }
+ }
+
+ void visitLocalSet(LocalSet* curr) {
+ visitExpression(curr);
+
+ flushRefCastResult(curr->index, *getModule());
+ flushRefAsResult(curr->index, *getModule());
+ }
+
+ void visitLocalGet(LocalGet* curr) {
+ visitExpression(curr);
+
+ if (!currRefCastMove[curr->index].target) {
+ currRefCastMove[curr->index].target = curr;
+ }
+
+ // As we only move RefAsNonNull RefAs casts right now, we should
+ // ignore a LocalGet if the type is already non-nullable, as
+ // adding an extra ref.as_non_null has no effect.
+ if (!currRefAsMove[curr->index].target && curr->type.isNullable()) {
+ currRefAsMove[curr->index].target = curr;
+ }
+ }
+
+ void visitRefAs(RefAs* curr) {
+ visitExpression(curr);
+
+ // TODO: support more than RefAsNonNull.
+ if (curr->op != RefAsNonNull) {
+ return;
+ }
+
+ auto* fallthrough = Properties::getFallthrough(curr, options, *getModule());
+ if (auto* get = fallthrough->dynCast<LocalGet>()) {
+ auto& bestMove = currRefAsMove[get->index];
+ if (bestMove.target && !bestMove.bestCast) {
+ bestMove.bestCast = curr;
+ }
+ }
+ }
+
+ void visitRefCast(RefCast* curr) {
+ visitExpression(curr);
+
+ // Using fallthroughs here is fine due to the following cases.
+ // Suppose we have types $A->$B->$C (where $C is the most refined)
+ // and $D, which is an unrelated type.
+ // Case 1:
+ // (ref.cast $A (ref.cast $C (local.get $x)))
+ //
+ // ref.cast $C is initially chosen for $x. Then we consider ref.cast $A.
+ // Since $A is less refined than $C, we ignore it.
+ //
+ // Case 2:
+ // (ref.cast $C (ref.cast $A (local.get $x)))
+ //
+ // ref.cast $A is initially chosen for $x. Then we consider ref.cast $C,
+ // which is more refined than ref.cast $A, so we replace it with ref.cast
+ // $C.
+ //
+ // Case 3:
+ // (ref.cast $B (ref.cast $B (local.get $x)))
+ //
+ // We initially choose to move the inner ref.cast $B. When we consider the
+ // outer ref.cast $B, we can see that it has the same type as tge existing
+ // ref.cast $B, so we ignore it.
+ //
+ // Case 4:
+ // (ref.cast $D (ref.cast $C (local.get $x)))
+ //
+ // This would produce a trap and should already be optimized away
+ // beforehand.
+ //
+ // If the best cast is already at the target location, we will still track
+ // it in currRefCastMove to see if we can obtain a better cast. However, we
+ // won't flush it.
+
+ auto* fallthrough = Properties::getFallthrough(curr, options, *getModule());
+ if (auto* get = fallthrough->dynCast<LocalGet>()) {
+ auto& bestMove = currRefCastMove[get->index];
+ // Do not move a cast if its type is not related to the target
+ // local.get's type (i.e. not in a subtyping relationship). Otherwise
+ // a type error will occur. Also, if the target local.get's type is
+ // already more refined than this current cast, there is no point in
+ // moving it.
+ if (bestMove.target && bestMove.target->type != curr->type &&
+ Type::isSubType(curr->type, bestMove.target->type)) {
+ if (!bestMove.bestCast) {
+ // If there isn't any other cast to move, the current cast is the
+ // best.
+ bestMove.bestCast = curr;
+ } else if (bestMove.bestCast->type != curr->type &&
+ Type::isSubType(curr->type, bestMove.bestCast->type)) {
+ // If the current cast is more refined than the best cast to move,
+ // change the best cast to move.
+ bestMove.bestCast = curr;
+ }
+ // We don't care about the safety of the cast at present. If there are
+ // two casts with the same type one being safe and one being unsafe, the
+ // first cast that we visit will be chosen to be moved. Perhaps in the
+ // future we can consider prioritizing unsafe casts over safe ones since
+ // users may be more interested in that.
+ }
+ }
+ }
+
+ bool hasCastsToMove() {
+ return refCastToApply.size() > 0 || refAsToApply.size() > 0;
+ }
+};
+
+// Given a set of RefAs and RefCast casts to move to specified
+// earlier expressions, duplicate the cast at the specified
+// earlier expression. The original cast that we are moving will
+// be optimized out by a later pass once we have applied the same
+// cast earlier.
+struct EarlyCastApplier : public PostWalker<EarlyCastApplier> {
+ EarlyCastFinder& finder;
+
+ EarlyCastApplier(EarlyCastFinder& finder) : finder(finder) {}
+
+ // RefCast casts are applied before RefAs casts. If there are multiple
+ // casts to apply to a location, they are nested within one another. Only
+ // at most one RefCast and at most one RefAs can be applied.
+ void visitLocalGet(LocalGet* curr) {
+ Expression* currPtr = curr;
+
+ auto refCastIter = finder.refCastToApply.find(curr);
+ if (refCastIter != finder.refCastToApply.end()) {
+ currPtr = replaceCurrent(Builder(*getModule())
+ .makeRefCast(currPtr,
+ refCastIter->second->type,
+ refCastIter->second->safety));
+ }
+
+ auto refAsIter = finder.refAsToApply.find(curr);
+ if (refAsIter != finder.refAsToApply.end()) {
+ replaceCurrent(
+ Builder(*getModule()).makeRefAs(refAsIter->second->op, currPtr));
+ }
+ }
+};
+
// Find the best casted verisons of local.gets: other local.gets with the same
// value, but cast to a more refined type.
struct BestCastFinder : public LinearExecutionWalker<BestCastFinder> {
@@ -215,22 +512,33 @@ struct OptimizeCasts : public WalkerPass<PostWalker<OptimizeCasts>> {
return;
}
- // First, find the best casts that we want to use.
+ // Look for casts which can be moved earlier.
+ EarlyCastFinder earlyCastFinder(getPassOptions(), getModule(), func);
+ earlyCastFinder.walkFunctionInModule(func, getModule());
+
+ if (earlyCastFinder.hasCastsToMove()) {
+ // Duplicate casts to earlier locations if possible.
+ EarlyCastApplier earlyCastApplier(earlyCastFinder);
+ earlyCastApplier.walkFunctionInModule(func, getModule());
+
+ // Adding more casts causes types to be refined, that should be
+ // propagated.
+ ReFinalize().walkFunctionInModule(func, getModule());
+ }
+
+ // Find the best casts that we want to use.
BestCastFinder finder;
finder.options = getPassOptions();
finder.walkFunctionInModule(func, getModule());
- if (finder.lessCastedGets.empty()) {
- // Nothing to do.
- return;
- }
+ if (!finder.lessCastedGets.empty()) {
+ // Apply the requests: use the best casts.
+ FindingApplier applier(finder);
+ applier.walkFunctionInModule(func, getModule());
- // Apply the requests: use the best casts.
- FindingApplier applier(finder);
- applier.walkFunctionInModule(func, getModule());
-
- // LocalGet type changes must be propagated.
- ReFinalize().walkFunctionInModule(func, getModule());
+ // LocalGet type changes must be propagated.
+ ReFinalize().walkFunctionInModule(func, getModule());
+ }
}
};
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-06 14:32:38 +0000