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++


 

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

34216. Условия обитания животных в океанах и морях 22.64 KB
  Водя является легко проницаемой средой для активно передвигающихся животных. Существование в воде водорослей и бактерий обеспечивает жизнь очень многих животных. Скопление органического детрита поступающего с суши обеспечивает обильное развитие водорослей бурых зелёных багряных а те в свою очередь создают благоприятные условия для жизни многих животных – фораминифер червей моллюсков иглокожих ракообразных.
34220. Современная биология 15.61 KB
  Ламарком происходит от двух греческих слов: bios жизнь и logos наука. Так ботаническими науками являются: микология наука о грибах; альгология наука о водорослях; бриология наука о мхах и т. К зоологическим наукам относятся: протозоология учение о простейших; гельминтология о паразитических червях; арахнология о паукообразных; энтомология о насекомых и т. К морфологическим наукам относятся: анатомия изучающая макроскопическую организацию животных и растений; гистология наука о тканях и о...