资源描述：
《编译原理课件cha.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第十一章目标代码生成（1）源程序编译前端中间代码代码优化中间代码代码生成器目标程序符号表代码生成器的位置第十一章目标代码生成代码生成器的输入包括中间代码和符号表中的信息。目标代码一般有以下三种形式：（1）能独立执行的机器语言代码，所有地址均以定位（代真）。（2）待装配的机器语言模块。当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码。（3）汇编语言代码，尚须经过汇编程序汇编，转换成可执行的机器代码。代码生成器着重考虑两个问题:一是如何使生成的目标代码较短；另一个是如何充分利用计算机的寄存器，减少目
2、标代码中访问存储单元的次数。这两个问题直接影响代码的执行速度。第十一章目标代码生成基本问题:所有代码生成器都要面对何种中间代码输入,（是式逆波兰，四元式，还是三元式？等问题）何种代码做为目标程序,选择适当的代码指令,最优的寄存器分配方案,和计算顺序等基本问提.为此本书见立了目标机器模型:并把中间代码对应的目标代码做了规定.利用待用信息,寄存器描述数组RVALUE,变量地址描述数组AVALUE等概念建立了代码生成算法.P316[例11。2]同学们应该好好研究。P317表11。4各中间代码对应的目标代码应该背过。寄存器分配：利用执行代
3、价的概念说明如何建立更佳的寄存器分配方案。对于循环L中某变量M，如果分配一个寄存器给它专用，那么，每执行循环一次，执行代价的节省数可用公式（11。1）计算。这个计算公式应该掌握。第十一章目标代码生成[例11。3]图11。4代表某程序的最内层循环，其中无条件转移和条件转移指令均以改用箭头来表示。各基本块入口之前和出口之后的活跃变量已列在图中。假定R0,R1和R2三个寄存器在该循环中将固定分配给某三个变量使用。现在，我们利用公式（11。1）计算各变量的执行代价节省数，并且取执行代价节省数最高的来确定这三个变量。解：因为B1中引用a前已
4、对a定值，所以use(a,B1)=0;在B2,B3中a被各引用一次，且在引用前未对a定值，所以use(a,B2)=use(a,B3)=1;B4中未引用a，所以use(a,B4)=0.因为a在B1中被定值且a在B1出口是活跃的，a在B2,B3和B4出口后不是活跃的则：live(a,B1)=1Live(a,B2)=live(a,B3)=live(a,B4)=0;所以代价节省数为：1+1+2*1=4。第十一章目标代码生成同样可以算出b,c,d,e,f的执行代价节省数分别为：6，3，6，4，4。按照代价节省数的大小我们把寄存器R0分配给d
5、,R1分配给b;a,e,f的执行代价相同,可人选其一将R2分配给a.DAG的目标代码为了生成更有效的目标代码，要考虑的另一个问题是，对基本块中中间代码序列，我们应按怎样的次序来生成其目标代码呢？本节P323给出了利用基本块的DAG图给出了基本块中中间代码序列排序的方法，以便生成较优的目标代码。下面我们学习一个例子，一加深其理解：[例11。6]考察下面中间代码序列G1:第十一章目标代码生成T1:=A+BT2:=A-BF:=T1*T2T1:=A-BT2:=A–CT3:=B-CT1:=T1*T2G:=T1*T3其对应的DAG如图ABC+
6、n1--n2n4T2**-Fn3*Gn7T3n5T1n6A第十一章目标代码生成上图的DAG含有7个结点，我们应用课本中的算法。把它们排序，主要步骤如下。第一步置初值：i=7；T的所有元素全为空null。内部结点n3和n7均满足第三步的要求，假定我们选取T[7]为结点n3。结点n3的最左子结点（内部）n1满足第5步的要求，因此按第6步，T[6]=n1.但n1的最左子结A为叶结，不满足第6步的要求。则现在只有n7满足第3步要求，于是T[5]=n7。结点n7的最左子结n6满足第5步的要求，因此T[4]=n6。结点n6的最左子结点n2同样
7、满足第5步的要求，因此T[3]=n2.余下的满足第3步要求的尚有n4和n5，假定选取T[2]=n4。当把n5列为T[1]后，算法工作结束。至此，我们求出的图的内结点顺序为：n5,n4,n2,n6,n1,n3.按这个次序从新表示中间代码序列为G1‘为：T3:=B-C;T2:=A-C;S1:=A–B;T1:=S1*T2;G:=T1*T3;S2:=A+B;F:=S2*S1。如前所述按后一个中间代码序列生成中间代码将会较优。第十一章目标代码生成窥孔优化几种窥孔优化的方法都比较好理解，这里不再重述课本内容。第十一章目标代码生成例题与习题解答
8、[例11。1]假设只有R0和R1两个寄存器，对赋值语句d=(a-b)+(a-c)+(a-c)生成目标代码。并写出寄存器描述数组RVALUE和变量地址描述数组AVALUE.该赋值语句的三地址序列：t:=a-bt1:=a-ct2:=t+t1d:=t1+
