We may need RPO traversal utility for BasicBlocks
In the DominanceFinder in soot.core.graph,
// we're locked into providing a List<BasicBlock<?>>, not a List<? extends BasicBlock<?>>, so
// we'll use the block iterator directly (which provides this type) rather than
// #getBlocksSorted.
blocks =
StreamSupport.stream(
Spliterators.spliteratorUnknownSize(
blockGraph.getBlockIterator(), Spliterator.ORDERED),
false)
.collect(Collectors.toList());
I find that the sorted for Blocks ued by dominator calculation might not be reverse post order (may be the pseudo topological order now ), which may cause incorrectness.
The author of this implementation mentioned that he used the algorithm proposed in this paper
https://web.cse.ohio-state.edu/~rountev.1/788/papers/cooper-spe01.pdf
* @see <a
* href="https://www.researchgate.net/publication/2569680_A_Simple_Fast_Dominance_Algorithm">
* https://www.researchgate.net/publication/2569680_A_Simple_Fast_Dominance_Algorithm </a>
I found that the following algorithm, which use Reverse post order blocks traversal and use post order of 2 blocks to decide the result intersect.
Shall we add a implementation for RPO and PO which may used for dom and post dom calculation?
Dear maintainer, hello! If you feel the issue does indeed exist, I'd like to try contributing code to fix it later.
We may need RPO traversal utility for BasicBlocks
In the
DominanceFinderinsoot.core.graph,I find that the sorted for Blocks ued by dominator calculation might not be reverse post order (may be the pseudo topological order now ), which may cause incorrectness.
The author of this implementation mentioned that he used the algorithm proposed in this paper
https://web.cse.ohio-state.edu/~rountev.1/788/papers/cooper-spe01.pdf
I found that the following algorithm, which use
Reverse post orderblocks traversal and use post order of 2 blocks to decide the resultintersect.Shall we add a implementation for RPO and PO which may used for dom and post dom calculation?
Dear maintainer, hello! If you feel the issue does indeed exist, I'd like to try contributing code to fix it later.