Compilers

The prior tutorial showed how to determine whether a loop can be shuffled (parallelized) by examining access patterns, computing distance vectors, and applying the first-positive rule. This tutorial puts those ideas into code. We’ll write a mini LLVM pass that takes a loop nest and reports which levels are shuffleable. For pedagogical purposes, we keep the problem constrained and avoid LLVM’s built-in dependence analysis. Problem Scope Our pass handles loops matching this template: ...

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. ...