LLVM contains an evolving set of classes and tools specifically designed to interact with loops. The Loop and LoopInfo classes are being continually improved, as are supporting data structures such as the Data Dependence Graph (DDG) and Program Dependence Graph (PDG). The pass manager infrastructure (both New and Legacy pass managers) provide infrastructure to write both function passes and loop passes. However, putting all of these concepts together to write a functioning loop optimization pass can still be a somewhat daunting task.
This tutorial will start by introducing basic terminology that is used within LLVM to describe loops (for example, many of the concepts introduced in
https://reviews.llvm.org/D65164). It will then look at the Loop and LoopInfo classes, and go over the interfaces they have to work with loops. It will provide examples of how these classes can be used to implement different types of loop optimizations, using examples from both the Loop Fusion and Loop Distribution passes. It will discuss the differences between a function pass and a loop pass, including a discussion of the advantages and disadvantages of each one when writing loop optimizations. It will also provide guidance on when each type of pass should be used. Finally, it will go through many of the useful utility functions that need to be used in order to write a loop optimization efficiently (e.g., updating the dominator tree, updating Scalar Evolution, etc.).