Постоянное сворачивание

Постоянное складывание и постоянная распространения являются связанными оптимизациями компилятора , используемых многими современными компиляторами . ^[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 ; c = b * 4; if (c > 10) { c = c - 10; } return c * 2;

Repeating both steps twice results in:

 int a = 30; int b = 3; int c; c = 12; if (true) { c = 2; } return c * 2;

As a and b have been simplified to constants and their values substituted everywhere they occurred, the compiler now applies dead code elimination to discard them, reducing the code further:

 int c; c = 12; if (true) { c = 2; } return c * 2;

In above code, instead of true it could be 1 or any other Boolean construct depending on compiler framework. With traditional constant propagation we will get only this much optimization. It can't change structure of the program.

There is another similar optimization, called sparse conditional constant propagation, which selects the appropriate branch on the basis of if-condition.^[2] The compiler can now detect that the if statement will always evaluate to true, c itself can be eliminated, shrinking the code even further:

 return 4;

If this pseudocode constituted the body of a function, the compiler could further take advantage of the knowledge that it evaluates to the constant integer 4 to eliminate unnecessary calls to the function, producing further performance gains.

See also[edit]

• Control-flow graph
• Use-define chain and SSA form
• Copy propagation
• Common subexpression elimination
• Partial evaluation

References[edit]

Further reading[edit]

• Muchnick, Steven S. (1997), Advanced Compiler Design and Implementation, Morgan Kaufmann, ISBN 9781558603202