|
|
A Program Dependency Graph (we will call it PDG from now on ) of a program
is a graph that has nodes assigned to each statements of the program and
directed edges represented a dependence. The rule is defined that an edge from a
statement s1 to another statement s2 exists, whenever some dynamic instances,
v, of s1 shares a dependence with a later dynamic instance of s2[2]. Typically, a
PDG has two types of dependence edges: a data-dependence edge and a
control-dependence edge. A data-dependence edge from s1 to s2 means that the
computation performed in s2 depends on the value computed in s1. A
control-dependence edge from s1 to s2 implies that s2 may or may not
be executed depending on the boolean outcome of s1, for instance, a
if-statement.
Consider the bubble sort algorithm on an array n[ ], as of the Algorithm 2 shown
below:
|
On data dependent point of view, the value of i in the first for-statement (line 1) controls the boolean expression in the second for-statement (of line 2), and j controls the rest of the program from line 3-6. From the aspect of control dependency, the execution of line 4-6 depends on the boolean outcome of the if-statement in line 3. Therefore a PDG of previous program can be drawn as follow, where a solid line represents a data-dependence relation and a dotted line is the control-dependence relation.:
