Постоянное складывание и постоянная распространения являются связанными оптимизациями компилятора , используемых многими современными компиляторами . [1] Расширенная форма распространения констант, известная как разреженное условное распространение констант, позволяет более точно распространять константы и одновременно удалять мертвый код .
Постоянное сворачивание
Сворачивание констант - это процесс распознавания и оценки константных выражений во время компиляции, а не их вычисление во время выполнения. Термины в постоянных выражениях обычно являются простыми литералами, такими как целочисленный литерал 2
, но они также могут быть переменными, значения которых известны во время компиляции. Рассмотрим утверждение:
я = 320 * 200 * 32 ;
Большинство компиляторов фактически не генерируют две инструкции умножения и хранилище для этого оператора. Вместо этого они идентифицируют такие конструкции и заменяют вычисленные значения во время компиляции (в данном случае 2,048,000
).
Постоянное сворачивание может использовать арифметические тождества. Если x
является числовым, значение 0 * x
равно нулю, даже если компилятор не знает значение x
(обратите внимание, что это недопустимо для чисел с плавающей запятой IEEE, поскольку это x
может быть Infinity или NotANumber . Тем не менее, некоторые языки, которые поддерживают производительность, такие как GLSL, допускают это для констант. , что иногда может вызывать ошибки).
Постоянное сворачивание может относиться не только к числам. Объединение строковых литералов и константных строк можно свернуть константой. Код, например, "abc" + "def"
может быть заменен на "abcdef"
.
Постоянное сворачивание и кросс-компиляция
При реализации кросс-компилятора необходимо следить за тем, чтобы поведение арифметических операций в архитектуре хоста соответствовало таковому в целевой архитектуре, поскольку в противном случае включение сворачивания констант изменит поведение программы. Это особенно важно в случае операций с плавающей запятой , точная реализация которых может широко варьироваться.
Постоянное распространение
Постоянное распространение - это процесс подстановки значений известных констант в выражения во время компиляции. К таким константам относятся константы, определенные выше, а также внутренние функции, применяемые к постоянным значениям. Рассмотрим следующий псевдокод:
int x = 14 ; int y = 7 - x / 2 ; вернуть y * ( 28 / x + 2 );
Размножение x дает:
int x = 14 ; INT у = 7 - 14 / 2 ; вернуться у * ( 28 / 14 + 2 );
Продолжение распространения приводит к следующему (который, вероятно, будет дополнительно оптимизирован путем удаления мертвого кода как x, так и y).
int x = 14 ; int y = 0 ; возврат 0 ;
В компиляторах реализовано постоянное распространение с использованием результатов анализа определения . Если все определения достижения переменной являются одним и тем же назначением, которое присваивает одну и ту же константу переменной, тогда переменная имеет постоянное значение и может быть заменена константой.
Постоянное распространение также может привести к упрощению условных переходов до одного или нескольких безусловных операторов, когда условное выражение может быть оценено как истинное или ложное во время компиляции, чтобы определить единственно возможный результат.
Оптимизация в действии
Постоянное сворачивание и распространение обычно используются вместе для достижения множества упрощений и сокращений путем их итеративного чередования до тех пор, пока не перестанут происходить изменения. Рассмотрим этот неоптимизированный псевдокод, который возвращает случайное число :
int a = 30 ; int b = 9 - ( a / 5 ); int c ; с = Ь * 4 ; если ( c > 10 ) { c = c - 10 ; } return c * ( 60 / a );
Однократное применение постоянного распространения с последующим сворачиванием констант дает:
int a = 30 ; int b = 3 ; int c ; с = Ь * 4 ; если ( c > 10 ) { c = c - 10 ; } return c * 2 ;
Повторение обоих шагов дважды приводит к:
int a = 30 ; int b = 3 ; int c ; c = 12 ; если ( правда ) { c = 2 ; } return c * 2 ;
Поскольку a
и b
были упрощены до констант и их значений, заменяемых везде, где они встречаются, компилятор теперь применяет удаление мертвого кода, чтобы отбросить их, еще больше сокращая код:
int c ; c = 12 ; если ( правда ) { c = 2 ; } return c * 2 ;
В приведенном выше коде вместо true
него может быть 1 или любая другая логическая конструкция в зависимости от структуры компилятора. С традиционным постоянным распространением мы получим только такую оптимизацию. Это не может изменить структуру программы.
Есть еще одна подобная оптимизация, называемая разреженным условным распространением констант , при которой соответствующая ветвь выбирается на основе if-condition
. [2] Теперь компилятор может определить, что if
выражение всегда будет истинным , c
само по себе может быть удалено, еще больше уменьшив код:
возврат 4 ;
Если бы этот псевдокод составлял тело функции, компилятор мог бы дополнительно воспользоваться знанием того, что он вычисляет постоянное целое число, 4
чтобы исключить ненужные вызовы функции, что приведет к дальнейшему увеличению производительности.
Смотрите также
Рекомендации
- ^ Стивен Мучник; Muchnick and Associates (15 августа 1997 г.). Реализация расширенного дизайна компилятора . Морган Кауфманн. ISBN 978-1-55860-320-2.
постоянное распространение ИЛИ постоянное сворачивание.
- ^ Wegman, Mark N; Zadeck Ф. Кеннет (апрель 1991), "постоянная распространения условных переходов", ACM Сделки по Языки программирования и системы , 13 (2): 181-210, CiteSeerX 10.1.1.130.3532 , DOI : 10,1145 / 103135.103136
дальнейшее чтение
- Мучник, Стивен С. (1997), Advanced Compiler Design and Implementation , Morgan Kaufmann, ISBN 9781558603202