Глобалната оптимизация включва преобразования, които се извършват в рамките на една функция и не изискват промяна в аргументите й. Този тип оптимизационни преобразувания са машиннонезависими, т.е. не зависят от типа на използвания процесор.
Съвременните компилатори се справят много добре с този вид оптимизации. В това отношение се отличава и ГНУ-компилаторът.
Глобалните оптимизационни преобразования се характеризират с голямо разнообразие. Ще разгледаме с помощта на примери някои от тях[5].
Пример 2.4. Общи действия в двата клона на условен оператор
Действия, които са общи за двата клона на условен оператор, често може да се изкарат извън условния оператор. Например фрагментът
if (y>0) {
x = x + 1; z = 2; w = z + x;
} else {
x = x + 1; w = z + x;
}
се опростява до
x = x + 1;
if (y>0) z = 2;
w = z + x;
Този тип преобразувания не само съкращават програмата, но увеличават полезността на изпреварващите изчисления, които съвременните микропроцесори извършват, така че в крайна сметка увеличават и скоростта.
Една и съща операция, която многократно се повтаря в цикъл, често може да се изнесе преди или след него.
Пример 2.5. Изкарване на повтарящи се оператори след цикъл
Цикълът
for (i=0;i<10000;i++) {
x = x * i;
if (z <= 0) y = sin (x);
a [j] = x + 2;
}
може да се опрости по следния начин:
for (i=0; i<10000; i++) {
x = x * i;
}
if (z <= 0) y = sin (x);
a [j] = x + 2;
Пример 2.6. Изкарване на повтарящи се оператори пред цикъл
Цикълът
while (s[i] != '\0') {
c = '?';
if (! isascii(s[i]))
s[i] = c;
i++;
}
се опростява по следния начин:
if (s[i] != '\0') {
c = '?';
do {
if (! isascii(s[i]))
s[i] = c;
i++;
} while (s[i] != '\0');
}
Пример 2.7. Комутативност между условен оператор и цикъл
Да разгледаме следния фрагмент:
for (i = 0; i < 10000; i++) {
a [i] = i;
if (u != 0) a [i] = 0;
b [i] = 2 + a [i];
}
Лесно се забелязва, че двойното присвояване на стойност на a[i] може да се избегне по следния начин:
for (i = 0; i < 10000; i++) {
if (u != 0)
a [i] = 0;
else
a [i] = i;
b [i] = 2 + a [i];
}
В действителност обаче съвременните компилатори ще опростят този фрагмент по следния начин:
if (u != 0)
for (i = 0; i < 10000; i++) {
a [i] = 0;
b [i] = 2;
}
} else {
for (i = 0; i < 10000; i++) {
a [i] = i;
b [i] = 2 + i;
}
}
Това става така, защото в днешно време компилаторите предпочитат преди всичко да подобрят скоростта на програмата, дори когато това е за сметка на размера й. Те обръщат повече внимание на размера на генерираната програма, само ако специално поискаме това.
Рекурсивните функции също се опростяват. Опашковата рекурсия се превръща в обикновен цикъл. Подобно на циклите, и тук често е възможно повтарящите се операции да се изпълняват само веднъж.
Пример 2.8. Ускоряване на рекурсивни функции
Да разгледаме следната функция:
int g (int x) {
int z = y;
if (w <= 0)
z = 100;
if (x == 0)
return 1;
else
return z * x * g(x-1);
}
Тя ще се опрости по следния начин:
int g(int x) {
int z;
int g1(int x) {
if (x == 0)
return 1;
else
return z * x * g1(x-1);
}
if (w <= 0)
z = 100;
else
z = y;
return g1(x);
}
Тук функцията g1 е вложена в стил Алгол и Паскал във функцията g и „вижда“ променливата z[6].
Пример 2.9. Обединяване на съседни цикли
Да разгледаме следния пример:
for (i=0; i<1000; i++)
a [i] = 0;
for (i=0; i<10000; i++)
b [i] = 0;
Тук операциите за проверка на край на циклите, както и за увеличаване на i се изпълняват общо 11000 пъти. Но ако обединим циклите по сления начин
for (i=0; i<1000; i++) {
a [i] = 0;
b [i] = 0;
}
for (i=1000; i<10000; i++)
b [i] = 0;
те ще се изпълняват само 10000 пъти.
Пример 2.10. Размяна на вложени цикли
Да разгледаме следния пример:
for (i=0; i<10000; i++)
for (j=0; j<10; j++)
a [i][j] = 0;
Тук операциите за проверка на край на циклите, както и за увеличаване на i и j се изпълняват общо 10000+10000.10 = 110000 пъти. Но ако двата цикъла се разменят по следния начин
for (j=0; j<10; j++)
for (i=0; i<10000; i++)
a [i][j] = 0;
те ще се изпълняват само 10+10.10000 = 100010 пъти.
Сега ще разгледаме още един важен тип оптимизационно преобразование. То може да се приложи при повечето от разгледаните примери, но го отложихме досега, за да не усложняваме излишно нещата.
Пример 2.11. Опростяване на индуктивни операции
Да разгледаме следния пример:
k = 1;
do {
v = (k-1)*n + i;
a[v] = 0;
k = k + 1;
} while (k <= m);
Тук стойноста на v на всяка стъпка се увеличава с n. Ако използваме този факт, ще можем значително да опростим израза, с който присвояваме стойност на v:
k = 1;
int v = i;
a[v] = 0;
k = k + 1;
while (k <= m) {
v = v + n;
a[v] = 0;
k = k + 1;
}
Дори и тук обаче, в цикъла има операция, която компилаторите ще отстранят. Изразът a[i] е еквивалентен на *(a+i). В него събирането може да се елиминира!
k = 1;
int *b = a + i;
*b = 0;
k = k + 1;
while (k <= m) {
b = b + n;
*b = 0;
k = k + 1;
}
v = b - a;
При повечето случаи от този тип, последният оператор е ненужен, тъй като стойността на v не се използва никъде. Ако това е така, компилаторът няма да генерира код за този оператор.