Лекция 10. Заключение (1157468)

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

Текст из файла

10. Заключение.110.1 Что было рассказаноИсходный код10.1.1. Что такое оптимизирующий компиляторОптимизатор 1: машиннонезависимая оптимизация удаление бесполезного кода удаление избыточныхвычислений удаление мертвого кода удаление недостижимогокодаТаблицасимволовПередний планВнутреннеепредставление 1Оптимизатор 1Внутреннеепредставление 2Оптимизатор 2Внутреннеепредставление 2Генератор кода210.1 Что было рассказаноИсходный код10.1.1. Что такое оптимизирующий компиляторОптимизатор 1: машиннонезависимая оптимизация удаление бесполезного кода удаление избыточныхвычислений удаление мертвого кода удаление недостижимогокодаОптимизатор 2: машинноориентированная оптимизация выбор команд распределение регистров планирование кодаТаблицасимволовПередний планВнутреннеепредставление 1Оптимизатор 1Внутреннеепредставление 2Оптимизатор 2Внутреннеепредставление 2Генератор кода310.1 Что было рассказаноИсходный код10.1.1.

Что такое оптимизирующий компиляторВнутреннее представление 1: инструкции вида:х  op, y, zгде х, y, z – абстрактныеобласти памяти, отведенныепод соответствующиепеременныеТаблицасимволовПередний планВнутреннеепредставление 1Оптимизатор 1Внутреннеепредставление 2Внутреннее представление 2: операции вида:OP X, Y, Zгде Х, Y, Z – регистрыили адреса ячеек памятиоперации объединяются вкомандыОптимизатор 2Внутреннеепредставление 2Генератор кода410.1 Что было рассказаноИсходный код10.1.1. Что такое оптимизирующий компиляторОптимизирующий компилятор: много оптимизирующихпреобразований, которые внекотором порядкеприменяются к кодукомпилируемой программы,повышая ее качество; порядок оптимизирующихпреобразований зависит откомпилируемой программы,в настоящее время делаютсяпервые попытки обеспечитьавтоматический подбороптимизирующихпреобразований по исходномукоду программы.ТаблицасимволовПередний планВнутреннеепредставление 1Оптимизатор 1Внутреннеепредставление 2Оптимизатор 2Внутреннеепредставление 2Генератор кода510.1 Что было рассказаноEntry10.1.2.

Граф потока управленияАВ программе выделяются базовые блоки(линейные участки) и строится ГПУ.Оптимизация в пределах одного базовогоблока называется локальной,оптимизация в пределах несколькихбазовых блоков (например, суперблока) –региональной,оптимизация в пределах процедуры –BCDглобальнойв настоящее время рассматривается такжемежпроцедурная и даже межмодульнаяоптимизацияEFExit610.1 Что было рассказано10.1.3. Локальная оптимизацияКаждый базовый блок задается тройкой объектов:B = P, Input, Outputгде P – последовательность инструкций блока B,Input – множество переменных, определения которых достигаютблока B,Output –множество переменных, живых после блока B. Все задачи локальной оптимизации позволяет решить методлокальной нумерации значений.Избыточные вычисления внутри базового блока автоматическиудаляются в процессе построения ОАГ (ориентированногоациклического графа).Множества Input и Output позволяют фиксировать использованиенеинициализированных переменных и исключить присваиваниезначений мертвым переменным.710.1 Что было рассказаноEntry10.1.4.

Нумерация вершин ГПУДля нумерации вершин ГПУстроится остовное дерево с корнемв Entry и выполняется его обход«сначала в глубину», используя«обратную нумерацию» (номерприсваивается при первом посещениивершины).Нумерация определяет порядокобработки вершин ГПУ привыполнении методов итерации.На рисунке представлен ГПУ посленумерации его вершин.B1B2B3B4B5B6Exit810.1 Что было рассказано10.1.5. Поток данныхВсе преобразования программы при ее оптимизации должнысохранять семантику программы.Семантика каждого фрагмента программы (инструкции, базовогоблока, группы базовых блоков, процедуры, модуля и т.п.) описываетсяпарой состояний процессора: состоянием во входной точкесоответствующего фрагмента и состоянием в его выходной точке. входная точка каждой инструкции расположена между этойинструкцией и предшествующей инструкцией; выходная точкаинструкции расположена между ней и следующей инструкцией;...

 I j 1  I j  I j 1  ...входной точкой базового блокаявляется входная точка его первойинструкции; выходной точкойбазового блока является выходнаяточка его последней инструкцииIn[B]BOut[B]910.1 Что было рассказано10.1.6. Передаточная функцияПара состояний во входной и выходной точках фрагмента определяетпередаточные функции этого фрагмента: передаточная функция прямого обхода ( f ) переводитсостояние во входной точке в состояние в выходной точке передаточная функция обратного обхода ( fb )переводитсостояние в выходной точке в состояние во входной точкеДля инструкций:Out[ I j ]  f I j ( In[ I j ])In[ I j ]  f b (Out[ I j ])IjДля базовых блоков:f B  f I1  f I 2  ...

 f I nf Bb  f Ib  f Ib  ... f Ibnn 111010.1 Что было рассказано10.1.7. Достигающие определенияОпределением переменной х называется инструкция, котораяприсваивает значение переменной х.Использованием переменной х является инструкция, одним изоперандов которой является переменная х.Каждое новое определение переменной х убивает ее предыдущееопределение.Определение d достигает точки p, если существует путь от точки,непосредственно следующей за d, к точке p, такой, что вдоль этогопути d остается живым.Для достигающих определений передаточная функция fIинструкции I может быть записана в виде: f I ( x)  genI  ( x  killI )1110.1 Что было рассказано10.1.7.

