Skip to content

lack RPO basicBlocks traversal may cause undeciable problem for dominator algorithm implementation #923

@shenjunjiekoda

Description

@shenjunjiekoda

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.

dom_algo

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions