loop splitting#Loop peeling

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:

int p = 10;

for (int i=0; i<10; ++i)

{

y[i] = x[i] + x[p];

p = i;

}

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:

y[0] = x[0] + x[10];

for (int i=1; i<10; ++i)

{

y[i] = x[i] + x[i-1];

}

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.

Brief history of the term

Apparently the term "peeling" was for the first time used by Cannings, Thompson and Skolnick 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.

In compiler technology, the term first turned up in late 1980s papers on VLIW and superscalar compilation.

References

{{Reflist|refs=

[https://gcc.gnu.org/gcc-7/changes.html GCC 7 Release Series — Changes, New Features, and Fixes - GNU Project]

{{Cite journal |author-last1=Cannings |author-first1=C. |author-last2=Thompson |author-first2=E. A. |author-last3=Skolnick |author-first3=H. H. |title=The recursive derivation of likelihoods on complex pedigrees |journal=Advances in Applied Probability |volume=8 |pages=622–625 |date=1976 |issue=4 |doi=10.2307/1425918|jstor=1425918 }}

{{Cite journal |author-last1=Cannings |author-first1=C. |author-last2=Thompson |author-first2=E. A. |author-last3=Skolnick |author-first3=H. H. |title=Probability functions on complex pedigrees |journal=Advances in Applied Probability |volume=10 |pages=26–61 |date=1978 |issue=1 |doi=10.2307/1426718|jstor=1426718 }}

{{Cite journal |author-last1=Callahan |author-first1=D. |author-last2=Kennedy |author-first2=Ken |author-link2=Ken Kennedy (computer scientist) |title=Compiling Programs for Distributed-memory Multiprocessors |journal=The Journal of Supercomputing |volume=2 |pages=151–169 |date=1988 |issue=2 |doi=10.1007/BF00128175|s2cid=10214341 }}

{{Cite conference |author-last1=Mahlke |author-first1=S. A. |author-last2=Lin |author-first2=D. C. |author-last3=Chen |author-first3=W. Y. |author-last4=Hank |author-first4=R. E. |author-last5=Bringman |author-first5=R. A. |title=Effective compiler support for predicated execution using the hyperblock |conference=25th Annual International Symposium on Microarchitecture |pages=45–54 |date=1992}}

}}

loop splitting#Loop peeling

Loop peeling

Brief history of the term

References

Further reading