Компиляторы. Оптимизация кода.

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

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

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

программы. Среди машинно-независимых методов можно выделить основные:

- свертка, т. е. выполнение операций, операнды которых известны вовремя компиляции;

- исключение лишних операций за счет однократного

программирования общих подвыражений;

- вынесение из цикла операций, операнды которых не изменяются внутри цикла.

Линейным участком является выполняемая по порядку

последовательность операций с одним входом и одним выходом (первая и последняя операции соответственно). Например, последовательность операций представленных ниже образуют линейный участок:

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), здесь С

(константа) – новый оператор, для которого не надо генерировать команды, К – результирующее значение свернутой триады. Алгоритм свертки последовательно просматривает триады линейного

участка. Пример работы данного алгоритма приведен в табл. 2.2.

С точки зрения работы компилятора, процесс свертки является дополнительным проходом по внутреннему представлению исходной программы, представленной триадами.  Но свертку можно проводить и с тетрадами. Кроме того, можно оптимизировать программу в семантических программах во время получения внутреннего представления; при этом пропадет необходимость в дополнительном проходе. Например, для выражения A:=B+C при восходящем грамматическом разборе программа должна выполнить только одну дополнительную проверку семантик B и С. Если они константы или их значения известны, то программа их складывает и связывает результат с А. В данном случае можно использовать таблицу переменных с известными значениями, которая должна сбрасываться в местах

генерации команд передачи управления. Исключение лишних операций – i-я операция линейного участка

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

операцией, лежащей между i-й и j-й операциями. Например, на линейном участке

D:=D+C*B;

A:=D+C*B;

можно выделить лишние операции. Если представить линейный участок в виде триад, то можно отметить, что операция C*B лишняя (во втором случае):

(1) * С,B

(2) + D,(1)

(3) := D,(2)

(4) * C,B

(5) + D,(4)

(6) := A,(5)

Лишней триада (4) является из-за того, что ни С ни В не изменяются после триады (1). Однако триада (5) лишней не является, так как после первого сложения D с C*B триада (3) изменяет значение D.

Алгоритм исключения лишних операций просматривает операции в порядке их появления. И если i-я триада лишняя, так как уже имеется идентичная ей j-я триада, то она заменяется триадой (SAME, j, 0), где операция

SAME ничего не делает и не порождает никаких команд при генерации. Для отслеживания внутренней зависимости переменных и триад можно

поставить им в соответствие числа зависимостей (dependency numbers). В этом случае используются следующие правила:

- для переменной А число зависимости dep(А) выбирается равным нулю, так как ее значение не зависит ни от одной триады;

- после обработки i-й триады, где переменной А присваивается какое- либо значение, число зависимости становится равным i, так как ее новое значение зависит от i-й триады;

- при обработке i-й триады число зависимостей dep(i) становится равным максимальному из чисел зависимостей ее операндов + 1.

Числа зависимостей используются следующим образом: если i-я триада идентична j-й триаде (j<i), то i-я триада является лишней тогда и только тогда,

когда dep(i)=dep(j).

 

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

Компоновщик

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

1.Сбор всех модулей из библиотек пользователей и системных библиотек.

2.Установка всех внешних ссылок м/д модулями.

3.Собщение о неопределенных ссылках.

4.Конструирование структуры оверлея.

5.Определение и построение загрузочного модуля

Главная задача программы компоновщика создать комплекс объект. модулей, полученных от компиляторов с различных языков в какой-нибудь из разновидностей исполняемых модулей и заменить неопределенные ссылки на внешние имена с соответствующими адресами или информацией доступной для загрузчиков. Классификация типов связей разграничивает 2 класса: управляющие и информационные. Для реализации которых используется единый технический подход, опирающийся на глобально-доступные имена элементов программных модулей. Управляющие связи в современных системах программирования определяются способами передачи управления и действиями, выполняемыми для решения частей общей задачи и представленные в одной из шести форм:

1.Вызов подпрограммы того же загрузочного модуля в процессе его выполнения, реализуемого простыми средствами модульного программирования.

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

3.Вызов подпрограммы, копия которой имеется в основной программе и который обычно реализуется в форме обращения к общей системной программе ОС или управляющей надстройке пользователя.

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

5.Динамический вызов параллельных процессов решения подзадач включая выполнение ехе-модули и dll-модули, которые подключаются на этапе выполнения.

6.Передача сообщения и сигналов автономным параллельным процессам и задачам широко применяемым для управления вычислениями в объектно-ориентированных оболочках.

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

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

2.Возрат результатов при вызове функций, при котором соблюдают стандарт. связанный с ЯП.

3.Использование глобальных областей памяти для обмена данными между подпрограммами и задачами.

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

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

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

2. как проверить корректность типов данных при обращении к подпрограммам и задачам?

3. как достигается переместимость объект. программы, т.е. возможность размещать ее в любом месте ОП?

4. как и почему компонуются отдельные логические сегменты в единый физический сегмент?

Объединение логических сегментов требует корректировки относительного адреса в уже сформированный коде путем добавления относительного смещения смещения начала логического сегмента для переместимых адресов. В случае использования внешних имен условный код указателя заменяется конкретным адресом соответственного объекта. Многообразие объектов переместимости, а иногда и использование разных кодов для внутреннего представления типов переместимости делают несовместимыми объектные коды, получаемые от трансляторов разных фирм или даже разных систем программирования одной фирмы. В модульном программировании различают связи по управлению и по данным, реализуемые с помощью адресных указателей или ссылок на данные и коды. При объедении модулей необходимо определить имена областей памяти и фрагментов программ, используемых в др модулей в списке операндов оператора public, внешние имена из других модулей вместе с их типами описываются в списке операндов оператора extended. Для указателей используются только ключевые слова word и dword, т.е. указатели в ассемблере нетипизированы. При обращении к подпрограммам и функциям по прямым адресам используются типы near и far. Передача параметров в форме непосредственных значений или адресных указателей осуществляются через стек. Необходимость проверки соответствия типов данных, аргументов, процедур и функций, а также числа аргументов в процедурах, существенно усложняет представления словаря внешних ссылокв объектных файлах. Компоновщики используют программные модули, хранящие информацию об именах исходных модулей программы, типе компилятора породившем этот модуль, а иногда и даже и о модели памяти под которую этот модуль оттранслирован.

 

⇐ Предыдущая6789101112131415Следующая ⇒

Поделиться: