Содержание
1.Назначение и цели оптимизации
2.Промежуточный язык
3.Элементы топологии программы
3.1. Блок (линейный участок)
3.2. Сильно связанная область
4.Способы оптимизации
4.1. Разгрузка участков повторяемости
4.1.1 Сдвиг инвариантных операторов
4.1.2. Сокращение глубины операции
4.2. Упрощение действий
4.2.1. Удаление индуктивных переменных и выражений
4.2.2. Замена сложных операций на более простые
4.2.3. Исключение избыточных выражений
4.2.4. Прочие преобразования
4.3. Реализация действий
4.3.1. Подстановка (свертка)
4.4. Чистка программы
4.4.1. Устранение идентичных операторов
4.4.2. Замена переменных в операторах условного перехода и устранение неиспользуемых определений
4.4.3 Устранение бесполезных операторов и переменных
4.5. Экономия памяти
4.6. Сокращение программы
4.7. Вставка псевдоблока
5.Последовательность применения оптимизирующих преобразований
1. Назначение и цели оптимизации
Всегда желательно иметь компилятор, который создает эффективно работающие объектные программы. Как правило, программа в кодах машины, полученная в результате трансляции, будет занимать больший объем памяти и работать медленнее, чем такая же программа, написанная опытным программистом. Термин "оптимизация" применяется к попыткам сделать выходные программы более "эффективными", т.е. быстрее работающими или более компактными. Таким образом, оптимизацией называется улучшение выходной программы, а часть транслятора, выполняющая эту функцию
- оптимизирующей частью транслятора.
Оптимизирующая часть транслятора выполняет следующие
действия:
1. Устраняет недостатки программы,вызванные небрежностью или низкой квалификацией программиста. Примером может служить вынесение из цикла операторов, не зависящих от управляющих переменных цикла, что приведет к сокращению времени выполнения программы, поскольку вынесенные операторы будут выполняться только один раз, а не многократно.
2. Устраняет излишние вычисления, неизбежно возникающие в процессе трансляции даже при самом тщательном написании программы на языке высокого уровня. Например, устранение повторного вычисления индексных выражений для элементов массива сокращает время выполнения программы и ее длину.
2. Промежуточный язык
Для повышения эффективности программы можно произвести над ней последовательность преобразований в различные моменты процесса компиляции. Например, можно оперировать с входной программой, со структурами, порождаемыми на стадии синтаксического анализа, с кодом, порождаемым в качестве выхода фазы генерации кода. Однако оптимизировать программу, уже протранслированную в коды машины, трудно по следующим причинам:
во-первых, единицы действия программы в кодах команд слишком мелки, что уже само по себе затрудняет анализ,
во-вторых, при трансляции входной программы в коды машины возможна потеря имеющейся в ней информации. Например, засылка промежуточных результатов в разные рабочие ячейки памяти делает практически невозможной идентификацию одинаковых частей программы;
в-третьих из-за нестандартности форматов различных элементов языка и рекурсивных конструкций, широко применяемых в текстах программ.
Поэтому,если транслятор производит оптимизацию программы, необходимо делать специальный проход, переводящий программу с исходного языка на промежуточный.
Строго сформулировать требования, предъявляемые к промежуточному языку, трудно. Однако уже из самого обоснования необходимости промежуточного языка видно, что:
а) операторы языка не должны быть слишком мелкими;
б) символы, идентификаторы и числа должны иметь фиксированный формат;
в) в строении операторов желательно отсутствие рекурсивности;
г) должна сохраняться вся информация, необходимая для оптимизации, которая есть во входном языке;
д) язык должен быть приспособлен к выполнению оптимизирующих преобразований и удобен для последующей трансляции в коды вычислительной машины.
Требования пп. "г" и "д" показывают, что разработать единый универсальный промежуточный язык для трансляции с любого языка программирования в коды любой вычислительной машины трудно. В качестве промежуточного языка можно использовать польскую запись, тетрады, триады, синтаксические деревья.
При рассмотрении вопросов оптимизации будем считать, что программа протранслирована с входного на некоторый промежуточный язык, оператор которого имеет следующий общий вид:
(mi) код операции аргументы оператора,
где mi - указатель оператора, а также идентификатор результата команды при отсутствии его присваивания некоторой переменной.
Необходимо различать переменные, введенные программистом (программные переменные),и переменные, генерируемые в процессе
трансляции на промежуточный язык (mi - идентификаторы). Между
определением программной переменной и ее использованием в качестве операнда существует следующая зависимость:
- если программная переменная, используемая в области, не определена в ней, то предполагается, что она определена во всех путях, ведущих к области;
- если программная переменная определена и используется в области, то внутри области существует путь между определением переменной и каждым ее использованием;
- если программная переменная определена в области, то, вообще говоря, это не значит, что она определена на каждом выходном пути.
Помимо программы на промежуточном языке, состоящей из последовательности операторов, для проведения оптимизации формируются следующие таблицы:
1. Таблицы идентификаторов и констант с обычной информацией о переменных и константах.
2. Таблица блоков, определяющая номера блоков (блоки нуме-
руются в произвольном порядке), их границы, непосредственно предшествующие и следующие блоки, а также любую информацию о частоте повторения блока.
3. Таблица последовательности операторов, определяющая линейную последовательность операторов в блоке. Она содержит последовательность указателей операторов mi. Эта таблица необходима, поскольку один указатель может принадлежать нескольким операторам.
3.Элементы топологии программы
3.1. Блок (линейный участок)
Вопросы оптимизации обычно связаны с топологией программы, т.е. со способом ее построения. Для того, чтобы локализовать процессы оптимизации и не связывать их с конкретным входным языком, они проводятся внутри отдельных участков программы, называемых блоками и сильно связанными областями.
Блок (линейный участок) - выполняемая по порядку последовательность операторов, имеющая единственную точку входа - первый оператор с меткой, на который может быть передано управление, и единственную точку выхода - последний оператор.
Блок моделирует часть программы на промежуточном языке, которая содержит операторы присваивания.
Формально модель линейного участка может быть представлена следующим образом:
блок B - это тройка вида (P,I,U),где
(1) P - список операторов S1,S2,...Sn (n>=0),
(2) I - множество входных переменных,
(3) U - множество выходных переменных.
При этом оператором называется цепочка (в общем случае) вида
A <--QB1...Br,
где A,B1,...,Br - переменные,Q - операция.
Здесь оператор присваивает значение переменной А и ссылается на B1,...,Br.
Если оператор Sj ссылается на А, то либо А--входная переменная, либо осуществлено присваивание ей значения некоторым оператором до Sj, (т. е. некоторым оператором Si,(i<j) . Таким образом, внутри ,блока все переменные, на которые ссылаются, к этому моменту определены либо внутренним образом как переменные, которым присвоены значения, либо внешним как входные переменные. Аналогично каждая выходная переменная либо является входной переменной, либо ей присвоено значение некоторым оператором.
Оператор S в программе называется входом в линейный участок, если он либо первый оператор в программе, либо помечен идентификатором, появляющимся в операторе перехода, либо непосредственно следует за условным оператором.
Линейный участок, относящийся к входу в участок S, состоит из S и всех операторов, следующих за ним вплоть до оператора останова, включая его, или вплоть до входа в следующий блок.
3.2. Сильно связанная область
Для каждого блока B=(P,I,U) можно найти ориентированный ациклический граф , представляющий этот блок. При этом каждый лист графа (концевая вершина) соответствует одной входной переменной в I, а каждая его внутренняя вершина - оператору из
P. Граф отражает порядок выполнения операторов программы и дает более наглядное представление, чем линейная последовательность операторов.
Если вершины i и j графа соответствуют участкам i и j программы, то дуга идет из i в j, если
1) последний оператор участка i не является ни оператором перехода, ни оператором останова, а участок j следует в программе за участком i или
2) последний оператор участка i является оператором перехода на метку L, которой помечен первый оператор участка j.
Сильно связанной областью направленного графа называется такое множество его вершин, что для любых двух вершин x и y (x != y) существует путь из x в y.
Будем рассматривать сильно связанные области Ri, обладающие следующими свойствами:
1) Ri является сильносвязанной областью, состоящей из множества блоков, каждый из которых предшествует сам себе и следует сам за собой внутри этого множества;
2) Ri != Rj;
3) для каждого i<j или пересечение Ri и Rj пусто, или Ri является подобластью Rj (включена в нее).
4. Способы оптимизации
Различают две категории оптимизирующих преобразований: преобразования исходной программы в ее внутренней форме, которые не зависят от объектного языка (машинно-независимые) и преобразования, осуществляемые на уровне объектной программы (машинно-ориентированные).