Реферат: Оптимизация программ

Алгоритм исключения лишних операций просматривает опера­ции в порядке их появления. Если i-я триада лишняя (уже име­ется идентичная j-я триада), то она заменяется триадой (SAME,j,0), где операция SAME ничего не делает и не порождает никаких команд при генерации. Чтобы следить за внутренней за­висимостью переменных и триад, им в соответствие ставятся числа независимости по следующим правилам:

1) Вначале для переменной А число независимости dep(А) равно нулю, так как ее начальное значение не зависит ни от од­ной триады.

2) После обработки i-й триады, в которой переменной А присваивается некоторое значение, dep(А) заменяется на i, так как ее новое значение зависит от i-й триады.

3) При обработке i-й триады ее число независимости dep(i) равно 1+ (максимальное из чисел зависимости ее операндов).

Числа зависимости используются следующим образом:если i-я триада идентична j-й триаде (j<i), то i-я триада считается лишней, если dep(i)=dep(j).

Алгоритм исключения лишних операций для каждой триады де­лает следующее:

1. Если операнд ссылается на триаду вида (SAME,j,0), то он заменяется на (j).

2. Вычисляется dep(i):= число независимости i-й триады, равное 1+(максимум чисел независимости ее операндов).

3. Если существует идентичная j-я триада, причем j<i и dep(i)=dep(j), то i-я триада лишняя и заменяется на (SAME,j,0).

4. Если i-я триада присваивает значение элементу массива В или простой переменной В, то dep(В) получает значение, равное

i.

4.4.2. Замена переменных в операторах условного перехода и устранение неиспользуемых определений

В результате сокращения глубины операции рекурсивная программная переменая (определенная через саму себя), являюща­яся управляющей в операторе условного перехода, может быть за­менена в нем генерируемой переменной t(mt- идентификатором).

Это в свою очередь может привести к тому, что рекурсивно опре­деленная программная переменная использоваться в блоке не бу­дет и само определение может быть устранено.

Определение не используется и может быть устранено, если результат определения не является операндом ни одного операто­ра рекурсивного определения и результат этого последнего не используется ни в каком другом операторе.

Существование неиспользуемых определений до оптимизации является ошибкой программиста. Но после оптимизации такие оп­ределения могут возникнуть как результат перестановки и изме­нения отдельных операторов в процессе оптимизации.

Для данного определения в данном блоке производится поиск использования этого определения во всех последующих командах блока и во всех блоках, которые могут следовать за ним.Поиск прекращается, когда находится оператор, использующий данное определение в качестве аргумента. Если такой оператор в данном и последующих блоках найден не будет, то определение считается неиспользуемым и устраняется.

Как только неиспользуемое определение устранено, все опе­раторы, от которых зависел устраненный оператор, если они ниг­де больше не используются, могут быть устранены.

4.4.3 Устранение бесполезных операторов и переменных

Если блок содержит такой оператор S, что переменная, ко­торой присваивается значение в S, не является активной после этого оператора, то S - бесполезный оператор. Иными словами,S

- бесполезный оператор, если он присваивает значение перемен­ной, которая не является выходной и на которую нет ссылки в последующих операторах.

Переменная А называется активной после выполнения опера­тора Si, если

- ей присвоено значение оператором Si;

- ей не присвоены значения операторами Si+1,...Sj;

- на нее ссылается оператор Sj+1.

Если оператор Si присваивает значение переменной А и она неактивна после момента i, то

- при i>0 можно удалить Si из P

- при i=0 можно удалить A из I

Например, пусть B=(P,I,U), где I= A,B,C , U= F,C  и P состоит из

F:=A+A

G:=F*C

F:=A+B

G:=A*B

Второй оператор бесполезен, т. к. его область действия пуста. Таким образом, одно применение преобразования устране­ния бесполезных операторов отображает B в B1=(P1,I,U), где P1 состоит из

F:=A+A

F:=A+B

G:=A*B

Теперь в B1 бесполезна входная переменная C и первый опе­ратор. Применив то же преобразование, можно получить B2=(P2,A,B,U), где P2 состоит из

F:=A+B

G:=A*B

4.5. Экономия памяти

Это способ улучшения программы за счет уменьшения объема памяти, отводимой под информационные объекты программы в каж­дом из ее возможных исполнений.

В соответствующую группу оптимизаций входят следующие преобразования:

- глобальная экономия памяти, т.е. совмещение по памяти не существующих одновременно статических переменных;

- изменение области существования автоматической перемен­ной;

- перемещение оператора отведения памяти под управляемую переменную по пути, ведущему к конечному оператору программы;

- совмещение по памяти динамических информационных объек­тов, например, замена стека локальных переменных или парамет­ров, вовлекаемых в рекурсию, одинарной переменной. Примером выполнения этого преобразования является замена функции

цел функция  F(N,M)

начало

целое K;

если N=M

то  F:=1

иначе

