Вынос вычисления выражений и замена общих подвыражений

 

Вынос общих подвыражений состоит в том, чтобы найти в тексте программы одинаковые подвыражения, вычислить их отдельно, присвоив значение этого подвыражения вспомогательной переменной, и заменить всюду по тексту данное подвыражение новой переменной. При выполнении преобразования следует проверять, во всех ли случаях вхождения в данное подвыражение имеют одинаковые значения.

 

Теорема 36. Пусть фрагмент программы

M S1

..........

Sk    expr(A, B,...)               

................                                                                                    (28)

   Sm    expr(A, B,...)

 

имеет единственный вход – оператор S1. Пусть операторы Sk и Sm имеют одинаковые подвыражения expr(A, B,...). Предположим, что во вхождения переменных из любого выражения expr(A, B,...) не входят дуги информационной зависимости из других вхождений этого фрагмента. Тогда этот фрагмент программы эквивалентен следующему, в котором вместо expr(A, B,...) подставлена переменная T, а если оператор S1 имел метку M, то эта метка должна быть переставлена оператору S0. 

 

M S0 T = expr(A, B,...)   

S1

..........

Sk    T              

................                                                            (29)

Sm    T

 

Доказательство. Заметим, что у нового фрагмента программы есть единственный вход – оператор S0. Если во фрагменте программы (29) выполнить подстановку вперед, а потом удалить оператор S0, то получим фрагмент (28). Поскольку фрагмент (29) удовлетворяет условию теоремы о подстановке вперед, а после выполнения подстановки вперед он будет удовлетворять условию теоремы об удалении оператора присваивания, фрагменты (28) и (29) эквивалентны. Конец доказательства.

 

       Замечание. Очевидно, что можно выносить вычисление выражения перед фрагментом и из одного оператора или из нескольких (не только из двух, как приведено в формулировке теоремы).

 

  Обсуждение целесообразности удаления общих подвыражений.

  Рассматриваемое преобразование уменьшает код программы и используется не только в распараллеливающих компиляторах, но и в оптимизирующих. Следует отметить, что данное преобразование является в некотором смысле обратным к подстановке вперед.

 

Пример 63. Фрагмент программы

   X = A+B+C

   Y = A+B-C

 равносилен следующему

   T = A+B

   X = T+C

   Y = T-C

Конец примера.

 

Пример 64. Фрагмент программы

   X = A+B+C

   A = 1

   Y = A+B-C

не равносилен следующему

   T = A+B

   X = T+C

  A = 1

   Y = T-C

Конец примера.

 

Пример 65. Фрагмент программы

   X = A+I+1

   Y = A-I-1

 равносилен следующему

   T = I+1

   X = A+T

   Y = A-T

Конец примера.

 

Пример 66. Фрагмент программы (Алгоритм Флойда построения матрицы кратчайших расстояний графа)

   DO 77 K = 1, N

   DO 77 J = 1, N

   DO 77 I = 1, N

   IF ( A(I, J) > A(I, K)+A(K, J) )

   A(I, J) = A(I, K)+A(K, J)

77 CONTINUE

 равносилен следующему

   DO 77 K = 1, N

   DO 77 J = 1, N

   DO 77 I = 1, N

   T = A(I, K)+A(K, J)

   IF ( A(I, J) > T )

   A(I, J) = T

77 CONTINUE

Конец примера.

 

Пример 67. Фрагмент программы

   IF ( X > 0 ) THEN

   A = C+D+E

   B = 2*(C+D)

 равносилен следующему

   T = C+D

   IF ( X > 0 ) THEN

   A = T+E

   B = 2*T

Конец примера.

 

 

 Пример 68. Фрагмент программы

   IF ( X > 0 ) THEN

   A = C+D+E

   B = 2*(C+D)

НЕ равносилен следующему

   IF ( X > 0 ) THEN

   T = C+D

   A = T+E

   B = 2*T

Конец примера.

 

 

Переименование безиндексных переменных

 

Переименование переменной состоит в том, чтобы в какой-либо части программы имя некоторой переменной заменить новым именем. Разумеется, новую переменную, если требует синтаксис языка, предварительно следует описать.

       Переименование переменных призвано устранять информационные зависимости в программе. Это преобразование также позволяет приводить фрагмент программы к виду с однократным присваиванием (т.е. каждая переменная получает свое значение только один раз).

 

Пример69.  Линейный участок программы

A = A + C

A = A+B

C = 3*A

A = A+A+C

write(A)

эквивалентен следующему

A = A + C

AA = A + B

