Loop fusion and loop distribution are two key optimizations that typically are featured prominently in a loop optimization pipeline. They are used both to improve performance of applications and also to enable other loop optimizations. For example, loop fusion can improve the performance of applications through increasing temporal data cache locality. It can also increase the scope of other optimizations by creating larger loop nests for intra-loop nest optimizations to work on. Similarly, loop distribution is often used to improve performance directly by distributing loops that exceed hardware resources (e.g., register pressure). It is also frequently used to distribute loops containing loop-carried dependencies into two loops: one with loop carried dependencies and the second with no loop carried dependencies; this enables other optimizations (e.g., vectorization) on the independent loop. Furthermore, these two optimizations can work nicely together, as they have the ability to "undo" transformations done by the other. Thus, the implementation of both of these optimizations must be robust as they can both play an important role in a loop optimization pipeline.
This talk will be a follow-on to "Revisiting Loop Fusion, and its place in the loop transformation framework", presented at the 2018 LLVM Developers' Meeting. The patch to implement basic loop fusion described in the talk is currently undergoing review on phabricator (https://reviews.llvm.org/D55851). We have prototypes to make loop fusion more aggressive by moving code from between two loops (making them adjacent) that will be posted for review once the basic loop fusion patch is accepted. We also have plans to peel loops to (to make their bounds conform), and improve the dependence analysis between the two loop bodies. This talk will also include findings from our current analysis of the loop distribution pass in LLVM. It will provide a summary of the strengths and limitations of loop distribution, and summarize any improvements that are made prior to EuroLLVM 2019. Finally, the presentation will discuss how loop fusion and loop distribution can fit into the existing loop optimization pipeline in LLVM.
