Loop fusion is an optimization/transformation that takes two (or more) loops and
fuses (or joins) them together to create a single loop.
This pass implements Basic Loop Fusion. It will fuse loops that conform to the
following 4 conditions:
- Adjacent (no code in between the two loops)
- Control flow equivalent (if one loop executes, the other loop executes)
- Identical bounds (both loops iterate the same number of iterations)
- No negative distance dependencies between the loop bodies.
The intention is to initially focus on the safety checks and mechanics of loop
fusion. It makes no changes to the IR to create opportunities for fusion.
Instead, it checks the necessary conditions and if all conditions are met, it
fuses two loops together.
Further information on loop fusion, and techniques to improve the opportunities
for loop fusion can be found at
This patch intentionally does not add the loop fusion pass into the pass
pipeline. The location of loop fusion in the pass pipeline needs to be discussed
and I would prefer to have that discussion outside of this review.
This patch was done in collaboration with Johannes Doerfert.