Оптимизация — это метод преобразования программы, который пытается улучшить код, заставляя его потреблять меньше ресурсов (т. Е. ЦП, память) и обеспечивать высокую скорость.
При оптимизации общие программные конструкции высокого уровня заменяются очень эффективными низкоуровневыми программными кодами. Процесс оптимизации кода должен следовать трем правилам, приведенным ниже:
-
Выходной код никоим образом не должен изменять значение программы.
-
Оптимизация должна увеличить скорость программы и, если возможно, программа должна потреблять меньше ресурсов.
-
Оптимизация должна быть быстрой и не должна задерживать весь процесс компиляции.
Выходной код никоим образом не должен изменять значение программы.
Оптимизация должна увеличить скорость программы и, если возможно, программа должна потреблять меньше ресурсов.
Оптимизация должна быть быстрой и не должна задерживать весь процесс компиляции.
Усилия по оптимизации кода могут быть предприняты на разных уровнях компиляции процесса.
-
В начале пользователи могут изменять / переставлять код или использовать лучшие алгоритмы для написания кода.
-
После генерации промежуточного кода компилятор может модифицировать промежуточный код путем вычисления адресов и улучшения циклов.
-
При создании целевого машинного кода компилятор может использовать иерархию памяти и регистры процессора.
В начале пользователи могут изменять / переставлять код или использовать лучшие алгоритмы для написания кода.
После генерации промежуточного кода компилятор может модифицировать промежуточный код путем вычисления адресов и улучшения циклов.
При создании целевого машинного кода компилятор может использовать иерархию памяти и регистры процессора.
Оптимизацию можно разделить на два типа: машинно-независимый и машинно-зависимый.
Машинно-независимая оптимизация
При этой оптимизации компилятор принимает промежуточный код и преобразует часть кода, которая не включает какие-либо регистры ЦП и / или абсолютные ячейки памяти. Например:
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) и дает тот же результат.
Инвариантный код : фрагмент кода, который находится в цикле и вычисляет одно и то же значение на каждой итерации, называется циклически инвариантным кодом. Этот код можно вывести из цикла, сохранив его для вычисления только один раз, а не с каждой итерацией.
Индукционный анализ : переменная называется индукционной переменной, если ее значение в цикле изменяется инвариантным значением цикла.
Снижение прочности : есть выражения, которые потребляют больше циклов ЦП, времени и памяти. Эти выражения должны быть заменены на более дешевые выражения без ущерба для вывода выражения. Например, умножение (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 следует вычислять только один раз.