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

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


 

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

60719. Правила ввода простого текста 85.5 KB
  Задачи: сформировать у учащихся представления о правилах ввода простого текста в текстовом редакторе Microsoft Word. актуализировать и углубить знания о возможностях текстового редактора Microsoft Word.
60720. Редактирование введенного текста. Форматирование документа 276.5 KB
  В поле Шрифт выбирается тип шрифта шрифты типа TrueType выглядят одинаково на экране и на печати рядом с их именем установлены значки. В поле Начертание выбирается начертание шрифта...
60721. Создание, переименование, перемещение, копирование, удаление, распечатка объектов Windows 235 KB
  Скажите что нужно сделать если вы хотите создать папку на рабочем столе Если вам нужно переименовать папку Если вы хотите переместить папку Если вы хотите копировать папку...
60722. Текстовый редактор Microsoft Word. Назначение. Настройки 382 KB
  Цель: дать понятие учащимся о текстовом редакторе Microsoft Word его назначение и о его настройки. Задачи: сформировать у учащихся представления о настройках текстового редактора Microsoft Word.
60723. Меню, панели «Стандартная», «Форматирование» 296 KB
  С помощью этой панели можно быстро и удобно выполнять операции по изменению шрифта вида выравнивания абзацев включать режим ввода списка оформлять обрамление текста его границы...
60724. Классификация программ растровой графики 2.42 MB
  Цель: дать учащимся понятие классификации программ растровой графики. И какие существуют виды компьютерной графики. Что такое векторная графика Назовите достоинства и недостатки векторной графики.
60725. Пример решения жизненной задачи 156.5 KB
  Это разнообразило бы отдых учащихся да и сами вы не прочь прокатится с горки. Итак у вас появляется жизненная задача построение ледяной горки. Основная часть Итак приступаем к построению ледяной горки.
60726. Проверка знаний по теме: «Microsoft Excel и моделирование в задачах управления» 377 KB
  Цель: проверка знаний учащихся по данному разделу Электронная таблица Microsoft Excel и моделирование в задачах управления. Закрепить на практике умения учащихся работать в электронной таблице Microsoft Excel.
60727. Моделирование биологической системы 1.27 MB
  Цель: дать понятие учащимся о моделирование биологической системы Задачи: сформировать у учащихся представления о моделировании биологической системы. актуализировать и углубить знания о моделях и моделировании.