第十二章代码生成 ·代码生成要考虑的主要问题 0 基本块的代码生成（在一个基本块范围内 考虑如何充分利用寄存器的问题) ·从dag生成代码
第十二章 代码生成 • 代码生成要考虑的主要问题 • 基本块的代码生成(在一个基本块范围内 考虑如何充分利用寄存器的问题) • 从dag生成代码
●代码生成要考虑的主要问题 具体细节依赖于目标机器和操作系统 共同的问题： 1.充分利用寄存器 基本块中 全局 寄存器分配：不把寄存器平均分配给各个变量使 用，而是从可用的寄存器中分出几个，固定分配给几个变量单 独使用。标准一以各变量在循环内需要访问主存单元的次数 为标准。 2.选择计算机指令系统 3.选择计算次序
l 代码生成要考虑的主要问题 ——具体细节依赖于目标机器和操作系统 共同的问题： 1. 充分利用寄存器 基本块中 全局 寄存器分配：不把寄存器平均分配给各个变量使 用，而是从可用的寄存器中分出几个，固定分配给几个变量单 独使用。标准——以各变量在循环内需要访问主存单元的次数 为标准。 2. 选择计算机指令系统 3. 选择计算次序
目标代码的三种形式 地址代真的机器代码 待装配的机器代码模块 汇编语言（宏汇编） 机器指令形式 (op source,destination) ADDS,d∥d+s SUB s,d //d-s MOV s,d /s→d 机器指令开销(cost) MOV R.M 开销2 ADD #1R 开销2 MOV RORI 开销1
目标代码的三种形式 地址代真的机器代码 待装配的机器代码模块 汇编语言（宏汇编） 机器指令形式 (op source ,destination) ADD s,d // d+s SUB s,d //d-s MOV s,d //s d 机器指令开销 (cost) MOV R,M 开销 2 ADD #1 ,R 开销 2 MOV R0,R1 开销 1
目标机器的地址方式 地址方式 汇编形式 地址 增加的开销 直接地址方式 M M 1 寄存器方式 R R 0 间接寄存器方式 *R contents(R) 0 索引方式 c(R) c+contents(R) 间接索引方式 *c(R) contents(c+contents(R))
目标机器的地址方式 地址方式 汇编形式 地址 增加的开销 直接地址方式 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+c 1.MOV b. Ro ADD c, o cost=6 MOV Ro a 2.MOV b, a ADD c, a cost=6 假定R,R,和R2中分别存放了a,b和c的地址，采 用： 3.MOV *R1 *Ro ADD *R2.*Ro cost=2 假定R,和R2中分别包含b和c的值，并且b的值在 这个赋值以后不再需要，则还可有 4.ADD R2,R MOV R1 、a cost=3
a:=b+c 1. MOV b, R0 ADD c, R0 cost=6 MOV R0 , a 2. MOV b, a ADD c, a cost=6 假定R0 , R1和R2中分别存放了a, b和c的地址, 采 用: 3. MOV *R1 , *R0 ADD *R2 , *R0 cost=2 假定R1和R2中分别包含b和c的值, 并且b的值在 这个赋值以后不再需要, 则还可有 4. ADD R2 , R1 MOV R1 , a cost=3
T4:=A+B-(E-(C+D) T1:=A+B MOV A,RO T2:=C+D ADD B.RO T3:=E-T2 MOV C,RI T4:=T1-T3 ADD D,R1 MOV R0,T1 MOV E,RO SUB R1,R0 MOV T1,RI SUB R0,R1 MOV R1,T4
T4:=A+B-(E-(C+D)) T1:= A+B MOV A,R0 T2:=C+D ADD B,R0 T3:=E-T2 MOV C,R1 T4:=T1-T3 ADD D,R1 MOV R0,T1 MOV E, R0 SUB R1,R0 MOV T1,R1 SUB R0,R1 MOV R1, T4
T2:=C+D MOV C,RO T3:=E-T2 ADD D,RO T1:=A+B MOV E,RI T4:=T1-T3 SUB RO,R1 MOV A,RO ADD B,RO SUB R1,R0 MOV RO,T4
T2:=C+D MOV C,R0 T3:=E-T2 ADD D,R0 T1:= A+B MOV E,R1 T4:=T1-T3 SUB R0,R1 MOV A,R0 ADD B, R0 SUB R1,R0 MOV R0,T4
简单的代码生成器（基本块内） 在一个基本块范围内考虑如何充分利用寄存器的问题： ●尽可能地让该变量的值保留在寄存器中 ·尽可能引用变量在寄存器中的值 待用信息：若在一个基本块中，变量在四元式中被定 值，在i后面的四元式i中要引用A值，且从i到j之间没有其 它对A的定值点，这时我们称是四元式i中对变量A的待用 信息或称下次引用信息，同时也称是活跃的，，若弘被多次 引用则可构成待用信息链与活跃信息链。 可从基本块的出口由后向前扫描，对每个变量建立相应的待用 信息链和活跃变量信息链
． 简单的代码生成器（基本块内） 在一个基本块范围内考虑如何充分利用寄存器的问题： l 尽可能地让该变量的值保留在寄存器中 l 尽可能引用变量在寄存器中的值 待用信息：若在一个基本块中，变量A在四元式i 中被定 值，在i 后面的四元式j 中要引用A 值，且从i 到 j 之间没有其 它对A的定值点，这时我们称j是四元式i 中对变量A 的待用 信息或称下次引用信息，同时也称A 是活跃的，，若A 被多次 引用则可构成待用信息链与活跃信息链。 可从基本块的出口由后向前扫描，对每个变量建立相应的待用 信息链和活跃变量信息链
计算待用信息的算法： 符号表中增加“待用信息”栏和“活跃信息” 栏 对各基本块的符号表中的待用信息”栏和活跃信息” 栏置初值，即把待用信息”栏置“非待用”，对“活跃 信息”栏按在基本块出口处是否为活跃而置成话跃”或 “非活跃”。这里假定变量都是活跃的，临时变量都是非 活跃的
计算待用信息的算法： 对各基本块的符号表中的“待用信息”栏和“活跃信息” 栏置初值，即把“待用信息”栏置 “非待用”，对“活跃 信息”栏按在基本块出口处是否为活跃而置成“活跃”或 “非活跃”。这里假定变量都是活跃的，临时变量都是非 活跃的。 符号表中增加“待用信息”栏和“活跃信息” 栏
从基本块出口到基本块入口由后向前依次处理每个四元 式。对每个四元式：A:=BopC,依次执行下述步骤： a)把符号表中变量A的待用信息和活跃信息附加到四元式i 上。 b)把符号表中变量A的待用信息栏和活跃信息栏分别置为 “非待用”和“非活跃”。（由于在i中对A的定值只能 在以后的四元式才能引用，因而对以前的四元式来说A 是不活跃也不可能是待用的) c)把符号表中变量B和C的待用信息和活跃信息附加到四元 式i上。 d)把符号表中变量B和C的待用信息栏置为“”，活跃信 息栏置为“活跃”。 注意，以上a)和b),c)和d)的次序不能颠倒
从基本块出口到基本块入口由后向前依次处理每个四元 式。对每个四元式i: A:=B op C，依次执行下述步骤： a） 把符号表中变量A的待用信息和活跃信息附加到四元式i 上。 b） 把符号表中变量A的待用信息栏和活跃信息栏分别置为 “非待用”和 “非活跃” 。 （由于在i 中对A的定值只能 在 i 以后的四元式才能引用，因而对 i以前的四元式来说A 是不活跃也不可能是待用的） c）把符号表中变量B和 C 的待用信息和活跃信息附加到四元 式 i 上。 d） 把符号表中变量B和 C的待用信息栏置为“ i”，活跃信 息栏置为“活跃” 。 注意，以上a）和b），c）和d）的次序不能颠倒