Тема 05(2016)Машинно-независимая оптимизация (1161800)

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

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

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

В этом случаекомпилятор должен выдать пользователю соответствующеесообщение об ошибке, либо предупреждение.Наибольшее количество проблем, естественно, возникает, еслисворачивается константа одного из плавающих типов.35.1. Простые оптимизации5.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  false45.1. Простые оптимизации5.1.3 Распространение копийПусть в оптимизируемой процедуре есть инструкция копированияx  yРаспространение копий означает замену всех последующихвхождений переменной x на переменную y.Рассмотрим множество всех команд копирования анализируемойпроцедуры.

Каждая команда копирования описывается четверкойx, y, b, p, где x и y представляют инструкцию копированияx  y, находящуюся в строке p базового блока b.Множество всех таких четверок обозначим через U.Множество U содержит все инструкции копирования анализируемойпроцедуры.55.1. Простые оптимизации5.1.3 Распространение копий В процедуре, ГПУ которой представлен на рисунке две командыкопированияB1 c  +,a, bd  ce  *,d, dentryB1B3 h  +,g, 1B2B3B5 b  *,g, aif(f>h)gotoB4B5B2 f  +,a, cg  ea  +,g, dif(a<c)gotoB4 f  -,d, gif(f>a)gotoB6 c  2B6exit65.1.

Простые оптимизации5.1.3 Распространение копий В процедуре, ГПУ которой представлен на рисунке, две командыкопированияB1 c  +,a, bd  ce  *,d, dentryB1B3 h  +,g, 1B2B3B5 b  *,g, aif(f>h)gotoB4B5B6exitB2 f  +,a, cg  ea  +,g, dif(a<c)gotoB4 f  -,d, gif(f>a)gotoB6 c  2d  c (2-я строка блока B1):четверка d, c, B1, 2g  e (2-я строка блока B2):четверка g, e, B2, 275.1. Простые оптимизации5.1.3 Распространение копий В процедуре, ГПУ которой представлен на рисунке две инструкциикопированияB1 c  +,a, bd  ce  *,d, dentryB1B3 h  +,g, 1B2B3B5 b  *,g, aif(f>h)gotoB4B5B6exitB2 f  +,a, cg  ea  +,g, dif(a<c)gotoB4 f  -,d, gif(f>a)gotoB6 c  2Следовательно множество Uинструкций копирования равноU = {d, c, B1, 2, g, e, B2, 2}85.1.

Простые оптимизации5.1.3 Распространение копийДля каждого базового блока b определиммножество copy(b) команд копирования(четверок x, y, b, p), содержащихся в блоке bмножество kill(b) переопределений y(четверок x, y, b, p), убиваемых в блоке b95.1. Простые оптимизации5.1.3 Распространение копийB1 c  +,a, bd  ce  *,c, centryB1B3 h  +,e, 1B2B3B5 b  *,e, aif(f>h)gotoB4B5B6B2 f  +,a, cg  ea  +,e, cif(a<c)gotoB4 f  -,c, eif(f>a)gotoB6 c  2Определим множества copy(b) дляблоков рассматриваемого примера.exit105.1.

Простые оптимизации5.1.3 Распространение копийB1 c  +,a, bd  ce  *,c, centryB1B3 h  +,e, 1B2B3B5 b  *,e, aif(f>h)gotoB4B5B6exitB2 f  +,a, cg  ea  +,e, cif(a<c)gotoB4 f  -,c, eif(f>a)gotoB6 c  2Определим множества copy(b) дляблоков рассматриваемого примера.copy(B1) = {d, c, B1, 2}copy(B2) = {g,e,B2,2}115.1. Простые оптимизации5.1.3 Распространение копийB1 c  +,a, bd  ce  *,c, centryB1B3 h  +,e, 1B2B3B5 b  *,e, aif(f>h)gotoB4B5B6exitB2 f  +,a, cg  ea  +,e, cif(a<c)gotoB4 f  -,c, eif(f>a)gotoB6 c  2Определим множества copy(b) дляблоков рассматриваемого примера.copy(B1) = {d, c, B1, 2}copy(B2) = {g,e,B2,2}Остальные блоки не содержат инструкций копирования, поэтому для этихблоков множества copy(b) пустые:copy(B3)=, copy(B4)=, copy(B5)=, copy(B6)=125.1.

Простые оптимизации5.1.3 Распространение копийB1 c  +,a, bd  ce  *,c, centryB1B3 h  +,e, 1B2B3B5 b  *,e, aif(f>h)gotoB4B5B6B2 f  +,a, cg  ea  +,e, cif(a<c)gotoB4 f  -,c, eif(f>a)gotoB6 c  2Определим множества kill(b)exit135.1. Простые оптимизации5.1.3 Распространение копийB1 c  +,a, bd  ce  *,c, centryB1B3 h  +,e, 1B2B3B5 b  *,e, aif(f>h)gotoB4B5B6exitB2 f  +,a, cg  ea  +,e, cif(a<c)gotoB4 f  -,c, eif(f>a)gotoB6 c  2Определим множества kill(b)g,e,B2,2 убивается в блоке B1, так какв З-ей строке этого блока переопределяетсяe.

