第11 章目标代码生成.docx
- 文档编号:3509227
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:17
- 大小:36.89KB
第11 章目标代码生成.docx
《第11 章目标代码生成.docx》由会员分享,可在线阅读,更多相关《第11 章目标代码生成.docx(17页珍藏版)》请在冰点文库上搜索。
第11章目标代码生成
第十一章目标代码生成
知识结构:
代码生成概述
可执行机器代码
目标代码的形式汇编语言代码
目标代码生成机器语言浮动模块
目标机器模型
代码生成算法
第一节基本问题
一、研究目标代码生成的关键问题
充分利用硬件的有效资源生成有效的目标代码。
1、生成目标代码时如何选择指令,使生成的目标代码较短。
例:
三地址代码a:
=a+1翻译为:
LDR0,a或INCa
ADDR0,#1
STR0,a
2、如何充分利用寄存器,减少目标代码访问内存次数
二、目标代码的形式
1、可执行机器代码(静态定位)。
特点:
占用存储空间的固定位置,生成目标代码,就可直接执行;
不能进行各模块的独立编译,对源程序只能一次性编译;
灵活性较差。
2、机器语言浮动模块,由连接程序把某些运行程序连接起来,转换成机器语言。
特点:
生成目标代码有较大的灵活性,可以随机分配内存;
连接是消耗一些系统时间。
3、汇编语言代码。
特点:
是从汇编语言到目标代码的转换,实现比较容易,并有利于软件移植;
需要两次翻译过程。
三、代码生成器的输入
代码生成器的输入包括源程序的中间表示以及符号表中的信息。
1、利用符号表中的信息来决定在中间代码中的名字所指示的数据对象的运行地址。
符号表+优化后中间代码
代码生成器
目标程序
例X:
=Y+Z其中:
X,Y,Z对应的地址分别为t0,t0+1,t0+2。
符号表
t0
t0+1
t0+2
地址
X
Y
Z
LDR0,Y—取数
ADDR0Z
STR0X—送数
2、在语义检查时发现了一些明显的错误,并加入了类型转换操作,可假设代码生成阶段的输入没有错误。
四、指令的选择
生成的代码质量取决于它的速度和大小,因此,指令集的一致性和完整性,指令速度和机器用语是非常重要的。
五、寄存器分配
如何充分利用寄存器,对于生成好的代码是非常重要的。
1、在寄存器分配期间,为程序的某一点选择驻留在寄存器中的一组变量;
2、在随后的寄存器指派阶段,挑出变量将要驻留的具体寄存器。
六、计算顺序选择
计算的顺序会影响目标代码的有效性和代码的执行效率。
第二节目标机器的模型
要设计一个好的代码生成器,必须预先熟悉目标机器和它的指令系统。
一、硬件设置
1、主存器;
2、字长;
3、寄存器。
二、指令系统
1、传送指令;
2、运算指令(算术运算,逻辑运算);
3、比较指令;
4、控制指令。
假设计算机指令
指令
意义
LDRi,B
STRi,B
JX
CMPA,B
J J≤X J=X J≠X J>X J≥X 把B单元的内容取到寄存器R,即(B)Ri 把寄存器Ri的内容存到B单元,即(Ri)B 无条件转向X单元 单元A与单元B比较,并根据比较情况把机器内部特征寄存器CT置成相应状态。 CT占两个二进位。 根据A 如CT=0,转X单元 如CT=0或CT=1转X单元 如CT=1转X单元 如CT≠1转X单元 如CT=2转X单元 如CT=2或CT=1转X单元 以上指令中运算符op包括一般计算机上常见的一些运算符,如ADD、SUB、MUL、DIV等等, 三、寻址方式 假设机器的寻址方式 类型 指令形式 意义(设op是二目运算符) 直接地址型 寄存器型 变址型 间接型 opRi,M opRi,Rj opRi,c(Rj) opRi,*M opRi,*Rj opRi,*c(Rj) (Ri)op(M)Ri (Ri)op(Rj)Ri (Ri)op((Rj)+c)Ri (Ri)op((M))Ri (Ri)op((Rj))Ri (Ri)op((Rj)+c)Ri 例1: STR0,M表示把寄存器R0的内容存到M单元,即 (Ri)M 例2: STR0,4(R1)表示把寄存器R0的内容存到(4+(R1))单元,此为变址指令 例3: LDR0,*4(R1)表示把(4+(R1))所指的单元的内容存到寄存器R0中,此为间址指令 例4: STR0,#1表示把常数1存到寄存器R0中。 第三节一个简单的代码生成器 一、代码生成器的任务 把每条中间代码变换成目标代码,并考虑在基本块内,充分利用寄存器的优化。 实现策略: 当前操作数在寄存器中直接引用,不在产生访问主存的目标代码; 应尽可能使执行的结果保留在寄存器中; 需要释放寄存器产生转存贮器的目标代码; 对于X: =Y+Z一般翻译为: LDR0,Y ADDR0,Z STR0,X 目标代码应尽量减少访问主存次数,可以提高目标代码的运行速度,为此要充分利用寄存器来保存变量的值和中间结果。 二、使用寄存器的算法 1、在基本块中,当生成计算某变量值的目标代码时,尽可能地让该变量的值保留在寄存器中,直到该寄存器必须用来存放新的值或者到达基本块出口为止; 2、后续的目标代码尽可能地引用变量在寄存器中的值,而不访问主存; 3、到达基本块的出口,把寄存器的值存到主存器的指令。 例: A: =(B+C)*D+E把它翻译为中间代码为: T1: =B+C T2: =T1*D A: =T2+E 翻译成目标代码序列为: (1)LDR,B (2)ADDR,C (3)STR,T1 (4)LDR,T1 (5)MULR,D (6)STR,T2 (7)LDR,T2 (8)ADDR,E (9)STR,A 考虑了效率和充分利用寄存器的问题之后,代码生成器就可以生成如下代码: (1)LDR,B (2)ADDR,C (3)MULR,D (4)ADDR,E (5)STR,A 三、活跃变量和待用信息 1、活跃变量 某变量A在程序中某点p是活跃变量(或称A在点p是活跃的),是指A的值要在从p开始的某通路上被引用。 (p)A: =BopC或(p)B: =AopC 活跃活跃 (q)T: =AopV(q)T: =AopV A的值在(q)点被引用。 2、待用信息 表示变量的值在后面的中间代码中任何处被引用。 (i)A: =BopC …无对A再定值 (j)X: =AopD 称(j)是(i)的下一个引用点(或称j是i的变量A的待用信息,A在点i是活跃的)。 上例中,点q是变量A的待用信息,或称A在点p是活跃的。 一般将临时变量均看作基本块出口之后的非活跃变量,非临时变量均看作基本块出口之后的活跃变量. 3、建立待用信息链和活跃变量信息链 可以从基本块的出口,由后向前把基本块中每个变量建立待用信息链和活跃变量信息链。 算法如下: 开始时,把基本块中各变量的符号表登记项的待用信息栏填写“非待用”,并根据该变量选择基本块的出口之后是不活跃的,把其中活跃信息栏填写“非活跃”。 从基本块的出口到基本块入口由后向前依次处理各中间代码。 对每个中间代码(i)A: =BopC,依次执行下述步骤: ①把符号表中变量A的待用信息和活跃信息附加到中间代码i上; ②把符号表中变量A的待用信息和活跃信息分别置为“非待用”和“非活跃”; ③把符号表中变量B和C的待用信息和活跃信息附加到中间代码i上; ④把符号表中变量B和C的待用信息均置为i,活跃信息均置为“活跃”。 例: 有一基本块中间代码为: T: =A-B U: =A-C V: =T+U W: =V+U 变量的符号表中待用信息、活跃信息 T(非,非)(3,y)(非,非) A(非,非)(2,y)(非,非) B(非,非)(1,y) C(非,非)(2,y) U(非,非)(4,y)(3,y)(非,非) V(非,非)(4,y)(非,非) W(非,y)(非,非) (1)T: =A-B 3,y2,y非,非 (2)U: =A-C 3,y非,非非,非 (3)V: =T+U 4,y非,非4,y (4)W: =V+U 非,y非,非非,非 注: j,y表示j点引用,非活跃变量。 四、寄存器和地址描述 1、寄存器描述数组(Rvalue) 记录可用寄存器的现行使用情况,并对寄存器的分配作出确定的判断。 了解当前未被占用的寄存器; 了解当前被占用的寄存器所分配的变量。 分配的变量 R0 A R1 (空闲) R2 B 2、变量地址描述数组(Avalue) 动态记录目标程序运行时,变量现行值存放的位置。 寄存器 主存 A R0 在 B R2 C 在 五、代码生成算法(P315) 对于中间代码(i)A: =BopC 1、调用GETREG((i)A: =BopC),得到一个寄存器R存放A。 2、查找Rvalue和Avalue若B,C在B′,C′中。 3、如果B′≠R,则生成目标代码: LDR,B′ opR,C′ 若B′为寄存器,则生成目标代码: opR,C′ 4、令Avalue[A]={R},Rvalue[R]={A} 5、如果B和C的值在基本块中不再被引用,也不是基本块出口之后的活跃变量,并且其值在某个寄存器Rk中,则删除RVALUE[Rk]中的B或C以及AVALUE[B]中的Rk,使寄存器不再为B或C所占用。 GETREG是一个函数过程,GETREG((i)A: =BopC)给出一个用来存放A的当前值的寄存器R,其中要用到中间代码i上的待用信息。 GETREG的算法如下: 如果B的现行值在某个寄存器Ri中,RVALUE[Ri]只包含B此外,或者B与A是同一标识符,或者B的现行值在执行中间代码A: =BopC之后不会再引用(此时,该中间代码i的附加信息中,B的待用信息和活跃信息分别为“非待用”和“非活跃”),则选取Ri为所需的寄存器R,并转 。 如果有尚未分配的寄存器,则从中选取一个Ri为所需的寄存器R,并转 。 从已分配的寄存器中选取一个Ri为所需的寄存器R,Ri满足以下条件: 占用Ri变量的值,同时存放在该变量主存单元中。 对RVALUE[Ri]中每一变量M,如果M不是A,或者如果M是A又是C,但不是B并且B也不在RVALUE[Ri]中,则: 如果AVALUE[M]不包含M,则生成目标代码STRi,M; 如果M是B,或者M是C但同时B也在RVALUE[Ri]中,则令AVALUE[M]={M}; 删除RVALUE[Ri]中的M; 给出R,返回。 中间代码 目标代码 RVALUE AVALUE T: =A-B LDR0,A SUBR0,B R0含有T T在R0中 U: =A-C LDR1,A SUBR1,C R0含有T R1含有U T在R0中 U在R1中 V: =T+U ADDR0,R1 R0含有V R1含有U V在R0中 U在R1中 W: =V+U ADDR0,R1 Ro含有W W在R0中 序号 中间代码 目标代码 备注 1 A: =BopC LDRi,B opRi,C 其中Ri是新分配给A的寄存器 如果B和/或C的现行值在寄存器中, 则目标中B和/或C用寄存器表示。 但如果C的现行值在Ri中,而B 的现行值不在Ri中,则C要用其 主存单元表示。 如果B的现行值也在Ri中, 则不生成第一条目标代码。 2 A: =op1B LDRi,B op1Ri,Ri 同1中备注 (1) 同1中备注(3) op1指一目运算符 3 A: =B LDRi,B 同1中备注 (1) 如果B的现行值在Ri中, 则如前所述,不生成目标代码 4 A: =B[I] LDRj,I LDRi,B(Rj) 同1中备注 (1) 如果I的现行值在Rj中, 则不生成第一条目标代码, 否则Rj是新分配给I的寄存器 5 A[I]: =B LDRi,B LDRj,I STRi,A(Rj) 同1中备注(3) 同4中备注 (2) 6 gotoX JX’ X’是标号为X的中间代码的目标代码的首地址 7 IfAropBgotoX LDRi,A CMPRi,B JropX’ X’的意义同6中备注 (1) 若A的现行值在Ri中,则不生成第一条目标代码 如果B的现行值也在Ri中,则目标代码中的B就是Ri rop指<,,=,,>或 8 A: =P LDRi,*P 同1中备注 (1) 9 P: =A LDRi,A STRi,*P 同1中备注 (1) 如果A的现行值在Ri中,则不生成第一条目标代码。 第四节寄存器分配 为了生成更有效的目标代码,需要考虑的一个问题就是如何更有效的利用寄存器,寄存器分配的策略: 1、把寄存器尽量优先分配给引用频繁的变量独占; 2、把寄存器作为操作数地址; 3、把变量的现行值保存在寄存器中。 一、执行代价算法(P318) 执行代价=每条指令访问主存单元次数+1 1、仅当变量在基本块中被定值时,其值才存放在寄存器中。 把寄存器分配给某变量使用,当该变量在基本块中被定值前,每引用一次,就可少访问一次主存,执行代价就节省1。 2、如果某变量在基本块中被定值且在基本块出口之后是活跃的,出在基本块时,就无须把它的值存放到主存单元中,执行代价就节省2。 3、计算公式(略) 二、执行代价计算注意的问题 1、变量是活跃的,在入口先把它的值从主存单元取到寄存器,执行代价为2,可忽略不计。 2、对于循环程序每循环一次,由于执行路径的不同,在计算执行代价时,认为循环体中的个基本块都被执行一次,可忽略不计。 三、循环中的目标代码生成算法 1、凡涉及到已固定分配到寄存器的变量,用寄存器表示; 2、某变量在循环入口之前是活跃的,在循环入口之前产生把结果值存入寄存器的目标代码。 3、某变量在循环出口是活跃的,在循环出口产生把寄存器的结果存入主存的目标代码。 4、在循环中的每个基本块出口,对没固定分配到寄存器的变量,产生把寄存器的结果存入主存的目标代码。 5、对已固定分配到寄存器的变量,在循环中某基本块出口不是活跃的可释放,作一般寄存器使用。 思考题: P3271。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第11 章目标代码生成 11 目标 代码 生成