Оптимизация линейных участков программы

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

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

· удаление бесполезных присваиваний;

· исключение избыточных вычислений (лишних операций);

· свертка операций объектного кода;

· перестановка операций;

· арифметические преобразования.

Удаление бесполезных присваиваний заключается в том, что если в составе линейного участка программы имеется операция присваивания значения некоторой произвольной переменной А с номером i, а также операция присваивания значения той же переменной А с номером j, i<j и ни в одной операции между i и j не используется значение переменной А, то операция присваивания значения с номером i является бесполезной. Фактически бесполезная операция присваивания значения дает переменной значение, которое нигде не используется. Такая операция может быть исключена без ущерба для смысла программы.

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

А:= В * С;

D:= В + С;

А:= D * С:

операция присваивания А:=В*С; является бесполезной и может быть удалена. Вместе с удалением операции присваивания здесь может быть удалена и операция умножения, которая в результате также окажется бесполезной.

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

Исключение избыточных вычислений (лишних операций) заключается в нахождении и удалении из объектного кода операций, которые повторно обрабатывают одни и те же операнды. Операция линейного участка с порядковым номером i считается лишней, если существует идентичная ей операция с порядковым номером j, j<i и никакой операнд, обрабатываемый этой операцией, не изменялся никакой операцией, имеющей порядковый номер между i и j.

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

Не всегда компилятору удается выполнить свертку, даже если выражение допускает ее выполнение. Например, выражение А:=2*В*С*3; может быть преобразовано к виду А:=6*В*С;, но при порядке вычислений А:=2*(В*(С*3)); это не столь очевидно. Для более эффективного выполнения свертки объектного кода возможно совместить ее выполнение с другим методом – перестановкой операций.

Перестановка операций заключается в изменении порядка следования операций, которое может повысить эффективность программы, но не будет влиять на конечный результат вычислений. Например, операции умножения в выражении А:=2*В*3*С; можно переставить без изменения конечного результата и выполнить в порядке А:=(2*3)*(В*С);. Тогда представляется возможным выполнить свертку и сократить количество операций.

Другое выражение A:=(B+C)+(D+E); может потребовать как минимум одной ячейки памяти (или регистра процессора) для хранения промежуточного результата. Но при вычислении его в порядке A:=B+(C+(D+E)); можно обойтись одним регистром, в то время как результат будет тем же.

Арифметические преобразования представляют собой выполнение изменения характера и порядка следования операций на основании известных алгебраических и логических тождеств. Например, выражение A:=B*C+B*D; может быть заменено на A:=B*(C+D);. Конечный результат при этом не изменится, но объектный код будет содержать на одну операцию умножения меньше.

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