Теория языков программирования методов трансляции (стр. 31 )

I I+1

goto цикл

выход: halt

Граф этой программы приведен на рис. 11.17.

Рис. 11.17. Граф управления.

Из графа видно, что{ℬ2, ℬ3} область с входом 2. Оператор Т J+1 инвариантен в этой области, так, что его можно перенести на новый участок, как показано на рис. 11.18.

Рис. 11.18. Преобразованный граф управления.

Несмотря на то, что в новом графе (программе) столько же операторов, что и в предыдущем, операторы в области будут выполняться часто, так что ожидаемое время выполнения уменьшится.

Индуктивное перемещение

Определение. Пусть Y область определения с одним входом, а X переменная, появляющаяся в некотором операторе, входящем в один из участков Y. Пусть ℬ1ℬ2 .. ℬne1,e2,..,em – такой путь вычисления, что ei принадлежит Y, 1 £ i £ m. Обозначим через X1, X2,… значения, присеваемые X в последовательности ℬe1e2.. em. Если X1, X2.. образуют арифметическую прогрессию (с положительной или отрицательной разностью) для любого пути вычисления типа указанного выше, то будем X называть индуцированной переменной в Y.

Будем также называть X индуцированной переменной, если она в ℬ неопределена и ее значения образуют арифметическую прогрессию.

Отметим, что задача нахождения всех индуцированных переменных в области нетривиальна (общего алгоритма не существует, но для частных случаев решения достаточно просты).

Пример. На рис.11.18 области {ℬ2 и ℬ3} имеют вход ℬ2. Если вход в ℬ2 осуществляется из ℬ2¢ и управление повторно передается от ℬ2 к ℬ3 и снова к ℬ2, то переменная I принимает значения 1,2,3,.. Таким образом, I – индуцированная переменная. Менее очевидно, что S – так же индуцированная переменная, поскольку она принимает значения Т+1, Т+2,. Т+3, а поскольку K не индуцированная, то она также принимает значения Т+1, 2Т+3, 3Т+6 ..

Важна особенность индуцированных переменных – их линейная связь друг с другом при передаче управления внутри области, которой они принадлежат. Например, для рис. 11.18 каждый раз при выходе из ℬ2, справедливы соотношения S=T+1 и I=S-T.

Если, как на рис. 11.18 какая-то индуцированная переменная используется только для управления в области (на это указывает тот факт, что ее значение не требуется за пределами области и что непосредственно перед входом в область ей присваивается всегда одна и та же константа), то ее можно исключить. Даже если за пределами области требуются все индуцированные переменные, внутри области можно использовать одну, а все остальные вычислить при выходе из области.

Пример. Рассмотрим рис. 11.18. Исключим индуцированную переменную I. Ее роль будет играть S. Заметим, что после участка ℬ2, переменная S принимает значение T+I, так, что когда управление возвращается от ℬ3 к ℬ2 должно выполняться соотношение S=T+I-1. Таким образом, оператор S T+I, можно заменить на S S+1. Но затем в ℬ2¢ надо правильно инициировать S, так что, когда управление перейдет из ℬ2¢ в ℬ2 значение S, после оператора будет Т+1.

Затем мы должны исправить проверку I=1000?, так, чтобы получить эквивалентную проверку относительно S. При выполнении этой проверки S имеет значение T+I. Следовательно, эквивалентной проверкой будет

R T+1000

S=R?

Поскольку R не зависит от области, вычисление R Т+1000 можно вынести в участок ℬ2¢. Тогда можно полностью избавиться от I. Новый граф представлен на рис. 11.19.

Рис. 11.19. Дальнейшее преобразование графа управления.

На рис11.19 видно, что участок ℬ3 исключен полностью, а область укорочена на один оператор. Конечно, размер участка ℬ2¢ увеличился, но по-видимому, области исполняются значительно чаще, чем участки вне области. Т. е. имеем ускоренный вариант программы.

Шаг S T в ℬ2¢ можно исключить, если отождествить S и T. Это возможно только по тому, что значения переменных S и T никогда не будут различными, но не смотря на это обе они будут «активными» в том смысле, что будут использоваться в дальнейших вычислениях. Иными словами в ℬ2 активна только переменная S, ни одна из них не активна в ℬ1, а в ℬ2¢ обе активны между операторами S T и R T+1000. Если Т заменить на S получим граф управления рис. 11.20.

Рис. 11.20. Окончательный вариант графа управления.

Для того чтобы понять, чем результирующий граф лучше исходного, превратим каждый из них в программу на языке ассемблера и введем новые коды операций (JZERO - переход в случае нулевого сумматора и JNZ - переход в случае ненулевого сумматора)

LOAD = 0 LOAD = 0

STORE K STORE K

LOAD = 1 LOAD = J

цикл: STORE I ADD = 1

LOAD J STORE S

ADD = 1 ADD =1000

ADD I STORE R

ADD K цикл: LOAD S

STORE K ADD = 1

LOAD I STORE S

SUBTR =1000 ADD K

JZERO выход STORE K

LOAD I LOAD S

ADD = 1 SUBTR R

JMP цикл JNZ цикл

выход: END END

а б

Заметим, что длина программы такая же, однако цикл короче (8 команд вместо 12).

Замена сложных операций

Внутри областей возможна замена сложных операций. Если внутри области есть оператор вида AB*I, в котором значение В не зависит от области, а I индуктивная переменная, то можно заменить умножение сложением или вычитанием величины, равной произведению значений, не зависящих от области разности арифметических программ, порождаемой индуктивной переменной.

Пример.

DO 5 J = 1, N

DO 5 I = 1, M

5  A(I, J) = B(I, J)

Пусть A(I, J) запоминается в ячейке А+M*(J-1)+I для 1 £ I£ M, 1£ J £ N; аналогичное предположение сделаем относительно B(I, J). Для удобства обозначим ячейку A+L через A(L). Тогда из исходной программы можно получить частично оптимизированную программу

N¢ N-1

J -1

J J+1

I 0

K M*J

цикл: I I+1

L K+I

A(L) B(L)

if I < M goto цикл

if J <N¢ goto цикл

halt

Граф управления новой программы изображен на рис. 11.21. В этом графе {ℬ2, ℬ3, ℬ4}- кисть, в которой переменная М инвариантна, а J- индуктивная переменная, возврастающая на 1. Поэтому оператор K М*J можно заменить на К К+М, предварительно присвоив К значение –М вне области.

Рис. 11.21. Граф управления.

Новый граф управления представлен на рис. 11.22. Программа представляемая этим новым графом, длиннее прежней, но области, соответствующие участкам ℬ2², ℬ3 и ℬ4 будут исполняться быстрее, поскольку умножение заменено сложением.

Рис. 11.22. Новый граф управления.

Можно получить более экономную программу, заменив всю область {ℬ2², ℬ3, ℬ4} одним участком. Окончательный граф управления представлен на рис. 11.23.

Рис. 11.23. Окончательный граф управления.

Развертывание циклов

Последние преобразование по улучшению кода, которое часто остается незамеченным, это развертывание циклов..

Рассмотрим граф на рис. 11.23.

Рис. 11.23. Граф управления.

В этом графе участки ℬ1 и ℬ2 выполняются 100 раз. Таким образом, 100 раз выполняется проверка. Не допуская никаких вольностей можно развернуть цикл на «один шаг» и получить граф рис. 11.24.

Рис. 11.24. Граф управления после развертывания цикла.

Программа представленная на рис. 11.24 длиннее, но в ней исполняется меньше команд (всего 50 проверок вместо 100)

6.4.  Анализ потоков данных

До сих пор мы использовали информацию о вычислениях в участках программ, не описывая, как этот участок и информацию о нем можно получить. В частности мы использовали:

1)  «Допустимые» при входе в участок выражения. Выражение А+В называется доступным при входе в участок, если А+В всегда вычисляется до достижения участка, но не ранее чем определены А и В.

2)  Множество участков, в которых переменная могла определяться последний раз перед тем, как поток управления достиг текущего участка. Эта информация полезна для размножения констант и выявления бесполезных вычисления. Она используется также для выявления возможных ошибок программиста, заключающихся в том, что на переменную делается ссылка до того, как она определена.