第12章 代码生成

1、第12章代码生成,代码生成要考虑的主要问题基本块的代码生成(在一个基本块范围内考虑如何充分利用寄存器的问题)PL/0相关的代码生成从DAG生成代码（略）,具体细节依赖于目标机器和操作系统共同的问题：1.充分利用寄存器基本块中全局寄存器分配：不把寄存器平均分配给各个变量使用，而是从可用的寄存器中分出几个，固定分配给几个变量单独使用。标准以各变量在循环内需要访问主存单元的次数为标准。2.选择计算机指令系统3.选择计算次序,代码生成需要考虑的主要问题,P276,3,目标代码的三种形式,(1)地址代真的机器代码(2)待装配的机器代码模块(3)汇编语言（宏汇编）机器指令形式(opsource,desti

2、nation)ADDs,d/d+sSUBs,d/d-sMOVs,d/sd机器指令开销(cost)MOVR,M开销2ADD#1,R开销2MOVR0,R1开销1,目标机器的地址方式,地址方式,形式,地址,开销,直接地址,M,M,1,寄存器,R,R,0,间接寄存器,*R,contents(R),0,索引(变址),c(R),c+contents(R),1,间接索引(变址),*c(R),Contents(c+contents(R),1,例a:=b+c1.MOVb,R0ADDc,R0cost=6MOVR0,a2.假定R0、R1和R2中分别包含a、b和c的地址:MOV*R1,*R0ADD*R2,*R0cos

3、t=23.假定R1和R2中分别包含b和c的值,并且b的值在这个赋值以后不再需要,则还可有ADDR2,R1MOVR1,acost=3,例T4:=A+B-(E-(C+D),T1:=A+BMOVA,R0T2:=C+DADDB,R0T3:=E-T2MOVC,R1T4:=T1-T3ADDD,R1MOVR0,T1MOVE,R0SUBR1,R0MOVT1,R1SUBR0,R1MOVR1,T4,例,T2:=C+DMOVC,R0T3:=E-T2ADDD,R0T1:=A+BMOVE,R1T4:=T1-T3SUBR0,R1MOVA,R0ADDB,R0SUBR1,R0MOVR0,T4,在一个基本块内考虑如何充分利用寄

4、存器：l尽可能地让该变量的值保留在寄存器中l尽可能引用变量在寄存器中的值l对于基本块内不再被引用的变量迟早释放。,简单的代码生成器（基本块内）,定值：假如有四元式i：ABopC则称A在四元式i中被定值，i是A的定值点。在一个基本块内，对A的引用仅仅发生在定值点之后。但对A允许多次定值，并且多次引用。,待用信息：若在一个基本块中，在i后面的四元式j中要引用A值，且从i到j之间没有其它对A的定值点，这时我们称j是四元式i中对变量A的待用信息或称下次引用信息，同时也称A是活跃的。若A被多处引用，则可构成待用信息链与活跃信息链。可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃信息链。

5、,假如有四元式i：ABopC,对所有变量的两栏置初值：“待用信息”栏全部置为“非待用”，记为F“活跃信息”栏按在基本块出口处是否为活跃而置成“活跃”（L）或“非活跃”（F）。假定变量都是活跃的，临时变量都是非活跃的。在计算过程中，对于有“待用信息”的变量，直接标记相应的四元式序号,符号表中增加“待用信息”栏和“活跃信息”栏,计算待用信息的算法,从基本块出口到入口由后向前依次处理每个四元式。对每个四元式i:A:=BopC，执行下述步骤：a)把符号表中变量A的待用信息和活跃信息附加到四元式上。b)把符号表中变量A的待用信息栏和活跃信息栏分别置为“非待用”和“非活跃”。（由于在i中对A的定值只能在i

6、以后的四元式才能引用，因而对i以前的四元式来说，A是不活跃也不可能是待用的）。c)把符号表中变量B和C的待用信息和活跃信息附加到四元式i上。d)把符号表中变量B和C的待用信息栏置为“i”，活跃信息栏置为“活跃”。注意，以上a)和b)，c)和d)的次序不能错乱。,若用A，B，C和D表示变量，用T，U，V表示中间变量，有四元式如下：(1)T:=A-B(2)U:=A-C(3)V:=T+U(4)D:=V+U其名字表中的待用信息和活跃信息如下表，用“F”表示“非待用”或“非活跃”，用“L”表示“活跃”。(1)(2)(3)(4)表示四元式序号。,例：,其中假定d在基本块的出口是活跃的。,例,代码序列,语句

7、,生成的代码,寄存器描述器,地址描述器,t:=a,b,MOVa,R0,SUBb,R0,空寄存器,t在R0中,u:=a,c,MOVa,R1,SUBc,R1,v:=t,u,ADDR1,R0,d:=v,u,STR1,d,d在R0中和存储器中,t在R0中,u在R1中,u在R1中,v在R1中,d在R0中,R0包含t,R0包含t,R1包含u,R1包含u,R0包含v,R0包含d,ADDR1,R0,从DAG生成目标代码,四元式序列GT1:=A+BT2:=C+DT3:=E-T2T4:=T1-T3,DAG:,ABE,CD,n9,n3,n8,n1,n2,n7,n6,n4,n5,T4,T1,T3,T2,+,-,-,+

8、,例：赋值语句T4:=A+B-(E-(C+D),T4:=A+B-(E-(C+D),T1:=A+BMOVA,R0T2:=C+DADDB,R0T3:=E-T2MOVC,R1T4:=T1-T3ADDD,R1MOVR0,T1MOVE,R0SUBR1,R0MOVT1,R1SUBR0,R1MOVR1,T4,T4:=A+B-(E-(C+D),T2:=C+DMOVC,R0T3:=E-T2ADDD,R0T1:=A+BMOVE,R1T4:=T1-T3SUBR0,R1MOVA,R0ADDB,R0SUBR1,R0MOVR0,T4原因：T4的计算紧跟在T1之后,尽量使结点的求值紧接其最左变量的求值之后启发式排序算法(1

9、)while存在未列入表的内部结点do(2)begin选取一个未列入表的但其全部父结点均已列入表的结点n;(3)将n列入表中;(4)whilen的最左子结点m不是叶结点并且其所有父结点均已列入表中do(5)begin将m列入表中;(6)n:=m(7)end(8)end,T8:=d+eT6:=a+bT5:=T6-cT4:=T5*T8T3:=T4-eT2:=T6+T4T1:=T2*T3,例:ai:=b+1,:=,ind,+,memb,const1,ind,+,consti,regsp,consta,regsp,+,+,基于树重写的代码生成,regi,+,ADDRj,Ri,regi,regj,(1)

10、,regj,constc,MOV#c,Rj,(2),regi,mema,MOVa,Ri,(3),mem,MOVRi,a,(4),mem,MOVRj,*Ri,(5),MOVc(Rj),Ri,:=,mema,regi,:=,ind,+,mema,regj,regi,constc,regi,regj,(6),regi,ADDc(Rj),Ri,(7),(8),INCRi,+,regi,ind,constc,regj,+,cost1,ADDRj,Ri,regi,regi,regi,regi,regj,+,+,(1),reg0,consta,MOV#a,R0,(7),reg0,ADDSP,R0,+,:=,

11、ind,memb,const1,ind,consti,regsp,reg0,reg0,regsp,+,+,+,MOV#a,R0ADDSP,R0ADDi(SP),R0MOVb,R1INCR1MOVR1,*R0,l命令式或过程式语言l应用式(Applicative)或函数式应用式语言：Lisp和ML语法：functionn(function2(function1(data)逐个函数应用在数据上的变换，最终得到一个结果。l基于规则(rule_based)和面向对象(object_oriented)程序执行是通过检查使能条件，决定执行适当动作。语法：使能条件1动作1使能条件2动作2.使能条件n动作n如

12、prolog,补充内容：程序设计语言的计算模型,已经成为越来越重要的计算模式；面向对象的程序设计语言支持抽象数据类型和继承性，即将数据和对数据的操作放在一起，定义一组具有公共行为属性和数据类型的对象，由类机制将这组对象给予抽象表示。,O-O程序设计,四种应用环境：批处理环境，交互环境，嵌入式系统和编程环境,l,批处理环境：一个程序输入一组数据文件，处理这些数据，然后生成一组输出文件。,l,交互环境：程序在执行过程中直接和用户在显示控制台上交互，不断从键盘或鼠标接受输入，将输出发送到显示器上。,l,嵌入式系统环境：1.没有操作系统，没有文件，直接和非标准的I/O设备交互；2.出错处理非常重要；3.常常是实时地操作；4.常常是一个分布式系统（并行）,描述并行任务的语言并行编译系统,语言