编译原理讲义课件.ppt

《编译原理讲义课件.ppt》由会员分享，可在线阅读，更多相关《编译原理讲义课件.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、8 目标代码生成学时：6知识点：涉及的问题 基本块、程序流图 下次引用信息 代码生成算法18 目标代码生成n目标代码生成程序的任务将前端产生的中间代码转换为等价的目标代码n对目标代码生成器的要求：正确高质量1.有效地利用目标机器的资源2.所生成的目标代码应高效地运行n本章目标：介绍一个简单的代码生成器算法产生最优化代码问题是不可判定的，实践中能够产生好的（虽不是最优的）代码的启发式技术就很令人满意了2本章主要内容8.1 代码生成器设计中的问题8.2 目标机器8.3 运行时的存储管理8.4 基本块和流图8.5 下次引用信息8.6 简单的代码生成器 小 结 作 业38.1 代码生成器设计中的问题n

2、代码生成器的具体细节依赖于目标机器和操作系统n所有的代码生成器固有的问题代码生成器的输入代码生成器的输出存储管理指令选择寄存器分配计算顺序选择代码生成器的设计4一、代码生成器的输入n中间代码经过语法分析、语义检查之后得到的正确的n符号表记录了与名字有关的信息决定中间表示中的名字所代表的数据对象的运行地址n假定：前期工作结果正确、可信中间代码足够详细必要的类型转换符已正确插入明显的语义错误已经发现、且正确恢复5二、代码生成器的输出n目标代码n形式绝对机器代码可把代码放在内存中固定的地方、立即执行可重定位机器代码.obj（DOS）、.o（UNIX）开发灵活，允许各子模块单独编译需要由连接装配程序将

3、它们连接在一起，生成可执行文件汇编代码代码生成过程容易，但需要汇编6三、存储管理n从名字到存储单元的映射由前端和代码生成器共同完成n三地址代码中的名字指向该名字在符号表中位置的指针n符号表中的信息在处理声明语句时填入“类型”决定了它的域宽“地址”确定该名字在过程的数据区域中的相对位置上述信息用于确定中间代码中的名字对应的数据对象在运行时的地址n生成机器代码时，指令地址通过计数器来实现7例如：中间代码与目标代码的对应n对于四元式j：goto iij目标代码.0n四元式100的机器码 四元式 地址 长度.100 (，)101 (，)102 (，)103 (，).n121212n+12n+12四元式

4、101的机器码8 88n+20n+20四元式102的机器码161616n+36n+36四元式103的机器码4 44n+40.将四元式j的地址记入与i相关的链表中，等待回填四元式i的地址已有，可以直接生成机器指令8四、指令选择n机器指令系统的性质决定了指令选择的难易程度n代码质量取决于它的执行速度和长度n对每一类三地址语句，可以设计它的代码框架如：x:=y+z 的代码框架可以是：MOV y,R0ADD z,R0MOV R0,xa:=b+cd:=a+ea:=a+1MOV b,R0ADD c,R0MOV R0,aMOV a,R0ADD e,R0MOV R0,dMOV a,R0ADD#1,R0MOV

5、R0,aINC a9五、寄存器分配n充分利用寄存器可以生成好的代码n寄存器使用的两个问题哪些变量要放在寄存器中指定的变量放在哪个寄存器中n寄存器指派的困难可用寄存器专用寄存器通用寄存器寄存器对把寄存器指派给相应的变量变量需要什么样的寄存器操作需要什么样的寄存器选择最优的寄存器指派方案是一个NP完全问题10六、计算顺序的选择n计算顺序影响目标代码的效率n选择最佳计算次序是一个NP完全问题七、代码生成器的设计n设计原则能够正确地生成代码易于实现、便于测试和维护n只介绍一个简单的代码生成算法主要考虑寄存器的有效使用118.2 目标机器n设计代码生成器的必要条件：熟悉目标机器n一般信息编址方式：按字节

