Control Dependence Graph and Data Dependence Graph

A Control Dependence Graph (CDG) and a Data Dependence Graph (DDG) are essential tools in computer science, particularly in compiler design and program analysis. They represent the dependencies between different parts of a program’s code, but they focus on two distinct types of relationships.

Control Dependence Graph (CDG)

A Control Dependence Graph illustrates how the execution of a statement is controlled by a conditional branching statement. In simpler terms, a statement is control-dependent on a conditional if the outcome of that conditional determines whether the statement will be executed.

• Nodes in a CDG represent the statements in a program.
• Edges represent the control dependencies. An edge from node A to node B means that the execution of statement B depends on the outcome of the conditional statement A.

Consider the following code snippet:

if (x > y) {
  z = x;
} else {
  z = y;
}
printf("%d", z);

In the Control Dependence Graph for this code:

• The statements z = x; and z = y; are both control-dependent on the if (x > y) condition. This is because the if statement’s evaluation to true or false directly dictates which of these two assignment statements will run.
• The printf("%d", z); statement is not control-dependent on the if statement because it will execute regardless of the condition’s outcome.

A CDG essentially maps out the “decision-making” structure of a program.

---

Data Dependence Graph (DDG)

A Data Dependence Graph shows how data flows between statements. It identifies situations where two statements access or modify the same memory location, creating a dependency.

• Nodes in a DDG represent the statements.
• Edges represent the data dependencies, indicating that the order of execution between the connected statements matters for the program’s correctness.

There are three primary types of data dependencies:

1、Flow (True) Dependence (RAW – Read After Write): A statement S2 is flow-dependent on S1 if S1 writes to a variable that S2 later reads. The value produced by S1 is consumed by S2.

x = 10;  // S1
y = x;   // S2

Here, S2 is flow-dependent on S1 because it reads the value of x written by S1.

2、Anti-Dependence (WAR – Write After Read): A statement S2 is anti-dependent on S1 if S1 reads a variable that S2 later writes to. Reordering these could cause S1 to read the wrong value.

y = x;   // S1
x = 20;  // S2

Here, S2 is anti-dependent on S1. If they were swapped, S1 would incorrectly use the value 20 for x.

3、Output Dependence (WAW – Write After Write): A statement S2 is output-dependent on S1 if both statements write to the same variable. Their relative order must be preserved.

x = 10;  // S1
x = 20;  // S2

Here, S2 is output-dependent on S1. Swapping them would change the final value of x.

A DDG is crucial for understanding how data is produced and consumed throughout a program.

---

Key Differences Summarized

Feature	Control Dependence Graph (CDG)	Data Dependence Graph (DDG)
Focus	Represents the control flow and decision-making structure.	Represents the flow of data and dependencies on shared memory locations.
Dependency	Based on conditional branches (e.g., if, while).	Based on access to the same variable (read/write operations).
Question Answered	“Does the outcome of a conditional statement determine if this statement executes?”	“Does this statement use, overwrite, or depend on data from another statement?”
Primary Use	Program slicing, software testing, and understanding program structure.	Instruction scheduling, parallelization, and compiler optimizations.