C = 3*AA

A = AA+AA+C

write(A)

Конец примера.

Пример70.  Фрагмент программы

A = B + C

IF K> 0

A = A+B

ENDIF

C = 3* A

не эквивалентен следующему фрагменту

A = B+C

IF K> 0

AA = A+B

ENDIF

C = 3* AA

Последнее вхождение переменной A исходного цикла использует значения различных генераторов в зависимости от переменной K. Для переименования переменных в этом примере необходимо предварительное преобразование условного оператора.

Конец примера.

Пример71.  Линейный участок программы

       A = A+C

       A = A+B

777 C = 3*A

       A = A+A+C

       write(A)

вообще говоря, не эквивалентен следующему

       A = A+C

       AA = A+B

777 C = 3*AA

       A = AA+AA

       write(A)

поскольку использование переменной A в операторе 777 может использовать значения нескольких генераторов (фрагмент имеет два входа).

Конец примера.

 

Будем говорить, что фрагмент программы обладаем свойством разложимости относительно оператора Operator, если этот фрагмент программы представим в виде

       PartOfProg1

       Operator

       PartOfProg2

где каждый из фрагментов PartOfProg1 и PartOfProg2 имеет один вход и один выход.

       Переименование переменных призвано устранять информационные зависимости в программе [ 120 ]. Это преобразование также позволяет приводить фрагмент программы к виду с однократным присваиванием (т.е. каждая переменная получает свое значение только один раз).

 

       Теорема 37. Пусть в тексте фрагмента программы имеется генератор безиндексной переменной A (будем называть его базисным) и, предположим, что всякое использование A в данном фрагменте использует значения базисного генератора и не использует значения других генераторов. Предположим, что за пределами данного фрагмента не используются значения базисного генератора переменной A. Предположим, что переменная AA не используется в данной программе. Тогда в рассматриваемом фрагменте переменную A можно заменить переменной AA (и имя базисного генератора и имена всех использований, использующих значения этого генератора). Результирующая программа будет эквивалентна исходной.

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

 

       Теорема 38. Пусть в тексте программы имеется генератор безиндексной переменной A (будем называть его базисным) и, предположим, что всякое использование A использует значения базисного генератора и не использует значения других генераторов. Тогда имя базисного генератора и имена всех использований, использующих значения этого генератора, могут быть заменены именем новой переменной.

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

       Лемма 1. Пусть оператор

L  Statement(A(I), A(J),...)

с меткой L включает использования A(I), A(J),...переменной A.Тогда этот оператор можно заменить фрагментом программы

L     AA(I) = A(I)

        AA(J)= A(J)

...........................

L1   Statement(AA(I), AA(J),...)

При этом если исходный оператор был последним оператором тел каких-либо циклов, то в заголовках этих циклов следует метку L заменить меткой L1. (Метка L переносится к первому добавленному оператору присваивания на тот случай, если существуют переходы (goto) к оператору с этой меткой). 

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

 

       Лемма 2. Пусть в текст программы входит оператор присваивания

L  A(I) = expr

с меткой L.Тогда этот оператор можно заменить фрагментом программы, состоящим из двух операторов

L      AA(I) = expr

L1    A(I) = AA(I)

Если исходный оператор был последним оператором тел каких-либо циклов, то в заголовках этих циклов следует метку L заменить меткой L1.

       Доказательство. В результирующем фрагменте выполним подстановку вперед, взяв исходный оператор в качестве базисного. После этого добавленный оператор (с меткой L1) удалим, как неиспользуемый. Получится исходный оператор присваивания.

 

       Теорема 39. (о переименовании переменной во фрагменте, разложимом относительно первого генератора). Пусть имеется фрагмент программы

       PartOfProg(A, B,...)

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

PartOfProg 1

X = expr 1

PartOfProg 2

где PartOfProg1 – не содержит генераторов переменной X и каждый из фрагментов PartOfProg1 и PartOfProg2 имеет один вход и один выход. Тогда эквивалентным преобразованием является замена исходного фрагмента на фрагмент программы

AA = A

BB=B

...........................

PartOfProg(AA, BB,...)

A = AA

B = BB

........................

(здесь AA, BB,... - новые переменные).

       Доказательство. Будем предполагать, что существует только одна безиндексная переменная A во фрагменте программы PartOfProg(A). Общий случай получается по индукции.

Рассмотрим случай существования генератора переменной A в исходном фрагменте. Представим фрагмент программы PartOfProg(A) в виде конкатенации фрагментов

PartOfProg 1( A )

A = expr 1

