Pokrok :)

Hotový projekt

Náplní tohoto modulu je vygenerování kódu v assembleru Universal Scriptu pro každou funkci. Bude to nějaká posloupnost instrukcí. Instrukce je v kompileru zastoupena třídou CInstruction, která má jako většina tříd a struktur složku kind, která určuje kterou z 33 instrukcí které Universal Script Assembler představuje. Třída CInstruction má také ukazel next na další instrukci. Kód dané funkce bude v paměti tedy uložen jako jednosměrný lineární spojový seznam sestávající z instancí třídy CInstruction. S tím souvisí proměnná opcodes struktury FUNCTION, která ukazuje na začátek kódu (spojového lineárního seznamu) funkce, kterou představuje. Psát program v assembleru, ať už v jakémkoliv, není zrovna uživatelsky nejpohodlnější a nejlehčí. Teď chceme aby to dělal stroj, aby cykly a podmínky napsal v assembleru a aby výsledek dělal to samé jako napsaný skript. Jak ale stroj naučíme programovat v assembleru, nebo aspoň vyjádřit skript, který máme uložený v paměti jako strom, vyjádřit jako program v assembleru Universal Scriptu? Nejjednodušší řešení je použítí tzv. šablon. Pro každou programovou konstrukci (if, while, for...) a výraz (sčítání, odčítání...) dáme kompileru šablonu, podle které vygeneruje kód/posloupnost instrukcí. Když bude vědět jak vyjádřit například if, nic mu nebrání aby to udělal. Kód který vygeneruje tento modul za pomoci šablon nebude nijak optimalizovaný. Ani pro velikost, ani pro rychlost ani pro nic jiného. Jen bude "chodit" a o to nám tu jde. Až kompiler dokončíte, můžete (měli by jste pokud chcete jazyk používat ve svých komerčních programech) popřemýšlet jak kód optimalizovat. To si vyžadá jistě vložení dalšího modulu, nejlépe za tento modu :) My se tady optimalizací bavit nebudeme, není to důležité pro o aby skriptovací jazyk fungoval. Jak se dá v assembleru napsat příkaz if-else jsme se podívali vlastně už v minulé lekci. Samotný if se moc neliší a jistě ho zvládnete vymyslet/odvodit z if-else nebo opsat sami :) Proto se podíváme hned na cykly. Co třeba cyklus for:

    for (i = 0; i < 5; i++)
    {
       a *= i;
    }

Kód který pro tento cyklus vygeneruje kompiler:

    Toto je inicializace cyklu i = 1, provede se pred provadenim cyklu
    ldc_int 0//Načti na vrchol zásobníku 0
    store 0//Ulož 0 do proměnné i (i má index 0)
    Tady zacina test a vyhodnoceni podminky
    start_0:
    load 0//Nacti na vrchol zasobniku promennou i
    ldc_int 5//Nacti na vrchol zasobniku konstantu 5
    if_cmplt true_2//Porovnej jestli je i < 5, pokud ano skoci se na navesti true_2
    ldc_int 0//i je vetsi nez 5, dosad na zasobnik nulu jako priznak toho ze podminka neplati
    goto stop_3//podminka neplati a skoc na stop_3, kde se rozhoduje jestli ma cyklus pokracovat
    true_2:
    ldc_int 1//dosad na zasobnik jednicku jako priznak toho ze podminka plati
    stop_3:
    ifeq stop_1//pokud je na vrcholu zasobniku 0, skoc na stop_1 (konec cyklu), jinak nikam neskakej a pokracuj v tele cyklu
    Tady zacina telo cyklu
    ldc_int 0//nacti na zasobnik nulu
    store 1//Uloz nulu do proměnne a (tento radek spolecne s predchozim tvori deklaraci a inicializaci proměnne a)
    load 1//nacti na zasobnik a
    load 0//nacti na zasobnik i
    mul//vynasob i s a (a *= i -> a = a * i)
    dup//okopiruj vysledek na zasobnik
    store 1//uloz vysledek nasobeni do a
    pop//sniz ukazatel vrcholu zasobniku o 1
    Tady zacina cast updates, neboli i++
    load 0//nacti na zasobnik proměnnou i
    dup//okopiruj ji zasobnik
    inc//zvys i o 1
    store 0//uloz inkrementovane i
    pop//sniz ukazatel vrcholu zasobniku o 1
    goto start_0//jdi na zacatek cyklu, k overeni podminky
    stop_1:

V této ukázce vidíme hned několik věcí. Víme, že inicializace cyklu se provede jen jednou a proto je první. Pak si můžeme všimnout jak se vypořádat s podmínkou. Poté následuje přímo tělo cyklu a poslední je část s kódem který se má provést po každém průchodu cyklu. Možná vám připadá že je v kódu několik zbytečných instrukcí. To máte pravdu. Většinu instrukcí dup a pop bychom mohli vynechat. Ale než si začnete programovat modul optimalizací kódu,počkejte než si vysvětlíme proč tam jsou. Čili v šabloně pro cyklus for budeme kód sestavovat následujícím způsobem. Za prvé vygenerujeme kód pro inicializaci cyklu. Za druhé vložíme návěští, které označuje začátek cyklu. Za třetí vygenerujeme kód pro podmínku. Následuje kód těla cyklu a skok na začátek cyklu. Poslední je návěští označující konec cyklu. V kompileru to bude vypadat následovně:

    case forT:
       //nejdriv vygeneruj kod pro inicializaci skriptu
       processFORINIT(statement->val.forS.inits);
       //vloz navesti oznacujici zacatek cyklu
       instruct_label("start",statement->val.forS.startlabel);
       //vygenruj kod pro podminku
       processEXPRESSION(statement->val.forS.condition);
       //vloz skok na konec cyklu pokud podminka neplati
       instruct_ifeq(statement->val.forS.stoplabel);
       //vygeneruj kod pro telo cyklu
       processSTATEMENT(statement->val.forS.body);
       //vygeneruj kod pro aktualizaci cyklu
       processEXPRESSION(statement->val.forS.updates);
       //podminka souvisi s pravidlem ze kazda operace musi zasobnik zanechat ve stavu v jakem byl pred
       //spustenim operace. Tz. ze pokud operace neco uklada na zasobnik, musi to pred skoncenim vsechno vyjmout, aby
       //by ukazatel zasobniku byl stejny jako pred operaci

       if (statement->val.forS.updates->kind == callT)
          if (statement->val.forS.updates->val.callE.symbol->val.functionS->returns_value == false)
             instruct_nop();
          else
             instruct_pop();
       else
          instruct_pop();
       //vloz skok na zactek cyklu
       instruct_lgoto(statement->val.forS.startlabel);
       //vloz navesti oznacujici konec cyklu
       instruct_label("stop",statement->val.forS.stoplabel);
       break;

Tuto šablonu najdete ve funkci processSTATEMENT. Podívejme se ještě do funkce processEXPRESSION na šablonu pro operátor '<':

    case lessT:
       //vygeneruj kod pro levou stranu podminky
       processEXPRESSION(expression->val.lessE.left);
       //vygeneruj kod pro pravou stranu podminky
       processEXPRESSION(expression->val.lessE.right);
       //vloz podmineny skok ktery skoci pokud leva starna je mensi nez prava
       instruct_if_cmplt(expression->val.lessE.truelabel);
       //podmineny skok neskocil, vloz na zasobnik nulu jako indikaci toho ze podminka nebyly splnena
       instruct_ldc_int(0);
       //vloz skok na misto kde si dalsi kod overi vysledek
       instruct_lgoto(expression->val.lessE.stoplabel);
       //vloz navesti, sem se skoci pokud je podminka splnena
       instruct_label("true",expression->val.lessE.truelabel);
       //vloz na zasobnik 1, indikace splenene podminky
       instruct_ldc_int(1);
       //navesti oznacujici misto kde bude vlozen kod ktery rozhodne co delat podle
       //vysledku porovnani

       instruct_label("stop",expression->val.lessE.stoplabel);
       break;

