Czy wiesz, że jesteśmy również na Slacku? Dołącz do nas już teraz klikając tutaj!

Teoria kompilacji: Kompilacja i optymalizacja


2019-02-28, 01:23

Tuż po przetworzeniu plików źródłowych przez preprocesor, efekt jego pracy trafia bezpośrednio do kompilatora, gdzie zostaje poddany procesowi kompilacji. Proces ten, mimo że w głowach wielu osób wydaje się być bardzo skomplikowanym, może zostać zamknięty w łatwą do zrozumienia abstrakcję. Zapraszam na wpis, który wyjaśni na czym dokładnie polega ten proces.

Kompilator idealny

Kompilacja jest względnie prostym procesem, który można podzielić na kilka kroków. Większość kompilatorów (o ile nie wszystkie) implementuje trójetapową abstrakcję:

Proces kompilacji

Pierwszym z etapów kompilacji jest front-end. Przyjmuje on kod źródłowy (po zakończeniu pracy przez preprocesor), po czym rozbija go na tokeny. Tokenami mogą być klamry, nawiasy, przecinki, nazwy (zmiennych, funkcji, klas), wartości (liczbowe, ciągi znakowe) i tak dalej. Następnie, na podstawie określanych przez język zasad, budowane są drzewa składniowe (Abstract Syntaxt Tree, AST), które transformowane są do kodu Interpretacji Wewnętrznej (Internal Representation, IR). W idealnym środowisku kod IR to kod o uniwersalnej składni, niezależnej od aktualnie kompilowanego języka. Jeżeli składnia kodu IR jest uniwersalna, to niewiele już brakuje do tego, aby móc tworzyć dowolną ilość warstw front-endu, rozpoczynających kompilację różnych od siebie języków programowania. Idąc dalej, można by rzec, że utworzenie nowego języka programowania sprowadza się do wymiany warstwy front-endu.


Następnym etapem jest przekazanie przez front-end kodu w postaci składni IR do warstwy middle-end. Tutaj drzewa składniowe poddawane są wielu optymalizacjom. Najczęstszymi powodami optymalizacji kodu są poprawa szybkości jego wykonania oraz zmniejszenie rozmiaru pliku wynikowego. Proces optymalizacji możemy wyobrazić sobie jako zestaw wielu funkcji, które kolejno wykonywane są na drzewach składniowych. Ważną zasadą każdej z nich jest to, aby zachowanie kodu było niezmienne (tj. przykładowo, jeżeli chcemy zwrócić w funkcji wartość -47, to kompilator nie może zadecydować, że będzie to wartość 21). Zakres operacji przebiegów optymalizacyjnych można zatem porównać do etapu refactoringu. Praktycznie każdy kompilator zezwala na sterowanie procesem optymalizacji, o czym kontynuować będę w dalszej części wpisu.


Ostatnim krokiem procesu kompilacji jest warstwa back-endu, która za zadanie ma przekonwertować kod IR na kod w postaci assemblera. O ile kod Interpretacji Wewnętrznej jest uniwersalny i niezależny od architektury, to na tym etapie podejmowane są decyzje na podstawie informacji o rodzaju architektury, na którą kompilowany jest kod. Podobnie jak front-end, kompilatory powinny implementować wiele różnych warstw back-endu, dla każdego typu architektury docelowej osobno. Rola tej warstwy kończy się w momencie wygenerowania plików języka assembly.

Jak to wygląda w praktyce?

Lista kompilatorów C++ jest długa. Jak wejdziemy na Wikipedię, to znajdziemy ich jeszcze więcej. Mimo tak wielkiej konkurencji, w świecie wybiły się głównie trzy kompilatory: GCC, Clang oraz MSVC. Poniżej postaram się omówić krótko każdy z nich.

GCC

Nazwa GCC jest rozwinięciem słów: GNU Compiler Collection. Jest to kompilator włączony do systemu GNU, co oznacza, że zalicza się on do wolnego (słowo pochodzące od wolności) oprogramowania. Jest on skupiony bezpośrednio na języku C oraz C++.

Kompilator ten implementuje abstrakcję front-end/middle-end/back-end. Front-end GCC parsuje kod, wyłuskując z niego pojedyncze tokeny. Następnie z tych tokenów generowane są drzewa składniowe, które dalej przechowywane są jako reprezentacja wewnętrzna o nazwie GIMPLE. Jest to prosty język serwujący w większości maksymalnie trójargumentowe polecenia.

Warstwa middle-end dokonuje optymalizacji, stosując wiele przebiegów optymalizacyjnych. Optymalizacje wykonywane są bezpośrednio na drzewach składniowych, po czym przekazywane są do warstwy back-endu. O ile składnia GIMPLE dobrze sprawdza się podczas optymalizacji, to niestety nie nadaje się ona do generowania kodu assemblera.

Tuż po przekazaniu danych do back-endu drzewa są konwertowane do innego formatu reprezentacji wewnętrznej: RTL (Register Transfer Language), która jest nieco bardziej zbliżona do języka assembly. O ile GIMPLE jest formatem niezależnym od architektury, to już RTL mocno skupia się na architekturze docelowej. Jeżeli chcecie zapoznać się z tym formatem zapisu, to zachęcam Was do zapoznania się z 10-tym rozdziałem dokumentacji GCC, który jest mu pełni poświęcony. W ostatnim kroku generowany jest plik z kodem źródłowym assemblera.

Kompilator GCC posiada bardzo rozbudowaną dokumentację, która w bardzo przystępny sposób przekazuje wiedzę związaną z procesem kompilacji. Link do dokumentacji: https://gcc.gnu.org

Clang

Clang jest to projekt o otwartym źródle, oparty o kompilator LLVM (Low Level Virtual Machine). LLVM podobnie jak GCC implementuje abstrakcję front-end/middle-end/back-end. Nazwa Clang ma dwa znaczenia:

  • Clang potrafi zachowywać się jako sterownik kompilacji. Oznacza to, że steruje on procesem kompilacji, począwszy od uruchomienia preprocesora, przez kompilację, optymalizację aż po linkowanie i generowanie pliku wynikowego. Domyślnym zachowaniem Clang jest bycie sterownikiem kompilacji.
  • Clang to również nazwa warstwy front-endu kompilatora LLVM. Aby ją uruchomić, należy przekazać opcję -cc1 do polecenia kompilującego:

    clang -cc1 main.cpp
    

Architektura kompilatora LLVM jest o wiele bardziej elastyczna względem kompilatora GCC. Po pierwsze, kompilator LLVM nie skupia się wyłącznie na językach C/C++. Języki te są zamknięte jako jeden z wielu front-endów tego kompilatora. Do grona front-endów LLVM zaliczyć możemy takie języki jak: Go, Haskell, Fortran oraz Rust. Dzięki ogólnodostępnym narzędziom developerskim kompilatora LLVM napisanie własnego języka programowania sprowadza się do utworzenia front-endu, który sprawdzi kod pod kątem składniowym/semantycznym, a następnie wygeneruje kod IR.

Jeżeli mowa o interpretacji wewnętrznej LLVM, to w przeciwieństwie do kompilatora GCC, mamy do czynienia z tylko jedną składnią, która jest wykorzystywana zarówno w warstwie middle-endu jak i back-endu.

Bonusowo, znalazłem bardzo ciekawe slajdy, które mogą być dobrym wstępem do interpretacji wewnętrznej kompilatora LLVM. Myślę, że mogą one nieco pomóc wszystkim tym, którzy chcą zrozumieć podstawy konwersji kodu źródłowego na IR.

MSVC

Kompilator MSVC jest rozwiązaniem firmy Microsoft, działającym na systemach operacyjnych Windows. Niestety, mimo poszukiwań nie dotarłem do źródeł, które cokolwiek mówiłyby o procesie kompilacji realizowanym przez ten kompilator. O ile GCC oraz Clang są projektami o otwartych źródłach, a wiedza na temat ich budowy jest łatwo dostępna, to na temat budowy rozwiązań stworzonych przez firmę Microsoft nie znalazłem nic. Może ktoś z Was może podzielić się swoim doświadczeniem w tym temacie? :)

