Оптимизирующий компилятор

Оптимизирующий компилятор — компилятор, в котором используются различные методы получения более оптимального программного кода при сохранении его функциональных возможностей. Наиболее распространённые цели оптимизации: сокращение времени выполнения программы, повышение производительности, компактификация программного кода, экономия памяти, минимизация энергозатрат, уменьшение количества операций ввода-вывода.

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

Оптимизация, как правило, реализуется с помощью последовательности оптимизирующих преобразований, алгоритмов, которые принимают программу и изменяют её для получения семантически эквивалентного варианта, который более эффективен с точки зрения какого-либо набора целей оптимизации. Было показано, что некоторые проблемы оптимизации кода являются NP-полными^[1], или даже неразрешимыми^[2]. Тем не менее, практически многие из них решаются эвристическими методами, дающими вполне удовлетворительные результаты.

Различают низко- и высокоуровневую оптимизацию. Низкоуровневая оптимизация преобразовывает программу на уровне элементарных команд, например, инструкций процессора конкретной архитектуры. Высокоуровневая оптимизация осуществляется на уровне структурных элементов программы, таких как модули, функции, ветвления, циклы.

Методы, используемые в оптимизациях, могут быть классифицированы по сфере применения: они могут влиять как на отдельный оператор, так и на целую программу. Локальные методы (затрагивающие небольшую часть программы) проще реализовать, чем глобальные (применяемые ко всей программе), но при этом глобальные методы часто оказываются более выгодными.

Локальные peephole-оптимизации (англ. peephole — «глазок») рассматривают несколько соседних (в терминах одного из графов представления программы) инструкций (как будто «смотрит в глазок» на код), чтобы увидеть, можно ли с ними произвести какую-либо трансформацию с точки зрения цели оптимизации. В частности, они могут быть заменены одной инструкцией или более короткой последовательностью инструкций.

Например, удвоение числа может быть более эффективно выполнено с использованием левого сдвига или путём сложения числа с таким же.

В локальной оптимизации рассматривается только информация одного базового блока за один шаг^[3]. Так как в базовых блоках нет переходов потока управления, эти оптимизации требуют незначительного анализа (экономя время и снижая требования к памяти), но это также означает, что не сохраняется информация для следующего шага.

Внутрипроцедурные оптимизации (англ. intraprocedural) — глобальные оптимизации, выполняемые целиком в рамках единицы трансляции (например, функции или процедуры)^[4]. При такой оптимизации задействовано гораздо больше информации, чем в локальной, что позволяет достигать более значительных эффектов, но при этом часто требуются ресурсозатратные вычисления. При наличии в оптимизируемой программной единице глобальных переменных оптимизация такого вида может быть затруднена.

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

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

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

Пример Пусть есть некоторая функция:

int pred(int x) {
    if (x == 0)
       return 0;
    else
       return x - 1;
}

До её встраивания код выглядел следующим образом:

 int f(int y) {
     return pred(y) + pred(0) + pred(y+1);
 }

После оптимизации:

int f(int y) {
    int temp = 0;
    if (y   == 0) temp += 0; else temp += y       - 1; /* (1) */
    if (0   == 0) temp += 0; else temp += 0       - 1; /* (2) */
    if (y+1 == 0) temp += 0; else temp += (y + 1) - 1; /* (3) */
    return temp;
}

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

Среди факторов, влияющих на оптимизацию, отмечаются как вычислительные характеристики целевой машины (например, количество и тактовая частота процессорных ядер, размер процессорного кэша, пропускная способность системной шины, объём оперативной памяти), так и архитектура целевого процессора (в частности, в разных архитектурах доступно различное количество регистров общего назначения, по-разному реализован вычислительный конвейер). Другой класс факторов, влияющих на оптимизацию — сценарии использования целевого программного кода, например, целевые характеристики оптимизации могут значительно отличаться для кода, предназначенного отладки и тестирования, для запуска время от времени, для постоянного использования, для применения во встраиваемых или автономных системах.

Среди принципов оптимизации, применяемых в различных методах оптимизации в компиляторах (некоторые из них могут противоречить друг другу или быть неприменимыми при разных целях оптимизации):

