Repository navigation
Conversation
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
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. |
Contributor
Author
|
Thanks for fixing this, and for the quick turnaround. |
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 (
rewrite_patterns!) time grows exponentially with the depth of diamond-shaped use chains. An integer add-with-carry chain is enough to trigger it:code_structured, maincode_structured, this PRWorklist 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 (
tfeeds both the next step andb, which also feeds the next step), so k doubles with each step.Fix
Each mark now carries the forwarding generation (one per
RBindrewrite) 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.cascadedentries are dropped on erase, likemodified.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_structuredoutput for the reproducer at D = 2, 4, …, 14 is byte-identical before and after (modulo source paths).codegenandanalysistest groups pass locally (741 pass, 1 broken; Julia 1.13.3, RTX 3060). Device tests were not run locally.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