Skip to content

Avoid exponential re-cascading of modified marks in the rewrite driver - #350

Closed
fuyutarow wants to merge 1 commit into
JuliaGPU:mainfrom
fuyutarow:fix-rewrite-cascade-exponential
Closed

fuyutarow wants to merge 1 commit into
JuliaGPU:mainfrom
fuyutarow:fix-rewrite-cascade-exponential

Conversation

@fuyutarow

Copy link
Copy Markdown
Contributor

Normalization (rewrite_patterns!) time grows exponentially with the depth of diamond-shaped use chains. An integer add-with-carry chain is enough to trigger it:

steps = [:(t = UInt16.(a) .+ UInt16.(b) .+ (t .>> 0x0008); b = UInt8.(t)) for _ in 1:D]
@eval function chain(x, y, o, tile::Int)
    a = ct.load(x; index = 1, shape = (tile,))
    b = ct.load(y; index = 1, shape = (tile,))
    t = UInt16.(a)
    $(steps...)
    ct.store(o; index = 1, tile = b)
    return
end
D 12 14 16 18
code_structured, main 0.58 s 2.06 s 7.99 s 34.6 s
code_structured, this PR 0.08 s 0.05 s 0.05 s 0.08 s

Worklist pops on main were 921 / 16,221 / 261,921 / 4,194,021 for D = 4 / 8 / 12 / 16 (≈ 2^D), while the statement count grows linearly.

Cause

The operand-modified cascade at the end of the driver loop deletes a node's mark when the node is popped, then marks its users. A node reachable from a forwarded value along k use paths is therefore re-marked, re-pushed and re-cascaded k times; the worklist's dedup only helps while the node is still queued. In a carry chain each step is a diamond (t feeds both the next step and b, which also feeds the next step), so k doubles with each step.

Fix

Each mark now carries the forwarding generation (one per RBind rewrite) that caused it. A node cascades only when its mark is newer than the generation that was current at its previous cascade. A stale mark stands only for IR changes that had already been applied when that earlier cascade ran, so cascading again cannot enable any match; marks from later forwardings still propagate as before. cascaded entries are dropped on erase, like modified.

An alternative would be to drop the transitive cascade in favour of revisiting only direct users; I kept the existing semantics since that is a design decision for you — happy to change course.

Testing

  • code_structured output for the reproducer at D = 2, 4, …, 14 is byte-identical before and after (modulo source paths).
  • codegen and analysis test groups pass locally (741 pass, 1 broken; Julia 1.13.3, RTX 3060). Device tests were not run locally.
  • Added test/codegen/rewrite.jl: a D = 24 carry chain must structure in under 30 s (2.4 s with this PR; on main this extrapolates to about an hour).

🤖 Generated with Claude Code

https://claude.ai/code/session_01FNMZB2CZGaeHy5tN9wEtFB

The operand-modified cascade in `rewrite_patterns!` cleared a node's mark
when it was popped, so a node reachable along k use paths from a forwarded
value was re-marked and re-cascaded k times. In diamond-shaped use graphs
(e.g. integer add-with-carry chains, where every carry feeds both the next
step and the low byte) k is exponential in depth, and normalization time
grew ~4x every two steps (D=18: 35 s).

Tag each mark with the forwarding generation (one per RBind rewrite) that
caused it, and let a node cascade only when its mark is newer than the
generation current at its last cascade. A stale mark stands only for IR
changes that already happened before that cascade, so skipping it cannot
miss a match. On the reproducer, D=18 now takes 0.08 s.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01FNMZB2CZGaeHy5tN9wEtFB
@maleadt

maleadt commented Nov 18, 2026

Copy link
Copy Markdown
Member

Thanks for tracking this down. With the generation marks, though, every new forwarding still cascades through the whole chain above it, so normalization stays quadratic (about 900k worklist pops at D = 192). The cascade was only needed because the driver visited users before their operands' defs; #351 visits defs first, as cuTile Python, GCC and Cranelift do, and drops the cascade entirely, with a fixpoint check in the test suite to catch missed rewrites. Closing in favor of that PR.

@maleadt maleadt closed this Nov 18, 2026
@fuyutarow

Copy link
Copy Markdown
Contributor Author

Thanks for fixing this, and for the quick turnaround.

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