Исключение лишних операций

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

Рассмотрим алгоритм исключения лишних операций для триад.

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

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)