Устранение частичной избыточности

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

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

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

Например, рассмотрим рис. 1а, здесь выражение « b/c » оценивается дважды по одному пути потока, т. е. когда условие b > c истинно, даже если значения переменных b и c не изменяются. Следовательно, этот конкретный фрагмент кода частично избыточен. Эту избыточность можно устранить, если мы вычислим выражение « b/c» один раз и сохраним его в переменной, скажем , t. Затем мы можем использовать переменную t в нашем коде всякий раз, когда нам нужно значение выражения « b/c ».

Можем ли мы устранить все лишнее?

В предыдущем примере мы устранили избыточность в коде, продублировав общее выражение и переместив его в блоки других путей кода. Однако не всегда возможно реализовать этот прием в кодах с десятками или сотнями путей выполнения. Например, на рисунке 2 ниже выражение b/c является избыточным в пути «1 ⇒ 2 ⇒ 3». Но мы не можем продублировать и переместить выражение в блок 3, как это было сделано в предыдущем примере, потому что это создаст ненужные вычисления в путях, отличных от «1 ⇒ 2 ⇒ 3» или «1 ⇒ 3 ⇒ 4». .

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

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

Алгоритм ленивого кода-движения

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

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

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

Интуиция частичной избыточности одного выражения:

Рассмотрим выражение E , которое является избыточным в блоке A, что означает, что E было вычислено на всех путях выполнения, которые достигают блока A. Теперь, в этом случае, должно существовать множество блоков, скажем, B, среди которых все блоки имеют выражение E , что делает его избыточным в блоке A. Набор исходящих ребер из B в потоковом графе обязательно образует набор разрезов, который может отключить блок A от входа в код, если он будет удален.

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

Предвосхищение выражений:

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

Алгоритм:

Движение ленивого кода:

Step 1: Find all the anticipated expressions using a backward data-flow pass at each point in the code.

Step 2: Place the expressions where their values are anticipated along some other execution path. 

Step 3: Find the postponable expressions using a forward data-flow pass and place at a point in the code where they cannot be postponed further. 

Postponable expressions are those which are anticipated at some point in the code but they are not used for a long span of flow of code.

Step 4: Remove all the temporary variables assignment that are used only once in the complete code.