第10章 代码生成 ■基本问题 ■目标机器模型 ■一个简单的代码生成器 ■寄存器分配（略） ■DAG的目标代码（略） ■作业 2025/4/3 课程目绿☒)
2025/4/3 1 第10章 代码生成 ◼ 基本问题 ◼ 目标机器模型 ◼ 一个简单的代码生成器 ◼ 寄存器分配(略) ◼ DAG的目标代码(略) ◼ 作业 课程目录
代码生成概述 ■逻辑阶段 编译程序的最后一个阶段 ■输入和输出中间代码 等价的目标代码 ■目标代码的一般形式 ◆绝对机器代码所有地址均已定位 优点：可立即执行 ·缺点：不能独立编译各模块，灵活性差 ◆可再定位机器代码需经连接与装入才可执行 ▣优点：子程序可单独编译 口缺点：需经汇编器辅助代码生成 ◆汇编语言代码 口优点：目标程序好读、可移植 口缺点：需经汇编器辅助代码生成 2025/4/3 D2
2025/4/3 2 代码生成概述 ◼ 逻辑阶段 编译程序的最后一个阶段 ◼ 输入和输出 中间代码 等价的目标代码 ◼ 目标代码的一般形式 ◆绝对机器代码 所有地址均已定位 优点:可立即执行 缺点:不能独立编译各模块,灵活性差 ◆可再定位机器代码 需经连接与装入才可执行 优点:子程序可单独编译 缺点:需经汇编器辅助代码生成 ◆汇编语言代码 优点:目标程序好读、可移植 缺点:需经汇编器辅助代码生成
基本问题 ■代码生成器的设计环境 ◆要依赖于目标机器、指令系统和操作系统。 ■输入 ◆源程序的中间表示、符号表中的信息。 ■ 目标程序 ◆汇编语言。 ■指令选择 ◆指令集丰富、选择合适。 寄存器分配 ◆有效合理使用寄存器、提高代码质量。 ■计算顺序选择 ◆影响代码的有效性。 2025/4/3 ☒3
2025/4/3 3 基本问题 ◼ 代码生成器的设计环境 ◆要依赖于目标机器、指令系统和操作系统。 ◼ 输入 ◆源程序的中间表示、符号表中的信息。 ◼ 目标程序 ◆汇编语言。 ◼ 指令选择 ◆指令集丰富、选择合适。 ◼ 寄存器分配 ◆有效合理使用寄存器、提高代码质量。 ◼ 计算顺序选择 ◆影响代码的有效性
目标代码生成器的基本设计要求 ■使所生成的目标代码尽可能的短 ■能较充分地发挥目标计算机可用资 源的效率 例如： ◆尽可能地使用执行速度快的指令 ◆充分利用计算机的寄存器和变址器， 以节省访问内存的时间 2025/4/3 章节目录国回4
2025/4/3 4 目标代码生成器的基本设计要求 ◼ 使所生成的目标代码尽可能的短 ◼ 能较充分地发挥目标计算机可用资 源的效率 例如： ◆尽可能地使用执行速度快的指令 ◆充分利用计算机的寄存器和变址器， 以节省访问内存的时间 章节目录
目标机模型 ■问题提出 ◆代码生成程序总是针对某一具体的计算机实现的 ◆因此，试图脱离具体的计算机来一般性讨论生成高 效的目标代码的全部细节是不合适的，也是不可行 的 ◆然而又不可能只局限于某一特定的计算机 ■折中方案 ◆定义一种假想的计算机模型，具有实际计算机的 共同特征 ◆依此模型为依据，讨论代码生成中的某些主要问题 2025/4/3 国5
2025/4/3 5 目标机模型 ◼ 问题提出 ◆代码生成程序总是针对某一具体的计算机实现的 ◆因此，试图脱离具体的计算机来一般性讨论生成高 效的目标代码的全部细节是不合适的，也是不可行 的 ◆然而又不可能只局限于某一特定的计算机 ◼ 折中方案 ◆定义一种假想的计算机模型，具有实际计算机的 共同特征 ◆依此模型为依据，讨论代码生成中的某些主要问题
目标机模型 ■指令形式（寻址方式） (R)一通用寄存器R:中的内容 (M)一内存单元M中的内容 类型 指令形式 意义（设op是二目运算符） 直接地址型 op Ri,M (Ri)op(M)→Ri 寄存器型 op Ri,Rj (Ri)op(R)→Ri 变址型 op Ri,c(Rj) (Ri)op(R)+c)→Ri 间接型 op Ri,*M (Ri)op(M)→R op Ri,*Rj (R)op(R)→R1 op Ri,*c(Ri) (Ri)op((R)+c)→R 直接操作数型 op Ri,#X (Ri)opX→Ri 2025/4/3 国D6
2025/4/3 6 目标机模型 ◼ 指令形式(寻址方式) (Ri)—通用寄存器Ri中的内容 (M)—内存单元M中的内容 类 型 指令形式 意义(设op是二目运算符) 直接地址型 op Ri,M (Ri)op(M)Ri 寄存器型 op Ri,Rj (Ri)op(Rj)Ri 变址型 op Ri,c(Rj) (Ri)op((Rj)+c)Ri 间接型 op Ri,*M (Ri)op((M))Ri op Ri,*Rj (Ri)op((Rj))Ri op Ri,*c(Rj) (Ri)op(((Rj)+c))Ri 直接操作数型 op Ri,#X (Ri)op X Ri
目标机模型 ■常备指令arc一源操作数 dst一目的操作数 指令形式 意义 举 例 LD dst,arc (arc)→dst LDR1,B(B)→R1 LDR1,#11→R1 LDR1,*(4(R0))(Ro)+4)→R1 ST arc,dst (arc)→dst STR1,B(R1)→B ADD dst,arc (dst)+(arc)→dst ADD R1,Ro(R1)+(Ro)→R1 SUB dst,arc (dst)-(arc)→dst SUB R1,T1(R1)-(T)→Ra MUL dst,arc (dst)*(arc)→dst MULR1,D(R1)*(D)→R1 DIV dst,arc (dst)/(arc)→dst DIV R1,A(R1)/(A)→R1 2025/4/3 章节目录国)
2025/4/3 7 目标机模型 ◼ 常备指令 arc—源操作数 dst—目的操作数 指令形式 意 义 举 例 LD dst,arc (arc)dst LD R1,B (B)R1 LD R1,#1 1R1 LD R1,*(4(R0))(((R0)+4))R1 ST arc,dst (arc)dst ST R1,B (R1)B ADD dst,arc (dst)+(arc)dst ADD R1,R0 (R1)+(R0)R1 SUB dst,arc (dst)-(arc)dst SUB R1,T1 (R1)-(T1)R1 MUL dst,arc (dst)*(arc)dst MUL R1,D (R1)*(D)R1 DIV dst,arc (dst)/(arc)dst DIV R1,A (R1)/(A)R1 章节目录
执行代价 ■ 衡量目标程序工作效率的指标 ◆目标程序的长短 ◆目标程序的执行时间—取决于访问内存的次数 ■一条指令执行代价 ◆定义：执行该指令所需访问内存的总次数 ◆值=该指令访问内存的次数+1（取指令访问一次内存） ■目标程序的执行代价 ◆定义：各条指令执行代价总和 ◆特点：该值越低目标程序的执行效率越高 产生目标代码时，应尽可能选用执行代价较小的指令 2025/4/3
2025/4/3 8 执行代价 ◼ 衡量目标程序工作效率的指标 ◆目标程序的长短 ◆目标程序的执行时间——取决于访问内存的次数 ◼ 一条指令执行代价 ◆定义：执行该指令所需访问内存的总次数 ◆值=该指令访问内存的次数+1(取指令访问一次内存) ◼ 目标程序的执行代价 ◆定义：各条指令执行代价总和 ◆特点：该值越低目标程序的执行效率越高 产生目标代码时，应尽可能选用执行代价较小的指令
执行代价举例 ■对三地址代码A:=B+C 指令 执行代价 ■若B,C分别在Ro,R1,且B值 以后不用，则 ■LDRo,R1 (0+1) 1 (1)ADD Ro,R1 (0+1) 1 ■LD R1,M (1+1) 2 若B在Ro,C在内存，且B值 ■STR1,T1 (1+1) 2 以后不用，则 ■ADDR1,#1 (1+1) 2 (2)ADD Ro,C (1+1)2 ■ADD Ro,米R1 (1+1) 2 或(3)LDR1,C ■LDRo,*M (2+1) 3 ADD Ro,R1 (1+2) 3 ■第(3)种特别适合于C值在块内还要被引用的情况， 虽然它的执行代价比前两种形式都高，但由于以 后可从寄存器中取得C值，故从总程序的执行代价 上看，仍是合算的 2025/4/3 章节目录冈区
2025/4/3 9 执行代价举例 ◼ 指令 执行代价 ◼ LD R0,R1 (0+1) 1 ◼ LD R1,M (1+1) 2 ◼ ST R1,T1 (1+1) 2 ◼ ADD R1,#1 (1+1) 2 ◼ ADD R0,*R1 (1+1) 2 ◼ LD R0,*M (2+1) 3 ◼ 对三地址代码A:=B+C ◼ 若B,C分别在R0,R1，且B值 以后不用，则 (1)ADD R0,R1 (0+1) 1 ◼ 若B在R0，C在内存，且B值 以后不用，则 (2)ADD R0,C (1+1) 2 或(3)LD R1,C ADD R0,R1 (1+2) 3 ◼ 第(3)种特别适合于C值在块内还要被引用的情况， 虽然它的执行代价比前两种形式都高，但由于以 后可从寄存器中取得C值，故从总程序的执行代价 上看，仍是合算的 章节目录
一个简单的代码生成器 概述 ■待用信息（略） 寄存器描述和地址描述 简单代码生成算法 2025/4/3 章节目录国回0
2025/4/3 10 一个简单的代码生成器 ◼概述 ◼待用信息(略) ◼寄存器描述和地址描述 ◼简单代码生成算法 章节目录