中间代码生成南京大学计算机科学与技术系

第六章中间代码生成赵建华南京大学计算机系第1页本章内容中间代码表达抽象语法树三地址代码：x=yopz静态类型检查类型检查（typechecking）语法分析之后抽象语法(syntax)检查，例如break位置，goto目标….中间代码生成第2页编译器前端逻辑构造第3页三地址代码（1）每条指令右侧最多有一种运算符一般情况能够写成x

=

yopz允许运算分量：名字：源程序中名字作为三地址代码地址常量：源程序中出现或生成常量编译器生成临时变量第4页三地址代码（2）指令集合（1）运算/赋值指令：x=yopz x

=

opy复制指令：x=y无条件转移指令：gotoL条件转移指令：ifxgotoL ifFalsexgotoL条件转移指令：ifxrelopygotoL第5页三地址代码（3）指令集合（2）过程调用/返回：paramx1 //设置参数paramx2…paramxncallp,n //调用子过程p，n为参数个数带下标复制指令：x=y[i]

x[i]=y注意：i表达离开数组位置第i个字节，而不是数组第i个元素地址/指针赋值指令：x=&y x=*y *x=y第6页例子语句doi=i+1;while(a[i]<v)；第7页三地址指令四元式表达办法在实现时，能够使用四元式/三元式/间接三元式来表达三地址指令四元式：能够实现为纪录（或构造）格式（字段）： op arg1 arg2 resultop:运算符内部编码arg1,arg2,result是地址x=y+z +yzx单目运算符不使用arg2param运算不使用arg2和result条件转移/非条件转移将目标标号放在result字段第8页四元式例子赋值语句：a=b*-c+b*-c第9页三元式表达三元式（triple） op arg1 arg2使用三元式位置来引用三元式运算成果x[i]=y需要拆分为两个三元式求x[i]地址，然后再赋值x=yopz需要拆分为（这里？是编号）(?) op y z = x ?问题：在优化时经常需要移动/删除/添加三元式，造成三元式移动。第10页三元式例子a=b*-c+b*-c第11页间接三元式包括了一种指向三元式指针列表我们能够对这个列表进行操作，完成优化功能；操作时不需要修改三元式中参数。第12页静态单赋值（SSA）SSA中所有赋值都是针对不一样名变量对于同一种变量在不一样途径中定值情况，能够使用φ函数来合并不一样定值if(flag)x=-1;elsex=1; y=x*aif(flag)x1=-1;elsex2=1;

x3=φ(x1,x2)；y=x3*a第13页类型和申明类型检查(TypeChecking)利用一组规则来检查运算分量类型和运算符预期类型是否匹配。类型信息用途查错、确定名字需要内存空间、计算数组元素地址、类型转换、选择正确运算符本节内容确定名字类型，变量存放空间布局（相对地址）第14页类型体现式类型体现式（type

expression）：表达类型构造基本类型类名类型构造算子作用于类型array[数字，类型体现式]record[字段/类型正确列表]（能够用符号表表达）函数类型构造算子

：参数类型

成果类型笛卡尔积：sXt能够包括取值为类型体现式变量第15页类型体现式例子类型例子元素个数为3X4二维数组数组元素统计类型该统计类型中包括两个字段:

x和y,其类型分别是float和integer类型体现式array[3,array[4,record[(x,float),(y,float)]]第16页类型等价不一样语言有不一样类型等价定义构造等价或者它们是相同基本类型或者是相同构造算子作用于构造等价类型而得到。或者一种类型是另一种类型体现式名字名等价类型名仅仅代表其本身第17页申明文法DTid;D|εTBC|record‘{’D‘}’Cint|floatCε|[num]C含义：D生成一系列申明；T生成不一样类型；B生成基本类型int/float；C表达分量，生成[num]序列；注意record中包括了各个字段申明。字段申明和变量申明文法一致。第18页局部变量存放布局变量类型能够确定变量需要内存即类型宽度可变大小数据构造只需要考虑指针函数局部变量总是分派在连续区间；因此给每个变量分派一种相对于这个区间开始处相对地址变量类型信息保存在符号表中；第19页计算T类型和宽度SDT综合属性：type,width全局变量t和w用于将类型和宽度信息从B传递到C

ε相称于C继承属性，由于总是通过拷贝来传递，因此在SDT中只赋值一次。也能够把t和w替代为C.t和C.w第20页SDT运行例子输入：int[2][3]第21页作用域和符号表在具有语句块概念编程语言中，标识符x在最内层x申明作用域中。每个作用域对应于一种符号表；多种符号表形成树状构造。在语义分析时，通过栈来寄存目前符号表及其祖先。第22页申明序列SDT（1）在处理一种过程/函数时，局部变量应当放到单独符号表中去；这些变量内存布局独立相对地址从0开始；假设变量放置和申明次序相同；SDT处理办法变量offset统计目前可用相对地址；每“分派”一种变量，offset值增加对应值top.put(id.lexeme,T.type,offset)在目前符号表(位于栈顶)中创建符号表条目，统计标识符类型，偏移量第23页申明序列SDT（2）我们能够把offset看作D继承属性D.offset表达D中第一种变量相对地址P{D.offset=0}DDTid;{D1.offset=D.offset+T.width;}D1第24页统计字段处理Trecord‘{‘D‘}’为每个统计创建单独符号表首先创建一种新符号表，压到栈顶；然后处理对应于字段申明D，字段都被加入到新符号表中；最后根据栈顶符号表构造出record类型体现式；符号表出栈第25页体现式代码SDD将体现式翻译成三地址指令序列体现式SDD属性code表达代码addr表达寄存体现式成果地址（临时变量）newTemp()能够生成一种临时变量gen(…)生成一种指令第26页增量式翻译方案主属性code满足增量式翻译条件。注意：top.get(…)从栈顶符号表开始，逐一向下寻找id信息。这里gen发出对应代码第27页数组元素寻址假设数组元素被寄存在连续存放空间中。元素从0到n-1编号，第i个元素地址为base+i*wK维数组寻址：假设数组按行寄存，即首先寄存A[0][i2]…[ik]，然后寄存A[1][i2]…[ik]，…A[i1][i2]…[ik]地址base+i1*w1+i2*w2+…+ik*wk或者base+((…((i1*n2+i2)*n3+i3)…)*nk+ik)*w其中：base、w、i、n值能够从符号表中找到。第28页新文法产生式数组元素L：LL[E]|id[E]以数组元素为左部赋值：SL=E;数组元素作为体现式中因子：ELL代码计算偏移量，将成果寄存于L.addr所指临时变量中综合属性array统计了对应数组信息：元素类型，基地址，…第29页数组元素作为因子L代码只计算了偏移量；数组元素寄存地址应当根据偏移量深入计算，即L数组基址加上偏移量使用三地址指令x=a[i]第30页数组元素作为赋值左部使用三地址指令a[i]=x第31页例子体现式：c+a[i][j]第32页类型检查和转换类型系统：给每一种组成部分赋予一种类型体现式通过一组逻辑规则来表达这些类型体现式必须满足条件可发觉错误、提升代码效率、确定临时变量大小、…第33页类型系统分类类型综合根据子体现式类型构造出体现式类型if

f类型为st且x类型为sthen

f(x)类型为t类型推导根据语言构造使用方式来确定该构造类型：iff(x)是一种体现式then对于某些类型α,β；f类型为α

β且x类型为α第34页类型转换假设在体现式x*i中，x为浮点数、i为整数，则成果应当是浮点数x和i使用不一样二进制表达方式浮点*和整数*使用不一样指令t1=(float)it2=xfmult1类型转换比较简单时SDD：EE1+E2{if(E1.type=integerandE2.type=integer)E.type=integer;elseif

(E1.type=floatandE2.type=integer)E.type=float;}}这个规则没有考虑生成类型转换代码第35页类型widening和narrowingJava类型转换规则编译器自动完成转换为隐式转换，程序员用代码指定转换为显式转换。第36页处理类型转换SDT函数Max求是两个参数在拓宽层次构造中最小公共祖先Widen函数已经生成了必要类型转换代码第37页函数/运算符重载通过查看参数来处理函数重载问题Ef(E1)

{

if

f.typeset={siti|1<=i<=k}andE1.type=sk

then

E.type=tk

}第38页控制流翻译布尔体现式能够用于变化控制流/计算逻辑值。文法BB‖B|B&&B|!B|(B)|ErelE|true|false语义B1‖B2中B1为真时，不计算B2，整个体现式为真。因此，当B1为真时应当跳过B2代码。B1&&B2中B1为假时，不计算B2，整个体现式为假短路代码通过跳转指令实现控制流处理逻辑运算符本身不在代码中出现；第39页短路代码例子语句：if(x<100||x>200&&x!=y)x=0;代码

if x<100 gotoL2

ifFalse x>200 gotoL1

ifFalse x!=y gotoL1L2:x=0L1:接下来代码注：当x<100为真时，直接执行x=0；因此执行x>200时，x<100必然为假同理：计算x!=y时，x<100为假，而x>200为真第40页控制流语句翻译文法：B表达布尔体现式，S代表语句S

if(B)S1Sif(B)S1

elseS2Swhile(B)S1代码布局见右图继承属性B.true：B为真跳转目标B.false：B为假跳转目标S.next：S执行完成时跳转目标第41页语法制导定义（1）第42页语法制导定义（2）增量式生成代码：S

while( {begin=newlabel();B.true=newlabel;B.false=S.next;gen(begin‘:’)}

B)

{gen(B.true‘:’);S1.next=begin;}S1{gen(‘goto’begin);}第43页布尔体现式控制流翻译生成代码执行时跳转到两个标号之一。体现式值为真时，跳转到B.true体现式值为假时，跳转到B.falseB.true和B.false是两个继承属性，根据B所在上下文指向不一样位置假如B是if语句条件体现式，分别指向then分支和else分支；假如没有else分支，则指向if语句下一条指令假如B是while语句条件体现式，分别指向循环体开头和循环出口处；第44页布尔体现式代码SDD（1）第45页布尔体现式代码SDD（2）第46页布尔体现式代码例子if(x<100||x>200&&x!=y)x=0;代码第47页布尔值和跳转代码程序中出现布尔体现式目标也许就是求出它值。例如x=a<b；处理办法：首先建立体现式语法树，然后根据体现式不一样角色来处理。文法：Sid=E;|if(E)S|while(E)S|SSEE‖E|E&&E|ErelE

|

…根据E语法树结点所在位置：Swhile(E)S1中E，生成跳转代码对于Sid=E，生成计算右值代码第48页回填（1）为布尔体现式和控制流语句生成目标代码关键问题：某些跳转指令应当跳转到哪里例如：if

(B)S按照短路代码翻译办法，B代码中有某些跳转指令在B为假时执行，这些跳转指令目标应当跳过S对应代码。生成这些指令时，S代码尚未生成，因此目标不确定通过语句继承属性next来传递。需要第二趟处理。如何一趟处理完成呢？第49页回填（2）基本思想：统计B代码中跳转指令gotoS.next，if…gotoS.next位置，不过不生成跳转目标。这些位置被统计到B综合属性B.falseList中；当S.next值已知时（即S代码生成完成时），把B.nextList中所有指令目标都填上这个值。回填技术：生成跳转指令时临时不指定跳转目标标号，而是使用列表统计这些不完整指令；等懂得正确目标时再填写目标标号；每个列表中指令都指向同一种目标第50页布尔体现式回填翻译（1）布尔体现式用于语句控制流时，它总是在取值true时和取值false时分别跳转到某个位置引入两个综合属性truelist:包括跳转指令（位置）列表，这些指令在取值true时执行falselist：包括跳转指令（位置）列表，这些指令在取值false时执行辅助函数Makelist(i)Merge(p1,p2)Backpatch(p,i)第51页布尔体现式回填翻译（2）第52页回填和非回填办法比较（1）B {B1.true=B.true,B1.false=newlabel();} B1|| {label(B1.false);B2.true=B.true;B2.false=B.false;} B2true/false属性赋值，在回填方案中对应为对应list赋值或者merge；本来生成label地方，在回填方案中使用M来统计对应代码位置。M.inst需要对英