Расщепление тела цикла (Jgvpyhlyuny mylg entlg)

Перейти к навигации Перейти к поиску

Расщепление тела цикла (англ. loop fission) — оптимизация компилятора, которая разбивает цикл в программе на несколько циклов, каждый из которых имеет те же индексные границы, однако содержит только часть тела исходного цикла.

Например, следующий код:

 int i, a[100], b[100];
 for (i = 0; i < 100; i++) {
   a[i] = 1; 
   b[i] = 2;
 }

в результате применения оптимизации преобразовывается в:

 int i, a[100], b[100];
 for (i = 0; i < 100; i++) {
   a[i] = 1;                     
 }
 for (i = 0; i < 100; i++) {
   b[i] = 2;
 }

Ключевой задачей таких оптимизаций является сокращение числа операций цикла. Здесь основным методом оптимизации является расщепление одного цикла на несколько, для каждого из которых число команд, необходимых для упаковки тела цикла, строго меньше числа команд для исходного цикла.

Расщепление полезно для изоляции цикловых зависимостей по данным при подготовке к векторизации цикла, для перестановок циклов или повышения вероятности кеширования в процессоре за счёт уменьшения общего количества данных, на которые делаются ссылки при полном выполнении каждого цикла.

Расщепление тела цикла является операцией, обратной слиянию циклов. Оно уместно, если количество вычислений в цикле становится чрезмерным, что в итоге приводит к снижению производительности. Расщепление также возможно, если цикл содержит условные операторы. В этом случае бывает полезно разделить циклы на два: один с условным оператором и один без него. В некоторых случаях (например, при использовании вложенных циклов) компилятор может расщепить тело цикла, а затем выполнить слияние, чтобы перестроить цикл другим способом для повышения производительности.

Литература

[править | править код]
  • Альфред Ахо, Моника Лам, Рави Сети, Джеффри Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е издание. — М.: «Вильямс», 2008. — 1184 с. — 1500 экз. — ISBN 978-5-8459-1349-4.
  • Steven S. Muchnick. Advanced Compiler Design and Implementation. — 5-е издание. — San Francisco: Morgan Kaufmann Publishers, 1997. — 856 с. — ISBN 1-55860-320-4.
  • Kennedy, Ken; & Allen, Randy. Optimizing Compilers for Modern Architectures: A Dependence-based Approach (англ.). — Morgan Kaufmann, 2001. — ISBN 1-55860-286-0.