Preliminaries
an immediate dominator to the node it dominates. Thus, among
other relations, we have idom(1, 2) and idom(4, end). Similarly,
from the postdominator tree, we obtain ipdom(4, 2) and ipdom
(End,4).
Given a dominator and a postdominator tree, it is easy to derive
the set of dominators and postdominators for any node. For exam-
ple, the set of dominators for node 4, denoted as dom(4), is {2, 1,
Start}. dom(4) is derived by first obtaining the immediate dom-
inator of 4 which is 2, followed by the immediate dominator of 2
which is 1, and finally the immediate dominator of 1 which is Start.
Similarly, we can derive the set of postdominators for node 2 as
{4, End}.
1.16 PROGRAM-DEPENDENCE GRAPH
A PDG for program P exhibits different kinds of dependencies ...