Fix two issues with DominanceFinder#744
Merged
kadirayk merged 4 commits intosoot-oss:developfrom Nov 8, 2023
Liam-DeVoe:fix-dom-finder
Merged
Fix two issues with DominanceFinder#744kadirayk merged 4 commits intosoot-oss:developfrom Liam-DeVoe:fix-dom-finder
kadirayk merged 4 commits intosoot-oss:developfrom
Liam-DeVoe:fix-dom-finder
Conversation
Liam-DeVoe
commented
Nov 7, 2023
Codecov ReportAll modified and coverable lines are covered by tests ✅
Additional details and impacted files@@ Coverage Diff @@
## develop #744 +/- ##
=============================================
+ Coverage 63.97% 64.42% +0.44%
- Complexity 3424 3447 +23
=============================================
Files 317 317
Lines 15408 15408
Branches 2612 2611 -1
=============================================
+ Hits 9858 9926 +68
+ Misses 4640 4567 -73
- Partials 910 915 +5
☔ View full report in Codecov by Sentry. |
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
2 participants
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.
First off: apologies for bundling two fixes with this PR. I would have submitted them separately, but the test I added runs into both issues, and so would fail on any PR which included only a fix for one. I've done the next best thing and split the fixes into commits (c07888e and b505857). However, I'm happy to split these into PRs on request.
c07888e: use .equals to compare to starting stmt
This closes #586 by using
.equalsfor comparison instead of==.b505857: use correct reverse postorder iteration for dominance finder
While investigating #586, I found that
DominanceFinderwas not computing the correct dominators for the test I added. I think the reasons for this are two-fold:DominanceFinder#getIdxToBlockandDominanceFinder#getBlockToIdxare not inverses (git checkout c07888eeaand runningtestBlockToIdxInverseconfirms this). This causes dominance indexes to become mixed up internally and the wrong dominator to be returned.blockGraph.getBlocks()to compute immediate dominators is correct. The algorithm referenced requires that blocks are iterated over in reverse postorder.blockGraph.getBlocks()'s xmldoc indicates that its ordering is not only not reverse postorder, but is not necessarily in any deterministic order.I've chosen to iterate over
blockGraph.getBlockIterator()instead, which fixes the first issue by usingblockGraph.getBlockIterator()as the ordered source of truth for nodes (and building the backwardsblockToIdxmap straight from it). This also fixes the second issue, asblockGraph.getBlockIterator()seems to provide the nodes in reverse postorder, as required. However, I'm not sure if this is an invariant I can rely on - let me know if it's not.I also fixed a dead pdf link along the way.