6.5. Способи оптимізації

Розрізняють дві категорії оптимізуючих перетворень: перетворення вихідної програми в її внутрішній формі, що не залежать від об'єктної мови (машинно-незалежні) і перетворення, здійснювані на рівні об'єктної програми (машинно-орієнтовані). Методи першої категорії застосовні майже до будь-якої мови програмування.

На практиці використовується дуже широкий набір машинно-незалежних оптимізуючих перетворень, що пов'язане з великою розмаїтістю неоптимальностей. До них відносяться:

- розвантаження ділянок повторюваності;

- спрощення дій;

- реалізація дій;

- чищення програми;

- економія пам'яті;

- скорочення програми.

6.5.1. Розвантаження ділянок повторюваності

Таку назву одержав спосіб оптимізації, що полягає в винесенні обчислень з багаторазово проведених ( що виконуються ) ділянок програми на ділянки програми, рідко прохідні.

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

попередні результати лінійні чи компоненти групи лінійних

компонент ділянки повторюваності виносяться з нього і розміщаються за виходи з ділянки повторюваності - чищення вниз.

При чищенні нагору винесені обчислення утворять новий безпосередній обов'язковий попередник ділянки повторюваності, а при чищенні вниз - безпосередній обов'язковий спадкоємець ділянки повторюваності.

Звичайно виносяться тільки такі вирази і лінійні фрагменти програми, що обов'язково виповнюються при кожнім проходженні ділянки повторюваності, що розвантажується.

Приклади.

а) Чищення вниз перетворить цикл

for K:=1 to 100 do

begin

X:=X*K;

if Z>0 then Y:=sin(X)

else A[I]:=X+2;

end

до виду:

for K:=1 to 100 do X:=X*K;

if Z>0 then Y:=sin(X);

else A[I]:=X+2;

б) Чищення нагору перетворить цикл

for K:=1 to 100 do

begin

if Z>0 then Y:=1

else Y:=Z+2;

X[K]:=X[K]-Y;

end

до виду

if Z>0 then Y:=1

else Y:=Z+2;

for K:=1 to 100 do X[K]:=X[K]-Y;

Прикладом чищення тіла рекурсивної функції може бути наступний:

тіло рекурсивної функції

ціла функція Ф(N)

begin

цілі Z,W;

W:=1;

if X>0 then W:=Y;

if N<=0 then Ф:=1

else

begin

Z:=N-W; Ф:=Z*Ф(Z)

end

end

де міститься два інваріантних гамаки, у результаті винесення яких може бути отримана наступна функція:

ціла функція Ф(N)

begin

var N:integer;

ціла функція F(M)

begin

var Z:integer;

if M<=0 then F:=1;

else

begin

Z:=M-W;

F:=Z*F(Z)

end

end

W:=1;

if X>0 then W:=Y;

Ф:=F(N);

end;

У групу розвантаження ділянок повторюваності також входять і різні перетворення, що здійснюють переміщення гамака по шляху, що веде до місця використання його результатів. При такім перетворенні на відміну від чищень гамак залишається в тих же зонах, циклах і процедурах

Наприклад, за допомогою цих перетворень фрагмент

for K:=1 then

begin

if N>0 то перехід на L;

N:=N*N;

L: if Z=0 then write(N);

end

N:=100;

може бути перетворений до виду:

for K:=1 to 100 do

if Z=0 then

begin

N:=A[K];

if N>0 then goto L;

N:=N*N;

L: write(N);

end;

N:=100;