Difference between data dependence and control dependence

Question

I'm struggling to understand the difference between data dependence and control dependence .

So what I saw as an example was :

data dependence e.g., instruction uses data created by another instruction

control dependence e.g., instruction waits to updated reg for comparison

What's hard for me to understand is that for example in beq I wait for the register to be updated but I also depend on his data.

So I don't know how to know the difference between them.

Adenoid

Answer 1

instruction waits to updated reg for comparison is a wrong description of control dependencies, no wonder

Conditional branch instructions themselves have a data dependency on their input register(s) before the branch condition can be checked.

Instructions after the branch have a control dependency on the branch. The front-end needs to know which instructions to fetch/decode, based on whether the branch was taken or not. (Or for indirect branches, what the target address was).

Branch prediction makes a guess that might later be discovered to be wrong. (When the branch instruction actually executes and checks the prediction).

In simple (scalar) in-order pipelines, there's no way for dependent instructions to reach the exec stage before the branch instruction does. Discovering and recovering from a branch mispredict just means re-steering the front-end to fetch from the correct address, discarding the instructions from the wrong path that had been fetched (and decoded).

But in out-of-order exec CPUs that can happen. Especially if the branch's inputs were part of a long dependency chain, but the instructions with a control dependency on it don't have data dependencies. (i.e. they're independent work that the out-of-order back-end can get started on speculatively.)

Branch prediction + speculative execution effectively hide control dependencies when the prediction is correct. That's why compilers will often transform if (a==0) return a; into if (a==0) return 0; and similar; if they're going to branch anyway (control dependency), break / avoid the data dependency for the code using the return value.

Related:

• What exactly happens when a skylake CPU mispredicts a branch? - a modern OoO exec CPU.

• Avoid stalling pipeline by calculating conditional early - Minimizing the length of the data dependency chain for the branch itself, so it can execute early and verify the branch prediction.

• Dependency chain analysis mentions the control dependency of the loop branch.

• CPU prediction and memory barrier - speculative execution past branches can introduce memory reordering.

• Why is a conditional move not vulnerable for Branch Prediction Failure? - CMOV is purely an ALU select operation, just a data dependency, not a control dependency.

  • gcc optimization flag -O3 makes code slower than -O2 shows how CMOV can be slower, creating a loop-carried data dependency chain instead of a control dependency that speculative execution can hide.

Brenneman