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