Постоянное складывание

Свертывание констант и распространение констант — это связанные оптимизации компилятора, используемые многими современными компиляторами . Усовершенствованная форма распространения констант, известная как разреженное условное распространение констант, может более точно распространять константы и одновременно удалять мертвый код .

Постоянное складывание

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

  i = 320 * 200 * 32;

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

Константное свертывание может использовать арифметические тождества. Если x числовое, значение 0 * x равно нулю, даже если компилятор не знает значения x (обратите внимание, что это недействительно для чисел с плавающей запятой IEEE, поскольку x может быть Infinity или NaN . Тем не менее, некоторые среды, которые способствуют повышению производительности, такие как шейдеры GLSL, допускают это для констант, что иногда может вызывать ошибки).

Постоянное свертывание может применяться не только к числам. Конкатенация строковых литералов и константных строк может быть свернута константами. Код, такой как "abc" + "def" может быть заменен на "abcdef".

Постоянное сворачивание и кросс-компиляция

При реализации кросс-компилятора необходимо следить за тем, чтобы поведение арифметических операций на хост-архитектуре соответствовало поведению на целевой архитектуре, поскольку в противном случае включение свертывания констант приведет к изменению поведения программы. Это имеет особое значение в случае операций с плавающей запятой , точная реализация которых может сильно различаться.

Постоянное

Распространение констант — это процесс замены значений известных констант в выражениях во время компиляции. К таким константам относятся константы, определенные выше, а также внутренние функции, применяемые к постоянным значениям. Рассмотрим следующий псевдокод:

  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);

Продолжение распространения дает следующее (которое, вероятно, будет дополнительно оптимизировано путем устранения мертвого кода как x, так и y).

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

Постоянное распространение реализуется в компиляторах с использованием результатов анализа определений . Если все определения достижения переменной представляют собой одно и то же присвоение, которое присваивает переменной одну и ту же константу, то переменная имеет постоянное значение и может быть заменена константой.

Распространение констант также может привести к упрощению условных ветвей до одного или нескольких безусловных операторов, когда условное выражение может быть оценено как истинное или ложное во время компиляции для определения единственно возможного результата.

Оптимизации в действии

Постоянное свертывание и распространение обычно используются вместе для достижения множества упрощений и сокращений, и их чередующееся итеративное применение продолжается до тех пор, пока эти эффекты не прекратятся.

Рассмотрим этот неоптимизированный псевдокод, возвращающий неизвестное число, ожидающее анализа:

  int a = 30;
  int b = 9 - (a / 5);
  int c;

  c = b * 4;
  if (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;

Повторение обоих шагов дважды дает:

  int a = 30;
  int b = 3;
  int c;

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

Заменив все использование переменных a и b компилятором устранение мертвого кода с константами к этим переменным применяется , оставляя:

  int c;
  c = 12;

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

(Булевы конструкции различаются в зависимости от языка и компилятора, но их детали, такие как статус, происхождение и представление true , не влияют на эти принципы оптимизации.)

Традиционное постоянное распространение не приводит к дальнейшей оптимизации; он не реструктурирует программы.

Однако аналогичная оптимизация, разреженное распространение условной константы , идет дальше путем выбора соответствующей условной ветви, и удаление всегда истинного условного теста. Таким образом, переменная c становится излишним, и остается только операция над константой:

  return 4;

Если этот псевдокод представляет собой тело функции, компилятор знает, что функция оценивается как целочисленная константа. 4, позволяющий заменить вызовы функции на 4и дальнейшее повышение эффективности программы.

См. также

• Граф потока управления
• Цепочка использования-определения и форма SSA
• Распространение копирования
• Удаление общего подвыражения
• Частичная оценка

Дальнейшее чтение

• Мучник, Стивен С. (1997), Расширенный дизайн и реализация компилятора , Морган Кауфманн, ISBN  9781558603202