Достигающие определенияДля базового блока B из n инструкций передаточная функция имеетвид f B ( x)  genB  ( x  killB )гдеkillB  kill1  kill2  ...  killngenB  genn  ( genn1  killn )  ( genn2  killn1  killn )  ... ( gen1  kill2  kill3  ...  killn )Определения, достигающие входа в каждый базовый блок,получаются в результате решения системы уравненийOut[ Bi ]  genBi  ( In[ Bi ]  killBi )In[ Bi ]   Out[ P]PPred ( Bi )с дополнительным условием Out[Entry] =  методом итераций.Множество Input[B] для базового блока B – это множество InRD[B],которое строится при исследовании достигающих определений1210.1 Что было рассказано10.1.8.

Живые переменныеМножества Output для базовых блоков строятся как результатанализа, позволяющего выявить живые переменные,т.е. переменные, используемые в базовых блоках, в которыепопадает управление после выхода из исследуемого базового блока.OutLV [B] – множества переменных, живых на выходе из блоков Bполучаются в результате решения системы уравненийIn[ B]  useB  (Out[ B]  def B )Out[ B]  In[S ]SSucc( B )С дополнительным условием In [Exit] = defB – множество переменных, определяемых в блоке В до ихиспользования в этом блокеuseB – множество переменных, используемых в блоке В до ихопределения в этом блоке1310.1 Что было рассказано10.1.9.

ПолурешеткиПолурешетка – это множество L, на котором определенабинарная операция «сбор» , такая, чтодля всех х, у и z  L:xx=x(идемпотентность)xу=уx(коммутативность)x  (y  z) = (x  y)  z(ассоциативность)Полурешетка имеет верхний элемент (или верх) Т  L такой, чтодля всех x  L выполняется Т  x = xДля всех пар x, у  L определим отношение :x  у тогда и только тогда, когда x  у = xОтношение  является отношением частичного порядка.1410.1 Что было рассказано10.1.10.

Структура потока данных Структурой потока данных называется четверка D, F, L,  , гдеD – направление анализа (Forward или Backward),F – семейство передаточных функций,L – поток данных, - реализация операции сбора. Семейство передаточных функций F называется замкнутым, если:F содержит тождественную функцию I: х L: I(х) = х.F замкнуто относительно композиции: f, g  F  h(x) = g(f(х)) F. Семейства передаточных функций, используемые при анализедостигающих определений и живых переменных являются замкнутыми.1510.1 Что было рассказано10.1.10.

Структура потока данных Структура потока данных D, F, L,  называется монотонной, еслих, у  L, f  F f(x  у)  f(x)  f(у). Структура потока данных D, F, L,  называется дистрибутивной,если х, у  L, f  F:f(x  у) = f(x)  f(у). Семейства передаточных функций, используемые при анализедостигающих определений и живых переменных являютсядистрибутивными.1610.1 Что было рассказано10.1.11. Обобщенный итеративный алгоритм Алгоритм. Итеративное решение задачи анализа потока данных Вход: граф потока управления,структура потока данных D, F, L, ,передаточная функция fВ  Fконстанта из l  L для граничного условияВыход: значения из L для In[B] и Out[В] для каждого блока Вв графе потока.Метод: if (D = Forward) {Out[Entry] = l;for each (В  Entry) Out[В] = Т;while (внесены изменения в Out)for (each В  Entry) {InB   Λ PPred  B OutP OutB   f B InB 1710.1 Что было рассказано10.1.11. Обобщенный итеративный алгоритм Обобщенный итеративный алгоритм сходится к решению уравненийпотока данных, которое является максимальной фиксированной точкойсистемы уравнений InB  OutP ΛPPred  B OutB   f B InB т.е.

представляет собой решение {In[Вi]max, Out[Вi]max} этойсистемы, такое, что для любого другого решения {In[Вi], Out[Вi]}выполняются условия In [Вi]  In[Вi]max и Out[Вi]  Out[Вi]maxгде  – полурешеточное отношение частичного порядка.Итеративный алгоритм(1) посещает базовые блоки не в порядке их выполнения, а в порядкеобхода ГПУ (на каждой итерации каждый узел посещается только один раз)(2) в каждой точке сбора применяет операцию сбора к значениям потокаданных, полученным к этому моменту(3) иногда в пределах итерации базовый блок B посещается до посещения егопредшественников1810.1 Что было рассказано10.1.12. ДоминаторыВ ГПУ вершина d является доминатором вершины n(этот факт записывается как d dom n или d = Dom(n)),если любой путь от вершины Entry до вершины n проходитчерез вершину d. Каждая вершина n является доминаторомсамой себя, так как путь от Entry до n проходит через n.Отношение dom рефлексивно, антисимметрично итранзитивно, т.е.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций