Dependence

Define:

• IN(S): set of memory loc$^{\rm n}$s which might be read by some exec$^{\rm n}$ of statement S
• OUT(S): set of memory loc$^{\rm n}$s which might be written by some exec$^{\rm n}$ of statement S

Reordering is constrained by dependences; There are four types:

• Data (``true'') dependence: $S_1 ~\delta_{}~ S_2$

  $OUT(S_1) \cap IN(S_2)$

• Anti dependence: $S_1 ~\overline{\delta}_{}~ S_2$

  $IN(S_1) \cap OUT(S_2)$

• Output dependence: $S_1 ~\delta^o_{}~ S_2$

  $OUT(S_1) \cap OUT(S_2)$

• Control dependence: $S_1 ~\delta^c_{}~ S_2$

These are static analogues of dynamic RAW, WAR, WAW and control hazards.