Схема СУ - перевода дерева операций в последовательность триад

Функцию, реализующую перевод узла дерева в последовательность триад, назовем Code. Входные и выходные данные у этой функции будут те же, что и при работе с командами ассемблера. Триады являются машинно – независимой формой внутреннего представления в компиляторе результирующей объектной программы, а потому не требуют дополнительных условий при генерации кода. Триады взаимосвязаны между собой, поэтому для установки корректной взаимосвязи функция генерации кода должна учитывать также текущий номер очередной триады (i).

Будем рассматривать те же варианты узлов дерева, что и для команд ассемблера (табл. 2.3).

Таблица 2.3

Вид узла дерева	Результирующий код	Примечание
	i) act (oper1, oper2)	act – тип триады oper1, oper2 – операнды (листья дерева)
	i) Code (Узел 2, i) i+j) act (oper1, ^i+j-1)	Узел 2 – нижележащий узел (не лист) дерева Code (Узел 2, i) – последовательность триад, порождаемая для Узла 2, начиная с триады с номером i, j – количество триад, порождаемых для Узла 2
	i) Code (Узел 2, i) i+j) act (^i+j-1, oper2)	Узел 2 – нижележащий узел (не лист) дерева Code (Узел 2, i) – последовательность триад, порождаемая для Узла 2, начиная с триады с номером i, j – количество триад, порождаемых для Узла 2
	i) Code (Узел 2, i) i+j) Code (Узел 3, i+j) i+j+k) act (^i+j-1, ^i+j+k-1)	Code (Узел 2, i) – последовательность триад, порождаемая для Узла 2, начиная с триады с номером i, j – количество триад, порождаемых для Узла 2 Code (Узел 3, i+j) – последовательность триад, порождаемая для Узла 3, начиная с триады с номером i+j, k – количество триад, порождаемых для Узла 3

Для триад не требуется учитывать операцию присваивания как отдельный тип узла дерева. Она преобразуется в триаду обычного вида. Рассмотрим в качестве примера дерево, приведенное на рис. 2. Согласно принципу СУ – перевода, построение начинается от корня дерева.

Шаг 1: 1) Code(U2, 1)

i):= (A, ^i-1)

Шаг 2: 1) Code(U3, 1)

j) Code(U5, j)

i-1) –(^j-1, ^i-2)

i):= (A, ^i-1)

Шаг 3: 1) Code (U4, 1)

k) + (^k-1, D)

j) Code(U5, j)

i-1) –(^j-1, ^i-2)

i):= (A, ^i-1)

Шаг 4: 1) *(B,C)

2) +(^1, D)

3) Code (U5, 3)

i-1) – (^j-1, ^i-2)

i):=(A, ^i-1)

Шаг 5: 1) *(B,C)

2) +(^1, D)

3) *(B, 10)

4) –(^2, ^3)

5):=(A, ^4)

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

Как и последовательность команд ассемблера, последовательность триад можно оптимизировать

Методы оптимизации кода

Оптимизация программы – это обработка, связанная с переупорядочиванием и изменением операций в компилируемой программе с целью получения более эффективной результирующей объектной программы. Рассмотрим подробно два метода: свертка объектного кода и исключение лишних операций.

Свертка объектного кода

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

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

Рассмотрим выполнение алгоритма свертки объектного кода. Для пометки операций, не требующих порождения объектного кода, будем использовать триады специального вида C(K,0). Алгоритм свертки последовательно просматривает триады и для каждой триады делает следующее:

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

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

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

4. если триада выполняет присваивание типа a:=b, тогда:

a. если B – константа, то А со значением константы заносится в таблицу (если там уже было старое значение для А, то оно исключается);

b. если В – не константа, то А вообще исключается из таблицы T, если она там есть.

Рассмотрим пример выполнения алгоритма. Пусть фрагмент исходной программы (записанный на языке 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)

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

Таблица 2.4

Триада	Шаг 1	Шаг 2	Шаг 3	Шаг 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)
T	(,)	(i,2)	(i,3)	(i,2)	(i,2)	(i,2) (j,21)

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

1.:=(i,2)

2.:= (i,3)

3.:=(j,21)

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

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

Поделиться:

Воспользуйтесь поиском по сайту: