Например, применение этого преобразования позволяет переходить от цикла
для 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- идентификатором).