Sunday, March 3, 2013

LLVM i Linux

Ostatnio dużo słychać o nowościach wprowadzanych w Linuksie, głownie w jądrze. Jednak jest pewna nowość, która wprowadzi fundamentalne zmiany w kodzie całego systemu, ale dla użytkowników będzie prawie niewidoczna - przynajmniej nie w swojej naturalnej postaci. Prędzej czy później na pewno zaowocuje to ulepszeniami i nowościami, w niektórych obszarach już tak się stało ale po kolei. W tym tekście postaram się przedstawić projekt LLVM i Clang, wyjaśnić czym są, jak działają i dlaczego są lepsze od GCC, czyli tego czego obecnie używa GNU/Linux.

W informatyce wszystko zaczęło się od programowania, systemy operacyjne, aplikacje, a nawet same języki programowania. Jak to mówią niektórzy, w programowaniu prędkością światła jest C - jakkolwiek by to nie zabrzmiało, to tak czy inaczej jest to prawdą E=mc2.

Systemy operacyjne i oprogramowanie wymagające szybkości działania pisze się w C lub C++. Z czasem, gdy komputery stawały się coraz szybsze zaczęto przedkładać prostotę i szybkość programowania nad wydajność. Nie przejmowano się tym ponieważ ciągły wzrost mocy obliczeniowej obecnych komputerów to rekompensował. Wtedy zaczęły powstawać nowe odmiany języków programowania w sensie procesu przetwarzania kodu źródłowego na maszynowy. Odchodzono od kodu kompilowanego na rzecz wirtualnych maszyn i interpreterów. Wirtualne maszyny Javy VM i .NET-tu odniosły ogromny sukces. W przypadku Javy największym zyskiem była przenośność napisanych programów, koncepcja kodu pośredniego w postaci wirtualnej maszyny sprawdziła się i udowodniła swoją słuszność.

Drugą bardzo popularną gałęzią i wcale nie nową były języki interpretowane: PHP, Python i cała masa innych. Język C i C++, zwłaszcza ten drugi nadal się rozwijał, ale koncepcja generowania kodu nie zmieniła się od lat. Zwolennicy wirtualnych maszyn chwalili sobie korzyści jakie niesie ich używanie, a użytkownicy języków skryptowych chwalili sobie szybkość i prostotę pisania w tych językach. Czy to znaczy, że racja musi leżeć po jednej stronie, nie! Wojna pomiędzy zwolennikami języków statycznych i dynamicznych zawsze trwała, a w tym czasie ktoś wpadł na genialny pomysł aby najlepszy język na świecie wyposażyć w rozwiązanie hybrydowe. Okazuje się, że lepszym wyborem jest połączenie dwóch metod niż wybieranie jednej z nich. Co ciekawe, koncepcja połączenia kompilacji statycznej z dynamiczną w C/C++ nie powstała wczoraj, ale w 2000 roku w projekcie LLVM.

LLVM


Logo projektu LLVM
Pełna nazwa projektu brzmi Low Level Virtual Machine, ale nie do końca oddaje ona czym obecnie jest projekt LLVM. Przede wszystkim utworzenie wirtualnej maszyny dla kodu generowanego przez C/C++ nie było jednym celem projektu. Chciano przy okazji wzbogacić kompilator o nowe możliwości, których brakowało do tej pory głównie dla GCC. LLVM to grupa kilku podprojektów tworzących kolekcję narzędzi ułatwiających i optymalizujących proces tworzenia kodu. Modularna budowa umożliwia wygodny rozwój i widocznie gwarantuje sukces. Zanim jednak podam przykłady obecnych osiągnięć LLVM chciałbym zwrócić uwagę na coś co jest sercem każdej maszyny wirtualnej - to jej "Bitcode".

Tradycyjny kompilator języka C/C++, taki jak GCC wykonuje trzy podstawowe etapy:

  • poddaje składni leksykalnej kod źródłowy
  • generuje odpowiadający instrukcjom języka kod maszynowy, dołącza niezbędny kod używanych bibliotek i optymalizuje wszystko razem
  • tworzy ostateczny format pliku wykonywalnego z kodem maszynowym

Zwróć uwagę, że od samego początku do końca kompilator posługuje się kodem maszynowym przeznaczonym dla konkretnej architektury. Ponad to wirtualna maszyna LLVM nie zajmuje się pierwszym etapem, tym zajmuje się inny projekt zwany Clang, o którym napiszę w dalszej części tekstu.

Architektura LLVM


W celu lepszej prezentacji architektury LLVM oraz zrozumienia jakie zadania realizują poszczególne podprojekty stworzyłem poniższy schemat. Prezentuje on przepływ kodu źródłowego, aż do kodu maszynowego i nie zawiera nawet większości podprojektów LLVM.

Architektura LLVM
LLVM posiada tak zwane front-endy, są to kompilatory. Ich zadaniem jest dostarczenie kodu dla wirtualnej maszyny w specyficznym formacje, nie mającym jednak nic wspólnego z kodem maszynowym przeznaczonym dla konkretnej architektury. Standardowo GCC nie potrafi generować bitcode dla LLVM, dlatego stworzono odmianę kompilatora zwaną llvm-gcc, obecnie jest to rozszerzenie dla samego GCC zwane DragonEgg. Jego zadanie polega na analizie kodu źródłowego zgodnie ze standardami GCC, ale generowany kod jest przeznaczony dla wirtualnej maszyny LLVM, a nie architektury procesora.
Drugim kompilatorem jest Clang, to własny projekt LLVM stworzony od podstaw na jego potrzemy. To właśnie on jest jednym z powodów sukcesu LLVM i chęci kompilacji Linuksa na LLVM.

"LLVM - 2.0 and beyond!"
Chris Lattner,
Google Tech Talk July 27, 2007

Clang


Clang jest kompilatorem języka C, C++ i Objective C, który jest kompatybilny z GCC. Oczywiście jego kompatybilność dotyczy głównie składni a nie rozszerzeń, te drugie są z kolei największym problemem w procesie kompilacji jądra Linux na Clang.

Największą zaletą Clang są jego rozbudowane i przyjazne dla człowieka komunikaty o błędach, oprócz lepszego wskazywania błędów podpowiada jak je rozwiązać. W praktyce oznacza to szybsze odnajdowanie błędów i ich naprawę, czyli szybszy rozwój systemu. Ważne jest to, że często Clang szybciej wykonuje kompilację, zużywa przy tym mniej zasobów, tworzy mniejszy i bardziej zoptymalizowany kod wykonywalny niż GCC.

"LLVM - 2.0 and beyond!"
Chris Lattner,
Google Tech Talk July 27, 2007
Jedną z egzotycznych możliwości Clang jest dynamiczna kompilacja JIT, tak jak ma to miejsce w przypadku np. Pythona - kompilowany kod jest od razu wykonywany na bieżąco.

Podobnie jak w LLVM budowa Clang jest modularna i Clang jest czymś więcej niż tylko kompilatorem - to kompilator z możliwością integrowania przydatnych narzędzi. Clang obsługuje wiele funkcji, które umożliwiają lepsza integrację ze środowiskami IDE. Przykładem takiego rozszerzenia jest source code refactoring (zobacz nagranie Clang MapReduce -- Automatic C++ Refactoring at Google Scale), który umożliwia zmianę nazw np. metod konkretnej klasy. Drugim przykładem może być Clang Static Analyzer, który pozwala na sprawdzenie błędów w kodzie bez kompilacji, niestety sama analiza nie jest szybsza niż sama kompilacja, ale z kompilacją byłaby o wiele dłuższa.

LLVM Optimizer


"LLVM - 2.0 and beyond!"
Chris Lattner,
Google Tech Talk July 27, 2007
Mechanizm optymalizacyjny maszyny LLVM działa na własnym formacie kodu, dzięki temu niezależnie czy kod pochodzi z C, C++ czy innego języka poddawany jest tym samym mechanizmom optymalizacji, a później jest przetłumaczany na kod maszynowy dla konkretnej architektury, czyli na tzw. back-end. To sprawia, że programiści do tej pory pracujący nad optymalizacją różnych kompilatorów teraz mogą wspólnie pracować nad jednym projektem i na dodatek na przejmować się specyfiką języka ani architektury.

Istotą bitcode jest niezależność od języka i architektury, dlatego musi on być w takiej formie, aby bez problemu można było przetłumaczyć każdą instrukcję z każdego języka na niego oraz aby każdy bitcode można było potem przetłumaczyć na dowolną architekturę. Tym pierwszym zajmują się front-end, a drugim back-end.

LLVM Intermediate Representation (IR)


IR to format języka wirtualnej maszyny LLVM (jego low-level bitcode), co ciekawe dostępny jest ona w tekstowej postaci czytelnej dla człowieka, co przyniosło dla LLVM największy sukces. Dzięki temu pisanie front-endów i back-endów jest bardzo proste w przeciwieństwie do GIMPLE z GCC.

Formą, która obsłuży każdy język i każdą architekturę okazały się krótkie instrukcje o stałej długości, jak w RISC. Opis tego kodu można zobaczyć na stronie projektu.
Z kolei na blogu LLVM został opublikowany opis dokładnie wyjaśniający cykl życia instrukcji w maszynie LLVM: Life of an instruction in LLVM.

Kto używa LLVM


Przede wszystkim Apple, LLVM jest podstawą XCode. Apple wykorzystując modularność LLVM (back-end) i możliwość kompilacji dynamicznej stworzyło OpenCL - framework, który pozwala na pisanie kodu niezależnego od środowiska sprzętowego. Jednym z przykładów jest możliwość wykonania graficznych operacji na sprzęcie nie wyposażonym w GPU.

