编译原理 第十一章目标代码生成 2005/6/12
编译原理 第十一章 目标代码生成 2005/6/12
编泽原理 目标代码的形式 墨机器语言代码 所有地址已定位，可立即执行 墨待装配的机器语言模块 汇编语言代码 代码生成考虑（执行速度）： 如何使生成的代码较短 慧如何利用计算机的寄存器，减少目标代码中访问存储单元的 次数 第2页
编译原理 第2页 目标代码的形式 机器语言代码 所有地址已定位，可立即执行 待装配的机器语言模块 汇编语言代码 代码生成考虑（执行速度）： 如何使生成的代码较短 如何利用计算机的寄存器，减少目标代码中访问存储单元的 次数
编译原理 11.1 基本问题 代码生成器的输入 目标程序 量指令选择寄存器分配 计算顺序选择 第3页
编译原理 第3页 11.1 基本问题 代码生成器的输入 目标程序 指令选择寄存器分配 计算顺序选择
编泽原理 11.2目标机器模型 售假设目标计算机有下列指令形式 类型 指令形式 意义（设op是二目运算符） 直接地址型 op Ri,M (Ri)op (M)=Ri 寄存器型 op Ri.Ri 变址型 (R)op(R)→R 间接型 op R;.c(Ri) (R)op(R)+c)→R op Ri,*M (Ri)op ((M))=Ri op Ri,*Ri (R)op(R)→R; op Ri,*c(Rj) (R)op(《(R)+c)=R 第4负
编译原理 第4页 11.2 目标机器模型 假设目标计算机有下列指令形式
编译原理 指令的意义： 指龄 意舣 指龄 意舣 LDRiB 把弹元的内溶取到寄存器R,阳)=R 以 如CT=0 转弹元 ST RiB 把寄存器鄂的大容存到弹元，印(R)=8。 以 如CT=减CT1转弹元 J X 无条件转向X弹元 以 如CT1 转弹元 CMP AB 把A弹元和弹元的值进行比较并根据比较 找 如CT判 转弹元 情机把机器内部特寄弃器CT置成相应态以 如CT=2 转弹玩 :CT占两个二进位，根据A盼别置CT知以 如CT=2减CT:1 转禅元 或域2 第5页
编译原理 第5页 指令的意义：
编泽原理 11.3一个简单的代码生成器 售将每条中间代码变换成目标代码，并在一个基本块范围内考虑充分利用寄存器问题。 例： 高级语言 A:=(B+C)*D+E 中间代码 T1:=B+C T2:=T1*D A:=T2+E 目标指令 (1) LD R,B 优化： (1) LD R,B (2) ADD R,C (2) ADD R,C (3) ST R,T1 (3) MUL R,D (4) LD R,T1 (4)ADD R,E (5) MUL R,D (5)ST R,A (6) ST R,T2 () LD R,T2 (⑧)ADD R,E (9)ST R,A 第6列
编译原理 第6页 11.3 一个简单的代码生成器 将每条中间代码变换成目标代码，并在一个基本块范围内考虑充分利用寄存器问题。 例： 高级语言 A:=(B+C)*D+E 中间代码 T1:=B+C T2:=T1*D A:=T2+E 目标指令 （1） LD R,B 优化： （1） LD R,B (2) ADD R,C (2) ADD R,C (3) ST R,T1 (３) MUL R,D (4) LD R,T1 （ ４) ＡＤＤ Ｒ，Ｅ (5) MUL R,D （５） ＳＴ Ｒ，Ａ (6) ST R,T2 (7) LD R,T2 (8) ＡＤＤ Ｒ，Ｅ （９）ＳＴ Ｒ，Ａ
编译原理 待用信息 计算变量待用信息算法 1、开始，将基本块中各变量的符号表登记项中的待用信息栏填为“非待 用”，并根据该变量在基本块出口之后是否活跃填写活跃信息栏。 2、,从基本块出口到基本块入口由后往前依次处理各中间代码，对每一中间 代码 i:A:=B o p C 依次执行： a)将符号表中变量A的待用信息和活跃信息附加到中间代码i上； b)将符号表中变量A的待用信息和活跃信息分别置为“非待用”和 “非活跃”； c)将符号表中变量B和C的待用信息和活跃信息附加到中间代码i上； )将符号表中变量B和C的待用信息均置为i,活跃信息均置为“活 跃 注意：次序不可颠倒。 如果中间代码形式为 A:=OpB或A:=B 除 不涉及C外步骤完全相同。 第7觉
编译原理 第7页 待用信息 计算变量待用信息算法 １、开始，将基本块中各变量的符号表登记项中的待用信息栏填为“非待 用”，并根据该变量在基本块出口之后是否活跃填写活跃信息栏。 ２、从基本块出口到基本块入口由后往前依次处理各中间代码，对每一中间 代码 ｉ：Ａ：＝Ｂ ｏｐ Ｃ 依次执行： ａ）将符号表中变量Ａ的待用信息和活跃信息附加到中间代码ｉ上； ｂ）将符号表中变量Ａ的待用信息和活跃信息分别置为“非待用”和 “非活跃”； ｃ）将符号表中变量Ｂ和Ｃ的待用信息和活跃信息附加到中间代码ｉ上； ｄ）将符号表中变量Ｂ和Ｃ的待用信息均置为ｉ，活跃信息均置为“活 跃”。 注意：次序不可颠倒。 如果中间代码形式为 Ａ：＝ ｏｐ Ｂ 或 Ａ：＝ Ｂ 除 不涉及Ｃ外步骤完全相同
编泽原理 雪考察基本块： T:=A-B U:=A-C V:=T+U W:-V+U 设 W是基本块出口的活跃变量，则有下表 第8页
编译原理 第8页 考察基本块： Ｔ：＝Ａ－Ｂ Ｕ：＝Ａ－Ｃ Ｖ：＝Ｔ＋Ｕ Ｗ：＝Ｖ＋Ｕ 设 Ｗ是基本块出口的活跃变量，则有下表
编译原理 符号表中的待用及活跃信息 变量名 选用信息及活跃信息 T (n,n)→(3，Y→(n,n) A (n,n)→(2，Y)→(1，Y B (n,n)→(1，Y C (n,n)→(2，Y) U (n,n)→(4，Y)→(3，Y)→(n,n) V (n,n)→(4，Y)→(n,n) W (n,Y)→(n,n) 第9页
编译原理 第9页 符号表中的待用及活跃信息
编泽原理 表12附加在中间代码上的待及活跃信息 輞 中闻阏 左值 左锁 古懒 1 T48 (3) 2Y9 2 40 (3Y) 3 V=T+U 49 49 4 W.-V+U 9 第0
编译原理 第10页