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

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.