第十一章目标代码生成(1).ppt

《第十一章目标代码生成(1).ppt》由会员分享，可在线阅读，更多相关《第十一章目标代码生成(1).ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十一章目标代码生成（第十一章目标代码生成（1 1）源程序编译前端中间代码代码优化中间代码代码生成器目标程序符 号 表 代码生成器的位置代码生成器的位置第十一章 目标代码生成 代码生成器的输入包括中间代码和符号表中的信息。代码生成器的输入包括中间代码和符号表中的信息。目标代码一般有以下三种形式：目标代码一般有以下三种形式：（1 1）能独立执行的机器语言代码，所有地址均以定位）能独立执行的机器语言代码，所有地址均以定位（代真）（代真）。（2 2）待装配的机器语言模块。当需要执行时，由连接）待装配的机器语言模块。当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能装入程序把它们和某些

2、运行程序连接起来，转换成能执行的机器语言代码。执行的机器语言代码。（3 3）汇编语言代码，尚须经过汇编程序汇编，转换成可）汇编语言代码，尚须经过汇编程序汇编，转换成可执行的机器代码。执行的机器代码。代码生成器着重考虑两个问题代码生成器着重考虑两个问题:一是如何使生成的一是如何使生成的目标代码较短；另一个是如何充分利用计算机的寄存目标代码较短；另一个是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数。这两个问器，减少目标代码中访问存储单元的次数。这两个问题直接影响代码的执行速度。题直接影响代码的执行速度。第十一章 目标代码生成基本问题基本问题:所有代码生成器都要面对何种中间代码输入所

3、有代码生成器都要面对何种中间代码输入,（是式逆波兰，四元式，还是三元式？等问题）（是式逆波兰，四元式，还是三元式？等问题）何种代码做为目标程序何种代码做为目标程序,选择适当的代码指令选择适当的代码指令,最优的最优的寄存器分配方案寄存器分配方案,和计算顺序等基本问提和计算顺序等基本问提.为此本书见立了目标机器模型为此本书见立了目标机器模型:并把中间代码对应的目并把中间代码对应的目标代码做了规定标代码做了规定.利用待用信息利用待用信息,寄存器描述数组寄存器描述数组RVALUE,RVALUE,变量地址描述数组变量地址描述数组AVALUEAVALUE等概念建立了代码生等概念建立了代码生成算法成算法.P

4、316P316例例1111。22同学们应该好好研究。同学们应该好好研究。P317 P317 表表1111。4 4 各中间代码对应的目标代码应该背过。各中间代码对应的目标代码应该背过。寄存器分配：利用执行代价的概念说明如何建立更佳寄存器分配：利用执行代价的概念说明如何建立更佳的寄存器分配方案。的寄存器分配方案。对于循环对于循环L L中某变量中某变量M M，如果分配一个寄存器给它如果分配一个寄存器给它专用，那么，每执行循环一次，执行代价的节省数可专用，那么，每执行循环一次，执行代价的节省数可用公式（用公式（1111。1 1）计算。这个计算公式应该掌握。）计算。这个计算公式应该掌握。第十一章 目标代

5、码生成 例例11。3图图11。4代表某程序的最内层循环，其中无条代表某程序的最内层循环，其中无条件转移和条件转移指令均以改用箭头来表示。各基本件转移和条件转移指令均以改用箭头来表示。各基本块入口之前和出口之后的活跃变量已列在图中。假定块入口之前和出口之后的活跃变量已列在图中。假定R0,R1和和R2三个寄存器在该循环中将固定分配给某三个三个寄存器在该循环中将固定分配给某三个变量使用。现在，我们利用公式（变量使用。现在，我们利用公式（11。1）计算各变量）计算各变量的执行代价节省数，并且取执行代价节省数最高的来的执行代价节省数，并且取执行代价节省数最高的来确定这三个变量。确定这三个变量。解：因为解

6、：因为B1中中引用引用a前已对前已对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)=1 Live(a,B2)=live(a,B3)=live(a,B4)=0;所以代价节省数所以代价节省数为：为：1+1+2*1=4。第十一章 目标代码生成 同样

