Оптимизация программ

Алгоритм преобразования арифметических выражений в ПОЛИЗ.

1. Поступающие на вход операнды сразу проходят на выход.

2. Поступающие на вход операторы сравниваются по приоритету. Если приоритет оператора на входе магазина больше, чем в верхушке магазина, то оператор со входа поступает в магазин (first in/last out). Если приоритет оператора на входе меньше или равен приоритету оператора в верхушке магазина, то оператор из верхушки магазина идет на выход и сравнение повторяется. Эти процедуры выполняются до тех пор, пока не исчерпается строка.

y:=a*(b+c) ­e/(d-k)

y сразу проходит на выход…

) / )

yabc yabc + e yabc + e­*dk yabc + e­*dk-/:=

1 23 2 32

При выполнении используется стек.

Операнды поступают в стек. Поступив на вход стека, оператор вытягивает из стека столько операндов, сколько ему нужно. Результат заталкивается в вершину стека.

2 2

3 5 25 3 1 25

2 1 1 25 25 y

1 y y y y

y

Если не принять специальных мер, в результате трансляции получаются программы,

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

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

“Плюсы” оптимизации на последних этапах (проходах) очевидны – именно там аккумулируются результаты неоптимальных решений на всех предыдущих этапах трансляции.

Оптимизация на начальных этапах:

1. Предварительное вычисление выражений.

При данных x := 2; y := 3;

оператор z:= x + y + 10

замена на z := 15;

2. Исключение невыполнимых ветвей. То есть тех ветвей, которые соответствуют невыполнимому сочетанию условий.

3. Выделение общих частей.

a := (x + y) * z - 35;

b := ((x + y) * z) / a;

4. Вынесение за цикл.

for i := 1 to 10 do begin

x := x + i; P(x);

k := b + c; /* выносится за цикл, т.к. не зависит

от параметра цикла */.

end;

Измененный вариант

k := b + c;

for i := 1 to 10 do begin

x := x + i; P(x);

end;

5.Вычисление логических выражений.

x => y & (z = 5 Ú x ¹ 5)

Так, например, при ложном условии x => y конъюнкция ложна вне зависимости от истинности условия в скобках. А само условие в скобках при истинности z = 5 истинно вне зависимости от выполнения второго скобочного условия.

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