Interpretacja wewnętrzna a generowanie drzew AST

Tak jak wspomniałem wyżej, kompilator operuje na drzewach składniowych. Są to drzewiaste struktury danych zbudowane z tokenów, na które podzielony został kod źródłowy. Istnieje możliwość podglądnięcia wygenerowanego drzewa składniowego powstałego z kompilowanego przez nas kodu. Przyjrzyjmy sie następującym linijkom:

int main() {
    int a = 10;
    int b = 20;
    int c = a + b;
}

Jest to bardzo prosty przykład, dla którego wygenerujemy drzewa składniowe przy użyciu kompilatorów Clang oraz GCC. Uprzedzam jednak: ten kod nie przypomina języka C++. Jest on zapisany przy pomocy składni mającej za zadanie wyświetlić wszystkie informacje potrzebne do odtworzenia struktury drzewa. Dodatkowo (niestety), sposób wygenerowania drzewa oraz struktura kodu wyjściowego zależy bezpośrednio od kompilatora i składni jego interpretacji wewnętrznej.

Dla kompilatora Clang (wersja 7) możemy wyrzucić drzewo składniowe na standardowe wyjście używając polecenia:

clang main.cpp -Xclang -ast-dump

W odpowiedzi na standardowym wyjściu otrzymamy coś na wzór:

TranslationUnitDecl 0x55afaffd5540 <<invalid sloc>> <invalid sloc>
|-TypedefDecl 0x55afaffd5ad0 <<invalid sloc>> <invalid sloc> implicit __int128_t '__int128'
| `-BuiltinType 0x55afaffd57b0 '__int128'
|-TypedefDecl 0x55afaffd5b38 <<invalid sloc>> <invalid sloc> implicit __uint128_t 'unsigned __int128'
| `-BuiltinType 0x55afaffd57d0 'unsigned __int128'
|-TypedefDecl 0x55afaffd5e78 <<invalid sloc>> <invalid sloc> implicit __NSConstantString 'struct __NSConstantString_tag'
| `-RecordType 0x55afaffd5c20 'struct __NSConstantString_tag'
|   `-CXXRecord 0x55afaffd5b88 '__NSConstantString_tag'
|-TypedefDecl 0x55afaffd5f10 <<invalid sloc>> <invalid sloc> implicit __builtin_ms_va_list 'char *'
| `-PointerType 0x55afaffd5ed0 'char *'
|   `-BuiltinType 0x55afaffd55d0 'char'
|-TypedefDecl 0x55afb000a440 <<invalid sloc>> <invalid sloc> implicit __builtin_va_list 'struct __va_list_tag [1]'
| `-ConstantArrayType 0x55afaffd61f0 'struct __va_list_tag [1]' 1 
|   `-RecordType 0x55afaffd6000 'struct __va_list_tag'
|     `-CXXRecord 0x55afaffd5f60 '__va_list_tag'
`-FunctionDecl 0x55afb000a4e8 <main.cpp:1:1, line:5:1> line:1:5 main 'int (void)'
  `-CompoundStmt 0x55afb000a880 <col:12, line:5:1>
    |-DeclStmt 0x55afb000a680 <line:2:2, col:12>
    | `-VarDecl 0x55afb000a600 <col:2, col:10> col:6 used a 'int' cinit
    |   `-IntegerLiteral 0x55afb000a660 <col:10> 'int' 10
    |-DeclStmt 0x55afb000a730 <line:3:2, col:12>
    | `-VarDecl 0x55afb000a6b0 <col:2, col:10> col:6 used b 'int' cinit
    |   `-IntegerLiteral 0x55afb000a710 <col:10> 'int' 20
    `-DeclStmt 0x55afb000a868 <line:4:2, col:15>
      `-VarDecl 0x55afb000a760 <col:2, col:14> col:6 c 'int' cinit
        `-BinaryOperator 0x55afb000a840 <col:10, col:14> 'int' '+'
          |-ImplicitCastExpr 0x55afb000a810 <col:10> 'int' <LValueToRValue>
          | `-DeclRefExpr 0x55afb000a7c0 <col:10> 'int' lvalue Var 0x55afb000a600 'a' 'int'
          `-ImplicitCastExpr 0x55afb000a828 <col:14> 'int' <LValueToRValue>
            `-DeclRefExpr 0x55afb000a7e8 <col:14> 'int' lvalue Var 0x55afb000a6b0 'b' 'int'

Możemy również zapisać wynik tej operacji do pliku:

clang main.cpp -Xclang -ast-dump > dump-file

Kompilator Clang serwuje nam drzewa składniowe w stanie sprzed zabiegów optymalizacyjnych. Możecie sprawdzić to, dorzucając do polecenia kompilującego jedną z flag optymalizacyjnych (wylistowane w następnej części wpisu). Sprawa ma się nieco inaczej z kompilatorem GCC. Kompilator ten pozwala nam przejrzeć stan drzew z każdego etapu optymalizacyjnego. Aby to zrobić, należy do polecenia kompilującego podać przełączniki --dump-tree-all (kod GIMPLE) lub --dump-rtl-all (kod RTL). Przykładowe polecenie kompilujące:

gcc --dump-tree-all main.cpp

Po wykonaniu tego polecenia w miejscu jego wywołania zostanie utworzony zestaw plików zawierających stan drzew po przejściu każdego etapu optymalizacyjnego. U mnie wygląda to tak:

-rw-r--r-- 1 root root 655786 Feb 25 19:51 main.cpp.001t.tu
-rw-r--r-- 1 root root      0 Feb 25 19:51 main.cpp.002t.class
-rw-r--r-- 1 root root    223 Feb 25 19:51 main.cpp.003t.original
-rw-r--r-- 1 root root    147 Feb 25 19:51 main.cpp.004t.gimple
-rw-r--r-- 1 root root    238 Feb 25 19:51 main.cpp.006t.omplower
-rw-r--r-- 1 root root    246 Feb 25 19:51 main.cpp.007t.lower
-rw-r--r-- 1 root root    246 Feb 25 19:51 main.cpp.009t.ehopt
-rw-r--r-- 1 root root    246 Feb 25 19:51 main.cpp.010t.eh
-rw-r--r-- 1 root root    378 Feb 25 19:51 main.cpp.011t.cfg
-rw-r--r-- 1 root root    251 Feb 25 19:51 main.cpp.012t.ompexp
-rw-r--r-- 1 root root    251 Feb 25 19:51 main.cpp.013t.printf-return-value1
-rw-r--r-- 1 root root    251 Feb 25 19:51 main.cpp.019t.fixup_cfg1
-rw-r--r-- 1 root root    263 Feb 25 19:51 main.cpp.020t.ssa
-rw-r--r-- 1 root root    263 Feb 25 19:51 main.cpp.027t.fixup_cfg3
-rw-r--r-- 1 root root    603 Feb 25 19:51 main.cpp.028t.inline_param1
-rw-r--r-- 1 root root    263 Feb 25 19:51 main.cpp.029t.einline
-rw-r--r-- 1 root root      0 Feb 25 19:51 main.cpp.046t.profile_estimate
-rw-r--r-- 1 root root    304 Feb 25 19:51 main.cpp.049t.release_ssa
-rw-r--r-- 1 root root    603 Feb 25 19:51 main.cpp.050t.inline_param2
-rw-r--r-- 1 root root    263 Feb 25 19:51 main.cpp.086t.fixup_cfg4
-rw-r--r-- 1 root root    263 Feb 25 19:51 main.cpp.218t.veclower
-rw-r--r-- 1 root root    263 Feb 25 19:51 main.cpp.219t.cplxlower0
-rw-r--r-- 1 root root    263 Feb 25 19:51 main.cpp.225t.resx
-rw-r--r-- 1 root root    263 Feb 25 19:51 main.cpp.227t.optimized
-rw-r--r-- 1 root root      0 Feb 25 19:51 main.cpp.311t.statistics

Dodatkowo możemy wygenerować plik z pojedynczego etapu optymalizacji (działa dla większości z nich). Aby to zrobić, należy w parametrze --dump-tree-all słowo all zastąpić kodem procesu optymalizacji (np. --dump-tree-release_ssa). W analogiczny sposób możemy wygenerować stan naszych drzew dla kodu RTL. Przykładowe polecenie:

gcc --dump-tree-release_ssa main.cpp

Wygenerowało mi plik main.cpp.049t.release_ssa o zawartości:

;; Function int main() (main, funcdef_no=0, decl_uid=2272, cgraph_uid=0, symbol_order=0)

Released 0 names, 0.00%, removed 0 holes
int main() ()
{
  int c;
  int b;
  int a;
  int D.2278;
  int _4;

  <bb 2> [0.00%]:
  a_1 = 10;
  b_2 = 20;
  c_3 = a_1 + b_2;
  _4 = 0;

<L0> [0.00%]:
  return _4;

}

Nieco wyprzedziłem materiał, więc… przejdźmy w takim razie do omówienia procesu optymalizacji.

Optymalizacja

Proces optymalizacji jest to proces polegający na modyfikowaniu drzew składniowych, nie zmieniając przy tym samego zachowania kodu. Można ten proces porównać do refactoringu, gdzie częścią wspólną obydwu z nich będzie niezmienność działania programu przy jednoczesnej poprawie kodu. Wszystkie optymalizacje są przeprowadzane na kodzie IR, która reprezentuje drzewa składniowe.

Optymalizować kod możemy w celu:

  • optymalizacji czasu kompilacji
  • optymalizacji wielkości kodu wynikowego
  • optymalizacji czasu wykonania programu
  • optymalizacja w celu lepszej pracy debuggera

Kompilatory GCC oraz Clang implementują następujący zestaw flag kompilacyjnych:

  • -O0: optymalizacja czasu kompilacji (domyślna wartość)
  • -O1 lub -O: optymalizacja wielkości kodu oraz czasu wykonywania (poziom 1)
  • -O2: optymalizacja wielkości kodu oraz czasu wykonywania (poziom 2)
  • -O3: optymalizacja wielkości kodu oraz czasu wykonywania (poziom 3)
  • -Os: optymalizacja wielkości kodu wynikowego
  • -Ofast: optymalizacja -O3 z dodatkowymi optymalizacjami obliczeniowymi
  • -Og: optymalizacja w celu lepszej pracy debuggera

Kompilator Clang dodatkowo implementuje dwie flagi:

  • -O4: alias dla flagi -O3
  • -Oz: optymalizacje -O2 z jeszcze lepszą optymalizacją wielkości kodu wynikowego

Wszystkie wyżej wymienione flagi są agregatami innych flag optymalizujących, o których więcej możecie przeczytać w dokumentacji: dla GCC tutaj, dla Clang tutaj i tutaj.

Gdybyście chcieli dowiedzieć się coś więcej na temat procesu optymalizacji, to zapraszam do dokumentacji GCC tutaj oraz Clang tutaj. Uprzedzam: mocne ;)


Kompilator MSVC wyróżnia się na tle GCC oraz Clang, implementując nieco inny zestaw flag:

  • /Od - brak optymalizacji w celu szybszej kompilacji i uproszczenia procesu debugowania
  • /O1 - optymalizacja wielkości kodu wynikowego
  • /O2 - optymalizacja będąca kompromisem wielkości kodu wynikowego oraz szybkości działania programu
  • /Ob - kontroluje optymalizacje funkcji inline
  • /Oi - optymalizacje wywołań funkcji
  • /Os - optymalizacja podobnie jak /O2, ale bardziej skupia się na wielkości kodu wynikowego
  • /Ot - domyślna optymalizacja. Przeciwieństwo /Os, czyli optymalizacja zarówno wielkości kodu wynikowego jak i szybkości działania programu
  • /Ox włącza zakres optymalizacji dla szybkości działania programu uruchamianych w /O2
  • /Oy pomija tworzenie fame-pointerów na stosie, w celu szybszego wywoływania funkcji

Przykładowe optymalizacje

Optymalizacji stosowanych przez kompilatory jest naprawdę wiele. Tak na prawdę, to każdy kompilator może optymalizować kod, używając własnych reguł i przełączników. Zaglądnijcie do linków, które podrzuciłem wyżej i przekonajcie się sami. Poniżej omówię kilka względnie “prostych” do zrozumienia optymalizacji kompilatora GCC.

Zbiorcze czyszczenie parametrów wywołań funkcji

Stos jest strukturą, która zmienia się z każdym uruchomieniem funkcji oraz z każdorazowym wejściem/wyjściem z aktualnego zakresu. Po zwróceniu wartości przez funkcję zachodzi potrzeba zdjęcia ze stosu jej parametrów. Domyślnie aktywowany przełącznik -fno-defer-pop czyści stos po każdorazowym wyjściu z wywołanej funkcji. Jeśli jednak użyjemy przełącznika -fdefer-pop, to kompilator zoptymalizuje kod tak, aby czyścić stos zbiorczo, np. po kilku wywołaniach funkcji. Dzięki takiemu zabiegowi możemy zyskać na czasie wykonania programu.

Wynoszenie kodu przed pętlę

Bardzo popularną optymalizacją, którą powinien stosować programista, jest wynoszenie przed pętlę kodu, który nie musi się w niej znajdować. Klasyczny przykład:

int value = findValue();
bool outed = false;
for (int i=0; i<1000000; i++) {
    if (value == 10 && !outed) {
        std::cout << "It's ten!";
        outed = true;
    }
    // other code...
}

Ten kod możemy śmiało zamienić na coś podobnego do:

int value = findValue();
if (value == 10) {
    std::cout << "It's ten!";
}

for (int i=0; i<1000000; i++) {
    // other code...
}

Tego typu optymalizacje (oczywiście na stanowczo bardziej zaawansowanym poziomie) przeprowadzi kompilator, kiedy w poleceniu kompilacji pojawi się flaga -funswitch-loops.

Sortowanie funkcji i bloków danych

Jak nam wszystkim wiadomo, kod wykonywany jest w sposób liniowy. Każdorazowe wywołanie funkcji nosi za sobą skok. Im dłuższy skok (skok pomiędzy odległymi od siebie miejscami w pamięci), tym dłużej on trwa. Domyśnie tworzone przez nas funkcje (i metody) znajdują się w pamięci w sposób niezoptymalizowany (mniej więcej w takiej kolejności, z jaką napotkał je kompilator). Jeżeli przekażemy w poleceniu kompilacyjnym flagę -freorder-functions, to kompilator spróbuje poukładać te funkcje tak, aby skoki pomiędzy nimi były możliwie jak najkrótsze.

Podobnie ma się sytuacja z blokami kodu. Kompilator może zoptymalizować nasz kod, aby po drodze było jak najmniej rozgałęzień (które de facto kończą się skokiem). Aby dać mu szansę na tą optymalizację, należy podać flagę -freorder-blocks.

Dodatkowa redukcja skoków

Redukować skoki możemy również przez spłaszczanie niektórych funkcji, czyli zastępowanie wywołań funkcji ich ciałami. Operacja ta nazywana jest function inlining. Możemy poprosić kompilator o spłaszczenie funkcji statycznych, jeżeli te są wywołane tylko w jednym miejscu (-finline-functions-called-once) albo dowolnych małych funkcji (-finline-small-functions). Limit wielkości tych drugich możemy określić przekazując flagę -finline-limit=n.

Kod nieosiągalny

Jedną z najpopularniejszych optymalizacji jest usuwanie z produkcji martwego kodu. Martwy kod to kod, do którego nie prowadzi ani jedna ścieżka wykonania. Aby kompilator mógł to zrobić, potrzebujemy najpierw powiedzieć mu, aby każdą funkcję przechowywał w osobnej sekcji programu (opcja -ffunction-sections). To samo możemy zrobić z blokami danych (opcja fdata-sections). Kiedy już to zrobimy, możemy poprosić linker o pozbycie się niewykorzystywanych sekcji. Robimy to przez przekazanie flag -Wl (przekaż flagę linkerowi) oraz --gc-sections (tę konkretną flagę).

Ostatecznie rozstrzygamy: i++ czy ++i?

Na samym początku kariery sporo początkujących osób razuje innych tzw. przedwczesną optymalizacją, twierdząc, że ++i w pętli for wykona się szybciej niż i++. Z jednej strony pewnie ktoś to zmierzył i OK, pewnie tak jest. Z drugiej jednak strony, wystarczy włączyć optymalizacje na poziomie chociażby O1, aby kompilator mógł sam zdecydować, czy nie lepiej post-inkrementację zamienić na pre-inkrementację, jeżeli ta okaże się szybsza, a warunki związane z niezmiennością zamiarów programisty na to pozwolą.

Moja rada jest taka: jeżeli planujecie optymalizować swój kod, to zaglądajcie w wygenerowany przez kompilator kod assemblera i upewnijcie się, czy faktycznie Wasza optymalizacja przyniesie zyski. Mówiąc o zyskach mam na myśli kompromis pomiędzy designem kodu a przyśpieszeniem działania aplikacji. Niektóre przedwczesne optymalizacje niewiele potrafią przyśpieszyć aplikację, szpecąc przy tym sporo nasz kod.

Optymalizacja a proces debugowania

Niestety, ale poszukiwanie błędów w kodzie zoptymalizowanym przez kompilator staje się nieco trudniejsze niż zwykle. Czasami różnice pomiędzy kodem nieskompilownym (znajdującym się w używanym przez nas IDE) a kodem skompilowanym przez kompilator są na tyle duże, że narzędzia debuggujące sobie z nimi nie radzą.


Przygotowałem bardzo prosty przykład, który obrazuje ten problem. Poniższy zrzut ekranu pochodzi z procesu debugowania kodu skompilowanego z flagą -O0 (brak optymalizacji):

Brak optymalizacji

Oczywiście, wszystko tutaj jest w porządku: możemy podglądnąć aktualną wartość obiektu klasy sf::Vector2f. Kiedy jednak skompilujemy ten kod z flagą -O3 (wysoka optymalizacja), to nasz debugger nie radzi sobie z poprawnym wyświetleniem zawartości tej zmiennej:

Optymalizacja O3

Ten (ciągle bardzo prosty) przykład pokazuje nam, ze dobrym zwyczajem jest niestosowanie optymalizacji kompilatora podczas procesu tworzenia kodu. Dobrze natomiast jest włączać flagi optymalizacyjne, jeżeli szukamy błędów, które wystąpiły na środowisku produkcyjnym.

Optymalizacja a Undefined Behavior

Jest jeszcze jeden drobiazg, o którym należy wspomnieć w temacie optymalizacji: optymalizowanie kodu na podstawie zachowań niezdefiniowanych (Undefined Behavior, UB). Zachowanie niezdefiniowane jest to sytuacja w kodzie, o której standard mówi, że jeżeli do niej dojdzie, to nie ma reguły na to, co może się wydarzyć. W ostateczności nie można zareagować na tą sytuację po jej wystąpieniu. Dodatkowo, kompilatory zakładają, że każdy kawałek kodu napisany przez programistę jest celowy, więc - na pewno nie będzie tam UB. Idąc dalej, skoro w kodzie programisty nie ma żadnych zachowań niezdefiniowanych, to kompilatory zostawiają sobie furtkę na lepszą optymalizację kodu.


Przeanalizujmy sobie poniższy kod:

#include <iostream>

int main(int argc, char* argv[]) {
     int i;
     std::cin >> i;
     if (i < 0) {
         i = -i;
     }

     if (i < 0) {
         return 1;
     }
     return 0;
}

W tym przykładzie może dojść do przepełnienia zmiennej typu całkowitego ze znakiem. Aby do tego doszło, należy wczytać do zmiennej i liczbę -2147483648. Zaraz po wczytaniu tej liczby wyłuskujemy jej wartość bezwzględną. Sęk w tym, że dla naszej wartości nie istnieje odpowiednik dodatni (typ int może pomieścić o jedną liczbę ujemną więcej, niż dodatnich). W tym miejscu następuje przepełnienie typu całkowitego, który dla typów ze znakiem jest traktowany przez standard jako zachowanie niezdefiniowane.

Idąc dalej, skoro jest to UB, to znaczy, że można ten kod zoptymalizować. Kompilator może założyć, że zmienna i w miejscu sprawdzaniu warunku if (i < 0) zawsze będzie przechowywała wartość dodatnią. W konsekwencji tego, ten warunek może zostać przez kompilator uznany jako nadmiarowy. Skoro nie jest on potrzebny, to finalnie może zostać on wyrzucony z kodu wynikowego.

Przygotowałem klikalny przykład, który pokazuje, w jaki sposób ten kod jest optymalizowany przez najnowszą wersję kompilatora Clang: https://godbolt.org/z/DXmVBs

Dla osób nie znających na tyle języka assembly: zwróćcie uwagę na to, że warunek if (i < 0) nie jest opatrzony żadnym kolorem. To znaczy, że kompilator zdecydował się wyrzucić go w procesie optymalizacji (-O3).

Generowanie kodu assemblera

Po procesie optymalizacji (przeprowadzonym przez warstwę middle-endu) następuje przekazanie kodu w postaci reprezentacji wewnętrznej do warstwy back-endu. W tym miejscu następuje generowanie kodu assemblera, którego składnia jest bardzo trywialna i zbliżona do instrukcji wykonywanych przez procesor. Kod wyjściowy back-endu jest generowany zgodnie z architekturą docelową, na którą kompilowany jest kod.

Gdzie kończy się C++?

Na sam koniec jako ciekawostkę odpowiem na pytanie: gdzie jest granica języka C++?


Jak wielu z Was pewnie się domyśla, rola języka C++ kończy się wraz z momentem zakończenia się procesu front-endu. Wszystko, co dzieje się dalej, jest już bardzo mało związane z naszym kochanym językiem. Bardzo dobrze to pokazuje architektura kompilatora llvm, który implementuje wiele różnych front-endów (np. Go, Haskell, Fortran, Rust). Jednym z takich front-endów jest właśnie Clang. Oznacza to również, że do stworzenia nowego (kompilowanego) języka programowania potrzebujemy jedynie wiedzy na temat podpięcia się pod kompilator llvm oraz znajomość składni jego interpretacji wewnętrznej.

Podsumowanie

Dowiedzieliśmy się dzisiaj, czym jest abstrakcyjny proces kompilacji oraz na jakie etapy się dzieli. Następnie omówiliśmy każdy z etapów kompilacji na podstawie dwóch kompilatorów: GCC oraz Clang. Wspomniałem również o różnicach pomiędzy obydwoma kompilatorami. W szerszy sposób podjęliśmy również proces optymalizacji, który potrafi nieco namieszać programistom. Podczas tematu optymalizacji poruszyliśmy również temat zachowań niezdefiniowanych oraz ich wpływ na efekt procesu kompilacji. Na sam koniec wyznaczyliśmy granicę, gdzie kończy się C++.



Marcin Kukliński

Zawodowo backend developer, hobbystycznie pasjonat języka C++. Po godzinach poszerza swoją wiedzę na takie tematy jak teorii kompilacji oraz budowa formatów plików. Jego marzeniem jest stworzyć swój własny język programowania.

Pssst! Używamy Cookies. Poprzez używanie naszego serwisu zgadzasz się na odczytywanie i zapisywanie Cookies w swojej przeglądarce.