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