Реферат: Оптимизация программ
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.