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


 

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

69202. ОСНОВИ АЕРОДИНАМІКИ ТА ДИНАМІКИ ПОЛЬОТУ 2.97 MB
  При обтіканні повітряним потоком різних тіл частин літальних апаратів виникають сили і моменти які залежать від форми літальних апаратів і впливають на їх льотнотехнічні характеристики. Аеродинаміка вивчає умови виникнення аеродинамічних сил тобто повітряних...
69203. Природа виникнення аеродинамічних сил. Принципи створення піднімальної сили 8.87 MB
  Картина обтікання крила літака потоком повітря показана на рис. Повна аеродинамічна сила крила: а картина обтікання крила літака потоком повітря; б схема створення повної аеродинамічної сили R.21 а наглядно видно що потік обтікає верхню і нижню частини профілю крила неоднаково.
69204. Основні закони руху повітря, що стискається. Загальні відомості про аеродинаміку великих швидкостей 3.81 MB
  Таким чином величина стиснення залежить від відношення швидкості потоку до швидкості звуку. Це відношення називається числом Маха і вважається критерієм стисливості потоку. Чим більше швидкість повітряного потоку швидкість польоту V і менше швидкість звуку...
69205. Хвильова криза. Поняття про критичне число Маха 8.3 MB
  Найменша швидкість дозвукового польоту при якій у якійнебудь точці крила швидкість потоку що обтікає крило стає рівної місцевої швидкості звуку називається критичною швидкістю польоту Vкр а відповідне їй число Маха польоту критичним Мкр.
69206. Основні види руху літального апарату. Горизонтальний політ літака 1.78 MB
  Основними видами руху які розглядаються в динаміці польоту є горизонтальний політ набір висоти зниження зліт посадка віраж та ін. При розрахунках льотних даних літака зручно користуватися графічними залежностями тяги від швидкості і висоти польоту.
69207. Зліт і посадка літака 6.06 MB
  Зліт і посадка є відповідно первинним і завершальним етапами польоту літака. При зльоті й при посадці змінюються швидкість і висота польоту тому рух літака в цих режимах є несталим. Зліт і посадка літака найбільш відповідальні етапи польоту що вимагають від льотчика граничної уваги і точності.
69208. ЛІТАК ТА ЙОГО СИСТЕМИ 1.62 MB
  Швидкісна система координатних осей ОXYZ використовується для вивчення аеродинамічних сил та при розвязанні задач аеродинамічного розрахунку літака рис. Початок швидкісної системи координатних осей розміщено в центрі мас літака. Головною віссю є швидкісна вісь ОХа направлена по вектору швидкості літака.
69209. Середні величини та показники варіації 167.5 KB
  Середня величина це узагальнююча кількісна характеристика сукупності однотипних явищ по одній варіюючій ознаці. Найважливішою умовою наукового використовування середніх величин в статистичному аналізі суспільних явищ в тому числі й методом динамічних...