{{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 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 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 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