Постоянное складывание
Свертывание констант и распространение констант — это связанные оптимизации компилятора, используемые многими современными компиляторами . [1] Усовершенствованная форма распространения констант, известная как разреженное условное распространение констант, позволяет более точно распространять константы и одновременно удалять мертвый код .
Постоянное складывание [ править ]
Свертывание констант — это процесс распознавания и оценки константных выражений во время компиляции , а не вычисления их во время выполнения. Термины в константных выражениях обычно представляют собой простые литералы, например целочисленный литерал. 2, но они также могут быть переменными, значения которых известны во время компиляции. Рассмотрим утверждение:
я = 320 * 200 * 32 ;
Большинство компиляторов на самом деле не генерируют две инструкции умножения и хранилище для этого оператора. Вместо этого они идентифицируют подобные конструкции и заменяют вычисленные значения во время компиляции (в данном случае 2,048,000).
Константное свертывание может использовать арифметические тождества. Если x числовое, значение 0 * x равно нулю, даже если компилятор не знает значения x (обратите внимание, что это недействительно для чисел с плавающей запятой IEEE, поскольку xможет быть Infinity или NaN . Тем не менее, некоторые среды, которые способствуют повышению производительности, такие как шейдеры GLSL , допускают это для констант, что иногда может вызывать ошибки).
Постоянное свертывание может применяться не только к числам. Конкатенация строковых литералов и константных строк может быть свернута константами. Код, такой как "abc" + "def" может быть заменен на "abcdef".
Постоянное сворачивание и кросс-компиляция [ править ]
При реализации кросс-компилятора необходимо следить за тем, чтобы поведение арифметических операций на хост-архитектуре соответствовало поведению на целевой архитектуре, поскольку в противном случае включение свертывания констант приведет к изменению поведения программы. Это имеет особое значение в случае операций с плавающей запятой , точная реализация которых может сильно различаться.
Постоянное распространение
Распространение констант — это процесс замены значений известных констант в выражениях во время компиляции. К таким константам относятся константы, определенные выше, а также внутренние функции , применяемые к постоянным значениям. Рассмотрим следующий псевдокод:
интервал х = 14 ;
интервал у = 7 - х / 2 ;
вернуть y * ( 28 / x + 2 );
Распространение x дает:
интервал х = 14 ;
int y = 7 - 14/2 ;
вернуть y * ( 28/14 + ) 2 ;
Продолжение распространения дает следующее (которое, вероятно, будет дополнительно оптимизировано путем устранения мертвого кода как x, так и y).
интервал х = 14 ;
интервал у = 0 ;
вернуть 0 ;
Постоянное распространение реализуется в компиляторах с использованием результатов анализа определений . Если все определения достижения переменной представляют собой одно и то же присвоение, которое присваивает переменной одну и ту же константу, то переменная имеет постоянное значение и может быть заменена константой.
Распространение констант также может привести к упрощению условных ветвей до одного или нескольких безусловных операторов, когда условное выражение может быть оценено как истинное или ложное во время компиляции для определения единственно возможного результата.
Оптимизации в действии [ править ]
Постоянное свертывание и распространение обычно используются вместе для достижения множества упрощений и сокращений, и их чередующееся итеративное применение продолжается до тех пор, пока эти эффекты не прекратятся.
Рассмотрим этот неоптимизированный псевдокод, возвращающий неизвестное число, ожидающее анализа:
интервал а = 30 ;
интервал б = 9 - ( а / 5 );
интервал с ;
в = б * 4 ;
если ( c > 10 ) {
c знак равно c - 10 ;
}
Вернуть c * ( 60 / a );
Применение постоянного распространения один раз с последующим постоянным свертыванием дает:
интервал а = 30 ;
интервал б = 3 ;
интервал с ;
в = б * 4 ;
если ( c > 10 ) {
c знак равно c - 10 ;
}
Вернуть с * 2 ;
Повторение обоих шагов дважды дает:
интервал а = 30 ;
интервал б = 3 ;
интервал с ;
с = 12 ;
если ( правда ) {
c знак равно 2 ;
}
Вернуть с * 2 ;
Заменив все использование переменных a и b компилятором с константами к этим переменным применяется устранение мертвого кода , оставляя:
интервал с ;
с = 12 ;
если ( правда ) {
c знак равно 2 ;
}
Вернуть с * 2 ;
(Булевы конструкции различаются в зависимости от языка и компилятора, но их детали, такие как статус, происхождение и представление значения true , не влияют на эти принципы оптимизации.)
Традиционное постоянное распространение не приводит к дальнейшей оптимизации; он не реструктурирует программы.
Однако аналогичная оптимизация, разреженное распространение условной константы , идет дальше путем выбора соответствующей условной ветви, [2] и удаление всегда истинного условного теста. Таким образом, переменная c становится излишним, и остается только операция над константой:
вернуть 4 ;
Если этот псевдокод представляет собой тело функции, компилятор знает, что функция оценивается как целочисленная константа. 4, позволяющий заменить вызовы функции на 4и дальнейшее повышение эффективности программы.
См. также [ править ]
- Граф потока управления
- Цепочка использования-определения и форма SSA
- Распространение копирования
- Удаление общего подвыражения
- Частичная оценка
Ссылки [ править ]
- ^ Стивен Мучник; Мучник и партнеры (15 августа 1997 г.). Расширенная реализация проекта компилятора . Морган Кауфманн. ISBN 978-1-55860-320-2 .
постоянное распространение ИЛИ постоянное сворачивание.
- ^ Вегман, Марк Н; Задек, Ф. Кеннет (апрель 1991 г.), «Постоянное распространение с условными ветвями», Транзакции ACM в языках и системах программирования , 13 (2): 181–210, CiteSeerX 10.1.1.130.3532 , doi : 10.1145/103135.103136 , S2CID 52813 828
Дальнейшее чтение [ править ]
- Мучник, Стивен С. (1997), Расширенный дизайн и реализация компилятора , Морган Кауфманн, ISBN 9781558603202