Loop fission and fusion

Loop fission and loop fusion are a pair of opposite compiler optimizations that restructure loops. Loop fission, also called loop distribution, breaks one loop into several loops over the same index range, each taking only a part of the original loop body. The aim is to turn a large loop body into smaller ones that make better use of locality of reference, and it is most effective on multi-core processors that can give each new loop to a different processor. Loop fusion, also called loop jamming, does the reverse and replaces several loops with a single one. It does not always speed a program up, because on some architectures two loops perform better than one thanks to the data locality inside each loop. Its main benefits are that it can avoid temporary array allocations, which gives large gains in numerical languages such as Julia when working elementwise on arrays, that it removes the overhead of loop control, and that it lets the processor exploit instruction-level parallelism when the bodies share no data dependencies. A compiler for C++ would need to inline calls, fuse the loops and remove the unused stores and allocation to fuse a typical expression, and as of clang 12 and gcc 11.1 it does not do so even at the highest optimization level.