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


 

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

39681. КОММУНИКАЦИЯ В РАЗЛИЧНЫХ СФЕРАХ ОБЩЕСТВЕННОЙ ЖИЗНИ 57.5 KB
  Различие состоит в том что основной функцией PR является управленческая и приоритет отдается межличностной коммуникации. На отдельных предприятиях для внутренней коммуникации имеются замкнутые системы радиовещания и телевидения. Результативность коммуникации складывается из многих компонентов. Она зависит и от выбора слов и речевых образцов принятых в деловой сфере коммуникации и от правильная ориентация на тип коммуникации межличностной внутригрупповой или массовой.
39682. Коммуникаторы и коммуниканты как субъекты коммуникации 63.5 KB
  Исходным понятием для изучения коммуникативной личности понятие личность. Множественность подходов и многообразие теорий и концепций личности раскрывает сложность проблемы обоснования социально значимых признаков личности. Социологическая концепция личности сформировалась в конке 19 в начале 20 века. В зависимости от придаваемой роли стадиям процесса формирования личности различаются подходов в исследовании личности.
39683. АУДИТОРИЯ И КОММУНИКАЦИЯ 28 KB
  Информация пронизывает весь процесс управления все его стадии. В такой системе обратная связь проявляется как реакция на управленческое действие которое осуществляет субъект управления в виде системы информации о состоянии управляемого объекта и его изменении в соответствии с заданной программой. Наличие такой обратной связи позволяет корректировать управленческие действия в процессе управления социальным развитием. Таким способом через обратную связь объект управления воздействует на субъект управления и оперативно оценивается...
39684. Основные этапы развития отечественной отоларингологии 347.5 KB
  Конец эпохи средневековья и период Возрождения характеризуются заметным прогрессом в медицине и прежде всего в развитии анатомии человека в том числе и анатомии уха носа и горла. К первым отечественным руководствам по болезням уха носа и горла следует отнести соответствующий раздел капитального труда по хирургии выдержавшего с 1807 по 1823 г. описана операция на лобных пазухах носа. Основой объединения болезней уха носа и горла в специальную дисциплину явилось анатомотопографическое единство этих органов их тесная физиологическая и...
39685. Проектирование технологических процессов 1.21 MB
  Задачами технологического проектирования являются определение условий изготовления изделий определение типа производства видов исходных заготовок проектирование технологического маршрута обработки выявление необходимых средств производства и порядка их применения определение себестоимости и трудоемкости изготовления изделий определение исходных данных для календарного планирования для организации технического контроля определение состава рабочей силы. Руководящая информация включает: стандарты устанавливающие требования к...
39686. ОСНОВЫ ПРОЕКТИРОВАНИЯ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ В МАШИНОСТРОЕНИИ 70 KB
  Общие принципы технической подготовки производства Рациональная организация производственного процесса невозможна без проведения тщательной технической подготовки производства. Техническая подготовка производства включает в себя следующее. 1 Конструкторскую подготовку производства.
39687. Расчетный метод определения точности 465 KB
  Блоксхема факторов влияющих на качество обрабатываемой заготовки на настроенном станке в общем виде представлена на рис. К числу первичных погрешностей обработки относятся: погрешность установки заготовки; погрешность от упругих деформаций технологической системы; погрешность настройки станка; погрешность от износа режущего инструмента; погрешность изза геометрической неточности станка и изготовления режущего инструмента; погрешность изза температурных деформаций системы; погрешность изза остаточных напряжений в заготовке....
39688. Современные перспективные направления повышения точности 61 KB
  Все сказанное определяет виртуальный образ технологической системы. Следовательно технологическая система станка должна быть оснащена соответствующими вычислительными средствами возмещающими деятельность человека и соответствующую часть технологической системы. Вычислительная система станка кроме традиционных задач управления процессом обработки должна выполнять следующие задачи: оценку точностных возможностей технологической системы на основе информации полученной подсистемами диагностики состояния станка и инструмента; оценку...