Repository navigation
Visit defs before users in the rewrite driver - #351
Merged
Merged
Conversation
The driver popped instructions from a LIFO worklist seeded in program order, so users were visited before the defs of their operands. When a forwarding rewrite later changed an operand, a pattern rooted at an already-visited user could only be found by revisiting it, so the driver cascaded such changes up the use chain, transitively and without limit. In diamond-shaped use graphs, such as add-with-carry chains, a node was revisited once per use path: a 20-step chain took 50 s to normalize. Seed the worklist in reverse so that the initial sweep visits defs first, like the reference implementation, GCC's forwprop and Cranelift. A rewrite then mostly changes instructions that are still queued, so drop the cascade and only re-queue the direct users of a changed instruction, as MLIR's greedy driver does. With the current rules this misses no rewrites across the test suite. Co-authored-by: fuyutarow <fuyutarow@gmail.com>
The driver only revisits the direct users of a changed instruction, and relies on visiting defs before users for everything else. Nothing caught a rewrite it missed: the IR was just left less optimized. When `verify_rewrites` is set, which the test suite does, run the rules a second time after the driver finishes and throw if any still fires, naming the rule and the instruction. This is the counterpart of InstCombine's fixpoint verification.
maleadt
force-pushed
the
tb/rewrite-cascade-depth
branch
from
November 18, 2026 13:26
8190d68 to
98900c4
Compare
Collaborator
|
I encountered this problem today, funnily enough, so thanks for fixing. It's been a while since v1.0.0. Could we do a release soon? @maleadt |
Member
Author
I plan on doing some cuTile.jl development in the next two weeks; OK if I release after that? |
Collaborator
|
Yeah that's alright. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Normalization time in
rewrite_patterns!grew exponentially with the depth of diamond-shaped use chains, as found by @fuyutarow in #350. An integer add-with-carry chain is enough:The driver's LIFO worklist was seeded in program order, so it visited users before the defs of their operands. When a forwarding rewrite then changed an operand, patterns rooted at already-visited users could only be found by revisiting them, so the driver cascaded the change up the use chain, transitively and without limit. A node reachable along k use paths was revisited k times, and every step of a carry chain doubles k: 20 steps took 50 s.
The first commit seeds the worklist in reverse, so the initial sweep visits defs before users, and drops the cascade: a change only re-queues the direct users of the changed instruction. That is how the other engines I looked at handle this:
rewrite_patterns.pymakes a single program-order pass with no revisits.The second commit adds that verification: with
cuTile.verify_rewrites[]set, which the test suite does,rewrite_patterns!runs the rules again after finishing and throws if any still fires.The full test suite, including examples, passes with verification on. With the old bottom-up order and no cascade, it reports two missed
subirewrites incodegen/integration. The reproducer's structured IR (D = 1–12) is identical to main's.At D = 192, other passes dominate (mostly
scalar_elim_pass!).Not addressed:
notify_erased!re-queues the def of an operand that lost a use, but not the def's remaining user, so aone_usematch rooted at that user can be missed. No current rule set can trigger it; the verifier would report it if one did.Supersedes #350.