编译器剖析从1999年在TurboC2 0下第一次用语言写出Hello

前从1999年在TurboC2.0下第一次用C语言写出 行当里也混了近15年。相信所有上机写过 盘敲进去的不过是一个个普通的英文字符，C编译器是如何神奇地发现哪一行出现了什么原理》课程后就已脱颖而出，比如大牛Linus和ChrisLattner，前者大学时就开启了他的Apple公司已经不动声色地把公司的Object-C编译器从GCC转成了LLVM和Clang，各位 背后站着的仍然是CharisLattner和LLVM。私下偷偷复印那本后来被称为旷世奇书的《莱昂Unix源代码分析》。其实，真正旷世之作的和Linux源代码就毫无保留地躺在那。冲动的曾经兴奋载这些源代码，但面对这的原型往往是不太复杂的，就如早期UnixC编译器，而这些原型往往就是最精如果我们要分析的是开源的相对完整的C编译器源代码，而不是一个教学用的toy，并编译器，一个是UCC编译器。如果我们还希望代码结构清晰，且函数名等能望文生义，能直接与C语言的文法吻合，不必去猜测这个函数名是哪几个单词的缩写，那UCC会更胜一筹。当然，UCC的原作者WenjunWang( )或多或少地受到LCC编译器的UCC就如一颗被遗落在角落的珍珠，渐渐地蒙上了尘埃。一万行左右的代码量，UCC就能实现一个基本完整的C编译器，虽然后端只面向32位的X86平台。UCC没有如LCC那样地可变目标，既可生成MIPS，也可生成SPARC和X86代码。虽然偶有BUG，纵然碧玉有瑕，即便不够知名，但只要把UCC这只麻雀解剖清楚，我们已能搞清C编译器是如何工作的，我们已能站在编译器实现的角度来品味那经40余年而愈久愈香的C语言。C和C++语言的相关书籍中，最最经典的如《TheCProgrammingLanguageC++Primer》和《TheC++programminglanguageCC++编译器的最早期注的焦点，UCCLCC在后端优化上都做得不够。不过，站C程序员的角度来看，C编译器的前C编译器与程序员的接口C编译器前端的实现，就能更深刻地理众里寻她千，蓦然回首，SheisC。那我们就启程吧第1章基础知 语言、文法与递 一个较复 由文法到分析 表达式 Declaration 语句 UCC编译器预 UCC的使 UCC 结合C语言来学汇 汇编语言简 整数运 浮点数的算术运 浮点数之间的比较操 指针、数组和结构 第2章UCC编译器的基本模 词法分 UCC编译器的内存管 C语言的类型系 UCC编译器的符号表管 第3章语法分 C语言的表达 条件表达式和二元表达 一元表达式和基本表达式 C语言的语句 C语言的外部 Declaration和函数定义FunctionDefinition 与Declaration有关的几个非终结 说明符DeclarationSpecifiers和符 第4章语义检 语义检查简 表达式的语义检 表达式的语义检查简 数组索引表达 基本表达 函数调用的语义检 成员选择运算 相容类型Compatible 一元运算符表达式的语义检 二元运算符、赋值运算符和条件表达式的语义检 对语句Statement的语义检 对的语义检 类型结构的构 结构体的类型结 结构体和数组的初始 内部连接和外部连 对外部进行语义检查的临门一 第5章中间代码生成及优 中间代码生成简 表达式的翻 布尔表达式的翻 再论符号symbol与公共子表达 通过“偏移”数组元素和结构体成 后缀表达式的翻 赋值表达式的翻 一元表达式及其他表达式的翻 语句的翻 If语句和复合语句的翻 Switch语句的翻 UCC编译器的优 删除无用的临时变量和优化跳转目 基本块的合 第6章汇编代码生 汇编代码生成简 寄存器的管 中间指令的翻 由中间指令产生汇编代码的主要流 为算术运算产生汇编代 为跳转指令产生汇编代 为函数调用与返回产生汇编代 为类型转换产生汇编代 参考文 语言、文法与递

1础知我们对语言这个概念再熟悉不过了，汉语和英语等都是自然语言。而C和C++语言是编程语言，若用更专业的术语，则这些编程语言被称为Formal 别。C和C++等编程语言之所以被称为形式语言，原因在于这些语言的产生过程是先有正式的穷集合，我E＝{x|x2n,n是非负整数}这样的描述法。CC源代码就是这个集合里的一个元素，合法的C源代码有无穷多个，那我们要用什么样的描述方法来表达C语言这个无穷集合？让我们不妨先这个比C语言简单得多的语言。T＝{a,a+a,a+a+a, (1-我们不难发现，上述集合T是由若干个a相加构成，这是个无穷集合，省略号“……”我们就来探索一下有没有更好的表达方法。让我们先把集合T一分为二。T＝ a+a+a,＝ 我们仔细观察其中的{a+a,a+a+a,…..}，越看越觉得这个式子跟TT＝{a} a+{a,a+a,a+a+a,……}＝ a| (1-式子(1-2)告诉我们，Taa+T构成。该式实际上由两个式子构成，TaT aa+11T＝ {a,a+a,a+a+a,….}＝ T a|T (1-式子(1-2)和(1-3)的区别在于，前者的递归出现a+T右侧，而后者的递归定义出T+a{a,a+a,a+a+a,形如(1-2)和(1-3)下a+aTaTT14和1512和13) a+→a+(1- →T+a+(1-图111述子14)psngee串aa言T向为T为+12的T而a和12产即T→a和→a+言T语言T法r r生为图11根T子符文。TTa+Ta1.1.1句一个较复我们先给出一个较复法，该文法描述了一个包含“语句、表达式和”的程Program，如1.2.1所示 if(expression)Statement if(expression)StatementelseStatement while(expression)Statement {StatementListopt} Statement| Expression; Declaration; →AdditiveExpression AdditiveExpression→AdditiveExpression+MultiplicativeExpressionAdditiveExpression→AdditiveExpression-MultiplicativeExpressionMultiplicativeExpression→PrimaryExpressionMultiplicativeExpression→MultiplicativeExpression*PrimaryExpressionMultiplicativeExpression→MultiplicativeExpression/PrimaryExpressionPrimaryExpression→id|num|(Expression)Declaration→intDeclarator→*Declarator|PostfixDeclarator→DirectDeclarator|PostfixDeclarator[num]|PostfixDeclarator(void)DirectDeclarator→id|(Declarator)1.2.1Program按照前面的约定，图1.2.1中的第一个产生式左侧的非终结符Program为文法的开始符{int}

a=b=d=d-}}c=c-}}请于ucc162.2.tar.gz，解压后的文法，其实很多产生式与第1.1节的产生式(1-2)及产生式(1-3)本质上是相同的。 a| (1- a|T (1-例如，以下几个从图1.2.1取出的产生式，如果把AdditveExpression视为T，把MultiplicativeExpression视为a后，就和产生式(1-3)是一样的。如前文所述，产生式(1-3)是四则运算符都是左结合的。所以我们选取形如(1-3)的产生式来表达加法运算。与T所表达的集合类似，AdditiveExpressionMultiplicativeExpression相加构成。换言之，要进MultiplicativeExpression。同理，MultiplicativeExpression由若干个引入的运算符，如&和|等。 →AdditiveExpression+MultiplicativeExpression id|num|(Expression)让我们再来分析图1.2.1中的以下几个与“语句Statement”有关的产生式。由Statement的产生式，我们可知，语if语句、while语句、复合语句及表达式语句构成。而if语句则以if开头，后面紧跟左括号，然后是表达式expression，接着是右括号，之后又是一个语句IfStatement→ if(expression)Statement if(expression)StatementelseStatement →while(expression)Statement →{StatementListopt} Statement 而StatementList对应的产生式实际上形如前面的产生式(1-3)。复合接下来，让我们再来讨论与Declaration相关的产生式，在C语言中，我们通过“声明”表达了 程序员自定义的某个标志符是什么类型”的概念 * |PostfixDeclarator→DirectDeclarator|PostfixDeclarator[num]|PostfixDeclarator(void) 而PostfixDeclarator则再次与产生式（1-3）神似。其产生式实际上告诉我们对应的产生式实际上表达了若干个*后面再跟一个PostfixDeclarator.通过[num]的后缀，我们实际上了一个大小为 的数组，而通过(void)的后缀,们实际上了一个无参的函数。我们知道，在中使用*，实际上是了一个指针。图121，。intaa[30][50],Declaration出发intaa[30][50]30,50numaaid。我们还可以由Declarationint(*cc)[3][5]C的语法，aacc是指向数组的指针。仔细观numnumid实际相当numid的识别列入“词法分析”范畴。通常，分析器指的intC语言的文法也不尽相同。但管中窥豹，我们已可见一斑。如果理表达式在这一节中，我们来讨论如何为图1.2.1中的文法构造分析器。时，我们从基本的26个英文字母入手，然后由英文字母组成各种各样的单词，之后按照语则组成句子，之后是段落，然后是文章。同理，我们要写一个语法分析器来识别图1.2.1文法对应的语言和运算符等。由字母表中的字符，我们可以组成基本的单1231、23这三个数字构成abca、bc3个字母组成。在编译领域，给单词起了一个专门的术Token，其中包含了单词的类型和单词的值。例123456同样是数，但它们的值不一样123abc是不同类型的单词。识别了token之后，我们就可以按照上一节文法所规定的法则去组成合法的、表达 ucc\examples\sc中的代码。其中lexh中的以下结构体描述了与Token相关的类型和值。lex是英文单词lexical的前缀。typedefTokenKindValuelex.cGetToken()Token1.3.16466行，我们7077行完成了对标志符的识别，标志符以字母开头，后面紧跟若干个数字和字母。因为if,elsewhilekeyword也符合标志符的特征，所以我们需要在第77行调用GetKeywordKind函数，判断一下识别出tokens.txttoken7885行，我们实现的是对数的识别，为简单起见，只完成了对十进制整数的识别。在C编译器中，我们要做得更复杂些，需要处理十进制整数、十六进制整数、floatdouble浮点数等。当然，还有许多简单的单词，是由一个字符构成的，例如+、－、*和/R1.3.1下面我们以 。显然，此处对PrimaryExpressionid,num和(expression)这三个候选式。如果当前tokenTK_LPAREN1.3.25760行则去识别产生式PrimaryExpression的候选式(expression)。我们预期接下来的字符串应该是加了一的宏定义，可以看到我们调用的其实就是前文所述的词法分析器GetToken()。 do{curToken=识别左括号之后，由该产生式所制定的规则，我们预期接下来token会构成一个合法的此处只要调Exprssion()即可Expression()函数返回后，我们期望当前终结符是右Expect(TK_RPAREN)中会进行比对，如果不是右括号，则报错；否则取下一个tokentoken。而53-56则是处理遇到标idnum的情况61至63的idnum或者左括号开头。换言之，PrimaryExpression的首符集是{id, 图 在图1.3.2中第54行，我们调用了函数CreateAstNode()创建了一个astNode结点，用于存为TK_NUM，值为123。structastNode的定义如下所示。其中，op用于存放结点的类型，而50这样的表达式，分析到30时，我们会为30构造一个astNode结点，遇到运算符*时，也 点则是运算符所需要的操作数。此处“抽象”反映的token流中提取信息，构造适合我typedefstructastNode{TokenKindop;Valuevalue;structastNode*}*接下来我们就来看看如何处理分析由若干个imaExpeion()相乘或相除构成的乘法表达式utpcaieEpeion。这里，我们把关注的焦点放在了如何实现运算符的左结合和右结合上。例如对于表达式100102而言，如果我们规定除法运算符是左结合的，因为15的第71841010AT100和10on符，则可把当前得到的AT子树作为左操作数，用2棵新的以除法运算符为根结点的T73行我们用的是he循环。而如果规定除法运算法是右结合的，则我们可按图1386100: PrimaryExpression* PrimaryExpression/100/10/2100/10AST，我们要看一下10后面是否还有乘法或除法运算符，如果有，则10要与其右侧的除法运算符先结合。所以先构造出来的AST是10/2，之后再以这棵子100作为左操作数，以除法运算法为根结点，构造一棵适合进行右结合运算的AST。对候选式PrimaryExpression/MultiplicativeExpression的分析过程与上述非终结符PrimaryExpression的分析过程类似，对于候选式中的非终结符，我们直接调用与之对应的同名函数来识别接下来的token串；对于候选式中的终结符，我们判断一下当前读入的token是否与之一致。图1.3.387、9496行实际上就完成了这个1.3.3对100/10/2，如果除法是右结合的，则运算结果为20；而如果除法是左结合的，则运算结果是5。如果定义一个新语言，硬要把除定为右结合，这是和习惯的，是a=b=c是右结合的。1.3.377行和92行，我们还看到了一NewTemp()的函a*b*c为例，如果乘法是左结合的，我们先进行的运算a*b,我们需要把运算结果存到一个临时变量中，之后再用这个临时c进行乘法，结果再存到一个新的临时变量中，如下所示t1=a*bt2=t1*处理完乘除法运算，我们再来看一下加减法运算的处理函数AdditiveExpression()图134uipcavexpeon()都是二元运算符，只是运算符不同而已。我们知道，在C语言中，还有许多类似的二元运可以考虑把对二元运算符的处理归并到一个函数中统一处理。在后续章节分析C编译器的源代码时，我们会在uccucexpc中看到arseinaEpesion()这个函数，C语言中所有的二元运算表达式都由这个处理函数进行分析.5再来看一下图1.3.6中的函数void 地想起了当年在《数据结构》课中那熟悉的二叉树前序、中序和后序遍历。这里，我们对135码。t0=a+bt1=t0*Declaration

图 下面，让我们再看看ucc\examples\sc\decl.c,这里我们要处理的是变量或函数的。 *Declarator |PostfixDeclarator ParameterList,int 我们以”int(*f(int,int,int))[4];”这个看起来复杂一点的为例子，进入命令行，运行以下命令，我们得到的结果是fis:function(int,int,int)whichreturnspointertoarray[4]ofint”，//WindowsD:\src\ucc\examples\sc>nmake-f//Linuxiron@ubuntu:sc$由于我们在这个简单的语言中只引入了int这个基本类型，所以所有的都是以开头的，之后再跟上符ecaaor。在符ecaaor中，我们可以进一步指定要声明的标志符为指针类型、数组类型或者函数类型。如果把*、[]和()看成类型运算符，把nt算表达式，我们希望PU做计算，从而可以得到运算结果；而通过类型表达式，程序员为ecaaor{PostfixDeclarator,*PostfixDeclarator,**PostfixDeclarator,***PostfixDeclarator,而非终结符PostfixDeclarator{DirectDeclarator,DirectDeclarator[num],DirectDeclarator(ParameterList),DirectDeclarator[num][num],DirectDeclarator(ParameterList)(ParameterList),DirectDeclarator[num](ParameterList),DirectDeclarator(ParameterList)[num],}在这里，我们可以发现 f(int)(int)竟然也是一个符合文法的，因为我们完全可DelcarationGCC、VisualStudio、ClangUCC都会给我们一个大大的错误提示，intf(int)(int)是个的，因为这个函数企图把函数作为返回值。在ucc给出的错误提示中，我们看到了(declchk.c,629)，这代表着我们是在ucc源代码declchk.c629行检查到了这个错误，错误提示中包含这样的信息是为了方便对UCC编译器源代码进行和分析。iron@ubuntu:test$ o.c:2:5:error:‘f’declaredasfunctionreturningafunctioniron@ubuntu:test$ucc o.c,2):error:functioncannotreturnfunctiontypeuccinvokecommanderror:/home/iron/bin/ucl-o iron@ubuntu:test$clang o.c:2:6:error:functioncannotreturnfunctiontype'int(int)'intf(int)(int);^1error引入表达能力更强的文法，到目前为止，我们介绍的文法被称为上下文无关文法，cone-r,实际上存在能力更强的文法。用集合的观点，通俗的来说，就是我们拜和。后都会有不同的感受”，这就是所谓的”ThereareathousandHamletsinathousandpeople's的。如果有一天，再复杂的语义规则都可以形式化了，那按照“可以形式化，就可以自动化”了。ecaaonpeon是ecaaon中的运算符换成了*[]和()成了nt等基本类型。如果你熟悉+以构成一个完整的类型表达式。我们会为”ntfnnint4];”构造一棵形如图1.3.7decl.c中的代码，我们可画图1.3.7复杂的分析树与语法虽然延用二叉树的结点astNode，但此处我们实际上用每个astNode的kids[1]域构成了一个链表来描述标志符f的类型信息，较特别的是在FUNCION()结点中，我们用其kids[0]域来记录其形参列表。图1.3.7所代表类型信息可简化为以下链表： ----> ---->POINTER----> >我们由链首出发，从左向右来构造一个新的类型，其含义是INT为基本类型，所得类型表述为,把POINTER类型运算符作用于上一步的结果，所得类型pointertoarray[4]of回值的类型，而函数的形参列表则存于结点FUNCTION()的kids[0]域中，所得类型为function(int,int,int)whichreturnspointertoarray[4]ofint前一步所得的类型即为标志符ff function(int,int,int)whichreturnspointertoarray[4]off”fs:“f138108第109至1371.3.8接下来，我们以非终结PostfixDeclarator为例，来分析一下如何构建形如图1.3.7的语法当然类似于图1.3.7，我们是把二叉树当单向链表来用了。 ----> ----> >其含义INT为基本类型，所得类型表述为把ARRAY[3]类型运算符作用于上一步的结果所得类型为array[3] array[5]of前一步所得的类型即为标志符arrarr array[3]ofarray[5]of行的，最先遇到的是int，之后是[3]，然后才是[5]，但在构造类型信息时，我们需要先把函数，我们先构建了int结点，接着在DirectDeclarator()函数中，我们构造了arr对应的结点，ARRAY[3]作为其前驱。int结 在Declaration()函数中进行构arr结 在DirectDeclarator()函数中进行构 PostfixDeclarator() ----> ---->arr ----> ----> >在Declaration()函数中进构建Declarator、DirectDeclaratorDeclaration的处理函数，与PostfixDeclarator类似，就不再述1.3.9观察Declaration的产生式，我们可以发现这样的产生式一次只能一个标志符，无法同时多个标志符，例如”int a,b;”。 这个问题不难解决，把上述产生式改为如 DeclaratorList,因为从语法结构上，“* c”是由一个符Declarator生成，而”d”由另一个符Declarator生成。 c,”int(*f(int,int,int))[4];”这样的复杂，需要先看f(int,int,int)，再向外看。这不符合人的直 intARRAY[4];ARRAY* f(int,int,int);上去实现控制流语句ifwhile语句。与语statement相关的产生式如下所 if(Expression)Statement if(Expression)StatementelseStatementWhileStatement→while(Expression)Statement { Statement| Expression; Declaration;经实现了表达式Expression和Declaration对应的处理函数。依照C语言标准，此处我们把赋值操作”id=Expression”视为赋值表达式，赋值表达式之后再跟上分号，则构成了表我们把Declaration727772行的IS_PREFIX_OF_DECL()实际用到的是我们前文介绍的首符集的概念，只有当前token属于Declaration的首符集时，我们才去识别Declaration。这里可能存在问题是，如TK_IDDeclaration的首符集时，该如何处理。就跟到陌生地方遇到叉路口一样，UCC图 1.3.1061CreateStmtNode()CreateAstNode()这两个不同的函数调用，从函数名中我们可以发现两者都是为了创建一个结点Node。CreateStmtNode()义，我们就可以发现，astStmtNode对象起始部分的数据恰好可以当作一个astNode对象来astStmtNodeastNode。这种技thenStmtIfStatementWhileStatement的处理函astNodetoken的TokenKindUCC的源代码中，我们需要专门为抽象语法树结点定义不同的类型，可参见”ucc\ucl\opinfo.h”。TokenKindastNode是不够的。以乘法运算符*为例，该符号用于四则运算”(a+b)*c”时，充当乘号。而在“int*a;”中则不是作为乘号来使用。所以在”ucc\examples\sc\tokens.txt”中，我们引入了TK_MUL和_PINTR*C语言的运算++astNode{TokenKindop;Valuevalue;structastNode*}*astStmtNode{TokenKindop;Valuevalue;structastNode*structastStmtNode*thenStmt;structastStmtNode*elseStmt;structastStmtNode*next;}*xpeonaementaement是递归定义的，atemenstStatementList→StatementList下面，我们举例来说明如if语句进行翻译，if语句可分为以下两种，我们以带分支的if语句为例来讨论IfStatement→if(Expression) IfStatement→if(Expression)Statement例如a=b=}我们期望把上述语句翻译为以下中间代码，通过有条件的oo和无条件的oo，我们就实现了控制流的转移。在U的指令集中，会有相应的硬件指令来实现条件或无条件跳bgpcue,abe_0和abe_1ooCoof和hefSfheneeabe_0fabe_1taemenNode(if(!c)goto 在VisitStatementNode()函数产生此跳转指a=goto在VisitStatementNode()函数产生此跳转指Label_0else语句的标号b=Else语句，存于astStmtNode对象elseStmtLabel_1是下一条语句的标号，存于有了这样的直观体会后，我们再来1.3.11111行调用的CretaeLabelNode()函数就是用来创建一个新的标号。给标号取Label_0Label_1，看起来就像给变量取名a,b,c，或叫、和，在实际开发中是要受人鄙视的，不过这些标号图 句对应的AST结点中存放while语句的标号Label_2，while语句的下一条语句的标号对应的处理函数见图1.3.12。在图1.3.12中，我们还看到了由一对大括号包围的复合语句的处理过程，为了记录Statement链表，我们在结构体astStmtNode中引入了next域，在图中150155行我们看到了构成单向链表的操作。而在153行中，我们要判断当前面对的token是否为Statement的首符，所以再次用到了首符集的概念。a=} //while语句的标号，存于kids[0]if(!c)gotoLabel_3//在VisitStatementNode()函数中生成此有条件跳转指令a=f //Then语句，存于astStmtNode对象的thenStmt域gotoLabel_2//VisitStatementNode() //while语句的下一条语句的标号，存于图 While和复合语astStmtNodeStatement对语句对应的AST结点，而第205210行则用于处理复合语句。图 NextChar函数，NextCharFromMem用于从内存中取下一个字符NextCharFromStdin则用于从当前进程的标准输入中取下一个字符，在第32行，我们调用了voidNextChar=}}用动ec的码只通给nexer()递同函指，们可让ec的法析器een内或标输中下个符和向象言中多异同际+虚数是过函表实的虚数是若干函指构的要微下nux内源码们可找好的虚数”结体比如uct e_opeaonnux核然用C言现但们是用C现承多这的向象想只创虚数这的作要C程员己手有+译代而数针实个常要概念们识别是非结符oram生字串但图134第34我调的是opounaten这因为oram产式下示为单见我就再为oram造个理数。第35告我，个oram别功，们该遇的文结符O,第36用遍语树产中代。 图 UCC编译器预UCC的使1.3ucc\examples\sc，我们对如何根据语言的文法来编写语法分析器，中间代码，C程序员还不能得到其所要的计算结果。C编译器还要由中间代码产生汇编代码。UCC编译器前，让我们先熟UCC编译器的使用。UCC编译器的大部分代码Ubuntu系统不算太复杂，这里不再画蛇添足。需要在ucc/makefile第1行和ucc/driver/linux.c第7行配置UCC的安装 源代码被解压到”/home/iron/src/ucc” ，则经过以下步骤就可构建并安装UCC到”iron@ubuntu:ucc$make-siron@ubuntu:ucc$make-stest如下所示，由cd~进入当前用户主gedit打开的.bashrc文件末尾添加一行”exportPATH=$PATH:/home/iron/bin其中”/home/iron/bin”UCCDIR，保存后退出，重新打开一个终端，即可使用ucc命令。 cd~ 接下来，我们用一个简单的例子来解释一下UCC的大致工作流程。编写以下C代码，存为文件”o.c”。这份代码用于求阶乘，其中有if语句、while语句、库函数调用及递归intf(intn){if(n<returnreturnn*f(n-}}intinti=1;}return}C源代码o.c需要先经过预处理器 PreProcessor)预处理。预处理器会根据预设ncude UserManual.txt”中所言”Beforereportingbugs:…….,sendtheprepocessedfilesto 关。C编译器再根据中间代码生成不同硬件平台的汇编语言，这部分工作被称为编译器的后端， WriteOnce,RunAnywhere”那让人热血沸腾的Slogan。当然，与运行平台相关的工作及优化的重头戏就交给了Java虚拟机。Java得到跨平台的代价是牺牲了一部分的运行效率，但在程序就不好玩了。生成中间代码之后解释执行，比”生成机器代码之后直接运行速度更低”的原因，aautne”目标模块o.o还需要携手函数库和其他的目标代码才能得到可执行程序o，这个工作被称为Linking，即连接，也有写为的，哪个是错误字，已经傻傻分不清楚了，权 --->o.i --->o.s iron@ubuntu:demo$ls iron@ubuntu:demo$ucc-Eo.c-oo.iiron@ubuntu:demo$ls iron@ubuntu:demo$ucc--dump-ast--dump-IR-So.i-oo.siron@ubuntu:demo$ls iron@ubuntu:demo$ucc-c o.s-o iron@ubuntu:demo$ls iron@ubuntu:demo$ucc o.o-o iron@ubuntu:demo$ iron@ubuntu:demo$./ f(1)=1f(2)=f(3)=f(4)=f(5)=f(6)=f(7)=f(8)=f(9)=362880f(10)=按上面的分析，我们可以发现，要由C源代码得到一份可执行程序，我们需要“预处UCCCLinuxWindowsuccucc–E等不uccUCC编译器阅读和分析时，比较有用的参数还有”--dump-ast--dump-IR”，用于生成字符串形式表达的抽象语法树AST，及优化后的中间代码IR。器、编译器、汇编器和连接器。UCC驱动的代码在ucc\driver 编译器的源代码则在\ucc\ucl。按“扫，剪裙边”的思路，下一小节，我们会先剖析一下UCC编译器驱动的代码。UCC在上一小节，通过以下四条命令，我们有意地给ucc传递不同的参数来依次调用预处理器、编译器、汇编器和连接器。当然实际使用ucc命令时，我们不会绕这么大一个圈子，直接 o.c -oo”即可得到可执行程序o。iron@ubuntu:demo$ucc-Eo.c- iron@ubuntu:demo$ucc--dump-ast--dump-IR-So.i-oo.siron@ubuntu:demo$ucc-co.s-oo.oiron@ubuntu:demo$ucco.o-o ucc\driver来分析一下ucc驱动器的源代码。图1.4.1给出了ucc\driver\linux.c中的部分代码。第17至22行是我们使用”ucc-Eo.c-oo.i”命令时，ucc驱动真正执行令其中的CPP代表的是CPreProcessor即C预处理器而非CPlusPlus,C++。通过-D参数，指定了GNUC等预定义的宏，而$1、$2和$3用于充当占位符ucc-E- o.c-I../-DREAL=double- 命令中的”-I../-DREAL=double”UCCDriver提取出来，用于替换字符串”$1”;而命令中的”o.c”21行的”$2”，充当预处理器的输入文件；命令中的”o.ii”则替换”$3”,用来存放预处理后的结果。而”-v”参数UCC驱动在终端上打印出实际所用到的/usr/bin/gcc-U -D_POSIX_SOURCE- -Dlinux-D =signed--I/home/iron/bin/include-I../-DREAL=double- o.c- ucc-S- o.c--dump-ast- 35行中$1、$2和$321ucl就是我UCCucc\ucl3846行分别是汇编器AssemblerLinker45行的参数"-lc","-lm"用来告诉连接器我们需要C函数库libc.so和数算函数库libm.so。/home/iron/bin/ucl- 1.4.1接下来的问题就是如何在ucc驱动中开启一个新进程来执行上述命令行所对应的预处理器、编译器、汇编器或者连接器。图1.4.2给出了在Linux平台上创建子进程及装载执行fork()Unix。生物界中，有许多细胞进行繁殖时，是通过细胞一分为二的来进行，Linux创建子进程的系统调用fork()也相当于这个过程。英文fork是叉子行为，clone。除了进程号PID、父进程号PPIDfork()fork()成功后，会有两个进程并发执行以下56行开始的代码，当然对这两个进程而言，因为fork()的返回值不一样，所以新创建的6366725859行则进程中加载外存中的某个可执行程序，这可借助系统调用execv()来实现。我们知道，编译后生成的可执行程序一般是存放在外存的，只有被装载器Loader从外存载入内存后，这个可执行程序才能运行。而Linuxexecv()系统调用就是起到这个装载器的作用。如果子进程通过execv()加载了一个可执行程序，那对子进程而言，其整个进程空间中的代码段和数据段就会被替换成新加载的可执行程序的代码段和数据段。这意味着一旦第63行的7273wait()有在子进程执行完或者出错时，父进程才会执行第74至82行之间的代码。UCC驱动会通过函数ParseCmdLine()分析程序员提供令行参数，并结合图1.4.1中的CPPProg ASProg和LDProg等命令模板，通过函数 mand()来构建实际要调用令，并将其作为参数传给图1.4.2中的Execute()函数。函数ParseCmdLine()和 在ucc\driver\ucc.c中，主要是进行一些字符串的处理，这里不再啰嗦。1.4.2结合C汇编汇编语言的语法和语义都不复杂，如果你会C语言，那你就一定能在很短时间内看懂开始C编译器剖析的长征时，我们有必要熟悉一下我们要到达的目的地。学习任何语言代码来熟悉汇编的办法。我们先简单介绍一些基本概念，然后给出一个简单C程序及由ucc\ucl\x86win32.tpl只是用到的汇编代码语法格Linux平台的有所不同，两者没有本质区别。X86Linux.tpl文件名中的”.tpl”是模板temte的缩写，其含义是文件x86Linux.tpl中包编代码中，%0、%1和%2是占位符，这和前一节1.4.1中的$1、$2和$3的作用类似。以下两条汇编指令用于比较%2和%1对应的两个有符号整数，如果两者不相等，则跳转到%0对应的目标地址处；若相等，则执行下一条汇编指令。助记符cmpcompare的缩写，cmpl中的后缀”l”表示进32位的比较jneJumpifNotEqualTEM "cmpl%2,%1;jne的指令集也被划分为指令和非指令。CPU处于可以使用任何指令的状态时，被称管理所有的软硬件资源，就要有权使用CPU的所有指令，所以要处于管态。而操作系统内核之外的应用程序只使用非指令，处于目态。当然，实际上x86CPU是有四个不同的ring0ring3Linuxring0ring3。所以概念上，我和输出out这样的指令在x86中都是指令，只有OS内核才能使用。如果一个应用程序理员拥有一样的权力，那带来的只能是。但在标准C语言里，并没有任何语法结构与开关中断这样的汇编指令相对应，而我们知道，Linux内核主要是用C语言来开发的。CC语言中嵌入汇编代码的机制。而我们要剖析的UCC编译器暂时还未提C代码中嵌入汇编的机Cinterrupt在Linux中，C程序员可调用read()和write()这样的库函数来向内核发出读文件和写文件的言的语义，ucc\ucl\x86Linux.tplUCC编译器原作者的选择。这个选择并页式管理是许多现代CPU普遍支持的内存管理机制，而In 的x86CPU因为要兼容干脆绕开x86的分段机制，及如何开启请求分页机制的工作已经由操作系统内核完成，操作栈中为该函数分配空间，这意味着C函数中的局部变量是在栈中动态分配的。或C++new操作，这部分动态数据区被称为堆Heap。我们平时会讲“这一堆乱七八糟代码数据区动态数据区（由堆和栈构成，运行时分配静态数据区（全局变量、静态变量和常量，编译时确定和来实现，由库函数实现者去花心思，不用劳烦C编译器。C编译器对栈的管理，主现“栈”空间的分配和回收，所以栈空间的管理不需要C程序员操心。需要另外说明的是，1.5.1C语言代码来举例说明动态和静态数据区的概念。1.5.1按C语言的语法图1.5.1中的str1是全局变量而str2是静态变量而第12行的” World”则是常量，这部分数据就保存在我们前文中所述的“静态数据区而函数h中的变量str3是个局部变量，在函数h被调用时，才会在栈中动态为str3分配内存，在第9行，我们让str3指向了由malloc分配的16字节的堆空间。图1.5.2是由”ucc-S 成的部分汇编代码。图1.5.2第8行的str1对应前述C代码中的str1，而第9行的str2.0则对应上述C代码中的静态变量str2，为了避免与可能存在的全局变量str2重名，UCC为静态变量str2加上了”.0”的后缀。第8行中的”.comm str1,4”告诉汇编器，str1是个全局变量，要占4个字节，在32位机器中，指针一般就占4个字节;而第9行的” 看到了C代码中的字符串常量"oWorld"，UCC编译器还为之起了一个名为”.str0”的名字，因为合法的C语言中不存在以”.”为前缀的变量名，所以我们可以不用担心”.str0”会跟C代码中的变量重名，而第5行的”.string”则指明了紧随其后的是以’\0’结束的字符串"oWorld"UCC编译器对静态数据区的管理只要做到这一层即可为这些变量分配具体位置的工作就由后续的汇编器和连接器来完成。而图1.5.23行”.data”则告诉汇编器接下来的是静态数据区，而第11行的”.text”则告诉汇编器接下来的又切换成代码区了，text是正文的意思，实际上代表的就是代码区。你可能也发现了，在图1.5.2中我们没有发strstr31.5.1C1.5.21535Ch()2320(%ebp)即为形str28行的-4(%ebp)是局部变str3。1.5.2而要比较好h对应的汇编代码，我们需要再介绍点关于寄存器的概念。X86汇编语言中描述的寄存器物理上存在于CPU中，而静态数据区则存在于内存中。因为寄存器直观上，CPU提供的寄存器数量似乎越多越好，但这有硬件成本的约束算机研究人点是放在CPU和内存之间的Cache上。UCC编译器使用的x86寄存器有eax、ebx、ecx、edx、esp、ebp、esi和edi等共8个寄存器。以”e”为前缀命名的32位版本的寄存器，去掉前缀得到的ax,bx,cx,dx,sp,bp,si和di，就是16位版本的寄存器。ax还可分为ah和al这两个8位的寄存器，其中的h表示高字节，而l表示低字节，bx、cx和dx寄存器也存在类似的8 点Arm的风格了，从R0一直到R15。不过，实事求是，这些通用的寄存器Register，确IT大佬们开会讨论后的结果是：eax,ecx,edx被划入易失寄存scratchregister，需要由主保存动作了，因为写内存是有一定的时间开销ebx,esiedi被划preserveregisters，需要由被调callee来保存，这意味着如果主调函数在保值寄存器中存放了有用的成原样即可。而UCC编译器使用了最简单的策略来管理“保值寄存器”，即在函数处不栈中逆序弹出(pop)。这就是我们在1.5.21719push30prologue是序言的epilogue则是尾声的意思。 "pushl%%ebp;pushl%%ebx;pushl%%esi;pushl%%edi;movl%%esp,%%ebp") "movl%%ebp,%%esp;popl%%edi;popl%%esi;popl%%ebx;popl当一个C函数被调用时，我们需要在栈中为该函数分配一段内存空间，我们需要记录86bp和esp86153图 栈示意pushebp,ebx,esiedi1.5.3ebp0,ebx0,esi0edi043行的movl指令可用于“内存与寄存器”或“寄存器与寄存器”之间的数据传递，mov是8位操作的后缀”b”,long，wordbyte的缩写。严格说来，32CPU的字stackpointer之意。第44行的sub指令是“substract”的缩写，相当“esp-=4;”的计算，放”oWorld”的地址。UCC编译器经过优化后，直接在第46行把”oWorld”的地址存指令就用于取”.str0”对应静态数据区的首地址，并存放到寄存器eax中。第47行的mov指令则把寄存器eax的数据传送到全局变量str1中。这正是图1.5.1中第12行C语句str1= popstrmain()中完成。有了这样的基础后，我们再回头去看图1.5.2h()函数对应的汇编代码，就应很有感觉了。当h()函数成为当前正在执行的函数时，寄存器ebp会被设置到图1.5.3的ebp2处，而ebp+20好是第一个形参str的地址，指令”movl20(%ebp),%eax”的含义是把ebp+20处的内容传递到寄存器eax中。ebp-4则对h()中的局部变量str3，汇编指令”movl%eax,1.5.3所示。需要注意esppushlesp4操作，poplesp4。Call指令会把其下一条指令的地址（即函数返回地址）入栈，这相当了esp减4的操作，而ret指令相当于做了esp加4的出栈操作。下一节，我们将再写几个简单的C程序，来解释ucc\ucl\x86Linux.tpl中的其他汇编代码。图 main()汇编代整数运让我们还是从熟悉的加减乘除等算术运算入手。图1.5.5给出了一个简单的C程序，其CCUCC编译器生成的汇编代.5141.5.6a111320b15始化的全局变量c；而第16行对应的是没有作初始化的静态变量d，为避免重名，被UCC编译器改名为”d.0”；而第17行对应的是初始化为5的静态变量e，被UCC编译器重命名 变量a和b的global，这代表变量名a,b是在全局可见的，但e.1是静态的，只在当前文件中可见。按照C语言的语义，全局或静态未初始化的变量其缺省值一般为0。在生成目标文件(后缀为.obj或.o的文件)时，我们只需要在目标模块中记录这块要被初始化为0的空间有多大就可以，没有必要把一堆的0存到目标文件中。确切地说，汇编代码中第15行的”.comm”用于未初始化的全局变量，comm是common之意，代表这是一块公共用地，即全局变量之意，而第16行的” m”则用于未初始化的静态变量，lcomm是localcommon之意，只在本目标模块中可见。.5517C语言算术运算所对应的汇编代码，如下图1.5.7所示。图1.5.7中的第3233行对应“c=a|b;”,32行把a的值从内存加eax33beaxeax34eaxc1.5.73549行所andl,shll,sarl,addl和subland，addsub对应按位与、加和减运shlShiftLeftsar和逻辑shr之分，sarShiftArithmeticRightshrShiftRight的缩写，两者的区别是sar右移时最要用之前的符号位来填充，而shr右移时最补0。例如，以下f()g()则不会。原因是：a是有符号整数，Csar汇编指令来进行移位操作，而a的值为-1，在内存中以补码形式存放时即为0xFFFFFFFF，算术右移后仍然是-1。而b为无符号整数，C编译器会选择shr来进行逻辑右移，最补inta=-unsignedintb=0xFFFFFFFF;voidf(){while(a>>=}voidwhile(b>>=}图 图1.5.7中的第50至52对应的是”ca*b，其中第51行的imul是有符号整数乘法signedmultiplemul5356行对应的是”c=a/b;”，第word16CPUword2字节，48字节，x86edxeax8个字节当成被除数，edx32eax32cdq指令后，edx32位的内容都是eax的最。如果寄存器eax最为1，edx各bit全为1；否则全为0。不难想象，如果要作无符号数的除法，因为eax的最不再被当作符号位，我们需要直接把edx寄存值赋值0，相x86Linux.tpl48所示： "movl$0,%%edx;divl1.5.755idivsigneddividediv则是无符号整数unsigneddivide。整数除法运算的结果有两部分，一部分是商，会被存放在寄存器eax中，如图1.5.756行所示；另一部分是余数，会被存放在寄存器edx中。当我们进行”c=a%b;”的运算时，就需要用到除法运算的余数，如图1.5.76164行所示。第57行的incincrement16567行对应的是”ca;”，66negnegative的缩写，数学上是取相反数的意思，如果有符号数a为-1，即0xFFFFFFFF，经过neg指令的处理后，就得到a的相反数1，即 68至70行对应的是”c=~a;”，第69行的not指令用于按位取位，如果a为-1，则按位取反为得到的是0x 让我们再来看一下C语言中的以下运算符，如图1.5.8UCC.821cmpa0，若不相等，则跳转到基本块”.BB2”处，如果相等，则执行第24行的指令，而第23行在汇编中只是个标号。而第34则跳转到基本块”.BB6”;否则(即a大于b)，则执行第36行，作”c++;”的操作。常用的条件跳JumpifJumpifNotJumpif>Jumpif>Jumpif<Jumpif<JumpifGreaterorJumpifAboveorJumpifLessorJumpif or我们以0xFFFFFFFF和0x 为例，如果都视为有符号数，则补码0xFFFFFFFF是-1，而0x 为0，此时有-1要小于0；但如果视为无符号数，则0xFFFFFFFF要大果要把这两个数的比较当作有符号整数之间的比较，则C编译器在产生cmp指令后，需要选择有符号数的条件跳转指令，如JG,JL，JGE和JLE；而如果要当作无符号整数之间的比较，则C编译器在产生cmp指令后，需要选择JA,JB,JAE和JBE等指令。如图1.5.9所示，有被执行。图1.5.9第5行，我们进行的是有符号整数之间的比较，此时-1大于0不成立；而第8行进行的是无符号整数之间的比较，此时无符号数0xFFFFFFFF大于0是成立的；我1114signedintunsignedint之间二元运算时，signedint会被提升unsignedint。我们很少会写出类似图1.5.9第11行这样的代码，但是如果一不就可能写出下1.5.10所示，运行结果竟然是”-1>0”。因此，有符号整数与无符号整数还是尽量不要混合在一起处理，其结果可能出乎意料。由图1.5.1022jbe指令可以发现，此处是把aa中的值始终都是0xFFFFFFFF。1.5.10oat和doueU点运算一般都会由专门的浮点运算来实现，例如In的x87，就是一个典型的FloatPointUnit，缩写为FPU，浮点运算单元。在下一小节中，我们会讨论一下UCC编译器用到的x87浮点运算指令。浮点数的算术运执行该程序，通过第9和第11行的输出语句，我们会得到以下结果：iron@ubuntu:1.5$ucc-ofpufpu.ciron@ubuntu:1.5$./fpu 1.0f0x3f800000，这个值正是按照“IEEE754标准”单精度格式编码的浮点数，对应的十进制值为。1.5.11ArchitecturesSoftwareDeveloper’sManualFigure8-2，我们可知x87内部实际上提供了864double8Figure8-2所描述的寄存器栈，当使fld1.5.1213x87栈顶寄存器和bfadd正是用于浮点数的加法，同样，后缀”s”表示14fstpc所对应的内存单元，fstSToreFloatingpointvalueppop16fmuls则是用于单Figure8-行所示。我们还注意到，图1.5.12第5行用于初始化变量a的值，正是我们面看到的。1.5.12浮点数运算的汇编代图15110CCaC87151225至36”87PUonol”自n手的ue86和e48ue86为87的onold过制87名onol其中ounnn 为87下e48的4C的是”Roundtowardzero”，即把超出精度的部分直接截断。这需要我们在浮点运算前对ControlWord寄存器进行设置，同时我们期望此处的浮点运算结束后，ControlWord寄存器的内容能恢复到运算前的样子，这需要在内存中先保存之前令字，同时，通过x87转换得来的整数也需要作为一个临时变量存放到内存中。这正是第26至36行的代码要完成的主要功能。图1.5.12的第25行用于把浮点数a从内存加载到x87中，第26行通过调整esp寄27fnstcwx8716Controlword存放到位于内存的栈中(%esp)处，fnstcwunmaskedfloating-pointexceptions”，即不对浮点运算异常进行检查。第28movzwl是MOVewithZero-extended的缩写，后缀”wl”16位的整数扩展为32位的整数，相当于1602831行用于设Figure8-6x87ControlWordRoundingControl位，该控制位用于指定浮点运算“舍入”时的行为。第31行的fldcw指令用于从内存中加载控制字到x87控制字寄存器中。第32fistpl指令实现了把x87栈顶寄存器中的浮点数转换成32位整数的操作，fistSToreInteger的助记符，后缀”p”表示要转换后要把x87栈顶寄存器出栈，而后缀”l”表示要把浮点数转换成32位整数。第33行用于恢复浮点运算34368(%esp)32d，并恢复esp指针。所以，实现浮点数转换成整数功能的关键代码是第32行。

1.5.13中的代码为例。在浮点数的编码中，IEEE754引入了一些特殊的编码来表示正无穷大、负无穷大，因为一个IEEE754也引入了一个称为NotANumber的特殊编码，用来表示这样的运算结果为“不是一个实数”，简写为NaN。图 NaN和无穷大”-inf”，而第10打印出来的结果是正穷大”inf”，但第13行打印出来的结果是NaN。iron@ubuntu:1.5$gccnan.c-onan-lmiron@ubuntu:1.5$-iron@ubuntu:1.5$uccnan.c-onaniron@ubuntu:1.5$./nan-Table3-有了这个概念后，我们再举一个浮点数比较的代码，及其对应的汇编代码，如 数据寄存器中一般存放操作数，如Figure8-2x87数据寄存器栈，有时需要寻址念；状态寄存器则反映了当前所处的状态，例如是否处于BUSY状态。x86CPU内我们有意忽EFLAGS寄存器中的标志位这样的细节，因为完全可以站在汇编指令的语义上来理解有符号和无符号整数之间的比较，就如图1.5.8和1.5.9之间的段落所述，如果需要做更深入理解，可查看InCPU手册的“Figure3-8Eflags1.5.14浮点单元x87内部也有相应的状态寄存器，如In手册的Figure8-4所示。而浮点数之间比较后的结果主要由x87状态寄存器的C0C2和C3Table3-31Figure8-1.5.141213abx87数据寄存器栈的栈顶。而14行则进行处x87数据寄存器栈顶的两个浮点数之间的比较，pp是COMpareFloatingpointvalues的助记符，后缀”pp”表示需要进行两次pop操作，即浮点数比15fnstswx87x8616ax中，ax32eax168ahax8位，fnstswSTorex87FPUStatusWord的助记符，其中”n”表示”withoutcheckingforpendingunmaskedfloating-pointexceptions”。第16行的test指令实际上进行的是“按位与”运算，而a位于st(1)Table3-31，我们可归纳为下表：“C2C00b>0偶b<1奇b==0偶2偶四种比较结果中，”b<a”即”a>b”1.5.1415test指令执行之后，得到的“C2C0”0的位数为奇数个，由此我们就可以产生第17行的代码jp.BB2”1”时，跳转到基本块”.BB2”4行的if条件成立，则执行”c++;”的运算。212422fildlLoaD的助记符，后缀”l”表示要加载的是321.5.14的代码中解释了比较(a>b)的情况，至于(ab)等其他比较操作对应的汇编代码可参X86Linux.tpl67107行。指针、数组和结构CUCC1.5.15number[0]20150。UCC编译器采取的翻译方memsetnumber0number[0]设为20151.5.151724行所示。CmemsetAPI如下所示：void*memset(void*s,intc,size_tcs17行的$64nnumber所占的内存c，表示我们要把指针s所指的大小为n字节的内存全部设为019行用于取内存单元-64(%ebp)20行把这个地址入栈，即对应参数s，而-64(%ebp)所对应的内存空间正是UCC编译器为局部数组number在栈中分配的空间。第21行完成了对库函数而与10行”ptr&number[1];”对应的汇编代码为252725number[0]的地址存到寄eax中，因number[1]number[0]4字节，所26行到了ptr所对应的内存单元中。11行”*ptr=2016;”对应的汇编代1.5.152930行，第29行通过movl指令把内存单元ptr中存放的内容传送到寄存器ecx中，这样ecx中存放的数据就是n