- Instruction i produces a result that may be used by instruction j, or
- Instruction j is data dependent on instruction k, and instruction k is data dependent on instruction i.
The second condition simply states that one instruction is dependent on another if there exists a chain of dependences of the first type between the two instructions. This dependence chain can be as long as the entire program.
Some of the data dependences are:
- Name Dependences
- Control Dependences
1. Name Dependences:
The name dependence occurs when two instructions use the same register or memory location, called a name.
There are two types of name dependences between an instruction i that precede instruction j in program order:
- An anti dependence between instruction i and instruction j occurs when instruction j writes a register or memory location that instruction i reads.
- An output dependence occurs when instruction i and instruction j write the same register or memory location.
2. Control Dependences:
A control dependence determines the ordering of an instruction, i, with respect to a branch instruction so that the instruction i is executed in correct program order.
Here C1 is control dependent on A1, and C2 control dependent on A2.