[Solved]: Algorithm to find Dominance Frontiers

Problem Detail: 

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?

Asked By : gon1332

Answered By : Wandering Logic

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24112