Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Свертка




Оптимизация внутри линейных участков

Оптимизация

Оптимизацией называется обработка, связанная с переупорядочиванием и изменением операций в компилируемой программе в целях получения более эффективного объектного кода. Обычно выделяют машинно-зависимую и машинно-независимую оптимизацию. Под машинно-зависимой оптимизацией понимается преобразование исходной программы в ее внутреннем представлении, что означает полную независимость от выходного языка, в отличие от машинно-зависимой, выполняемой на уровне объектной программы.

Среди машинно-независимых методов можно выделить самые основные:

- Свертка, т.е. выполнение операций, операнды которых известны во время компиляции..

- Исключение лишних операций за счет однократного программирования общих подвыражений.

- Вынесение из цикла операций, операнды которых не изменяются внутри цикла.

Линейным участком является выполняемая по порядку последовательность операций с одним входом и одним выходом (первая и последняя операции соответственно). Например, последовательность операций представленных ниже образуют линейный участок.

I:=1+1;

I:=3;

B:=7+I;

Внутри линейного участка обычно проводят две оптимизации: свертку и устранение лишних операций.

Свертка – это выполнение во время компиляции операций исходной программы, для которых значения операндов уже известны, и, поэтому, нет нужды их выполнять во время счета. Например, внутреннее представление в виде триад линейного участка программы представленного выше изображено ниже.

(1) + 1,1

(2):= I,(1)

(3):= I,3

(4) + 7,(3)

(5):= B,(4)

Видно, что первую триаду можно вычислить во время компиляции и заменить результирующей константой. Менее очевидно, что четвертую триаду также можно вычислить, т.к. к моменту ее обработки известно, что I равно 3. Полученный после свертки результат

(1):= I,2

(2):= I,3

(3):= B,10

Главным образом свертка применяется к арифметическим операциям, так как они наиболее часто встречаются в исходной программе. Кроме того, она применяется к операторам преобразования типа. Причем проблема упрощается, если эти преобразования заданы явно, а не подразумеваются по умолчанию.

Процесс свертки операторов, имеющих в качестве операндов константы, понятен и сводится к внутреннему их вычислению. Свертка операторов, значения которых могут быть определены в результате некоторого анализа, несколько сложнее. Обычно свертку осуществляют только в пределах линейного участка при помощи таблицы Т, вначале пустой, содержащей пары (К, А), где А – простая переменная для которой известно текущее значение К. Кроме того, каждая свертываемая триада заменяется новой триадой (С, К, 0), где С (константа) – новый оператор, для которого не надо генерировать команды, а К – результирующее значение свернутой триады. Алгоритм

свертки последовательно просматривает триады линейного участка.Пример работы данного алгоритма приведен в таблице 1.

Таблица 1 - Последовательность шагов алгоритма свертки

  Шаг 1 Шаг 2 Шаг 3 Шаг 4 Шаг 5
1 + 1,1 С 2 С 2 С 2 С 2
2 := I,(1) := I,(1) := I,2 := I,2 := I,(1)
3 := I,3 := I,3 := I,3 := I,3 := I,3
4 + 7,(3) + 7,(3) + 7,(3) C 10 C 10
5 := B,(4) := B,(4) := B,(4) := B,(4) := B,10
Т     (I,2) (I,3) (I,3)
Т         (B,10)

С точки зрения работы компилятора процесс свертки является дополнительным проходом по внутреннему представлению исходной программы представленной триадами. Но свертку можно проводить и с тетрадами. Кроме того, можно оптимизировать программу в семантических программах во время получения внутреннего представления и при этом отпадает необходимость в дополнительном проходе. Например, для выражения

A:=B+C

при восходящем грамматическом разборе программа должна выполнить только одну дополнительную проверку семантик B и С. Если они константы или их значения известны, то программа их складывает, и результат связывает с А. В данном случае можно использовать таблицу переменных с известными значениями, которая должна сбрасываться в местах генерации команд передачи управления.




Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 613; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.008 сек.