7、可以算出同样可以算出b,c,d,e,f 的执行代价节省数分别为：的执行代价节省数分别为：6，3，6，4，4。按照代价节省数的大小我们把寄存器。按照代价节省数的大小我们把寄存器R0分配给分配给d,R1分配给分配给b;a,e,f 的执行代价相同的执行代价相同,可人选可人选其一将其一将R2分配给分配给a.DAG的目标代码的目标代码 为了生成更有效的目标代码，要考虑的另一个问题是，为了生成更有效的目标代码，要考虑的另一个问题是，对基本块中中间代码序列，我们应按怎样的次序来生对基本块中中间代码序列，我们应按怎样的次序来生成其目标代码呢？本节成其目标代码呢？本节P323给出了利用基本块的给出了利用基本块的

8、DAG图给出了基本块中中间代码序列排序的方法，以便生图给出了基本块中中间代码序列排序的方法，以便生成较优的目标代码。成较优的目标代码。下面我们学习一个例子，一加深其理解：下面我们学习一个例子，一加深其理解：例例11。6 考察下面中间代码序列考察下面中间代码序列 G1:第十一章 目标代码生成 T1:=A+B T2 :=A-B F :=T1*T2 T1:=A-B T2:=A C T3:=B-C T1:=T1*T2 G:=T1*T3其对应的其对应的DAG如图如图A A A AB B B BC C C C+n1n1n1n1-n2n2n2n2n4n4n4n4T2T2T2T2*-F F F Fn3n3n3

9、n3*G G G Gn7n7n7n7T3T3T3T3n5n5n5n5T1T1T1T1n6n6n6n6A A A A第十一章 目标代码生成 上图的上图的DAG含有含有7个结点，我们应用课本中的算法。把它个结点，我们应用课本中的算法。把它们排序，主要步骤如下。们排序，主要步骤如下。第一步置初值：第一步置初值：i=7；T的所有元素全为空的所有元素全为空null。内部内部结点结点n3和和n7均满足第三步的要求，假定我们选取均满足第三步的要求，假定我们选取T7为为结点结点n3。结点结点n3的最左子结点（内部）的最左子结点（内部）n1满足第满足第5步的要步的要求，因此按第求，因此按第6步，步，T6=n1.

10、但但n1的最左子结的最左子结A为叶结，为叶结，不满足第不满足第6步的要求。则现在只有步的要求。则现在只有n7满足第满足第3步要求，于步要求，于是是T5=n7。结点结点n7 的最左子结的最左子结n6满足第满足第5步的要求，因步的要求，因此此T4=n6。结点结点n6的最左子结点的最左子结点n2同样满足第同样满足第5步的要步的要求，因此求，因此T3=n2.余下的满足第余下的满足第3步要求的尚有步要求的尚有n4和和n5，假定选取假定选取T2=n4。当把当把n5列为列为T1后，算法工作结束。后，算法工作结束。至此，我们求出的图的内结点顺序为：至此，我们求出的图的内结点顺序为：n5,n4,n2,n6,n1

11、,n3.按这个次序从新表示中间代码序列为按这个次序从新表示中间代码序列为G1为：为：T3:=B-C ;T2:=A-C;S1:=A B;T1:=S1*T2;G:=T1*T3;S2:=A+B;F:=S2*S1。如前所述按后如前所述按后一个中间代码序列生成中间代码将会较优。一个中间代码序列生成中间代码将会较优。第十一章 目标代码生成 窥孔优化窥孔优化 几种窥孔优化的方法都比较好理解，这里不再重述课本几种窥孔优化的方法都比较好理解，这里不再重述课本内容。内容。第十一章 目标代码生成例题与习题解答例题与习题解答例11。1假设只有假设只有R0和和R1两个寄存器，对赋值语句两个寄存器，对赋值语句d=(a-b

12、)+(a-c)+(a-c)生成目标代码。并写出寄存器描生成目标代码。并写出寄存器描述数组述数组RVALUE和变量地址描述数组和变量地址描述数组AVALUE.该赋值语句的三地址序列：该赋值语句的三地址序列：t:=a-b t1:=a-c t2:=t+t1 d:=t1+t2 将此代码看成一基本块，并设在基本块末尾，变量将此代码看成一基本块，并设在基本块末尾，变量d是活跃的。生成目标代码表如图：是活跃的。生成目标代码表如图：第十一章 目标代码生成 中间代码中间代码 目标代码目标代码 RVALUE AVALUE t:=a-b LD R0,a R0 含含 t t在在 R0 中中 SUB R0,b t1:=

13、a-c LD R1,a R0含含t t在在R0中中 SUB R1,c R1含含t1 t1在在R1中中 t2:=t+t1 ADD R0,R1 R0含含t2 t2 在在R0中中 R1含含t1 t1在在R1中中d:=t1+t2 ADD R0,R1 R0含含d d在在R0中中 ST R0,d d在在R0和存储器中和存储器中 第十一章 目标代码生成例例11。2（k3）假设假设R0,R1 和和R2为可用寄存器，试对以下各表达式分为可用寄存器，试对以下各表达式分别生成最优目标代码。别生成最优目标代码。A+(B+(C*(D+E/F+G)*H)+(I*J)解：首先生成三地址中间代码序列：解：首先生成三地址中间代

14、码序列：T1:=E/F T2:=D+T1 T3:=G+T2 T4:=C*T3 T5:=H*T4 T6:=B+T5 T7:=A+T6 T8:=I*J T9:=T7+T8第十一章 目标代码生成 最优的目标代码：最优的目标代码：LD R0,E DIV R0,F ADD R0,G MUL R0,H MUL R0,C ADD R0,B ADD R0,A LD R1,I MUL R1,J ADD R0,R1例例11。3（K1）对以下中间代码序列对以下中间代码序列 G:第十一章 目标代码生成 T1:=B C T2:=A*T1 T3:=D+1 T4:=E F T5:=T3*T4 W:=T2/T5 假设可用寄存

15、器为假设可用寄存器为R0和和R1，W是基本块出口的活是基本块出口的活跃变量，用简单代码生成算法生成目标代码，同时列跃变量，用简单代码生成算法生成目标代码，同时列出代码生成过程中的寄存器描述和变量地址描述。出代码生成过程中的寄存器描述和变量地址描述。中间代码中间代码 目标代码目标代码 RVALUE AVALUET1:=B-C LD R0,B R0含含 T1 T1 在在 R0中中 SUB R0,C T2:=A*T1 MUL R0,A R0 含含 T2 T2 在在 R0 中中 ST R0,T2 T2同时在同时在R0和存储器中和存储器中T3:=D+1 LD R1,D R1 含含 T3 T3 在在 R1

16、 中中 第十一章 目标代码生成 ADD R1,#1 T4:=E-F LD R0,E R0含含 T4 T4 在在 R0 中中 SUB R0,F T5:=T3*T4 MUL R1,R0 R1含含 T5 T5 在在R1中中 LD R0,T2 R0含含T2 T2在在R0和存储器中和存储器中W:=T2/T5 DIV R0,R1 R0含含W W在在 R0中中 ST R0,W W在在R0和存储器和存储器中中第十一章 目标代码生成第十二章并行编译基础第十二章并行编译基础 并行计算机是近二十几年来发展迅速的一类计算并行计算机是近二十几年来发展迅速的一类计算机。并行编译系统已经成为了现代高性能计算机系机。并行编译系统已经成为了现代高性能计算机系统中一个重要的部分。并行程序设计主要有两种途统中一个重要的部分。并行程序设计主要有两种途径，即使用并行程序设计语言编写并行程序，或将径，即使用并行程序设计语言编写并行程序，或将串行程序并行化。因此，并行编译系统就是能够处串行程序并行化。因此，并行编译系统就是能够处理并程序设计语言，能够实现串行程序并行化。具理并程序设计语言，能够实现串行程序并行化。具有并行优化能力的编译系统。在这个问题上我们只有并行优化能力的编译系统。在这个问题上我们只是要求了解。是要求了解。第十一章 目标代码生成