В программировании инвариантный к циклам код состоит из операторов или выражений (в императивном языке программирования ), которые могут быть перемещены за пределы тела цикла без влияния на семантику программы. Инвариантное к циклам перемещение кода (также называемое подъемом или скалярным продвижением ) — это оптимизация компилятора , которая автоматически выполняет это перемещение.
В следующем примере кода можно применить две оптимизации.
int i = 0 ; пока ( 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 ; если ( i < n ) { x = y + z ; int const t1 = x * x ; сделать { a [ i ] = 6 * i + t1 ; ++ i ; } пока ( i < n ); } Этот код можно оптимизировать еще больше. Например, сокращение силы может удалить два умножения внутри цикла ( 6*iи a[i]), а исключение индукционной переменнойi может полностью исключиться . Поскольку 6 * iдолжно быть в шаге с iсамим собой, нет необходимости иметь оба.
Обычно анализ идущих определений используется для определения того, является ли оператор или выражение инвариантным к циклу.
Например, если все определения достижения для операндов некоторого простого выражения находятся за пределами цикла, выражение можно переместить из цикла.
Недавняя работа с использованием анализа зависимости потока данных [1] позволяет обнаруживать не только инвариантные команды, но и более крупные фрагменты кода, такие как внутренний цикл. Анализ также обнаруживает квазиинварианты произвольной степени, то есть команды или фрагменты кода, которые становятся инвариантными после фиксированного числа итераций тела цикла.
Циклически-инвариантный код, выведенный из цикла, выполняется реже, что обеспечивает ускорение. Другим эффектом этого преобразования является возможность хранить константы в регистрах и отсутствие необходимости вычислять адрес и обращаться к памяти (или строке кэша) на каждой итерации.
Однако, если создано слишком много переменных, возникнет высокое давление регистров , особенно на процессорах с небольшим количеством регистров, таких как 32-битный x86 . Если компилятор исчерпает регистры, некоторые переменные будут сброшены . Чтобы противостоять этому, можно выполнить обратную оптимизацию, повторную материализацию .