Содержание

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.Элементы топологии программы


Информация о работе «Оптимизация программ»
Раздел: Информатика, программирование
Количество знаков с пробелами: 36941
Количество таблиц: 0
Количество изображений: 0

Похожие работы

Скачать
29567
28
0

... ; i=1,3. Q – количество сырья Для автоматизированной обработки данных и вычислений используется пакет программ линейной оптимизации программного продукта Microsoft Excel. Решение Определяем оптимальные производственные мощности филиалов для производства определенного количества продукции различных видов с помощью транспортной задачи. Постановка транспортной задачи. Требуется определить ...

Скачать
82492
2
0

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

Скачать
6526
0
0

... заданных операндов. 3)  Использование косвенной адресации, когда операнд хранит адрес операнда. 4)  Ограничение использования стека. программа оптимизация ассемблер код 4. Машинно-независимая оптимизация кода ассемблера Машинно-независимая оптимизация предполагает: 1. Одним из важнейших источников оптимизации кода является удаление общих подвыражений, т.е. подвыражений, которые ...

Скачать
74118
11
4

... лишь контекстным анализом. Как было отмечено в [12], применение глубокого статического анализа программ может позволить существенно снизить количество ложных срабатываний и повысить точность обнаружения уязвимостей защиты. 4.3. Использование методов анализа потоков данных для решения задачи обнаружения уязвимостей В отделе компиляторных технологий по контракту с фирмой Nortel Networks ...

0 комментариев


Наверх