add ReversePostOrderBlockTraversal and update DominanceFinder#928
Merged
swissiety merged 5 commits intosoot-oss:developfrom Apr 23, 2024
Merged
add ReversePostOrderBlockTraversal and update DominanceFinder#928swissiety merged 5 commits intosoot-oss:developfrom
ReversePostOrderBlockTraversal and update DominanceFinder#928swissiety merged 5 commits intosoot-oss:developfrom
Conversation
Codecov ReportAttention: Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## develop #928 +/- ##
=============================================
+ Coverage 70.04% 70.11% +0.06%
- Complexity 4069 4085 +16
=============================================
Files 312 315 +3
Lines 15303 15389 +86
Branches 2618 2626 +8
=============================================
+ Hits 10719 10790 +71
- Misses 3727 3738 +11
- Partials 857 861 +4 ☔ View full report in Codecov by Sentry. |
swissiety
approved these changes
Apr 22, 2024
sootup.core/src/main/java/sootup/core/graph/DominanceFinder.java
Outdated
Show resolved
Hide resolved
swissiety
approved these changes
Apr 23, 2024
Collaborator
swissiety
left a comment
swissiety
left a comment
There was a problem hiding this comment.
👍 thanks for your contribution!
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.
Summary
Implement RPO Traversal to Enhance CFG Analysis in Soot
Details
This PR addresses the specific issue raised in the Issue #923 concerning the potential problems due to the lack of Reverse Post-Order (RPO) traversal in the dominance analysis.
The proposed changes introduce an RPO traversal algorithm, which is integrated into the existing
ForwardStmtGraphandBackwardStmtGraphvia thegetBlocksSortedinterface. Additionally, the changes apply RPO in theDominanceFinderto enhance the accuracy and performance of dominator calculations.Key changes include:
sootup/core/graph/ReversePostOrderBlockTraversal.javaand create RPO one as a wrapper of PO.ForwardStmtGraphandBackwardStmtGraph.DominanceFinderto ensure the correctness of dominator tree generation.DominanceFinder(the head node should not have an immediate dominator). This was addressed by removing the@Nonnullannotation fromgetImmediateDominatorand allowing a return value of null when the input is the head node.DominatorFinder,PostDominatorFinder,PostOrderBlockTraversal,ReversePostOrderBlockTraversalto verify the fixes.Thank you for reviewing this pull request and considering this update!