ВУЗ:
Составители:
58
Рассмотрим пример выполнения алгоритма:
Пусть фрагмент исходной программы имеет вид:
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)
Процесс выполнения алгоритма свертки можно отразить в таблице:
Триада Шаг 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) (которые не порождают объ-
ектного кода), то в результате получим следующую последовательность триад:
1. := (I, 2)
2. := (I, 3)
3. := (J, 21)
Оптимизация объектного кода методом исключения лишних
операций
Сначала определим понятие лишней операции. Операция линейного участ-
ка с порядковым номером i считается лишней, если существует более ранняя
идентичная ей операция с порядковым номером j и никакая переменная, от ко-
торой зависит эта операция, не изменялась никакой третьей операций, имею-
щей порядковый номер между i и j.
Алгоритм исключения лишних операций просматривает операции в поряд-
ке их следования. Также как и алгоритму свертки, алгоритму исключения лиш-
них операций проще всего работать с триадами, потому что они полностью от-
ражают взаимосвязь операций.
Чтобы следить за внутренней зависимостью переменных и триад алгоритм
присваивает им некоторые значения, называемые числами зависимости, по сле-
дующим правилам:
• изначально для каждой переменной ее число зависимости равно 0, так
