ConstraintAnalysis: Add conditional propagation by kripken · Pull Request #8867 · WebAssembly/binaryen

kripken · 2026-06-25T17:26:53Z

When we see an if, br_if, etc., we can propagate the condition along the
true branch, and its negation along the other.

kripken · 2026-06-26T00:14:02Z

That one works, yeah, but it is not easy to prove that. It depends on how the conditions relate:

log(x)
if y:        ;; these two lines changed
  return     ;;
if x > 1:
  unreachable

Now nothing can be inferred for the x in log(x), not even that x <= 1.

tlively · 2026-06-26T00:48:39Z

The backward flow you need is similar to the forward flow. The initial state is bottom for each block ending in unreachable (or at which a contradiction is discovered during the forward flow) and top at the end of other exit blocks (if you are not interleaving it with the forward flow). Then you flow backward. Branch conditions are OR'd into the predecessor blocks instead of AND'd into successor blocks. If we follow the C/C++ model, some care needs to be taken around calls and atomic operations because they are allowed to happen in loops that may be followed by unreachables.

kripken · 2026-06-26T17:31:58Z

Yes, that sounds right. Though the ORing will in generally stop working after one branch, unless we get lucky...

tlively · 2026-06-26T20:20:12Z

+    // We pass the next function the index of the successor among the others.
+    assert(succ == pred->out[0] || succ == pred->out[1]);
+    auto succIndex = succ == pred->out[1] ? 1 : 0;


We wouldn't need to calculate the index like this if we just started with an indexed for loop instead of a range-based for loop over the successors when we process work list items.

Hmm, I suppose, but the code seems overall simpler to me as is? getBranchConstraints handles blocks, without caring about indexing; when we do start to care about indexing, we get the index in this trivial way.

The other advantage is that we would then be consistently using indices everywhere instead of using blocks in the signature of this function and then indices in the signatures of the getConstraintsFromXYZ functions. (Although this may be moot; see below.)

If we want to avoid succIndex, another option is "fallthrough" as in, are we falling through to the block right after us, or are we branching somewhere else. That is really the operation here. Though, I'm not sure if it's any better?

If-else does not really have a fallthrough, but it is the case that for the operations handled here, we just care about whether we need to negate the condition or not. (br_table will of course have to care about the specific index.

We could replace succIndex with a boolean of either of those names, if we wanted?

The property we care about is "is this the block I end up in when the condition expression was truthy," not about the relative positions of the blocks if we were to linearize the CFG. But I expect this to be moot if we make the change I suggest in #8867 (comment).

I implemented that comment, but I'm not sure if you think it is moot? getBranchConstraints is still doing more than just call the handlers, it also looks at succIndex.

The property we care about is "is this the block I end up in when the condition expression was truthy," not about the relative positions of the blocks if we were to linearize the CFG.

Yes, it is just that we compute "is this the ifTrue path" using the relative positions of blocks. We have to compute this somewhere, or stash it in the IR. Atm the IR construction rule is, as I said, that the physically adjacent block is the first successor.

I renamed it to physicalSuccessor now, which avoids succIndex, and I think makes it clear how we relate that physical successor to the ifTrue/false paths.

I don't love it, but I see where you're coming from and I don't think it's worth going back and forth more on this one, so lgtm.

tlively · 2026-06-26T20:25:36Z

-                           const BasicBlockConstraintMap& predEnd,
+  // Gets branch constraints using a successor index and a parsed constraint.
+  std::optional<LocalConstraint>
+  getConstraintsFromParsed(Index succIndex,


I don't think this function is adding much anymore. Let's inline it into its callers. (This will simplify getContraintsFromBreak in particular.)

The function body is 14 lines of code/comments - inlining it would lead to duplication?

It handles the case where nothing was parsed, and negating the condition based on succIndex.

Concrete demonstration of what I have in mind in #8867 (comment).

tlively · 2026-06-26T20:28:53Z

+        ;; We can infer 1 here.
+        (drop
+          (ref.is_null
+            (local.get $param)


If we have an x == null constraint, then instead of optimizing (ref.is_null (local.get x)) => (i32.const 1), we can optimize (local.get x) => (ref.null none).

Then follow-up optimization in other passes will be able to optimize much more than just a parent ref.is_null.

tlively · 2026-06-26T23:30:04Z

+    // We pass the next function the index of the successor among the others.
+    assert(succ == pred->out[0] || succ == pred->out[1]);
+    auto succIndex = succ == pred->out[1] ? 1 : 0;


The other advantage is that we would then be consistently using indices everywhere instead of using blocks in the signature of this function and then indices in the signatures of the getConstraintsFromXYZ functions. (Although this may be moot; see below.)

tlively · 2026-06-26T23:50:08Z

+      return getConstraintsFromBreak(br, succIndex);
+    } else if (auto* br = brancher->dynCast<BrOn>()) {
+      return getConstraintsFromBrOn(br, succIndex);
+    }


Example of how simple this could be without helper function overhead:

Suggested change

}

Expression* cond = nullptr;

bool negate = false;

if (auto* iff = brancher->dynCast<If>()) {

cond = iff->condition;

} else if (auto* br = brancher->dynCast<Break>()) {

cond = br->condition;

negate = true;

} else if (auto* br = brancher->dynCast<BrOn>();

br && (br->op == BrOnNull || br->op == BrOnNonNull)) {

cond = br->ref;

negate = br->op == BrOnNonNull;

} else {

return {};

}

if (auto parsed = LocalConstraint::parseBoolean(cond)) {

if (negate ^ (succIndex == 1)) {

parsed.constraint = parsed.constraint.negate();

}

return parsed;

}

return {};

We could make this even simpler by ~~removing negate~~ only setting negate for BrOnNull if we updated the CFG walker so that the ifTrue successors were consistently at index 0 for if, br_if, and br_on*.

Thanks, I see better what you mean now.

However,

BrOn doesn't use parseBoolean, it parses a LocalGet directly - the constraint depends on the BrOn opcode, unlike the others.

Once we add Switch support, we'll need to call out to other code anyhow - i.e. they won't all be boolean-style branches. At that point, I think it will be nicer as in the current code, to call "handle If", "handle BrOn", "handle Switch" and so forth, which is very high level.

BrOn doesn't use parseBoolean, it parses a LocalGet directly - the constraint depends on the BrOn opcode, unlike the others.

But it might as well use parseBoolean since that already handles the LocalGet. Then you can just negate the condition when you have br_on_null instead of br_on_non_null. No need to duplicate the LocalGet parsing logic.

2. Once we add Switch support, we'll need to call out to other code anyhow

No argument there, but there is still room to reduce repetition and boilerplate in the existing code, mostly be doing less constraint parsing in the BrOn case, but also potentially via tweaks like not taking std::optional in getContraintsFromParsed.

But it might as well use parseBoolean since that already handles the LocalGet

...yes, it does handle that, but logically these are different operations. Atm we can't write (br_on_null (ref.eq ..)), but parseBoolean would parse such a thing. This could lead to odd bugs later. I think it's better to be explicit: br_on only handles one constraint, and we can parse it directly.

not taking std::optional in getContraintsFromParsed.

I guess I can move it from there to the main user. See last commit. That simplifies the API slightly I think.

(br_on_null (ref.eq ...)) would of course be disallowed by validation, the same way (br_if (ref.null none)) would be. But the two cases are similar enough that we're happy using the same Literal::makeZero(type) method to create the "falsey" value for both of them. Both br_on_non_null and br_if branch on "truthy" values (and br_on_null just negates br_on_non_null), so I think it's very natural to use parseBoolean for both of them.

I'd be ok with that, but we should rename it then - BrOn's input is a reference, not an integer boolean, so parseBoolean is logically wrong. I don't have a good idea for a shared name, though... do you?

parseCondition (I discarded parseTruthyOrFalsey and parseBooleany)

Ok, switched to parseCondition.

tlively · 2026-06-29T21:20:19Z

+      return getConstraintsFromBreak(br, succIndex);
+    } else if (auto* br = brancher->dynCast<BrOn>()) {
+      return getConstraintsFromBrOn(br, succIndex);
+    }


(br_on_null (ref.eq ...)) would of course be disallowed by validation, the same way (br_if (ref.null none)) would be. But the two cases are similar enough that we're happy using the same Literal::makeZero(type) method to create the "falsey" value for both of them. Both br_on_non_null and br_if branch on "truthy" values (and br_on_null just negates br_on_non_null), so I think it's very natural to use parseBoolean for both of them.

tlively · 2026-06-29T21:22:16Z

+  getConstraintsFromParsed(LocalConstraint parsed, Index succIndex) {
+    auto& [local, constraint] = parsed;


I'm still not very happy with this helper. All it does is determine whether the constraint needs to be negated or not, but for the Break and BrOn callers, it does not even do this job fully. The logic for negation is different enough for the different branch instructions that I don't think it is useful to try to factor it out. See suggested replacements below.

Thanks, I removed getConstraintsFromParsed and inlined the negation into the callers. I agree this is simpler that way.

Co-authored-by: Thomas Lively <tlively123@gmail.com>

tlively

LGTM with possible final simplifications:

Renaming parseBoolean so we can reuse it for the BrOn case.
getBranchConstraints could do nothing but dispatch to the proper getConstraintsFromXXX handler if we used a traditional for loop instead of a range-based for loop to iterate over the successor blocks.

kripken added 30 commits June 3, 2026 16:08

go

413f4e8

go

817a9ca

go

c14b3b9

work

35329c8

go

1dfe44c

f

6e6d06e

go

c9f67d1

go

5f1fdc8

go

c339b79

go

d673317

go

c4321a9

go

260fb83

go

4fe70e3

go

c0d19d9

go

e6f2d34

go

200566c

go

83e845e

go

e16096b

go

494f67a

go

6e76ac0

go

cf2b0e4

form

2a02004

work

279dc39

work

6e8f576

work

fcd7e41

work

6537ace

work

61dd31e

work

783e6ff

go

3e0055e

go

c1e3dc8

kripken added 4 commits June 26, 2026 11:49

refactor to a clearly-defined BasicBlockConstraintMap&

525bbb7

format

34db73c

simplify branching APIs

d5b9de6

add suggested test

33835ec

tlively reviewed Jun 26, 2026

View reviewed changes

Comment thread src/ir/constraint.h

Comment thread src/passes/ConstraintAnalysis.cpp Outdated

Comment thread src/ir/constraint.cpp Outdated

Comment thread src/ir/constraint.cpp Outdated

Comment thread src/passes/ConstraintAnalysis.cpp

tlively reviewed Jun 26, 2026

View reviewed changes

kripken added 7 commits June 26, 2026 16:02

default to unreachable

cfdb684

simplify logic as suggested

7711526

simplify logic as suggested (proves nothing is impossible after and)

ee1e63a

comment

d547056

assert instead of else-assert

edb3197

reverse succIndex placing

09ec1d5

format

761073d

tlively reviewed Jun 26, 2026

View reviewed changes

kripken added 2 commits June 29, 2026 14:12

remove optional from getConstraintsFromParsed param

45602d9

format

c7b9d7a

tlively reviewed Jun 29, 2026

View reviewed changes

kripken and others added 2 commits June 29, 2026 14:32

Update src/passes/ConstraintAnalysis.cpp

b0af845

Co-authored-by: Thomas Lively <tlively123@gmail.com>

remove getConstraintsFromParsed as requested

9958fee

tlively approved these changes Jun 29, 2026

View reviewed changes

kripken added 5 commits June 29, 2026 15:30

parseCondition

69a02b9

format

acabc42

rename to physicalSuccessor

9868a32

format

11b25da

simplify

0626427

kripken merged commit 82b8645 into WebAssembly:main Jun 30, 2026
16 checks passed

kripken deleted the constraint.2 branch June 30, 2026 16:11

-    }
+    Expression* cond = nullptr;
+    bool negate = false;
+    if (auto* iff = brancher->dynCast<If>()) {
+      cond = iff->condition;
+    } else if (auto* br = brancher->dynCast<Break>()) {
+      cond = br->condition;
+      negate = true;
+    } else if (auto* br = brancher->dynCast<BrOn>();
+               br && (br->op == BrOnNull || br->op == BrOnNonNull)) {
+      cond = br->ref;
+      negate = br->op == BrOnNonNull;
+    } else {
+      return {};
+    }
+    if (auto parsed = LocalConstraint::parseBoolean(cond)) {
+      if (negate ^ (succIndex == 1)) {
+        parsed.constraint = parsed.constraint.negate();
+      }
+      return parsed;
+    }
+    return {};

		getConstraintsFromParsed(LocalConstraint parsed, Index succIndex) {
		auto& [local, constraint] = parsed;

Uh oh!

Conversation

kripken commented Jun 25, 2026

Uh oh!

kripken commented Jun 26, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tlively commented Jun 26, 2026

Uh oh!

kripken commented Jun 26, 2026

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tlively Jun 26, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

tlively left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

kripken commented Jun 26, 2026 •

edited

Loading

tlively Jun 26, 2026 •

edited

Loading