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

 

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

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

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

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

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

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

Приклади.

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

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;

Скорочення глибини операції

 

Скорочення глибини операції - процедура виносу за межі циклу операторів, аргументи яких є функціями рекурсивно означених змінних, і заміна їх усередині циклу простими рекурсивними операторами присвоювання, аргументи яких не залежать від інших змінних.

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

Наведемо приклад скорочення глибини операції стосовно оператора t4:=K*10+I з n-го блоку:

 

n-й блок

L:t4:=K*10+I

t5:=t6+K

z(t2):=z(t2)+x(t4)+y(t5)

K:=K+1

перехід на L

 

у результаті виконання цієї операції оператор t4:=K*10+I

зсувається в (n-1)-й блок, а в n-му блоці він заміняється оператором t4:=t4+10:

(n-1)-й блок

...

t4:=K*10+I

n-й блок

L: z(t2):=z(t2)+x(t4)+y(t5)

K:=K+1

t4:=t4+10

t5:=t6+K

перехід на L

 

Спрощення дій

 

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

Видалення індуктивних змінних і виразів

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

Наприклад, застосування зазначених перетворень перетворить фрагмент

for I:=1 to 99 do

begin

K:=I+J;

A[K]:= A[K]+1

end;

K:=10;

у фрагмент

I:=1;

for K:=I+J to 99+J do

begin

A[K]:= A[K]+1

end;

K:=10;

Тут I,K - індуктивні змінні. У даному випадку з циклу видалений індуктивний вираз K:=I+J.

Заміна складних операцій на більш прості

Дуже важливим перетворенням з цієї групи є зниження сили операцій, що заміняє в індуктивних обчисленнях складні операції на більш прості; наприклад, піднесення до степеня або ділення заміняється множенням (наприклад, вираз Х/4.0 заміняється на вираз Х* О.25), а множення - додаванням

Наприклад, застосування цього перетворення дозволяє переходити від циклу

for K:=1 to 100 do

V:=(K-1)*N+I

до більш ефективно працюючого фрагмента:

V:=I;

for K:=1 to 100 do

begin

A[V]:=A[V]+1;

V:=V+N

end

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

 

Виключення надлишкових виразів

 

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

Наприклад, ця операція здійснює перехід від фрагмента

if B>0 then

begin

A:=A+2;

X:=A*B+C

end

else Y:=A*B+D;

Z:= A*B;

до фрагмента

if B>0 then

begin

A:=A+2;

W:=A*B;

X:=W+C

end

else

begin

W:=A*B;

Y:=W+D

end;

Z=W;

 

Інші перетворення

 

У цю же групу входить економія загальних підвиразів, що заміняє, наприклад, оператор:

X:=(A+B)*(A+B+C)/(A+B+E)

на фрагмент Y:=A+B; X:=Y*(Y+C)/(Y+E),

а також такі перетворення, як втягування обчислення параметрів у процедуру, спрощення підстановки параметра-масиву, перебудови умовних операторів (типу заміни оператора, якщо X>0 && Y<2 то Z:=1 на оператор, якщо X>0 то початок якщо Y<2 то Z:=1 кінець), видалення копіювань (зокрема, тих, що заміняють пересилання значень масиву на пересилання його вказівника), інші різні способи перебудови структури інформаційних об'єктів у залежності від характеру їх використання і з метою скорочення часу роботи з об'єктами; різні способи реалізації змінних через швидкі регістри, заміна рекурсії на цикли

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

 

Реалізація дій

Це спосіб підвищення якості програми за рахунок виконання певних обчислень на етапі трансляції. Набір перетворень даного типу містить у собі наступні оптимізації:

· константні дії (підстановка або згортання констант), коли відбувається виконання операцій над константами;

· розпроцедурення - відкрита підстановка тіла процедури на місце її виклику;

· ліквідація константних розпізнавачів - заміна умовного оператора на одну з його гілок, якщо його умовний вираз має константне значення.

 

Реалізація дій здійснюється також при:

· утягуванні констант, коли вирази, що мають тотожно константні значення, заміняються на ці значення;

· при аналітичних перетвореннях (наприклад, що заміняють Е*1 на Е чи 0*Е на 0, де Е - довільне підвираз);

· ототожненні (чи втягуванні унікальних), що видаляє з програми оператор-пересилання виду X:=Y, де X і Y - змінні, заміняючи або входження X на Y

· утягування нагору (назад) - наприклад, фрагмент Y:=F(W); X:=Y; заміняється на X:=F(W), або входження Y на X - утягування вниз (уперед) - наприклад, X:=Y; якщо Z>0 те W:=Y+1 інакше W:=Y+2 заміняється на фрагмент якщо Z>0 те W:=X+1 інакше W:=X+2.

Підстановка (згортання)

 

Операції, операнди яких відомі під час компіляції, немає необхідності виконувати під час обрахунку.

Підстановка (згортання) - це заміна змінної або mi-ідентифікатора результату заданою чи обчисленою константою, причому ця заміна провадиться під час трансляції, а не в процесі розв'язання.

Згортання головним чином застосовуються до арифметичних операторів +,-,*,/, тому що вони найбільше часто використовуються у вихідній програмі

Чищення програми

Даний спосіб підвищує якість програми за рахунок видалення з її непотрібних об'єктів і конструкцій

Набір перетворень цього типу містить у собі наступні оптимізації:

· видалення ідентичних операторів;

· видалення з програми операторів, недосяжних по управлінню від початкового;

· видалення перетворювачів, що інформаційно не впливають на інші оператори;

· видалення несуттєвих операторів, тобто операторів, що не впливають на результат програми;

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

· видалення процедур, до яких немає звертань;

· видалення невикористовуваних змінних, видів, операцій і т. д.