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

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

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

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

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

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

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

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

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

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 и т. Д.

Базовая идентификация блока

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

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

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

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

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

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

Оптимизация цикла

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

Invariant code: Фрагмент кода, который находится в цикле и вычисляет одно и то же значение на каждой итерации, называется инвариантным к циклу кодом. Этот код можно вывести из цикла, сохранив его для однократного вычисления, а не для каждой итерации.
Induction analysis : Переменная называется индукционной переменной, если ее значение изменяется внутри цикла на инвариантное значение.
Strength reduction: Есть выражения, которые потребляют больше циклов ЦП, времени и памяти. Эти выражения следует заменить более дешевыми выражениями без ущерба для вывода выражения. Например, умножение (x * 2) дороже с точки зрения циклов процессора, чем (x << 1), и дает тот же результат.

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

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

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

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

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

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

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

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

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

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

[повторяющееся выражение]	[частично повторяющееся выражение]

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

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

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 следует вычислять только один раз.