Loop splitting

From Wikipedia, the free encyclopedia

Loop splitting (or loop peeling) 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.

A useful special case is loop peeling, which can simplify a loop with a problematic first (or first few) iteration by performing that iteration separately before entering the loop.

Here is an example of loop peeling. Suppose the original code looks like this:

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

In the above code, only in the 1st iteration is p=10. For all other iterations p=i-1. We get the following after loop peeling:

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

Loop peeling was introduced in gcc in version 3.4.

[edit] Further reading

Kennedy, Ken; & Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 1-55860-286-0. 

[edit] See also

• Loop unwinding