Interesujące projekty kompilatorów

Question

Jestem obecnie w trakcie wyboru projektu na kurs kompilatora na poziomie gradu, który ma zostać ukończony w ciągu najbliższych 8 tygodni. Chciałbym zrobić coś związanego z optymalizacją, ponieważ nie pracowałem zbyt wiele w tej dziedzinie, ale wszystko w tej dziedzinie jest uczciwą grą.

Jaki był najciekawszy projekt związany z kompilatorem, który zrobiłeś? Czego nauczyłeś się najbardziej?

---

Edit: Dziękuję wszystkim za wielkie sugestie. Przepraszam, że nie aktualizowałem tego tak długo.

Projekt, który wykonałem, to prosta optymalizacja autovectorization na LLVM. LLVM ma typy wektorowe, ale wydaje się, że nie ma sposobu na ich wykorzystanie bez wsparcia dla front-endu. Ta optymalizacja przekształciła normalny kod skalarny w kod wektorowy.

Ponieważ auto-wektoryzacja jest dość trudną optymalizacją do wdrożenia, ograniczyliśmy nasz zakres tak bardzo, jak tylko mogliśmy. Po pierwsze, w celu pokazania paralelizmu poziomu instrukcji w kodzie, szukaliśmy pętli jednoblokowych, które pasowały do ​​naszych kryteriów, a następnie rozwijano je określoną liczbę razy, aby były wygodnie wektoryzowane. Następnie wdrożyliśmy algorytm pakowania określony w Exploiting Superword Level Parallelism with Multimedia Instruction Sets autorstwa Larsena i Amarasinga.

Nawet uproszczona wersja tej optymalizacji jest dość skomplikowana. Istnieje wiele ograniczeń; na przykład nie chcesz wektoryzować zmiennej, która żyje poza pętlą, ponieważ reszta programu oczekuje, że będzie skalarna. W ciągu ostatnich kilku tygodni poświęciliśmy wiele godzin. Projekt był jednak zabawny i wiele się nauczyliśmy.

Answer 1

Jeśli interesuje Cię optymalizacja, wektoryzacja pętli przy użyciu zestawów instrukcji SSE i MMX może być interesująca.

Answer 2

Wydaje mi się, że napisanie własnego prostego języka skryptów osadzonych było jednym z najciekawszych projektów związanych z kompilacją, które zrobiłem. Nauczyło mnie to każdego aspektu procesu od projektu do koncepcji, a ponieważ robiłem to od podstaw, mogłem uczynić go tak prostym lub złożonym jak potrzebowałem, co pozwoliło mi zrozumieć koncepcje bez hałasu, modyfikując ustalone projekt mógł mieć.

Answer 3

Kiedyś napisałem język programowania i maszynę wirtualną, aby go uruchomić. Język był w stanie interfejsować się do funkcji napisanych specjalnie dla tego, które były zawarte w bibliotece DLL (to było przed automatyzacją OLE) w 16-bitowym systemie Windows.

Wykonanie całej czynności front-to-back pozwoliło mi doskonale zrozumieć język z obu stron. Czytałam różne książki do kompilacji w tym czasie (takie jak niesławna książka o Smoczku), ale nigdy tak naprawdę nie zapadła, dopóki nie napisałem czegoś konkretnego. Teraz, po wielu latach, praca, którą wykonałem, dała mi znacznie więcej zrozumienia i zrozumienia, takich rzeczy jak Java VM i praca CLR.

Answer 4

Uczenie się kompilatorów sprawia, że ​​najlepiej jest wykonywać od zera do końca. Używając prostego mechanizmu backendowego, a nie x86, wybierz raczej prostą maszynę, taką jak MIPS. Zrobiłem mój projekt kompilatora undergrad na symulator PDP-11, który był świetnym celem, ponieważ utrzymywał rzeczy bardzo proste. Dzięki przykładowemu kodowi mogliśmy wykonać prosty imperatywny kompilator języka w ciągu około czterech tygodni. W C!

Dziś, używając potężnych języków, takich jak ML, kompilator powinien być znacznie łatwiejszy.

To, co robisz, powinno naprawdę zależeć od tego, w czym interesujesz. Jeśli chodzi o optymalizację, znajdź prosty szkielet, w którym to wszystko jest potrzebne.

Myślę, że obecnie najbardziej owocnym obszarem było kompilowanie dla celów gwintowanych lub kompilacji typu "dokładnie na czas".

Answer 5

Wykrywanie pętli i sparametryzowane rozwijanie powinny być wystarczająco trudne, aby było interesujące. Niezbyt seksowne, ale zbyt seksowne w ciągu 8 tygodni cię zatopią.

Answer 6

W mojej klasie kompilatorów dla undergrad, najpierw napisaliśmy parser rekursywny (zstępujący) dla języka podobnego do Pascala od zera: Lexical Analyzer, parser, wszystko.

Około połowy semestru przekierowaliśmy do generatorów analizatorów składni/skanerów, takich jak lex/yacc lub flex/bison. Zbudowaliśmy kompilator, który zabrałby nasz podzbiór Pascal i skompilował go do złożenia dla maszyny stosu, którą dostaliśmy (maszyna na stosie jest prosta, ale zasady są takie same).

Jeśli interesują Cię kompilatory, nie mogę polecić wystarczająco dobrze Dragon Book. Jest przeznaczony do wykorzystania na 1 semestr undergrad course, a druga połowa jako kurs na poziomie magisterskim, i obejmuje każdy element teorii i optymalizacji, jakiego można sobie życzyć. Nawet Joel likes it. =)

Cheers

Answer 7

Rozważmy typ wnioskowania dla istniejącej dynamicznie wpisany języku.

Answer 8

W ośmiotygodniowym okresie będziesz musiał uważać na "zakres pełzania". To nie jest zbyt ambitne, szczególnie. jeśli ten projekt obejmuje inne aspekty kompilacji konstrukcji (leksykowanie/parsowanie) lub jeśli nadal uczysz się narzędzi (debugger, yacc) i pośrednich struktur danych (DAG).

Powiedziawszy to, moją pierwszą sugestią byłoby wypróbowanie jakiejś Live Variable Analysis. Algorytmy są dość dobrze ustalone, więc wystarczy po prostu zakodować je w swoich strukturach danych, itp.

Pozwoli to na wykonanie ograniczonej formy usuwania martwych kodów. Oznacza to, że jeśli wykryje się, że zmienna jest zadeklarowana, ale nigdy nie jest używana, nie przydzielaj jej miejsca. Jeśli wykryjesz, że wartość jest ustawiona, ale nigdy nie jest czytana, nie generuj zestawu.

Analiza zmiennej na żywo może również pomóc w rejestracji, więc możesz sobie z tym poradzić, jeśli masz czas, i powinieneś być w stanie ponownie wykorzystać niektóre z twoich kompilacji do usuwania Dead Code.

Answer 9

Można napisać optymalizator dla IronScheme, ponieważ obecnie działa on bardzo dobrze, z wyjątkiem kilku "wewnętrznych" funkcji. :)

Answer 10

Kilka lat temu zaprojektowałem DSL i napisałem kompilator do produktu, który wyprodukowała moja firma. DSL używał nieparzystej kombinacji deklaratywnych reguł, logiki sterowanej zdarzeniami i dziedziczenia kompozycyjnego. To był bardzo zabawny projekt i wiele się nauczyłem.

Naprawdę wzbudziło to moje zainteresowanie w kompilatorach składających się na parowniki: &, więc starałem się nadążać za interesującymi nowościami w dziedzinie technologii kompilacji.

W odniesieniu do optymalizacji, oto artykuł zabawy, które czytałem w zeszłym roku:

http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf

W niniejszym artykule autorzy opisują technikę automatycznego wykrywania optymalizacje wizjer (przekraczając wydajności kilku popularnych Kompilatory C++) bez pomocy eksperta, który musi napisać kilka specjalnych kodów. Ich technika wykorzystuje nienadzorowane algorytmy uczenia się, aby odkryć zastępcze wysokiej jakości wizjery.

Po zapoznaniu się z nim, przyszło mi do głowy, że ich podejście można zwiększyć, dostarczając algorytmowi "opis maszyny" zawierający listę wszystkich instrukcji (wraz z ich efektami podstawowymi i ich efektami ubocznymi) obsługiwanych przez docelową architekturę procesora . Następnie, zamiast używać metody brute-force do znalezienia równoważnych sekwencji instrukcji, solver może znaleźć te sekwencje o wiele łatwiej.

Algorytm uczenia maszynowego nadal wykorzystywałby obserwacje empiryczne do określenia najbardziej wydajnej sekwencji instrukcji (ponieważ efekty pamięci podręcznej, mikrooperacje i potokowanie wymagają niemal empirycznych danych czasowych), ale równoważność wyniku można przewidzieć za pomocą algebraicznego dowódca twierdzeń, działający na opisie maszyny.

W artykule omawiają, w jaki sposób ich optymalizatorzy mogli odkryć sekwencje zastępujące peephole w dwóch lub trzech instrukcjach (ponieważ w przeciwnym razie przeszukanie brute-force mogłoby zająć zbyt dużo czasu i zająć zbyt dużo pamięci). Umieszczenie inteligentnego rozwiązania w odpowiednim miejscu w algorytmie może umożliwić pracę z dłuższymi sekwencjami zastępowania.

Anyhoo ... daj mi znać, gdy skończysz z tym projektem! I nie zapomnij wspomnieć o mnie w sekcji "Podziękowania"! ;-)

Answer 11

Inne interesujące projekty mogą obejmować:

• Dodaj optymalizacji ogon rozmowę z open-source Sun JVM.

• Dodaj nazwaną optymalizację wartości zwracanej (NRVO) do maszyn wirtualnych Python lub Ruby.

• dodawania just-in-time regex do kodu bajtowego kompilacja, na swoim ulubionym celem (Net ma go już. Jestem całkiem pewny, że Java nie.)

Answer 12

Podczas pisania własny język jest zabawną i tradycyjną działalnością akademicką, istnieje już zbyt wiele słabo wdrożonych projektów związanych z kompilacją. Również 8 tygodni to za mało czasu, aby wykonać dobrą pracę przy pełnej implementacji językowej.

Jeśli interesuje Cię "coś związanego z optymalizacją", wybierz już istniejący język lub maszynę wirtualną i zoptymalizuj ją pod kątem wydajności, rozmiaru lub obu. Zapobiegnie to konieczności wymyślania całej wersji językowej, pozwala skupić się na problemie optymalizacji, stworzy produkt przydatny dla innych ludzi, a nie tylko inne ćwiczenie akademickie, a może nawet być przydatny w zdobyciu pracy.

Wierzę, że interpreter kodu bajtowego Parrot i różne parsery w .Net Iron-Language mogą skorzystać nawet z prostych optymalizacji.

Answer 13

Oprócz sugestii "Smoczej księgi", bardzo polecam "Zaawansowany projekt kompilatora & Wdrażanie", autor: Steven S.Muchnick, który koncentruje się na reprezentacjach pośrednich, generowaniu kodu i technikach optymalizacji.

Answer 14

Zajrzyj do pomocy w projekcie Shed Skin, który kompiluje Python do C++. Myślę, że latem, wezwano do pomocy. Ustalenie sposobów ulepszenia kompilacji do C++ zapewniłoby fenomenalną optymalizację dla programów pythonowych!

http://code.google.com/p/shedskin/

Answer 15

Oto kolejny pomysł ... choć to jeszcze trochę duży niejasne:

Większość optymalizacja odbywa się w czasie kompilacji (oprócz kompilatorów JIT, które optymalizują przy starcie). Ale istnieje również wiele możliwości optymalizacji w czasie łącza i podczas instalacji.

Jestem szczególnie zainteresowany ideą platformy, na której nie przejmujesz się linkowaniem do czasu instalacji. Ale podczas tego procesu łączenia w czasie instalacji bierzesz agresywną strategię optymalizacji, ponieważ znasz wiele szczegółowych informacji o architekturze maszyny i możesz podejmować bardziej subtelne i dobrze uzasadnione decyzje dotyczące optymalizacji.

Answer 16

Automatyczne generowanie kodu inline przy użyciu testów heurystycznych dla kompromisów dotyczących rozmiaru/prędkości.

Answer 17

Zrobiłem to w moim własnym nauczaniu "droga powrotna". Nie położyłbym tak dużego nacisku na optymalizację, jak na inne rzeczy, takie jak wnioskowanie o typ lub JIT lub kod bajtowy lub obsługa formatu obiektu/debugowania.

Nie ma nic złego w koncentrowaniu się na optymalizacji, o ile jednocześnie przekazuje się, że jest o wiele mniej ważne niż ludzie myślą. Liczy się tylko w kodzie, że:

• biegnie w obcisłych pętli na dnie stosu wywołań (czyli bez wywoływania funkcji, jawnie lub niejawnie)
• faktycznie zajmuje znaczną część czasu wykonania aplikacji (czyli jeśli kod jest rzadko uruchamiany, optymalizacja go nie pomoże).

Jest to dość mały ułamek całego kodu, który zobaczy kompilator.

Edycja: Niestety, nie mogę uciec od pracy z kompilatorami Fortran, które bezlitośnie szyfrują kod, co bardzo utrudnia debugowanie, mając jednocześnie wpływ na wydajność.

Answer 18

Kompilator perlowy B :: CC przydaje się przy dodawaniu i analizowaniu typów. Po prostu nie mam na to wystarczająco dużo czasu.

Wystarczająco dużo czasu ostatnio. http://blogs.perl.org/users/rurban/2011/02/use-types.html