Warsztat.GDCompo!ProjektyMediaArtykułyQ&AForumOferty pracyPobieranie

Opisz napotkaną sytuację, a redakcja niezwłocznie znajdzie rozwiązanie!

wyślij anuluj

Tworzenie języków programowania na potrzeby gier z użyciem infrastruktury LLVM

http://warsztat.gd/files/articles/wgk2011/wgk-llvm.pdf

http://dablang.net

1. Wstęp

Tworzenie gier komputerowych wymaga technik programistycznych, które rzadko są używane poza dość wąską dziedziną aplikacji ukierunkowanych na wydajność. Również możliwość wyboru używanego języka programowania jest dosyć ograniczona. Podstawowym wymogiem jest możliwość kompilacji do kodu natywnego. Tymczasem większość nowych języków jest interpretowana lub też osadzona w maszynie wirtualnej. Inną niepożądaną cechą jest wbudowany w język automatyczny garbage collector. Choć pozwala on – według niektórych ­­– na łatwiejsze tworzenie kodu to powoduje również trudne do przewidzenia przestoje w działaniu aplikacji. Przerwa trwająca kilkadziesiąt milisekund nie wpływa w żadnym stopniu na działanie aplikacji webowej, ale jest nieakceptowalna w przypadku gry komputerowej.

O ile twórcy innego rodzaju oprogramowania doczekali się wielu języków ściśle dostosowanych do ich potrzeb, o tyle programiści gier komputerowych nie mają dużego wyboru poza C i C++. Trzeba jednakże zauważyć, że w stosunku do C, C++ wprowadza niewiele rzeczywistych usprawnień. Nowe cechy tego języka sprawiają, że jest to język bardzo skomplikowany, zarówno dla jego użytkowników, jak i twórców kompilatorów. Dodatkowo większość tych cech nie nadaje się do krytycznych wydajnościowo zastosowań, ze względu na narzuty, które pojawiają się podczas ich rzeczywistego zastosowania.

Nie można zapominać, że znaczna część gier komputerowych przeznaczona jest również do działania na konsolach takich jak Xbox 360 oraz Playstation 3. Wyposażone są one w procesory PowerPC, które znacznie gorzej niż "domowe" układy oparte na architekturze x86 radzą sobie z wykonaniem nieliniowego kodu, wymagającego wielu pośrednich odwołań do pamięci. Tymczasem programowanie obiektowe, które stanowi jedną z podstaw C++, skupia się na tworzeniu kolejnych poziomów abstrakcji i odwołań do obiektów rozrzuconych w pamięci.

Dlatego też moim zdaniem programowanie gier wymaga stworzenia języka lub języków programowania ściśle dostosowanych do potrzeb. Liczba mnoga pojawia się, gdyż można wyodrębnić kilka kategorii podprogramów używanych w grach komputerowych:

1. Kod silnika/bazowych modułów gry potrzebuje języka o umiarkowanych możliwościach, natomiast wskazane jest, by koszty poszczególnych elementów języka były łatwe do przewidzenia przez programistę.

2. Kod odpowiedzialny za przetwarzanie dużych ilości danych potrzebuje prostego języka o bardzo dużych możliwościach optymalizacyjnych. Język ten powinien obsługiwać również równoległość, najlepiej także na procesorach graficznych.

3. Kod odpowiedzialny za mechanikę gry (tzw. gameplay) powinien udostępniać mechanizmy do łatwego prototypowania i łatwego skryptowania.

Do tej pory wszystkie te zastosowania wymagały użycia różnych języków, które dość słabo się ze sobą integrują. Przykładowo wybór C++ jako języka bazowego, OpenCL jako języka przetwarzania danych oraz Lua jako języka dla skryptów wymaga trzech różnych środowisk i narzędzi do tworzenia, testowania czy profilowania aplikacji.

2. Proces kompilacji

Na początku chciałbym zastrzec, że mimo użycia kodu w języku C++ artykuł nie opisuje procesu kompilacji kodu C++. Kompilacja C++ jest niezwykle skomplikowana w porównaniu do innych języków i nie jest ściśle związana z tematyką niniejszego artykułu. Kod C++ został użyty dla ułatwienia lektury przez czytelnika, który języka C++ używa na co dzień.

2.1. Tworzenie kodu

 

Działanie kompilatora składa się z trzech zasadniczych etapów:

 

Front-end to narzędzie, które analizuje dostarczony przez użytkownika kod w postaci tekstowej, sprawdza poprawność tego kodu i generuje na jego podstawie drzewo składni (ang. AST – abstract syntax tree).

 

Middle-end to narzędzie, które dokonuje optymalizacji AST i przekształca wysokopoziomowe instrukcje w niskopoziomowe.

 

Back-end to narzędzie, które na podstawie przetworzonego AST generuje kod maszynowy i/lub informacje dla dalszych narzędzi (m.in. linkera).

 

Przykładowy kod, na którym zostaną pokazane poszczególne etapy to:

 

#define VALUE(x) (0x100 | x)

 

extern "C" int printf(const char *format, ...);

 

struct value_printer

{

  int * v;

 

  value_printer(int v1, int v2)

  {

    v = new int[2];

    v[0] = v1;

    v[1] = v2;

  }

 

  ~value_printer()

  {

    delete [] v;

  }

 

  void print()

  {

    if (v)

    {

      printf("%x + %x = %x\n", v[0], v[1], v[0] + v[1]);

    }

  }

};

 

int main()

{

  int v1 = VALUE(0x80);

  int v2 = VALUE(0x40);

 

  value_printer v(v1, v2);

  v.print();

 

  return 0;

}

 

 

2.2. Preprocesor


                Pierwszym etapem kompilacji w językach wyposażonych w preprocesor jest zastosowanie go. W trakcie tego procesu dołączane zostają pliki nagłówkowe (dyrektywa #include) oraz rozwijane makrodefinicje (#define, #if itp.). W naszym przykładzie, by uniknąć włączania długiego kodu (co jest bolączką C++, zwłaszcza przy stosowaniu rozbudowanych bibliotek jak STL czy Boost), jedyna używana funkcja biblioteczna printf została zdefiniowana ręcznie. Jedyną zmianą wykonaną przez preprocesor jest zmiana

 

int v1 = VALUE(0x80);

int v2 = VALUE(0x40);

 

na

 

int v1 = (0x100 | 0x80);

int v2 = (0x100 | 0x40);

 

 

Oczywiście w przypadku rzeczywistych aplikacji działanie preprocesora jest znacznie silniejsze ­– w C (a co za tym idzie również C++) wiele konstrukcji opiera się na makrodefinicjach. Na przykład w przypadku aplikacji Windows zadaniem preprocesora jest między innymi wybór między wariantami ANSI i Unicode poszczególnych funkcji systemowych (np. MessageBox zostaje rozwijany do MessageBoxA lub MessageBoxW).

 

2.3. Analiza leksykalna

 

Następnym krokiem jest analiza leksykalna, czyli podział kodu programu na tokeny. Token to pojedynczy symbol występujący w kodzie, którym może być przykładowo: słowo kluczowe, klamra, operator, stała liczbowa lub znakowa czy też dowolny identyfikator stworzony przez użytkownika.

 

 

EXTERN "C" INT printf ( CONST CHAR * format , ... ) ;

STRUCT value_printer

{

INT * v ;

value_printer ( INT v1 , INT v2 )

{

v = NEW INT [ 2 ] ;

v [ 0 ] = v1 ;

v [ 1 ] = v2 ;

}

~ value_printer ( )

{

DELETE [ ] v ;

}

VOID print ( )

{

IF ( v )

{

printf ( "%x + %x = %x\n" , v [ 0 ] , v [ 1 ] , v [ 0 ] + v [ 1 ] ) ;

}

}

} ;

INT main ( ) {

INT v1 = ( 0x100 | 0x80 ) ;

INT v2 = ( 0x100 | 0x40 ) ;

value_printer v ( v1 , v2 ) ;

v . print ( ) ;

RETURN 0 ;

}

 

Należy zauważyć, że już na etapie tokenizacji trzeba podjąć kilka decyzji projektowych co do języka. Przykładowo w powyższym przykładzie nazwy typów wbudowanych zostały potraktowane jako słowa kluczowe. Nie jest to jednak ścisły wymóg. Równie dobrze można potraktować typy wbudowane jak zdefiniowane przez użytkownika i rozpoznawać je na etapie analizy składniowej.

2.4. Analiza składniowa

 

Celem analizy składniowej jest zmiana listy tokenów na drzewo instrukcji (AST). W tym celu definiuje się gramatykę, która określa jak mogą być łączone ze sobą symbole (początkowo równoważne tokenom) w celu tworzenia nowych symboli.

Przykładem gramatyki może być następujący zbiór definicji:

 

Typ Identyfikator ; -> DeklaracjaZmiennej

Liczba -> Wyrażenie

Wyrażenie + Wyrażenie -> Wyrażenie

Identyfikator = Wyrażenie ; -> Przypisanie

 

Od konstrukcji języka zależy w jaki sposób składnia jest przetwarzana. Część języków może być przetwarzana w pojedynczym przebiegu, podczas gdy inne wymagają kilku przebiegów, aby zebrać wszystkie informacje na podstawie kodu. Przykładowo, dla prostych języków dużą część analizy i sprawdzania poprawności kodu można wykonać już na etapie analizy składniowej. W przypadku złożonych języków jak C++ jest to często niemożliwe, gdyż typy danych mogą być tworzone dynamicznie za pomocą mechanizmu szablonów.

 

 

 

 

Rys 1. Fragmenty wygenerowanego AST

2.5. Przetwarzanie AST

 

Gdy kompilator ma dostępne AST, następuje drugi etap kompilacji (middle-end). Polega on na transformacjach składni, mających dwojaki cel: optymalizację (lub wręcz przeciwnie – osadzanie informacji, które będą służyły do debugowania programu) oraz przekładanie instrukcji wyższego poziomu na instrukcje niższego poziomu. Ma to na celu zmianę wysokopoziomowego programu na instrukcje docelowej maszyny.

Takie transformacje często określane są jako lowering. Przykładem loweringu w C++ jest zmiana wywołań metod klas na odpowiadające im wywołania funkcji. W tym celu, zgodnie z konwencją wywołania funkcji, nastepuje zmiana z

 

object->fun(arg1, arg2);

 

na

 

class_fun(object, arg1, arg2);

 

Podobnie rozwijane są inne elementy języka. Na przykład dodawane są wywołania konstruktorów i destruktorów:

 

{

  CObject object;

  ...

}

 

zostanie zmienione na

 

{

  [storage] CObject object;

  CObject_ctr(object);

  ...

  Cobject_dtr(object);

}

 

Kolejnym przekształceniem może być rozwinięcie alokacji lokalnych (na stosie) do ich rzeczywistej postaci:

 

{

  CObject * object =

    stack_allocate(sizeof(CObject), alignof(CObject));

  ...

}

 

Takie alokacje zostają następnie zebrane w całym bloku i ustawione zostają odpowiednio wskaźniki obiektów:

 

{

  void * stack = stack_allocate(32);

  CObject * object = stack + 4;

  ...

}

 

Dodatkowo na tym etapie stosowane mogą być optymalizacje, takie jak CSE (common subexpression elimination) czy CP (constant propagation). Nie jest to jednak wymóg, optymalizacje mogą mieć miejsce również w trzecim etapie (budowaniu kodu maszynowego).

Gdy program jest już wystarczająco niskopoziomowy, by móc przełożyć go na możliwości docelowej architektury, następuje ostatni etap kompilacji.

 

2.6. Generowanie kodu maszynowego

 

Ostatnim etapem kompilacji jest translacja operacji na instrukcje docelowej maszyny. W przypadku gdy jest nią rzeczywisty procesor, musimy zatroszczyć się m.in. o optymalny dobór rejestrów w celu eliminacji nadmiernej ilości operacji load/store. Innym zagadnieniem jest odpowiedni podział instrukcji dla poszczególnych jednostek wykonawczych (współczesne procesory składają się z wielu jednostek, które mogą przetwarzać kod równolegle).

Ten etap jest trudny zwłaszcza dla maszyn typu CISC, gdzie jest wiele różnych instrukcji, które mogą posłużyć do wykonania tych samych operacji. Na szczęście etap ten prawie w całości może zostać wykonany przez LLVM.

 

3. CZYM JEST LLVM?

 

LLVM (Low Level Virtual Machine) to kompleksowy pakiet mający na celu pomoc twórcom kompilatorów. Składa się z wielu elementów, spośród których należy wyróżnić:

1. Zestaw bibliotek, który można wykorzystać we własnym programie do manipulacji bytecodem maszyny LLVM.

2. Zewnętrzne narzędzia do analizy i optymalizacji bytecodu (w tym też asembler i disasembler).

3. Pakiet Clang będący front- i middle-endem dla języków C, C++ oraz Objective C.

 

LLVM operuje na własnym bytecodzie, nieodzwierciedlającym architektury żadnego fizycznego procesora. Wirtualna maszyna LLVM to procesor RISC o nieograniczonej liczbie rejestrów. Należy jednak zwrócić uwagę, że LLVM operuje na kodzie w postaci SSA (single static assignment) – każdy rejestr może zostać zainicjalizowany jedynie raz, a potem można jedynie odczytywać z niego wartości. Umożliwia to dużo łatwiejszą analizę kodu oraz większe możliwości optymalizacji. Jak jednak rozwiązać typowe zagadnienia programistyczne, takie jak bloki warunkowe oraz pętle w modelu SSA? Służą do tego specjalne instrukcje – węzły phi. Łączą one różne ścieżki wykonania, ustawiając w nowym rejestrze wartość jednego z kilku innych rejestrów w zależności od ścieżki wykonania programu. Przykładowo, instrukcja warunkowa:

 

int a;

if (b > 4)

  a = 5;

else

  a = 6;

 

Jest reprezentowana w postaci

 

%0 = wartość b

%1 = stała ‘4’

%2 = porównaj %0 i %1

Jeżeli %2 to skocz do #A

Jeżeli nie %2 to skocz do #B

 

#A:

%3 = stała ‘5’

Skocz do #C

 

#B:

%4 = stała ‘6’

Skocz do #C

 

#C:

%5 = phi < %3 dla #A, %4 dla #B>

Zapisz %5 w zmiennej a

 

Instrukcja phi działa w następujący sposób: dla każdej możliwej ścieżki, z której można osiągnąć instrukcję phi, przypisywany jest pewien rejestr. W zależności od ścieżki wybierany jest jeden z nich.

 

Oczywiście ręczne tworzenie konstrukcji SSA dla typowych operacji, takich jak operowanie na zmiennych byłoby dość uciążliwe dla twórców kompilatorów. Dlatego LLVM umożliwia prostsze podejście: dostępne są instrukcje load i store, którymi można operować bezpośrednio na pamięci (wskaźnikach). Następnie jedna z faz optymalizacji (mem2reg) przekształca operacje na pamięci w operacje na rejestrach z użyciem węzłów phi.

 

Rejestry w LLVM są silnie typowane. Dostępne są różne typy maszynowe, takie jak liczby całkowite i zmiennoprzecinkowe różnej wielkości, a także typ binarny (używany przy porównaniach i skokach) oraz wskaźnikowy. Obsługę struktur i klas musi zapewnić twórca języka. Do jego dyspozycji jest bardzo rozbudowana instrukcja GetElementPtr, która umożliwia łatwe tworzenie tablic i struktur.

4. UŻYCIE LLVM PRZY TWORZENIU KOMPILATORA

4.1. Front-end

LLVM nie udostępnia narzędzi potrzebnych w tym etapie. Użytkownik może zbudować własne narzędzia lub skorzystać z jednej z wielu dostępnych bibliotek. Dobrym wyborem może być zestaw lex (flex) i yacc (bison). Pozwalają one na łatwe stworzenie AST na podstawie określonej gramatyki.

4.2. Middle-end

Naszym zadaniem jest transformacja AST do postaci kodu LLVM. Nie musimy ręcznie generować kodu asemblerowego. Biblioteki LLVM pozwalają na tworzenie poszczególnych konstrukcji, takich jak funkcje, bloki i poszczególne instrukcje, za pomocą obiektowego interfejsu. Lowering wysokopoziomowych instrukcji musimy przeprowadzić samemu, zgodnie z potrzebami naszego języka. Możemy też dokonać optymalizacji, i to na dwa sposoby. Po pierwsze, część optymalizacji można przeprowadzić jeszcze na drzewie AST. Jednak nie zawsze warto samemu implementować tego typu operacje, ponieważ LLVM jest w stanie samemu przeprowadzić dużą część optymalizacji, na przykład propagacja stałych czy usuwanie wspólnych podwyrażeń. Możemy również zaimplementować własne fazy optymalizacji bezpośrednio w LLVM. Operujemy wtedy na poszczególnych elementach konstrukcyjnych LLVM – przykładowo możemy stworzyć fazę optymalizacji funkcji. Wtedy nasz kod zostanie wykonany na rzecz każdej funkcji w programie.

Przykładowymi fazami optymalizacji, które można dodać do LLVM – zwłaszcza w przypadku wysoko wydajnego kodu na potrzeby tworzenia gier komputerowych – są optymalizacje kodu zmiennoprzecinkowego. Domyślnie LLVM nie dokonuje agresywnych optymalizacji tego typu kodu, ponieważ może to wprowadzać niedokładność w obliczeniach. W przypadku kodu gier nie ma to jednak często znaczenia a zysk wydajności wynikający z takich optymalizacji jest duży. Warto przy okazji zauważyć, że LLVM wspiera kod typu SIMD (SSE dla procesorów Intel). Każdy wbudowany typ ma swój odpowiednik wektorowy (na przykład 4 liczby zmiennoprzecinkowe pojedynczej precyzji), nie jesteśmy jednak ograniczeni do konkretnego zestawu instrukcji (choć oczywiście back-end dokona optymalnej generacji kodu maszynowego jedynie kiedy docelowa architektura wspiera używane  konstrukcje SIMD).

4.3. Back-end

 

Tym etapem kompilacji zajmuje się głównie LLVM. Warto zauważyć, że LLVM oferuje zarówno kompilację statyczną, jak i JIT (Just In Time) – kompilację w czasie wykonania programu. JIT może być wielką zaletą w przypadku niektórych rodzajów kodu, takich jak kod przekształcający duże ilości danych. Procesory rozwijają się bardzo szybko i kolejne generacje układów mają coraz bogatszy zestaw instrukcji. W przypadku procesorów Intel można założyć, że gracz posiada obsługę instrukcji SSE1-SSE3, natomiast zestawy instrukcji SSE4.1 i 4.2 są już rzadziej spotykane. Ostatnio pojawił się też zestaw instrukcji AVX operujący na rejestrach 256-bitowych. JIT umożliwia wykorzystanie 100% możliwości sprzętu gracza, nie ograniczając się do ustalonej z góry architektury. Biblioteki JIT LLVM pozwalają też na automatyczną alokację pamięci na kod wykonywalny i załadowanie tam wygenerowanych funkcji. Ma to znaczenie w nowoczesnych systemach operacyjnych, które wykorzystują flagi stron pamięci (domyślnie alokowana pamięć może być wykorzystana jedynie dla danych, a próba wykonania zawartego w niej kodu powoduje błąd wykonania).

4.4. Przykład użycia LLVM

Większość obliczeń, które wykonujemy w grze nie wymaga naukowej precyzji. Tymczasem model liczb zmiennoprzecinkowych, używany w komputerach PC (IEEE 754) posiada kilka detali, które mogą znacznie zmniejszyć wydajność, takich jak specjalne wartości liczbowe (nieskończoność, NaN czy liczby zdenormalizowane). Dodatkowo w celu zachowania maksymalnej precyzji obliczeń, kompilator może zrezygnować z pewnych uproszczeń. Przykładowo, mając liczbę x, wynik wyrażenia "x + x + x" może być inny niż wyrażenia "x * 3".

Na szczęście używając mamy możliwość dostosowania optymalizacji, również za pomocą własnego kodu. Poniżej przestawiony jest przykład przebiegu optymalizacyjnego, którego zadaniem jest usuwanie przekształceń identycznościowych, takich jak mnożenie przez 1 oraz dodawanie i odejmowanie 0:

struct RemoveFloatingIDS : public BasicBlockPass

{

  virtual bool runOnBasicBlock(BasicBlock &block)

  {

    BasicBlock::InstListType &ins = block.getInstList();

 

    for (BasicBlock::InstListType::iterator it = ins.begin(), end = ins.end(); it != end; ++it)

    {

      Instruction & i = *it;

      if (!i.isBinaryOp()) continue;     

      BinaryOperator &binOp = dynamic_cast<BinaryOperator&>(i);

      Value *L = binOp.getOperand(0);

      Value *R = binOp.getOperand(1);

      ConstantFP *rCons = dynamic_cast<ConstantFP*>(R);

      if (!rCons) continue;

 

      float rValue = rCons->getValueAPF().convertToFloat();

      int op = binOp.getOpcode();

 

      if ((op == Instruction::FAdd || op == Instruction::FSub) && fabs(rValue) == 0.0f)

      {

        binOp.replaceAllUsesWith(L);

        binOp.eraseFromParent();

        return true;       

      } 

      if ((op == Instruction::FMul || op == Instruction::FDiv) && rValue == 1.0f)

      {

        binOp.replaceAllUsesWith(L);

        binOp.eraseFromParent();

        return true;       

      }

    }

    return false;

  }

};

 

Kod używający LLVM operuje na bardzo intuicyjnych konstrukcjach takich jak blok, instrukcja, wartość czy stała. W łatwy sposób można tworzyć własne instrukcje i wyrażenia oraz przekształcać kod LLVM zgodnie z potrzebami tworzonego przez nas języka.

5. ZAKOŃCZENIE

 

LLVM to jeden z najbardziej obiecujących projektów ostatnich lat. Do tej pory tworzenie kompilatorów było zajęciem bardzo wymagającym, przez co rzadko spotykało się zastosowanie własnych (kompilowanych) języków programowania. LLVM pozwala na ominięcie sporej części trudności, przez co rzeczywiste staje się wykorzystanie DSL (domain specific language) nawet w najbardziej wymagających zadaniach, takich jak gry komputerowe.

Mam nadzieję, że w przeciągu kilku najbliższych lat powstaną języki bardziej dostosowane do zagadnienia tworzenia gier komputerowych niż C++. Innym przydatnym zastosowaniem byłoby stworzenie środowiska programistycznego (IDE) zintegrowanego z LLVM. Częściowo dokonał tego Apple w XCode4, gdzie wykorzystywany jest Clang do analizy kodu już w trakcie pisania. Jednak dopiero pełna integracja z LLVM pozwoli na zmniejszenie bariery między tworzeniem a uruchamianiem programu.

BIBLIOGRAFIA

[1]  Wirth N.: Compiler Construction, Addison-Wesley, 1996

[2] Terry P.: Compilers and Compiler Generators: An Introduction with C++, International Thomson Computer Press, 1997

[3] Low Level Virtual Machine: http://llvm.org/

[4] Dąbrowski T.: Quick Data Transformation, http://dabroz.scythe.pl/2010/11/18/quick-data-transformation

Tekst dodał:
Tomasz Dąbrowski
06.09.2011 13:44

Ostatnia edycja:
Tomasz Dąbrowski
03.04.2012 17:25

Kategorie:

Aby edytować tekst, musisz się zalogować.

# Edytuj Porównaj Czas Autor Rozmiar
#3 edytuj (poprz.) 03.04.2012 17:25 Tomasz Dąbrowski 31.01 KB (+29.94 KB)
#2 edytuj (poprz.) (bież.) 03.04.2012 17:24 Tomasz Dąbrowski 1.08 KB (+1)
#1 edytuj (bież.) 06.09.2011 13:44 Tomasz Dąbrowski 1.08 KB
Zwykły
Do sprawdzenia
Do akceptacji
  • Napisz komentarz:
    Aby dodać swój komentarz, musisz się zalogować.
Licencja Creative Commons

Warsztat używa plików cookies. | Copyright © 2006-2017 Warsztat · Kontakt · Regulamin i polityka prywatności
build #ff080b4740 (Tue Mar 25 11:39:28 CET 2014)