Оптимизация объектного кода методом свертки

Свертка объектного кода - это выполнение во время компиляции тех операций исходной программы для которых значения операндов уже известны. Поэтому нет необходимости многократно выполнять их в самой результирующей программе - вполне достаточно один раз выполнить их при ее компиляции.

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

Алгоритм свертки работает со специальной таблицей T, которая содержит пары <переменная>-<константа> для всех переменных, значения которых уже известны. Кроме того, алгоритм свертки помечает те операции во внутреннем представлении программы, для которых в результате свертки уже не требуется генерация кода. Так как при выполнении алгоритма свертки учитывается взаимосвязь операций, то удобной формой представления для него являются триады, так как в других формах представления операций (таких как тетрады или команды ассемблера) требуются дополнительные структуры, чтобы отразить связь результатов одних операций с операндами других.

Алгоритм свертки триад последовательно просматривает триады линейного списка и для каждой триады делает следующее:

1) Если операнд есть переменная, которая содержится в таблице T, то операнд заменяется на соответствующее значение константы.

2) Если операнд есть ссылка на особую триаду типа C(K,0), то операнд заменяется на значение константы K.

3) Если все операнды триады являются константами, то триада может быть свернута. Тогда данная триада выполняется и вместо нее помещается особая триада вида C(K,0), где K - константа, результат выполнения свернутой триады. (При генерации кода для особой триады объектный код не порождается, а потому она в дальнейшем может быть просто исключена).

4) Если триада является присваиванием типа A:=B, тогда: если B - константа, то A со значением константы заносится в таблицу T (если там уже было старое значение для A, то это старое значение исключается). Если B - не константа, то A вообще исключается из таблицы T, если оно там есть.

 

Рассмотрим пример выполнения алгоритма.

Пусть фрагмент исходной программы (записанной на языке типа Паскаль) имеет вид:

I := 1 + 1;

I := 3;

J := 6*I + I;

Ее внутренне представление в форме триад будет иметь вид:

+ (1,1)

:= (I, ^1)

:= (I, 3)

* (6, I)

+ (^4, I)

:= (J, ^5)

Процесс выполнения алгоритма свертки можно отразить в табл. 7:

Таблица 7. Пример работы алгоритма свертки

Триада	Шаг 1	Шаг 2	Шаг 3	Шаг 4	Шаг 5	Шаг 6
1	C (2, 0)	C (2, 0)	C (2, 0)	C (2, 0)	C (2, 0)	C (2, 0)
2	:= (I, ^1)	:= (I, 2)	:= (I, 2)	:= (I, 2)	:= (I, 2)	:= (I, 2)
3	:= (I, 3)	:= (I, 3)	:= (I, 3)	:= (I, 3)	:= (I, 3)	:= (I, 3)
4	* (6, I)	* (6, I)	* (6, I)	C (18, 0)	C (18, 0)	C (18, 0)
5	+ (^4, I)	+ (^4, I)	+ (^4, I)	+ (^4, I)	C (21, 0)	C (21, 0)
6	:= (J, ^5)	:= (J, ^5)	:= (J, ^5)	:= (J, ^5)	:= (J, ^5)	:= (J, 21)
Т	( , )	( I, 2 )	( I, 3 )	( I, 3 )	( I, 3 )	( I, 3 ) ( J, 21 )

Если исключить особые триады типа C(K,0) (которые не порождают объектного кода), то в результате выполнения свертки получим следующую последовательность триад:

:= (I, 2)

:= (I, 3)

:= (J, 21)

Оптимизация объектного кода методом исключения лишних операций

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

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

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

1) изначально для каждой переменной ее число зависимости равно 0, так как в начале работы программы значение переменной не зависит ни от какой триады;

2) после обработки i-ой триады, в которой переменной A присваивается некоторое значение, число зависимости A (dep(A)) получает значение i, так как значение A теперь зависит от данной i-ой триады;

3) при обработке i-ой триады ее число зависимости (dep(i)) принима ется равным значению: 1+(максимальное из чисел зависимости операндов).

Таким образом, при использовании чисел зависимости триад и переменных можно утверждать, что если i-ая триада идентична j-ой триаде (j<i), то i-ая триада считается лишней в том и только в том случае, когда dep(i)=dep(j).

Алгоритм исключения лишних операций использует в своей работе также особого вида триады SAME(j,0), которые означают, что некоторая триада i идентична триаде j.

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

Если операнд ссылается на особую триаду вида SAME(j,0), то он заменяется на ссылку на триаду с номером j (^j).

Вычисляется число зависимости текущей триады с номером i, исходя из чисел зависимости ее операндов.

Если существует идентичная j-ая триада, причем j<i и dep(i)=dep(j), то текущая триада i заменяется на триаду особого вида SAME(j,0).

Если текущая триада есть присвоение, то вычисляется число зависимости соответствующей переменной.

Рассмотрим работу алгоритма на примере:

D := D + C*B;

A := D + C*B;

C := D + C*B;

Этому фрагменту программы будет соответствовать следующая последовательность триад:

* (C, B)

+ (D, ^1)

:= (D, ^2)

* (C, B)

+ (D, ^4)

:= (A, ^5)

* (C, B)

+ (D, ^7)

:= (C, ^8)

Работу алгоритма отобразим в табл. 8.

Теперь, если исключить триады особого вида SAME(j,0), то в результате выполнения алгоритма получим следующую последовательность триад:

* (C, B)

+ (D, ^1)

:= (D, ^2)

+ (D, ^1)

:= (A, ^4)

:= (C, ^4)

Обратите внимание, что в итоговой последовательности изменилась нумерация триад и номера в ссылках одних триад на другие. Если в программе компилятора в качестве ссылок использовать не номера триад, а непосредственно указатели на них, то изменение ссылок в таком варианте не потребуется.

Таблица 8. Пример работы алгоритма исключения лишних операций.

Обрабатываемая триада i	Числа зависимости переменных				Числа зависимости триад	Триады, полученные после выполнения
	A	B	C	D	dep(i)	алгоритма
1) * (C, B)	0	0	0	0	1	1) * (C, B)
2) + (D, ^1)	0	0	0	0	2	2) + (D, ^1)
3) := (D, ^2)	0	0	0	3	3	3) := (D, ^2)
4) * (C, B)	0	0	0	3	1	4) SAME (1, 0)
5) + (D, ^4)	0	0	0	3	4	5) + (D, ^1)
6) := (A, ^5)	6	0	0	3	5	6) := (A, ^5)
7) * (C, B)	6	0	0	3	1	7) SAME (1, 0)
8) + (D, ^7)	6	0	0	3	4	8) SAME (5, 0)
9) := (C, ^8)	6	0	9	3	5	9) := (C, ^5)

Общий алгоритм генерации и оптимизации объектного кода

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

Алгоритм должен выполнить следующую последовательность действий:

1) построить последовательность триад на основе дерева вывода;

2) выполнить оптимизацию кода методом свертки;

3) выполнить оптимизацию кода методом исключения лишних операций;

4) преобразовать последовательность триад в последовательность команд на языке ассемблера (полученная последовательность команд и будет результатом выполнения алгоритма).

Алгоритм преобразования триад в команды языка ассемблера - это единственная машинно-зависимая часть общего алгоритма. При преобразовании компилятора для работы с другим результирующим объектным кодом потребуется изменить только эту часть, при этом все алгоритмы оптимизации и внутреннее представление программы останутся неизменными.

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: