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


 

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

19198. Взаимодействие рентгеновского излучения с твердым телом (фотоэффект, эффект Комптона) 353 KB
  Лекция 10 Взаимодействие рентгеновского излучения с твердым телом фотоэффект эффект Комптона. Сечение фотоэффекта и его связь с линейным коэффициентом поглощения рентгеновского излучения. Расчет массового коэффициента поглощения для полиатомных образцов. Полезно
19199. Характеристики электронных пучков. Источники ускоренных электронов. Термоэмиссионные и автоэмиссионные катоды и их характеристики 141 KB
  Лекция 11 Характеристики электронных пучков. Источники ускоренных электронов. Термоэмиссионные и автоэмиссионные катоды и их характеристики. Основные узлы и характеристики электронной пушки. Электронные пучки принято разбивать на два класса: Электронные пучки ...
19200. Параметры ионных источников. Конструктивные элементы ионных источников. Дуоплазматрон и ионный источник Пеннинга 113.5 KB
  Лекция 12 Параметры ионных источников. Конструктивные элементы ионных источников. Дуоплазматрон и ионный источник Пеннинга. Ионный источник – устройство для получения в вакууме ионного пучка – пространственно сформированного потока ионов скорость направленного дви...
19201. Магнитные масс-анализаторы. Понятие разрешения по массам. Квадрупольные масс-анализаторы 155.5 KB
  Лекция 13 Магнитные массанализаторы. Понятие разрешения по массам. Квадрупольные массанализаторы. Для выделения из ионного пучка ионов нужной массы используются массанализаторы массспектрометры. Наиболее часто в установках элементного анализа применяются магнит...
19202. Основные понятия вакуумной техники. Длина свободного пробега ионов при различных давлениях 71 KB
  Лекция 14 Основные понятия вакуумной техники. Длина свободного пробега ионов при различных давлениях. Адсорбция остаточных газов на поверхности образца. Методы очистки поверхности. Состояние разреженного газа при давлении ниже атмосферного принято называть вакуумом....
19203. Детекторы заряженных частиц – канальные электронные умножители и микроканальные пластины. Поверхностно-барьерный детектор 128.5 KB
  Лекция 15 Детекторы заряженных частиц – канальные электронные умножители и микроканальные пластины. Поверхностнобарьерный детектор. Твердотельный рентгеновский спектрометр. В настоящее время наиболее распространенными детекторами заряженных частиц являются канал...
19204. Основные понятия вакуумной техники. Длина свободного пробега ионов при различных давлениях. Адсорбция остаточных газов на поверхности образца 123 KB
  Лекция 16 Основные понятия вакуумной техники. Длина свободного пробега ионов при различных давлениях. Адсорбция остаточных газов на поверхности образца. Методы очистки поверхности. Состояние разреженного газа при давлении ниже атмосферного принято называть вакуумом....
19205. ОСНОВНЫЕ ПОНЯТИЯ И СВОЙСТВА ПЛАЗМЫ 254 KB
  Лекция № 1. Плазма – коллективное состояние заряженных частиц ионизованного газа. Пространственные и временные масштабы разделения зарядов в плазме. Идеальная и неидеальная вырожденная плазма. Холодная газоразрядная горячая и релятивистская плазма. I. ОСНОВНЫ...
19206. Траектории заряженных частиц в однородных электрическом и магнитном полях 603 KB
  Лекция № 2. Траектории заряженных частиц в однородных электрическом и магнитном полях. Отклонение и фокусировка заряженных частиц в постоянном электрическом поле. Фокусировка в плоском и цилиндрическом конденсаторах. Электростатические энергоанализаторы. Фокусиро