20613

Устранение общих подвыражений

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

2 Удаление бесполезного кода Допустим имеем следующую последовательность инструкций 3 Оптимизация циклов Пример 1: Пусть имеем цикл while i n2 Возможно модернизировать в следующую последовательность инструкций t:=n2 while i t Пример 2: while i t a:=b2 при условии что b не изменяется в теле цикла данную последовательность инструкций можно заменить на: a:=b2 while i t Метод перемещения кода заключается в выносе перед циклом выражений не изменяющихся в процессе его выполнения. 4 Переменные индукции и снижение стоимости 5 Оптимизация...

Русский

2013-07-31

92 KB

1 чел.

Лекция №14.

Устранение общих подвыражений

1) Распространение копий

Использование после инструкции вида f := g переменной g  вместо f, где это возможно.

Переменная х на выходе оказалась не живой, следовательно ее можно удалить.

Пример:

после оптимизации избавились от дорогостоящей операции сложения.

2) Удаление бесполезного кода

Допустим, имеем следующую последовательность инструкций

3) Оптимизация циклов

Пример 1:

Пусть имеем цикл

while i<n-2

Возможно модернизировать в следующую последовательность инструкций

t:=n-2

while i<t

Пример 2:

while i<t

a:=b*2

при условии, что b не изменяется в теле цикла, данную последовательность инструкций можно заменить на:

a:=b*2

while i<t

Метод перемещения кода заключается в выносе перед циклом выражений, не изменяющихся в процессе его выполнения.

4) Переменные индукции и снижение стоимости

5) Оптимизация базовых блоков на основе дагов

Пример:

Пусть имеется следующая последовательность инструкций

a:=b+c

b:=a-d

c:=b+c

d:=a-d

При условии, что b на выходе не является живой переменной после оптимизации данную последовательность можно заменить на следующую

a:=b+c

d:=a-d

c:=d+c

Из дага удаляются все корни (т.е. узлы без предков), которые не имеют живых переменных или таковые переменные вписанные как дополнительные в существующие узлы.

6) Использование алгебраических тождеств

  1.  х+0=х-0=0+х=х
  2.  х/1=х*1=1*х=х
  3.  х**2=х*ч
  4.  х*2=2*х=х+х
  5.  замена констант

Пример:

a:=b+c

b:=b-d

c:=c+d

e:=b+c

e:=b+c    b:=b-d

e:=b-d+c    a:=b+c

e:=a-d

После выполненных преобразований исходная последовательность инструкций примет вид:

a:=b+c

c:=c+d

e:=a-d

7)Рассмотрение циклов в графах потоков

Узел d графа потока доминирует над узлом n, если любой путь из начального узла графа потока в узел n проходит через d.

d    dom    n

Таким образом, вход в цикл доминирует над всеми узлами цикла.


 

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

12798. ПОЛЯРИЗАЦИЯ СВЕТА. Естественный и поляризованный свет 296 KB
  ЛАБОРАТОРНАЯ РАБОТА № 35 ПОЛЯРИЗАЦИЯ СВЕТА Естественный и поляризованный свет Свет является электромагнитной волной т.е. волной в которой происходят колебания векторов и вектор напряженности электрического поля вектор напряженности магнитного поля...
12799. Кодирующее устройство для кода Файра 272.13 KB
  Расчётнопояснительная записка к курсовой работе по дисциплине: Передача информации Тема: Кодирующее устройство для кода Файра. Аннотация. Курсовая работа по курсу Передача информации. Преподаватель: Каевченко Михаил Антонович. Авт
12800. ПРЕДСТАВЛЕНИЕ И ЗАПИСЬ ДВОИЧНЫХ ЧИСЕЛ 687 KB
  Лабораторная работа № 1 ПРЕДСТАВЛЕНИЕ И ЗАПИСЬ ДВОИЧНЫХ ЧИСЕЛ Цель работы: Изучить правила перевода чисел из одной системы исчисления в другую. Изучить способы кодирования двоичных чисел. Изучить формы представления двоичных чисел а также способы перевода одно
12801. ИЗУЧЕНИЕ РАБОТЫ ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ. ПРОЕКТИРОВАНИЕ КОМБИНАЦИОННЫХ ЛОГИЧЕСКИХ СХЕМ 477.5 KB
  Лабораторная работа № 2 ИЗУЧЕНИЕ РАБОТЫ ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ. ПРОЕКТИРОВАНИЕ КОМБИНАЦИОННЫХ ЛОГИЧЕСКИХ СХЕМ Цель работы: Изучить работу базовых логических элементов и основ построения различных комбинационных схем. Краткие теоретические сведения В ЭВМ
12802. ИЗУЧЕНИЕ СЛОЖНЫХ ЛОГИЧЕСКИХ ВЫСКАЗЫВАНИЙ 409.5 KB
  Лабораторная работа № 3 ИЗУЧЕНИЕ СЛОЖНЫХ ЛОГИЧЕСКИХ ВЫСКАЗЫВАНИЙ Цель работы: Изучить основы алгебры логики и составления сложных логических выражений. Краткие теоретические сведения Как и фундаментальные операции И ИЛИ и НЕ более сложные функции также мо...
12803. Реконструкция сиропного отделения при приготовлении помадных конфет производительностью 27 т/сут 1.78 MB
  Кондитерские изделия по своим вкусовым достоинствам, питательной ценности и усвояемости являются высококачественными продуктами питания, пользующиеся большим спросом у населения. Эта продукция широко представлена в торговле и общественном питании во всех населенных пунктах страны, но спрос на нее все не ослабевает
12804. ИССЛЕДОВАНИЕ ОДНОРАЗРЯДНЫХ СУММАТОРОВ И СИНТЕЗ МНОГОРАЗРЯДНЫХ СУММАТОРОВ 529.5 KB
  Лабораторная работа № 5 ИССЛЕДОВАНИЕ ОДНОРАЗРЯДНЫХ СУММАТОРОВ И СИНТЕЗ МНОГОРАЗРЯДНЫХ СУММАТОРОВ Цель работы: Изучить принципы работы одноразрядного сумматора и принципы построения многоразрядных сумматоров. Краткие теоретические сведения Сумматором
12805. ИЗУЧЕНИЕ РАБОТЫ ПОСЛЕДОВАТЕЛЬНЫХ И НАКАПЛИВАЮЩИХ СУММАТОРОВ 603 KB
  Лабораторная работа № 6 ИЗУЧЕНИЕ РАБОТЫ ПОСЛЕДОВАТЕЛЬНЫХ И НАКАПЛИВАЮЩИХ СУММАТОРОВ Цель работы: Изучить принципы построения последовательных и накапливающих сумматоров. Краткие теоретические сведения Последовательное суммирование многоразрядных чисел ...
12806. ИЗУЧЕНИЕ РАБОТЫ ЦИФРОВОГО ДВОИЧНО-ДЕСЯТИЧНОГО КОМБИНАЦИОННОГО СУММАТОРА 924 KB
  Лабораторная работа № 7 ИЗУЧЕНИЕ РАБОТЫ ЦИФРОВОГО ДВОИЧНОДЕСЯТИЧНОГО КОМБИНАЦИОННОГО СУММАТОРА Цель работы: Изучить принципы построения двоичнодесятичных комбинационных сумматоров. Краткие теоретические сведения Для построения двоичнодесятичного с