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

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


 

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

35663. Чернігівська кераміка. Особливості її форми та колориту 1.77 MB
  До побутових художніх керамічних виробів належать полив’яні глиняні яйця так звані писанки широко розповсюджені на Русі в тому числі і в Чернігові. У формах керамічних виробів того часу помітні прототипи форм і елементів декору гончарних виробів наступних віків горщик макітра миска. У формах керамічних виробів того часу помітні прототипи форм і елементів декору гончарних виробів наступних віків горщик макітра миска. Розпис ангобами в оздобленні глиняних виробів набув широкого розповсюдження в ХVІ–ХVІІ ст.
35664. Вишивка атласними стрічками. Картина Кошик з квітами 1.69 MB
  Його мета полягає в тому щоб з’ясувати якої вони думки щодо того якою повинна бути обрана мною картина. Аналіз об’єктіваналогів Ця картина приваблює мене своєю кольоровою гамою у поєднанні з ніжним віддтінком тканини. Ця картина приваблює мене своїми дрібними деталями тобто вони виконані францюзькими вузликами.
35665. Вязання крючком. Творчий проект 208.84 KB
  Відповідно до метиоб’єкту і предмету роботи були поставлені такі завдання: Проаналізувати та теоретично обґрунтувати особливості в’язання крючком. Висока якість виконання речей з могил коптів дозволяє вважати що техніка в'язання була відома набагато раніше. У 1867 році Вільям Фелкін висунув гіпотезу що в'язання було відоме ще за часів Троянської війни.
35666. Технологія пошиття повсякденної спідниці 64.07 KB
  Але де взяти нову спідницю щоб вона була не тільки модна але і подобалася б у всіх деталях добре сиділа на фігурі і була не дуже дорога Найкраще зшити її самої. Мета: Зшити спідницю. Завдання: 1 Навчитися шити спідницю 2 Ознайомитися з технологією пошиття спідниці 3 Зшити спідницю. Мистецтво шиття Для того щоб зшити спідницю потрібно виконати кілька етапів.
35667. Випалювання сови. Творчий проект 2.23 MB
  Випалювання сови Хід проектування У ході проектування свого виробу я повинен пройти такі етапи: І. Щоправда я вимушений був розчаруватись бо не мав спеціального пристрою для випалювання по дереву. І коли у школі задали домашнє завдання зробити якийнебудь виріб то одразу ж згадав про випалювання і прийшовши додому взявся за роботу. Серед багатьох художніх ремесел що з обробкою дерева окреме місце посідає декоративне випалювання.
35668. Вышитая открытка. Творческий проект 1.08 MB
  3 Минимаркетинговое исследование Проведя минимаркетинговое исследование направленное на выбор объекта проектирования выяснилось что 5 проголосовало за мягкую игрушку 15 за изготовление открытки техникой скрапбукинг а остальные проголосовали за изготовление вышитой открытки. По большому счету это были не совсем обычные открытки не представляющие большой культурной ценности. Кроме того в тоже время а именно к концу 19го века стали очень популярны фото открытки. Привнеся в европейскую традицию чтото свое отечественные...
35669. Театрализованные игры. Исследовательская работа 965.67 KB
  Что такое театрализованная игра. ОБЪЕКТ ИССЛЕДОВАНИЯ Игра. Что такое театрализованная игра. Он хочет играть играет всем и познаёт окружающий мир прежде всего и легче всего в игре игрой.
35670. Виготовлення спідниці. Творчий проект 586.77 KB
  Іспанія епохи Відродження була в той момент законодавцем мод і вводить в гардероб каркасний костюм. Спідниці шиються на спеціальному щільному чохлі з металевими або деревяними обручами різних розмірів. Вузька в талії, підігнана до корсета, спідниця розширюється донизу, облягаючи конусоподібний каркас (вертюгаден) без єдиної складкиитки 5 грн –1 моток 1 моток 5 грн Прикраси 3 грн –1 шт...