Tím bych nechal být cykly a podmínky if. Podmínku if známe z minulé lekce. Czklus while je jednodušší než for. Na začátku bude mít návěští označující jeho začátek. Následovat bude kód zpracovávající podmínku. Pokud bude podmínka platit, nebude se nikam skákat a bude se provádět kód následující za podmínkou, tj. tělo cyklu. Na konci těla cyklu bude skok na začátek cyklu a poslední bude návěští označující konec cyklu, na které se skočí při nesplnění podmínky. Šablony pro další porovnávací operátory vycházejí ze stejné filosofie jako šablona pro '<'. Ukážeme si například šablonu pro sčítání:

    case plusT:
       //vygeneruj kod pro levou stranu
       processEXPRESSION(expression->val.plusE.left);
       //vygeneruj kod pro pravou stranu
       processEXPRESSION(expression->val.plusE.right);
       //proved soucet
       instruct_add();
       break;

Jednoduché, nebo ne? Teď se pokusím vám na příkladu vysvětlit proč jsou do kódu vkládány instrukce dup a pop, které v celkovém kontextu mohou být zbytečné jako v ukázkovém kódu pro cyklus if. Následující výraz je v Universal Scriptu platný:

5 + 8;

Pro vygenerování kódu se použije výše uvedená šablona. Výsledek sčítání bude uložen na zásobník, ale jak je vidět, výsledek se nikam neukládá. Povím vám o jednompravidle které platí pro náš virtuální stroj založený na zásobníku. Po provedení kterékoliv akce musí být ukazatel zásobníku ve stejném stavu jako před provedením akce. Byl-li tedy ukazatel zásobníku před tím než se přešlo na vykonání tohoto součtu například 5, musí být po vykonání součtu také 5. To ale za použití této šablony nebude splněno, protože součet se uloží na zásobník, ale není odtud nikam přesunut. Do žádné proměnné ho neukládáme. Vrchol zásobníku by tedy byl 6. To může ovlivnit další chod programu, pokud třeba kód následující po tomto součtu, měl pracovat s nějakou hodnotou, kterou na zásobník uložil kód předcházející součtu, že? Proto je nutno snížit zásobník zpět na 5 vložením instrukce pop a bude to vpořádku. Proto po každém příkazu typu výraz (pokud nejde o volání funkce, která nevrací hodnotu) je vkládána instrukce pop:

    case expT:
       //zpracuj vyraz
       processEXPRESSION(statement->val.expression);
       //podminka souvisi s pravidlem ze kazda operace musi zasobnik zanechat ve stavu v jakem byl pred
       //spustenim operace. Tz. ze pokud operace neco uklada na zasobnik, musi to pred skoncenim vsechno vyjmout, aby
       //by ukazatel zasobniku byl stejny jako pred operaci

       if (statement->val.expression->kind == callT)
          if (statement->val.expression->val.callE.symbol->val.functionS->returns_value == false)
             instruct_nop();
          else
             instruct_pop();
       else
          instruct_pop();

       break;

A tomu jsou přizpůsobeny i šablony pro ostatní výrazy, například pro přiřazení výrazu do proměnné:

    case assignmentT:
       //zpracuj výraz na pravé straně
       processEXPRESSION(expression->val.assignmentE.right);
       //vysledek okopiruj do zasobniku
       instruct_dup();
       //uloz to do promenne
       instruct_store_lvalue(expression->val.assignmentE.left);
       break;

Tady lze vidět že je vložena instrukce dup, která výsledek výrazu okopíruje na zásobník ještě jednou. A to právě kvůli vkládání instrukce pop. Normálně by stačilo tuto instrukci vynechat. Výsledek výarz na pravé straně přiřazení by tak byl instrukcí store uložen do proměnné a ukazatel vrcholu zásobníku by byl vpořádku. Ale příkaz a = 4; není volání funkce která nevrací hodnotu, bude za něj vložena instrukce pop která snižuje vrchol zásobníku o 1. Při použití stejných hodnot ukaztele zásobníku, by tedy bez použití funkce instrukce dup byl ukazatel zásobníku snížen na hodnotu 4, což už je také špatně (pokud původní ukazatel byl 5).

Myslím že na osvětlení toho jak je genrován kód funkcí by to stačilo. Zbylé šablony si prohlédněte ve zdrojových kódech kompileru. Předposlední funkcí kterou si ukážeme je funkce pro přidání instrukce do spojového seznamu instrukcí dané funkce:

    //****************************************************************************************************************
    //Funkce prida instrukci do spojoveho seznamu instrukci
    //****************************************************************************************************************

    void CCode::AddInstruction(CInstruction* instruction)
    {
       if (!m_CurrCodeStart) //pokud ukazatekl na zacetk kodu je neplatny
       { //znamena to ze do seznamu nebyla jest pridana ani prvni instrukce
          m_CurrCodeStart = m_CurrCode = instruction; //nastavime proto zacatek seznamu instrukci na nove pridavanou instrukci
       }
       else
       {
          m_CurrCode->next = instruction; //ukazatel na dalsi instrukci u soucane instrukce nastavime na nove pridavanou instrukci
          m_CurrCode = m_CurrCode->next; //ukazatel na soucasnou instrukci nastavime na nove pridanou instrukci
       }
    }

Proměnná m_CurrCodeStart je pomocná proměnná ukazující na začátek kódu/spojového seznamu instrukcí zpracovávané funkce. Pokud je tento ukazatel NULL, znamená to že do kódu dané funkce nebyla dosud přidána jediná instrukce. Proto přidáme první instrukci na začátek kódu. Ukazatel m_CurrCode ukazuje na poslední instrukci (pokud je přidána první instrukce, je zárověň první i poslední v seznamu), za kterou mohou být přidávány další instrukce. Pokud je ukazatel m_CurrCodeStart, znamená to že kód funkce obsahuje minimálně 1 instrukci, proto další instrukci přidáme za poslední instrukci (nastavením jejího ukazele next) a ukazatel na poslední instrukci přenastavíme, aby ukazoval na poslední přidanou instrukci. Ve funkci processFUNCTION jen uložíme ukazatel ukazující na začátek vygenerovaného kódu:

    //****************************************************************************************************************
    //Pruchod funkcemi
    //****************************************************************************************************************

    void CCode::processFUNCTION(FUNCTION* function)
    {
       if (function->kind == localT) //sestavovat kod ma smysl jen pro lokalni funkci, u externi nezname telo
       {
          m_CurrCodeStart = NULL; //seznam instrukci je prazdny
          function->labels = new LABEL[function->labelCount]; //vytvor pole pro navesti
          m_CurrLabels = function->labels; //ukazatel na aktualni pole popisku nastav na nove vytvorene pole

          if (function->statements != NULL)
             processSTATEMENT(function->statements); //zpracuj telo funkce

       //uloz ukazatel na seznam instrukci
       function->opcodes = m_CurrCodeStart;
       }
    }

Poslední je funkce pro vytvoření instrukce, instance třídy CInstruction, abychom měli do seznamu instrukcí/kódu zpracovávané funkce co přidávat :) Například funkce instruct_mul, pro vytvoření instrukce násobení:

    //****************************************************************************************************************
    //Prida do seznamu instrukci mul
    //****************************************************************************************************************

    void CCode::instruct_mul()
    {
       CInstruction* pInstruction = new CInstruction;
       pInstruction->mul(NULL);
       AddInstruction(pInstruction);
    }

Je vytvořena nová instance třídy CInstruction a pak zavolána její metoda mul(), která je nastaví členskou proměnnou kind třídy na konstantu mulCK, která značí že jde o instrukci násobení. Poslední příkaz zavolá funkci AddInstruction (výše.) která instrukci přidá do kódu zpracovávané funkce. To je pro tuto kapitolu vše. Jak už jsem psal výše, zbytek programového kódu si prohlédněte ve zdrojovém projektu. Věm, že vám nebude dělat větší problémy.

Část 6
Část 8