Skip to content

Visit defs before users in the rewrite driver - #351

Merged
maleadt merged 2 commits into
mainfrom
tb/rewrite-cascade-depth
Nov 19, 2026
Merged

maleadt merged 2 commits into
mainfrom
tb/rewrite-cascade-depth

Conversation

@maleadt

@maleadt maleadt commented Nov 18, 2026 •

Copy link
Copy Markdown
Member

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:

steps = [:(t = UInt16.(a) .+ UInt16.(b) .+ (t .>> 0x0008); b = UInt8.(t)) for _ in 1:D]
@eval function chain(x, y, o)
    a = ct.load(x, 1, (16,))
    b = ct.load(y, 1, (16,))
    t = UInt16.(a)
    $(steps...)
    ct.store(o, 1, b)
    return
end

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:

  • cuTile Python's rewrite_patterns.py makes a single program-order pass with no revisits.
  • GCC's forwprop and Cranelift's aegraph visit defs before uses and never re-queue users.
  • MLIR's greedy driver and LLVM's InstCombine re-queue only direct users. MLIR adds an outer loop that re-runs over the whole IR; InstCombine runs once and verifies the fixpoint in tests.

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 subi rewrites in codegen/integration. The reproducer's structured IR (D = 1–12) is identical to main's.

D 16 20 192
main 2.7 s 50 s –
this PR 0.01 s 0.015 s 0.76 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 a one_use match rooted at that user can be missed. No current rule set can trigger it; the verifier would report it if one did.

Supersedes #350.

maleadt and others added 2 commits November 18, 2026 14:20
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
maleadt force-pushed the tb/rewrite-cascade-depth branch from 8190d68 to 98900c4 Compare November 18, 2026 13:26
@maleadt maleadt changed the title Bound the rewrite driver's operand-modified cascade by rule depth Visit defs before users in the rewrite driver Nov 18, 2026
@maleadt
maleadt merged commit 80905fc into main Nov 19, 2026
7 checks passed
@maleadt
maleadt deleted the tb/rewrite-cascade-depth branch November 19, 2026 10:18
@AntonOresten

Copy link
Copy Markdown
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

@maleadt

maleadt commented Nov 19, 2026

Copy link
Copy Markdown
Member Author

It's been a while since v1.0.0. Could we do a release soon? @maleadt

I plan on doing some cuTile.jl development in the next two weeks; OK if I release after that?

@AntonOresten

Copy link
Copy Markdown
Collaborator

Yeah that's alright.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants