Compilers 107 - Optimizer Loop Unrolling

The last post covered optimization in general. In this post you’ll look at a specific optimization called “loop unrolling”.

The Compiler series:

• Compilers 101 – Overview and Lexer
• Compilers 102 – Parser
• Compilers 103 – Semantic Analyzer
• Compilers 104 – IR Generation
• Compilers 105 – Back End Overview
• Compilers 106 - Optimizer

Loop Unrolling

Loops are a key optimization point. Unrolling a loop means that you repeat the code content of the loop multiple times. It is essentially exactly what you are taught not to do when writing code.

Loop unrolling avoids costly branches. This will not necessarily unroll the entire loop so that you get code repeated 100s of times, but it may unroll it a bit so the code repeats a few times.

Modern hardware hates branches because it makes other optimization more difficult, so unrolling a loop enables additional optimizations for both the compiler itself and the CPU.

Here is a simple loop:

Dim i As Integer = 0
While i < 2
  i = i + 1
Wend
Beep

This gets modeled as a control flow graph:

A control flow graph is a directed graph.

Looking at the above, the while gets converted to an if. After the integer assignment, there is a branch back to the if. If the condition is false, then it branches to the beep. This is essentially a Goto, for old-timers.

But the compiler may also insert stuff on your behalf. For example, Xojo adds Yield function calls to enable cooperative threading and these function calls cannot be removed by the optimization process.

So to unroll the loop, the idea is that there are only two iterations of the loop which the compiler is able to determine.

So unrolling results in this:

In this short and simple example, the value of the “i” variable is never used so it can be discarded, saving both iteration time and storage space.