Kompiler - Část 8 , Emitting |  |
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