Практикум «Оптимизирующие компиляторы» (на примере GCC), страница 13

. . ‘9’ – этот операнд должен быть тем же, что и операндс указанным номером;o ‘r’ – это регистр из GENERAL_REGS;o ‘m’ – это операнд из memory_operand;Практикум «оптимизирующие компиляторы»o ‘=’ – признак того, что операнд может потерять своё староезначение; имеет силу над всеми альтернативами;o ‘%’ – этот операнд может быть переставлен местами соследующим операндом; например, это имеет место длякоммутативных операций, таких как сложение, побитовоеИЛИ и т.п.результат-инструкции – выход (результат) инструкциидополнительныеset-выражения– дополнительные выражениявида (set …); предполагается, что они будут выполняться параллельно,поэтому выход одного из них нельзя использовать на входе другого.условие-применимости-описания–условиесрабатыванияшаблона; при его истинности этот шаблон можно применять.шаблонвыхода–целеваяпоследовательностьассемблерныхинструкций или код на C, который генерирует эту последовательность.атрибуты – атрибуты инструкции; устанавливаются значения атрибутов,если значения по умолчанию не подходят.Теперь рассмотрим несколько примеров описаний из AVR.(define_insn "negqi2"[(set (match_operand:QI 0 "register_operand" "=r")(neg:QI (match_operand:QI 1 "register_operand" "0")))]"""neg %0"[(set_attr "length" "1")(set_attr "cc" "set_zn")])Практикум «оптимизирующие компиляторы»В данном примере описывается инструкция negqi2, которая обращаетзнак операнда.

Операнд имеет размер байта (QI), должен находиться врегистре(“register_operand”).Далеевидно,чтоприёмникрезультата должен совпадать с источником значения (у операндаисточника имеется ограничение ‘0’, которое указывает на то, что это тотже регистр, что и стоящий на первом месте, т.е. регистр-результат), и, чтоестественно, это значение может измениться в результате выполненияоперации (на что указывает ‘=’).Практикум «оптимизирующие компиляторы»Оптимизации в компилятореОпределение оптимизирующего преобразованияПреобразованием программы является любая функция p, определённымобразом изменяющая внутреннее представление программы. Существуетобщийклассконкретизирующихпреобразований(обобщающих,сужающих и эквивалентных), использующийся как при доказательствеправильности программ, так и при оптимизирующих трансформациях.Подклассомконкретизирующиханализирующихпреобразований,преобразований,направленныхнаявляетсярешениеклассзадачверификации и на решение задач потокового анализа при оптимизациипрограмм.На практике из класса конкретизирующих преобразований используютсянекоторые основные подклассы, например:• оптимизирующие преобразование, направленные на повышениеэффективности программ (улучшающие программу в традиционномсмысле–уменьшениемвремениисполненияиразмерагенерируемого кода – с учётом разнообразия платформ и средисполнения);• преобразования,назначениемкоторыхявляетсяповышениесамодокументируемости и наглядности аннотируемой программы(пополнениепрограммыутверждениямиоеёсвойствахипреобразование базисной программы с помощью переименованияобъектов,вставокпрограммы);явныхописаний,улучшенияструктурыПрактикум «оптимизирующие компиляторы»• преобразования, осуществляющие построение отладочной версиипрограммы(спополнениембазиснойпрограммынаборомоператоров, проверяющих справедливость свойств программы,указанных в аннотациях, пример аннотации – макрос assert.).Оптимизирующее преобразование в компиляторе исполняется в три этапа:1.

определить часть программы, которую надо оптимизировать, иопределить соответствующее оптимизирующее преобразование;2. проверить, что преобразование не изменяет результат исполненияданного участка кода или изменяет его в рамках, утверждённыхпользователем;3. провести преобразование.Пункт 1 является предметом длительных исследований, так как егоисполнениезависитотмножествафакторов(вт.ч.архитектурапроцессора).

Пункт 2 гласит о том, что результат работы программы недолжен изменяться. Наиболее слабое определение гласит что:Преобразованиедопустимо,еслиоригинальнаяипреобразованнаяпрограммы дают один и тот же вывод для разных исполнений приодинаковых входных данных.Уточнение 1.1. Два запуска программы являются идентичными, если онипроизведены при одинаковых входных данных и если каждая парасоответствующих операторов с недетерминированным исполнением приобоих запусках даёт одинаковый результат.Обычно недетерминированные исполнение является результатом вызовавнешних функций, например процедур операционной системы.Рассмотрим некоторые возможные нарушения корректности выполненияпрограммы при преобразованиях:Практикум «оптимизирующие компиляторы»Переполнение.for (i=0; i<n; i++)temp = b[k] + 2.5;{for (i=0; i<n; i++)a[i] = a[i] + b[k] + 2.5;{}a[i] = a[i] + temp;}Недостоверно, что a[i]+(b[k]+2.5), вместо версии (a[i]+b[k])+2.5всегда будет исполнено без переполнения.

Возможно, суммирование(b[k]+2.5)дастпереполнениесразуже,вотличиеотнепреобразованной версии, и результат исполнения программы будетотличаться.Разные результаты могут получаться из-за изменения порядка следованияопераций в программе, и ошибка может накапливаться. Здесь женеобходимо вспомнить про ошибки округления.Ошибка при работе с памятью. В предыдущем примере в первом случае,если индекс k выходит за допустимые пределы, но n=0 цикл выполнятьсяне будет, и адресации памяти по неверному адресу не будет. Как толькомы выносим этот инвариант за пределы цикла, имеем ошибку.Различные результаты в случае, если массивы a и b перекрываются.Примеры некорректных преобразований можно перечислять бесконечно,поэтому на практике применяют несколько другое правило:Преобразование программы корректно, если для всех семантическиправильных исполнений программы, оригинальная и преобразованнаяверсии программы дают идентичный результат для идентичных запусков.Фактически, при программировании мы делаем множество допущений,которые могут в конкретном случае и не выполняться: например,индексация массива может не выходить за пределы его размерностей.Корректность в этом контексте является не свойством самой программы, аПрактикум «оптимизирующие компиляторы»свойством её конкретного запуска – поскольку при одних входных данныхпрограмма может вести себя корректно, при других некорректно.

Те жесамые соображения относятся и к обработке исключений. Вообщенедостоверно, что преобразованная программа будет давать абсолютнотакой же результат, как и исходная – возможно это не требуется.Таким образом, на практике используется ещё более слабое утверждение:Преобразование программы корректно, если для всех семантическикорректныхзапусковпреобразованнаяидентичныхисходнойверсиизапусках.производятВсепрограммы,оригинальнаяэквивалентныеперестановкиоперациикоммутативныхиприоперацийподразумеваются эквивалентными.Естественно, если в случае выполнения компилятором пункта (3)появляется погрешность в вычислениях, выходящая за определённыерамки, необходимо вернуться к пункту (2) – трудно заранее предугадать,как будет оптимизировано исполнение коммутативных операторов.Участки экономии.Оптимизирующие преобразования обычно производятся над некоторымучастком программы, и, в зависимости от типа преобразования,рассматриваются участки различной структуры и величины.

Основныеградации величины участков экономии такие:1. оператор – в основном арифметические операторы являютсяучастком экономии в рамках одного оператора;2. базовый блок – последовательность операторов с единственнойточкой входа и без ветвлений, базовый блок (ББ) был объектоммногих ранних исследований по оптимизации;Практикум «оптимизирующие компиляторы»3. самый вложенный цикл, в этом контексте выполняются многиеоптимизации;4. идеально вложенное гнездо циклов (все циклы, кроме самоговложенного содержат в себе только один оператор – более глубоковложенный цикл);5.

вложенное гнездо циклов (любого формата);6. процедура (глобальная оптимизация);7. множество процедур, рассматриваемых вместе (межпроцедурнаяоптимизация).Каждое оптимизирующее преобразование применяется с целью улучшениянекоторойхарактеристики(характеристик)программы.Зачастуюпреобразование при улучшении одной из характеристик, ухудшает другую.Приведём примеры характеристик:1. количествозанимаемыхресурсовпроцессора(например,функциональных устройств);2.

минимизация количества выполняемых операций;3. минимизация количества обращений в оперативную память;4. минимизация размера программы и использования памяти дляданных;5. минимизация энергопотребления.Базовымпонятием,используемымвовсехоптимизирующихпреобразованиях уровня базового блока и выше, является понятиезависимости по данным.В общем случае встречаются три типа зависимости по данным: истиннаяили потоковая, антизависимость, и зависимость по выходу (выходная). Длякаждого типа зависимости определены исток (источник зависимости) иПрактикум «оптимизирующие компиляторы»сток зависимости (зависящий оператор). Графом зависимости по даннымявляется ориентированный граф, вершинами которого являются операторыпрограммы, две вершины Si и Sj соединены дугой, если существуетзависимость одного из трёх перечисленных типов с истоком в Si и стоком вSj.

Каждая дуга имеет метку, определяющую тип зависимости и глубинузависимости (для оператора в теле гнезда цикла) – номер цикла,порождающего данную зависимость.Пусть Si обозначает i-й оператор в программе или ББ, если считать влексикографическом порядке.

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