Свёртка констант

Свёртка констант (англ. constant folding) и распространение констант (так же продвижение констант, дублирование констант, англ. constant propagation) — часто используемые в современных компиляторах оптимизации, уменьшающие избыточные вычисления, путём замены константных выражений и переменных на их значения^[1]. Так же часто применяется расширенный алгоритм sparse conditional constant propagation (англ.), выполняющий одновременно распространение констант и удаление некоторого мёртвого кода^[2].

Свёртка констант

Свёртка констант — оптимизация, вычисляющая константные выражения на этапе компиляции. Прежде всего, упрощаются константные выражения, содержащие числовые литералы. Также могут быть упрощены выражения, содержащие никогда неизменяемые переменные или переменные, объявленные как константы. Рассмотрим пример:

  i = 320 * 200 * 32;

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

Распространение констант

Распространение констант — оптимизация, заменяющее выражение, которое при выполнении всегда возвращает одну и ту же константу, самой этой константой^[3]. Это может быть константа, определённая ранее, или встроенная функция (англ.), применённая к константам. Рассмотрим следующий пример:

  int x = 14;
  int y = 7 - x / 2;
  return y * (28 / x + 2);

Распространение x возвращает:

  int x = 14;
  int y = 7 - 14 / 2;
  return y * (28 / 14 + 2);

Далее, свёртка констант и распространение y возвращают следующее (присваивания x и y, вероятно, в дальнейшем будут удалены оптимизацией удаления мёртвого кода):

  int x = 14;
  int y = 0;
  return 0;

См. также

• Граф потока управления
• SSA-представление

Примечания

1. ↑ Практикум "Оптимизирующие компиляторы" (на примере GCC). — НГУ им. Лобачевского. — С. 100.
2. ↑ Advanced Compiler Design and Implementation. — С. 362-370.
3. ↑ Компиляторы - принципы, технологии, инструменты, С. 760.

Литература

• Ахо, Альфред В.; Сети, Рави; Ульман, Джеффри Д. Компиляторы - принципы, технологии, инструменты. — Вильямс, 2003. — ISBN 5-8459-0189-8
• Muchnick, Steven S. Advanced Compiler Design and Implementation. — Morgan Kaufmann Publishers, 1997. — ISBN 1-55860-320-4

Ссылки

• Усовершенствованный алгоритм распространения констант с использованием GSA-представления
• Оптимизации в компиляторах. Часть 1