Оптимизация программ

Содержание

1.Назначение и цели оптимизации

2.Промежуточный язык

3.Элементы топологии программы

3.1. Блок (линейный участок)

3.2. Сильно связанная область

4.Способы оптимизации

4.1. Разгрузка участков повторяемости

4.1.1 Сдвиг инвариантных операторов

4.1.2. Сокращение глубины операции

4.2. Упрощение действий

4.2.1. Удаление индуктивных переменных и выражений

4.2.2. Замена сложных операций на более простые

4.2.3. Исключение избыточных выражений

4.2.4. Прочие преобразования

4.3. Реализация действий

4.3.1. Подстановка (свертка)

4.4. Чистка программы

4.4.1. Устранение идентичных операторов

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

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

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

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

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

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

1. Назначение и цели оптимизации

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

- оптимизирующей частью транслятора.

Оптимизирующая часть транслятора выполняет следующие

действия:

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

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

2. Промежуточный язык

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

во-первых, единицы действия программы в кодах команд слишком мелки, что уже само по себе затрудняет анализ,

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

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

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

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

а) операторы языка не должны быть слишком мелкими;

б) символы, идентификаторы и числа должны иметь фиксиро­ванный формат;

в) в строении операторов желательно отсутствие рекур­сивности;

г) должна сохраняться вся информация, необходимая для оптимизации, которая есть во входном языке;

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

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

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

(mi) код операции аргументы оператора,

где mi - указатель оператора, а также идентификатор ре­зультата команды при отсутствии его присваивания некоторой пе­ременной.

Необходимо различать переменные, введенные программистом (программные переменные),и переменные, генерируемые в процессе

трансляции на промежуточный язык (mi - идентификаторы). Между

определением программной переменной и ее использованием в ка­честве операнда существует следующая зависимость:

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

- если программная переменная определена и используется в области, то внутри области существует путь между определением переменной и каждым ее использованием;

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

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

1. Таблицы идентификаторов и констант с обычной информацией о переменных и константах.

2. Таблица блоков, определяющая номера блоков (блоки нуме-

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

3. Таблица последовательности операторов, определяющая ли­нейную последовательность операторов в блоке. Она содер­жит последовательность указателей операторов mi. Эта таблица необходима, поскольку один указатель может при­надлежать нескольким операторам.

3.Элементы топологии программы

3.1. Блок (линейный участок)

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

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

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

Формально модель линейного участка может быть представле­на следующим образом:

блок B - это тройка вида (P,I,U),где

(1) P - список операторов S1,S2,...Sn (n>=0),

(2) I - множество входных переменных,

(3) U - множество выходных переменных.

При этом оператором называется цепочка (в общем случае) вида

A <--QB1...Br,

где A,B1,...,Br - переменные,Q - операция.

Здесь оператор присваивает значение переменной А и ссыла­ется на B1,...,Br.

Если оператор Sj ссылается на А, то либо А--входная пере­менная, либо осуществлено присваивание ей значения некоторым оператором до Sj, (т. е. некоторым оператором Si,(i<j) . Таким образом, внутри ,блока все переменные, на которые ссылаются, к этому моменту определены либо внутренним образом как перемен­ные, которым присвоены значения, либо внешним как входные пе­ременные. Аналогично каждая выходная переменная либо является входной переменной, либо ей присвоено значение некоторым опе­ратором.

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

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

3.2. Сильно связанная область

Для каждого блока B=(P,I,U) можно найти ориентированный ациклический граф , представляющий этот блок. При этом каждый лист графа (концевая вершина) соответствует одной входной пе­ременной в I, а каждая его внутренняя вершина - оператору из

P. Граф отражает порядок выполнения операторов программы и да­ет более наглядное представление, чем линейная последователь­ность операторов.

Если вершины i и j графа соответствуют участкам i и j программы, то дуга идет из i в j, если

1) последний оператор участка i не является ни оператором перехода, ни оператором останова, а участок j следует в программе за участком i или

2) последний оператор участка i является оператором пере­хода на метку L, которой помечен первый оператор участка j.

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

Будем рассматривать сильно связанные области Ri, обладаю­щие следующими свойствами:

1) Ri является сильносвязанной областью, состоящей из множества блоков, каждый из которых предшествует сам себе и следует сам за собой внутри этого множества;

2) Ri != Rj;

