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