Editing Optimizing compiler (section)

=== Loop optimizations ===
{{Main|Loop optimization}}
''Loop optimization'' acts on the statements that make up a loop, such as a ''for'' loop, for example [[loop-invariant code motion]]. Loop optimizations can have a significant impact because many programs spend a large percentage of their time inside loops.<ref name="aho-sethi-ullman" />{{rp|page=596}}

Some optimization techniques primarily designed to operate on loops include:

;[[Induction variable analysis]]: Roughly, if a variable in a loop is a simple linear function of the index variable, such as <code>j := 4*i + 1</code>, it can be updated appropriately each time the loop variable is changed. This is a [[strength reduction]] and also may allow the index variable's definitions to become [[dead code]].<ref name="aho-sethi-ullman" />{{rp|pages=596–598}} This information is also useful for [[bounds-checking elimination]] and [[dependence analysis]], among other things.

;[[Loop fission]] or loop distribution: Loop fission attempts to break a loop into multiple loops over the same index range with each new loop taking only a part of the original loop's body. This can improve [[locality of reference]] to both the data being accessed within the loop and the code in the loop's body.

;[[Loop fusion]] or loop combining or loop ramming or loop jamming: Another technique that attempts to reduce loop overhead. When two adjacent loops would iterate the same number of times regardless of whether that number is known at compile time, their bodies can be combined as long as they do not refer to each other's data.

;[[Loop inversion]]: This technique changes a standard ''while'' loop into a ''do/while'' (also known as ''repeat/until'') loop wrapped in an ''if'' conditional, reducing the number of jumps by two, for cases when the loop is executed. Doing so duplicates the condition check (increasing the size of the code) but is more efficient because jumps usually cause a [[pipeline stall]]. Additionally, if the initial condition is known at compile-time and is known to be [[Side effect (computer science)|side-effect]]-free, the ''if'' guard can be skipped.

;[[Loop interchange]]: These optimizations exchange inner loops with outer loops. When the loop variables index into an array, such a transformation can improve the locality of reference, depending on the array's layout.

;[[Loop-invariant code motion]]: If a quantity is computed inside a loop during every iteration, and its value is the same for each iteration, it can vastly improve efficiency to hoist it outside the loop and compute its value just once before the loop begins.<ref name="aho-sethi-ullman" />{{rp|page=596}} This is particularly important with the address-calculation expressions generated by loops over arrays. For correct implementation, this technique must be used with [[loop inversion]], because not all code is safe to be hoisted outside the loop.

;[[Loop nest optimization]]: Some pervasive algorithms such as matrix multiplication have very poor cache behavior and excessive memory accesses. Loop nest optimization increases the number of cache hits by operating over small blocks and by using a loop interchange.

;Loop reversal: Loop reversal reverses the order in which values are assigned to the index variable. This is a subtle optimization that can help eliminate [[dependence analysis|dependencies]] and thus enable other optimizations. Furthermore, on some architectures, loop reversal contributes to smaller code, as when the loop index is being decremented, the condition that needs to be met for the running program to exit the loop is a comparison with zero. This is often a special, parameter-less instruction, unlike a comparison with a number, which needs the number to compare to. Therefore, the amount of bytes needed to store the parameter is saved by using the loop reversal. Additionally, if the comparison number exceeds the size of word of the platform, in standard loop order, multiple instructions would need to be executed to evaluate the comparison, which is not the case with loop reversal.

;[[Loop unrolling]]: Unrolling duplicates the body of the loop multiple times, to decrease the number of times the loop condition is tested and the number of jumps; tests and jumps can hurt performance by impairing the instruction pipeline. A "fewer jumps" optimization. Completely unrolling a loop eliminates all overhead, but requires that the number of iterations be known at compile time.

;[[Loop splitting]]: Loop splitting attempts to simplify a loop or eliminate dependencies by breaking it into multiple loops that have the same bodies but iterate over different contiguous portions of the index range. A useful special case is ''[[loop peeling]]'', which can simplify a loop with a problematic first iteration by performing that iteration separately before entering the loop.

;[[Loop unswitching]]: Unswitching moves a conditional from inside a loop to outside the loop by duplicating the loop's body inside each of the if and else clauses of the conditional.

;[[Software pipelining]]: The loop is restructured in such a way that work done in an iteration is split into several parts and done over several iterations. In a tight loop, this technique hides the latency between loading and using values.

;[[Automatic parallelization]]: A loop is converted into multi-threaded or vectorized (or even both) code to use multiple processors simultaneously in a shared-memory multiprocessor (SMP) machine, including multi-core machines.