PartOfProg 2( A )

где PartOfProg1(A) представляет собой часть PartOfProg(A) от начала до первого генератора переменной A (не включая его), а PartOfProg2(A) - оставшиеся операторы. (Заметим, что один (или оба) из этих фрагментов может быть пустым – не содержать ни одного оператора). Тогда результирующий фрагмент программы примет вид

AA = A

PartOfProg 1( AA )

AA=expr

PartOfProg2(AA)

A=AA

 В части

AA=A

PartOfProg1(AA)

выполним подстановку вперед и получим

AA = A

PartOfProg1(A)

AA=expr

PartOfProg2(AA)

A = AA

Теперь можно удалить первый оператор присваивания этого фрагмента, получив ему эквивалентный

PartOfProg1(A)

AA=expr

PartOfProg2(AA)

A = AA

Новый фрагмент можно получить из фрагмента

PartOfProg1(A)

A=expr

PartOfProg2(A)

A = A

переименованием переменных (и, согласно предыдущей теореме, эти фрагменты эквивалентны). В заключение осталось удалить пустой оператор присваивания A=A. Таким образом, описанное в условии теоремы преобразование является последовательностью известных эквивалентных преобразований и, значит, само оно тоже эквивалентно.

 

Условия переименования безиндексных переменных без труда переносятся на переменные с индексами, если у всех рассматриваемых вхождений индексные выражения одинаковы и если индексы на протяжении всего фрагмента не меняются. В частности, если индексное выражение меняется в цикле, то одновременно у всех рассматриваемых вхождений. Схема переименования переменных с разными индексами представлена в [ 100 ]. В работе [ 122 ] разработана техника анализа решетчатых графов и сообщается о возможности ее применения к переименованию индексных переменных.

В следующих двух примерах по-разному выполняется переименование, поскольку в качестве базовых выбраны разные операторы.

Пример72. Цикл

DO 99 I = 5, 100

X(I) = B(I)*K(I)

K(I) = X(I-1)+X(I-3)

99 X(I-1) = A(I+1)+X(I-1)

преобразуется к эквивалентному фрагменту программы

XX (2)= X (2)

XX(3)=X(3)

DO 99 I = 5, 100

X(I) = B(I)*K(I)

K(I) = X(I-1)+XX(I-3)

99 XX(I-1) = A(I+1)+X(I-1)

       После такой замены далее в тексте программы должны быть заменены многие вхождения переменной X на XX.

Конец примера.

 

Пример 73.  Цикл

DO 99 I = 5, 100

X(I) = B(I)*K(I)

K(I) = X(I-1)+X(I-3)

99 X ( I -1) = A ( I +1)+ X ( I -1)

преобразуется к эквивалентному фрагменту программы

XX(4)=X(4)

DO 99 I = 5, 100

XX(I) = B(I)*K(I)

K(I) = XX(I-1)+X(I-3)

99 X(I-1) = A(I+1)+XX(I-1)

X (100) = XX (100)

Конец примера.

 

Пример74. Цикл

    DO 99 I = 1, 100

       X(I) = A(I+1)+X(I)

       K(I) = X(I+1)+X(I)

       IF K(I)> 0 GOTO 100

X(I) = B(I)*X(I)

 99 CONTINUE

преобразуется к эквивалентному циклу

    DO 99 I = 1, 100

    XX(I) = A(I+1)+X(I)

    K(I) = X(I+1)+XX(I)

IF K(I)> 0 GOTO 100

       X(I) = B(I)*XX(I)

 99 CONTINUE

Конец примера.

 

Пример75.  Цикл

DO 99 I = 1, 100

    X(I) = A(I+1)+X(I)

    K(I) = X(I+1)+X(I)

       X(I) = B(I)*K(I)

 99 CONTINUE

преобразуется к эквивалентному циклу

    DO 99 I = 1, 100

    XX(I) = A(I+1)+X(I)

    K(I) = X(I+1)+XX(I)

       X(I) = B(I)*K(I)

 99 CONTINUE

Конец примера.

 

Пример76. Цикл

    DO 99 I = 1, 100

    X(I) = A(I+1)+X(I-1)

    K(I) = X(I+1)+X(I)

       X(I) = B(I)*K(I)

 99 CONTINUE

преобразуется к эквивалентному фрагменту программы

DO 99 I = 1, 100

    XX(I) = A(I+1)+X(I-1)

    K(I) = X(I+1)+XX(I)

       X(I) = B(I)*K(I)

 99 CONTINUE

Конец примера.

Пример77. Цикл

