Outline

• Motivation: exec$^{\rm n}$ order really matters, even on fairly ``ordinary'' architectures.
• Dependence analysis: how compiler can analyse array subscript exp$^{\rm n}$s in order to determine whether restructuring would be valid - e.g.
  • Loop interchange
  • Loop fusion
  • Loop reversal
  • Loop parallelisation (for parallel or pipelined machines)
  • Loop vectorisation (machines with vector registers and vector instructions)
• Loop transformation using unimodular matrices: given the dependence structure, how does the compiler efficiently find the optimum loop transformation?