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

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

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

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

  я = 320 * 200 * 32;

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

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

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

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

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

Постоянное распространение

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

  int Икс = 14;  int у = 7 - Икс / 2;  возвращаться у * (28 / Икс + 2);

Размножение x дает:

  int Икс = 14;  int у = 7 - 14 / 2;  возвращаться у * (28 / 14 + 2);

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

  int Икс = 14;  int у = 0;  возвращаться 0;

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

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

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

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

  int а = 30;  int б = 9 - (а / 5);  int c;  c = б * 4;  если (c > 10) {     c = c - 10;  }  возвращаться c * (60 / а);

Однократное применение постоянного размножения с последующим сворачиванием констант дает:

  int а = 30;  int б = 3;  int c;  c = б * 4;  если (c > 10) {     c = c - 10;  }  возвращаться c * 2;

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

  int а = 30;  int б = 3;  int c;  c = 12;  если (истинный) {     c = 2;  }  возвращаться c * 2;

В качестве а и б были упрощены до констант, и их значения заменялись везде, где они встречались, теперь компилятор применяет устранение мертвого кода чтобы отбросить их, еще больше сократив код:

  int c;  c = 12;  если (истинный) {     c = 2;  }  возвращаться c * 2;

В приведенном выше коде вместо истинный это может быть 1 или любая другая логическая конструкция в зависимости от структуры компилятора. С традиционным постоянным распространением мы получим только такую ​​оптимизацию. Это не может изменить структуру программы.

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

  возвращаться 4;

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

Смотрите также

Рекомендации

  1. ^ Стивен Мучник; Muchnick and Associates (15 августа 1997 г.). Расширенная реализация проекта компилятора. Морган Кауфманн. ISBN  978-1-55860-320-2. постоянное распространение ИЛИ постоянное сворачивание.
  2. ^ Wegman, Mark N; Задек, Ф. Кеннет (апрель 1991 г.), «Постоянное распространение с условными ветвями», Транзакции ACM по языкам и системам программирования, 13 (2): 181–210, CiteSeerX  10.1.1.130.3532, Дои:10.1145/103135.103136

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