Pokrok :)

Hotový projekt
Předposlední modul našeho kompileru generuje první výstup, výstupní soubor. Modul předešlý nám vygeneroval assembly kód skriptu, který
máme v paměti uložený jako lineární spojový seznam složený z instancí třídy CInstruction. Jak víme, třída CInstruction obsahuje členskou proměnnou
kind, která udává jakou instrukci konkrétně třída zastupuje. Jistě nebude problém projít vygenerovaný kód od začátku do konce a postupně instrukce zapisovat do souboru.
To je ten lehčí úkol který bude mít modul Emitting na starost. Vezmeme to od toho těžšího a to je výpočet maximální výšky zásobníku - stack limit.
Stack Limit
Maximální výška zásobníku. Zní to učeně, nebo ne? Vlastně jde o to vypočítat, kolik místa v zásobníku bude funkce maximálně potřebovat k výpočtům a k volání funkcí.
Výpočet to není zase tak složitý. Musíme jen vědět co která instrukce dělá se zásobníkem a projít kód od začátku do konce, abychom to mohli spočítat.
Třeba pokud víme, že instrukce dup zvýší vrchol zásobníku o 1, víme že na její provedení potřebujeme jedno místo v zásobníku. Pokud jsou za sebou tyto instrukce dvě, potřebujeme místa
dvě. Pokud je ale za první instrukcí dup instrukce pop a další dup až po pop, stačí nám opět jedno místo. Vrchol zásobníku se zvýší o 1 při první instrukci dup, instrukce pop ho ale zase
sníží o 1, tj. na původní hodnotu. Další instrukce dup ho zase zvýší, ale pořád nám na to stačí jedno místo v zásobníku. K vypočítání maximální výšky zásobníku použijeme také
vygenerovaný assembly kód. Příklad jsem uváděl na instrukcích dup a pop. K výpočtu prostě potřebujeme znát jak program vypadá v assembly formě.
Při výpočtu bude tedy nutné také projít celý vygenerovaný kód dané funkce. I když kód je lineární spojový seznam, budeme ho procházet rekurzivně. Tzn. že pokud narazíme na instrukci skoku (
jedno jestli podmíněný nebo ne), vždy budeme ve výpočtu pokračovat na adrese na kterou se skáče a zpátky se vrátíme až narazíme na instrukci nreturn nebo vreturn. Pak se pokračuje dál v kódu který následuje
za skokem který nás předtím odklonil. Je fakt, že skok může skočit někam dopředu, takže abychom se v kódu nezamotali a nekontrolovali některé instrukce několikrát, má třída CInstruction také
proměnnou visited, do které si poznamenáme jestli jsme instrukci už kontrolovali. Pokud ano, nemá cenu ji kontrolovat znovu. To je myslím vše co je nutné k pochopení výpočtu, praktickou část
představuje funkce GetMaxStackSize:
//****************************************************************************************************************
//vrati maximalni velikost zasobniku pro danou funkci
//
//Ve funkci se mohou vyskytovat aritmeticjke operace, volani funkci a pri tom se musi operandy ukladat na zasobnik
//Tato funkce spocita kolik hodnot bude v zasobniku maximalne pritomno pri vykonavani dane funkce.
//Uvedem si priklad. Budeme mit treba funkci ktera jen vola funcki max(1,2,3,4). na zasobnik se musi ulozit tyto
//ctyri argumenty: 1,2,3,4. Maximalni velikost asobniku bude 4. Tato hodnota je vyuzita ve virtualnim stroji ke zjisteni,
//zda muzeme volat a vykonat dalsi funkci aniz by doslo k preteceni, tj. preplneni zasobniku
//****************************************************************************************************************
void CEmit::GetMaxStackSize(CInstruction* code,int iCurrStackSize,int* iMaxStackSize)
{
if (code)
{
//pokud jsme instrukci este nekontrolovali
if (!code->visited)
{
code->visited = 1;
switch (code->kind)
{
case incCK: //tyto instrukce nemeni vrchol zasobniku
case decCK:
case nopCK:
case negCK:
case labelCK:
break;
case lgotoCK:
GetMaxStackSize(m_CurrLabels[code->val.gotoC].position,iCurrStackSize,iMaxStackSize);
break; //nemeni zasobnik
case storeCK: //pocinaje instrukci store, nasledujici instrukce snizuji vrchol zasobniku 0 1
case popCK: //napriklad aritmeticke instrukce add,sub,div,mul vybiraji ze zasobniku dva operandy
case shlCK: //a jeden tam ulozi, ve vysledku se tak vrchol zasobniku snizi o 1 oproti predchozimu stavu
case shrCK:
case mulCK:
case modCK:
case subCK:
case divCK:
case addCK:
case orCK:
case andCK:
iCurrStackSize--;
break;
case ifeqCK:
iCurrStackSize--; //podminene skoky vsechny ve vyslekdu snizuji vrchol zasobniku o 1
//ale u skoku pokracujeme zkoumanim kodu ktery by se porvedl pokud by podminka platila
GetMaxStackSize(m_CurrLabels[code->val.ifeqC].position,iCurrStackSize,iMaxStackSize);
break;
case ifneCK:
iCurrStackSize--;
GetMaxStackSize(m_CurrLabels[code->val.ifneC].position,iCurrStackSize,iMaxStackSize);
break;
case if_cmpeqCK:
iCurrStackSize--;
GetMaxStackSize(m_CurrLabels[code->val.if_cmpeqC].position,iCurrStackSize,iMaxStackSize);
break;
case if_cmpgtCK:
iCurrStackSize--;
GetMaxStackSize(m_CurrLabels[code->val.if_cmpgtC].position,iCurrStackSize,iMaxStackSize);
break;
case if_cmpltCK:
iCurrStackSize--;
GetMaxStackSize(m_CurrLabels[code->val.if_cmpltC].position,iCurrStackSize,iMaxStackSize);
break;
case if_cmpleCK:
iCurrStackSize--;
GetMaxStackSize(m_CurrLabels[code->val.if_cmpleC].position,iCurrStackSize,iMaxStackSize);
break;
case if_cmpgeCK:
iCurrStackSize--;
GetMaxStackSize(m_CurrLabels[code->val.if_cmpgeC].position,iCurrStackSize,iMaxStackSize);
break;
case if_cmpneCK:
iCurrStackSize--;
GetMaxStackSize(m_CurrLabels[code->val.if_cmpneC].position,iCurrStackSize,iMaxStackSize);
break;
case vreturnCK: //pokud narazime na return, ukocnime vypocet
case nreturnCK:
return;
case loadCK: //nasledujici instrukce zvysuji vrchol zasobniku o 1
case ldc_intCK: //jako napriklad instrukce pro nacteni celociselne, desetinne
case ldc_stringCK: //nebo retezcove konstanty na zasobnik
case ldc_doubleCK:
case dupCK:
iCurrStackSize++;
//soucasna vyska zasobniku muze byt mensi nez maximalni hodnota nalezena drive,
//musime si pamatovat tu nejevsti. maximalni vyska zasobniku se uklada jen pokud narazime na
//instrukci ktera ukazatel vrcholu zasobniku zvysuje
*iMaxStackSize = max(iCurrStackSize,*iMaxStackSize);
break;
case ecallCK:
//volani funkce ze zasobniku uvolni parametry, vrchol zasobniku bude snizen o pocet zadanych parametru
//a pokud funkce vraci hodnotu, bude tato hodnota na vrcholu zasobniku po provedeni fce
//a tudiz se zvysi zasobnik o 1
iCurrStackSize -= code->val.ecallC.arguments;
*iMaxStackSize = max(iCurrStackSize,*iMaxStackSize);
if (code->val.ecallC.function->type->kind != VOID_TYPE)
iCurrStackSize++;
break;
case lcallCK:
iCurrStackSize -= functionToStackChange(code->val.lcallC);
if (code->val.ecallC.function->returns_value == true)
iCurrStackSize++;
*iMaxStackSize = max(iCurrStackSize,*iMaxStackSize);
break;
}
}
GetMaxStackSize(code->next,iCurrStackSize,iMaxStackSize);
}
}
Funkce functionToStackChange jen z podpisu funkce přečtě počet parametrů které funkce má. Pamatujete si jak například pro funkci: fce(a.,b,c,d) byl vytvořen podpis: fce(4). 4 v závorce značí, že
má 4 parametry, které bude třeba uložit na zásobník. Funkce functionToStackChange má za úkol zjistit číslo ze závorek podpisu funkce a vrátit ho, abychom věděli kolik
míst v zásobníku bude pro uložení parametrů potřeba. Z toho vyplývá, že největším žroutem zásobníku je volání funkcí.
Emitting
Z minulé lekce máme vygenerovaný assembly kód, zjistili jsme též Locals Limit a před chvíli vypočítali také Stack Limit. Nic víc už k vypsání assembly
kódu skriptu do souboru nepotřebujeme. Součet Locals Limit a Stack Limit určuje kolik místa v zásobníku potřebuje funkce k provedení. Jednak k uložení výsledků a potom k výpočtům.
Bylo by fajn v assembly kódu funkce nějak rozeznat od sebe, proto každá funkce začíná symbolem .function podpis_funkce a končí .end (end-function).
Kód lokální funkce bude uzavřen mezi tyto symboly. pro externí funkce máme zaveden symbol .extern "knihovna" typ podpis_funkce. Ale pro externí funkce žádný kód negenerujeme ani
o nich nic víc vědět nepotřebujeme. Kromě kódu funkce se v bloku funkce budou vyskytovat ještě dva symboly. Bude to .locals_limit číslo, určující Locals Limit a .stack_limit číslo, který
jak je možná poznat udává limit zásobníku. Všechno ostatní jsou buď instrukce nebo něco co nemá v assembly souboru co dělat. Pro vygenerovaný soubor jsem zvolil
příponu .usa, což znamená Universal Scrip Assembly. Na kód který vypisuje vygenerovanýá kód se podívejte do ukázkového projektu. Jde jen o funkci processCode. Funkce obsahuje jen
velký switch pro všechny možné instrukce a generovaání kódu probíhá nějak takhle:
case nopCK:
fprintf(m_assemblyFile,instruction_nop);
break;
Všechny konstanty použité pro jména instrukcí, jako instruction_nop jsou ještě s dalšími definovány v souboru opcodes.h.
No, ještě napíšeme assembly modul a máme kompletní kompiler :)
Část 7
Část 9
|