6、编址每个字有4个字节寄存器：n个通用寄存器：R0、R1、Rn-1指令形式：OP S,D其中 OP：MOV、ADD、SUB S：源操作数 D：目的操作数12寻址方式地址形式 汇编方式 地址 占用存储空间 绝对地址 M M 1 寄存器 R R 0 变址 c(R)c+contents(R)1 间接寄存器 *R contents(R)0 间接变址 *c(R)contents(c+contents(R)1 立即数#c 常数c 1n指令代价指令所占用存储单元字数=1+S寻址方式占用字数+D寻址方式占用字数13举例nMOV R0，R1将寄存器R0的内容复制到R1中代价：1nMOV R5，M将寄存器R5的内容

7、放到存储单元M中代价：2nADD#1，R3将寄存器R3的内容增加1代价：2nSUB 4(R0)，*12(R1)将地址为(contents(12+contents(R1)的单元中的值减去contents(4+contents(R0)，结果仍存放到地址为(contents(12+contents(R1)的单元中。代价：314三地址语句a:=b+c的代码(1)MOV b,R0ADD c,R0 指令代价为6MOV R0,a(2)MOV b,aADD c,a 指令代价为6(3)假定R0、R1和R2中分别存放了a、b和c的地址：MOV *R1,*R0ADD *R2,*R0 指令代价为2(4)假定R1和R2

8、中分别包含b和c的值，b的值以后不再需要：ADD R2,R1MOV R1,a 指令代价为315n过程的语义决定了运行时名字如何与存储单元相联系。n存储分配策略静态存储分配存储器中活动记录的位置在编译时刻已经确定栈式存储分配当开始执行一个过程时，一个新的活动记录压入栈顶当该过程的活动结束时，其活动记录从栈中弹出n活动记录的内容参数、返回值控制链、访问链、机器状态局部数据、临时变量8.3 运行时的存储管理n活动记录的分配和释放是调用序列和返回序列的一部分n讨论三地址语句 call returnhaltaction16静态存储分配情况三地址代码：三地址代码：/*S的代码*/action1call p

9、action2halt/*P的代码*/action3returnS的活动记录的活动记录(64字节字节)：045660返回地址arrijP的活动记录的活动记录(88字节字节)：04返回地址buf84n17n三地址语句call的目标机器指令：MOV指令：存放返回地址GOTO指令：将控制转移到被调用过程的目标代码 MOV#here+20,callee.static_areaGOTO callee.code_areahere：该MOV指令的地址20：call的机器指令的代价#here+20：返回地址被调用过程活动记录的开始地址被调用过程代码的第一条指令地址n三地址语句return的目标机器指令：GOT

10、O *callee.static_area代码结构18静态存储分配举例100:action1120:MOV#140,364132:GOTO 200140:action2160:HALT 200:action3220:GOTO *364 300:304:364:368:保存返回地址 调用过程P 返回到364存储单元里存放的地址 S的代码：的代码：P的代码：的代码：S的活动记录：(300-363)P的活动记录：(364-451)返回地址单元 返回地址单元局部数据单元局部数据单元140返回地址返回地址19栈式存储分配情况n活动记录分配在栈中n活动记录在栈中的位置，直到运行时才能确定n这个位置常被存放

11、在一个寄存器中n寄存器SP保存指向栈顶活动记录开始位置的指针当发生过程调用时，调用过程给SP一个增量，使之指向被调用过程的活动记录的开始位置，同时将控制转移到被调用过程；当控制返回到调用过程时，再将SP减去原来的增量，从而释放了被调用过程的活动记录。20代码结构n主程序的代码MOV#stackstart,SP第一个过程的代码HALT初始化控制栈n三地址语句call的机器代码ADD#caller.recordsize,SP MOV#here+16,SP GOTO callee.code_area SP指向下一个活动记录n三地址语句return的机器代码GOTO*0(SP)SUB#caller.r

12、ecordsize,SP间接变址，返回调用过程该指令在被调用过程的代码中SP指回调用过程的活动记录该指令在调用过程的代码中21程序说明三地址代码：/*S的代码*/action1call qaction2halt/*P的代码*/action3return/*q的代码*/action4call paction5call qaction6call qreturn各过程目标代码的起址：s：#100p：#200q：#300活动记录的大小：ssize=20psize=40qsize=60控制栈的开始位置：#60022100:MOV#600,SP108:action1128:ADD#ssize,SP136:

13、MOV#152,*SP144:GOTO 300152:SUB#ssize,SP160:action2180:HALT 200:action3220:GOTO *0(SP)栈式存储分配举例300:action4320:ADD#qsize,SP328:MOV#344,*SP336:GOTO 200344:SUB#qsize,SP352:action5372:ADD#qsize,SP380:MOV#396,*SP388:GOTO 300396:SUB#qsize,SP404:action6424:ADD#qsize,SP432:MOV#448,*SP440:GOTO 300448:SUB#qsize

14、,SP456:GOTO *0(SP)600:SPq初始化栈call qcall preturncall qcall qreturn23程序执行及栈的变化情况SP=600SS的活动记录20call qSP=620返回地址152q的活动记录60qcall pSP=680p的活动记录40返回地址344preturn返回地址344SP=620p的活动记录40call qSP=680q的活动记录60返回地址396qreturn返回地址396SP=620q的活动记录60call qSP=680q的活动记录60返回地址448qreturn返回地址448SP=620q的活动记录60return返回地址152S

15、P=600q的活动记录60haltS的活动记录2024运行时名字的地址n假定三地址语句为：x:=0n静态存储分配情况静态数据区的基址：staticx在数据区中的位置是 12x的实际地址应为：static+12尽管在编译时可确定static+12的值，但在生成中间代码时，static的值可能并不知道。这样，必须生成相应的三地址代码以“计算”static+12的值。赋值语句 x:=0 被翻译为如下三地址代码：static12:=0若 static=100，则相应的目标代码为：MOV#0,11225用display表存取非局部名字，该表存放在寄存器中x局部于一个活动记录，该活动记录的display表

16、指针在寄存器R3中将语句 x:=0 翻译成为如下三地址语句：t1:=12+R3*t1:=0n栈式存储分配情况t1中存放的是x的地址这个序列可由如下机器指令来实现：MOV#0,12(R3)268.4 基本块和流图n基本块具有原子性的一组连续语句序列。控制从第一条语句流入，从最后一条语句流出，中途没有停止或分支（末尾除外）n划分基本块的方法确定入口语句三地址代码的第一条语句条件/无条件语句转移到的语句紧跟在条件/无条件语句后面的语句确定基本块从一个入口语句（含该语句）到下一个入口语句（不含）从一个入口语句（含该语句）到停止语句（含该语句）27举例基本块：t1:=a*at2:=a*bt3:=2*t2

17、t4:=t1+t3t5:=b*bt6:=t4+t5(1)i:=m-1(2)j:=n(3)t1:=4*n(4)v:=at1(5)i:=i+1(6)t2:=4*i(7)t3:=at2(8)if t3v goto(9)(13)if i=j goto(23)(14)t6:=4*i(15)x:=at6(16)t7:=4*i(17)t8:=4*j(18)t9:=at8(19)at7:=t9(20)t10:=4*j(21)at10:=x(22)goto(5)(23)t11:=4*i(24)x:=at11(25)t12:=4*i(26)t13:=4*n(27)t14:=at13(28)at12:=t14(29

18、)t15:=4*n(30)at15:=x基本块划分：B1B2B3B4B5B628流图n定义：把控制流信息加到基本块集合中，形成程序的有向图，称为流图（控制流图）n构造：流图的结点是基本块如果一个结点基本块的入口语句是程序的第一条语句，则称此基本块结点为首结点。如果在某个执行序列中，基本块B2紧跟在基本块B1之后执行，则从B1到B2有一条有向边，B1是B2的前驱，B2是B1的后继。即如果：有一个条件/无条件转移语句从B1的最后一条语句转移到B2的第一条语句；B1的最后一条语句不是无条件转移语句，并且在程序的语句序列中，B2紧跟在B1之后。n实现：用记录；用链表n转移语句指向块而不是指向三地址语句

19、因为基本块变换后，语句会发生变化n循环的定义：强连通；唯一入口29举例 (1)i:=m-1 (2)j:=n(3)t1:=4*n (4)v:=at1(5)i:=i+1 (6)t2:=4*i(7)t3:=at2 (8)if t3v goto (9)(13)if i=j goto (23)(14)t6:=4*i(15)x:=at6(16)t7:=4*i(17)t8:=4*j(18)t9:=at8(19)at7:=t9(20)t10:=4*j(21)at10:=x(22)goto (5)(23)t11:=4*i(24)x:=at11(25)t12:=4*i(26)t13:=4*n(27)t14:=at

20、13(28)at12:=t14(29)t15:=4*n(30)at15:=xB1B2B3B4B5B6B2B3B6B2308.5 下次引用信息n在把三地址代码转换成为目标代码时，遇到的一个重要问题：如何充分利用寄存器？如何充分利用寄存器？n作用：如果存于寄存器的名字的值以后不再需要，那么该寄存器可以分配给其它名字n基本思路：在一个基本块范围内考虑把在基本块内还要被引用的变量的值尽可能保存在寄存器中把在基本块内不再被引用的变量所占用的寄存器尽早地释放n如：翻译语句 x:=y op z x、y、z在基本块中是否还会被引用？在哪些三地址语句中被引用？31计算下次引用信息三地址语句序列：i:x:=1j:

21、y:=x op zj 是三地址语句是三地址语句 i 中中 x 的下次引用信息的下次引用信息n假定讨论在一个基本块内的引用信息所有的变量在基本块出口处都是活跃的符号表中含有记录下次引用信息和活跃信息的域语句i对变量x定值没有对变量x定值的其他语句语句j引用x在语句i处定的值32算法 输入：组成基本块的三地址语句序列 输出：基本块中各名字的下次引用信息 方法：1.把基本块中各变量在符号表中的下次引用信息域置为“无下次引用”、活跃信息域置为“活跃”。2.从基本块出口到入口由后向前依次处理各语句，对每个三地址语句 i:x:=y op z，依次执行下述步骤：a)把当前符号表中变量 x的下次引用信息和活跃

