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
We may need RPO traversal utility for BasicBlocks In the
DominanceFinder
insoot.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 order
blocks 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.