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


 

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

58807. Програма. Мова програмування 182.5 KB
  Основні елементи однієї з мов програмування – алфавіт; основні поняття мови: числа, рядки, описи, ідентифікатори, оператори, величини, операції; типи даних у мові програмування, набір функцій та операцій, допустимих для кожного з типів даних...
58812. Поурочные разработки по истории древнего мира 1.54 MB
  Подробные поурочные планы содержат весь необходимый материал для проведения полноценных уроков по истории Древнего мира в 5 классе общеобразовательных школ, рассчитаны на преподавателей, работающих по учебникам А.А. Вигасина, Г.И. Годера, И.С. Свенцицкой (М.: Просвещение), Ф.А. Михайловского (М.: Русское слово)
58813. Використання інноваційних технологій навчання на уроках української літератури 218 KB
  Досвід переконує, що комп’ютер сприяє не тільки розвитку самостійності, творчих здібностей учнів, його застосування дозволяє змінити саму технологію надання освітніх послуг, зробити урок більш наочним і цікавим.
58814. КУЛЬТУРА ЗАХІДНОЇ ЄВРОПИ V-XV СТОЛІТЬ. СПІВАНА ІСТОРІЯ 220 KB
  Вступне слово вчителя. Слово вчителя. Слово вчителя. Навчання ми почали з тривіуму або предметів про слово граматики риторики і діалектики.
58815. Кровообіг і лімфообіг 844.5 KB
  Кровообіг це безперервний рух крові по кровоносних судинах зумовлений роботою серця. Повідомлення учня Еволюція кровоносної системи і серця хребетнихâ таблиця Еволюція кровоносної системи Відмітити що вперше кровоносна система зявилась у Кільчастих червів а серце у Молюсків. Розглянути особливості будови кровоносної системи і серця у риб земноводних плазунів птахів ссавців. Учні відзначають що з будовою серця повязана температура тіла.