Оптимизация линейных участков программ
Линейный участок программы — это выполняемая по порядку последовательность операций, имеющая один вход и один выход. Чаще всего линейный участок содержит последовательность вычислений, состоящих из арифметических операций и операторов присвоения значений переменным.
Для операций, составляющих линейный участок программы, могут применяться следующие виды оптимизирующих преобразований:
- удаление бесполезных присваиваний;
- исключение избыточных вычислений (лишних операций);
- свертка операций объектного кода;
- перестановка операций;
- арифметические преобразования.
Удаление бесполезных присваиваний заключается в том, что если в составе линейного участка программы имеется операция присвоения значения некоторой произвольной переменной А с номером i, а также операция присвоения значения той же переменной А с номером j, i<j и ни в одной операции между i и j не используется значение переменной А, то операция присвоения значения с номером i является бесполезной. Фактически бесполезная операция присваивания значения дает переменной значение, которое нигде не используется. Такая операция может быть исключена без ущерба для смысла программы.
В общем случае, бесполезными могут оказаться не только операции присваивания, но и любые другие операции линейного участка, результат выполнения которых нигде не используется.
Например, во фрагменте программы
А := В * С;
D := В + С;
А := D * С;
операция присвоения А:=В*С; является бесполезной и может быть удалена. Вместе с удалением операции присвоения здесь может быть удалена и операция умножения, которая в результате также окажется бесполезной.
Обнаружение бесполезных операций присваивания далеко не всегда столь очевидно, как было показано в примере выше. Проблемы могут возникнуть, если между двумя операциями присваивания в линейном участке выполняются действия над указателями (адресами памяти) или вызовы функций, имеющих так называемый «побочный эффект».
Например, в следующем фрагменте программы
Р := @А;
А := В * С;
D := Р^ + С;
А := D * С;
операция присвоения А:= В*С; уже не является бесполезной, хотя это и не столь очевидно. В этом случае неверно следовать простому принципу о том, что если переменная, которой присвоено значение в операции с номером i, не встречается ни в одной операции между i и j, то операция присвоения с номером i является бесполезной.
Исключение избыточных вычислений (лишних операций) заключается в нахождении и удалении из объектного кода операций, которые повторно обрабатывают одни и те же операнды. Операция линейного участка с порядковым номером i считается лишней, если существует идентичная ей операция с порядковым номером j,j<i и никакой операнд, обрабатываемый этой операцией, не изменялся никакой операцией, имеющей порядковый номер между i и j.
Свертка объектного кода — это выполнение во время компиляции тех операций исходной программы, для которых значения операндов уже известны. Тривиальным примером свертки является вычисление выражений, все операнды которых являются константами.
Например, выражение А:=2*В*С*3; может быть преобразовано к виду А:=6*В*С.
Более сложные варианты алгоритма свертки принимают во внимание также и переменные, и функции, значения для которых уже известны.
Хорошим стилем программирования является объединение вместе операций, производимых над константами, чтобы облегчить компилятору выполнение свертки.
Перестановка операций заключается в изменении порядка следования операций, которое может повысить эффективность программы, но не будет влиять на конечный результат вычислений.
Например, операции умножения в выражении А:=2*В*3*С; можно переставить без изменения конечного результата и "выполнить в порядке А:=(2*3)*(В*С). Тогда представляется возможным выполнить свертку и сократить количество операций.
Арифметические преобразования представляют собой выполнение изменения характера и порядка следования операций на основании известных алгебраических и логических тождеств.
Например, выражение A:=B*C+B*D;может быть заменено на А:=В*(С+D):. Конечный результат при этом не изменится, но объектный код будет содержать на одну операцию умножения меньше.
К арифметическим преобразованиям можно отнести и такие действия, как замена возведения в степень на умножение; а целочисленного умножения на константы, кратные 2, — на выполнение операций сдвига. В обоих случаях удается повысить быстродействие программы заменой сложных операций на более простые.
Дата добавления: 2016-03-27; просмотров: 912;