Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Пример [ править ]

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

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 .

Ссылки [ править ]

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

Внешние ссылки [ править ]