Calculate post dominator with non exiting control flow

Question

Using the basic algorithm to calculate post dominators I run into trouble when working with a CFG containing an infinite loop (i.e., not terminating).

The algorithm:

// post dominator of the start node is the start itself
 PDom(n0) = {n0}
 // for all other nodes, set all nodes as the post dominators
 for each n in N - {n0}
     Dom(n) = N;
 // iteratively eliminate nodes that are not post dominators
 while changes in any PDom(n)
     for each n in N - {n0}:
         PDom(n) = {n} union with intersection over PDom(p) for all p in post(n)

I have the following function:

function x: 
  while true:
     doNothing

Which has the following CFG graph:

                              -CFG->
[METHOD_START] -CFG-> [WHILE]        [DO_NOTHING]  [METHOD_END]
                              <-CFG-

When calculating the post dominator tree (starting from METHOD_END) this runs in the obvious problem, that there is no elimination of any nodes in PDom

The start and final PDom will be:

METHOD_RETURN : { METHOD_RETURN }
METHOD_START  : { METHOD_RETURN, DO_NOTHING, WHILE, METHOD_START }
WHILE         : { METHOD_RETURN, DO_NOTHING, WHILE, METHOD_START }
DO_NOTHING    : { METHOD_RETURN, DO_NOTHING, WHILE, METHOD_START }

This would imply, that WHILE is post dominated by METHOD_START which is obviously false.

How do I have to account for infinite loops in post dominator calculations?

Using the definition of (post) domination of "a node d (post) dominates a node n if every path from the start node to n must go through d" I would assume that the domination tree would have to be empty.

Answer 1

The problem is that I was trying to apply the domination algorithm on a forest, i.e., the method has multiple different graphs. However, the algorithm is only defined on a graph. Consequently, before applying the algorithm to the method graph I need to calculate the CFG slice from the start point. I..e, in the given example this would be only { METHOD_RETURN }.