3) для каждого i<j или пересечение Ri и Rj пусто, или Ri является подобластью Rj (включена в нее).

4. Способы оптимизации

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

Методы первой категории применимы почти к любому алгебра­ическому языку - ФОРТРАНу, АЛГОЛу, PL/1 и.т.д.

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

- разгрузка участков повторяемости;

- упрощение действий;

- реализация действий;

- чистка программы;

- экономия памяти;

- сокращение программы.

4.1. Разгрузка участков повторяемости

Такое название получил способ оптимизации, состоящий в вынесении вычислений из многократно проводимых (исполняемых ) участков программы на участки программы , редко проходимые.

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

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

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

Примеры.

а) Чистка вниз преобразует цикл

для K:=1, K+1 пока K<=100

цикл

начало

X:=X*K;

если Z>0 то Y:=sin(X);

иначе A[I]:=X+2;

конец

к виду

для K:=1, K+1 пока K<=100

цикл X:=X*K;

если Z>0 то Y:=sin(X);

иначе A[I]:=X+2;

б) Чистка вверх преобразует цикл

для K:=1, K+1 пока K<=100

цикл

начало

если Z>0 то Y:=1;

иначе Y:=Z+2;

X[K]:=X[K] - Y; конец

к виду

если Z>0 то Y:=1;

иначе Y:=Z+2;

для K:=1, K+1 пока K<=100

цикл X[K]:=X[K] - Y;

Примером чистки тела рекурсивной функции может быть сле­дующий:

тело рекурсивной функции

цел функция Ф(N)

начало

целые Z,W;

W:=1;

если X>0 то W:=Y;

если N<=0 то Ф:=1

иначе

начало

Z:=N-W; Ф:=Z*Ф(Z) конец

конец

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

цел функция Ф(N)

начало

целое N;

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

начало

целое Z;

если M<=0 то F:=1;

иначе

начало

Z:=M-W; F:=Z*F(Z) конец

конец

W:=1;

если X>0 то W:=Y;

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

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

Например, с помощью этих преобразований фрагмент

для K:=1, K+1 пока K<=100

цикл

начало

N:=A[K];

если N>0 то переход на L; N:=N*N;

L: если Z=0 то ВЫВОД(N); конец

N:=100;

может быть преобразован к виду:

для K:=1, K+1 пока K<=100

цикл

если Z=0 то

начало

N:=A[K];

если N>0 то переход на L; N:=N*N;

L: ВЫВОД(N); конец;

N:=100;

4.1.1 Сдвиг инвариантных операторов

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

Оператор инвариантен и может быть вынесен из блока, если он удовлетворяет следующим условиям:

1) сдвиг оператора не приводит к тому, что результат сдвигаемого оператора перемещается через оператор, в котором результат используется.

Например, для блока

(mi) * A,B

.

.

.

(mk) := C,(mi)

если ни A, ни B не определяются в области, то оператор mi может быть сдвинут вниз, но не может быть поставлен после опе­ратора mk.

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

(mi) := A,1

.

.

(mj) := A,10

.

.

(mk) := C,A

если больше никакой оператор после mj не присваивает зна­чение переменной A, то оператор mj может быть сдвинут вниз, но не может быть поставлен после оператора mk, операторами mi, а также вверх, но не выше оператора, использующего значение пе­ременной A, присвоенное оператором mi.

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

Таким образом, оператор инвариантен в области, если его операнды не зависят от места определения переменных в данной области.

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

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

сдвига операторов.

Рассмотрим условия, достаточные для сдвига операторов

I. Сдвиг оператора, не являющегося оператором присваива­ния, из области назад (на его входные пути) производится, если операнды оператора не зависят от места определения переменных в области, т.е.:

1) mi - идентификаторы, используемые в качестве аргумента оператора, не определены в блоке ни одним предшествующим опе­ратором;

2) программные переменные оператора не определены в об­ласти.

Если оба эти условия выполняются, то операнды оператора не зависят от места определения переменных в области.

II. Сдвиг оператора присваивания, из области назад (на его входные пути) производится, если:

1) mi - идентификаторы, используемые в качестве аргумента оператора, не определены в блоке ни одним предшествующим опе­ратором;

2) программные переменные, используемые в качестве опе­ранда оператора не определены в области;

