Editing Loop splitting

{{short description|Compiler optimization technique}}
{{Use dmy dates|date=August 2019|cs1-dates=y}}
'''Loop splitting''' is a [[compiler optimization]] technique. It attempts to simplify a [[Control flow#Loops|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 <code>p = 10</code> only for the first iteration, and for all other iterations, <code>p = i - 1</code>. A compiler can take advantage of this by [[loop unwinding|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 <code>p</code> inside the loop body.

Loop peeling was introduced in [[GNU Compiler Collection|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"/>

== References ==
{{Reflist|refs=
<ref name="R1">[https://gcc.gnu.org/gcc-7/changes.html GCC 7 Release Series — Changes, New Features, and Fixes - GNU Project<!-- Bot generated title -->]</ref>
<ref name="Cannings1976">{{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 }}</ref>
<ref name="Cannings1978">{{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 }}</ref>
<ref name="Callahan_1988">{{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 }}</ref>
<ref name="Mahlke_1992">{{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}}</ref>
}}

== Further reading ==
* {{cite book |author-last1=Kennedy |author-first1=Ken |author-link1=Ken Kennedy (computer scientist) |author-last2=Allen |author-first2=Randy |title=Optimizing Compilers for Modern Architectures: A Dependence-Based Approach |url=https://archive.org/details/optimizingcompil00alle_837 |url-access=limited |chapter=Chapter 5.7. Index-Set Splitting - Chapter 5.7.2. Loop Peeling |publisher=[[Academic Press]] / [[Morgan Kaufmann Publishers]] / [[Elsevier]] |date=2002 |edition=2011 digital print of 1st |isbn=978-1-55860-286-1 |lccn=2001092381 |pages=[https://archive.org/details/optimizingcompil00alle_837/page/n208 211]–212}}

{{Compiler optimizations}}

{{DEFAULTSORT:Loop Splitting}}
[[Category:Compiler optimizations]]