Исключение лишних операций

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).

Таблица 3.4 – Пример исключения лишних операций

Вынесение инвариантных операций за тело цикла

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

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

Во время первого прохода цикла заполняется таблица инвариантных переменных, во время второго – выполняется собственно вынесение операций.

27. Компоновщики – редакторы связей.

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

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. Передача параметров в форме непосредственных значений или адресных указателей осуществляются через стек. Необходимость проверки соответствия типов данных, аргументов, процедур и функций, а также числа аргументов в процедурах, существенно усложняет представления словаря внешних ссылокв объектных файлах. Компоновщики используют программные модули, хранящие информацию об именах исходных модулей программы, типе компилятора породившем этот модуль, а иногда и даже и о модели памяти под которую этот модуль оттранслирован.

28. Загрузчики: абсолютные, перемещающие, связывающие.

Загрузчик копирует готовый к выполнению модуль в ПМ по команде ОС. Во время этого копирования загрузчик может осуществлять адресную трансляцию перемещаемого модуля. Загрузчик может быть либо двоичным (абсолютным), либо перемещаемым. При двоичной загрузке готовому к выполнению модулю присваиваются физические адреса еще во время компоновки и т.о. никакое перемещение не возможно. Перемещаемый загрузчик загружает программу в любую область ОП.

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

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

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

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

Таблица определения символов перечисляет все символы класса, каждая запись таблицы – это пара (DName[i],DVal[i]), где DName содержит символы, а DVal – соответствующие им значения. Значением символа обычно является перемещаемый адрес А команды или данных в пределах сегмента. Когда сегмент перемещается загрузчиком, элементы сегмента с перемещаемым адресом настраиваются единообразно на место в памяти с абсолютным адресом, определяемым символом этого элемента.

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

Таблица использования состоит из списка всех внешних символов, на которые имеются ссылки в сегменте.

Важной переменной, используемой в перемещающем загрузчике, является адрес загрузки программы (PROGADDR).Существует несколько алгоритмов построения перемещающих загрузчиков:

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

a. Прочитать запись-заголовок;

b. Проверить имя и длину программы;

c. Получить PROGADDR от ОС;

d. Прочитать первую запись тела программы;

e. Пока тип записи не равен «Е» выполнить следующие шаги:

i. Если объектный код задан в символическом виде, то преобразовать его во внутреннее представление;

ii. Если тип записи равен «Т», то переписать объектный код в заданное место ОП;

iii. Если тип записи равен «N», то модифицировать заданное поле, т.е. прибавить к нему значение PROGADDR;

iv. Прочитать следующую запись объектной программы;

f. Передать управление по адресу, заданному в записи конец, т.е. тип записи «Е» плюс PROGADDR.

2. Перемещение с помощью маски – эффективен на компьютерах, где используется прямая адресация и фиксированный командный формат. Формат записей тела программы тот же, что и ранее, за исключением того, что теперь с каждым словом объектного кода связан разряд перемещения. Эти разряды собираются вместе и образуют маску, которая записывается после указателя длины каждой записи тела программы. Если разряд перемещения установлен в единицу, то при перемещении программы начальный адрес программы добавляется к слову, соответствующему этому разряду. Значение разряда перемещения равное нулю показывает, что никаких преобразований при перемещении делать не нужно.