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


 

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

10704. Хвильовий Микола. Я (Романтика) Цвітові яблуні 19.09 KB
  Я Романтика Хвильовий Микола Цвітові яблуні З далекого туману з тихих озер загірної комуни шелестить шелест: то йде Марія. Я виходжу на безгранні поля проходжу перевали і там де жевріють кургани похиляюсь на самотню пустельну скелю. Я дивлюсь в даль. Тоді дума за
10705. Сом - Вишня Остап 15.88 KB
  Сом Вишня Остап За славним містом Енськом на Харківщині тече річка Оскіл що впадає у Північний Донець. її заплава розбивається на кілька рукавів зарослих густими очеретами верболозом соковитою травою. І скрізь силасиленна озеречок вкритих густою зеленою ряскою..
10706. Мина Мазайло - Куліш Микола - Комедія 17.74 KB
  Мина Мазайло Куліш Микола Комедія Перша дія 1 Розмова Рини Мазайло з її подругою Улею з якої зясовується що у родині Мазайла відбуваються сварки через сторичне питання. Мокій Мазайло дуже захоплюється українською мовою і хоче переробити своє прізвище на МазайлоКв...
10707. Лісова пісня - Українка Леся - Драма-феєрія в 3-х діях 16.09 KB
  Лісова пісня Українка Леся Драмафеєрія в 3х діях Пролог Старий ліс на Волині дика і таємнича місцина. Початок весни. З лісу вибігає Той що греблі рве. Вік перемовляється з потерчатами та Русалкою яка нагадує йому про своє кохання дорікає зрадою. Водяник сварить Рус...
10708. Камінний господар - Леся Українка 14.25 KB
  Камінний господар Леся Українка Камінний господар поетична драма обробка Лесі Українки в якій уперше в українській літературі зображається образ чоловікаспокусника. Імпульсом до написання твору стала пушкінська драма Камінний гість. У творі було вкладено відм
10709. Микола Джеря - Нечуй-Левицький Іван 16.56 KB
  Микола Джеря Нечуй-Левицький Іван Понад самим берегом вється в траві стежка через усе село. Підеш тією стежкою глянеш кругом себе і скрізь бачиш зеленезелене море верб садків конопель соняшників кукурудзи та густої осоки. От стеляться розложисті як скатерть зел
10710. Маруся Чурай - Костенко Ліна 20.11 KB
  Маруся Чурай Костенко Ліна РОЗДІЛ І Якби знайшлась неопалима книга Під час пожежі у Полтаві 1658 року згоріли всі документи міських судових справ. А можливо серед них могла б знайтися справа Марусі Чурай. Справа ця розглядалася на одному з судів з приводу вбивства козака...
10711. Fata morgana - Коцюбинський Михайло - (З сільських настроїв) - Повість 19.4 KB
  Fata morgana Коцюбинський Михайло З сільських настроїв Повість ЧАСТИНА ПЕРША Проходячи біля зруйнованої сахарні Андрій Волик згадує своє колишнє життя. Він працював на фабриці та отримував кожного місяця 13 карбованців. Тепер сахарня стоїть пусткою але Андрій сподіває...
10712. Три зозулі з поклоном - Тютюнник Григір – Новела - Любові всевишній присвячується 14 KB
  Три зозулі з поклоном Тютюнник Григір Новела Любові всевишній присвячується Повертаючись додому хлопець помічає що сусідка Марфа Яркова щось дуже пильно його розглядає. Мати пояснює що Марфа любила його батька а він на нього схожий. Потім мати згадує що Марфа за