22、信息附加到语句 i上；b)把符号表中 x 的下次引用信息和活跃信息分别置为“无下次引用”和“非活跃”；c)把当前符号表中变量y和z的下次引用信息和活跃信息附加到语句 i上；d)把符号表中y和z的下次引用信息均置为 i，活跃信息均置为“活跃”。abcd次序不能颠倒!33举例n计算向量点积的程序begin prod:=0;i:=1;do begin prod:=prod+ai*bi;i:=i+1 end while i=20end.n程序的控制流图：B1(1)prod:=0(2)i:=1(3)t1:=4*i(4)t2:=a-4(5)t3:=t2t1(6)t4:=4*i(7)t5:=b-4(8)t6

23、:=t5t4(9)t7:=t3*t6(10)t8:=prod+t7(11)prod:=t8(12)t9:=i+1(13)i:=t9(14)if i=20 goto B2B234计算B2中变量的下次引用信息n初始化符号表：变量 下次 活跃 i 无 活prod 无 活a 无 活b 无 活t1 无 活t2 无 活t3 无 活t4 无 活t5 无 活t6 无 活t7 无 活t8 无 活t9 无 活 附加信息 语句 变量 下次 活跃 n从出口到入口依次检查每条三地址语句：(14)if i=20 i 无无 活活 14 活活(13)i:=t9 i 14 活活 无无 非活非活 t9 无无 活活13 活活(12

24、)t9:=i+1 t9 13 活活 无无 非活非活 i 无无 非活非活 12 活活(11)prod:=t8 prod 无无 活活 无无 非活非活 t8 无无 活活 11 活活(10)t8:=prod+t7 t8 11 活活 无无 非活非活 prod 无无 非活非活 10 活活 t7 无无 活活 10 活活35变量 下次 活跃 i 无 活prod 无 活a 无 活b 无 活t1 无 活t2 无 活t3 无 活t4 无 活t5 无 活t6 无 活t7 无 活t8 无 活t9 无 活 14 活活 无无 非活非活13 活活 无无 非活非活 12 活活 无无 非活非活 11 活活 无无 非活非活 10

