Дизайн компилятора - оптимизация кода

Оптимизация - это метод преобразования программы, который пытается улучшить код, заставляя его потреблять меньше ресурсов (т. Е. ЦП, память) и обеспечивать высокую скорость.

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

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

Усилия по оптимизации кода могут быть предприняты на разных уровнях компиляции процесса.

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

Оптимизацию можно разделить на два типа: машинно-независимый и машинно-зависимый.

Машинно-независимая оптимизация

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

do
{
   item = 10;
   value = value + item; 
} while(value<100);

Этот код включает в себя повторное присвоение идентификатора элемента, который, если мы скажем так:

Item = 10;
do
{
   value = value + item; 
} while(value<100);

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

Машинно-зависимая оптимизация

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

Основные блоки

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

Программа может иметь различные конструкции в качестве базовых блоков, таких как условные операторы IF-THEN-ELSE, SWITCH-CASE и циклы, такие как DO-WHILE, FOR и REPEAT-UNTIL и т. Д.

Идентификация основного блока

Мы можем использовать следующий алгоритм, чтобы найти основные блоки в программе:

Искать в заголовках всех базовых блоков, с которых начинается базовый блок:
- Первое утверждение программы.
- Заявления, которые являются целью любой ветви (условные / безусловные).
- Заявления, которые следуют за любым заявлением ветви.
Операторы заголовка и операторы, следующие за ними, образуют основной блок.
Базовый блок не включает в себя какой-либо оператор заголовка любого другого базового блока.

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

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

График потока управления

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

Loop Optimization

Большинство программ работают в системе как цикл. Становится необходимым оптимизировать циклы, чтобы сэкономить циклы процессора и память. Циклы могут быть оптимизированы следующими методами:

Инвариантный код : фрагмент кода, который находится в цикле и вычисляет одно и то же значение на каждой итерации, называется кодом, инвариантным к циклу. Этот код можно вывести из цикла, сохранив его для вычисления только один раз, а не с каждой итерацией.
Индукционный анализ : переменная называется индукционной переменной, если ее значение в цикле изменяется инвариантным значением цикла.
Снижение прочности : есть выражения, которые потребляют больше циклов ЦП, времени и памяти. Эти выражения должны быть заменены более дешевыми выражениями без ущерба для вывода выражения. Например, умножение (x * 2) дороже с точки зрения циклов ЦП, чем (x << 1) и дает тот же результат.

Устранение мертвого кода

Мертвый код - это один или несколько операторов кода, которые:

Либо никогда не выполняется, либо недоступен,
Или, если выполняется, их вывод никогда не используется.

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

Частично мертвый код

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

На приведенном выше графике потока управления изображен фрагмент программы, в котором переменная «a» используется для назначения вывода выражения «x * y». Предположим, что значение, присвоенное 'a', никогда не используется внутри цикла. Сразу после того, как элемент управления покидает цикл, 'a' присваивается значение переменной 'z', которое будет использоваться позже в программе. Здесь мы заключаем, что код присваивания «а» нигде не используется, поэтому он может быть исключен.

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

Частичное резервирование

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

[избыточное выражение]

[частично избыточное выражение]

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

Другим примером частично избыточного кода может быть:

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

Мы предполагаем, что значения операндов ( y и z ) не изменяются от присвоения переменной a переменной c . Здесь, если выражение условия истинно, тогда y OP z вычисляется дважды, в противном случае - один раз. Кодовое движение может использоваться для устранения этой избыточности, как показано ниже:

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

Здесь, является ли условие истинным или ложным; y OP z следует вычислять только один раз.