ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 08.04.2021
Просмотров: 503
Скачиваний: 2
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
21
Лабораторная
работа
№
5
Оптимизация
промежуточного
кода
Цель
работы
Изучение
методов
машинно
-
независимых
и
машинно
-
зависимых
методов
оптимизации
кода
и
их
практическое
освоение
на
примере
модуля
оптимизации
промежуточного
кода
транслятора
.
Содержание
работы
Построение
модуля
оптимизации
промежуточного
кода
для
транслятора
программ
.
Задание
Реализовать
оптимизацию
промежуточного
кода
(
свертку
)
за
счет
исключения
триад
,
связанных
с
константными
вычислениями
и
обращениями
к
данным
.
Методические
рекомендации
к
заданию
Оптимизация
программы
при
ее
компиляции
производится
с
целью
улучшения
ее
характеристик
–
уменьшения
объема
используемой
памяти
(
как
для
программы
,
так
и
для
данных
)
или
увеличения
производительности
.
Обычно
достижение
двух
этих
критериев
противоречит
друг
другу
,
а
уменьшение
объема
используемой
памяти
для
кода
программы
часто
вынуждает
использовать
алгоритмы
,
требующие
больш
и
х
массивов
данных
.
Тем
не
менее
,
есть
возможность
улучшения
всех
свойств
программы
за
счет
исключения
«
лишнего
»
кода
.
Оптимизация
может
быть
машинно
-
независимой
и
машинно
-
зависимой
.
В
первом
случае
устраняется
общая
избыточность
кода
,
во
втором
–
используются
особенности
архитектуры
конкретной
вычислительной
системы
для
свертки
последовательностей
инструкций
в
более
компактные
и
/
или
быстрые
.
В
качестве
машинно
-
независимой
оптимизации
необходимо
осуществить
свертку
константных
выражений
до
одной
константы
,
таким
образом
,
значение
константного
выражения
будет
вычислено
во
время
трансляции
.
Свертку
необходимо
выполнять
без
учета
возможных
изменений
значений
переменных
или
их
отсутствия
в
транслируемом
фрагменте
,
т
.
е
.
выражения
,
подлежащие
свертке
,
не
должны
содержать
переменных
.
Таким
образом
,
последовательность
триад
,
соответствующая
загрузке
констант
и
вычислению
значения
константного
выражения
,
будет
свернута
до
одной
триады
загрузки
константы
.
Машинно
-
зависимая
оптимизация
должна
заключаться
в
учете
особенностей
архитектуры
компьютера
,
представленных
в
табл
. 4.1.
Таблица
4.1
Допустимые
режимы
адресации
целевой
машины
Варианты
допустимых
сочетаний
режимов
адресации
Примеры
Тип
операции
Группа
операции
первый
операнд
второй
операнд
триада
ассемблер
Регистровый
–
–(^5,
∅
)
inc R
Непосредственный
–
–(8,
∅
)
cpl Data
Все
,
кроме
пересылки
(
загрузки
)
Прямой
–
–(a,
∅
)
inc (Addr)
Регистровый
–
C(8,
∅
)
mov R, Data
Унарная
Пересылка
(
загрузка
)
Регистровый
–
V(b,
∅
)
mov R, (Addr)
Регистровый
Регистровый
+(^6, ^7)
add R, R
Все
,
кроме
присваивания
Регистровый
Непосредственный
+(^6, 34)
add R, Data
Бинарная
Присваивание
Прямой
Регистровый
=(a, ^4)
mov (Addr), R
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
22
Прямой
режим
адресации
означает
,
что
за
кодом
операции
следует
адрес
,
по
которому
производится
обращение
для
считывания
или
записи
данных
–
эти
данные
и
являются
собственно
операндом
.
При
непосредственном
режиме
адресации
за
кодом
операции
следуют
непосредственно
данные
,
т
.
е
.
значение
операнда
.
Из
таблицы
4.1
видно
,
что
в
данном
компьютере
эти
режимы
не
совмещаются
для
двух
операндов
одной
операции
.
В
реальных
машинах
приемником
результата
обычно
является
один
из
операндов
–
часто
это
регистр
процессора
или
вершина
стека
для
стековой
машины
.
Таким
образом
,
бинарная
операция
становится
не
трех
- (
операнд
1,
операнд
2,
результат
),
а
двухадресной
(
операнд
1
и
он
же
результат
,
операнд
2).
В
отличие
от
инструкций
традиционных
реальных
компьютеров
,
в
триадах
не
указывается
приемник
результата
–
результат
просто
будет
востребован
по
ссылке
на
триаду
.
Поэтому
в
данном
случае
регистровый
режим
адресации
может
также
означать
и
стековый
–
это
зависит
от
типа
конкретной
машины
(
регистровая
,
стековая
)
и
,
следовательно
,
способа
реализации
передачи
результата
одной
операции
для
использования
его
в
качестве
операнда
другой
операцией
(
результат
будет
помещен
либо
в
регистр
,
либо
на
вершину
стека
).
Идентификаторы
(
имена
)
переменных
существуют
только
в
исходном
коде
программы
и
в
ее
записи
в
виде
триад
.
В
машинном
коде
(
непосредственно
в
инструкциях
процессора
)
им
соответствуют
адреса
переменных
.
Поэтому
триаде
обращения
к
переменной
соответствует
,
фактически
,
некоторая
операция
подготовки
адреса
(
актуально
для
некоторых
типов
микропроцессоров
),
а
случаю
прямой
адресации
будет
соответствовать
использование
имени
переменной
в
качестве
операнда
триады
.
Обобщая
эту
информацию
,
получаем
,
что
свертка
может
выполняться
следующим
образом
:
1.
Если
единственный
операнд
унарной
операции
или
второй
(
правый
)
операнд
бинарной
операции
,
кроме
присваивания
,
является
ссылкой
на
триаду
загрузки
константы
,
то
он
заменяется
самой
константой
,
а
соответствующая
триада
загрузки
удаляется
.
2.
Если
единственный
операнд
унарной
операции
является
константой
,
то
вычисляется
соответствующая
операция
,
а
триада
заменяется
на
триаду
загрузки
полученного
значения
.
3.
Если
первый
(
левый
)
операнд
бинарной
операции
,
кроме
присваивания
,
является
ссылкой
на
триаду
загрузки
константы
и
второй
(
правый
)
операнд
–
константой
,
то
вычисляется
соответствующая
операция
и
триада
заменяется
на
триаду
загрузки
полученного
значения
,
а
предшествующая
триада
загрузки
константы
удаляется
.
4.
Если
первый
(
левый
)
операнд
операции
присваивания
является
ссылкой
на
триаду
обращения
к
переменной
,
то
он
заменяется
именем
переменной
,
а
соответствующая
триада
загрузки
удаляется
.
Каждая
триада
в
списке
должна
быть
проанализирована
на
возможность
применения
к
ней
каждого
правила
,
но
для
адекватной
оптимизации
промежуточного
кода
необходима
также
четкая
последовательность
этих
действий
.
Так
как
в
качестве
операндов
могут
фигурировать
ссылки
только
на
предшествующие
триады
,
то
анализировать
список
триад
необходимо
«
сверху
вниз
» –
последовательно
,
от
меньших
номеров
триад
к
большим
.
Каждую
триаду
необходимо
рассматривать
на
возможность
применения
к
ней
правил
в
приведенном
выше
порядке
,
так
как
применение
правила
1
может
повлечь
возможность
применения
правила
2
и
т
.
д
.,
но
не
наоборот
.
Также
следует
обратить
внимание
на
то
,
что
исключить
какую
-
либо
триаду
из
списка
можно
только
тогда
,
когда
на
нее
не
останется
ни
одной
ссылки
.
Учитывая
,
что
в
рамках
данной
работы
не
ставится
задача
оптимизации
общих
подвыражений
,
можно
утверждать
,
что
ссылка
на
каждую
триаду
является
единственной
.
Таким
образом
,
исключать
триады
,
ставшие
«
ненужными
»,
можно
одновременно
с
заменой
ссылки
на
нее
значением
.
При
программной
реализации
рекомендуется
не
исключать
триады
из
списка
,
что
приведет
к
изменению
нумерации
,
а
заменять
их
пустыми
и
пропускать
при
контрольном
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
23
выводе
или
выводе
в
файл
протокола
.
Это
позволит
сохранить
нумерацию
,
что
облегчает
реализацию
алгоритма
,
проверку
его
работоспособности
и
адекватности
.
Работу
алгоритма
можно
проиллюстрировать
на
следующем
примере
:
1)
a = 1;
1:
V(a,
∅
)
// a
2:
C(1,
∅
)
// 1
3:
=(^1, ^2)
// a = 1;
2)
b = (a + 2 * (5 + 7)) * 3;
4:
V(b,
∅
)
// b
5:
V(a,
∅
)
// a
6:
C(2,
∅
)
// 2
7:
C(5,
∅
)
// 5
8:
C(7,
∅
)
// 7
9:
+(^7, ^8)
// 5 + 7
10:
×
(^6, ^9)
// 2 * (5 + 7)
11:
+(^5, ^10)
// a + 2 * (5 + 7)
12:
C(3,
∅
)
// 3
13:
×
(^11, ^12) // (a + 2 * (5 + 7)) * 3
14:
=(^4, ^13)
// b = (a + 2 * (5 + 7)) * 3;
В
табл
. 4.2
приведен
список
триад
,
соответствующий
приведенным
операторам
,
и
показаны
шаги
,
на
которых
выполняется
свертка
.
В
списке
триад
выделены
те
операнды
и
триады
,
которые
подлежат
свертке
,
а
в
нижней
строке
указан
номер
применяемого
правила
.
Таблица
4.1
Допустимые
режимы
адресации
целевой
машины
Шаг
1
Шаг
2
Шаг
3
Шаг
4
Шаг
5
Шаг
6
Шаг
7
Шаг
8
Шаг
9
1
V(a,
∅
∅
∅
∅
)
2
C(1,
∅
)
C(1,
∅
)
C(1,
∅
)
C(1,
∅
)
C(1,
∅
)
C(1,
∅
)
C(1,
∅
)
C(1,
∅
)
C(1,
∅
)
3 =(
^1
, ^2)
=(a, ^2)
=(a, ^2)
=(a, ^2)
=(a, ^2)
=(a, ^2)
=(a, ^2)
=(a, ^2)
=(a, ^2)
4
V(b,
∅
)
V(b,
∅
)
V(b,
∅
)
V(b,
∅
)
V(b,
∅
)
V(b,
∅
)
V(b,
∅
)
V(b,
∅
)
V(b,
∅
)
5
V(a,
∅
)
V(a,
∅
)
V(a,
∅
)
V(a,
∅
)
V(a,
∅
)
V(a,
∅
)
V(a,
∅
)
V(a,
∅
∅
∅
∅
)
6
C(2,
∅
)
C(2,
∅
)
C(2,
∅
)
C(2,
∅
)
C(2,
∅
∅
∅
∅
)
7
C(5,
∅
)
C(5,
∅
)
C(5,
∅
∅
∅
∅
)
8
C(7,
∅
)
C(7,
∅
∅
∅
∅
)
9 +(^7, ^8) +(^7,
^8
)
+(
^7
, 7)
C(12,
∅
∅
∅
∅
)
10
×
(^6, ^9)
×
(^6, ^9)
×
(^6, ^9)
×
(^6,
^9
)
×
(
^6
, 12)
C(24,
∅
∅
∅
∅
)
11 +(^5, ^10) +(^5, ^10) +(^5, ^10) +(^5, ^10) +(^5, ^10) +(^5,
^10
) +(^5, 24) +(^5, 24) +(^5, 24)
12 C(3,
∅
)
C(3,
∅
)
C(3,
∅
)
C(3,
∅
)
C(3,
∅
)
C(3,
∅
)
C(3,
∅
∅
∅
∅
)
13
×
(^11,^12)
×
(^11,^12)
×
(^11,^12)
×
(^11,^12)
×
(^11,^12)
×
(^11,^12)
×
(^11,
^12
)
×
(^11, 3)
×
(^11, 3)
14 =(^4, ^13) =(^4, ^13) =(^4, ^13) =(^4, ^13) =(^4, ^13) =(^4, ^13) =(^4, ^13) =(
^4
, ^13) =(a, ^13)
4
1
3
1
3
1
1
4
–
Программная
реализация
должна
быть
выполнена
на
основе
транслятора
,
созданного
в
предыдущей
лабораторной
работе
.
Трансляция
в
промежуточный
код
и
его
оптимизация
должны
представлять
собой
два
этапа
,
выполняемых
строго
последовательно
,
а
передача
информации
между
ними
–
посредством
внутреннего
представления
списка
триад
(
не
через
файл
протокола
).
Оптимизированный
промежуточный
код
желательно
помещать
в
тот
же
файл
протокола
,
вслед
за
исходным
.
В
основной
части
отчета
необходимо
отразить
разработанный
алгоритм
оптимизации
промежуточного
кода
и
протоколы
работы
усовершенствованного
транслятора
.
Выводы
по
работе
должны
содержать
обоснование
адекватности
реализованного
алгоритма
.
Теория
языков
программирования
и
методы
трансляции
©
Кафедра
АиКС
,
СурГУ
, 2010
24
Список
рекомендуемой
литературы
Основная
литература
1.
Молчанов
,
А
.
Ю
.
Системное
программное
обеспечение
:
учебник
для
студентов
вузов
/
А
.
Ю
.
Молчанов
. –
СПб
.:
Питер
, 2003. – 395
с
.
2.
Гордеев
,
А
.
В
.
Системное
программное
обеспечение
:
учебник
для
студентов
вузов
/
А
.
В
.
Гордеев
,
А
.
Ю
.
Молчанов
. –
СПб
.:
Питер
, 2002. – 736
с
.
3.
Опалева
,
Э
.
А
.
Языки
программирования
и
методы
трансляции
/
Э
.
А
.
Опалева
,
В
.
П
.
Самойленко
. –
СПб
.:
БХВ
-
Петербург
, 2005. – 476
с
.
4.
Пратт
,
Т
.
Языки
программирования
:
разработка
и
реализация
/
Т
.
Пратт
,
М
.
Зелковиц
;
Под
общей
ред
.
А
.
Матросова
. –
СПб
.:
Питер
, 2002. – 688
с
.
5.
Карпов
,
Ю
.
Г
.
Основы
построения
трансляторов
:
теория
и
технология
программирования
:
учебное
пособие
для
студентов
вузов
/
Ю
.
Г
.
Карпов
. –
СПб
.:
БХВ
-
Петербург
, 2005. – 270
с
.
Дополнительная
литература
6.
Ахо
,
А
.
Теория
синтаксического
анализа
,
перевода
и
компиляции
/
А
.
Ахо
,
Дж
.
Ульман
. –
т
. 1, 2. –
М
.:
Мир
, 1978.
7.
Грис
,
Д
.
Конструирование
компиляторов
для
цифровых
вычислительных
машин
/
Д
.
Грис
. –
М
.:
Мир
, 1975.
8.
Вайнгартен
,
Ф
.
Трансляция
языков
программирования
/
Ф
.
Вайнгартен
. –
М
.:
Мир
,
1977. – 190
с
.
9.
Карпов
,
Ю
.
Г
.
Теория
автоматов
:
учебник
для
вузов
/
Ю
.
Г
.
Карпов
. –
СПб
.:
Питер
,
2002. – 208
с
.
10.
Фридл
,
Дж
.
Регулярные
выражения
:
библиотека
программиста
/
Дж
.
Фридл
. – 2-
е
изд
.
–
СПб
.:
Питер
, 2003. – 464
с
.
11.
Новиков
,
Ф
.
А
.
Дискретная
математика
для
программистов
:
учебник
для
вузов
/
Ф
.
А
.
Новиков
. –
СПб
.:
Питер
, 2001. – 304
с
.
12.
Элджер
,
Дж
. C++:
библиотека
программиста
/
Дж
.
Элджер
. –
СПб
.:
Питер
, 2001. –
320
с
.
13.
Бентли
,
Д
.
Жемчужины
программирования
:
библиотека
программиста
/
Д
.
Бентли
. – 2
изд
. –
СПб
.:
Питер
, 2002. – 272
с
.