ВУЗ:
Составители:
59
как в начале работы программы значение переменной не зависит ни от
какой триады;
• после обработки i-ой триады, в которой переменной A присваивается
некоторое значение, число зависимости A (dep(A)) получает значение i,
так как значение A теперь зависит от данной i-ой триады;
•
при обработке i-ой триады ее число зависимости (dep(i)) принимается
равным значению: 1+(максимальное из чисел зависимости операндов).
Таким образом, при использовании чисел зависимости триад и переменных
можно утверждать, что если i-я триада идентична j-й триаде (j<i), то i-я триада
считается лишней в том и только в том случае, когда dep(i)=dep(j).
Алгоритм исключения лишних операций использует в своей работе также
особого вида триады SAME(j,0), которые означают, что некоторая триада 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) * (C, B); 2) + (D, ^1); 3) := (D, ^2); 4) * (C, B); 5) + (D, ^4);
6) := (A, ^5); 7) * (C, B); 8) + (D, ^7); 9) := (C, ^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)
