/*
* Copyright 2026 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.
*/
//
// Use mathematical constraint solving to optimize. For example:
//
// if (x == 10) {
// assert(x != 0); // redundant and can be removed.
// }
//
// For loops, we must avoid the following problem:
//
// x = 0
// do {
// print(x >= 0 & x < 100)
// x++
// } while (x < 100)
//
// Say that we flow information around precisely. Then initially x is 0 at the
// top of the loop, and x++ turns it into 1. 1 < 100 so we return to the top of
// the loop, and now x can be 0 or 1. We will then interpret this loop for 100
// iterations at compile time, going from [0] to [0, 1] to [0, 2] and so forth,
// which is obviously not a good idea.
//
// Instead, we do something similar to "widening" in abstract interpretation
// (which at a loop header, where a merge occurs, widens the range of values
// based on the bounds check that it sees elsewhere). We do something even
// simpler here, which can be accomplished in an eager way as follows:
//
// * x++ turns x from 0 to 1 in the example above, in the first iteration of
// the loop.
// * When we then see x == 1 that branches with x < 100, we turn that into
// x >= 1 && x < 100. This is "imprecise", because perhaps the local will
// not actually get incremented all the way to 100, but it is an upper
// bound that ends up getting us to the result we want in common loop
// shapes. (And it is safe to do because we allow more values for x, meaning
// we can prove fewer things, so we won't prove anything false.)
// * After doing that, we return to the top of the loop, where now we can see
// x >= 0 && x < 100. After running that through the loop a second time, no
// more happen: we successfully "jumped ahead" to the end state of the
// loop variable.
//
// Doing this eagerly when we see a branch, rather than identifying specific
// loop headers and analyzing their bounds more precisely, is good enough for
// us: the only imprecision we add is "x == C, branch with x < D => x >= C &&
// x < D". While imprecise, if we see "x == C, branch with x < D", then this is
// a situation inside a loop: if it were not, then x would get constant-
// propagatated to the branch anyhow by other passes. And, if this is in a loop,
// then this widening is exactly what we want. This eager approach avoids us
// needing to analyze loops shapes specifically and/or to consider branch
// conditions "from afar" (seeing a branch on "x < D", but *not* applying it
// eagerly, and instead using it later at the loop header or in some whole-
// function analysis).
//
#include <algorithm>
#include "cfg/cfg-traversal.h"
#include "cfg/wto.h"
#include "ir/constraint.h"
#include "ir/drop.h"
#include "ir/literal-utils.h"
#include "ir/local-graph.h"
#include "ir/properties.h"
#include "ir/utils.h"
#include "pass.h"
#include "support/unique_deferring_queue.h"
#include "support/utilities.h"
#include "wasm-builder.h"
#include "wasm.h"
#define CONSTRAINT_DEBUG 0
#ifndef CONSTRAINT_DEBUG
#define CONSTRAINT_DEBUG 0
#endif
namespace wasm {
using namespace wasm::constraint;
namespace {
// Information in a basic block.
struct Info {
// For WTOWorklist
bool inQueue;
Index index;
// All relevant operations: local gets and sets and uses of them.
std::vector<Expression**> actions;
// The branching instruction at the end of the block (or nullptr if there is
// something like a return or an unreachable, which are terminators that don't
// interest us in this pass - we just look at ifs and brs).
Expression* brancher = nullptr;
// For each local index, we track the constraints we know about it. We only do
// so at the start of each block, which is enough for the analysis below.
BasicBlockConstraintMap startConstraints;
void dump(Function* func) {
std::cout << "Info{" << actions.size();
if (brancher) {
std::cout << ", " << *brancher;
}
std::cout << ", " << startConstraints << "}\n";
}
};
struct ConstraintAnalysis
: public WalkerPass<
CFGWalker<ConstraintAnalysis, Visitor<ConstraintAnalysis>, Info>> {
bool isFunctionParallel() override { return true; }
// Locals are not modified here.
bool requiresNonNullableLocalFixups() override { return false; }
std::unique_ptr<Pass> create() override {
return std::make_unique<ConstraintAnalysis>();
}
using Super = WalkerPass<
CFGWalker<ConstraintAnalysis, Visitor<ConstraintAnalysis>, Info>>;
// Branches outside of the function can be ignored, as we only look at local
// state in the function.
bool ignoreBranchesOutsideOfFunc = true;
// A relevant local is one that we care about optimizing.
std::vector<bool> relevantLocals;
bool fastMath;
bool isRelevantType(Type type) {
if (type == Type::v128) {
// TODO optimize SIMD where it makes sense, but for now we don't want to
// do things like propagate v128 constants, which are large.
return false;
}
// Floating-point math does not follow the basic rules of logic (for
// example, NaN < NaN and NaN >= NaN are both false, despite the law of the
// excluded middle). Constraints follow the rules of logic, so we cannot
// operate on floats unless we have fast-math enabled (which assures us we
// can ignore NaNs).
// TODO: when values are constant and non-NaN, we could optimize even
// without fast-math
return !type.isFloat() || fastMath;
}
void doWalkFunction(Function* func) {
fastMath = getPassOptions().fastMath;
// Mark the relevant locals.
relevantLocals.assign(func->getNumLocals(), false);
for (Index i = 0; i < func->getNumLocals(); ++i) {
relevantLocals[i] = isRelevantType(func->getLocalType(i));
}
Super::doWalkFunction(func);
}
// Store the actions we care about.
void addAction() {
if (currBasicBlock) {
auto* currp = getCurrentPointer();
currBasicBlock->contents.actions.push_back(currp);
}
}
void visitLocalGet(LocalGet* curr) {
if (isRelevantType(curr->type)) {
addAction();
}
}
void visitLocalSet(LocalSet* curr) {
if (isRelevantType(getFunction()->getLocalType(curr->index))) {
addAction();
}
}
void visitUnary(Unary* curr) { addAction(); }
void visitBinary(Binary* curr) { addAction(); }
void visitRefEq(RefEq* curr) { addAction(); }
void visitRefIsNull(RefIsNull* curr) { addAction(); }
static void doStartIfTrue(ConstraintAnalysis* self, Expression** currp) {
// We are right after the condition, so we are in the block before the If's
// branching. Mark the If as the brancher (unless in unreachable code).
if (self->currBasicBlock) {
self->currBasicBlock->contents.brancher = *currp;
}
Super::doStartIfTrue(self, currp);
}
static void doEndBranch(ConstraintAnalysis* self, Expression** currp) {
if (self->currBasicBlock) {
self->currBasicBlock->contents.brancher = *currp;
}
Super::doEndBranch(self, currp);
}
void visitFunction(Function* curr) {
if (!entry) {
// Body is unreachable, no entry block.
return;
}
flow();
optimize();
}
// Flow infos around until we have inferred all we can about the constraints
// in each location.
void flow() {
#if CONSTRAINT_DEBUG
dumpCFG("flow");
#endif
// Start from the entry as the only reachable block. That block has incoming
// values - defaults - for each var.
entry->contents.startConstraints.setReachable();
auto& entryConstraints = entry->contents.startConstraints;
auto* func = getFunction();
for (Index i = func->getVarIndexBase(); i < func->getNumLocals(); i++) {
if (!relevantLocals[i]) {
// No point to apply a constraint to an irrelevant local.
continue;
}
auto type = func->getLocalType(i);
// TODO: support tuples
if (type.size() == 1 && LiteralUtils::canMakeZero(type)) {
// We have a default value, so we can prove something.
auto value = Literal::makeZero(type);
entryConstraints.set(i, Constraint{Abstract::Eq, {value}});
}
// Note that we need no special handling for non-nullable locals. They
// cannot be used before being set, so it doesn't matter what we have in
// the map for them. We leave them as proving nothing (as if they were
// parameters in effect) as that is more efficient in the way the
// information is encoded (see constraint.h).
}
// Starting from the entry, keep going while we find something new.
WTOWorklist<ConstraintAnalysis> work(*this);
work.push(entry);
work.run([&](BasicBlock* block) {
// Start at the top of the block, then go through, applying things.
BasicBlockConstraintMap constraints = block->contents.startConstraints;
#if CONSTRAINT_DEBUG
std::cout << block << " start constraints: " << constraints << '\n';
#endif
for (auto** currp : block->contents.actions) {
if (constraints.unreachable) {
break;
}
applyToConstraints(*currp, constraints);
}
if (constraints.unreachable) {
// Nothing to send.
return;
}
#if CONSTRAINT_DEBUG
std::cout << block << " end constraints: " << constraints << '\n';
#endif
// We now know the values at the end of the block. Flow it onward, and
// where it causes changes, queue more work.
for (auto* out : block->out) {
auto& outStartConstraints = out->contents.startConstraints;
// Find the constraints sent to this specific successor, if there is a
// branch, and use them.
if (auto branch = getBranchConstraints(block, out);
filterRelevant(branch), !branch.empty()) {
auto sentConstraints = constraints;
applyBranchConstraints(branch, sentConstraints);
#if CONSTRAINT_DEBUG
std::cout << block << " sending branch to " << out
<< " with sent constraints: " << sentConstraints << '\n';
#endif
// If anything changed at the start of the target block, flow onwards.
if (outStartConstraints.approximateOr(sentConstraints)) {
#if CONSTRAINT_DEBUG
std::cout << "out's start after " << outStartConstraints << '\n';
std::cout << block << " branch-modified " << out
<< " to start with: " << outStartConstraints << '\n';
#endif
work.push(out);
}
} else {
// There are no specific branch constraints, so send the unmodified
// |constraints|, avoiding a copy.
if (outStartConstraints.approximateOr(constraints)) {
#if CONSTRAINT_DEBUG
std::cout << block << " modified " << out
<< " to start with: " << outStartConstraints << '\n';
#endif
work.push(out);
}
}
}
});
}
// If we change types, we must refinalize.
bool refinalize = false;
// After inferring all we can, apply it to optimize the code.
void optimize() {
// If we find local.gets that we can optimize, we queue those changes here.
// This order is useful for the following reason:
//
// (i32.eqz
// (local.get $x)
// )
//
// If we can infer that x is 42, and we do that first, then we end up with
// eqz of 42. That is something Precompute can handle, but not us - this
// pass only looks at constraints on locals. We do not lose any optimization
// power by leaving this to Precompute, but it is less efficient and may
// require more cycles; it is also less convenient for testing, as we must
// avoid inferrable local.gets in order to fully test constraint
// optimization.
//
// Instead, we queue local.get changes to happen later, after the eqz in the
// example above. That is, the eqz gets a chance to get optimized, and if it
// does, the queued local.get change ends up unnoticable (it changes a thing
// not in the IR; a slight waste of work, but less wasteful than waiting for
// Precompute).
//
// This queue of changes contains tuples of currp (the pointer to the
// local.get) and the value to replace it with.
std::vector<std::pair<Expression**, Expression*>> getOptimizations;
for (auto& block : basicBlocks) {
// Follow the general shape of flow(): we need to see what the state is
// at each intermediate point inside the block. (Flowing between blocks is
// of course not needed at this stage.)
auto& constraints = block->contents.startConstraints;
for (auto** currp : block->contents.actions) {
#if CONSTRAINT_DEBUG
std::cout << block << " trying to optimize " << **currp << '\n';
#endif
if (!constraints.unreachable) {
applyToConstraints(*currp, constraints);
if (auto* rep = optimizeLocalGet(currp, constraints)) {
getOptimizations.emplace_back(currp, rep);
} else {
optimizeConstraint(currp, constraints);
}
} else {
// This is unreachable code: just mark it so.
*currp = getDroppedChildrenAndAppend(
*currp,
*getModule(),
getPassOptions(),
Builder(*getModule()).makeUnreachable());
refinalize = true;
}
}
}
// Apply local.get optimizations after all that.
for (auto& [currp, rep] : getOptimizations) {
*currp = rep;
}
if (refinalize) {
ReFinalize().walkFunctionInModule(getFunction(), getModule());
}
}
// Given an expression and the constraints on it, see if it is a local.get
// that we can optimize, and return the value to optimize to, if so.
Expression* optimizeLocalGet(Expression** currp,
const BasicBlockConstraintMap& constraints) {
// A bare local.get can be optimized, if we know that local is a constant.
if (auto* get = (*currp)->dynCast<LocalGet>()) {
if (auto lit = constraints.get(get->index).getLiteral()) {
// Among references, only propagate nulls. Other things, like strings,
// may increase size, so we leave them for passes like Precompute and
// GUFA.
if (lit->type.isRef() && !lit->isNull()) {
return nullptr;
}
Builder builder(*getModule());
auto* rep = builder.makeConstantExpression(*lit);
// See if the type changes.
auto oldType = get->type;
if (!Type::isSubType(rep->type, oldType)) {
// The value we know must exist here is impossible, which means it was
// cast in a way that traps at runtime. This code is unreachable.
rep = builder.makeUnreachable();
refinalize = true;
} else if (rep->type != oldType) {
// We are refining.
refinalize = true;
}
return rep;
}
}
return nullptr;
}
// Given an expression and the constraints on it, parse it into a constraint
// if we can, and optimize it.
void optimizeConstraint(Expression** currp,
const BasicBlockConstraintMap& constraints) {
auto* curr = *currp;
// Note that we don't need to try to parse a series of constraints with
// ParsedAndedConstraints: if there is a tree of ANDed things, we will
// simply optimize it as we walk it, each time handling one.
auto parsed = LocalConstraint::parse(curr);
if (!parsed) {
return;
}
if (!relevantLocals[parsed->local]) {
return;
}
auto result = constraints.proves(*parsed);
if (result == Unknown) {
// If we parsed something using two locals, like x != y, we can also look
// for the flipped condition among y's constraints TODO
return;
}
// We know the result!
auto& wasm = *getModule();
auto value =
LiteralUtils::makeFromInt32(result == True ? 1 : 0, curr->type, wasm);
*currp = getDroppedChildrenAndAppend(
curr, wasm, getPassOptions(), value, DropMode::IgnoreParentEffects);
}
// Given a predecessor and one of its successors, find new constraints that
// can be added due to the flow to that specific successor.
ParsedAndedConstraints getBranchConstraints(BasicBlock* pred,
BasicBlock* succ) {
auto* brancher = pred->contents.brancher;
if (!brancher) {
return {};
}
// We handle the case of two successors for now. When there are less, other
// opts can handle things. TODO: Switch is the case of more than 2.
if (pred->out.size() != 2) {
return {};
}
// CFGWalker builds the IR by putting the physical successor as the first
// successor (that is, the first is the one we reach without branching).
// We pass that along to the specific branch type handlers, so they can
// figure out if we are in the true or false path.
assert(succ == pred->out[0] || succ == pred->out[1]);
auto physicalSuccessor = (succ == pred->out[0]);
if (auto* iff = brancher->dynCast<If>()) {
return getConstraintsFromIf(iff, physicalSuccessor);
} else if (auto* br = brancher->dynCast<Break>()) {
return getConstraintsFromBreak(br, physicalSuccessor);
} else if (auto* br = brancher->dynCast<BrOn>()) {
return getConstraintsFromBrOn(br, physicalSuccessor);
}
// TODO: Switch
return {};
}
ParsedAndedConstraints getConstraintsFromIf(If* iff, bool physicalSuccessor) {
auto parsed = ParsedAndedConstraints::parseCondition(iff->condition);
if (!physicalSuccessor) {
// We are in the ifFalse, so negate the condition.
parsed.negate();
}
return parsed;
}
ParsedAndedConstraints getConstraintsFromBreak(Break* br,
bool physicalSuccessor) {
// We get here when there is more than one successor, so there must be a
// condition.
assert(br->condition);
auto parsed = ParsedAndedConstraints::parseCondition(br->condition);
if (physicalSuccessor) {
// The branch was not taken, so negate the condition.
parsed.negate();
}
return parsed;
}
ParsedAndedConstraints getConstraintsFromBrOn(BrOn* brOn,
bool physicalSuccessor) {
// The constraint on that local depends on the op.
// TODO: Handle BrOnCast* etc using subtyping operations.
if (brOn->op != BrOnNull && brOn->op != BrOnNonNull) {
return {};
}
// parseCondition can parse more things than a local.get, which is all we
// handle here, but there is no other valid IR that can appear there, so we
// can reuse it.
auto parsed = ParsedAndedConstraints::parseCondition(brOn->ref);
// Negate depending on the op and (similar to Break) the successor.
if ((brOn->op == BrOnNull) ^ physicalSuccessor) {
parsed.negate();
}
return parsed;
}
// When applying constraints for a binary operation like x = y + 1, we may
// end up with lots of nonlinear work, in a loop: x may go from 0 to 1, then
// branch back to the top and merge, making it in the range [0, 1], then get
// incremented and loop again, leading to [0, 2] and so forth, only stopping
// when it reaches the loop bound, which may be very high. We don't want to
// spend significant time on such constant operations, as other passes will
// propagate them anyhow, so we stop before applying such x = y + 1
// operations a ridiculous number of times, by widening to a worst case.
static const Index MaxBinaryActions = 20;
// How many times we processed each Binary action.
std::unordered_map<Binary*, Index> binaryActionCounts;
// Given an expression, apply it to the constraints. For example, a local.set
// sets the value for that local.
void applyToConstraints(Expression* curr,
BasicBlockConstraintMap& constraints) {
if (auto* set = curr->dynCast<LocalSet>()) {
if (!relevantLocals[set->index]) {
// No point to apply a constraint to an irrelevant local.
return;
}
// Look at the fallthrough. It is valid to do so, because our constraints
// only track two things, constants and locals. For a constant, it does
// not change while falling through. For a local, the only way for the
// local to change while falling through is to go through a tee of that
// local - but that would keep the same value there anyhow. That is:
//
// (local.set $other
// (block
// ..
// (local.tee $source
// (block
// ..
// (local.get $source)
// )
// )
// )
// )
//
// The fallthrough here is the local.get of $source. We can set $other to
// the value in $source, because while $source did have a write while
// falling through, it did not alter the value, and there is no
// opportunity to write any other value while falling through. (And, any
// local.tee appearing here would have been reached earlier in the
// traversal, and handled.)
auto* value = set->value;
while (1) {
if (value->is<LocalSet>()) {
// We stop at the first tee: we don't need to look any further, and
// will just apply that local's values to ourselves, saving repeated
// work.
break;
}
auto* next = Properties::getImmediateFallthrough(
value, getPassOptions(), *getModule());
if (value == next) {
break;
} else {
value = next;
}
}
// Now that we know the value, check binary action counting limits (see
// above).
if (auto* binary = value->dynCast<Binary>()) {
// The code below will stop calculating this binary once we pass
// MaxBinaryActions operations on it. That is enough to prevent
// unbounded work on this binary, however, we may end up reaching this
// basic block an even larger number of times for other reasons, i.e.,
// just because of a very complex CFG. That should be very rare, but can
// happen. In debug builds we check we do not exceed a very high limit
// there, intending to throw an assert rather than just hang in the case
// of a bug (as assert is easier to diagnose, even if it happens after a
// long delay).
auto& count = binaryActionCounts[binary];
#ifndef NDEBUG
static const Index MaxBasicBlockActions = 1024 * 1024;
assert(count < MaxBasicBlockActions);
#endif
count++;
if (count >= MaxBinaryActions) {
constraints.setProvesNothing(set->index);
return;
}
}
constraints.set(set->index, value);
}
}
// Filters out constraints on irrelevant locals.
void filterRelevant(ParsedAndedConstraints& parsed) {
parsed.erase(std::remove_if(parsed.begin(),
parsed.end(),
[&](const LocalConstraint& pair) {
return !relevantLocals[pair.local];
}),
parsed.end());
}
// Apply branch constraints to the current set of constraints.
void applyBranchConstraints(const ParsedAndedConstraints& branch,
BasicBlockConstraintMap& constraints) {
for (auto& pair : branch) {
// Extend the range of values in the "jump ahead" manner described in the
// top-level comment.
if (!applyBranchRangeExtensionToConstraints(pair, constraints)) {
// Otherwise, apply the constraint normally.
constraints.approximateAnd(pair.local, pair.constraint);
}
if (constraints.unreachable) {
return;
}
}
}
bool
applyBranchRangeExtensionToConstraints(const LocalConstraint& branch,
BasicBlockConstraintMap& constraints) {
using namespace Abstract;
// "Jump ahead" and extend ranges. If the branch is x < M, and we were
// x == N, then extend to x >= N && x < M (see top-level comment). Note that
// we don't need to worry about a contradiction here: this code is only
// reached if x == N && x < M. If it is reached, that is not a
// contradiction, and extending x == N to x >= N is also not.
auto M = branch.constraint.term;
// We only handle the case of N being a constant, for two reasons:
//
// * As mentioned above, if a constant reaches a conditional branch, then
// other passes would have propagated it into the branch check itself,
// if that were possible. The only case where it isn't possible is when
// it is a loop variable (so it looks like a constant at first, but gets
// written another value by the branch back to the loop top). By only
// handling constants here, we only extend ranges for loop variables (and
// extending ranges can have downsides, so it is good we do it in a
// targeted way).
// * The case of a constant for the initial value N is exactly what we want
// to optimize here: most typical loop patterns iterate from 0 or 1 or
// such.
//
// So things work out perfectly here: constants are safe to optimize (no
// risk of extension causing downsides) and are exactly what we want to
// optimize.
//
// (Note that there is no limitation on *M*, the upper bound of the loop: we
// can iterate up to a constant or to a local. I.e. loops from 0 to 100 and
// 5 to x work, but not loops from x to 100 or x to y.)
auto N = constraints.get(branch.local).getLiteral();
if (!N) {
return false;
}
// We can handle both x < M as the branch, as described above, or
// x <= M (if N <= M).
if (branch.constraint.op == Abstract::LtS ||
branch.constraint.op == Abstract::LeS) {
constraints.set(branch.local, branch.constraint);
if (!constraints.unreachable) {
constraints.approximateAnd(branch.local, {GeS, {*N}});
}
return true;
}
if (branch.constraint.op == Abstract::LtU ||
branch.constraint.op == Abstract::LeU) {
constraints.set(branch.local, branch.constraint);
if (!constraints.unreachable) {
constraints.approximateAnd(branch.local, {GeU, {*N}});
}
return true;
}
return false;
}
};
} // anonymous namespace
Pass* createConstraintAnalysisPass() { return new ConstraintAnalysis(); }
} // namespace wasm