Движение кода, инвариантное к циклу
 | Эта статья нуждается в дополнительных цитатах для проверки . ( январь 2021 г. ) |
В компьютерном программировании инвариантный к циклу код состоит из операторов или выражений (на императивном языке программирования ), которые можно перемещать за пределы тела цикла, не затрагивая семантику программы. Инвариантное к циклу перемещение кода (также называемое подъемом или скалярным продвижением ) — это оптимизация компилятора , которая выполняет это перемещение автоматически.
Пример
[ редактировать ]В следующем примере кода можно применить две оптимизации.
int i = 0;
while (i < n) {
x = y + z;
a[i] = 6 * i + x * x;
++i;
}
Хотя расчет x = y + z и x * x инвариантен к циклу, необходимо принять меры предосторожности перед перемещением кода за пределы цикла. Возможно, что условие цикла false (например, если n содержит отрицательное значение), и в этом случае тело цикла вообще не должно выполняться. Один из способов гарантировать правильное поведение — использовать условный переход вне цикла. Оценка условия цикла может иметь побочные эффекты , поэтому дополнительная оценка со стороны if конструкцию следует компенсировать заменой while петля с do {} while. Если используется код do {} while во-первых, весь процесс защиты не нужен, поскольку тело цикла гарантированно выполнится хотя бы один раз.
int i = 0;
if (i < n) {
x = y + z;
int const t1 = x * x;
do {
a[i] = 6 * i + t1;
++i;
} while (i < n);
}
Этот код можно оптимизировать дальше. Например, уменьшение силы может удалить два умножения внутри цикла ( 6*i и a[i]), и исключение индукционной переменной могло бы тогда ускользнуть i полностью. С 6 * i должен идти в ногу с i само по себе нет необходимости иметь оба.
Обнаружение инвариантного кода
[ редактировать ]Обычно анализ определений используется для определения того, является ли оператор или выражение инвариантом цикла.
Например, если все определения операндов некоторого простого выражения находятся за пределами цикла, выражение можно вывести из цикла.
Недавняя работа с использованием анализа зависимости потока данных [1] позволяет обнаруживать не только инвариантные команды, но и более крупные фрагменты кода, такие как внутренний цикл. Анализ также выявляет квазиинварианты произвольных степеней, то есть команды или фрагменты кода, которые становятся инвариантными после фиксированного числа итераций тела цикла.
Преимущества
[ редактировать ]Инвариантный к циклу код, выведенный из цикла, выполняется реже, что обеспечивает ускорение. Другим эффектом этого преобразования является возможность хранения констант в регистрах и отсутствие необходимости вычислять адрес и обращаться к памяти (или строке кэша) на каждой итерации.
Однако если будет создано слишком много переменных, возникнет высокая нагрузка на регистры , особенно на процессорах с небольшим количеством регистров, таких как 32-битный x86 . Если компилятору не хватает регистров, некоторые переменные будут потеряны . Чтобы противодействовать этому, можно выполнить обратную оптимизацию — рематериализацию .
См. также
[ редактировать ]Дальнейшее чтение
[ редактировать ]- Ахо, Альфред В.; Сетхи, Рави; И Уллман, Джеффри Д. (1986). Составители: принципы, методы и инструменты. Эддисон Уэсли. ISBN 0-201-10088-6 .
Ссылки
[ редактировать ]- ^ Мойен, Жан-Ив; Рубиано, Томас; Зайллер, Томас (2017). «Цикл квазиинвариантного обнаружения фрагментов». Автоматизированная технология проверки и анализа . Конспекты лекций по информатике. 10482 : 91–108. дои : 10.1007/978-3-319-68167-2_7 . ISBN 978-3-319-68166-5 .