|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
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.
Трудно найти компилятор, в котором были бы реализованы все перечисленные методы оптимизации. Да, скорее всего, это и не нужно, - такой компилятор работал бы чрезвычайно медленно. Мы здесь лишь коснулись возможных методов оптимизации, не давая готовых рецептов реализации. От вашего учебного компилятора не потребуется оптимизировать все и вся. Этот материал дан в первую очередь для того, чтобы вы сами разрабатывали более эффективные программы, не смотря на сверхпроизводительность вашего компьютера. Эффективное программирование – это немаловажный фактор, по которому судят о квалификации программиста. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.) |