• уменьшение избыточности: повторное использование результатов вычислений, сокращение числа перевычислений;
• компактификация кода: удаление ненужных вычислений и промежуточных значений;
• сокращение числа переходов в коде: например, использование встраивания функций (англ. Inline expansion) или размотки цикла позволяет во многих случаях ускорить выполнение программы ценой увеличения размера кода;
• локальность: код и данные, доступ к которым необходим в ближайшее время, должны быть размещены рядом друг с другом в памяти, чтобы следовать принципу локальности ссылок (англ. Locality of reference);
• использование иерархии памяти: размещать наиболее часто используемые данные в регистрах общего назначения, менее используемые — в кэш, ещё менее используемые — в оперативную память, наименее используемые — размещать на диске.
• распараллеливание: изменение порядка операций может позволить выполнить несколько вычислений параллельно, что ускоряет исполнение программы (см. размотка цикла).

Анализ индуктивных переменных

если переменная в цикле является результатом простой линейной функции от индуктивной переменной, например for (i=0; i < 10; ++i) j = 17 * i;, то можно соответствующим образом обновлять данную переменную на каждой итерации. Это называется понижение силы операций.

Деление цикла на части

Оптимизация пытается разделить цикл на несколько отдельных с тем же диапазоном индекса. Каждый новый цикл является частью тела исходного цикла. Это может улучшить локальность ссылок (см. Принцип локальности ссылок (англ. Locality of reference)).

Объединение циклов (Слияние циклов)

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

Инверсия цикла

Этот метод меняет стандартный while цикл на do/while цикл, поставленный под некоторое условие, что уменьшает количество переходов на два для случаев, когда цикл выполняется.

Расщепление цикла

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

Оптимизации потока данных основаны на анализе потока данных (англ. Data-flow analysis) и обычно в качестве исходных данных рассматривают связанные друг с другом граф потока управления и граф потока данных, а также часто — дерево циклов и цикловую разметку графа потока управления. Путём анализа, в частности, пропагации информации, на этих графах, выявляется возможность оптимизации с точки зрения нужных целей, а затем оптимизации применяются.

Удаление общих подвыражений

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

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

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

Анализ индуктивных переменных (англ. Induction variable analysis)

См. описание в оптимизации циклов.

Удаление тупиковых записей

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

SSA (Single Static Assignment, Единственное статическое присваивание) — это форма представления графа потока данных (DFG, Data Flow Graph), при которой каждой переменной значение присваивается только один раз. Это позволяет избежать умножения дуг в графе при множественных записях и чтениях одной переменной и облегчает анализ графа. Для этого SSA-представление вводит специальные Phi-функции (узлы графа потока данных) в некоторых местах схождения в графе потока управления. Эти новые узлы являются так называемыми псевдоприсваиваниями.

Множественные определения возможны не только из-за схождений потока управления («или»), но из-за возможности чтения некоторого составного значения как целого, которое было записано по частям более, чем одной операцией («и»). В этом случае для поддержания SSA-формы вводятся дополнительные псевдоприсваивания внутри базовых блоков, которые собирают одно значение из нескольких.

На SSA основаны некоторые оптимизации. Хотя некоторые из них могут работать и без SSA, наиболее эффективными они являются в присутствии SSA.

• Эффективность алгоритма

• Альфред Ахо, Моника Лам, Рави Сети, Джеффри Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е издание. — М.: «Вильямс», 2008. — 1184 с. — 1500 экз. — ISBN 978-5-8459-1349-4.
• Steven Muchnick, Advanced Compiler Design and Implementation — Morgan Kaufmann, 1997 — ISBN 1-55860-320-4
• Keith Cooper, Linda Torczon, Engineering a Compiler, Second Edition — Morgan Kaufmann, 2011 — ISBN 978-0-12-088478-0

• НОУ ИНТУИТ | Введение в оптимизацию приложений с использованием компиляторов Intel | Информация Архивная копия от 24 декабря 2017 на Wayback Machine / Интуит.ру, 2011