Intuitive Loop Dependency Analysis: Think in 1D
Dependency analysis is one of the most important and fundamental topics in compiler optimization. It answers whether and how we can parallelize a loop to run programs faster—whether on CPU, GPU, TPU, or any other architecture. For first-time learners, it’s also one of the most opaque and abstract topics. Many end up memorizing the rules—which is what I did—then gradually, if ever, come to understand them through practice. This article aims to help readers gain an intuitive understanding of the basics through concrete examples. We’ll first walk through four typical cases, unroll them, and examine the dependency patterns with our own eyes. One especially powerful technique I’ve found is to mentally view a multi-dimensional array as a 1D array, just as it’s physically stored in memory. Then we’ll introduce the concept of the distance vector and explain how to systematically determine whether a loop can be parallelized. ...