Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Исключение лишних операций




Алгоритм исключения лишних операций просматривает операции в порядке их следования. Так же как и алгоритм свертки, алгоритму исключения лишних операций проще работать с триадами, потому что они полностью отражают взаимосвязь операций.

Рассмотрим алгоритм исключения лишних операций для триад.

Чтобы следить за внутренней зависимостью переменных и триад, алгоритм присваивает им некоторые значения, называемые числами зависимости, по следующим правилам:

· изначально для каждой переменной ее число зависимости равно 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

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...