Линейный участок программы — это выполняемая по порядку последовательность операций, имеющая один вход и один выход. Чаще всего линейный участок содержит последовательность вычислений, состоящих из арифметических операций и операторов присвоения значений переменным.
Для операций, составляющих линейный участок программы, могут применяться следующие виды оптимизирующих преобразований:
- удаление бесполезных присваиваний;
- исключение избыточных вычислений (лишних операций);
- свертка операций объектного кода;
- перестановка операций;
- арифметические преобразования.
Удаление бесполезных присваиваний заключается в том, что если в составе линейного участка программы имеется операция присвоения значения некоторой произвольной переменной А с номером 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, — на выполнение операций сдвига. В обоих случаях удается повысить быстродействие программы заменой сложных операций на более простые.
Свертка объектного кода
Свертка объектного кода — это выполнение во время компиляции тех операций исходной программы, для которых значения операндов уже известны. Нет необходимости многократно выполнять эти операции в результирующей программе — вполне достаточно один раз выполнить их при компиляции программы.
Алгоритм свертки для линейного участка программы работает со специальной таблицей Т, которая содержит пары (<переменная>,<константа>) для всех переменных, значения которых уже известны.
Рассмотрим выполнение алгоритма свертки объектного кода для триад. Для пометки операций, не требующих порождения объектного кода, будем использовать триады специального вида С (k, 0).
Алгоритм свертки триад последовательно просматривает триады линейного участка и для каждой триады делает следующее:
1 Если операнд есть переменная, которая содержится в таблице Т, то операнд
заменяется на соответствующее значение константы.
2 Если операнд есть ссылка на особую триаду типа С(k, 0), то операнд заменяется на значение константы k.
3 Если все операнды триады являются константами, то триада может быть
свернута. Тогда данная триада выполняется и вместо нее помещается особая
триада вида С(k,0), где k — константа, являющаяся результатом выполнения
свернутой триады. (При генерации кода для особой триады объектный код не
порождается, а потому она в дальнейшем может быть просто исключена.)
Если триада является присваиванием типа А:=В, тогда:
- если В — константа, то А со значением константы заносится в таблицу Т
(если там уже было старое значение для А, то это старое значение исключается);
- если В — не константа, то А вообще исключается из таблицы Т, если оно
там есть.
Рассмотрим пример выполнения алгоритма.
Пусть фрагмент исходной программы (записанной на языке типа Pascal) имеет вид:
I:=1+1;
I:=3;
J:=6*I+I
Ее внутреннее представление в форме триад будет иметь вид:
1 +(1,1);
2 :=(I,^1);
3 := (I,3);
4 *(6,I);
5 +(^4, I);
6 :=(J,^5).
Процесс выполнения алгоритма свертки показан в табл. 4.7.
Таблица 4.7 Пример работы алгоритма свертки
Триада | Шаг 1 | Шаг 2 | ШагЗ | Шаг 4 | Шаг 5 | Шаг 6 |
С (2, 0) | С (2, 0) | С (2, 0) | С (2, 0) | С (2, 0) | С (2, 0) | |
:= (I, ^1) | :=(I,2) | :=(I,2) | :=(I,2) | :=(I,2) | :=(I,2) | |
:=(I,3) | :=(I,3) | :=(I,3) | :=(I,3) | :=(I,3) | :=(I,3) | |
*(6,I) | * (6,I) | *(6,I) | С (18, 0) | С (18, 0) | С (18, 0) | |
+ (^4, I) | + (^4, I) | + (^4, I) | + (^4, I) | С (21,0) | С (21, 0) | |
:=(J,^5) | :=(J,^5) | :=(J,^5) | :=(J,^5) | :=(J,^5) | :=(J,21) | |
Т | (,) | (I, 2) | (I,3) | (I, 3) | (I, 3) | (I, 3) (J,21) |
Если исключить особые триады типа С(k,0) (которые не порождают объектного кода), то в результате выполнения свертки получим следующую последовательность триад:
1 := (I, 2)
2 := (I, 3)
3 := (J, 21)
Исключение лишних операций
Алгоритм исключения лишних операций просматривает операции в порядке их следования. Так же как и алгоритму свертки, алгоритму исключения лишних операций проще всего работать с триадами, потому что они полностью отражают взаимосвязь операций.
Рассмотрим алгоритм исключения лишних операций для триад.
Чтобы следить за внутренней зависимостью переменных и триад, алгоритм присваивает им некоторые значения, называемые числами зависимости, по следующим правилам:
1) изначально для каждой переменной ее число зависимости равно 0, так как в на
чале работы программы значение переменной не зависит ни от какой триады;
2) после обработки i-й триады, в которой переменной А присваивается некоторое значение, число зависимости A (dep(A))получает значение i, так как зна
чение А теперь зависит от данной i-й триады;
3) при обработке 1-й триады ее число зависимости (depd)) принимается равным значению 1+(максимальное из чисел зависимости операндов).
Таким образом, при использовании чисел зависимости триад и переменных можно утверждать, что если i-я триада идентична j-й триаде (j<i), то i-я триада считается лишней в том и только в том случае, когда dep(i)=dep(j).
Алгоритм исключения лишних операций использует в своей работе триады особого вида SAME(j, 0). Если такая триада встречается в позиции с номером i, то это означает, что в исходной последовательности триад некоторая триада i идентична триаде j.
Алгоритм исключения лишних операций последовательно просматривает триады линейного участка. Он состоит из следующих шагов, выполняемых для каждой триады:
1 Если какой-то операнд триады ссылается на особую триаду вида SAME(j,0), то
он заменяется на ссылку на триаду с номером j (^j).
2 Вычисляется число зависимости текущей триады с номером i, исходя из чисел зависимости ее операндов.
3 Если в просмотренной части списка триад существует идентичная j-я триада,
причем j<i и dep(i)=dep(j),то текущая триада i заменяется на триаду особого вида SAME(j,0).
4 Если текущая триада есть присвоение, то вычисляется число зависимости соответствующей переменной.
Рассмотрим работу алгоритма на примере:
D:=D+C*B;
A:=D+C*B;
C:=D+C*B;
Этому фрагменту программы будет соответствовать следующая последовательность триад:
1) * (С, В)
2) + (D, ^1)
3) :=(D, ^2)
4)* (С, В)
5)+ (D, ^4)
6) :=(А, ^5)
7)* (С, В)
8)+ (D, ^7)
9):= (С, ^8)
Видно, что в данном примере некоторые операции вычисляются дважды над одними и теми же операндами, а значит, они являются лишними и могут быть исключены. Работа алгоритма исключения лишних операций отражена в табл. 4.8.
Таблица 4.8 Пример работы алгоритма исключения лишних операций
Обрабатываемая триада i | Числа зависимости переменных | Числа зависимости триад dep(i) | Триады, полученные после выполнения алгоритма | |||
А | В | С | D | |||
1)*(С,В) | 1) * (С, В) | |||||
2)+(D,^l) | 2) + (D, ^1) | |||||
3) := (D, ^2) | 3):=(D, ^2) | |||||
4) * (С, В) | 4) SAME (1,0) | |||||
5) + (D, ^4) | 5) + (D, ^1) | |||||
6):= (А, ^5) | 6):= (А, ^5) | |||||
7) * (С, В) | 7) SAME (1, 0) | |||||
8) + (D, ^7) | 8) SAME (5, 0) | |||||
9):=(С,^8) | 9):= (С, ^5) |
Теперь, если исключить триады особого вида SAME( j, 0), то в результате выполнения алгоритма получим следующую последовательность триад:
1) * (С, В)
2) + (D, ^1)
3) := (D, ^2)
4) + (D, ^1)
5) := (А, ^4)
6) := (С, ^4)