3) блок является артикуляционным, т.е. лежит на пересече­нии всех входных или всех выходных путей сильно связанной об­ласти;

4) не существует другого определения или использования программной переменной на любом пути от входа в область до этого определения.

III. Сдвиг оператора, не являющегося оператором присваи­вания, из области вперед (на его выходные пути) производится, если:

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

2) программные переменные, используемые в качестве аргу­мента оператора не переопределяются ни на одном пути между оператором и точкой выхода из области;

3) mi - указатель, являющийся результатом действия опера­тора, не используется на пути между оператором и концом блока.

IV. Сдвиг оператора присваивания, из области назад (на его входные пути) производится, если:

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

2) программные переменные, используемые в качестве аргу­мента оператора не переопределяются ни на одном пути между оператором и точкой выхода из области;

3) блок является артикуляционным пунктом области;

4) не существует другого определения

программной переменной ни на одном пути между определением и

точкой выхода из области;

5) программная переменная не используется в области.

4.1.2. Сокращение глубины операции

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

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

Приведем пример сокращения глубины операции применительно к оператору t4:=K*10+I из n-го блока :

n-й блок

L:t4:=K*10+I t5:=t6+K z(t2):=z(t2)+x(t4)+y(t5) K:=K+1

переход на L

в результате выполнения этой операции оператор t4:=K*10+I сдвигается в (n-1)-й блок, а в n-м блоке он заменяется опера­тором t4:=t4+10:

(n-1)-й блок

. . .

t4:=K*10+I

n-й блок

L: z(t2):=z(t2)+x(t4)+y(t5)

K:=K+1 t4:=t4+10 t5:=t6+K переход на L

4.2. Упрощение действий

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

4.2.1. Удаление индуктивных переменных и выражений

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

Например, применение указанных преобразований переводит фрагмент

для I:=1, I+1 пока I<100

цикл

начало

K:=I+J; A[K]:= A[K]+1 конец;

K:=10;

во фрагмент

I:=1;

для K:=I+J, K+1 пока K<100+J

цикл

начало

A[K]:= A[K]+1 конец;

K:=10;

Здесь I,K - индуктивные переменные. В данном случае из цикла удалено индуктивное выражение K:=I+J.

4.2.2. Замена сложных операций на более простые

Весьма важным преобразованием из этой группы является по­нижение силы операций, заменяющее в индуктивных вычислениях сложные операции на более простые; например, возведение в сте­пень или деление заменяется умножением ( например, выражение Х/4.О заменяется на выражение Х* О.25), а умножение - сложени­ем.

Например, применение этого преобразования позволяет пере­ходить от цикла

для K:=1, K+1 пока K<=100

цикл V:=(K-1)*N+I

к более эффективно работающему фрагменту:

V:=I;

для K:=1, K+1 пока K<=100

цикл

начало A[V]:=A[V]+1;

V:=V+N конец

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

4.2.3. Исключение избыточных выражений

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

Например, эта операция осуществляет переход от фрагмента

если B>0 то

начало

A:=A+2; X:=A*B+C; конец

иначе Y:=A*B+D;

Z:= A*B;

к фрагменту

если B>0 то

начало

A:=A+2; W:=A*B; X:=W+C; конец

иначе начало

W:=A*B; Y:=W+D; конец;

Z=W;

4.2.4. Прочие преобразования

В эту же группу входит

экономия общих подвыражений, заменяющая, например, опера­тор

X:=(A+B)*(A+B+C)/(A+B+E) на фрагмент

Y:=A+B; X:=Y*(Y+C)/(Y+E),

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

если X>0 && Y<2 то Z:=1

на оператор

если X>0 то начало если Y<2 то Z:=1 конец),

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

ний массива на пересылку его указателя), другие различные

способы перестройки структуры информационных объектов в за-

висимости от характера их использования и с целью сокращения

времени работы с объектами; различные способы реализации пере-

менных через быстрые регистры, замена рекурсии на циклы .

Другие оптимизирующие преобразования, упрощающие

действия,- это преобразования по объединению и по расчленению

циклов, по перестановке заголовков циклов.

4.3. Реализация действий

Это способ повышения качества программы за счет выполне­ния определенных ее вычислений на этапе трансляции.

Набор преобразований данного типа включает в себя следую­щие оптимизации:

константные действия (подстановка или свертка констант), когда происходит выполнение операций над константами;

распроцедуривание - открытая подстановка тела процедуры на место ее вызова;

ликвидация константных распознавателей - замена условного

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

Реализация действий осуществляется также при

- втягивании констант, когда выражения, имеющие тождест­венно константные значения, заменяются на эти значения; при аналитических преобразованиях ( например, заменяющих Е*1 на Е или 0*Е на 0, где Е - произвольное подвыражение);

- отождествлении ( или втягивании уникальных), которое удаляет из программы оператор-пересылку вида X:=Y, где X и Y - переменные, заменяя либо вхождение X на Y - втягивание вверх (назад) - например, фрагмент Y:=F(W);X:=Y; заменяется на X:=F(W), либо вхождения Y на X - втягивание вниз (вперед) - например, X:=Y; если Z>0 то W:=Y+1 иначе W:=Y+2 заменяется на фрагмент если Z>0 то W:=X+1 иначе W:=X+2.

4.3.1. Подстановка (свертка)

Операции, операнды которых известны во время компиляции, нет необходимости выполнять во время счета.

Подстановка (свертка) - это замена переменной или mi-идентификатора результата заданной или вычисленной констан­той, причем эта замена производится во время трансляции, а не в процессе решения.

Свертка главным образом применяется к арифметическим опе­раторам +,-,*,/, т.к. они наиболее часто используются в исход­ной программе.

Например, для линейного участка

А:= 1+1

А:= 3

В:= 7+А,

представленного на промежуточном языке в виде триад:

(1) + 1,1 (2) := (1), А

(3) := 3,А (4) + 7,(3)

(5) := (4),В

1-ю триаду можно вычислить во время компиляции и заменить на результирующую константу, аналогично можно вычислить 4-ю триаду

.

Получается следующий результат свертки:

(1) := 2,А (2) := 3,А (3) := 10,В

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

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

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

новой триадой (С,К,0), где С(константа) - новый оператор, для

которого не нужно генерировать команды, а К - результирующее

значение свернутой триады.

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

1) Если операнд есть переменная, которая содержится в таблице Т, то операнд заменяется на соответствующее значение К.

2) Если операнд есть ссылка на триаду типа (С,К,0), то операнд заменяется на константу К.

3) Если все операнды являются константами и операция мо­жет быть свернута, то данная триада исполняется и вместо нее подставляется триада (С,К,0), где К - результирующее значение.

4) Если триада является присваиванием А:=В значения пере­менной без индекса А, то:

а) если В - константа, то А со значением В заносится в таблицу Т (старое значение А, если оно было, исключается);

б) если В - не константа, то А со своим значением исклю­чается из Т, если она там была.

4.4. Чистка программы

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

Набор преобразований этого типа включает в себя следующие оптимизации:

- удаление идентичных операторов;

- удаление из программы операторов, недостижимых по уп­равлению от начального;

- удаление преобразователей, информационно не влияющих на другие операторы;

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

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

- удаление процедур, к которым нет обращений;

- удаление неиспользуемых переменных, видов, операций и т. д.

4.4.1. Устранение идентичных операторов

i-тая операция считается лишней, если существует более ранняя идентичная j-тая операция и никакая переменная, от ко­торой зависит эта операция, не изменяется третьей операцией, лежащей между i-той и j-той операциями.

Оператор F считается идентичным и может быть устранен из программы, если существуют другие операторы G1,G2,...Gn, та­кие, что

1) оператор F и все операторы G1, G2, ... Gn выполняют одну и ту же операцию над одними и теми же операндами;

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

чала через операторы G.

Например, для линейного участка:

Е:= Е+С*В

А:= Е+С*В

С:= Е+С*В,

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

(1) * С,В (4) * С,В (7) * С,В

(2) + Е,(1) (5) + Е,(4) (8) + Е,(7)

(3) := (2),Е (6) := (5),А (9) :=(8),С

появление операции С*В во второй и третий раз лишнее, так как ни С, ни В не изменяются после 1-й триады.Однако второе сложение Е с С*В (5-я триада) не является лишним, так как после первого сложения Е с С*В 3-я триада изменяет значение Е. Но третье сложение Е с С*В лишнее и может быть заменено ссыл­кой на 5-ю триаду.

Алгоритм исключения лишних операций просматривает опера­ции в порядке их появления. Если 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.