Optymalizacja kodu wynikowego

Ten artykuł trzeba dopracować zgodnie z zaleceniami edycyjnymi: opis optymalizacji GCC całkowicie tu nie pasuje. Dokładniejsze informacje o tym, co trzeba poprawić, być może leżą na stronie dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości prosimy usunąć szablon {{Dopracować}} z kodu tego artykułu.

Optymalizacja kodu wynikowego – proces, w którym dosłowna wersja kodu źródłowego, zwykle w postaci jakiegoś drzewa, jest przekształcana w osoba umożliwiającą sprawne wykonanie.

Optymalizacja dopuszcza poprawić wydajność, wielokrotnie jednak taki kod jest trudniejszy do debugowania, albowiem utracona zostaje pełna odpowiedniość pomiędzy kodem źródłowym a wykonywanym.

Pewne optymalizacje, jak np. pominięcie wskaźników ramek (ang. omit-frame-pointer), uniemożliwiają działanie debugera na poniektó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ł także mniej taktów procesora aby mógł się wykonać, albowiem ta optymalizacja znosi konieczność zapisywania, ustawiania oraz przywracania zawartości rejestru przechowującego ten wskaźnik.

Optymalizacja w celu uzyskania wyższej szybkości wykonywania kodu przez procesor bywa prowadzona w kilku krokach oraz na wielorakich etapach.

Metody optymalizacji kodu

Optymalizacje potrafią dotyczyć (1) drzewa rozbioru gramatycznego bądź grafu przepływu sterowania, a więc być niezależne od docelowej maszyny, albo też (2) uwzględniać jej specyficzne cechy. W zależności od potrzeb oraz ustawień kompilacji, metody te bywają 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 są stałe argumenty. Pewne kompilatory umieją 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 oraz 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 oraz arytmetycznych - zastosowanie znanych własności oraz tożsamości, np. unikanie mnożenia przez 1 czy dodawania 0.
• Eliminacja zbędnych wyrażeń - pomijanie tych instrukcji albo wyrażeń, które nie są używane albo 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 oraz zaledwie zastępowana nową wartością 12.
• Eliminacja wspólnych podwyrażeń (ang. common subexpression elimination) - kiedy jakieś podwyrażenie jest kilkakrotnie w wielorakich wyrażeniach, jest liczone tylko raz.
• Łączenie instrukcji (ang. instruction combining) - kiedy 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) - dopuszcza uniknąć kosztów wywołania podprogramu, ma zastosowanie z reguły dla krótkich funkcji, zawierających zwykle parę instrukcji; jeśli funkcja jest wywoływana w programie raz, względnie niewielką liczbę razy także 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; prowadzi do zmniejszenie rozmiaru kodu wynikowego.
• Przeistoczenie 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 oraz przesunięciami bitowymi,
  • dzielenie przez potęgi dwójki także zastępują przesunięcia bitowe,
  • wyliczanie modulo potęga dwójki zastępuje iloczyn bitowy,
  • potęgowanie ze stałym wykładnikiem całkowitym da się zastąpić ciągiem mnożeń oraz dodawań,
  • dzielenie przez stałą da się 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 albo 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 albo wyzerowanie bitu da się wykonywać standardowymi operacjami bitowymi (AND, OR), jednak są procesory posiadające rozkazy, które wprost działają na bitach.
• Rozwijanie pętli (ang. loop unrolling) - opiera się na powtórzeniu treści pętli parę razy oraz równocześnie wykonaniu proporcjonalnie mniejszej liczby obiegów pętli. Koszt wykonywania instrukcji skoku, koniecznych w realizacji pętli, są w procesorach potokowych znaczne, ten odmiana optymalizacji dopuszcza osiągnąć większą wydajność.
• Wektoryzacja - użycie rozkazów wektorowych SIMD tam, gdzie jest to możliwe.

Optymalizacja wiąże się także 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 pomiędzy rejestrami a pamięcią, w szczególności wielokrotnie 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ć parę instrukcji procesora zerujących pamięć. Podobnie, zamiast wywołania funkcji formatującej printf("%s\n", napis), która w tym przypadku zaledwie wypisze napis, da się 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 albo nawet model procesora.

Optymalizacja ogólna jest wykonywana na zasadach, które są wspólne dla wszystkich maszyn, architektur oraz procesorów. Użytkownik może samodzielnie wybrać optymalizacje, które posiadają 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ń oraz spowodować znaczny wzrost objętości kodu wykonywalnego programu;
• -Os – kod optymalizowany w celu minimalizacji rozmiaru pliku wykonywalnego;

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ąstka da się zmieścić się w szybkiej pamięci podręcznej procesora.

Kompilator może także wykonać wiele optymalizacji, aby program lepiej działał na konkretnej maszynie. Jest to związane z pewnymi charakterystycznymi cechami procesora, takimi jak: ilość oraz rodzaje rejestrów (np. procesory PowerPC posiadają więcej rejestrów ogólnego przeznaczenia niż Pentium), ilość oraz 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), wielopotokowość, czy superskalarność posiadają także ogromne znaczenie z punktu widzenia optymalizacji.

GCC na platformie x86 potrafi optymalizować kod pod szereg wielorakich procesorów. Włączenie optymalizacji powoduje często, że kod wynikowy nie uruchomi się na innym, podobnym procesorze albo 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 8320409918. 
• Optymalizacja przekładu. W: David Gries: Konstrukcja translatorów dla maszyn cyfrowych. Warszawa: Państwowe Wydawnictwo Naukowe, 1984. ISBN 8301022302.