начало

K:=M+1; F:=F(N,K)*K конец

конец

на функцию

цел функция F(N,M) начало

цел функ G(Z);

начало

целое K

если N=Z

то  F:=1

иначе

начало

K:=Z+1; F:=F(K)*K конец

конец

F:=G(N) конец;

4.6. Сокращение программы

При данном способе улучшение программы достигается за счет сокращения ее размера.

К преобразованиям этого типа относится чистка линейного участка, при которой в начальную (или в конечную) его вершину выносятся и заменяются на один экземпляр имеющиеся на всех пу­тях в блоке одинаковые конструкции. Например,

если A>0

то

начало

X:=X+3

Z:=2 конец

иначе начало X:=X+3 W:=X+4 конец

преобразуется к виду

X:=X+3 если A>0 то Z:=2 иначе W:=X+4

В эту же группу входит и запроцедуривание - поиск в прог­рамме похожих фрагментов и формирование их в виде процедуры.

4.7. Вставка псевдоблока

В процессе оптимизации операторы, сдвигаемые из блоков, собираются в псевдоблок. После оптимизации области Rk операто­ры псевдоблока должны быть вставлены в программу так, чтобы они выполнялись до (после) выполнения операторов области Ri.

Для того, чтобы операторы псевдоблока выполнялись на всех входных (выходых) путях области Rk, они должны вставляться во все блоки, непосредственно предшествующие (следующие) области либо из псевдоблока должен быть сформирован блок ,который бу­дет вставлен на все входные (выходные) пути области Rk.

Вставка операторов в существующие блоки или формирование из псевдоблока фактического блока выполняется по следующему алгоритму (алгоритм рассматривается для операторов, сдвинутых назад на входные пути, для операторов, сдвинутых вперед, алго­ритм аналогичен ):

1) операторы вставляются во все блоки, непосредственно предшествующие области, которые имеют только один не­посредственно следующий блок. Вставляемые операторы записыва­ются перед оператором перехода.

2) из псевдоблока создается формальный блок, который вставляется на всех входных путях, идущих от непосредственно предшествующих блоков, имеющих несколько преемников.

3) если входной блок программы принадлежит области Rk, то псевдоблок формируется в формальный блок и ставится на неявном пути между внешним и вызывающим оператором и начальным блоком.

Это соответствует созданию нового блока.

5.Набор и последовательность оптимизирующих преобразований

Каждый из способов оптимизации может быть реализован в виде отдельного преобразования. В то же время практика оптими­зирующей трансляции показала, что все эти способы оптимивации, не совпадая друг с другом, реализуют во многом совпадающие процессы обработки программы, в основе которых лежит небольшое число более элементарных и фундаментальных преобразований программ.

Поэтому в реальных оптимизирующих трансляторах разнооб­разные наборы способов оптимизации программ сводятся к приме­нению более простых преобразований в их сочетании друг с дру­гом и с учетом их совокупного влияния на транслируемую прог­рамму.

Реально используемые наборы оптимизирующих преобразований не обладают свойством , позволяющим не следить за порядком применения преобразованнй. Обычно существуют ситуации, когда применение одного преобразования закрывает возможяости приме­нения другого (в этом случае говорят, что первое преобравова­ние обладает тупиковостью по отношонию ко второму) или, наобо­рот, приводит к новым возможностям другого преобразования (т. о. обладает повторностью по отношению к нему).

Поэтому важным для имеющегося набора оптимизирующих пре­образований (с точки зрения качества получаемой программы) представляется выбор порядка применения преобразований из на­бора. Нужно стремиться к тому, чтобы в последовательности при­менения любое преобразование не предшествовало преобразованию, по отношению к которому оно тупиково, но предшествовало преоб­равованию, по отношению к которому оно повторно.

Можно дать некоторые частные рекомендации по оптимизации циклов и линейных участков.

Оптимизацию циклов можно осуществлять в три прохода, расположенных между проходом обычного анализа, в котором полу­чается внутреннее представление исходной программы, и прохо­дом, генерирующим объектный код:

1) анализ циклов - выявление циклов, подлежащих оптимиза­ции и получение необходимой для оптимизации информации;

2) вынесение за границу циклов инвариантных операций;

3) замена сложных операций.

Свертка или исключение лишних операций на линейных участ­ках осуществляются непосредственно перед или в процессе обра­ботки инвариантных операций.

Литература

1. С.Я.Виленкин, Э.А.Трахтенгерц. Математическое обеспе­чение управляющих вычислительных машин. М.: Энергия,

1972.

2. Д.Грис.  Конструирование компиляторов для цифровых вы­числительных машин. М.: Мир, 1975.

3. А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978.

4. В.Н.Касьянов, И.В.Поттосин. Методы построения трансля­торов. Новосибирск, издательство "Наука", 1986.

5. В.Н.Касьянов. Оптимизирующие преобразования программ.

М.: Наука, 1988.