(optimization): Using equality analysis to improve match optimization#9893
(optimization): Using equality analysis to improve match optimization#9893eytan-starkware wants to merge 1 commit intomainstarkware-libs/cairo:mainfrom eytan_graphite/_optimization_using_equality_analysis_to_improve_match_optimizationstarkware-libs/cairo:eytan_graphite/_optimization_using_equality_analysis_to_improve_match_optimizationCopy head branch name to clipboard
Conversation
|
This change is |
PR SummaryMedium Risk Overview Refactors def-site analysis to return Threads Reviewed by Cursor Bugbot for commit 35a7393. Bugbot is set up for automated code reviews on this repo. Configure here. |
eec8a84 to
87fb9bb
Compare
0e6d92d to
221e270
Compare
There was a problem hiding this comment.
Cursor Bugbot has reviewed your changes and found 1 potential issue.
❌ Bugbot Autofix is OFF. To automatically fix reported issues with cloud agents, have a team admin enable autofix in the Cursor dashboard.
Reviewed by Cursor Bugbot for commit 87fb9bb. Configure here.
| self.fixes.push(fix_info); | ||
| return info; | ||
| } | ||
| } |
There was a problem hiding this comment.
Equality fold corrupts candidate on unreachable failure path
Medium Severity
Inside try_get_fix_info, std::mem::take empties candidate.arm_demands[arm_idx] before the only return None check. If try_get_fix_info returns None, the equality-fold call site falls through to Some(candidate) without discarding the corrupted candidate. This differs from the construct-anchored call site which sets info.candidate = None on failure. Currently the None path is unreachable from the equality fold (because additional_remappings is always empty), but the asymmetry is fragile — adding any new early-return to try_get_fix_info would silently corrupt the candidate's arm demand, causing incorrect demand propagation for downstream construct-anchored folds targeting the same arm.
Additional Locations (1)
Reviewed by Cursor Bugbot for commit 87fb9bb. Configure here.
87fb9bb to
5f6644d
Compare
|
define a struct Code quote: (usize, usize) |
|
Suggestion: self.equalities[block_id.0].as_mut()?.get_enum_construct(var) |
|
how can candidate.match_variable be an enum that was constructed by payload_var, without payload_var being visable at the end of the block? Code quote: self.get_enum_variant(block_id, candidate.match_variable)
&& self.is_visible_at_block_end(payload_var, block_id) |
5f6644d to
35a7393
Compare
Summary
Extends the match optimizer to fold matches whose variant is already known via equality analysis, not just when a local
EnumConstructstatement is present in the same block. When equality analysis can determine the variant of a matched variable at a block's exit, the match is replaced with a direct goto to the corresponding arm, provided the matched value is droppable and the payload variable is copyable and in scope.To support this:
DefSitesnow storesOption<DefLocation>instead ofDefLocation, replacing theUNRESOLVEDsentinel withNonefor variables in unreachable blocks. The assertion that all slots are resolved is removed.EqualityStategains a mutableget_enum_constructmethod that performs path compression viafind.MatchOptimizerContextnow holds equality analysis results, dominator information, and def-site information, and exposesget_enum_variantandis_visible_at_block_endhelpers.try_get_fix_infois generalized to accept a variant, an innerVarUsage, an optional(stmt_idx, output_var)for construct removal, and afix_block, decoupling it from theStatementEnumConstructtype.FixInforeplacesstatement_location+remove_enum_construct+n_same_block_statementwithfix_blockandenum_construct_removal: Option<(usize, usize)>, which isNonefor equality-anchored folds.optimize_matchesnow takes adbparameter, threaded through fromOptimizationPhase.Type of change
Please check one:
Why is this change needed?
The previous match optimizer only eliminated a match when the matched enum value was constructed by a
StatementEnumConstructimmediately upstream. Cases where the variant was already known through equality analysis (e.g., after a prior match on the same variable) were not folded, leaving redundant multi-arm matches in the lowered IR.What was the behavior or documentation before?
A match on a variable whose variant was already known via equality analysis was left as-is, producing multiple blocks and redundant match arms in the lowered output.
What is the behavior or documentation after?
When equality analysis knows the variant of a matched variable at a block's exit and the payload is visible and copyable, the match is folded into a direct goto to the correct arm at that point, collapsing the redundant blocks. Test data reflects the reduced block count in the optimized output.
Related issue or discussion (if any)
None.
Additional context
The regression test
unresolved_assert_firesis removed because theUNRESOLVEDsentinel and its associated assertion no longer exist; unreachable-block variables are now represented asNoneinDefSites.