《学时数及其分布》由会员分享，可在线阅读，更多相关《学时数及其分布（15页珍藏版）》请在金锄头文库上搜索。
1、 目标代码生成 源程序编译前端中间代码代码优化中间代码代码生成器目标程序符 号 表代码生成器的位置代码生成器的输入包括中间代码和符号表中的信息 。目标代码一般有以下三种形式：（1）能独立执行的机器语言代码，所有地址均以定位 （代真） 。（2）待装配的机器语言模块。当需要执行时，由连接 装入程序把它们和某些运行程序连接起来，转换成能 执行的机器语言代码。 （3）汇编语言代码，尚须经过汇编程序汇编，转换成可 执行的机器代码。代码生成器着重考虑两个问题: 一是如何使生成的 目标代码较短；另一个是如何充分利用计算机的寄存 器，减少目标代码中访问存储单元的次数。这两个问 题直接影响代码的执行速度。n基本
2、问题:所有代码生成器都要面对何种中间代码输入 , （是式逆波兰，四元式，还是三元式？等问 题）何种代码做为目标程序,选择适当的代码指令,最 优的寄存器分配方案,和计算顺序等基本问提.n为此本书见立了目标机器模型:并把中间代码对应的目 标代码做了规定.利用待用信息,寄存器描述数组 RVALUE,变量地址描述数组AVALUE等概念建立了代码生 成算法.P316例11。2同学们应该好好研究。P317 表11。4 各中间代码对应的目标代码应该背过 。n寄存器分配：利用执行代价的概念说明如何建立更佳 的寄存器分配方案。对于循环L中某变量M，如果分配一个寄存器给它 专用，那么，每执行循环一次，执行代价的节
3、省数可 用公式（11。1）计算。这个计算公式应该掌握。例11。3图11。4代表某程序的最内层循环，其中无条 件转移和条件转移指令均以改用箭头来表示。各基本 块入口之前和出口之后的活跃变量已列在图中。假定 R0,R1和R2三个寄存器在该循环中将固定分配给某三个 变量使用。现在，我们利用公式（11。1）计算各变量 的执行代价节省数，并且取执行代价节省数最高的来 确定这三个变量。解：因为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
4、中被定值且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, R1分配给b; a,e,f 的执行代价相同,可人选 其一将R2分配给a. nDAG的目标代码为了生成更有效的目标代码，要考虑的另一个问题是， 对基本块中中间代码序列，我们应按怎样的次序来生 成其目标代码呢？本节P323给出了利用基本块的DAG 图给
5、出了基本块中中间代码序列排序的方法，以便生 成较优的目标代码。下面我们学习一个例子，一加深其理解：例11。6 考察下面中间代码序列 G1:T1 := A+BT2 := A- BF := T1 * T2T1 := A- BT2 := A CT3 := B - CT1 := T1 * T2G := T1 * T3 其对应的DAG如图A AB BC C+ +n1n1- - -n2n2 n4n4T2T2* * *- -F Fn3n3* *G Gn7n7T3T3 n5n5T1T1n6n6A A上图的DAG含有7个结点，我们应用课本中的算法。把它 们排序，主要步骤如下。第一步置初值： i = 7； T的所
6、有元素全为空null。内部 结点n3和n7均满足第三步的要求，假定我们选取T7为 结点n3。结点n3的最左子结点（内部）n1满足第5步的要 求，因此按第6步，T6=n1.但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, n3.按这个次序从新表示中间代码序
7、列为G1为：T3 := B-C ; T2 := A- C ; S1 := A B ; T1 := S1 * T2;G := T1 * T3; S2 := A + B ; F := S2 * S1 。如前所述按后 一个中间代码序列生成中间代码将会较优。n 窥孔优化几种窥孔优化的方法都比较好理解，这里不再重述课本 内容。例题与习题解答例11。1假设只有R0和R1两个寄存器，对赋值语句d = (a-b) + (a-c) + (a-c)生成目标代码。并写出寄存器描 述数组RVALUE和变量地址描述数组AVALUE.该赋值语句的三地址序列：t := a-bt1 := a-ct2 := t + t1d :
8、= t1 + t2 将此代码看成一基本块，并设在基本块末尾，变量 d是活跃的。生成目标代码表如图：中间代码 目标代码 RVALUE AVALUEt :=a-b LD R0, a R0 含 t t在 R0 中SUB R0, bt1 :=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为可用寄存器，试对以下各表达式分
9、 别生成最优目标代码。A+ (B+( C *( D + E/F + G)* H ) + ( I * J ) 解：首先生成三地址中间代码序列：T1 := E/FT2 := D + T1T3 := G + T2T4 := C * T3T5 := H * T4T6 := B + T5T7 := A + T6T8 := I * JT9 := T7 + T8最优的目标代码：LD R0, EDIV R0, FADD R0, GMUL R0, HMUL R0, CADD R0, BADD R0, ALD R1, IMUL R1, JADD R0,R1 例11。3（K1）对以下中间代码序列 G :T1 :=
10、B CT2 := A * T1T3 := D + 1T4 := E FT5 := T3 * T4W := T2/T5假设可用寄存器为R0和R1，W是基本块出口的活 跃变量，用简单代码生成算法生成目标代码，同时列 出代码生成过程中的寄存器描述和变量地址描述。中间代码 目标代码 RVALUE AVALUE T1:=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 中 ADD R1, #
11、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和存储器 中第十二章并行编译基础 并行计算机是近二十几年来发展迅速的一类计算 机。并行编译系统已经成为了现代高性能计算机系 统中一个重要的部分。并行程序设计主要有两种途 径，即使用并行程序设计语言编写并行程序，或将 串行程序并行化。因此，并行编译系统就是能够处 理并程序设计语言，能够实现串行程序并行化。具 有并行优化能力的编译系统。在这个问题上我们只 是要求了解。
