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


 

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

55865. Развитие ситуативной речи 7-9 классы 1.68 MB
  Правила безопасного диалога Мы все дети одной планеты Человек и религия Каждая крупная статья предусматривает после себя три вида заданий: Обсуждаем прочитанное Выполняем задания Выполняем творческие задания.
55866. School in our life 86.5 KB
  After the home, the school is the place where pupils spend a lot of time. School is not only a place of education, it is a place, where pupils develop their personal skills.
55867. SCHOOL LIFE 12.18 MB
  I see that most of you like school and I do hope you go there to get new information. But I think these are not the only reasons why you come to school. Could you tell what you do at school. Look at the screen and make up sentences.
55868. Шкільне життя 131.5 KB
  Мета: ознайомити з новими лексичними одиницями; практикувати навички читання, монологічного мовлення, аудіювання; тренувати учнів у вживанні Future Indefinite Tense. Розвивати пам’ять учнів, виховувати інтерес до різних видів позакласної діяльностіі.
55870. Schule 2.75 MB
  Guten Tag! Die Kinder begrüßen einander. Ich freue mich euch wieder zu sehen. Hört das Rätsel und rate mal wie ist das Thema unserer Stunde? Im Dorfe steht ein schönes Haus,da gehen Kinder ein und aus sie gehen fleißig Tag für Tag wer woll das Haus mir nennen mag?
55871. Science and modern life 64.5 KB
  To introduce the topic ask students if they are studying science at school and whether they like it or not, why/why not, and what kinds of things do they do in their science classes. Then give the students the short general knowledge quiz.