Материалы представленные на сайте исключительно с целью ознакомления пользователям Интернета и не преследуют коммерческих целей или нарушение авторских прав.
© 2018 - 2024
Данное преобразование состоит в том, чтобы фрагмент программы
S 1
..........
S ( k -1)
Sk ( 22 )
S ( k +1)
..........
Sm
заменить на фрагмент программы
S ( k +1)
..........
Sm
S 1 ( 23 )
..........
S(k-1)
Sk
Здесь S1,...,Sm - операторы программы.
Теорема 32 . Пусть для фрагментов программы S1,..., Sk и S(k+1),..., Sm операторы S1 и S(k+1) являются единственными точками входа, а операторы Sk и Sm - единственными точками выхода соответственно. Будем считать, что между этими фрагментами нет условных или безусловных переходов. Кроме того, будем предполагать, что для фрагмента S1,..., Sk, S(k+1),...,Sm оператор S1 является единственным входом, а Sm - единственным выходом. Предположим, что в графе информационных связей НЕ существует такой дуги циклически независимой зависимости (v1,v2), что v1 принадлежит одному из переставляемых фрагментов программы, а v2 - другому. Тогда рассматриваемая перестановка фрагментов программы эквивалентна.
Доказательство. Корректность перестановки вытекает из того, что каждый из фрагментов S1,...,Sk, S(k+1),...,Sm, S1,...,Sk и S(k+1),...,Sm имеют по одной точке входа и одной точке выхода.
Из отсутствия переходов между фрагментами вытекает, что не существует цикла, содержащего хотя бы по одному оператору из каждого из двух рассматриваемых фрагментов, который мог бы разрушиться от перестановки фрагментов. С другой стороны, перестановка этих фрагментов не создаст новых циклов.
Два фрагмента программы эквивалентны тогда и только тогда, когда при одних и тех же исходных данных на их выходе получаются одинаковые значения результирующих данных. Предположим, что фрагменты программы S1,...,Sk, S(k+1),...,Sm и S(k+1),...,Sm,S1,...,Sk неэквивалентны. Тогда найдется некоторая переменная, обозначим ее A, принимающая разные значения после выполнения этих фрагментов. Это возможно лишь в двух случаях:
1) последнее значение переменной A в этих фрагментах вычисляют разные операторы;
2) последнее значение переменной A вычисляет один и тот же оператор, но этот оператор использует разные значения некоторой переменной, которую будем обозначать B.
Первый случай означает, что в каждом из фрагментов S1,...,Sk и S(k+1),...,Sm есть операторы присваивания, вычисляющие A в один и тот же момент выполнения фрагмента S1,...,Sm. Но это означает существование такой дуги (v1,v2) типа out-out в графе информационных связей, что v1 принадлежит фрагменту S1,...,Sk, v2 - фрагменту S(k+1),...,Sm и оба вхождения обращаются к одной и той же ячейке памяти в один и тот же момент выполнения фрагмента S1,..., Sm (т.е. существует циклически независимая дуга). Противоречие.
Второй случай означает, что в одном из фрагментов S1,..., Sk или S(k+1),...,Sm, находится оператор, вычисляющий A и использующий B, а в другом - оператор, вычисляющий B. Но, как и в предыдущем случае, это означает существование такой дуги (v1,v2) типа in-out либо out-in в графе информационных связей, что v1 принадлежит фрагменту S1,...,Sk, v2 - фрагменту S(k+1),...,Sm и оба вхождения обращаются к одной и той же ячейке памяти (в данном случае B) в один и тот же момент выполнения фрагмента S1,...,Sm (это дуга циклически независимой зависимости).
Конец доказательства.
Необходимость условий данной теоремы проиллюстрируем следующими примерами.
Пример 45. Фрагмент программы
10 X ( K ) = A ( I +1)
15 A(I+1) = 1
НЕ равносилен следующему
10 A ( I +1) = 1
15 X ( K ) = A ( I +1)
(Здесь зависимость между вхождениями переменной A является циклически независимой). Действительно, при начальных значениях I=1; K=1; A(2)=2; первый фрагмент вычисляет X(1)=2 , а второй X(1)=1.
Конец примера.
Пример 46. Фрагмент программы
10 X ( K ) = A ( I +1)
15 A(I) = 1
равносилен следующему
10 A ( I ) = 1
15 X ( K ) = A ( I +1)
(Здесь зависимость между вхождениями переменной A не является циклически независимой).
Конец примера.
Пример 47. Фрагмент программы
10 X ( K ) = A ( I +1)
15 K = 1
НЕ равносилен следующему
10 K = 1
15 X ( K ) = A ( I +1)
(Здесь зависимость между вхождениями переменной K является циклически независимой). Действительно, при начальных значениях I=1; K=2; A(2)=1; X(1)=2, первый фрагмент вычисляет X(1)=2 , а второй X(1)=1.
Конец примера.
Пример 48. Фрагмент программы
10 IF ( C <0)
15 L = A ( I +1)
20 B = X ( K )
НЕ равносилен следующему
10 IF (C<0)
20 B = X ( K )
15 L = A ( I +1)
(Здесь в исходном фрагменте у оператора 20 два входа).
Конец примера.
Пример 49. Фрагмент программы
IF ( C <0)
L = A ( I +1)
B = X ( K )
равносилен следующему
B = X ( K )
IF ( C <0)
L = A ( I +1)
Конец примера.
Пример 50. Фрагмент программы
K = X +1
goto 99
K = I -1
99 A = K
НЕ равносилен следующему
K = X+1
K = I-1
goto 99
99 A = K
(Здесь у всего фрагмента из двух переставляемых операторов в целом два выхода).
Конец примера.
Пример 51. Фрагмент программы
С = 1
goto 99
...
88 С = 2
99 A = K
НЕ равносилен следующему
С = 1
goto 99
...
99 A = K
88 С = 2
(Здесь у фрагмента из оператора 99 два входа. У результирующего фрагмента на выходе всегда C=2, а у исходного может быть и C=1.).
Конец примера.
Пример 52. Фрагмент программы
write ( F ,10)
write ( F ,20)
НЕ равносилен следующему
write ( F ,20)
write ( F ,10)
Здесь вхождения F связаны выходной зависимостью.
Конец примера.
Предыдущую теорему несложно обобщить на случай перестановки фрагментов программы, между которыми есть еще один фрагмент.
Теорема 33 . Пусть имеется фрагмент программы S1,...,Sm , представляющий собой последовательность трех подряд идущих фрагментов S1,...,Sk; S(k+1),...,Sr; S(r+1),...,Sm . Операторы S1, S(k+1), S(r+1) являются единственными точками входа, а операторы Sk, Sr и Sm - единственными точками выхода этих фрагментов соответственно. Кроме того, будем предполагать, что для всего фрагмента S1,...,Sm оператор S1 является единственным входом, а Sm - единственным выходом. Предположим, что в графе информационных связей НЕ существует такой циклически независимой дуги (v1,v2), что v1 принадлежит фрагменту S1,...,Sk; а v2 - S(k+1),...,Sr; S(r+1),...,Sm или v1 принадлежит S1,...,Sk; S(k+1),...,Sr; а v2 принадлежит фрагменту S(r+1),...,Sm. Тогда рассматриваемая перестановка фрагментов программы S1,...,Sk; и S(r+1),...,Sm синтаксически корректна и эквивалентна.
Для доказательства следует дважды воспользоваться предыдущей теоремой.
Теорема 34 . (о произвольной перестановке фрагментов в соответствии с дугами информационных зависимостей). Пусть имеется последовательность фрагментов программы F1,..., Fn и перестановка чисел s(i), i = 1,…, n . Пусть каждый из этих фрагментов имеет один вход и один выход. Предположим, что для любых двух чисел i, j = 1,…, n, i < j выполняется условие
Тогда последовательность фрагментов Fs(1),..., Fs(n) эквивалентна исходной последовательности F1,..., Fn .
Доказательство. Будем преобразовывать последовательность фрагментов Fs(1),..., Fs(n) эквивалентными перестановками к исходной последовательности F1,..., Fn . Рассмотрим такое число k , для которого s(k)=1. Покажем, что для любого j такого, что j<k, не существует дуги циклически независимой зависимости из Fs(j) в Fs(k) . Действительно, поскольку в исходной программе Fs(k) = F1 по тексту раньше, чем Fs(j) , то в Fs(k) = F1 не могут входить дуги циклически независимой зависимости. Поэтому фрагмент Fs(k) = F1 можно переставить на первое место (где он и был раньше) и будет получена программа равносильная исходной F1, Fs(1),..., Fs(k-1), Fs(k+1), …, Fs(n) . Теперь можно показать, что равносильной перестановкой фрагментов можно на второе место в последовательности переставить фрагмент F2 . И т.д. методом математической индукции можно показать, что из результирующей последовательности Fs(1),..., Fs(n) равносильными перестановками может быть получена исходная последовательность фрагментов.
Для векторных компьютеров перестановка операторов в теле цикла иногда позволяет цикл представить в виде последовательности векторных команд. Это происходит вследствие того, что циклически порожденные дуги графа информационных связей, которые были направлены "снизу-вверх", теперь будут направлены "сверху-вниз".
Пример 53. Фрагмент программы
DO 99 I = 1, N
X(I) = A(I+1)
K(I) = X(I+1)
99 CONTINUE
равносилен следующему, поскольку зависимость циклически порожденная.
DO 99 I = 1, N
K(I) = X(I+1)
X(I) = A(I+1)
99 CONTINUE
При этом операторы второго цикла могут выполняться одновременно для всех итераций.
Конец примера.
Пример 54. Фрагмент программы
DO 99 I = 1, N
X(I) = A(I+1)
IF X(I)<0 THEN K(I) = X(I)
99 CONTINUE
не равносилен следующему, поскольку зависимость циклически независима
DO 99 I = 1, N
IF X(I)<0 THEN K(I) = X(I)
X(I) = A(I+1)
99 CONTINUE
Конец примера.
Перестановка операторов в теле цикла иногда позволяет разбивать цикл, в теле которого много операторов присваивания на несколько циклов, в телах которых меньше операторов. Это преобразование может использоваться, например, в компьютерах с конвейерной архитектурой - (если для конвейеризации большого цикла недостаточно ресурсов).
Пример 55. Не разрушит ли следующий пример теорему о перестановке операторов?
S1
..........
goto 99
S(k-1)
Sk (24)
99 S(k+1)
..........
Sm
заменить фрагментом программы
99 S(k+1)
..........
Sm
S1 (25)
..........
goto 99
S(k-1)
Sk
Здесь S1,...,Sm - операторы программы.
Конец примера.
Подстановка вперед
Это преобразование подставляет правую часть оператора присваивания вместо последующих вхождений левой части этого же оператора (если это не нарушает равносильность) [20, с 26]. В частном случае, когда правая часть оператора присваивания является константой, это преобразование называется протягиванием констант. В результате протягивания констант уменьшается код программы, повышается быстродействие и исчезают некоторые дуги информационной зависимости, что может способствовать распараллеливанию. Подстановка вместо переменных их значений в индексных выражениях позволяет точнее строить граф информационных связей.
Пример 56. Фрагмент программы
10 X ( K ) = A ( I +1) + B
20 B = X ( K )
равносилен следующему
10 X ( K ) = A ( I +1)+ B
20 B = A ( I +1) + B
Конец примера.
Пример 57. Фрагмент программы
goto 77
..................
T = 5
77 A = T + E
B = 2*T
НЕ равносилен следующему
goto 77
.....................
T = 5
77 A = 5+ E
B = 2*5
Конец примера.
Теорема 35 . Пусть у фрагмента программы
S 1 X ( F 1) = expr ( A , B ,...)
v 1
…………………. ( 26 )
Sm ... = ... X ( F 1)...
v2
F1 - какое-либо индексное выражение, одинаковое в обоих случаях. Пусть для рассматриваемого фрагмента программы выполняются условия:
1. S1 - единственная точка входа фрагмента.
2. В графе информационных связей дуга (v1,v2) между вхождениями X(F1), является единственной дугой этого фрагмента, входящей во вхождение v2 переменной X.
3. Нет дуг, входящих во вхождения индексного выражения F1 оператора Sm из вхождений данного фрагмента.
4. Нет дуг, выходящих из вхождений выражения expr(A,B,...) в генераторы операторов S1,..,S(m-1).
Тогда подстановка вперед является эквивалентным преобразованием.
Доказательство. После выполнения подстановки из исходного фрагмента программы получается фрагмент
S1 X(F1) = expr(A,B,...)
................……………….. ( 27 )
Sm ... = ... expr ( A , B ,...)...
Очевидно, что для эквивалентности исходного и результирующего фрагментов достаточно, чтобы к моменту выполнения оператора Sm переменная X(F1) и выражение expr(A,B,...) принимали одинаковые значения. Предположим, что это неверно. Тогда к моменту выполнения оператора Sm либо вхождение X(F1), либо выражение expr(A,B,...) поменяло свое значение.
Предположим, что свое значение поменяло вхождение X(F1). Тогда, ввиду единственности входа у фрагмента, либо где-то в рассматриваемом фрагменте существует еще один генератор X(F1) , что противоречило бы условию 2 теоремы, либо изменило свое значение индексное выражение F1, но тогда в рассматриваемом фрагменте есть генератор какой-либо переменной, входящей в выражение F1. Наличие такого генератора означает, что в графе информационных связей из рассматриваемого фрагмента есть дуга в F1, что противоречит условию 3 теоремы.
Теперь предположим, что свое значение поменяло выражение expr(A,B,...). Тогда, где-то по пути от S1 до Sm свое значение поменяло какое-то вхождение этого выражения. Но это означает, что у операторов S2,..,S(m-1) есть генератор переменной из данного выражения, что противоречит условию 4 теоремы.
Полученные противоречия завершают доказательство теоремы.
Условия предыдущей теоремы не являются необходимыми. Действительно, если в операторе Sm вхождение X(F1) умножается на ноль, то никакие нарушения условий теоремы не препятствуют эквивалентности подстановки.
Пример 58. Фрагмент программы
goto Sm
..................
S1 X(K) = A+B
X(K) = 1
A = T+E
Sm B = 0* X ( K ) + C
равносилен следующему
goto Sm
..................
S1 X(K) = A+B
X(K) = 1
A = T+E
Sm B = 0*(A+B) +C
хотя условия теоремы не выполнены.
Конец примера.
С другой стороны, если нарушается любое из условий теоремы, то существует такая программа, в которой выполняются все остальные условия, но подстановка неэквивалентна. В этом смысле условия теоремы являются необходимыми.
Пример 59. Фрагмент программы
10 IF ( C <0)
15 X ( K ) = A ( I +1)
20 B = X ( K )
НЕ равносилен следующему
10 IF (C<0)
15 X(K) = A(I+1)
20 B = A(I+1)
(фрагмент из операторов 15-20 имеет 2 входа).
Конец примера.
Пример 60. Фрагмент программы
10 X ( K ) = A ( I +1)
15 X ( K ) = 1
20 B = X ( K )
НЕ равносилен следующему
10 X(K) = A(I+1)
15 X ( K ) = 1
20 B = A ( I +1)
(В использование X(K) входят две дуги зависимости)
Конец примера.
Пример 61. Фрагмент программы
10 X ( K ) = A ( I +1)
15 K = 1
20 B = X ( K )
НЕ равносилен следующему
10 X(K) = A(I+1)
15 K = 1
20 B = A ( I +1)
(В индексное значение использования X(K) входит дуга зависимости)
Конец примера.
Пример 62. Фрагмент программы
X ( K ) = A ( I +1)
I = 1
B = X ( K )
НЕ равносилен следующему
X ( K ) = A ( I +1)
I = 1
B = A ( I +1)
(Из вхождения в правую часть первого оператора есть дуга зависимости).
Конец примера.
Дата: 2018-12-21, просмотров: 414.