soot-oss / SootUp

A new version of Soot with a completely overhauled architecture
https://soot-oss.github.io/SootUp/
GNU Lesser General Public License v2.1
546 stars 66 forks source link

add `ReversePostOrderBlockTraversal` and update `DominanceFinder` #928

Closed shenjunjiekoda closed 2 months ago

shenjunjiekoda commented 2 months ago

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 ForwardStmtGraph and BackwardStmtGraph via the getBlocksSorted interface. Additionally, the changes apply RPO in the DominanceFinder to enhance the accuracy and performance of dominator calculations.

Key changes include:

Thank you for reviewing this pull request and considering this update!

codecov[bot] commented 2 months ago

Codecov Report

Attention: Patch coverage is 84.21053% with 12 lines in your changes are missing coverage. Please review.

Project coverage is 70.11%. Comparing base (0ff4b1c) to head (26e2b35). Report is 11 commits behind head on develop.

:exclamation: Current head 26e2b35 differs from pull request most recent head c40e877. Consider uploading reports for the commit c40e877 to get more accurate results

Files Patch % Lines
...ava/sootup/core/graph/PostOrderBlockTraversal.java 81.57% 5 Missing and 2 partials :warning:
...tup/core/graph/ReversePostOrderBlockTraversal.java 80.00% 4 Missing and 1 partial :warning:
Additional details and impacted files ```diff @@ 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 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.