Свертка
Оптимизация внутри линейных участков
Оптимизация
Оптимизацией называется обработка, связанная с переупорядочиванием и изменением операций в компилируемой программе в целях получения более эффективного объектного кода. Обычно выделяют машинно-зависимую и машинно-независимую оптимизацию. Под машинно-зависимой оптимизацией понимается преобразование исходной программы в ее внутреннем представлении, что означает полную независимость от выходного языка, в отличие от машинно-зависимой, выполняемой на уровне объектной программы.
Среди машинно-независимых методов можно выделить самые основные:
- Свертка, т.е. выполнение операций, операнды которых известны во время компиляции..
- Исключение лишних операций за счет однократного программирования общих подвыражений.
- Вынесение из цикла операций, операнды которых не изменяются внутри цикла.
Линейным участком является выполняемая по порядку последовательность операций с одним входом и одним выходом (первая и последняя операции соответственно). Например, последовательность операций представленных ниже образуют линейный участок.
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 и С. Если они константы или их значения известны, то программа их складывает, и результат связывает с А. В данном случае можно использовать таблицу переменных с известными значениями, которая должна сбрасываться в местах генерации команд передачи управления.