Stworzenie kompilatora to bardzo trudne zadanie. Na szczęście, dzięki rozwojowi projektów takich jak LLVM, rozwiązanie tego problemu stało się znacznie prostsze, co pozwala nawet pojedynczym programistom stworzyć nowy język, który będzie porównywalny pod względem wydajności z C. Praca z LLVM jest utrudniona przez to, że system ten posiada ogromną ilość kodu, z niewielką dokumentacją. Aby spróbować naprawić ten brak, autor materiału, którego tłumaczenie publikujemy dzisiaj, planuje zademonstrować przykłady kodu napisanego w Go oraz pokazać, jak są one transliterowane najpierw w , a następnie — w LLVM IR przy użyciu kompilatora . Kod Go SSA i LLVM IR został nieco edytowany, aby usunąć części, które nie odnoszą się do przedstawianych tutaj wyjaśnień, aby te wyjaśnienia były bardziej zrozumiałe.
Pierwszy przykład
Pierwsza funkcja, którą zamierzam tutaj omówić, przedstawia prosty mechanizm do dodawania liczb:
func myAdd(a, b int) int{
return a + b
}Ta funkcja jest bardzo prosta, a być może nie ma prostszej. Translituje się do następującego kodu Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0W takim przedstawieniu funkcji wskazówki dotyczące typów danych umieszczone są po prawej stronie, w większości przypadków można je zignorować.
Ten mały przykład już pozwala dostrzec istotę jednego z aspektów SSA. Mianowicie, w procesie konwersji kodu do formy SSA każde wyrażenie jest dzielone na najprostsze części, z których się składa. W naszym przypadku instrukcja return a + b, tak naprawdę, składa się z dwóch operacji: dodawania dwóch liczb i zwracania wyniku.
Ponadto widać tutaj podstawowe bloki programu, w tym kodzie jest tylko jeden blok — blok wejściowy (entry block). Szczegóły dotyczące bloków omówimy poniżej.
Kod Go SSA łatwo przekształca się w LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
} Można zauważyć, że chociaż stosowane są tu inne konstrukcje składniowe, struktura funkcji zasadniczo się nie zmieniła. Kod LLVM IR jest nieco bardziej rozbudowany niż kod Go SSA i przypomina C. Tutaj, w deklaracji funkcji, na początku znajduje się opis typu danych, który zwraca, a typ argumentu jest podawany przed nazwą argumentu. Ponadto, dla uproszczenia analizy IR, przed nazwami globalnych encji stoi symbol @, a przed nazwami lokalnych — symbol % (funkcja również jest uważana za globalną encję).
Jedną z cech tego kodu, na którą warto zwrócić uwagę, jest to, że decyzja o 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 podejmowana podczas tworzenia kodu LLVM IR. To jeden z wielu powodów, dla których kod LLVM IR nie jest, jak wielu się wydaje, platformowo niezależny. Taki kod stworzony dla jednej platformy nie może być po prostu wzięty i skompilowany dla innej platformy (chyba że podejdzie się do rozwiązania tego zadania ).
Jeszcze jeden interesujący aspekt, który warto zauważyć, to to, że typ i64 nie jest liczbą całkowitą ze znakiem: jest neutralny w kwestii reprezentacji znaku liczby. W zależności od instrukcji może reprezentować zarówno liczby ze znakiem, jak i liczby bez znaku. W przypadku reprezentacji operacji dodawania nie ma to znaczenia, dlatego tutaj nie ma różnicy w pracy z liczbami ze znakiem lub bez znaku. Warto zauważyć, że w języku C przekroczenie wartości zmiennej całkowitej ze znakiem prowadzi do nieokreślonego zachowania, dlatego frontend Clang dodaje do operacji flagę nsw (no signed wrap), co wskazuje LLVM, że może przyjąć założenie, iż podczas dodawania nigdy nie występuje przekroczenie wartości.
Może mieć to znaczenie dla niektórych optymalizacji. Na przykład dodanie dwóch wartości i16 na platformie 32-bitowej (z 32-bitowymi rejestrami) wymaga po wykonaniu dodawania operacji rozszerzenia znaku, aby pozostać w zakresie i16. Z tego powodu często bardziej efektywne jest wykonywanie operacji całkowitych z uwzględnieniem rozmiarów rejestru.
To, co dzieje się dalej z tym kodem IR, obecnie nas szczególnie nie interesuje. Kod jest optymalizowany (ale w przypadku tak prostego przykładu jak nasz, nic już nie jest optymalizowane), a następnie przekształcany w kod maszynowy.
Drugi przykład
Następny przykład, który omówimy, będzie nieco bardziej skomplikowany. Mianowicie, mowa będzie o funkcji, która sumuje slice liczb całkowitych:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Ten kod przekształca się w 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 widać już więcej konstrukcji charakterystycznych dla reprezentacji kodu w formie SSA. Prawdopodobnie najbardziej oczywistą cechą tego kodu jest to, że nie ma tutaj strukturalnych poleceń kontrolujących przepływ obliczeń. Kontrolowanie przepływu obliczeń odbywa się jedynie za pomocą skoków warunkowych i bezwarunkowych, a jeśli uznać tę komendę za polecenie do kontroli przepływu, polecenie zwrotu.
W rzeczywistości warto zwrócić uwagę na to, że program nie jest podzielony na bloki za pomocą nawiasów klamrowych (jak w językach rodziny C). Jest podzielony etykietami, co przypomina języki asemblerowe, i przedstawiony w postaci podstawowych bloków. W SSA podstawowymi blokami nazywa się nieprzerwane sekwencje kodu, które zaczynają się od etykiety i kończą instrukcjami zakończenia podstawowego bloku, np. — return i jump.
Jeszcze jeden interesujący szczegół tego kodu to instrukcja phi. Instrukcja ta jest dość nietypowa, zrozumienie jej może potrwać chwilę. Pamiętaj, że — to skrót od Static Single Assignment. Jest to pośrednia reprezentacja kodu używanego przez kompilatory, w której każdej zmiennej przypisywana jest wartość tylko raz. Doskonale nadaje się do wyrażania prostych funkcji, jak nasza funkcja myAdd, pokazanej powyżej, ale nie nadaje się do bardziej złożonych funkcji — tak jak omawiana w tej sekcji funkcja suma. W szczególności w trakcie wykonywania pętli zmieniają się zmienne i i n.
SSA omija ograniczenie na jednokrotne przypisanie wartości zmiennych, korzystając z tzw. instrukcji phi (jej nazwa pochodzi z alfabetu greckiego). Chodzi o to, że aby można było utworzyć reprezentację SSA kodu dla języków takich jak C, trzeba stosować pewne sztuczki. Wynikiem wywołania tej instrukcji jest bieżąca wartość zmiennej (i lub n), a jako jej argumenty wykorzystuje się listę bloków podstawowych. Na przykład rozważmy taką instrukcję:
t0 = phi [entry: 0:int, for.body: t6] #n Jej sens polega na tym, że jeśli poprzednim blokiem podstawowym był blok entry (wejściowy), to t0 to stała 0, a jeśli poprzednim blokiem podstawowym był for.body, to należy wziąć wartość t6 z tego bloku. Wszystko to może wyglądać dość tajemniczo, ale dzięki temu mechanizmowi zapewniona jest funkcjonalność SSA. Z ludzkiego punktu widzenia wszystko to utrudnia zrozumienie kodu, ale fakt, że każda wartość przypisywana jest tylko raz, znacznie upraszcza wiele optymalizacji.
Zauważ, że jeśli piszesz własny kompilator, zwykle nie musisz zajmować się takimi rzeczami. Nawet Clang nie generuje wszystkich tych instrukcji phi, korzysta z mechanizmu alloca (przypomina to pracę z zwykłymi zmiennymi lokalnymi). Następnie, podczas przechodzenia optymalizacji LLVM, nazywanej , instrukcje alloca są przekształcane do formy SSA. TinyGo jednak otrzymuje dane wejściowe od Go SSA, które, co wygodne, zostały już przekształcone do formy SSA.
Kolejną nowością omawianego fragmentu pośredniego kodu jest to, że dostęp do elementów slice'a po indeksie przedstawiony jest w postaci operacji obliczania adresu i operacji dereferencji uzyskanego wskaźnika. Można tu zobaczyć też bezpośrednie dodawanie stałych do kodu IR (na przykład — 1:int). W przypadku funkcji myAdd To nie było używane. Teraz, gdy zrozumieliśmy te szczegóły, spójrzmy, jak ten kod przekształci się w postać LLVM IR:
define i64 @sum(i64* %ptr, i64 %len, i64 p) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, ref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, ref.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, jak wcześniej, możemy zobaczyć taką samą strukturę, zawierającą inne konstrukcje składniowe. Na przykład w wywołaniach phi miejsca i etykiety zostały zamienione. Jednak jest coś, na co warto zwrócić szczególną uwagę.
Na początek, możemy zobaczyć zupełnie inną sygnaturę funkcji. LLVM nie obsługuje slice'ów, w rezultacie, w ramach optymalizacji, kompilator TinyGo, który wygenerował ten kod pośredni, podzielił opis tej struktury danych na części. Mógłby on przedstawić trzy elementy slice'a (ptr, len i cap) w postaci struktury (struct), jednak przedstawienie ich jako trzy oddzielne encje pozwala na przeprowadzenie pewnych optymalizacji. Inne kompilatory mogą przedstawiać slice w inny sposób, to zależy od konwencji wywołania funkcji danej platformy.
Jeszcze jedną interesującą cechą tego kodu jest wykorzystanie instrukcji getelementptr (często w skrócie nazywaną GEP).
Ta instrukcja działa z wskaźnikami i jest używana do uzyskania wskaźnika na element slice'a. Na przykład, porównajmy ją z następującym kodem napisanym w C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Lub z następującym, równoważnym temu:
int* sliceptr(int *ptr, int index) {
return ptr + index;
} Najważniejsze jest to, że instrukcja getelementptr nie wykonuje operacji dereferencji. Oblicza tylko nowy wskaźnik w oparciu o istniejący. Można ją traktować jako instrukcje mul i add na poziomie sprzętowym. Szczegóły dotyczące instrukcji GEP można przeczytać. .
Jeszcze jedna interesująca cecha tego kodu pośredniego polega na zastosowaniu instrukcji icmp. To jest uniwersalna instrukcja wykorzystywana do porównywania liczb całkowitych. Wynikiem wykonania tej instrukcji zawsze jest wartość typu i1 — wartość logiczna. W tym przypadku porównanie odbywa się z użyciem słowa kluczowego slt (signed less than), ponieważ porównujemy dwie liczby, które wcześniej były przedstawione jako int. Gdybyśmy porównywali dwie liczby całkowite bez znaku, wówczas jako instrukcję użyjemy icmp, a słowem kluczowym używanym w porównaniu byłoby ult. Do porównania liczb zmiennoprzecinkowych stosuje się inną instrukcję, fcmp, działającą w podobny sposób.
Podsumowanie
Uważam, że poruszyłem w tym materiale najważniejsze cechy LLVM IR. Oczywiście, jest tu jeszcze wiele innych rzeczy. W szczególności w pośrednim przedstawieniu kodu mogą występować liczne adnotacje, które uwzględniają w procesie optymalizacji określone cechy kodu znane kompilatorowi, które nie mogą być wyrażone w inny sposób w IR. Na przykład, jest to flaga inbounds instrukcji GEP, lub flagi nsw i nuw, które mogą być dodane do instrukcji add. To samo dotyczy słowa kluczowego private, wskazującego optymalizatorowi, że oznaczona funkcja nie będzie referencjonowana z zewnątrz bieżącej jednostki kompilacji. Umożliwia to przeprowadzanie wielu interesujących optymalizacji międzyproceduralnych, takich jak eliminacja nieużywanych argumentów.
Szczegóły dotyczące LLVM można znaleźć w , do której będziesz często sięgać, rozwijając własny kompilator oparty na LLVM. Oto , w którym omawiana jest budowa kompilatora dla bardzo prostego języka. Oba te źródła informacji będą przydatne w tworzeniu własnego kompilatora.
Drodzy Czytelnicy! Czy korzystasz z LLVM?
Źródło: habr.com
