ELSE FALSE

Переопределим синтаксис и семантику логических выражений следующим образом:

S ® E

E ® TôT OR E

T ® FôF AND T

F ® iô(E)ôNOT F

Где: C OR D определяется, как IF C THEN TRUE ELSE D;

C AND D определяется, как IF C THEN D ELSE FALSE;

NOT C определяется, как IF C THEN FALSE ELSE TRUE;

При генерации тетрад используются идентификаторы, константы 0 (FALSE) и 1 (TRUE), тетрада (:=, K,, X) – что соответствует X:= K и тетрада (B, Y, i, j). Последняя тетрада имеет следующий смысл: если идентификатор Y имеет значение TRUE, то осуществляется переход на i -ю тетраду, в противном случае на j -ю.

На рис. 7.4 приведено несколько примеров, при разборе которых надо учесть, что результат выражения всегда заносится в X. В первой тетраде в X заносится 1, то есть значение выражения вначале предполагается равным TRUE. Если обнаруживается, что выражение и в самом деле имеет значение TRUE, то выполняется переход с пропуском оставшихся тетрад, в том числе и последней. Если же значение выражения FALSE, то происходит переход на последнюю тетраду, в которой в X заносится 0.

Идентификаторы в тетрадах с рис. 7.4 располагаются в том же порядке, что и в исходном выражении. И наконец, для оператора NOT тетрады не генерируются. Если A представляется, как (B, A, i, j), то NOT A, как (B, A, j, i), то есть меняются местами адреса переходов по TRUE и FALSE.

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

ВЫНЕСЕНИЕ ИНВАРИАНТНЫХ ВЫЧИСЛЕНИЙ ЗА ЦИКЛ

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

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

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.

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

Поиск по сайту: