中间代码生成 - 计算机系主页.ppt

《中间代码生成 - 计算机系主页.ppt》由会员分享，可在线阅读，更多相关《中间代码生成 - 计算机系主页.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章 中间代码生成,赵建华南京大学计算机系,本章内容,中间代码表示抽象语法树三地址代码：x=y op z静态类型检查类型检查（type checking）语法分析之后的抽象语法(syntax)检查，比如break的位置，goto的目标.中间代码生成,编译器前端的逻辑结构,三地址代码（1）,每条指令右侧最多有一个运算符一般情况可以写成x = y op z允许的运算分量：名字：源程序中的名字作为三地址代码的地址常量：源程序中出现或生成的常量编译器生成的临时变量,三地址代码（2）,指令集合 （1）运算/赋值指令：x=y op zx = op y复制指令：x=y无条件转移指令：goto L条件转移指

2、令：if x goto Lif False x goto L条件转移指令：if x relop y goto L,三地址代码（3）,指令集合（2）过程调用/返回：param x1/设置参数param x2param xncall p, n/调用子过程p，n为参数个数带下标的复制指令：x=yi xi=y注意：i表示离开数组位置第i个字节，而不是数组的第i个元素地址/指针赋值指令：x=&yx=*y*x=y,例子,语句do i = i + 1; while (aiv)；,三地址指令的四元式表示方法,在实现时，可以使用四元式/三元式/间接三元式来表示三地址指令四元式：可以实现为纪录（或结构）格式（字段

3、）：oparg1arg2resultop: 运算符的内部编码arg1,arg2,result是地址x=y+z+ y z x单目运算符不使用arg2param运算不使用arg2和result条件转移/非条件转移将目标标号放在result字段,四元式的例子,赋值语句：a=b* -c + b* -c,三元式表示,三元式（triple）oparg1arg2使用三元式的位置来引用三元式的运算结果xi=y需要拆分为两个三元式求xi的地址，然后再赋值x=y op z需要拆分为（这里？是编号）(?)opyz =x?问题：在优化时经常需要移动/删除/添加三元式，导致三元式的移动。,三元式的例子,a=b*-c +

4、 b * -c,间接三元式,包含了一个指向三元式的指针的列表我们可以对这个列表进行操作，完成优化功能；操作时不需要修改三元式中的参数。,静态单赋值（SSA）,SSA中的所有赋值都是针对不同名的变量对于同一个变量在不同路径中定值的情况，可以使用函数来合并不同的定值if (flag) x=-1; else x = 1;y = x*aif (flag) x1=-1; else x2 = 1; x3=(x1,x2)；y = x3*a,类型和声明,类型检查(Type Checking)利用一组规则来检查运算分量的类型和运算符的预期类型是否匹配。类型信息的用途查错、确定名字需要的内存空间、计算数组元素的地

5、址、类型转换、选择正确的运算符本节的内容确定名字的类型，变量的存储空间布局（相对地址）,类型表达式,类型表达式（type expression）：表示类型的结构基本类型类名类型构造算子作用于类型array数字，类型表达式record字段/类型对的列表（可以用符号表表示）函数类型构造算子：参数类型结果类型笛卡尔积：s X t可以包含取值为类型表达式的变量,类型表达式的例子,类型例子元素个数为3X4的二维数组数组的元素的记录类型该记录类型中包含两个字段: x和y,其类型分别是float和integer类型表达式array3, array4,record(x,float),(y,float),类型等

6、价,不同的语言有不同的类型等价的定义结构等价或者它们是相同的基本类型或者是相同的构造算子作用于结构等价的类型而得到的。或者一个类型是另一个类型表达式的名字名等价类型名仅仅代表其自身,声明,文法D T id ; D | T B C | record D C int | floatC | num C含义：D生成一系列声明；T生成不同的类型；B生成基本类型int/float；C表示分量，生成num序列；注意record中包含了各个字段的声明。字段声明和变量声明的文法一致。,局部变量的存储布局,变量的类型可以确定变量需要的内存即类型的宽度可变大小的数据结构只需要考虑指针函数的局部变量总是分配在连续的区

7、间；因此给每个变量分配一个相对于这个区间开始处的相对地址变量的类型信息保存在符号表中；,计算T的类型和宽度的SDT,综合属性：type, width全局变量t和w用于将类型和宽度信息从B传递到C 相当于C的继承属性，因为总是通过拷贝来传递，所以在SDT中只赋值一次。也可以把t和w替换为C.t和C.w,SDT运行的例子,输入：int23,作用域和符号表,在具有语句块概念的编程语言中，标识符x在最内层的x声明的作用域中。每个作用域对应于一个符号表；多个符号表形成树状结构。在语义分析时，通过栈来存放当前符号表及其祖先。,声明序列的SDT（1）,在处理一个过程/函数时，局部变量应该放到单独的符号表中去

8、；这些变量的内存布局独立相对地址从0开始；假设变量的放置和声明的顺序相同；SDT的处理方法变量offset记录当前可用的相对地址；每“分配”一个变量，offset的值增加相应的值top.put(id.lexeme, T.type, offset)在当前符号表(位于栈顶)中创建符号表条目，记录标识符的类型，偏移量,声明序列的SDT（2）,我们可以把offset看作D的继承属性D.offset表示D中第一个变量的相对地址PD.offset =0 DD T id; D1.offset = D.offset + T.width; D1,记录字段的处理,Trecord D 为每个记录创建单独的符号表首先

9、创建一个新的符号表，压到栈顶；然后处理对应于字段声明的D，字段都被加入到新符号表中；最后根据栈顶的符号表构造出record类型表达式；符号表出栈,表达式代码的SDD,将表达式翻译成三地址指令序列表达式的SDD属性code表示代码addr表示存放表达式结果的地址（临时变量）new Temp()可以生成一个临时变量gen()生成一个指令,增量式翻译方案,主属性code满足增量式翻译的条件。注意：top.get()从栈顶符号表开始，逐个向下寻找id的信息。这里的gen发出相应的代码,数组元素的寻址,假设数组元素被存放在连续的存储空间中。元素从0到n-1编号，第i个元素的地址为base+i*wK维数组

10、的寻址：假设数组按行存放，即首先存放A0i2ik，然后存放A1i2ik，Ai1i2ik的地址base+i1*w1+i2*w2+ik*wk或者base+(i1*n2+i2)*n3+i3)*nk+ik)*w其中：base、w、i、n的值可以从符号表中找到。,新的文法产生式,数组元素L：LLE | idE以数组元素为左部的赋值：SL=E;数组元素作为表达式中的因子：ELL的代码计算偏移量，将结果存放于L.addr所指的临时变量中综合属性array记录了相应数组的信息：元素类型，基地址，,数组元素作为因子,L的代码只计算了偏移量；数组元素的存放地址应该根据偏移量进一步计算，即L的数组基址加上偏移量使用

11、三地址指令x=ai,数组元素作为赋值左部,使用三地址指令ai=x,例子,表达式：c+aij,类型检查和转换,类型系统：给每一个组成部分赋予一个类型表达式通过一组逻辑规则来表示这些类型表达式必须满足的条件可发现错误、提高代码效率、确定临时变量的大小、,类型系统的分类,类型综合根据子表达式的类型构造出表达式的类型if f 的类型为st且x的类型为sthen f(x)的类型为t类型推导根据语言结构的使用方式来确定该结构的类型：if f(x)是一个表达式then 对于某些类型,；f的类型为且x的类型为,类型转换,假设在表达式x*i中，x为浮点数、i为整数，则结果应该是浮点数x和i使用不同的二进制表示方

12、式浮点*和整数*使用不同的指令t1 = (float) it2 = x fmul t1类型转换比较简单时的SDD：EE1 + E2 if(E1.type = integer and E2.type = integer) E.type = integer; else if (E1.type = float and E2.type= integer) E.type = float;这个规则没有考虑生成类型转换代码,类型的widening和narrowing,Java的类型转换规则编译器自动完成的转换为隐式转换，程序员用代码指定的转换为显式转换。,处理类型转换的SDT,函数Max求的是两个参数在拓宽

13、层次结构中的最小公共祖先Widen函数已经生成了必要的类型转换代码,函数/运算符的重载,通过查看参数来解决函数重载问题Ef(E1) if f.typeset = siti|1= i= k and E1.type=sk then E.type = tk ,控制流的翻译,布尔表达式可以用于改变控制流/计算逻辑值。文法B BB | B & B | !B | (B) | E rel E | true | false语义B1B2中B1为真时，不计算B2，整个表达式为真。因此，当B1为真时应该跳过B2的代码。B1&B2中B1为假时，不计算B2，整个表达式为假短路代码通过跳转指令实现控制流的处理逻辑运算符本

14、身不在代码中出现；,短路代码的例子,语句：if (x200 代码 if x 200goto L1 ifFalse x != ygoto L1L2: x=0L1: 接下来的代码,注： 当x200时，x200为真,控制流语句的翻译,文法：B表示布尔表达式，S代表语句S if (B) S1S if (B) S1 else S2Swhile (B) S1代码的布局见右图继承属性B.true：B为真的跳转目标B.false：B为假的跳转目标S.next：S执行完毕时的跳转目标,语法制导的定义（1）,语法制导的定义（2）,增量式生成代码：S while ( begin = newlabel(); B.tr

15、ue = newlabel; B.false = S.next; gen(begin :) B ) gen(B.true :);S1.next=begin;S1gen(goto begin);,布尔表达式的控制流翻译,生成的代码执行时跳转到两个标号之一。表达式的值为真时，跳转到B.true表达式的值为假时，跳转到B.falseB.true和B.false是两个继承属性，根据B所在的上下文指向不同的位置如果B是if语句的条件表达式，分别指向then分支和else分支；如果没有else分支，则指向if语句的下一条指令如果B是while语句的条件表达式，分别指向循环体的开头和循环出口处；,布尔表达式

16、的代码的SDD（1）,布尔表达式的代码的SDD（2）,布尔表达式代码的例子,if (x 200 的代码,布尔值和跳转代码,程序中出现布尔表达式的目的可能就是求出它的值。比如x=ab；处理方法：首先建立表达式的语法树，然后根据表达式的不同角色来处理。文法：S id = E; | if (E) S | while (E) S | S SE EE | E & E | E rel E | 根据E的语法树结点所在的位置：Swhile ( E ) S1中的E，生成跳转代码对于Sid = E，生成计算右值的代码,回填（1）,为布尔表达式和控制流语句生成目标代码的关键问题：某些跳转指令应该跳转到哪里例如：if

17、 (B) S按照短路代码的翻译方法，B的代码中有一些跳转指令在B为假时执行，这些跳转指令的目标应该跳过S对应的代码。生成这些指令时，S的代码尚未生成，因此目标不确定通过语句的继承属性next来传递。需要第二趟处理。如何一趟处理完毕呢？,回填（2）,基本思想：记录B的代码中跳转指令goto S.next，if goto S.next的位置，但是不生成跳转目标。这些位置被记录到B的综合属性B.falseList中；当S.next的值已知时（即S的代码生成完毕时），把B.nextList中的所有指令的目标都填上这个值。回填技术：生成跳转指令时暂时不指定跳转目标标号，而是使用列表记录这些不完整的指令；

18、等知道正确的目标时再填写目标标号；每个列表中的指令都指向同一个目标,布尔表达式的回填翻译（1）,布尔表达式用于语句的控制流时，它总是在取值true时和取值false时分别跳转到某个位置引入两个综合属性truelist: 包含跳转指令（位置）的列表，这些指令在取值true时执行falselist：包含跳转指令（位置）的列表，这些指令在取值false时执行辅助函数Makelist(i)Merge(p1,p2)Backpatch(p,i),布尔表达式的回填翻译（2）,回填和非回填方法的比较（1）,B B1.true=B.true, B1.false = newlabel();B1 | label(B

19、1.false); B2.true = B.true; B2.false=B.false; B2,true/false属性的赋值，在回填方案中对应为相应的list的赋值或者merge；原来生成label的地方，在回填方案中使用M来记录相应的代码位置。M.inst的需要对英语相应label的标号；原方案生成的指令goto B1.false，现在生成了goto M.inst,回填和非回填方法的比较（2）,回填时生成指令坯，然后加入相应的list原来跳转到B.true的指令，现在被加入到B.truelist中。,布尔表达式的回填例子,x200 & x!=y,控制转移语句的回填,Sif ( B ) S

20、 |if (B) S else S|while (B) S | L | AL L S | S语句的综合属性：nextlistnextlist中的跳转指令的目标应该是S执行完毕之后紧接着执行的下一条指令的位置。考虑S是while语句、if语句的子语句时，分别应该跳转到哪里？,控制转移语句的回填（2）,M的作用就是用M.instr记录下一个指令的位置规则1中记录了then分支的代码起始位置；规则2中，分别记录了then分支和else分支的起始位置；N的作用是生成goto指令坯，N.nextlist只包含这个指令的位置,控制转移语句的回填(3),Break、Continue的处理,虽然break、continue在语法上是一个独立的句子，但是它的代码和外围语句相关。方法：(break语句)跟踪外围语句S，生成一个跳转指令坯将这个指令坯的位置加入到S的nextlist中。跟踪的方法在符号表中设置break条目，令其指向外围语句在符号表中设置指向S的nextlist的指针，然后把这个指令坯的位置直接加入到nextlist中。,