Optymalizacja kodu wynikowego

Optymalizacja kodu wynikowego – jeden z etapów działania kompilatora lub interpretera, którego celem jest poprawa wydajności programu przy zachowaniu jego pełnej funkcjonalności. Optymalizacja nie jest wykonywana na poziomie kodu źródłowego programu, lecz na wewnętrznej reprezentacji kodu programu (np. drzewie AST programu). Optymalizacja składa się zwykle z wielu kroków, które mogą być aplikowane wielokrotnie na różnych etapach kompilowania programu.

Optymalizacja pozwala poprawić wydajność, często jednak taki kod jest trudniejszy do debugowania, ponieważ utracona zostaje pełna odpowiedniość pomiędzy kodem źródłowym a wykonywanym.

Niektóre optymalizacje, jak np. pominięcie wskaźników ramek (ang. omit-frame-pointer), uniemożliwiają działanie debugera na niektórych architekturach. Z drugiej strony pominięcie tych wskaźników zwalnia jeden rejestr procesora czyniąc go dostępnym dla innych celów. Program będzie potrzebował również mniej taktów procesora aby mógł się wykonać, ponieważ ta optymalizacja znosi konieczność zapisywania, ustawiania i przywracania zawartości rejestru przechowującego ten wskaźnik.

Metody optymalizacji kodu

Optymalizacje mogą dotyczyć (1) drzewa rozbioru gramatycznego bądź grafu przepływu sterowania, a więc być niezależne od docelowej maszyny, lub też (2) uwzględniać jej specyficzne cechy. W zależności od potrzeb i ustawień kompilacji, metody te mogą być wielokrotnie aplikowane podczas optymalizacji kodu.

Przykłady optymalizacji z pierwszej grupy:

• Wyliczanie wartości stałych (ang. constant folding) – jeśli to możliwe, obliczanie od razu wartości wyrażeń, w których występują stałe argumenty. Niektóre kompilatory potrafią także wyliczać w chwili kompilacji wartości funkcji dla stałych argumentów. Np. x := 5 * 12 – 1; y := cos(0.0) może zostać uproszczone do x := 59; y := 1.0;.
• Propagacja stałych (ang. constant propagation) – jeśli zmiennej zostaje przypisywana wartość stała i następnie zmienna używana jest w jakimś wyrażeniu, zostaje zastąpiona stałą. Np. x := 5; y := x * 3 może zostać uproszczone do x := 5; y := 5 * 3 (po wyliczaniu wartości stałych ostatnia instrukcja uprości się z kolei do y := 15).
• Upraszczanie wyrażeń logicznych i arytmetycznych – zastosowanie znanych własności i tożsamości, np. unikanie mnożenia przez 1 czy dodawania 0.
• Eliminacja zbędnych wyrażeń – pomijanie tych instrukcji lub wyrażeń, które nie są używane lub których obliczenie będzie miało ten sam wynik. Np. w x := 7; y := 5; x := 12 pierwsze przypisanie może zostać pominięte, bo wartość x = 7 nie jest używana i jedynie zastępowana nową wartością 12.
• Eliminacja wspólnych podwyrażeń (ang. common subexpression elimination) – gdy jakieś podwyrażenie występuje kilkakrotnie w różnych wyrażeniach, jest liczone tylko raz.
• Łączenie instrukcji (ang. instruction combining) – gdy kolejne instrukcje wykonują podobne działania są zastępowane jedną instrukcją, np. x := x + 5; x := x – 3 jest zastępowane jedną instrukcją x := x + 2.
• Jednokrotne obliczenie wartości niezależnych od pętli – przesunięcie poza pętlę wszystkich wyrażeń, które nie zależą od przebiegu pętli.
• Wstawienie treści funkcji w miejscu wywołania (ang. inlining) – pozwala uniknąć kosztów wywołania podprogramu, ma zastosowanie głównie dla krótkich funkcji, zawierających zwykle kilka instrukcji; jeśli funkcja jest wywoływana w programie raz, względnie niewielką liczbę razy również może zostać wstawiona w miejscu wywołania. Powoduje zwiększenie wielkości kodu wynikowego.
• Łączenie pętli (ang. loop fusion) – wykonywanie w jednej pętli instrukcji z sąsiednich pętli, mających te same warunki iterowania.
• Spłaszczanie pętli (ang. loop collapsing) – zastępowanie kilku zagnieżdżonych pętli jedną pętlą.
• Zastępowanie rekursji ogonowej przez iterację
• Eliminacja identycznych argumentów funkcji – jeśli pewne argumenty funkcji są we wszystkich jej wywołaniach takie same, kompilator może zrezygnować z ich bezpośredniego przekazywania; np. jeśli te argumenty są stałe, zostaną wstawione wprost w treści funkcji.
• Eliminacja nieosiągalnego kodu (ang. dead code elimination) – usuwanie z wyjścia nieosiągalnych fragmentów programu; ma na celu zmniejszenie rozmiaru kodu wynikowego.
• Zmiana kolejności bloków podstawowych w celu zmniejszenia liczby skoków.
• Łączenie bloków podstawowych
• Eliminacja zbędnych instrukcji warunkowych

Przykłady optymalizacji z drugiej grupy:

• Zmniejszanie kosztu operacji – wybór szybszych operacji arytmetyczno-logicznych, np.:
  • mnożenie przez stałą zastępuje się dodawaniem i przesunięciami bitowymi,
  • dzielenie przez potęgi dwójki również zastępują przesunięcia bitowe,
  • wyliczanie modulo potęga dwójki zastępuje iloczyn bitowy,
  • potęgowanie ze stałym wykładnikiem całkowitym można zastąpić ciągiem mnożeń i dodawań,
  • dzielenie przez stałą można zastąpić mnożeniem przez odwrotność (również dotyczy to działania na liczbach całkowitych),
  • w przypadku pętli, mnożenia zależne od numeru iteracji zastępowane są przez dodawanie.
• Optymalizacja przez dziurkę od klucza lub przez szparkę (ang. peephole optimization) – analiza wykonywana na niewielkiej liczbie sąsiednich instrukcji, której celem jest zastąpienie znanych wzorców instrukcji równoważnymi, specyficznymi dla danego procesora rozkazami, pozwalającymi wykonać określone działania szybciej. Np. ustawienie lub wyzerowanie bitu można wykonywać standardowymi operacjami bitowymi (AND, OR), jednak istnieją procesory posiadające rozkazy, które wprost działają na bitach.
• Rozwijanie pętli (ang. loop unrolling) – polega na powtórzeniu treści pętli kilka razy i jednocześnie wykonaniu proporcjonalnie mniejszej liczby obiegów pętli. Koszt wykonywania instrukcji skoku, koniecznych w realizacji pętli, są w procesorach potokowych znaczne, ten rodzaj optymalizacji pozwala osiągnąć większą wydajność.
• Wektoryzacja – użycie rozkazów wektorowych SIMD tam, gdzie jest to możliwe.

Optymalizacja wiąże się również z alokacją rejestrów, czyli określeniem, w których rejestrach procesora będą zapisywane wartości na poszczególnych etapach obliczeń. Dąży się do minimalizacji liczby przesłań wartości między rejestrami a pamięcią, w szczególności często wykorzystywane wartości powinny znajdować się w rejestrach.

Kompilator może też optymalizować powszechnie używane funkcje biblioteczne. Znając ich działanie w pewnych przypadkach zastępuje wywołania funkcji równoważnym ciągiem instrukcji. Np. w języku C funkcja memset zeruje wskazany obszar pamięci, dla niewielkich obszarów kompilator może wstawić kilka instrukcji procesora zerujących pamięć. Podobnie, zamiast wywołania funkcji formatującej printf("%s\n", napis), która w tym przypadku jedynie wypisze napis, można zastosować szybszą funkcję puts(napis).

Optymalizacje w GCC

Kompilator GCC przeprowadza najpierw optymalizację niezależną od architektury, a następnie, jeśli użytkownik sobie tego zażyczy, optymalizację kodu pod konkretny procesor lub nawet model procesora.

Optymalizacja ogólna jest wykonywana na zasadach, które są wspólne dla wszystkich maszyn, architektur i procesorów. Użytkownik może samodzielnie wybrać optymalizacje, które mają zostać wykonane, albo wybrać jeden ze zdefiniowanych poziomów optymalizacji (przełączniki -O, -O2, -O3, -Os):

• -O – optymalizacja tylko w zakresie podstawowym, skraca to proces kompilacji programu;
• -O2 – wszystkie bezpieczne optymalizacje, tzn. nie zostanie włączona żadna optymalizacja, która mogłaby zmienić w istotny sposób działanie programu (np. zmniejszyć precyzję obliczeń zmiennoprzecinkowych);
• -O3 – najwyższy poziom optymalizacji, może powodować problemy w działaniu skomplikowanych programów, zmniejszyć precyzję obliczeń i spowodować znaczny wzrost objętości kodu maszynowego programu;
• -Os – kod optymalizowany w celu minimalizacji rozmiaru pliku wykonywalnego;
• -Og – stosuje optymalizacje, które przyspieszają pracę programu, nie spowalniają znacząco kompilacji ale zapewniają możliwość debugowania kodu aplikacji;

Wbrew pozorom najwyższy poziom optymalizacji (-O3) nie musi przekładać się na szybsze działanie programu. Dłuższy kod wynikowy sprawia, że stosunkowo niewielka jego część da się zmieścić w szybkiej pamięci podręcznej procesora.

Kompilator może również wykonać wiele optymalizacji, aby program lepiej działał na konkretnej maszynie. Jest to związane z pewnymi charakterystycznymi cechami procesora, takimi jak: ilość i rodzaje rejestrów (np. procesory PowerPC mają więcej rejestrów ogólnego przeznaczenia niż Pentium), ilość i algorytmy zarządzające pamięcią cache (aby zmaksymalizować jej użycie). Rodzaje instrukcji (z naciskiem na instrukcje wyspecjalizowane do obróbki pewnych typów danych oraz instrukcje SIMD), potokowość czy superskalarność mają również ogromne znaczenie z punktu widzenia optymalizacji.

GCC na platformie x86 potrafi optymalizować kod pod szereg różnych procesorów. Włączenie optymalizacji powoduje często, że kod wynikowy nie uruchomi się na innym, podobnym procesorze lub będzie na nim działał wyjątkowo wolno.

Bibliografia

• Optymalizacja. W: William McCastline Waite, Gerhard Goos: Konstrukcja kompilatorów. Warszawa: Wydawnictwa Naukowo-Techniczne, 1989. ISBN 83-204-0991-8.brak strony w książce
• Optymalizacja przekładu. W: David Gries: Konstrukcja translatorów dla maszyn cyfrowych. Warszawa: Państwowe Wydawnictwo Naukowe, 1984. ISBN 83-01-02230-2.brak strony w książce