編譯器設(shè)計(jì)與實(shí)現(xiàn)

1、編譯器設(shè)計(jì)與實(shí)現(xiàn)第1頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二一、概述1、編譯器各階段2022/9/27詞法分析器語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器錯(cuò)誤處理器符號表管理器源程序目標(biāo)程序第2頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二2、編譯器各階段的分組前端：依賴于語言并很大程度上獨(dú)立于目標(biāo)機(jī)器。一般包括語法分析、詞法分析、符號表的建立、語義分析、中間代碼生成以及相關(guān)錯(cuò)誤處理。后端：依賴于目標(biāo)機(jī)器的階段或某些階段的某些部分。一般來說，后端完成的任務(wù)不依賴于源語言而只依賴于中間語言。主要包括代碼優(yōu)化、代碼生成以及相關(guān)的錯(cuò)誤處理和符號表操作。202

2、2/9/27第3頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二二、符號表符號表是編譯器保存信息的中心庫，編譯器的各部分通過符號表進(jìn)行交互，并訪問符號表中的數(shù)據(jù)符號。符號表把各種名字映射到符號集合。常量、標(biāo)識符和標(biāo)號都是名字，不同名字有不同的屬性。符號管理不僅要處理符號本身，還管理符號的作用域。2022/9/27第4頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二1、符號的表示struct symbol char *name; /名稱int scope;/作用域Coordinate src;/在源程序中位置Symbol up;/連接符號表中上一個(gè)符號List uses;/可

3、保存一個(gè)Coordinate列表，表示使用情況int sclass;/擴(kuò)展存儲(chǔ)類型/符號標(biāo)記Type type;/如變量、函數(shù)、常量、結(jié)構(gòu)或聯(lián)合等信息floatref;/被引用的粗略次數(shù)union /聯(lián)合u為標(biāo)號、結(jié)構(gòu)、聯(lián)合、枚舉、常量、全局/和靜態(tài)變量提供附加信息 u;/Xsymbol x;/由后端處理，如為變量分配寄存器/為調(diào)試器產(chǎn)生數(shù)據(jù)信息2022/9/27第5頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二1、符號的表示scope域：enum CONSTANTS=1, LABELS, GLOBAL, PARAM, LOCAL ;第k層中聲明的局部變量其scope域等于LOCA

4、L+k。src域：typedef struct coord char *file;unsigned x, y; Coordinate;file指名包含該符號定義文件名，y和x表示出現(xiàn)的行號及行中位置。sclass域：符號擴(kuò)展類型可以是AUTO、REGISTER、STATIC或EXTERN等首字母大寫的類型表示全小寫類型的指針，如Symbol。2022/9/27第6頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二2、符號表的表示externTableconstants;externTableexternals;externTableglobals;externTableidentifi

5、ers;externTablelabels;externTabletypes;struct table intlevel; /同symbol中scope域Table previous;/符號表鏈表，指向level-1的表struct entry struct symbol sym;struct entry *link; *buckets256;/這是一個(gè)哈希鏈數(shù)組，方便插入、查找Symbol all;/指向當(dāng)前及其外層所有符號列表的表頭;2022/9/27第7頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二3、符號表舉例int x, y;f(int x, int a)int b;y

6、= x + a*b;if (y 5)int a;y = x + a*b;2022/9/27第8頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二2022/9/273045600000a b x y第9頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二4、符號表的相關(guān)操作查找和建立標(biāo)識符Symbol install(const char * name, Table * tpp, int level, int arena); Symbol lookup(const char *name, Table tp);標(biāo)號:與標(biāo)識符相似，但不涉及作用域常量：這些符號保存在constants表

7、中產(chǎn)生變量：用于產(chǎn)生靜態(tài)變量保存字符串等2022/9/27第10頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二三、代碼生成接口這一章內(nèi)容定義了與目標(biāo)機(jī)器無關(guān)的前端和與目標(biāo)機(jī)器相關(guān)的后端之間的接口。Lcc接口包括一些共享數(shù)據(jù)結(jié)構(gòu)、18個(gè)函數(shù)和包括36個(gè)操作符的語言。該語言用于將可執(zhí)行代碼從源程序生成dag（有向無環(huán)圖）。共享數(shù)據(jù)結(jié)構(gòu)可供前后端共享，但某些域?yàn)橐欢怂接小ymbol就是一個(gè)共享數(shù)據(jù)結(jié)構(gòu)。2022/9/27第11頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二1、類型度量typedef struct metrics unsigned char size, ali

8、gn, outofline; Metrics;size:類型的大小；align：對齊字節(jié)數(shù)；outofline：控制相關(guān)類型的常量的放置。為1時(shí)，不出現(xiàn)在dag中，存于靜態(tài)變量中。Metrics charmetric;Metrics shortmetric;Metrics intmetric;Metrics floatmetric;Metrics doublemetric;Metrics structmetric;2022/9/27第12頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二2、接口記錄typedef struct interface Xinterfacex;Interfa

9、ce;lcc為每一種目標(biāo)機(jī)器形成一個(gè)獨(dú)有的接口實(shí)例。x域是對interface的擴(kuò)展，后段使用它存放與目標(biāo)及其相關(guān)的接口數(shù)據(jù)和函數(shù)，對后端私有。2022/9/27第13頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二3、dag操作可執(zhí)行代碼用dag來描述。函數(shù)體是用dag組成的序列或森林。每個(gè)dag都可以同過gen函數(shù)傳給后端。dag節(jié)點(diǎn)struct node short op;short count; Symbol syms3;Node kids2;Node link;Xnode x;2022/9/27第14頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二3、dag操作o

10、p域存放dag操作符。dag操作符后綴表示操作數(shù)類型：enum F=FLOAT,I=INT,U=UNSIGNED,P=POINTER,V=VOID,B=STRUCT;如CNST，有變體CNSTI、CNSTU、CNSTP等。CNST = 1u.sym;return INT; goto id;第26頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二4、標(biāo)識符識別case h: case j: case k: case m: case n: case o:case p: case q: case x: case y: case z:case A: case B: case C: case D

11、: case E: case F:case G: case H: case I: case J: case K:case M: case N: case O: case P: case Q: case R:case S: case T: case U: case V: case W: case X:case Y: case Z:id:if (limit - rcp = 6 & prect = 11 & prect = 13) int op = t;t = gettok();if (operop = ASGN)p = asgntree(ASGN, p, value(expr1(0);else r

12、eturn p2022/9/27第32頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二條件表達(dá)式：conditonal-expression:binary-expression? expression : conditional-expressionstatic Tree expr2(void) Tree p = expr3(4);if (t = ?) Tree l, r;Coordinate pts2;if (Aflag 1 & isfunc(p-type)warning(%s used in a conditional expressionn,funcname(p);p = po

13、inter(p);t = gettok();pts0 = src;l = pointer(expr(:);pts1 = src;r = pointer(expr2(); return p;2022/9/27第33頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二另有二元表達(dá)式、一元表達(dá)式、后綴表達(dá)式和基本表達(dá)式。表達(dá)式分析多是用遞歸和大量switch語句實(shí)現(xiàn)。在編譯領(lǐng)域用一個(gè)分析函數(shù)代替n個(gè)函數(shù)處理n級優(yōu)先是非常流行的。關(guān)于表達(dá)式的分析還包括表達(dá)式語義的分析，如類型檢查轉(zhuǎn)換、函數(shù)調(diào)用分析等各種操作。2022/9/27第34頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二2、語

14、句分析代碼的表示：表達(dá)式首先被編譯為分析樹然后轉(zhuǎn)化為dag。每個(gè)函數(shù)的dag在代碼表中被串起來，代碼表表示了函數(shù)的代碼。code結(jié)構(gòu)：struct code enum Blockbeg, Blockend, Local, Address, Defpoint, Label, Start, Gen, Jump, Switch kind;Code prev, next;union u;2022/9/27第35頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二語句的識別：void statement(int loop, Swtch swp, int lev) float ref = refin

15、c;if (Aflag = 2 & lev = 15)warning(more than 15 levels of nested statementsn);switch (t) case IF: ifstmt(genlabel(2), loop, swp, lev + 1); break;case WHILE: whilestmt(genlabel(3), swp, lev + 1); break;case DO: dostmt(genlabel(3), swp, lev + 1); expect(;); break; refinc = ref;expect(;)break;2022/9/27

16、第36頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二if語句的識別：if expression = 0 goto Lstatement1 goto L+1L:statement2L1：static void ifstmt(int lab, int loop, Swtch swp, int lev) t = gettok();expect();/判斷if后的（definept(NULL);walk(conditional(), 0, lab); /包含listnode函數(shù)生成dag并加入refinc /= 2.0; /森林，把入口加入代碼表.同時(shí)根statement(loop, sw

17、p, lev);/據(jù)接過設(shè)置flab，tlabif (t = ELSE) branch(lab + 1);t = gettok();definelab(lab);statement(loop, swp, lev);if (findlabel(lab + 1)-ref)definelab(lab + 1); elsedefinelab(lab);2022/9/27第37頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二在循環(huán)、switch、goto語句中都用到了標(biāo)號和跳轉(zhuǎn)，標(biāo)號使通過definelab函數(shù)定義的，而跳轉(zhuǎn)通過branch函數(shù)生成。除語句識別外，還有聲明的識別。聲明的識別非常

18、復(fù)雜，c語言中聲明的形式很多，處理時(shí)大量的相互遞歸調(diào)用。經(jīng)過前端的分析后，將源程序轉(zhuǎn)化為dag，并添加進(jìn)代碼表。2022/9/273、小結(jié)第38頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二六、中間代碼生成編譯器的后端通過function接口函數(shù)調(diào)用gencode和emitcode來遍歷代碼表。walk和listnodes函數(shù)操作處理dag森林。newnode函數(shù)為節(jié)點(diǎn)分配內(nèi)存并用它的參數(shù)只來初始化節(jié)點(diǎn)的域。listnode還負(fù)責(zé)刪除公共子表達(dá)式。2022/9/27第39頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二1、構(gòu)建節(jié)點(diǎn)Node listnodes(Tree t

19、p, int tlab, int flab) Node p = NULL, l, r;int op;if (tp = NULL)return NULL;if (tp-node) /node標(biāo)識listnode訪問過的樹return tp-node;if (isarray(tp-type)op = tp-op + sizeop(voidptype-size);elseop = tp-op + sizeop(tp-type-size);switch (generic(tp-op) tpnode p;return p;2022/9/27第40頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二

20、2、控制流最簡單的一元和二元操作加入結(jié)點(diǎn)表，但是并不會(huì)出現(xiàn)在根中。賦值等操作可以用這種情況解決。 要改變控制流需要跳轉(zhuǎn)。case JUMP: l = listnodes(tp-kids0, 0, 0); list(newnode(JUMP+V, l, NULL, NULL); reset(); break;2022/9/27第41頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二static void list(Node p) if (p & p-link = NULL) if (forest) p-link = forest-link;forest-link = p; elsep-l

21、ink = p;forest = p;2022/9/27forest是一個(gè)循環(huán)鏈表，不為空則指向鏈表最后一個(gè)節(jié)點(diǎn)，為空則將其初始化，link域可以表示根結(jié)點(diǎn)。第42頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二case LT: /LT代表大于轉(zhuǎn)移，是接口dag標(biāo)識符 l = listnodes(tp-kids0, 0, 0); r = listnodes(tp-kids1, 0, 0); if (tlab) list(newnode(generic(tp-op) + opkind(l-op), l, r, findlabel(tlab); else if (flab) switch

22、 (generic(tp-op) case EQ: op = NE; break;case NE: op = EQ; break; case GT: op = LE; break; case LT: op = GE; break; case GE: op = LT; break; case LE: op = GT; break; default: assert(0); list(newnode(op + opkind(l-op), l, r, findlabel(flab); if (forest & forest-syms0) forest-syms0-ref+; break;2022/9/

23、27第43頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二2022/9/27ai&ai+bi0&ai+bikids1作為一個(gè)addr。最后emitasm生成一個(gè)換行符。2022/9/27第54頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二3、寄存器的分配從上節(jié)我們可以看出，代碼發(fā)送器可以生成匯編代碼，但是匯編代碼中的寄存器是如何分配的？寄存器分配包括兩個(gè)內(nèi)容：分配：決定哪些值占用寄存器指派：為每個(gè)值指派特定的寄存器2022/9/27第55頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二2022/9/27例程名作用 linearize為輸出一棵指令樹排序 rall

24、oc為一條指令釋放和分配寄存器 putreg釋放一個(gè)忙寄存器 getreg發(fā)現(xiàn)和分配一個(gè)寄存器 askreg發(fā)現(xiàn)和分配一個(gè)空寄存器 askfixedreg嘗試分配一個(gè)制定的寄存器 spillee標(biāo)記一個(gè)最遠(yuǎn)使用寄存器溢出 spill溢出一個(gè)或多個(gè)寄存器 spillr溢出一個(gè)寄存器 genspill產(chǎn)生代碼溢出一個(gè)寄存器 genreload產(chǎn)生代碼重載一個(gè)被溢出的寄存器 reprune當(dāng)genreload更新x.kids后，更新kids第56頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二在后端選擇指令并將子指令從樹中分離出來，linearize采用前序遍歷分離的樹，并按照最后執(zhí)行的順

25、序鏈接指令。gen再將每條指令傳遞給ralloc函數(shù)，ralloc一般首先調(diào)用putreg來釋放不再被其子節(jié)點(diǎn)使用的寄存器，然后調(diào)用getreg函數(shù)為自身分配一個(gè)寄存器。對于臨時(shí)變量，ralloc在首次賦值的時(shí)候?yàn)樗峙湟粋€(gè)寄存器，在最后一次使用的時(shí)候釋放該機(jī)存器。2022/9/27第57頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二寄存器狀態(tài)的跟蹤unsigned freemask2;unsigned usedmask2;用掩碼表示寄存器的狀態(tài)對于寄存器r：int n = r-set;r-mask & freemaskn 為0表示寄存器忙2022/9/27第58頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二寄存器分配：寄存器分配器對森林進(jìn)行三遍掃描:第一遍對所有使用臨時(shí)變量的節(jié)點(diǎn)建立一個(gè)表。該列表指名了臨時(shí)變量節(jié)點(diǎn)的最后一次使用。第二遍對森林的掃描刪去一些用于寄存器復(fù)制的指令，把計(jì)算源寄存器的表達(dá)式重定向，使用目的寄存器。最后一遍掃描為每個(gè)節(jié)點(diǎn)分配寄存器。2022/9/27第59頁，共65頁，2022年，5月20日，20點(diǎn)34分，星期二寄存器的溢出：寄存器溢出是指寄存器分配器用完寄存器時(shí)需要生成代碼來空出一個(gè)忙寄存器，將其值存儲(chǔ)回存儲(chǔ)器中，并將那些未被處理的使用該寄存器的節(jié)點(diǎn)替換成存儲(chǔ)器結(jié)點(diǎn)。存儲(chǔ)器分配用完時(shí)最有選擇是把最遠(yuǎn)使