Лекция 06. Машинно-независимая оптимизация (1157464)

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

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

6. Машинно-независимаяоптимизация16.1. Простые оптимизации6.1.1 Сворачивание константСворачивание констант, или вычисление константных выражений –это вычисление выражений, все операнды которых – константы,значения которых известны во время компиляции и подстановкасвернутых констант в выражения, операндами которых они являются.Оптимизация состоит в том, что часть вычислений выполняется вовремя компиляции и убирается из программы.Основная проблема – добиться, чтобы все операции выполнялисьточно так же, как они выполнялись бы во время выполненияпрограммы.Прежде всего это связано с исключительными ситуациями.В случае булевских вычислений исключительные ситуации невозбуждаются и потому таких проблем не возникает.26.1. Простые оптимизации6.1.1 Сворачивание константВ случае вычисления целых констант для некоторых исходныхданных компилируемой программы в процессе вычисления можетполучиться «деление на ноль», или «переполнение».

В этом случаекомпилятор должен выдать пользователю соответствующеесообщение об ошибке, либо предупреждение.Наибольшее количество проблем, естественно, возникает, еслисворачивается константа одного из плавающих типов.36.1. Простые оптимизации6.1.2 Алгебраические упрощения и перегруппировкаПрименение тождеств (i и j - переменные типа int):i0  0i i0 i0  i  ii 1  1  i  i / 1  ii 0  0i  0 (i )  ii  ( j )  i  jПрименение тождеств (b - переменная типа Boolean):b  true  true  b  trueb  false  false  b  bb & true  true & b  bb & false  false & b  false46.1. Простые оптимизации6.1.3 Распространение копийПусть в оптимизируемой процедуре есть инструкция копированияx  yРаспространение копий означает замену всех последующихвхождений переменной x на переменную y.Рассмотрим множество всех команд копирования анализируемойпроцедуры.

Каждая команда копирования описывается четверкойx, y, b, p, где x и y представляют инструкцию копированияx  y, находящуюся в строке p базового блока b.Множество всех таких четверок обозначим через U. Множество Uсодержит все инструкции копирования анализируемой процедуры.Пример. В процедуре, представленной на следующем слайде,имеется две команды копирования56.1. Простые оптимизации6.1.3 Распространение копийB1 c  +,a, bd  ce  *,d, dentryB3 h  +,g, 1B1B5 b  *,g, aif(f>h)gotoB2B3 d  c (2-я строка блока B1):четверка d, c, B1, 2B4B5B6exitB2 f  +,a, cg  ea  +,g, dif(a<c)gotoB4 f  -,d, gif(f>a)gotoB6 c  2 g  e (2-я строка блока B2):четверка g, e, B2, 2U = {d, c, B1, 2, g, e, B2, 2}66.1.

Простые оптимизации6.1.3 Распространение копийДля каждого базового блока b определиммножество copy(b) команд копирования(четверок x, y, b, p), содержащихся в блоке bмножество kill(b) переопределений y(четверок x, y, blk, p), убиваемых в блоке b76.1. Простые оптимизации6.1.3 Распространение копийБлокcopyentry entryB1B2B3B4B5B6exitkillB1{d, c, B1, 2}{g,e,B2,2}B2{g,e,B2,2}B3B4B5B6{d, c, B1, 2}exitg,e,B2,2 убивается в блоке B1, таккак в З-ей строке этого блокапереопределяется ed, c, B1, 2 убивается в блоке B6, таккак единственная инструкция этого8блока переопределяет c6.1. Простые оптимизации6.1.3 Распространение копийСистема уравнений составляется по аналогии с системойуравнений для достигающих определений:сначала из множества инструкций копированияудаляются инструкции «убитые» в блоке b, потом в негодобавляются инструкции копирования блока b.Второе уравнение содержит операцию пересечения, таккак по всем путям должны приходить одинаковые копии.OutCP (b)  copy(b)  ( InCP (b)  kill(b))InCP (b)   OutCP ( p)pPred(b)96.1.

Простые оптимизации6.1.4 Распространение копийБлокEntryB1entryB2B3B1B4B5B6exitB2B3B4B5InCP{d, c, B1, 2}{d, c, B1, 2, g,e,B2,2}{d, c, B1, 2, g,e,B2,2}{d, c, B1, 2, g,e,B2,2}{g,e,B2,2}B6exit106.1. Простые оптимизации6.1.3 Распространение копийB1 c  +,a, bd  ce  *,c, centryB3 h  +,e, 1B1B5 b  *,e, aif(f>h)gotoB2B3B2 f  +,a, cg  ea  +,e, cif(a<c)gotoB4 f  -,c, eif(f>a)gotoB6 c  2B4B5B6exit116.2. Оптимизация циклов6.2.1 Классификация дуг ГПУДуги ГПУ, являющиеся дугами и его остовного дерева,называются остовными.Дуги ГПУ, не являющиеся дугами его остовного дерева, ноимеющие такое же направление, что и остовные, называютсяпрямыми.Дуги ГПУ, направленные противоположно остовным, называютсяобратно направленными.Обратно направленная дуга ГПУ Bi, Bk называется обратной,если Bk = Dom(Bi)Остальные дуги ГПУ называются поперечными.

