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