Loop Dependence Analysis - Classification

Classification

A dependence between two operations: a and b, can be classified according to the following criteria:

• Operation type
  • If a is a write and b is a read, this is a flow dependence
  • If a is a read and b is a write, this is an anti-dependence
  • If a is a write and b is a write, this is an output dependence
  • If a is a read and b is a read, this is an input dependence

• Chronological order
  • If Sa < Sb, this is a lexically forward dependence
  • If Sa = Sb, this is a self-dependence
  • If Sa > Sb, this is a lexically backward dependence

• Loop dependence
  • If all distances (σ) are zero (same place in memory), this is loop independent
  • If at least one distance is non-zero, this is a loop carried dependence