Data dependencies
True data dependency (RAW - Read After Write)
Such a dependecy exists when the output of
one instruction is required as an input of one of the
next instructions:
Instr1: MUL r4, r3, r1 -- r4 = r3 * r1
...
Instrn: ADD r2, r4, r5 -- r2 = r4 + r5, [(Instr_1, RAW),...]
Output dependency (WAW - Write After Write)
This kind of dependency appears when two instructions
are using the same location as an output, they both
write in the same register/memory address:
Instr1: MOVE r3, r7 -- r3 = r7
...
Instrn: ADD r3, r4, r5 -- r3 = r4 + r5, [(Instr_1, WAW),...]
Anti-dependency (WAR - Write After Read)
This type of dependency exists when an instruction
uses the value from a memory location or from a register
as an input operand, while one of the subsequent
instructions writes in that location/register:
Instr1: ADD r1, r3, r7 -- r1 = r3 + r7
...
Instrn: ADD r3, r4, r5 -- r3 = r4 + r5, [(Instr_1, WAR),...]
Elimination of artificial dependencies
The output dependency and the antidependecy are not real dependencies,
they are called artificial and can be eliminated by using additional registers.
For example, the previous WAW dependency can be eliminated by storing the result of
the ADD in another register and making sure that from that point further
the new register will be used instead of r3:
Instr1: MOVE r3, r7 -- r3 = r7
...
Instrn: ADD r8, r4, r5 -- r8 = r4 + r5, no dependency
Instrn+1: MOVE r1, r8 -- here, r8 is used instead of r3