Kompiler - Část 9 , Assembling |  |
Pokrok :) Hotový projekt I když se to může zdát neuvěřitelné, dostali jsme se k poslední lekci o kompileru. Poslední, desátá lekce, se už bude týkat virtuálního stroje. Posledním úkolem kompileru je převést vygenerovaný assembly kód do nějaké binární podoby. Assembly kód, který vygeneruje modul Coding a do souboru zapíše modul Emitting, představuje zjednodušenou formu skriptu. Kód je složen z jednoduchých instrukcí, které ale stále máme v souboru v podobě textu a pro jejich dekódování a provádění bychom museli používat porovnávání řetězců, řetězcových konstant, a to také není zrovna dvakrát rychlý a optimální způsob. Proto převedeme instrukce z textové podoby na čísla. Každá instrukce bude mít přiřazeno jedinečné číslo. Například instrukce nop má kód, číslo 0, jak již víme z teorie k virtálnímu stroji. K uložení kódu/čísla instrukce nám bohatě postačí jeden bajt, pač máme 33 instrukcí. K tomu by nám stačilo i 6 bitů, ale takový datový typ počítač nemá, takže musíme sáhnout po nejbližším bajtu s 8 bity. Než se pustíme do probírání programového kódu tohoto modulu, čeká nás opět trocha teorie, opakování, shrnutí všeho, co k tomu potřebujeme vědět. ### Struktura binárního souboru: Binární soubor bude mít příponu .usb, což je zkratka pro Universal Script Binary. To já jen tak pro začátek. Je nutné rozmyslet si, jak bude binární soubor skriptu vypadat. To znamená vědět, co všechno potřebujeme mít o skriptu uložené, co všechno o něm potřebujeme vědět. Bude potřeba uložit kódový segment, tj. těla funkcí v podobě bajtových instrukcí. Kód všech funkcí bude představovat jeden dlouhý kódový segment. Chtělo by to tedy znát nějaké informace o funkcích, hlavně kde v kódovém segmentu jejich tělo začíná a kde končí. Pak také máme pro funkce vypočítaný Locals Limit a limit zásobníku. O tyto hodnoty také nechceme přijít. Vyřešíme to všechno strukturou, která bude sdružovat potřebné informace o funkci. Uložit a načíst strukturu ze souboru už není takový problém. Stejně jako budeme mít strukturu pro uložení informací o lokální funkci, budeme mít i strukturu pro externí funkce. Jde sice v obou případech o funkce, ale liší se v informacích, které o nich potřebujeme vědět. Poslední věcí jsou konstanty. Tím myslím číselné a řetězcové konstanty. Jedna možnost je uložit je do kódového segmentu přímo v instrukci, která s konstantou pracuje. Třeba instrukce ldc_int, která má bajtový kód 19, by tedy v paměti zabírala 5 bajtů. První bajt by bylo číslo 19 a zbylé čtyři by patřily integer konstantě, kterou by tato instrukce měla načíst na zásobník. To se dá celkem jednoduše dekódovat, že. Horší je to ale v případě řetězcových konstant. Řetězce jednak zaberou víc bajtíků a za druhé mohou být různě dlouhé a proto by ani nebylo tak jednoduché přečíst třeba instrukci ldc_string (kód 20), protože bychom nevěděli, jak je i s operandem (onou řetězcovou konstantou) dlouhá. Načítání řetězcové konstanty by nás tedy zdržovalo a když bychom řetězcové konstanty využívali více "hojně" a v případě že by se jednalo o stejný řetězec, by to bylo evidentně plýtvání místem. Myslím, že lepší bude uložit všechny konstanty do jakési tabulky a přiřadit jim indexy. Každá instrukce, která pak bude chtít s konstantou pracovat, bude znát jen index pod kterým ji najde v tabulce. Teď víme co budeme v souboru potřebovat, proč to budeme potřebovat a částečně také, jak to potom bude ve virtuálním stroji fungovat. Teď to ještě budeme muset nějak zorganizovat, jako co půjde jak a za sebou :). Aby byl binární soubor trochu pružnější, označíme každou sekci číslem. Tak budeme moci třeba snadno změnit pořadí zapsání sekcí v kompileru, ale nemusíme měnit čtení ve virtuálním stroji, pač tomu bude záležet jen na tom aby načetl platné číslo sekce a sekci už potom hravě přečte. Můžeme tak nejdřív uložit třeba informace o funkcích, pak tabulku konstant a poslední kódový segment. Nebo můžeme zapsat první tabulku konstant, pak kódový segment a poslední informace o funkcích. Nyní se můžeme podívat na struktury pro uchování popsaných informací. Všechny struktury i čísla sekcí jsou definovány v souboru scriptheaders.h: `#define FUNCTION_ID 0 //sekce s informacemi o lokalni funkci #define CODE_ID 1 //sekce pro kodovy segment #define CONSTANTS_ID 2 //sekce pro tabzulku konstant #define IMPORT_ID 3 //sekce s informacemi o importovane funkci //typy konstant #define INT_CONST 0 #define ZSTRING_CONST 1 #define DOUBLE_CONST 2 #define VOID_TYPE 3 //struktura pro ulozeni informaci o importovane externi funkci struct IMPORT { char* name; //jmeno funkce char* signature; //podpis funkce char* library; //knihovna z ktere funkce pochazi char type; //typ vracene hodnoty }; //hlavicka funkce struct FUNCTION_HEADER { char* name; //jmeno funcke unsigned short inputs; //pocet vstupnich parametru unsigned short ouputs; //vracenych hodnot, bud 0 nebo 1 unsigned short localsLimit; unsigned short stackLimit; unsigned int startCode; //adresa do kodoveho segmentu kde kod funkce zacina unsigned int endCode; //odresa do kodoveho segmentu kde kod funkce konci }; //struktura predstavujici konstantu struct CONSTANT { char type; //typ konstanty union { int intval; //misto pro ulozeni integeru char* str; //misto pro ulozeni retezce double doubleval; //misto pro ulozeni double } val; bool operator == (CONSTANT& right) { if ((type == INT_CONST) && (right.type == INT_CONST)) { return (val.intval == right.val.intval) ? true : false; } else if ((type == DOUBLE_CONST) && (right.type == DOUBLE_CONST)) { return (val.doubleval == right.val.doubleval) ? true : false; } else if ((type == ZSTRING_CONST) && (right.type == ZSTRING_CONST)) { return (strcmp(val.str,right.val.str) == 0) ? true : false; } else return false; } };` ### Assembling Nejvhodnější překlad je sestavování a když už tento proces ve škole nazývali česky, bylo to právě tohle slovo. Není to nic těžkého, vlastně jde jen o zpracování souboru a to už každý z vás určitě dělal :) Připoměňme si, jaké soubory budeme zpracovávat: `.function main(0) .locals_limit 2 .stack_limit 3 ldc_int 5 store 0 ldc_int 4 store 1 load 0 load 1 if_cmpgt true_2 ldc_int 0 goto stop_3 true_2: ldc_int 1 stop_3: ifeq else_0 load 1 dup store 0 pop goto stop_1 else_0: load 0 dup store 1 pop stop_1: .endf` To je soubor který vznikne kompilací tohoto testového skriptu: `main() { a = 5; b = 4; if (a > b) a = b; else b = a; }` Žádný složitý skript, že :) Ale jako ukázku jsem ho použil záměrně, protože se v emitovaném souboru nacházejí místa, které jste nemohli vidět u příkladu Hello World a to jsou zvýrazněná návěští. To mi dělalo největší problém, když jsem se snažil pochopit tuto část kompileru, když jsem procházel kód z kterého jsem se učil a následně to sám psal. V podobě assembler kódu vidíme, které instrukce kam skákají. Daná místa jsou označena návěštími :) Instrukce, které provádějí skoky, ať už podmíněné či ne, mohou v kódu skákat vpřed i vzad. Pokud by skákali jenom vzad, bylo by to pro nás jednoduché, protože bychom vždy načetli nejdřív návěští (tudíž si můžeme zapamatovat jeho pozici) a až někdy později bychom našli instrukci, která na dané návěští skáče a nebyl by pro nás problém doplnit zapamatovanou pozici (adresu) v kódu (protože zpracováváme soubor od začátku do konce!) :) Ale se skoky vpřed je to složitější :( Tam je to naopak, vždy nejdřív načteme instrukci skoku a návěští kam skáče až někdy později. V době, kdy načteme instrukci, nemůžeme ještě vědět adresu kam má skočit, protože nevíme kolik instrukcí "je napsáno" mezi instrukcí skoku a návěštím kam skáče :) Taky již víme, že různé instrukce mohou být různě dlouhé, čili že některé zaberou různý počet bajtíků :) Tak co s tím? Řešení je celkem snadné. Budeme zpracovávat soubor od začátku do konce. Vytvoříme si dvě pole. Do jednoho budeme ukádat názvy návěští a jejich adresu v kódu - můžeme mu říkat pole "návěští". Pokud načítáme návěští, jeho pozici, adresu v kódu už známe! Do druhého pole budeme ukládat názvy návěští a adresu instrukce, která se na něj odkazuje - říkejme mu pole "děr". Přesněji řečeno, bude to adresa operandu instrukce skoku, která se na návěští odkazuje, která na něj skáče. Vím, příšerná věta, ale věřím že za chvíli to bude jasné. Než to však dovysvětlím, musím ještě poznamenat jednu věc. Řekl jsem, že v kódovém segmentu budou uložena těla všech funkcí v daném skriptu. V různých funkcích můžeme mít ale stejná jména návěští, čili návěští budeme muset nějak upravit, abychom při ukládání návěští do jednoho či druhého pole měli vždy jednoznačné návěští k dané adrese v kódu. To uděláme jednoduše tak, že před návěští připojíme ještě jméno funkce, ve které se nachází. To je snadno zjistitelné. Pokud bychom se podívali na příklad, tak návěští true_2 si uložíme do pole jako main(0)_true_2. Jak jsem tedy napsal, budeme zpracovávat soubor od začátku do konce. Když načteme návěští, vytvoříme nové jednoznačné návěští a společně s jeho adresou ho uložíme do pole "návěští". Pokud načteme instrukci nějakého skoku, převedeme ji na její bajtový kód a uložíme do kódového segmentu. Teď si zapamatujeme aktuální pozici v kódovém segmentu! Každá instrukce skoku má parametr, který určuje kam skákat a tím je právě návěští (adresa v kódu). Sestavíme jednoznačné návěští stejně jako v prvním případě. Do pole "děr" si uložíme návěští a zapamatovanou pozici. Do kódového segmentu pak vložíme čtyři nulové bajty, bajty s hodnotou nula. Adresa v kódu segmentu je uložena v integer proměnné a ta je velká 4 bajty, proto 4 bajty. Tím nám v kódovém segmentu vzniklo místo pro pozdější doplnění adresy, kam se má skákat. A pokračujeme ve zpracovávání souboru. Až celý soubor zpracujeme, budeme mít celý kódový segment vytvořený a nic nám nebrání v tom, abychom k instrukcím skoku doplnili cílové adresy skoků, které už teď musíme všechny znát! Stačí jen projít seznam "děr" a na příslušné pozice v kódu zapsat přislušné adresy ze seznamu "návěští". Díky tomu, že jsme u každé instrukce skoku vložili čtyři prázdné bajty pro pozdější doplnění adresy, si ani nic nepřepíšeme :) Tedy pokud budeme správně počítat :) Nyní se můžeme podívat na strukturu, která v sobě uchovává názvy návěští a jejich adresy a na třídu CLabelsList která slouží jako pole, seznam pro uložení většího počtu adres s návěštími. Definované jsou v souboru assembler.h, ještě se třídou CAssembler a implemntované jsou v souboru assembler.cpp :) assembler.h: `//**************************************************************************************************************** //Struktura do ktere se ulozi adresa navesti //**************************************************************************************************************** struct LABEL_ADRESSES { char* unique_labelname; //unikatni identifikator, jmeno navesti unsigned int label_offset; //offset, adresa navesti bool operator == (char* right) //operator pro porovnani { return (strcmp(unique_labelname,right) == 0) ? true : false; } }; //**************************************************************************************************************** //trida predstavujici seznam adres a navesti //**************************************************************************************************************** class CLabelsList { private: std::vector m_List; public: HRESULT AddLabel(char* uniquename,int iOffset); LABEL_ADRESSES* GetLabel(char* uniquename); int GetLabelAdress(char* uniquename); int Contains(char* uniquename); unsigned int Size(); LABEL_ADRESSES* operator [] (unsigned int index); ~CLabelsList(); };` Nejsou to složité třídy. Třída CLabelsList má jen metody, které využijeme. AddLabel přidá návěští do seznamu, Getlabel vrátí položku seznamu, která je reprezentována strukturou LABEL_ADRESSES, podle jména návěští, GetLabelAdress vrátí adresu, pozici návěští v kódovém segmentu a metoda Contains se používá ke zjištění toho, zda dané návěští je v seznamu. Na implementaci metod se můžete podívat do zdrojového souboru, není tam nic čím bychom se tady museli zabývat, jen práce s polem :) Podíváme se raději na třídu CAssembler a na to jak se soubor s assembly kódem překládá do finální binární podoby. Třída CAssembler má jen jednu veřejnou metodu a tou je, jak už známe z dřívějška, metoda Process, která má jeden parametr a to je jméno souboru, který má zpracovat. Jméno výstupního souboru se generuje automaticky. Podívejme se tedy na nejdůležitější část metody Process: `char* token = getToken(m_inputFile); //precteni symbolu ze vstupniho souboru while (token) { //v teto chvili se ocekava jen symbol .function, ze ktereho by se mely skripty skladat, nebo symbol .import //jiny symbol je v tuto chvili neplatny if (strcmp(token,token_function) == 0) processFUNCTION(); else if (strcmp(token,token_import) == 0) processIMPORT(); else theLog.ReportError(line,"Illegal top-level token '%s' in source file: '%s'\n",token,pFile); token = getToken(m_inputFile); } //doplneni adres navesti k instrukcim skoku processHoles(); //vypis tabulky konstant WriteConstants(); //vypis kodoveho segmentu WriteCodeSegment();` Než začne smyčka, která zpracuje celý skript, načte se první symbol. Hlavní smyčka očekává že přečte jen symboly .function nebo .import. Ostatní symboly už spadají pod tyto zmíněné a jsou zpracovány funkcemi, které se volají pro jmenované dva symboly, tedy processFUNCTION a processIMPORT. Pokud hlavní smyčka načte něco jiného, je to v téhle verzi Universal Scriptu neplatný symbol a chybová hláška se vypíše do logu. První funkce má za úkol zpracovat funkce lokální, tedy ty, které jsou napsané v samotném skriptovacím jazyce. Druhá funkce má pak na starost funkce importované. Po skončení hlavní smyčky je celý soubor zpracovaný, ale nic kromě definic funkcí ještě není uloženo na disku. Kódový segment je uložen v paměti, protože ještě čeká na doplnění adres návěští k instrukcím skoku. To je také první, co se provede po skončení cyklu :) Následně už víme všechno a nic nebrání tomu zapsat to všechno do binárního souboru, tedy to, co tam ještě nemáme a to jsou konstanty a kódový segment. Nyní se můžeme podívat na funkci processFUNCTION: `//**************************************************************************************************************** //Funkce pro zpracovani funkce //**************************************************************************************************************** void CAssembler::processFUNCTION() { FUNCTION_HEADER* fh = new FUNCTION_HEADER; char id; char* token = NULL; char* tmp = NULL; int iparam = 0; //nulovani struktury memset(fh,0,sizeof(FUNCTION_HEADER)); fh->startCode = m_iCurrPositionInCode; //ulozeni adresy kde funkce zacina //musime nacist jmeno funkce token = getToken(m_inputFile); tmp = token; //docasne ulozeni ukazatele //pocitame dokud nenajdeme (, kde jsou parametry, treba fce min(2), tj min, dva parametry for (tmp; *tmp != '(';tmp++); //ted mame v end pozici kde konci jmeno a je zavorka( //nacteni poctu argumentu tmp++; char numArguments[128]; int index = 0; while(*tmp != ')') { numArguments[index++] = *tmp; tmp++; } numArguments[index] = 0; fh->inputs = atoi(numArguments); //ted se rozhodne kolik ma vystupnich parametru, jeden nebo zadny if (*(++tmp) == '1') fh->ouputs = 1; else fh->ouputs = 0; fh->name = token; //ulozeni jmena fce m_CurrFuncName = token; do { token = getToken(m_inputFile); //precteni symbolu ze souboru if (IsLabel(token)) //pokud nacteny symbol je navesti { token[strlen(token) - 1] = 0; //zrus dvojtecku na konci navesti m_LabelsPositions.AddLabel(stringConcat(m_CurrFuncName,"_",token,NULL),m_iCurrPositionInCode); //uloz adresu navesti do seznamu } else if (strcmp(token,token_locals_limit) == 0) //symbol udava lokalni limit funkce { token = getToken(m_inputFile); iparam = atoi(token); fh->localsLimit = iparam; } else if (strcmp(token,token_stack_limit) == 0) //symbol udava limit zasobniku funkce { token = getToken(m_inputFile); iparam = atoi(token); fh->stackLimit = iparam; } else if (strcmp(token,token_end_function) == 0) { ; //nic nedelej } else processCode(token); //assembly tela funkce } while (token && (strcmp(token,token_end_function) != 0)); fh->endCode = m_iCurrPositionInCode; //ulozeni adresy kde funkce konci //ulozeni ziskanych informaci do souboru id = FUNCTION_ID; //oznaceni ze se jedna o blok definice funkce fwrite(&id,sizeof(char),1,m_binFile); WriteZString(fh->name,m_binFile); fwrite(&(fh->inputs),sizeof(unsigned short),1,m_binFile); fwrite(&(fh->ouputs),sizeof(unsigned short),1,m_binFile); fwrite(&(fh->localsLimit),sizeof(unsigned short),1,m_binFile); fwrite(&(fh->stackLimit),sizeof(unsigned short),1,m_binFile); fwrite(&(fh->startCode),sizeof(unsigned int),1,m_binFile); fwrite(&(fh->endCode),sizeof(unsigned int),1,m_binFile); theLog.TraceF("Function %s, inputs: %i, outputs: %i, code size: %i ",fh->name,fh->inputs,fh->ouputs,fh->endCode - fh->startCode); }` Dobře, možná je trochu delší, ale delší neznamená složitá :) V první části, než se dostaneme k cyklu, jen načítáme jméno funkce a zjišťujeme, kolik má parametrů (číslo v závorce). Celé jméno funkce si uložíme do struktury, která uchovává informace o funkci a také do proměnné m_CurrFuncName. Tato proměnná je v dalších funkcích použita k sestavení jedinečného návěští, o kterém jsem psal před několika řádky, možná odstavci :) V cyklu potom čteme jednotlivé symboly ze souboru. Nejdřív zjišťujeme, jestli se jedná o návěští a pokud ano, uložíme si jedinečné návěští i s adresou do seznamu návěští (m_LabelsPositions). Pokud symbol není návěští, může to být ještě jeden ze tří symbolů specifických pro funkci, a to .locals_limit, .stack_limit nebo .endf. Každý případ hlídá jedna rozhodovací konstrukce :) V prvních dvou případech si uložíme zjištěné hodnoty a v posledním případě neuděláme nic, protože se jedná o konec funkce a v tom případě cyklus končí. Poslední možný případ, čemu se může přečtený symbol rovnat, je nějaká instrukce a na tu zavoláme funkci processCode, která zjistí kód instrukce a ten zapíše do kódového segmentu i s případnými parametry. Po skončení cyklu je v kódovém segmentu tělo celé funkce. Na konec zapíšeme všechno co o funkci víme do výstupního binárního souboru. Funkce processIMPORT, která zpracovává importované funkce, obsahuje podobný kód jako tato funkce, jen nevytváří nic v kódovém segmentu, pač tělo funkce není pro nás známé. Na implementaci se podívejte do zdrojáku :) Tady se podíváme radši na funkci processCode, která vytváří kódový segment. Nebo aspoň na nějaké její části, protože je taky docela dlouhá :) `. . . //musime projit vsechny moznosti prislusejici konstantam v opcodes.h if (strcmp(token,instruction_nop) == 0) AddCode(nopCI); else if (strcmp(token,instruction_mul) == 0) AddCode(mulCI); . . . else if (strcmp(token,instruction_lgoto) == 0) { AddCode(lgotoCI); //pridej kod goto strparam = getToken(m_inputFile); //precti parametr m_LabelsHoles.AddLabel(stringConcat(m_CurrFuncName,"_",strparam,NULL),m_iCurrPositionInCode); //pridej do seznamu diru AddHoleForLabel(); //udelej v kodu misto pro doplneni adresy } . . . else if (strcmp(token,instruction_load) == 0) { AddCode(loadCI); strparam = getToken(m_inputFile); iparam = atoi(strparam); AddIndex16((unsigned short)iparam); } . . . else if (strcmp(token,instruction_ldc_int) == 0) { AddCode(ldc_intCI); strparam = getToken(m_inputFile); //precteni parametru iparam = atoi(strparam); //konstanta ktera se ma nacist AddIndex32(m_Constants.GetIntNumber(iparam)); //index do tabulky konstant } . . .` První typ instrukcí je nejjednodušší. Nemají žádné parametry a stačí jen přidat jednobajtový kód instrukce do kódového segmentu. Druhý typ jsou instrukce podmíněných a nepodmíněných skoků. Jako v prvním případě se nejdřív do kódového segmentu uloží kód instrukce. Pak se načte návěští a přidá se do seznamu "děr" (m_LabelsHoles) i s aktuální pozicí v kódu. Poslední příkaz přidá místo pro budoucí doplnění adresy, jak jsem o tom psal :) Třetí typ instrukcí jsou instrukce které vybírají a ukládají proměnné z/do zásobníku. V příkladu je instrukce load. Jak jsem psal už někde daleko dříve :), k proměnným přistupujeme také pomocí indexů, které jsou uloženy už v assembly kódu, čili stačí je jen přečíst a uložit za instrukci do kódového segmentu pomocí funkce AddIndex16. Možná už dřív jsem psal, že na indexovaání proměnných budeme používat 16 bitový integer bez znaménka. Jeho rozsah by měl stačit pro běžný počet proměnných ve skriptu :) Kdyžtak není nic jednoduššího než to tady přepsat na 32 bitový integer :) Posledním typem jsou instrukce jako ldc_string, které pracují s konstantami. O těch jsme si řekli, že by bylo fajn je mít uložené v nějaké tabulce. Index konstanty je už 32 bitový a po vložení kódu instrukce do kódového segmentu je index konstanty vložen funkcí AddIndex32. Na stejném řádku se i ptáme tabulky konstant na index načtené konstanty a tabulka konstant se podívá, jestli už konstantu v sobě má, a pokud nemá, tak si ji k sobě přidá. Každopádně ale vrátí index konstanty v tabulce konstant :) Poslední funkcí kterou si ukážeme je processHoles: `//**************************************************************************************************************** //Funkce pro zpracovani der do kterych se maji ulozit adresy navesti //**************************************************************************************************************** void CAssembler::processHoles() { unsigned int labelscount = m_LabelsHoles.Size(); //zjisti pocet der unsigned int adress = 0; //pomocna promenna pro adresu for (unsigned int i = 0; i < labelscount; i++) //projdi cely seznam der { LABEL_ADRESSES* pLabel = m_LabelsHoles[i]; //tady se zeptame na adresu navesti podle unikatniho jmena navesti adress = (unsigned int)m_LabelsPositions.GetLabelAdress(pLabel->unique_labelname); //doplnime ziskanou adresu do priparvene diry *((unsigned int*)(&m_pByteCode[pLabel->label_offset])) = adress; } }` Jediné co na téhle funkci může vypadat děsivě jsou ty hvězdičky v posledním příkazu cyklu :) Dělá to přesně to, co jsem popisoval v teorii někde nahoře. Prochází to pole všech "děr" v kódu a z pole "návěští" to zjistí adresu návěští, která se má doplnit do kódového segmentu, což udělá ten poslední řádek s hodně hvězdičkama(no jenom s dvěmi :)). ### Závěr: Myslím, že v assembly.cpp už není nic co by vám mělo dělat větší problémy a co by jste nerozluštili bez toho, abych to tady víc rozepisoval. To hlavní jsme si řekli a zbytek jsou jen podpůrné funkce a zápisy do souborů, které můžete s klidem opsat :) Nyní je myslím na místě gratulace, protože máte hotový kompiler pro vlastní skriptovací jazyk. Dobrá práce! Část 8 Část 10