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

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


 

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

84411. DIE WIRTSCHAFT DER BRD 20.33 KB
  Deutschland gehört zu den führenden Industrieländern der Welt. Mit ihren wirtschaftlichen Leistungen nimmt sie den dritten Platz und im Welthandel den zweiten Platz ein. Die Bundesrepublik Deutschland gehört zu der Gruppe dersieben großen westlichen Industrieländern.
84412. Wien. Die Geschichte Wiens 19.76 KB
  Der Stephansdom ist mit seiner Mischung von Stilen für Wein und sein Völker und Kulturgemisch symbolisch. Unter den zahlreichen Gebäuden und Kirchen Wiens sind drei, die man wegen ihren historischen und kulturellen Bedeutung kennen sollte: die Karlskirche...
84413. IM THEATER 19.02 KB
  Durch die Glastür trat ich in die Vorhalle und gab meine Garderobe ab. Kaum war ich damit fertig, da klingelte es auch schon zum ersten Mal. An den Wände im Foyer hingen Photos berühmter Schauspieler. Bevor ich den Zuschauerraum betrat, kaufte ich mir noch ein Programmheft.
84414. MEINE SCHULPRAXIS 19.36 KB
  Meiner Meinung nach ist der Lehrerberuf sehr schön, aber auch sehr schwer und verantwortungsvoll. Der Lehrer muss umfangreiche Kenntnisse haben. Es ist aber nicht leicht, das Interesse der Schüler zum Lernen zu erwecken.
84415. INTERNET IN UNSERE LEBEN 19.12 KB
  Das Surfen in sozialen Netzwerken wie Facebook oder Twitter kostet Zeit. Deshalb sperren einige Unternehmen ihren Mitarbeitern den Zugang. Andere hingegen nutzen die Möglichkeiten der Netzwerke.
84416. DER STAATSAUBAU DER UKRAINE 17.5 KB
  Die Ukraine ist ein demokratischer, unabhängiger Staat. Am 24. August 1991 wurde die Unabhängigkeit der Ukraine verkündet. Die Staatssymbole der Ukraine sind die Nationalhymne, das Staatswappen und die Nationalflagge.
84417. Технология возделывания ярового ячменя и кукурузы 214 KB
  Комплексная механизация сельскохозяйственного производства — такая форма организации труда, при которой все основные и вспомогательные процессы в какой-либо отрасли хозяйства выполняются машинами или механизмами в определенной последовательности.
84418. Экономический анализ хозяйственной деятельности в ЗАО «Куйбышевское» 71.73 KB
  Важнейшая задача сельского хозяйства состоит в обеспечении населения страны продовольствием. В условиях формирования рыночной экономики эта задача может быть решена только путём повышения экономической эффективности сельскохозяйственного производства.
84419. АНАЛИЗ ГОСУДАРСТВЕННОГО БЮДЖЕТА УКРАИНЫ 101.31 KB
  Первый заместитель главы администрации президента Ирина Акимова недавно заявила что объём теневой экономики в Украине составляет около 500 млрд грн. Запланирован рост по следующим статьям доходов бюджета: собственные поступления бюджетных учреждений 41 млрд грн или 244...