Реферат: Оптимизация программ
2. Устраняет излишние вычисления, неизбежно возникающие в процессе трансляции даже при самом тщательном написании программы на языке высокого уровня. Например, устранение повторного вычисления индексных выражений для элементов массива сокращает время выполнения программы и ее длину.
2. Промежуточный язык
Для повышения эффективности программы можно произвести над ней последовательность преобразований в различные моменты процесса компиляции. Например, можно оперировать с входной программой, со структурами, порождаемыми на стадии синтаксического анализа, с кодом, порождаемым в качестве выхода фазы генерации кода. Однако оптимизировать программу, уже протранслированную в коды машины, трудно по следующим причинам:
во-первых, единицы действия программы в кодах команд слишком мелки, что уже само по себе затрудняет анализ,
во-вторых, при трансляции входной программы в коды машины возможна потеря имеющейся в ней информации. Например, засылка промежуточных результатов в разные рабочие ячейки памяти делает практически невозможной идентификацию одинаковых частей программы;
в-третьих из-за нестандартности форматов различных элементов языка и рекурсивных конструкций, широко применяемых в текстах программ.
Поэтому,если транслятор производит оптимизацию программы, необходимо делать специальный проход, переводящий программу с исходного языка на промежуточный.
Строго сформулировать требования, предъявляемые к промежуточному языку, трудно. Однако уже из самого обоснования необходимости промежуточного языка видно, что:
а) операторы языка не должны быть слишком мелкими;
б) символы, идентификаторы и числа должны иметь фиксированный формат;
в) в строении операторов желательно отсутствие рекурсивности;
г) должна сохраняться вся информация, необходимая для оптимизации, которая есть во входном языке;
д) язык должен быть приспособлен к выполнению оптимизирующих преобразований и удобен для последующей трансляции в коды вычислительной машины.
Требования пп. "г" и "д" показывают, что разработать единый универсальный промежуточный язык для трансляции с любого языка программирования в коды любой вычислительной машины трудно. В качестве промежуточного языка можно использовать польскую запись, тетрады, триады, синтаксические деревья.
При рассмотрении вопросов оптимизации будем считать, что программа протранслирована с входного на некоторый промежуточный язык, оператор которого имеет следующий общий вид:
(mi) код операции аргументы оператора,
где mi - указатель оператора, а также идентификатор результата команды при отсутствии его присваивания некоторой переменной.
Необходимо различать переменные, введенные программистом (программные переменные),и переменные, генерируемые в процессе
трансляции на промежуточный язык (mi - идентификаторы). Между
определением программной переменной и ее использованием в качестве операнда существует следующая зависимость:
- если программная переменная, используемая в области, не определена в ней, то предполагается, что она определена во всех путях, ведущих к области;
- если программная переменная определена и используется в области, то внутри области существует путь между определением переменной и каждым ее использованием;
- если программная переменная определена в области, то, вообще говоря, это не значит, что она определена на каждом выходном пути.
Помимо программы на промежуточном языке, состоящей из последовательности операторов, для проведения оптимизации формируются следующие таблицы:
1. Таблицы идентификаторов и констант с обычной информацией о переменных и константах.
2. Таблица блоков, определяющая номера блоков (блоки нуме-
руются в произвольном порядке), их границы, непосредственно предшествующие и следующие блоки, а также любую информацию о частоте повторения блока.
3. Таблица последовательности операторов, определяющая линейную последовательность операторов в блоке. Она содержит последовательность указателей операторов mi. Эта таблица необходима, поскольку один указатель может принадлежать нескольким операторам.
3.Элементы топологии программы
3.1. Блок (линейный участок)