Kolejnym dużym użytkownikiem jest Google, który używa Clang dla swoich własnych bibliotek i silnika wyszukiwań. Najbardziej jednak skorzystał na tym Android, jego Renderscript jest podstawą działania aplikacji graficznych na przeróżnych tabletach i telefonach. Zastanawiałeś się kiedyś czym jest format .apk używany przez aplikacje ściągane ze sklepu Google play? To bitcode LLVM, który został skompilowany na dowolnym urządzeniu. Podczas pierwszego uruchomienia zostanie on przetworzony przez back-end z bitcode LLVM na architekturę twojego urządzenia i po prostu działa.
Tak samo sprawa wygląda z aplikacjami w Chrome, spójrz na projekt Portable Native Client (PNaCl).

Warto wspomnieć o GNOME Shell, który emuluje efekty graficzne nawet na maszynach nie wspierających akceleracji 3D, a to dzięki LLVMpipe.

Nie trudno domyślić się że Apple i Google są firmami, które rozwijają LLVM ale są też inne głównie Qualcomm Innovation Center i Intel oraz wiele instytucji naukowych i edukacyjnych. LLVM używają ośrodki naukowe, takiej jak CERN i Argonne National Laboratory. LLVM/Clang używa nawet Adobe, więcej przykładów możesz znaleźć na stronie LLVM Users.

Kto przeszedł na LLVM


Czy wiesz, że Linus Torvalds zaczął pracę nad jądrem Linux, bo zafascynował się systemem MINIX? Teraz domyślnym kompilatorem w MINIX jest Clang.

Obecnie przechodzi na niego FreeBSD, wszystko zaczęło się od tego, że projekt nie mógł zaakceptować nowej licencji GPLv3 obowiązującej nowe wersie GCC. Szukając wyjścia z sytuacji postanowił wybrać LLVM, podobnie było z Apple.

Kto nie chciałby mieć pingwina ze skrzydłami smoka?


LLVMLinux

Dotarliśmy do sedna tego tekstu, wygląda na to, że po sukcesach jakie odniósł LLVM deweloperzy chcą umożliwić kompilację jądra i całego systemu na Clang. Jeżeli chodzi o jądro to tym zajmuje się projekt LLVMLinux (llvm.linuxfoundation.org), natomiast jeżeli mowa o pierwszej dystrybucji, która zostanie skompilowana w całości na Clang to najprawdopodobniej będzie to Debian. Obecnie tylko 12% pakietów nie udało się jeszcze skompilowanych przy pomocy Clang, stan tego procesu można śledzić przez stronię clang.debian.net. Wprowadzeniem Clang do Debiana zajmuje się Sylvestre Ledru, jak pisze, robi to po to, aby przekonać się czy system GNU/Linux może skorzystać na LLVM. Więcej o procesie kompilacji Debiana dowiesz się z prezentacji Make Debian compiler agnostic - Building Debian with LLVM/Clang na FOSDEM'13.

Parę dni temu odbyła się konferencja Embedded Linux Conference 2013, na której Behan Webster prezentował obecny stan prac w procesie przystosowywania jądra do kompilacji na Clang. Pierwsza część prezentacji odpowiada na pytanie dlaczego kompilować jądro na Clang, druga część dotyczy technicznych problemów z tym związanych.



Szybki rozwój


Podczas spotkania LLVM Developer Meeting 2012 zaprezentowano jak bardzo przyśpiesza rozwój tego projektu. Sądząc po liczbach, wspomnianych wyżej osiągnięciach i możliwościach nie sposób oprzeć się wrażeniu, że LLVM i Clang w najbliższej przyszłości mogą stać się standardem w projektach open source.

LLVM Developer Meeting 2012 San Jose, November 8, 2012
LLVM Developer Meeting 2012 San Jose, November 8, 2012
Co prawda nie brakuje również negatywnych ocen dla LLVM/Clang oraz wątpliwości związanych z licencją UIUC License (BSD-style). Wiele z tych kwestii jest poruszanych w artykule Distributions looking at LLVM na LWN.net.

Mimo wszystko uważam, że uczynienie systemu Linux kompatybilnym z LLVM/Clang jest jak najbardziej słuszne, zawsze zostaje jeszcze GCC. Wierzę, że w open source, tak jak w biologii różnorodność zwiększa szanse przetrwania gatunku. Możliwość kompilacji systemu Linux na dwóch różnych kompilatorach może mu tylko pomóc, a nie zaszkodzić.


Pozostałe zasoby:
RenderScript, edu4android.com
"Mac OS X 10.5 Leopard: the Ars Technica review", arstechnica.com
"LLVM", The Architecture of Open Source Applications