Rangeanalysis: Fix a bad join-order in boundedPhiRankStep. - #20579
Conversation
Sorry, something went wrong.
There was a problem hiding this comment.
Pull Request Overview
This PR optimizes the join order in the boundedPhiRankStep predicate by refactoring how phi input edges are referenced in range analysis. The key change is replacing the conceptual forall quantification over (inp, edge) pairs with direct rank-based indexing to improve query performance.
Key changes:
- Refactored predicate signatures to use rank indices (rix) instead of (inp, edge) pairs
- Moved the translation from (inp, edge) to rank index earlier in the analysis pipeline
- Updated related predicates to work with the new rank-based approach
Sorry, something went wrong.
There was a problem hiding this comment.
Thanks for providing this alternative fix. I like this one much better (and it shows the same speedup on the affected DCA projects for C/C++) ❤️ LGTM!
The Coding Standards failures are unrelated, and they should be fixed by merging in main. I'll just merge this now 🤠
Sorry, something went wrong.
The predicate boundedPhiRankStep has a non-linear recursion with a sub-optimal join. The key thing to notice is that a bunch of predicates use the pair Sem::SsaVariable inp, SsaReadPositionPhiInputEdge edge to reference phi input along an edge, which is eventually conceptually quantified in a forall. However, this conceptual forall is implemented with the usual ranking trick, so we really just need the rank of the edge input. The translation from (inp, edge) to the rank index is the source of the poor join, so we can simply push this in through all the predicates that need to reference the edge input.
This is an alternative fix to #20576.