Tworzenie kompilatora jest bardzo trudnym zadaniem. Ale na szczęście wraz z rozwojem projektów takich jak LLVM rozwiązanie tego problemu zostało znacznie uproszczone, co pozwala nawet jednemu programiście stworzyć nowy język o wydajności zbliżonej do C. Pracę z LLVM komplikuje fakt, że to system reprezentowany jest przez ogromną ilość kodu, opatrzonego niewielką ilością dokumentacji. Aby spróbować naprawić to niedociągnięcie, autor materiału, którego tłumaczenie dzisiaj publikujemy, zademonstruje przykłady kodu napisanego w Go i pokaże, jak są one po raz pierwszy tłumaczone na język , a następnie w LLVM IR przy użyciu kompilatora . Kody Go SSA i LLVM IR zostały nieznacznie zmienione w celu usunięcia elementów niemających związku z podanymi tutaj wyjaśnieniami, aby wyjaśnienia były bardziej zrozumiałe.
Pierwszy przykład
Pierwszą funkcją, której się tutaj przyjrzę, jest prosty mechanizm dodawania liczb:
func myAdd(a, b int) int{
return a + b
}Ta funkcja jest bardzo prosta i być może nic nie może być prostsze. Tłumaczy się to następującym kodem Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0W tym widoku wskazówki dotyczące typów danych są umieszczone po prawej stronie i w większości przypadków można je zignorować.
Ten mały przykład pozwala już zobaczyć istotę jednego aspektu SSA. Mianowicie, podczas konwersji kodu do postaci SSA, każde wyrażenie jest rozkładane na najbardziej elementarne części, z których się składa. W naszym przypadku polecenie return a + bw rzeczywistości reprezentuje dwie operacje: dodanie dwóch liczb i zwrócenie wyniku.
Dodatkowo tutaj widać podstawowe bloki programu, w tym kodzie jest tylko jeden blok - blok wejściowy. Poniżej porozmawiamy więcej o blokach.
Kod Go SSA łatwo konwertuje do LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Można zauważyć, że chociaż zastosowano tu różne struktury składniowe, to struktura funkcji pozostaje w zasadzie niezmieniona. Kod LLVM IR jest trochę silniejszy od kodu Go SSA, podobnie jak C. Tutaj, w deklaracji funkcji, najpierw znajduje się opis typu danych, które zwraca, typ argumentu jest wskazany przed nazwą argumentu. Dodatkowo, aby uprościć analizę IR, nazwy jednostek globalnych poprzedzone są symbolem @, a przed nazwami lokalnymi znajduje się symbol % (funkcja jest również uważana za byt globalny).
Jedną rzeczą, na którą warto zwrócić uwagę w tym kodzie, jest decyzja dotycząca reprezentacji typu Go int, który może być reprezentowany jako wartość 32-bitowa lub 64-bitowa, w zależności od kompilatora i celu kompilacji, jest akceptowany, gdy LLVM generuje kod IR. Jest to jeden z wielu powodów, dla których kod LLVM IR nie jest, jak wiele osób sądzi, niezależny od platformy. Takiego kodu, stworzonego dla jednej platformy, nie można po prostu pobrać i skompilować na inną platformę (chyba że nadajesz się do rozwiązania tego problemu ).
Kolejną interesującą kwestią, na którą warto zwrócić uwagę, jest typ i64 nie jest liczbą całkowitą ze znakiem: jest neutralna pod względem reprezentowania znaku liczby. W zależności od instrukcji może reprezentować zarówno liczby ze znakiem, jak i bez znaku. W przypadku reprezentacji operacji dodawania nie ma to znaczenia, więc nie ma różnicy w pracy z liczbami ze znakiem i bez znaku. Tutaj chciałbym zauważyć, że w języku C przepełnienie zmiennej całkowitej ze znakiem prowadzi do niezdefiniowanego zachowania, więc nakładka Clang dodaje flagę do operacji nsw (bez podpisanego opakowania), co informuje LLVM, że może założyć, że dodawanie nigdy się nie przepełni.
Może to być ważne w przypadku niektórych optymalizacji. Na przykład dodanie dwóch wartości i16 na platformie 32-bitowej (z rejestrami 32-bitowymi) wymaga po dodaniu operacji rozszerzania znaku, aby pozostać w zakresie i16. Z tego powodu często bardziej efektywne jest wykonywanie operacji na liczbach całkowitych w oparciu o rozmiary rejestrów maszyny.
To, co stanie się dalej z tym kodem IR, nie jest teraz dla nas szczególnie interesujące. Kod jest optymalizowany (ale w przypadku tak prostego przykładu jak nasz nic nie jest optymalizowane), a następnie konwertowany na kod maszynowy.
Drugi przykład
Następny przykład, któremu się przyjrzymy, będzie nieco bardziej skomplikowany. Mianowicie mówimy o funkcji sumującej wycinek liczb całkowitych:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Ten kod jest konwertowany na następujący kod Go SSA:
func sum(numbers []int) int:
entry:
jump for.loop
for.loop:
t0 = phi [entry: 0:int, for.body: t6] #n int
t1 = phi [entry: 0:int, for.body: t7] #i int
t2 = len(numbers) int
t3 = t1 < t2 bool
if t3 goto for.body else for.done
for.body:
t4 = &numbers[t1] *int
t5 = *t4 int
t6 = t0 + t5 int
t7 = t1 + 1:int int
jump for.loop
for.done:
return t0Tutaj można już zobaczyć więcej konstrukcji typowych dla reprezentacji kodu w formie SSA. Być może najbardziej oczywistą cechą tego kodu jest fakt, że nie ma w nim żadnych uporządkowanych poleceń sterujących przepływem. Aby kontrolować przebieg obliczeń, istnieją tylko skoki warunkowe i bezwarunkowe oraz, jeśli uznamy to polecenie za polecenie sterujące przepływem, polecenie powrotu.
Tak naprawdę tutaj można zwrócić uwagę na to, że program nie jest podzielony na bloki za pomocą nawiasów klamrowych (jak w rodzinie języków C). Jest on podzielony etykietami, przypominającymi języki asemblera i przedstawiony w formie podstawowych bloków. W SSA podstawowe bloki definiuje się jako ciągłe sekwencje kodu rozpoczynające się od etykiety i kończące się podstawowymi instrukcjami uzupełniania bloku, takimi jak - return и jump.
Inny interesujący szczegół tego kodu jest reprezentowany przez instrukcję phi. Instrukcje są dość nietypowe i ich zrozumienie może zająć trochę czasu. Zapamietaj to jest skrótem od Static Single Assignment. Jest to pośrednia reprezentacja kodu używanego przez kompilatory, w której każdej zmiennej przypisuje się wartość tylko raz. Świetnie nadaje się do wyrażania prostych funkcji, takich jak nasza funkcja myAddpokazanej powyżej, ale nie nadaje się do bardziej złożonych funkcji, takich jak funkcja omówiona w tej sekcji sum. W szczególności zmienne zmieniają się podczas wykonywania pętli i и n.
SSA omija ograniczenie przypisywania wartości zmiennych jednorazowo za pomocą tzw. instrukcji phi (jego nazwa pochodzi z alfabetu greckiego). Faktem jest, że aby wygenerować reprezentację kodu SSA dla języków takich jak C, trzeba zastosować pewne sztuczki. Wynikiem wywołania tej instrukcji jest bieżąca wartość zmiennej (i lub n), a jako jego parametry używana jest lista podstawowych bloków. Rozważmy na przykład tę instrukcję:
t0 = phi [entry: 0:int, for.body: t6] #n
Jego znaczenie jest następujące: jeśli poprzedni blok podstawowy był blokiem entry (wejście), następnie t0 jest stałą 0, a jeśli poprzedni blok podstawowy był for.body, to musisz przyjąć wartość t6 z tego bloku. Wszystko to może wydawać się dość tajemnicze, ale to właśnie ten mechanizm sprawia, że SSA działa. Z ludzkiego punktu widzenia wszystko to sprawia, że kod jest trudny do zrozumienia, ale fakt, że każda wartość jest przypisana tylko raz, znacznie ułatwia wiele optymalizacji.
Zauważ, że jeśli napiszesz własny kompilator, zazwyczaj nie będziesz musiał zajmować się tego typu rzeczami. Nawet Clang nie generuje wszystkich tych instrukcji phi, wykorzystuje mechanizm alloca (przypomina to pracę ze zwykłymi zmiennymi lokalnymi). Następnie, podczas uruchamiania przepustki optymalizacyjnej LLVM o nazwie , instrukcje alloca przekonwertowany do formatu SSA. Jednakże TinyGo otrzymuje dane wejściowe z Go SSA, które dla wygody są już konwertowane do formatu SSA.
Kolejną innowacją rozważanego fragmentu kodu pośredniego jest to, że dostęp do elementów plasterka według indeksu jest reprezentowany w postaci operacji obliczenia adresu i operacji wyłuskania powstałego wskaźnika. Tutaj możesz zobaczyć bezpośrednie dodanie stałych do kodu IR (na przykład - 1:int). W przykładzie z funkcją myAdd to nie zostało wykorzystane. Teraz, gdy mamy już te funkcje za sobą, przyjrzyjmy się, czym staje się ten kod po konwersji do postaci LLVM IR:
define i64 @sum(i64* %ptr, i64 %len, i64 %cap) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, %deref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, %deref.next ]
%2 = icmp slt i64 %1, %len
br i1 %2, label %for.body, label %for.done
for.body: ; preds = %for.loop
%3 = getelementptr i64, i64* %ptr, i64 %1
%4 = load i64, i64* %3
%5 = add i64 %0, %4
%6 = add i64 %1, 1
br label %for.loop
for.done: ; preds = %for.loop
ret i64 %0
}
Tutaj, podobnie jak poprzednio, widzimy tę samą strukturę, która zawiera inne struktury syntaktyczne. Na przykład w rozmowach phi zamienione wartości i etykiety. Jest tu jednak coś, na co warto zwrócić szczególną uwagę.
Na początek tutaj widać zupełnie inną sygnaturę funkcji. LLVM nie obsługuje plasterków, w wyniku czego w ramach optymalizacji kompilator TinyGo, który wygenerował ten kod pośredni, podzielił opis tej struktury danych na części. Może reprezentować trzy elementy plasterka (ptr, len и cap) jako strukturę (struct), ale przedstawienie ich jako trzech oddzielnych bytów pozwala na pewne optymalizacje. Inne kompilatory mogą reprezentować wycinek na inne sposoby, w zależności od konwencji wywoływania funkcji platformy docelowej.
Kolejną interesującą cechą tego kodu jest użycie instrukcji getelementptr (często w skrócie GEP).
Ta instrukcja działa ze wskaźnikami i służy do uzyskania wskaźnika do elementu plasterka. Dla przykładu porównajmy to z następującym kodem napisanym w C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Lub z następującym odpowiednikiem tego:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Najważniejszą rzeczą jest tutaj instrukcja getelementptr nie wykonuje operacji dereferencji. Po prostu oblicza nowy wskaźnik na podstawie istniejącego. Można to potraktować jako instrukcję mul и add na poziomie sprzętowym. Możesz przeczytać więcej o instrukcjach GEP .
Kolejną interesującą cechą tego kodu pośredniego jest użycie instrukcji icmp. Jest to instrukcja ogólnego przeznaczenia używana do implementowania porównań liczb całkowitych. Wynikiem tej instrukcji jest zawsze wartość typu i1 — wartość logiczna. W tym przypadku porównania dokonuje się za pomocą słowa kluczowego slt (ze znakiem mniej niż), ponieważ porównujemy dwie liczby poprzednio reprezentowane przez typ int. Gdybyśmy porównywali dwie liczby całkowite bez znaku, użylibyśmy icmp, a słowem kluczowym użytym w porównaniu byłoby ult. Do porównania liczb zmiennoprzecinkowych używana jest inna instrukcja, fcmp, który działa w podobny sposób.
Wyniki
Uważam, że w tym materiale opisałem najważniejsze cechy LLVM IR. Oczywiście jest tu dużo więcej. W szczególności pośrednia reprezentacja kodu może zawierać wiele adnotacji, które umożliwiają przebiegom optymalizacji uwzględnienie pewnych cech kodu znanych kompilatorowi, których inaczej nie można wyrazić w podczerwieni. Na przykład jest to flaga inbounds Instrukcje GEP lub flagi nsw и nuw, które można dodać do instrukcji add. To samo dotyczy słowa kluczowego private, wskazując optymalizatorowi, że zaznaczona przez niego funkcja nie będzie się odwoływać spoza bieżącej jednostki kompilacji. Pozwala to na wiele ciekawych optymalizacji międzyproceduralnych, takich jak eliminacja nieużywanych argumentów.
Więcej o LLVM możesz przeczytać w , do którego będziesz często odwoływać się podczas tworzenia własnego kompilatora opartego na LLVM. Tutaj , który dotyczy opracowania kompilatora dla bardzo prostego języka. Obydwa te źródła informacji przydadzą Ci się podczas tworzenia własnego kompilatora.
Drodzy Czytelnicy! Czy korzystasz z LLVM?
Źródło: www.habr.com