25、活活 10 活活符号表：附加信息 语句 变量 下次 活跃(9)t7:=t3*t6 t7 10 活活 无无 非活非活 t3 无无 活活 9 活活 t6 无无 活活 9 活活(8)t6:=t5t4 t6 9 活活 无无 非活非活 t5 无无 活活 8 活活 t4 无无 活活 8 活活(7)t5:=b-4 t5 8 活活 无无 非活非活 b 无无 活活 7 活活(6)t4:=4*i t4 8 活活 无无 非活非活 i 12 活活 6 活活(5)t3:=t2t1 t3 9 活活 无无 非活非活 t2 无无 活活 5 活活 t1 无无 活活 5 活活(4)t2:=a-4 t2 5 活活 无无 非活非活

26、a 无无 活活 4 活活(3)t1:=4*i t1 5 活活 无无 非活非活 i 6 活活 3 活活368.6 简单的代码生成器n思想：在基本块内充分利用寄存器n方法：尽可能让变量的值保存在寄存器中，只有在下面两种情况下存储它们如果此寄存器要用于其它计算已到达基本块出口后续的代码尽可能引用变量在寄存器中的值，而不访问主存n在基本块之间如何充分利用寄存器的困难：一个基本块可能有多个后继，而每个后继又可能有多个前驱，因而后继基本块不易判断变量的值是否存放在寄存器中，以及存放在那个寄存器中n假定：三地址语句中的每个算符都对应一个相应目标语言算符37考虑引用信息n代码生成时，要考察不同的情况n不同的情

27、况下，生成的目标代码也不同n如 a:=b+c(1)b的值在Ri中，c的值在Rj中，且b不再活跃 ADD Rj,Ri 代价为 1(2)b的值在Ri中，c的值在存储单元Mc中，且b不再活跃 ADD Mc,Ri 代价为2 或 MOV Mc,Rj ADD Rj,Ri 代价为338数据结构n寄存器描述器记录每个寄存器的当前内容开始时，寄存器描述器指示所有的寄存器均为空代码生成过程中，每个寄存器在任一给定时刻将保留0个或多个名字的值。n地址描述器记录某时刻一个名字的当前值存放的位置，可能是：一个寄存器地址一个栈地址一个存储单元地址或这些地址的一个集合这些信息可以存放在符号表中，用来确定对一个名字的存取方式

28、39寄存器分配函数getregn输入：三地址语句 x:=y op z 寄存器描述器和名字的地址描述器n输出：地址L（L或者是寄存器，或者是存储单元）n算法(1)若y的值在R中，且该R中不含其它名字的值，并且以后y不再活跃，没有下次引用信息，则返回R作为L。(2)若(1)失败，有空R时，就返回一个空R作为L。(3)若(2)失败，x在块中有下次引用，或op是一个需要寄存器的算符，则找一个已被占用的R。如果R的值尚未在存储单元中，用指令MOV R，M将R的值存放到一个存储单元中，如果R同时保存有几个变量的值，则对每一个需要存储的变量值都应产生一条MOV指令。并且更新地址描述器为，返回R。(4)如x在

29、块中不再被引用，或找不到合适的被占用的寄存器，则返回x的存储单元Mx作为L。40代码生成算法n 输入：基本块的三地址语句输出：基本块的目标代码n方法：对基本块中每个三地址语句x:=y op z执行以下操作：(1)确定工作单元 L：=getreg(i:x:=y op z)(2)查看y的地址描述器，以确定y的值存放的当前位置y若y的值同时存放在存储器和寄存器中，那么选择寄存器作为y如果y的值在寄存器L中，更新y的地址描述器（y不在L中）和L的寄存器描述器（L中不含y的值）如果y的值不在L中，则生成指令：MOV y,L(3)生成指令：op z,L更新x的地址描述器（x的值在L中），如果L为寄存器，更

30、新L的寄存器描述器（L中只含x的值）(4)若y/z的当前值没有下次引用，在块的出口非活跃，并且在寄存器中，则更新寄存器描述器及y/z的地址描述器（此后，这些寄存器不再包含y和/或z的值）41特殊情况n若三地址语句是 x:=op y与x:=y op z类似n若三地址语句是 x:=y（复写语句）若y的值在R中，更新R的寄存器描述器和x的地址描述器，以记录x的值仅在保存y的那个寄存器中。若y没有下次引用，且在块的出口非活跃，则该寄存器不再保留y的值。若y的值仅在存储器My中，原则上可以在地址描述器中指出X在My中，但是这样会复杂代码生成算法，因为以后若要改变y的值必须先保存x的值。调用函数getre

31、g来找一个存放x值的寄存器R，生成指令MOV y,R，并更新R的寄存器描述器和x、y的地址描述器。或者，若X无下次引用信息，生成指令MOV My，Mx，更新x的地址描述器。42n处理：使用MOV指令把那些在块出口是活跃的、且当前值还不在存储单元中的名字的值存储到它们的存储器地址中。n方法：使用寄存器描述器确定哪些名字的当前值仍保留在寄存器中使用地址描述器确定其中哪些名字的当前值还不在存储单元里使用活跃变量信息来确定是否需要存储其当前值n在没有进行数据流分析的情况下，需要假定用户定义的所有变量在基本块出口处都是活跃变量在计算下次引用信息的算法中，第一步要把活跃信息域置为“活跃”基本块的出口处43

32、举例n考虑赋值语句 d:=(a-b)+(a-c)+(a-c)n三地址语句序列：t:=a-bu:=a-cv:=t+ud:=v+un假定在基本块的出口d是活跃的n有两个寄存器R0和R144翻译过程t:=a-bu:=a-cv:=t+ud:=v+u寄存器全空MOV a,R0SUB b,R0R0含tt在R0中MOV a,R1SUB c,R1R0含tR1含ut在R0中u在R1中ADD R1,R0R0含vR1含uv在R0中u在R1中ADD R1,R0R0含dd在R0中MOV R0,dd在R0和内存单元中语句 生成的代码 寄存器描述器 地址描述器45为索引赋值语句生成目标代码n考虑两种语句形式：a:=bi 和

33、ai:=bn假定数组采用静态存储分配基址已知，用数组名表示下标i存放的位置不同，生成的目标代码也不同i在Ri中i在Mi中i在栈中a:=biai:=bMOV b(Ri),RMOV b,a(Ri)MOV Mi,RMOV b(R),RMOV Mi,R MOV b,a(R)MOV Si(A),RMOV b(R),RMOV Si(A),R MOV b,a(R)2 4 4 3 5 5 i的位置46为指针赋值语句生成目标代码n考虑两种语句形式：a:=*p 和*p:=anP存放的位置不同，生成的目标代码也不同p在Rp中p在Mp中p在栈中a:=*p*p:=aMOV*Rp,aMOV a,*RpMOV Mp,RMO

34、V*R,RMOV Mp,R MOV a,*RMOV Sp(A),RMOV*R,RMOV a,R MOV R,*Sp(A)2 3 3 2 4 4 p的位置47nif xy goto z实现：x-y的结果送入寄存器R判断R的值为正、负、还是零若为负，则转移到zn利用条件码表示计算结果或存入寄存器R的值为正、负、还是零如：if xy goto z目标代码：CMP x,yCJ z为条件语句生成目标代码目标代码：MOV y,R0ADD z,R0MOV R0,xCJ P语句序列x:=y+zif x0 goto P48小 结n设计代码生成器时要考虑的问题输入、输出存储管理、寄存器分配目标机器相关问题（指令、寄存器、编址方式、寻址能力、寻址模式等）指令选择、计算顺序选择n基本块和控制流图基本块：具有原子性的语句序列基本块的划分：入口语句的确定流图：有向图，结点：基本块，边：控制流49小 结（续）n下次引用信息作用计算方法n代码生成器寄存器描述器地址描述器寄存器分配函数getreg代码生成算法50作 业51