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

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.