7.4. Вынесение инвариантных вычислений за цикл

Если вычисления внутри цикла зависят от переменной, которая в этом цикле не изменяется, то это вычисление можно вынести из цикла Это приведет к реорганизации части матрицы тетрад. При этом необходимо решить три задачи:

 Распознавание инвариантных вычислений – это наиболее сложная из них. Например, требуется определить, что можно вынести из цикла в следующей программе:

FOR i 1 TO 10 DO BEGIN





FOR j 1 TO 10 DO BEGIN

LA  A 10;

LB  B  Y[i +2];

LC  C  C+10

END;

END;

Оператор с меткой LA приводит всегда к одному и тому же результату и поэтому может быть вынесен за цикл. В операторе LB индексное выражение i + 2 также не меняется при выполнении внутреннего цикла и может быть без ущерба вынесено из него. Можно также проверить, изменяется ли во внутреннем цикле значение Y и B и если они не меняется, то за внутренний цикл можно вынести весь оператор с меткой LB. Оператор LC включает в себя переменную C, значение которой меняется во внутреннем цикле, и, следовательно, этот оператор из цикла выносить нельзя. Заметим, что, если перед LA имеются операторы (внутри цикла), которые ссылаются на A или B, то в этом случае ничего кроме вычисления индексного выражения мы из цикла вынести не сможем.

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

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

Для циклов можно предложить и другие методы оптимизации. Иногда два цикла можно объединить в один, уменьшив таким образом число команд проверки и приращения значения переменной цикла. Например, следующие операторы:

FOR i 1 TO 100 DO A[ i ] 0

FOR j 1 TO 100 DO B[ j ] 3C[ j ]

можно объединить в один цикл:

FOR k 1 TO 100 DO BEGIN A[ k ] 0 B[ k ] 3C[ k ] END;

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

FOR i 1 TO 100 DO

IF X > Y THEN A[ i ]  B[ i ] + X

ELSE A[ i ]  B[ i ]  Y;

можно превратить в

IF X > Y THEN

FOR i 1 TO 100 DO A[ i ]  B[ i ] + X

ELSE

FOR i 1 TO 100 DO A[ i ]  B[ i ]  X;

В преобразованной программе условный оператор выполняется лишь один раз, в то время как в исходной он бы исполнялся 100 раз.

Внутри циклов целесообразно по возможности уменьшать силу операций. Например цикл

FOR i 1 TO 100 DO Q[ i ] i  5;

можно заменить на

J5; FOR i 1 TO 100 DO BEGIN Q[ i ]  J; J  J  5 END;

Умножение i  5 в исходном цикле заменено более быстрым сложением: J  5.

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