DO 99 I = 5, 100

    X(I-1) = A(I+1)+X(I-1)

    K(I) = X(I-1)+X(I-3)

       X(I) = B(I)*K(I)

 99 CONTINUE

преобразуется к эквивалентному фрагменту программы

       XX(2)=X(2)

       XX(3)=X(3)

DO 99 I = 5, 100 

    XX(I-1) = A(I+1)+X(I-1)

    K(I) = XX(I-1)+XX(I-3)

       X(I) = B(I)*K(I)

99 CONTINUE

Конец примера.

 

Пример78.  неудобный ПРИМЕР ДЛЯ ПЕРЕИМЕНОВАНИЯ МАССИВОВ.  

 

DO 77 I = 1, M do

X(2*I) = 2*X(I)

77 continue

 

Этот цикл вычисляет члены геометрической прогрессии и записывает их в массив X. При этом отношение количества элементов массива X, которые получили новое значение к элементам, которые не получили такого значения очень мало (стремиться к нулю с увеличением количества итераций цикла).  

Конец примера.

 

 

6.3  Преобразования циклов

 

Раскрутка цикла

 

Раскрутка цикла [ 45 ] заменяет цикл

   DO 999 I=1, N

999 ТЕЛОЦИКЛА(I)

на следующий фрагмент программы

ТЕЛОЦИКЛА(1)

ТЕЛОЦИКЛА(2)

........................

ТЕЛОЦИКЛА(N)

I = N

Границы цикла должны быть константами (в частности, значение N в данном цикле должно быть известно на этапе трансляции).

Если ТЕЛОЦИКЛА(I) содержит помеченные операторы, на которые указывают goto, то в копиях тела цикла метки должны вводиться новые. В упрощенном варианте раскрутку можно применять лишь для циклов, в теле которых не содержатся помеченные операторы, на которые указывают goto.

Счетчику цикла следует присвоить значение последней итерации.

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

Поскольку при раскрутке цикла не меняется порядок выполнения операций, это преобразование всегда эквивалентно. Более того, оператор цикла по своей семантике определяется, как краткая запись раскрутки.

 

Пример 79. Цикл

   DO 99 I = 1, 3

   X(I) = A(I+1)

   K(I) = X(I-1)

99 CONTINUE

эквивалентен следующему фрагменту программы

   X(1) = A(2)

   K(1) = X(0)

   X(2) = A(3)

   K(2) = X(1)

   X(3) = A(4)

   K(3) = X(2)

Конец примера.

 

 

6.3.2 Удаление оператора (заголовка) цикла

 

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

       Другой вариант этого же преобразования состоит в удалении заголовка цикла и замене счетчика в теле цикла на его последнее значение.

       Если заголовок цикла имел метку, то в обоих вариантах, удаляя заголовок цикла, вместо него надо написать пустой оператор CONTINUE, сохранив метку. 

 

Теорема 40. Если тело цикла не содержит ни одного оператора, то удаление оператора цикла является равносильным преобразованием.

       Доказательство. Это утверждение является очевидным следствием предыдущего.

 

Теорема 41. Если цикл имеет лишь одну итерацию, то удаление оператора цикла является равносильным преобразованием при замене счетчика цикла на его единственное значение в теле цикла.

       Доказательство. Описанное преобразование является в данном случае раскруткой цикла и по этой причине - эквивалентно.

 

Теорема 42. Пусть в теле цикла есть только условные операторы и присваивания. Предположим, что все генераторы операторов присваивания тела цикла не зависят от счетчиков цикла или других переменных, меняющих свое значение при выполнении цикла. Пусть граф информационных связей тела цикла не содержит дуг истинной циклически порожденной зависимости. Тогда, удалив заголовок цикла, поставив в теле цикла вместо счетчика его последнее значение, и, поставив после тела цикла оператор, присваивающий счетчику его последнее значение, получим фрагмент программы, эквивалентный исходному.

       Доказательство. Сделаем раскрутку цикла. Раскрутка содержит столько копий тела цикла, сколько было итераций. Докажем, что все копии, кроме последней, можно удалить.

