Дипломная работа на тему: Значение и цели оптимизации. Промежуточный язык. Элементы топологии программы

Введение

Различают две категории оптимизирующих преобразований: преобразования исходной программы в ее внутренней форме, которые не зависят от объектного языка (машинно-независимые) и преобразования, осуществляемые на уровне объектной программы (машинно-ориентированные).

Методы первой категории применимы почти к любому алгебраическому языку - ФОРТРАНу, АЛГОЛу, РL/1 и.т.д.

На практике используется весьма широкий набор машинно-независимых оптимизирующих преобразований, что связано с большим разнообразием неоптимальностей. К ним относятся:

Оглавление

- Назначение и цели оптимизации

- Промежуточный язык

- Элементы топологии программы

- Блок линейный участок

- Сильно связанная область

- Способы оптимизации

- Разгрузка участков повторяемости

- Сдвиг инвариантных операторов

- Сокращение глубины операции

- Упрощение действий

- Удаление индуктивных переменных и выражений

- Замена сложных операций на более простые

- Исключение избыточных выражений

- Прочие преобразования

- Реализация действий

- Подстановка свертка

- Чистка программы

- Устранение идентичных операторов

- Замена переменных в операторах условного перехода и устранение неиспользуемых определений

- Устранение бесполезных операторов и переменных

- Экономия памяти

- Сокращение программы

- Вставка псевдоблока

- Последовательность применения оптимизирующих преобразований

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

- оптимизирующей частью транслятора

- Оптимизирующая часть транслятора выполняет следующие

- действия

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

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

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

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

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

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

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

- Строго сформулировать требования, предъявляемые к промежуточному языку, трудно. Однако уже из самого обоснования необходимости промежуточного языка видно, что

- а операторы языка не должны быть слишком мелкими

- б символы, идентификаторы и числа должны иметь фиксированный формат

- в в строении операторов желательно отсутствие рекурсивности

- г должна сохраняться вся информация, необходимая для оптимизации, которая есть во входном языке

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

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

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

- mi код операции аргументы оператора,

- где mi - указатель оператора, а также идентификатор результата команды при отсутствии его присваивания некоторой переменной

- Необходимо различать переменные, введенные программистом программные переменные,и переменные, генерируемые в процессе

- трансляции на промежуточный язык mi - идентификаторы. Между

- определением программной переменной и ее использованием в качестве операнда существует следующая зависимость

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

- если программная переменная определена и используется в области, то внутри области существует путь между определением переменной и каждым ее использованием

- если программная переменная определена в области, то, вообще говоря, это не значит, что она определена на каждом выходном пути

- Помимо программы на промежуточном языке, состоящей из последовательности операторов, для проведения оптимизации формируются следующие таблицы

- Таблицы идентификаторов и констант с обычной информацией о переменных и константах

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

- Таблица последовательности операторов, определяющая линейную последовательность операторов в блоке. Она содержит последовательность указателей операторов mi. Эта таблица необходима, поскольку один указатель может принадлежать нескольким операторам

- Элементы топологии программы

- Блок линейный участок Вопросы оптимизации обычно связаны с топологией программы, т.е. со способом ее построения. Для того, чтобы локализовать процессы оптимизации и не связывать их с конкретным входным языком, они проводятся внутри отдельных участков программы, называемых блоками и сильно связанными областями

- Блок линейный участок - выполняемая по порядку последовательность операторов, имеющая единственную точку входа - первый оператор с меткой, на который может быть передано управление, и единственную точку выхода - последний оператор

- Блок моделирует часть программы на промежуточном языке, которая содержит операторы присваивания

- Формально модель линейного участка может быть представлена следующим образом

- блок В - это тройка вида Р,I,U,где

- 1 Р - список операторов S1,S2,...Sn n0,

- 2 I - множество входных переменных,

- 3 U - множество выходных переменных

- При этом оператором называется цепочка в общем случае вида

- А --qb1...вr,

- где А,В1,...,Вr - переменные,Q - операция

- Здесь оператор присваивает значение переменной А и ссылается на В1,...,Вr

- Если оператор Sj ссылается на А, то либо А--входная переменная, либо осуществлено присваивание ей значения некоторым оператором до Sj, т. е. некоторым оператором Si,ij . Таким образом, внутри ,блока все переменные, на которые ссылаются, к этому моменту определены либо внутренним образом как переменные, которым присвоены значения, либо внешним как входные переменные. Аналогично каждая выходная переменная либо является входной переменной, либо ей присвоено значение некоторым оператором

- Оператор S в программе называется входом в линейный участок, если он либо первый оператор в программе, либо помечен идентификатором, появляющимся в операторе перехода, либо непосредственно следует за условным оператором

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

- Сильно связанная область

- Для каждого блока ВР,I,U можно найти ориентированный ациклический граф , представляющий этот блок. При этом каждый лист графа концевая вершина соответствует одной входной переменной в I, а каждая его внутренняя вершина - оператору из

- Р. Граф отражает порядок выполнения операторов программы и дает более наглядное представление, чем линейная последовательность операторов

- Если вершины i и j графа соответствуют участкам i и j программы, то дуга идет из i в j, если

- последний оператор участка i не является ни оператором перехода, ни оператором останова, а участок j следует в программе за участком i или

- последний оператор участка i является оператором перехода на метку L, которой помечен первый оператор участка j

- Сильно связанной областью направленного графа называется такое множество его вершин, что для любых двух вершин x и y x y существует путь из x в y

- Будем рассматривать сильно связанные области Ri, обладающие следующими свойствами

- 1 Ri является сильносвязанной областью, состоящей из множества блоков, каждый из которых предшествует сам себе и следует сам за собой внутри этого множества