Навигация
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- идентификатором).
Это в свою очередь может привести к тому, что рекурсивно определенная программная переменная использоваться в блоке не будет и само определение может быть устранено.
Определение не используется и может быть устранено, если результат определения не является операндом ни одного оператора рекурсивного определения и результат этого последнего не используется ни в каком другом операторе.
Существование неиспользуемых определений до оптимизации является ошибкой программиста. Но после оптимизации такие определения могут возникнуть как результат перестановки и изменения отдельных операторов в процессе оптимизации.
Для данного определения в данном блоке производится поиск использования этого определения во всех последующих командах блока и во всех блоках, которые могут следовать за ним.Поиск прекращается, когда находится оператор, использующий данное определение в качестве аргумента. Если такой оператор в данном и последующих блоках найден не будет, то определение считается неиспользуемым и устраняется.
Как только неиспользуемое определение устранено, все операторы, от которых зависел устраненный оператор, если они нигде больше не используются, могут быть устранены.
Похожие работы
... ; i=1,3. Q – количество сырья Для автоматизированной обработки данных и вычислений используется пакет программ линейной оптимизации программного продукта Microsoft Excel. Решение Определяем оптимальные производственные мощности филиалов для производства определенного количества продукции различных видов с помощью транспортной задачи. Постановка транспортной задачи. Требуется определить ...
... практичных алгоритмов оптимизированного перебора, позволяющих за разумное время осуществлять распараллеливание достаточно больших участков. Анализ работ, посвященных оптимизации кода для процессоров с параллелизмом на уровне команд показывает, что для достижения наилучших результатов необходимо применение комплекса оптимизаций, среди которых можно выделить следующие классы. Преобразования циклов ...
... заданных операндов. 3) Использование косвенной адресации, когда операнд хранит адрес операнда. 4) Ограничение использования стека. программа оптимизация ассемблер код 4. Машинно-независимая оптимизация кода ассемблера Машинно-независимая оптимизация предполагает: 1. Одним из важнейших источников оптимизации кода является удаление общих подвыражений, т.е. подвыражений, которые ...
... лишь контекстным анализом. Как было отмечено в [12], применение глубокого статического анализа программ может позволить существенно снизить количество ложных срабатываний и повысить точность обнаружения уязвимостей защиты. 4.3. Использование методов анализа потоков данных для решения задачи обнаружения уязвимостей В отделе компиляторных технологий по контракту с фирмой Nortel Networks ...
0 комментариев