Циклически инвариантное движение кода - Loop-invariant code motion

В компьютерное программирование, код, инвариантный к циклам состоит из утверждений или выражений (в императив язык программирования ), который можно переместить за пределы тела цикла, не влияя на семантику программы. Циклически инвариантное движение кода (также называемый подъем или же скалярное продвижение) это оптимизация компилятора который выполняет это движение автоматически.

Пример

В следующем примере кода можно применить две оптимизации. 

int я = 0;пока (я < п) {    Икс = у + z;    а[я] = 6 * я + Икс * Икс;    ++я;}

Хотя расчет х = у + г и х * х инвариантен к циклам, перед перемещением кода за пределы цикла необходимо принять меры предосторожности. Возможно, условие цикла ложный (например, если п содержит отрицательное значение), и в таком случае тело цикла вообще не должно выполняться. Один из способов гарантировать правильное поведение - использовать условный переход вне цикла. Оценка условия цикла может иметь побочные эффекты, поэтому дополнительная оценка если конструкция должна быть компенсирована заменой пока петля с делать пока. Если использованный код делать пока во-первых, весь процесс защиты не нужен, так как тело цикла гарантированно выполняется хотя бы один раз. 

int я = 0;если (я < п) {    Икс = у + z;    int const t1 = Икс * Икс;    делать {        а[я] = 6 * я + t1;        ++я;    } пока (я < п);}

Этот код можно оптимизировать в дальнейшем. Например, снижение силы может удалить два умножения внутри цикла (6 * я и а [я]), и индукционная переменная устранение может затем устранить я полностью. С 6 * я должен идти в ногу с я Сама по себе нет необходимости иметь и то, и другое.

Обнаружение инвариантного кода

Обычно анализ определений используется для определения того, является ли оператор или выражение инвариантным для цикла.

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

Недавняя работа с использованием анализа зависимости потока данных [1] позволяет обнаруживать не только инвариантные команды, но и более крупные фрагменты кода, такие как внутренний цикл. Анализ также выявляет квазиинварианты произвольной степени, то есть команды или фрагменты кода, которые становятся инвариантными после фиксированного числа итераций тела цикла.

Преимущества

Код, инвариантный к циклам, который был выведен из цикла, выполняется реже, что обеспечивает ускорение. Еще один эффект этого преобразования - позволяет хранить константы в регистрах и избавляться от необходимости вычислять адрес и обращаться к памяти (или строке кэша) на каждой итерации.

Однако, если будет создано слишком много переменных, будет высокий регистрировать давление, особенно на процессорах с небольшим количеством регистров, например 32-битных x86. Если в компиляторе кончатся регистры, некоторые переменные будут пролился. Чтобы противодействовать этому, может быть выполнена обратная оптимизация, рематериализация.

Смотрите также

дальнейшее чтение

  • Ахо, Альфред V .; Сетхи, Рави; И Ульман, Джеффри Д. (1986). Компиляторы: принципы, методы и инструменты. Эддисон Уэсли. ISBN  0-201-10088-6.

внешняя ссылка

  1. ^ Мойен, Жан-Ив; Рубиано, Томас; Сейлер, Томас (2017). "Обнаружение квазиинвариантного фрагмента цикла". Автоматизированная технология проверки и анализа. 10482: 91–108. Дои:10.1007/978-3-319-68167-2_7.