 |
Исключение лишних операций
|
|
|
|
Алгоритм исключения лишних операций просматривает операции в порядке их следования. Так же как и алгоритм свертки, алгоритму исключения лишних операций проще работать с триадами, потому что они полностью отражают взаимосвязь операций.
Рассмотрим алгоритм исключения лишних операций для триад.
Чтобы следить за внутренней зависимостью переменных и триад, алгоритм присваивает им некоторые значения, называемые числами зависимости, по следующим правилам:
· изначально для каждой переменной ее число зависимости равно 0, так как в начале работы программы значение переменной не зависит ни от какой триады;
· после обработки i - й триады, в которой переменной A присваивается некоторое значение, число зависимости A (dep (A)) получает значение i, так как значение А теперь зависит от данной i -й триады;
· при обработке i -й триады ее число зависимости (dep(i)) принимается равным значению 1+(максимальное из чисел зависимости операндов).
Т.е., при использовании чисел зависимости триад и переменных можно утверждать, что если i -я триада идентична j -ой триаде (j<i), то i -я триада считается лишней в том и только в том случае, когда dep(i) = dep(j).
Алгоритм исключения лишних операций использует в своей работе триады особого вида SAME(j,0). Алгоритм исключения лишних операций состоит из следующих шагов, выполняемых для каждой триады:
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)
Видно, что в данном примере некоторые операции вычисляются дважды над одними и теми же операндами, а значит, они являются лишними и могут быть исключены. Работа алгоритма отражена в табл. 2.5.
Таблица 2.5
| Обрабатываемая триада i | Число зависимости переменных | Числа зависимости триад dep(i) | Полученные триады | |||
| A | B | C | D | |||
| 1) *(C,B) | 1) *(C,B) | |||||
| 2) +(D, ^1) | 2) +(D, ^1) | |||||
| 3):=(D, ^2) | 3):=(D, ^2) | |||||
| 4) *(C, B) | 4) SAME(1,0) | |||||
| 5) +(D, ^4) | 5) +(D, ^1) | |||||
| 6):=(A, ^5) | 6):=(A, ^5) | |||||
| 7) *(C,B) | 7) SAME(1,0) | |||||
| 8) +(D, ^7) | 8) SAME(5,0) | |||||
| 9):=(C, ^8) | 9):=(C, ^5) |
Теперь, если исключить триады особого вида SAME(j,0), то в результате выполнения алгоритма получим следующую последовательность триад:
1. * (C, B)
2. + (D, ^1)
3.:= (D, ^2)
4. + (D, ^1)
5.:=(A, ^4)
6.:=(C, ^4)
В итоговой последовательности изменилась нумерация триад и номера в ссылках одних триад на другие. Если в компиляторе в качестве ссылок использовать не номера триад, а непосредственно указатели на них, то изменение ссылок в таком варианте не потребуется.
Содержание работы
В ходе выполнения работы студенты должны выполнить следующие задания
1. Вычислите следующие выражения, записанные в форме обратной польской записи:
a. 1 2 *3 4 5 * + +
b. 1 2 3 4 5 * * + +
c. 1 2 + 3 * 5 + 4 –
d. 1 2 + 3 * 5 4 + -
Напишите для каждого из них выражение в форме инфиксной (обычной) записи.
2. Дана грамматика G({(,),^,&,~,a}, {S, T, E}, P, S):
P:
S 
S^T 
T T&E 
E ~E 
Постройте схему СУ – компиляции выражений входных цепочек языка, заданного этой грамматикой, во внутреннее представление в форме ПОЛИЗ.
|
|
|
3. Для грамматики, приведенной в задаче № 2, постройте схему СУ – перевода во внутреннее представление программы в форме триад. Выполните перевод в форму триад цепочки символов a^a&~a&(a^~~a).
4. Для грамматики, приведенной в задаче № 2, постройте схему СУ – перевода во внутреннее представление программы в форме команд ассемблера. Выполните перевод в ассемблерный код цепочки символов a^a&~a&(a^~~a).
5. Дана последовательность операций:
A:=2;
B:=A*3;
C:=4*3 + 1;
A:=D;
D:=B+C;
C:=A;
B:=A + 4*C + 3*(D + 12);
Преобразуйте ее в форму записи на основе триад. Выполните свертку операций.
6. Дана последовательность операций:
A:=B*C + D*E;
B:=B*C + D*E;
C:=B*C + D*E;
D:=B*C – (D*E +2);
E:=B*C – (D*E +3);
A:=A*E + B*E + 1;
B:=A*E + B*E + 1;
Преобразуйте ее в форму записи на основе триад. Выполните исключение лишних операций.
7. Постройте алгоритм распределения регистров для хранения промежуточных результатов на основе внутреннего представления программы в форме триад.
8. Постройте алгоритм перевода внутреннего представления программы в форме триад в последовательность команд ассемблера.
5. Контрольные вопросы
1. Почему в большинстве компиляторов помимо генерации результирующего объектного кода выполняется еще и его оптимизация? Можно ли построить компилятор, исключив фазу оптимизации?
2. От чего зависит эффективность объектного кода, построенная компилятором?
3. В чем заключается основной принцип СУ-перевода?
4. Почему имеются трудности с оптимизацией выражений, представленных в форме обратной польской записи?
5. Какой из двух основных методов оптимизации, машинно-зависимый или машинно-независимый, может порождать более эффективный результирующий код?
Список литературы
1. Молчанов А.Ю. Системное программное обеспечение: Учебник для вузов – СПб.: Питер, 2006. - 396с.
2. Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум – СПб.: Питер, 2005. - 284с.
3. Свердлов С.З. Языки программирования и методы трансляции: Учебное пособие – СПб.: Питер, 2007. – 638 с.
Составитель СТРОКИНА Юлия Германовна
ОСНОВНЫЕ ЭТАПЫ ТРАНСЛЯЦИИ
Лабораторный практикум
|
|
|
по дисциплине
«Системное программное обеспечение»
Подписано в печать. Формат 60х84 1/16.
Бумага офсетная. Печать плоская. Гарнитура Times New Roman Cyr.
Усл. печ. л. 1,9. Усл.кр.-отт. 1,9.Уч.-изд. л. 1,8.
Тираж 100 экз. Заказ. №
ГОУ ВПО Уфимский государственный авиационный технический университет
Центр оперативной полиграфии УГАТУ
450000, Уфа - центр, ул. К. Маркса, 12
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
Уфимский государственный авиационный технический университет
Кафедра вычислительной техники и защиты информации
ОСНОВНЫЕ ЭТАПЫ ТРАНСЛЯЦИИ
Лабораторный практикум
по дисциплине
«Системное программное обеспечение»
Уфа 2008
|
|
|
