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


 

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

65482. ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЕКСПЛУАТАЦІЇ ОРНОГО АГРЕГАТУ ПРИ НЕСТІЙКОМУ РУСІ 201.5 KB
  При цьому недостатньо приділяється уваги дослідженням орного агрегату як механічної системи а динамічна взаємодія трактора та начіпногоплуга суттєво впливає на ефективність агрегату і позначається на якісних показниках обробітку ґрунту.
65483. ФОРМУВАННЯ ДЕРЖАВНОЇ ПОЛІТИКИ ІНВЕСТИЦІЙНОГО РОЗВИТКУ РЕГІОНУ 255.5 KB
  Важливою передумовою стійкого економічного зростання в Україні є активізація інвестиційної діяльності. Сучасний стан розвитку економіки характеризується певним пожвавленням інвестиційного процесу та зростанням валового внутрішнього продукту країни.
65484. ФОРМУВАННЯ ФІНАНСОВОГО МЕХАНІЗМУ ДІЯЛЬНОСТІ СТРАХОВОЇ КОМПАНІЇ 356 KB
  Збалансований і налагоджений фінансовий механізм дозволяє формувати і використовувати активи страхової компанії з метою забезпечення максимального рівня її платоспроможності. Однак аналіз наукових праць свідчить що питання формування фінансового механізму...
65485. ФІНАНСОВА ПОЛІТИКА РОЗВИТКУ СІЛЬСЬКОГО ГОСПОДАРСТВА УКРАЇНИ: ТЕОРІЯ, МЕТОДОЛОГІЯ, ПРАКТИКА 432 KB
  Фінансова політика держави у сучасних умовах ринкових перетворень виступає визначальною для розвитку національної економіки. Ускладнення процесів економічних трансформацій, посилення їх динамізму, фінансова криза та її негативні наслідки виявили...
65486. БЕЛЬГІЯ ТА КОЛОНІАЛЬНИЙ ПОДІЛ АФРИКИ 172 KB
  ХХ століття стало свідком краху колоніальних імперій, проте інтерес дослідників до різних аспектів історії колоніальної політики не слабшає. У сучасному світі в істориків з'являються все нові можливості для вивчення історичних явищ і розширення проблематики своїх досліджень...
65487. Метод розрахунку довговічності елементів авіаційних конструкцій, навантажених розтягом-стиском та згином 3.54 MB
  Метод розрахунку довговічності конструкцій за номінальними напруженнями ґрунтується на використанні понять ефективного коефіцієнта концентрації напружень і коефіцієнта якості конструкції. Такий підхід дозволяє на етапі проектування уникнути значної частини тривалих і коштовних втомних...
65488. Окупаційний режим та єврейське населення Дніпропетровщини 1941-1943 роки 218.5 KB
  Трагедія єврейського населення Дніпропетровській області не знайшла ще повномасштабного відпрацьовування хоча її фактична сторона може являти собою вагомий додаток до характеристики окупаційної політики нацистів стосовно представників даної національності.
65489. ТЕРМОЕЛЕКТРИЧНИЙ ПЕРЕТВОРЮВАЧ З КЕРОВАНИМ ПРОФІЛЕМ ТЕМПЕРАТУРНОГО ПОЛЯ 648 KB
  Тому підвищення точності вимірювання температури – актуальна та важлива наукова і практична задача вирішення якої може дати значний економічний ефект. Аналіз показує що точність приладів вимірювання температури росте однак похибка вимірювання температури зменшується мало бо у вимірювальному...
65490. Вплив бобово-злакових травосумішей на родючість та протиерозійну стійкість дерново-підзолистого еродованого ґрунту західного Передкарпаття 305 KB
  Для досягнення цієї мети передбачалось вирішити наступні завдання: встановити ґрунтозахисну ефективність багаторічних бобовозлакових травостоїв та їх вплив на стік і змив ґрунту; виявити зміни агрохімічних і воднофізичних показників родючості ґрунту в процесі залуження...