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

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

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

Отслаивание цикла

[править | править код]

Отслаивание цикла (разгрузка цикла, от англ. loop peeling) является частным случаем расщепления цикла, при котором из основного цикла выносятся одна или несколько зависимых итераций.

Например, следующий код на языке Си:

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

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

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

Таким образом, компилятор выносит первую итерацию, при которой p = 10, и изменяет цикл, ведь в остальных итерациях p = i-1.

Новый код равносилен предыдущему, однако устраняет необходимость в переменной р внутри тела цикла.

Впервые данная оптимизация появилась в GCC версии 3.4, и улучшилась в версии 7[1].

Примечания

[править | править код]
  1. GCC 7 Release Series — Changes, New Features, and Fixes - GNU Project (англ.). gcc.gnu.org. Дата обращения: 4 августа 2023. Архивировано 2 сентября 2020 года.

Литература

[править | править код]
  • Альфред Ахо, Моника Лам, Рави Сети, Джеффри Ульман. Компиляторы: принципы, технологии и инструментарий = 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.