Loop splitting

Template:Short description Template:Use dmy dates Loop splitting is a compiler optimization technique. It attempts to simplify a loop or eliminate dependencies by breaking it into multiple loops which have the same bodies but iterate over different contiguous portions of the index range.

Loop peeling

Loop peeling is a special case of loop splitting which splits any problematic first (or last) few iterations from the loop and performs them outside of the loop body.

Suppose a loop was written like this: <syntaxhighlight lang="c">

int p = 10;
for (int i=0; i<10; ++i)
{
  y[i] = x[i] + x[p];
  p = i;
}

</syntaxhighlight> Notice that p = 10 only for the first iteration, and for all other iterations, p = i - 1. A compiler can take advantage of this by unwinding (or "peeling") the first iteration from the loop.

After peeling the first iteration, the code would look like this: <syntaxhighlight lang="c">

y[0] = x[0] + x[10];
for (int i=1; i<10; ++i)
{
  y[i] = x[i] + x[i-1];
}

</syntaxhighlight> This equivalent form eliminates the need for the variable p inside the loop body.

Loop peeling was introduced in gcc in version 3.4. More generalised loop splitting was added in GCC 7.<ref name="R1"/>

Brief history of the term

Apparently the term "peeling" was for the first time used by Cannings, Thompson and Skolnick<ref name="Cannings1976"/> in their 1976 paper on computational models for (human) inheritance. There the term was used to denote a method for collapsing phenotypic information onto parents. From there the term was used again in their papers, including their seminal paper on probability functions on complex pedigrees.<ref name="Cannings1978"/>

In compiler technology, the term first turned up in late 1980s papers on VLIW and superscalar compilation.<ref name="Callahan_1988"/><ref name="Mahlke_1992"/>

Further reading

• Template:Cite book