Пример генерации по сбалансированному дереву
Пример. b+ (a^.d+e) +с
Пусть в результате генерации по сбалансированному дереву получили следующую последовательность команд:
1. S.S1 а
2. S.S2 d
3. S.S3 S.S2*S.S1
4. S.S4 е
5. S.S5 S.S3+S.S4 (9)
6. S.S6 Ь
7. S.S7 с
8. S.S8 S.S6+S.S7
9. S.S9 S.S8 + S.S5.
Для облегчения перестановки команд, связанных непосредственно с командой, вызывающей задержку (в примере (9) команды 6, 7), иначе говоря, поддерева на данном представлении псевдокоманд сохраняется информация, отражающая древовидную структуру или взаимозависимость команд, полученных при генерации по дереву.
В примере (9) команда (8) вызывает задержку команды (9). Для устранения этой задержки требуется вместе с командой (8) переставить команды (6) и (7), иначе говоря, поддерево.
Имеется две возможности: 1) переставить поддерево перед командой (1). В этом случае время жизни регистра S.S8 распространяется на весь интервал (команда (1)—команда (9)).
Мы можем также переставить поддерево между командами (3) и (4). Команда (5) не может быть начата пока не будет получен результат команды (3). Команда (4) не оказывает влияния, поэтому чтобы уменьшить время жизни регистра S.S4, мы переставляем поддерево в указанное место. Таким образом, в «окне» будут начаты команда умножения, выполняемая па раллельно с командой сложения (4).
Данный вид оптимизации выполняется на линейном участке, по представлению, которое получается в ходе работы генератора псевдокода. Как уже отмечалось, полученные в результате псевдокоманды отличаются от команд в том, что они содержат виртуальные, а не действительные номера A/S регистров.
Метки: возможности, пример, перестановка команд, сбалансированное дерево, последовательность команд