Рассмотрим первую копию тела цикла (остальные рассматриваются аналогично). Поскольку граф информационных связей тела исходного цикла не содержит дуг истинной циклически порожденной зависимости, значения генераторов первой копии тела цикла не используются в других копиях. Поскольку генераторы операторов присваивания не зависят от счетчика цикла или других переменных, меняющих свое значения в цикле, эти генераторы на каждой итерации пишут данные в одну и ту же ячейку памяти. Поскольку значения генераторов первой копии тела цикла перезаписываются в дальнейших копиях, эти значения не используются и после раскрутки цикла (далее могут использоваться только значения последней копии тела цикла). Поэтому, все операторы присваивания первой копии тела цикла можно заменить пустыми операторами. Тогда все условные операторы первой копии тела цикла будут содержать только пустые операторы – и, следовательно, их тоже можно заменить пустыми операторами. В конце концов, первую копию тела цикла можно заменить пустым оператором. Поскольку раскрутка цикла представляет собой конкатенацию копий тела цикла, этот пустой оператор можно удалить.

       Аналогично могут быть удалены и другие копии тела цикла, кроме последней. В последней копии тела цикла вместо счетчика цикла стоит его последнее значение. Таким образом, исходный цикл эквивалентно преобразован к виду, описанному в условии теоремы.

 

Пример80. Цикл

  DO 99 I = 5, 100, 10

99 X = A+B

эквивалентен оператору

99 X = A+B

Конец примера.

 

Пример 81. Цикл

  DO 99 I = 5, 100, 10

99 X = A+X

не эквивалентен оператору

99 X = A+X

Конец примера.

 

Пример82. Цикл

  DO 99 I = 5, 100, 10

99 X = A(I)+B

не эквивалентен оператору

99 X = A(100)+B

(Последняя итерация исходного цикла происходит при I=95 и, поэтому исходный цикл должен быть заменен на оператор 99 X = A(95)+B).

Конец примера.

 

Пример 83. Цикл

  DO 99 I = 5, 100, 10

99 X = A(I)+B*I

эквивалентен оператору

99 X = A(95)+95*B

Конец примера.

 

Пример84. Цикл

  DO 99 I = 5, 100, 10

99 X = X+1

не эквивалентен оператору

99 X = X+1

Конец примера.

 

 

Канонизация циклов

Данное преобразование заменяет всякий цикл равносильным, с левой границей 1 и шагом тоже 1. Иногда используется термин «нормализация» (do-loop normalization) [ 20, с. 37]. Это преобразование применимо к любому оператору цикла

 

    DO 99 I=L, N, h

99 ТЕЛОЦИКЛА(I)

 

и заменяет его оператором цикла

 

    DO 99 J=1, (N-L+1)//h

99 ТЕЛОЦИКЛА(h*(J-1)+L)

 

Здесь // означает операцию целочисленного деления. К описанным требованиям канонического вида цикла можно добавить еще одно: последний оператор тела цикла должен быть CONTINUE.

Алгоритм выполнения канонизации состоит в следующем:

1) сгенерировать новую переменную (обозначим ее J) для имени нового счетчика цикла.

2) Всюду в теле цикла заменить старый счетчик цикла I на выражение (h*(J-1)+L). Для выполнения этого преобразования можно использовать подстановку вперед.

3) В заголовке цикла левая граница заменяется числом 1, а правая - (N-L+1)//h.

4) Если последний оператор тела исходного цикла не CONTINUE, то надо этот оператор (CONTINUE) приписать в конце цикла со сгенерированной новой меткой и эту же метку указать в заголовке цикла.

 

Замечание. Пункт 2 приведенного алгоритма может заметно увеличить время выполнения цикла, поскольку заменяет переменную I выражением с тремя операциями. Поэтому, вместо пункта 2 иногда при канонизации удобнее использовать пункт 2’

2’) В теле цикла первым оператором поставить присваивание

 I = (h*(J-1)+L).

У такой формы канонизации общий объем вычислений увеличится не сильно, но появиться дополнительный оператор и в индексных выражениях вместо нового счетчика цикла J будет стоять индуктивная переменная I.

 

Пример 85. Для цикла

DO 99 I = K-1, N, 2

if (A(I)< X) goto 99

K = B+X

99 X = I+X

канонический вид будет следующий

DO 88 J = 1, (N-K)//2

if (A(2*(J-1)+K-1)< X) goto 99

K = B+X

99 X = 2*(J-1)+K-1+X

88 CONTINUE

Конец примера.

 

Канонический вид цикла допускает вариации, в зависимости от дальнейших преобразований. Следует отметить, что для некоторых преобразований удобно иметь цикл, у которого начальное значение счетчика (левая граница) равно 0 (например, [ 68 ]). Иногда перед циклом и после цикла добавляются пустые операторы, которые перехватывают передачи управления, ведущие на заголовок цикла и выходящие из цикла соответственно [ 121 ].

 

 

⇐ Предыдущая13141516171819202122Следующая ⇒

Поделиться: