The algorithm that is used by gcc and llvm is that of Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy (page 9). We start with the immediate dominators of each control-flow graph node B already calculated and stored in idom[B]:

for each B in all basic blocks
    if size of Predecessors(B) >= 2
        for each P in Predecessors(B)
            runner = P
            while runner != idom[B]    # idom is the immediate dominator
                DF(runner) += B
                runner = idom[runner]

My question is about the Predecessors set. Do they refer to the direct predecessors ("fathers") of B or to all of them that lead to B?


Predecessors(B) is just the set of direct predecessors of B. The "fathers", not the more distant ancestors.

Dominance frontier nodes must be join points in the graph, and a node can only be a join point if it has more than one predecessor.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.