【教学课件】第十一章代码生成.ppt

《【教学课件】第十一章代码生成.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第十一章代码生成.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十一章第十一章 代码生成代码生成词法分析器词法分析器语法分析器语法分析器中间代码生成器中间代码生成器优化段优化段源程序源程序单词符号单词符号语法单位语法单位四元式四元式表表格格管管理理出出错错处处理理目标代码生成器目标代码生成器四元式四元式目标代码目标代码n代代码码生生成成是是把把语语法法分分析析后后或或优优化化后后的的中中间间代码变换成目标代码。代码变换成目标代码。n目标代码一般有以下三种形式：目标代码一般有以下三种形式：能能够够立立即即执执行行的的机机器器语语言言代代码码，所所有有地地址址已已经经定位；定位；待待装装配配的的机机器器语语言言模模块块。执执行行时时，由由连连接接装装配配程程

2、序序把把它它们们和和某某些些运运行行程程序序连连接接起起来来，转转换换成成能执行的机器语言代码；能执行的机器语言代码；汇汇编编语语言言代代码码。尚尚须须经经过过汇汇编编程程序序汇汇编编，转转换换成可执行的机器语言代码。成可执行的机器语言代码。n代码生成着重考虑的问题：代码生成着重考虑的问题：如何使生成的目标代码较短；如何使生成的目标代码较短；如何充分利用计算机的寄存器，减少目标代如何充分利用计算机的寄存器，减少目标代码中访问存贮单元的次数。码中访问存贮单元的次数。如何充分利用计算机的指令系统的特点。如何充分利用计算机的指令系统的特点。11.1 基本问题基本问题 n代码生成器的输入代码生成器的输

3、入 代代码码生生成成器器的的输输入入包包括括源源程程序序的的中中间间表表示示，以以及符号表中的信息及符号表中的信息类型检查类型检查11.1 基本问题基本问题 n目标程序目标程序 绝对机器代码、可再定位机器语言、汇编语言绝对机器代码、可再定位机器语言、汇编语言采用汇编代码作为目标语言采用汇编代码作为目标语言 n指令选择指令选择 n寄存器分配寄存器分配 n计算顺序选择计算顺序选择 11.2 目标机器模型目标机器模型 n考虑一个抽象的计算机模型考虑一个抽象的计算机模型具具有有多多个个通通用用寄寄存存器器，他他们们既既可可以以作作为为累累加加器器，也可以作为变址器。也可以作为变址器。运算必须在某个寄存

4、器中进行。运算必须在某个寄存器中进行。含有四种类型的指令形式含有四种类型的指令形式如果如果op是一目运行符，则是一目运行符，则“op Ri,M”的意的意义为：义为：op（M）Ri，其余类型可类推。其余类型可类推。op 包括一般计算机上常见的一些运算符，如包括一般计算机上常见的一些运算符，如ADD加加SUB减减MUL乘乘DIV除除n不不考考虑虑代代码码的的执执行行效效率率，目目标标代代码码生生成成是不难的，例如：是不难的，例如：A:=(B+C)*D+E翻译为四元式：翻译为四元式：T1:=B+CT2:=T1*DT3:=T2+EA:=T3 11.3 一个简单代码生成器一个简单代码生成器G假设只有一个

5、寄存器可供使用假设只有一个寄存器可供使用目标代码：目标代码：LD R0，BADD R0，CST R0，T1假假设设T1，T2，T3在在基基本本块块之之后不再引用后不再引用:LD R0，BADD R0，CMUL R0，DADD R0，EST R0，A 四元式四元式T1:=B+CT3:=T2+ET2:=T1*DA:=T3 LD R0，T1MUL R0，DST R0，T2LD R0，T2ADD R0，EST R0，T3LD R0，T3 ST R0，A11.3 一个简单代码生成器一个简单代码生成器n四四元元式式的的中中间间代代码码变变换换成成目目标标代代码码，并并在在一一个个基本块的范围内考虑如何充分

6、利用寄存器：基本块的范围内考虑如何充分利用寄存器：在在生生成成计计算算某某变变量量值值的的目目标标代代码码时时，尽尽可可能能让该变量保留在寄存器中。让该变量保留在寄存器中。后后续续的的目目标标代代码码尽尽可可能能引引用用变变量量在在寄寄存存器器中中的值，而不访问内存。的值，而不访问内存。在在离离开开基基本本块块时时，把把存存在在寄寄存存器器中中的的现现行行的的值放到主存中。值放到主存中。11.3.1 待用信息待用信息n如如果果在在一一个个基基本本块块内内，四四元元式式i对对A定定值值，四四元元式式j要要引引用用A值值，而而从从i到到j之之间间没没有有A的的其其他他定定值值，那那么么，我我们们称

7、称j是是四四元元式式i的的变量变量A的的待用信息待用信息。（即下一个引用点）。（即下一个引用点）i:A:=B op Cj:D:=A op En假假设设在在变变量量的的符符号号表表登登记记项项中中含含有有记记录录待用信息和活跃信息的栏。待用信息和活跃信息的栏。n待用信息和活跃信息的表示：待用信息和活跃信息的表示：1 (x,x)表表示示变变量量的的待待用用信信息息和和活活跃跃信信息息。其其中中i表表示示待待用用信信息息，y表表示示活活跃跃，表表示示非待用和非活跃；非待用和非活跃；2 在在符符号号表表中中，(x，x)(x，x)表表示示后后面面的符号对代替前面的符号对；的符号对代替前面的符号对；3 不

8、不特特别别说说明明，所所有有说说明明变变量量在在基基本本块块出出口之后均为非活跃变量。口之后均为非活跃变量。n计算待用信息和活跃信息的算法步骤：计算待用信息和活跃信息的算法步骤：1.开开始始时时，把把基基本本块块中中各各变变量量的的符符号号表表登登记记项项中中的的待待用用信信息息栏栏填填为为“非非待待用用”，并并根根据据该该变变量量在在基基本本块块出出口口之之后后是是不不是是活活跃跃的的，把把其其中中的的活活跃跃信信息息栏栏填填为为“活活跃跃”或或“非活跃非活跃”；2.从基本块出口到基本块入口从基本块出口到基本块入口由后向前由后向前依次处依次处理各个四元式。对每一个四元式理各个四元式。对每一个

9、四元式i:A:=B op C，依次执行下面的步骤：依次执行下面的步骤：1)把符号表中变量把符号表中变量A的待用信息和活跃信息的待用信息和活跃信息附加到四元式附加到四元式i上；上；2)把符号表中把符号表中A的待用信息和活跃信息分别的待用信息和活跃信息分别置为置为“非待用非待用”和和“非活跃非活跃”；3)把符号表中变量把符号表中变量B和和C的待用信息和活跃的待用信息和活跃信息附加到四元式信息附加到四元式i上；上；4)把符号表中把符号表中B和和C的待用信息均置为的待用信息均置为i，活活跃信息均置为跃信息均置为“活跃活跃”。例：基本块例：基本块1.T:=A-B2.U:=A-C3.V:=T+U4.W:=

10、V+U设设W是基本块出口之后的活跃变量。是基本块出口之后的活跃变量。建立待用信息链表与活跃变量信息链表如下：建立待用信息链表与活跃变量信息链表如下：n附加在四元式上的待用附加在四元式上的待用/活跃信息表：活跃信息表：(4)W:=V+U(3)V:=T+U(2)U:=A-C(1)T:=A-B(,y)(,)(,)(4,y)(,)(4,y)(3,y)(,)(,)(3,y)(2,y)(,)序号序号 四元式四元式 左值左值 左操作数左操作数 右操作数右操作数变量名变量名初始状态初始状态信息链信息链(待用待用/活跃信息栏活跃信息栏)(3,y)(,)(2,y)(1,y)(1,y)(2,y)(4,y)(,)(3

11、,y)T(,)A(,)B(,)C(,)U(,)V(,)W(,y)(,)(4,y)(,)n寄存器描述数组寄存器描述数组RVALUE动态记录各寄存器的使用信息动态记录各寄存器的使用信息RVALUER=A,Bn变量地址描述数组变量地址描述数组AVALUE动态记录各变量现行值的存放位置动态记录各变量现行值的存放位置AVALUEA=R1,R2,An补充说明：补充说明：因因为为寄寄存存器器的的分分配配是是局局限限于于基基本本块块范范围围之之内内的的，一一旦旦处处理理完完基基本本块块中中所所有有四四元元式式，对对现现行行值值在在寄寄存存器器中中的的每每个个变变量量，如如果果它它在在基基本本块块之之后后是是活

12、活跃跃的的，则则要要把把它它存存在在寄寄存器中的值存放到它的主存单元中。存器中的值存放到它的主存单元中。要要特特别别强强调调的的是是，对对形形如如：A:=B的的四四元元式式，如如果果B的的现现行行值值在在某某寄寄存存器器Ri中中，则则无无须须生生成成目目标标代代码码，只只须须在在RVALUE(Ri)中中增增加加一一个个A，(即即把把Ri同同时时分分配配给给B和和A)，并并把把AVALUE(A)改为改为Ri。n代码生成算法：代码生成算法：对每个四元式对每个四元式:i:A:=B op C，依次执行：依次执行：1.以以四四元元式式:i:A:=B op C 为为参参数数，调调用用函函数数过过程程GET

13、REG(i:A:=B op C)，返返回回一个寄存器一个寄存器R，用作存放用作存放A的寄存器。的寄存器。2.利利用用AVALUEB和和AVALUEC，确确定定B和和C现现行行值值的的存存放放位位置置B和和C。如如果果其其现现行值在寄存器中，则把寄存器取作行值在寄存器中，则把寄存器取作B和和C 3.如果如果BR，则生成目标代码：则生成目标代码：LD R,B op R,C 否则生成目标代码否则生成目标代码 op R,C 如果如果B或或C为为R，则删除则删除AVALUEB或或AVALUEC中的中的R。4.令令AVALUEA=R,RVALUER=A。5.若若B或或C的现行值在基本块中不再被引用，的现行

14、值在基本块中不再被引用，也不是基本块出口之后的活跃变量，且其也不是基本块出口之后的活跃变量，且其现行值在某寄存器现行值在某寄存器Rk中，则删除中，则删除RVALUERk中的中的B或或C以及以及AVALUEB或或AVALUEC 中的中的Rk，使得该寄存器不再，使得该寄存器不再为为B或或C占用。占用。n寄存器分配函数过程：寄存器分配函数过程：GETREG(i:A:=B op C)返返回回一一个个用用来来存存放放A的的值的寄存器值的寄存器1 如如果果B的的现现行行值值在在某某个个寄寄存存器器Ri中中，RVALUERi中中只只包包含含B，此此外外，或或者者B与与A是是同同一一个个标标识识符符，或或者者

15、B的的现现行行值值在在执执行行四四元元式式A:=B op C之之后后不不会会再再引引用用，则则选选取取Ri为为所所需需要要的的寄寄存存器器R，并转并转4；2 如如果果有有尚尚未未分分配配的的寄寄存存器器，则则从从中中选选取取一一个个Ri为所需要的寄存器为所需要的寄存器R，并转并转4；3 从从已已分分配配的的寄寄存存器器中中选选取取一一个个Ri为为所所需需要要的的寄寄存器存器R。最好使得最好使得Ri满足一下条件：满足一下条件：占占用用Ri的的变变量量的的值值也也同同时时存存放放在在该该变变量量的的贮贮存存单单元元中中，或或者者在在基基本本块块中中要要在在最最远远的的将将来来才才会会引用到或不会引

16、用到。引用到或不会引用到。对对RVALUERi中中每每一一变变量量M，如如果果M不不是是A，或或 者者 如如 果果 M是是 A又又 是是 C，但但 不不 是是 B并并 且且 B也也 不不 在在 RVALUERi中，则中，则(1)如如果果AVALUEM不不包包含含M，则则生生成成 目目标标代代码码 ST Ri，M(2)如果如果M是是B，或者或者M是是C但同时但同时B也在也在RVALUERi中，则令中，则令AVALUEM=M，Ri，否则令，否则令AVALUEM=M(3)删除删除RVALUERi中的中的M 4 给出给出R，返回。返回。例：基本块例：基本块1.T:=A-B2.U:=A-C3.V:=T+U4.W:=V+U设设W是是基基本本块块出出口口之之后后的的活活跃跃变变量量，只只有有R0和和R1是是可可用用寄寄存存器器，生生成成的的目目标标代代码码和和相相应应的的RVALUE和和AVALUE:中间代码中间代码 目标代码目标代码 RVALUE AVALUET:=ABU:=ACV:=TUW:=VULD R0，ASUB R0，BR0含有含有TT在在R0中中LD R1，ASUB R1，CR0含有含有TR1含有含有UT在在R0中中U在在R1中中ADD R0，R1R0含有含有VR1含有含有UV在在R0中中U在在R1中中ADD R0，R1R0含有含有WW在在R0中中