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

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

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

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

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

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

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

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

Удаление бесполезных присваиваний заключается в том, что если в составе линейного участка программы имеется операция присваивания значения некоторой произвольной переменной А с номером 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, – на выполнение операций сдвига. В обоих случаях удается повысить быстродействие программы заменой сложных операций на более про­стые.