2.4. Триады и косвенные триады
Триады так же, как и тетрады, являются удобной промежуточной формой представления бинарных операций. Формат триады имеет вид:
<код операции>, <операнд1>, <операнд2> .
В качестве кодов операций триад можно использовать коды операций тетрад, за исключением операций условного перехода BE (BL, BM), которые для триад не используются.
В триадах отсутствует поле для записи результата. Если в качестве операнда некоторой триады нужно использовать результат выполнения другой (ранее выполненной) триады, то в соответствующее поле триады записывается ссылка на триаду, в которой этот результат был получен. Результаты выполнения триад хранятся отдельно.
Пример 2.2
Запись в виде последовательности триад выражения A B – C / D:
(1) , A, B
(2) /, C, D
(3) –, (1), (2)
Номера триад указаны в скобках.
Количество триад и тетрад, необходимое для представления одних и тех же конструкций языка, является одним и тем же, но каждая триада занимает в памяти меньше места. Экономия памяти при использовании триад в качестве промежуточной формы программы по сравнению с тетрадами достигается также за счет того, что после выполнения триады, в которой одним из операндов является результат выполнения i-й триады, ее результат может быть уничтожен.
При выполнении машинно-независимой оптимизации некоторые операции могут удаляться из промежуточного представления программы или переставляться на другое место. При использовании тетрад такие преобразования не вызывают затруднений. В случае же триад могут возникнуть осложнения за счет того, что триады ссылаются друг на друга. Поэтому, если машинно-независимая оптимизация будет выполняться, необходимо либо хранить все результаты выполнения триад, либо использовать косвенные триады.
Косвенные триады представляются двумя списками. В первом списке хранятся сами триады, причем одинаковые триады в список заносятся только один раз. Второй список содержит номера триад в порядке их выполнения. При использовании косвенных триад перестановка и исключение идентичных операций во время машинно-независимой оптимизации производятся путем преобразования списка, содержащего номера триад. При этом вид триад и их количество в списке не изменяются. Использование косвенных триад приводит к дополнительному сокращению объема памяти, необходимого для хранения промежуточной формы программы, если исходная программа содержит большое число идентичных операций (обычно это имеет место при наличии в программе большого числа индексированных переменных).
Пример 2.3
Представить с помощью косвенных триад следующие операторы языка ПАСКАЛЬ:
A := B[j] + B[j + 1]; C := B[j] – B[j + 1]; D := B[j] + 2 B[j + 1];
Решение
Список триад Порядок выполнения триад
(1) SUBS, B, j (1), (2), (3), (4), (5),
(2) + , j , 1 (1), (2), (3), (6), (7),
(3) SUBS, B, (2) (1), (2), (3), (8), (9), (10)
(4) + , (1), (3)
(5) := , (4), A
(6) – , (1), (3)
(7) := , (6), C
(8) , 2, (3)
(9) + , (1), (8)
(10) := , (9), D