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

0 чел.

Лекция №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++


 

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

81101. Спортивная тренировка, ее составные части 24.65 KB
  Тренировка является важнейшей частью спортивной подготовки. Физическая подготовка это педагогический процесс направленный на воспитание физических качеств и развитие функциональных возможностей создающих благоприятные условия для совершенствования всех сторон подготовки.
81102. Прислів’я та приказки в українській та німецькій мовах 80 KB
  Протягом багатьох століть вони виявляли здатність народу відбирати й осмислювати найхарактерніші, найтиповіші сторони явищ природи, праці, побуту, родинного й суспільного життя і в результаті ставали конденсатором багатовікового життєвого досвіду, взаємин людей між собою, між класами...
81103. Питоме та чуже в термінології 53.68 KB
  Другі слова видаються органічними для англійського тексту, де їхні корінь і лексичне значення здебільшого прозорі. Але живосилом притягнуті в українську мову, вони втрачають цю органічність і набирають вигляду «стороннього тіла».
81104. Формирования мотивации в овладении иностранным языком на среднем этапе обучения 22.72 KB
  Ученик а также его родители должны иметь возможность выбора школы учителя программы обучения видов занятий форм контроля. Минимизация применения наград и наказаний за результаты обучения. 3адачи обучения должны исходить из запросов интересов и устремлений ученика.
81105. Пятая французская республика 45.8 KB
  Политическая система Франции сформировывалась на протяжении многих лет и даже веков. Франция по праву считается колыбелью республиканских идей. Великая Французская Революция 1789 г. дала толчок к революционным процессам во всем мире.
81106. Антропологический состав народов мира 27.24 KB
  Ненаучными являются расовые концепции которые утверждают что расы обладают определенными психологическими свойствами детерминирующими исторический процесс. Существует качественное отличие расы человека и расы животных.
81107. ИСКУТВЕННЫЕ АППАРАТЫ ПО ВОСТАНОВЛЕНИЮ ЗРЕНИЯ 558.12 KB
  Сетчатка состояит из слоя рецепторов и нескольких слоев других клеток рецепторы расположены на дальней от света стороне сетчатки прилегающей к глазному дну. Световоспринимающие фоторецепторы располагаются в самом наружном слое сетчатки соприкасающимся с пигментным слоем и скрыты под внутренними...
81108. Основні засади та правила роботи журналіста під час інтерв’ю 54 KB
  Причому до проблем творчості й майстерності журналіста входить не лише безпосереднє створення тексту, але (й передусім) мистецтво збирати матеріал для нього. Журналістика - це мистецтво спілкування, а з розвитком аудіовізуальних медіа – також і мистецтво публічного спілкування перед мікрофоном чи телекамерою.
81109. Соотношение фактического и юридического содержания правоотношения 44.86 KB
  Существует мнение, что правоотношение – это общественное отношение, урегулированное нормами права. Другое мнение сводится к тому, что правоотношение является общественным отношением особого рода, так называемая правовая форма общественного отношения.