Следовательно kill(B1) ={g,e,B2,2}d,c,B1,2 убивается в блоке B6, так как единственная инструкцияэтого блока переопределяет c. Следовательно kill(B6) ={d,c,B1,2}145.1. Простые оптимизации5.1.3 Распространение копийB1 c  +,a, bd  ce  *,c, centryB1B3 h  +,e, 1B2B3B5 b  *,e, aif(f>h)gotoB4B5B6exitB2 f  +,a, cg  ea  +,e, cif(a<c)gotoB4 f  -,c, eif(f>a)gotoB6 c  2Определим множества kill(b)g,e,B2,2 убивается в блоке B1, так какв З-ей строке этого блока переопределяетсяe. Следовательно kill(B1) ={g,e,B2,2}d,c,B1,2 убивается в блоке B6, так как единственная инструкцияэтого блока переопределяет c.

Следовательно kill(B6) ={d,c,B1,2}15Множества kill(b) остальных блоков пустые.5.1. Простые оптимизации5.1.3 Распространение копийentryТаким образом для базовых блоковрассматриваемой процедуры множестваcopy(b) и kill(b) следующие:B1bkill(b)B1{d, c, B1, 2}{g,e,B2,2}B2{g,e,B2,2}B3B4B5B6{d, c, B1, 2}exitentry B2B3copy(b)B4B5B6exit165.1. Простые оптимизации5.1.3 Распространение копийСистема уравнений составляется по аналогии с системойуравнений для достигающих определений:сначала из множества инструкций копированияудаляются инструкции «убитые» в блоке b, потом в негодобавляются инструкции копирования блока b.Второе уравнение содержит операцию пересечения,так как по всем путям должны приходить одинаковыекопии.OutCP (b)  copy(b)  ( InCP (b)  kill(b))InCP (b)   OutCP ( p)pPred(b)175.1.

Простые оптимизации5.1.4 Распространение копийРешив систему уравнений методом итераций, получимследующие значения InCPentrybEntryB1B1B2B3B4B5B6exitB2B3B4B5B6exitInCP(b){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}185.2. Оптимизация циклов5.2.1 Классификация дуг ГПУДуги ГПУ, являющиеся дугами и его остовного дерева,называются остовными.Дуги ГПУ, не являющиеся дугами его остовного дерева, ноимеющие такое же направление, что и остовные, называютсяпрямыми.Дуги ГПУ, направленные противоположно остовным, называютсяобратно направленными.Обратно направленная дуга ГПУ Bi, Bk называется обратной,если Bk = Dom(Bi)Остальные дуги ГПУ называются поперечными.

Поперечные дугисоединяют различные поддеревья остовного дерева и впрограммах нормальных программистов не встречаются(поперечные и обратно направленные дуги любят Фортранные19программисты, но и у них они постепенно выходят из моды).5.2. Оптимизация циклов5.2.2 Естественные циклыОпределение. Естественным циклом называется цикл соследующими свойствами:Цикл имеет единственный входной узел, называемый егозаголовком,Существует обратное ребро, ведущее в заголовок циклаОпределение.

Естественный цикл обратного ребра Bi, Bkсоставляют узел Bk (заголовок цикла) и все узлы ГПУ, изкоторых можно достичь узла Bi, не проходя через узел Bk.(этиузлы составляют тело цикла).205.2. Оптимизация цикловB15.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 , который является вложеннымциклом215.2.

Оптимизация циклов5.2.3 Естественные циклы. Пример.У естественных циклов обратных дугB1B4, B3 и B8, B3 один и тот же заголовокB3 и одно и то же множество вершин{B3, B4, B5, B6, B7, B8, B10 }.B2B4Эти два цикла можно объединитьв один. В этот цикл вложены циклыобратных дуг B10, B7 и B7, B4B3B6B5B7B8B10B9225.2. Оптимизация циклов5.2.3 Естественные циклы. Пример.B3 У естественных циклов обратных дугB4B4, B3 и B8, B3 один и тот же заголовок B3и одно и то же множество вершин{B3, B4, B5, B6, B7, B8, B10 }.Эти два цикла можно объединить в один.В этот объединенный цикл вложены циклыB6B5B7обратных дуг B10, B7 и B7, B4B8B10235.2. Оптимизация циклов5.2.4 Алгоритм построения естественного цикла по обратной дугеВход:ГПУ G = N, Е с входным узлом Entry.Обратная дуга e = n, d  EВыход:подграф C G, являющийся естественным циклом.Метод:(1)начальное значение С – множество {n, d}.(2)узел d помечается как «посещенный».(3)начиная с узла n выполняется поиск в глубину(4)на обратном графе потока (направления дугзаменены на противоположные).все узлы, посещенные на шаге (3), добавляютсяв C.245.2.

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

Оптимизация циклов5.2.6 Перемещение кода, инвариантного относительно циклаИнструкция инвариантна относительно цикла, если онаудовлетворяет одному из следующих условий: ее операнды – константы все определения операндов, достигающие инструкции находятсявне цикла внутри цикла имеется в точности одно определение операнда, нооно само инвариантно относительно цикла.275.2. Оптимизация циклов5.2.6 Перемещение кода, инвариантного относительно цикла Рассмотрим пример: цикл с заголовком B2.B1 b2i1B2 if(i>100) B3B4 da+d B5 dced+1fd+1ab+1c2if(i%2=0)EntryB1B6 ii+1if(a<2)B2Блок B1 выполняется до цикла, все остальные – вцикле.Инструкции ab+1, c2, a<2инвариантны относительно цикла.B3B4Оптимизация состоит в том, что в ГПУB6добавляется еще один блок – предзаголовокцикла B2, в который выносятся из цикла всеинвариантные инструкции.B5Exit285.2.

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

Тип файла PDF

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

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

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