20611

Оптимизация базовых блоков c помощью дагов

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

1 t1:=4i t2:=a[t1] t3:=4i t4:=b[t3] t5:=t2t4 t6:=prodt5 prod:=t6 t7:=i1 i:=t7 i =20 goto1 Поочередно рассматривается каждая инструкция блока. e:=ab f:=ec g:=fd n:=ab i:=ic j:=ig = e:=ab f:=ec g:=fd i:=ic j:=ig Локальная оптимизация устранение лишних инструкций MOV R0a MOV a R0 устранение недостижимого кода if а = 1 goto L1 goto L2 L1: L2: = if а = 1 goto L2 goto L1 L1: goto L2 = goto L2 3.

Русский

2013-07-31

88 KB

1 чел.

Лекция №12

Оптимизация базовых блоков c помощью дагов

Алгоритм построения дага базового блока:

  1.  Листья помечаются уникальным идентификатором, или именами переменных, или константами.
  2.  внутренние узлы помечены операторами.
  3.  внутренние узлы могут быть также помечены последовательно идентификаторами, принимающими значения, вычисляемые в этих узлах.

(1)

t1:=4*i

t2:=a[t1]

t3:=4*i

t4:=b[t3]

t5:=t2*t4

t6:=prod+t5

prod:=t6

t7:=i+1

i:=t7

i<=20 goto(1)

Поочередно рассматривается каждая инструкция блока.

Когда встречается инструкция вид x:=y+z, то ищутся узлы, представляющие текущие значения y и z. Это могут быть как листья, так и внутренние узлы дага.

Затем создается узел, помеченный как “+”, устанавливаются связи узла с дочерними узлами у и z. Этот узел помечается как х.

Если уже имеется узел, обозначающий y+z, то новый узел х в графе не создается, а х добавляется к списку идентификаторов имеющегося узла.

Набор трехадресных инструкций с учетом оптимизации на даге:

t1:=4*i

t2:=a[t1]

t4:=b[t1]

t5:=t2*t4

t6:=t5+t6

t7:=t7+1

Пример: построить и оптимизировать даг.

e:=a+b

f:=e-c

g:=f*d

n:=a+b

i:=i-c

j:=i+g

=>

e:=a+b

f:=e-c

g:=f*d

i:=i-c

j:=i+g

Локальная оптимизация

  1.  устранение лишних инструкций

MOV R0,a

MOV a, R0

  1.  устранение недостижимого кода

if а = 1 goto L1  

     goto L2 

L1:

L2:

=> if  !а = 1 goto L2  

goto L1              

L1: goto L2

=> goto L2

3. алгебраические упрощения

 b:=b * 1

  1.  снижение стоимости инструкции

b:=a*a => sqr(a)

  1.  использование машинных идиом (автоинкремент, адресация)

x:=x+1 => x++


 

А также другие работы, которые могут Вас заинтересовать

72254. Процессуальное право Республики Казахстан 98 KB
  Цель лекции: сформировать у студентов представление о системе процессуального права его принципах участниках уголовно и гражданско-процессуальных правоотношений и стадиях уголовного и гражданского процесса.
72255. Борьба с коррупцией в Казахстане 66.5 KB
  За правонарушения связанные с коррупцией несут ответственность лица уполномоченные на выполнение государственных функций и лица приравненные к ним. К лицам уполномоченным на выполнение государственных функций относятся: все должностные лица депутаты Парламента...
72256. Уголовное право Республики Казахстан 199 KB
  Уголовное право регулирует общественные отношения возникающие после совершения преступления между государством в лице правоохранительных органов и лицом совершившим преступление. Состав преступления. Понятие стадий преступления.
72257. Основы экологического права Республики Казахстан 150 KB
  Специфика природных объектов как объектов регулирования со стороны экологического права выражается в их естественном характере происхождения и функционирования в их органической взаимосвязи с окружающей природной средой.
72258. Основы финансового права Республики Казахстан 212.5 KB
  Финансовая деятельность государства осуществляется только на основе права каковым является финансовое право. Поэтому можно встретить высказывание согласно которому финансы подразделяются на финансы граждан финансы юридических лиц финансы государственно-территориальных образований...
72259. Основы организации и деятельности правоохранительных органов Республики Казахстан 76 KB
  Быстрое и полное раскрытие преступлений, изобличение и привлечение к уголовной ответственности лиц, их совершивших, правильное применение уголовного закона, обеспечение защиты от необоснованного обвинения и осуждения, от незаконного ограничения прав и свобод человека...
72260. Суд и правосудие в Республике Казахстан 117 KB
  Сегодня в нашей республике судебной системе как самостоятельной ветви власти отводится центральное место в реализации государственной функции по соблюдению и защите прав и свобод человека Цель лекции: сформировать у студентов представление о судебной системе принципах правосудия.