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