Исключение лишних операций
Алгоритм исключения лишних операций просматривает операции в порядке их следования. Так же как и алгоритму свертки, алгоритму исключения лишних операций проще всего работать с триадами, потому что они полностью отражают взаимосвязь операций.
Рассмотрим алгоритм исключения лишних операций для триад.
Чтобы следить за внутренней зависимостью переменных и триад, алгоритм присваивает им некоторые значения, называемые числами зависимости, по следующим правилам:
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)
Дата добавления: 2016-03-27; просмотров: 963;