Поперечные дугисоединяют различные поддеревья остовного дерева и впрограммах нормальных программистов не встречаются (их, атакже обратно направленные дуги любят великие Фортранные12программисты, но и у них они постепенно выходят из моды).6.2. Оптимизация циклов6.2.2 Натуральные циклыОпределение. Натуральным (или естественным) цикломназывается цикл со следующими свойствами:Цикл имеет единственный входной узел, называемый егозаголовком,Существует обратное ребро, ведущее в заголовок циклаОпределение. Натуральный цикл обратного ребра Bi, Bkсоставляют узел Bk (заголовок цикла) и все узлы ГПУ, изкоторых можно достичь узла Bi, не проходя через узел Bk.(этиузлы составляют тело цикла).136.2. Оптимизация цикловB16.2.3 Натуральные циклы. Пример.На рисунке справа – пять обратных дуг:B3B10, B7, B7, B4, B4, B3,B8, B3, B9, B1Обратной дуге B10, B7B4соответствуетнатуральный цикл {B7, B8, B10}, так какиз вершин B8 и B10 можно достичьвершины B10, не проходя через B7.B2B6B5B7B8Обратной дуге B7, B4 соответствуетнатуральный цикл{B4, B5, B6, B7, B8, B10}B10B9Этот цикл включает в себя цикл дугиB10, B7 , который является вложеннымциклом146.2.

Оптимизация циклов6.2.3 Натуральные циклы. Пример.У натуральных циклов обратных дугB1B4, B3 и B8, B3 один и тот же заголовокB3 и одно и то же множество вершин{B3, B4, B5, B6, B7, B8, B10 }.B2B4Эти два цикла можно объединитьв один. В этот цикл вложены циклыобратных дуг B10, B7 и B7, B4B3B6B5B7B8B10B9156.2. Оптимизация циклов6.2.3 Натуральные циклы. Пример.B3 У натуральных циклов обратных дугB4B4, B3 и B8, B3 один и тот же заголовок B3и одно и то же множество вершин{B3, B4, B5, B6, B7, B8, B10 }.Эти два цикла можно объединить в один.В этот объединенный цикл вложены циклыB6B5B7обратных дуг B10, B7 и B7, B4B8B10166.2.

Оптимизация циклов6.2.4 Алгоритм построения натурального цикла по обратной дугеВход:ГПУ G = N, Е с входным узлом Entry.Обратная дуга e = n, d  EВыход:подграф C G, являющийся натуральным циклом.Метод:(1)начальное значение С – множество {n, d}.(2)узел d помечается как «посещенный».(3)начиная с узла n выполняется поиск в глубину(4)на обратном графе потока (направления дугзаменены на противоположные).все узлы, посещенные на шаге (3), добавляютсяв C.176.2. Оптимизация циклов6.2.5 Построение натурального цикла по обратной дуге.

ПримерПрименим алгоритм 6.2.4 для построениянатурального цикла, соответствующегообратной дуге B7, B4.Отметив вершину B4 как посещенную,выполним поиск в глубину, начиная свершины B7.При этом будем считать, что на ГПУ стрелкисоответствуют не концу, а началу дуги,т.е. роль множества Succ (B7) выполняетмножество Pred (B7) = {B5, B6, B10}B4B6B5B7B8B10186.2.

Оптимизация циклов6.2.5 Построение натурального цикла по обратной дуге. ПримерПрименим алгоритм 6.2.4 для построениянатурального цикла, соответствующегоB4обратной дуге B7, B4.B6Отметив вершину B4 как посещенную,выполним поиск в глубину, начиная сB5B7вершины B7.B4B6B8B5B10B7B8B10196.2. Оптимизация циклов6.2.6 Перемещение кода, инвариантного относительно циклаИнструкция инвариантна относительно цикла, если онаудовлетворяет одному из следующих условий: ее операнды – константы все определения операндов, достигающие инструкции находятсявне цикла внутри цикла имеется в точности одно определение операнда, нооно само инвариантно относительно цикла.206.2.

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

Тип файла PDF

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

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

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