第10章(2)代码生成 ■目标机器模型 ■一个简单的代码生成器 ■作业 2025/4/2 课程目录国m
2025/4/2 第10章 (2) 代码生成 ◼ 目标机器模型 ◼ 一个简单的代码生成器 ◼ 作业 课程目录 1/11
代码生成概述p279 ■逻辑阶段编译程序的最后一个阶段 ■输入和输出中间代码等价的目标代码 ■目标代码的一般形式 ◆汇编语言代码 口优点：目标程序好读、可移植 缺点：需经汇编器辅助代码生成 ■代码生成器的设计环境 ◆要依赖于目标机器、指令系统和操作系统。 2025/4/2 ☒221
2025/4/2 代码生成概述 p279 ◼ 逻辑阶段 编译程序的最后一个阶段 ◼ 输入和输出 中间代码 等价的目标代码 ◼ 目标代码的一般形式 ◆汇编语言代码 优点:目标程序好读、可移植 缺点:需经汇编器辅助代码生成 ◼ 代码生成器的设计环境 ◆ 要依赖于目标机器、指令系统和操作系统。 2/11
目标代码生成器的基本设计要求 ■目标代码尽可能的短 ■充分地发挥目标机可用资源效率 例如 ◆尽可能地使用执行速度快的指令 ◆充分利用寄存器和变址器，以节省访 问内存的时间 2025/4/2 31
2025/4/2 目标代码生成器的基本设计要求 ◼ 目标代码尽可能的短 ◼ 充分地发挥目标机可用资源效率 例如： ◆尽可能地使用执行速度快的指令 ◆充分利用寄存器和变址器，以节省访 问内存的时间 3/11
目标机模型假想的计算机模型p280 ■常备指令arc一源操作数 dst一目的操作数 指令形式 意义 举例 LD dst,arc (arc)→dst LDR1,B(B)→R1取数 MOVE LDR1,#11→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)→R MUL dst,arc (dst)*(arc)→dst MUL R1,D(R1)*(D)→R1 DIV dst,arc (dst)/(arc)→dst DIV R1,A(R1)/(A)→R1 e●p●●● ●●●●● ●●●●●● 2025/4/2 国4m
2025/4/2 目标机模型 假想的计算机模型 p280 ◼ 常备指令 arc—源操作数 dst—目的操作数 指令形式 意 义 举 例 LD dst,arc (arc)dst LD R1,B (B)R1 取数 MOVE LD R1,#1 1R1 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 . . . 4/11
一个简单的代码生成器 ■算法策略 ◆依次把每条中间代码变换成目标代码 ◆在一个基本块范围内充分利用寄存器 ■如何充分利用寄存器一 做到 ◆尽可能地让变量（存结果）的值保留在寄存器中 ◆尽可能引用变量（操作数）在寄存器中的值，直到 该寄存器必须用来存放别的变量值或者已到达基本 块出口为止 ■为了生成高效的目标代码，充分利用寄存器， 代码生成器需要了解如下信息 ◆哪些变量以后还会被引用 ◆变量的值当前在何处一 寄存器描述和地址描述 2025/4/2 5/11
2025/4/2 一个简单的代码生成器 ◼ 算法策略 ◆ 依次把每条中间代码变换成目标代码 ◆ 在一个基本块范围内充分利用寄存器 ◼ 如何充分利用寄存器——做到 ◆ 尽可能地让变量(存结果)的值保留在寄存器中 ◆ 尽可能引用变量(操作数)在寄存器中的值，直到 该寄存器必须用来存放别的变量值或者已到达基本 块出口为止 ◼ 为了生成高效的目标代码，充分利用寄存器， 代码生成器需要了解如下信息 ◆ 哪些变量以后还会被引用 ◆ 变量的值当前在何处——寄存器描述和地址描述 5/11
目 三地址代码 目标代码 寄存器描述 地址描述 标 (1)T1:=A+B LD Ro,A RO空闲 ADD Ro,B Ro含T1 T1在Ro 2)T2:=T1C LD R1 Ro Ro含T1 Ro,R1 T1在R0 生 R1空闲 SUB R1,C R1含T2均非空 T2在R1 成 (3)T3:=D+E ST Ro,Ti R0T1存入内存 T1在T1 Ro 举 LD Ro,D R1含T2 T2在R1T2以后 T1最远用到 ADD Ro,E Ro含T3 例 T3在RO 不用 (4)T3:T2*T3R1 MUL R1,Ro R1含T3 T3在RT1在T1 (⑤)T4:T3 LD Ro T1 R1含T3 T3在R1T3以后 R0T1存入RO ADD Ro,R1 R0含T4 T4在R0不用 (6)T5:=T3-ER1 SUB R1,E R1含T5Ro含T4 T5在R1T4在R0 (7)F:=T4*T5 MUL Ro R1 T4以后 RoF存内存 ST Ro,F Ro含F F在RO,F 不用 假设只有R0,R1两个寄存器可用，出口处只有F活跃 2025/4/2 6/11
2025/4/2 目 标 代 码 生 成 举 例 三地址代码 (1)T1:=A+B (2)T2:=T1-C (3)T3:=D+E (4)T3:=T2*T3 (5)T4:=T1+T3 (6)T5:=T3-E (7)F:=T4*T5 目标代码 寄存器描述 地址描述 假设只有R0 ,R1两个寄存器可用 R0空闲 LD R0 ,A ADD R0 ,B R0含T1 T1在R0 R1空闲 LD R1 ,R0 SUB R1 ,C R0含T1 R1含T2 T1在R0 T2在R1 R0,R1 均非空 R0 T1最远用到 ST R0 ,T1 R0 T1存入内存 LD R0 ,D ADD R0 ,E R1含T2 R0含T3 T1在T1 T2在R1 T3在R0 T2以后 不用 R1 MUL R1 ,R0 R1含T3 T3在R1 T1在T1 R0 LD R0 ,T1 ADD R0 ,R1 R1含T3 R0含T4 T3在R1 T4在R0 R1 SUB R1 ,E R1含T5 R0含T4 T5在R1 T4在R0 T3以后 T1存入R0 不用 T4以后 R0 不用 MUL R0 ,R1 ，出口处只有F活跃 F存内存 ST R0,F R0含F F在R0，F 6/11
寄存器描述 p283 ■寄存器描述 ◆目的动态地记录各寄存器分配信息 ◆内容描述每个寄存器当前的状况 ▣空闲已分配某个变量 已分配给某些变量 ◆数据结构 数组 Ro R1 R7 RVALUE 空闲 B D,Ti 举例 ◆RVALUE[Ro]={}一寄存器Ro空闲 ◆RVALUE[R]={B}—R1中持有B的值 ◆RVALUE[R]={D,T1}—R7中持有D,T1的值 2025/4/2 D 7/11
2025/4/2 寄存器描述 p283 ◼ 寄存器描述 ◆目的 动态地记录各寄存器分配信息 ◆内容 描述每个寄存器当前的状况 空闲 已分配某个变量 已分配给某些变量 ◆数据结构 数组 RVALUE . R0 R1 . R7 ◼ 举例 ◆RVALUE[R0]={ }——寄存器R0空闲 空闲 ◆RVALUE[R1]={B}——R1中持有B的值 B ◆RVALUE[R7]={D,T1}——R7中持有D,T1的值 D,T1 7/11
地址描述 p283 ■地址描述 ◆目的动态地记录各变量现行值的存放位置 ◆内容描述每个变量现行值所在位置状况 ▣只在寄存器只在内存同时在寄存器和内存 ◆数据结构 数组 B C . T1 AVALUE R1 C R7,T1 ■举例 AVALUE[B]={R1}一变量B的值在寄存器R1中 AVALUE[C]={C}一变量C的值在内存单元C中 AVALUE[T]={R7,T}—变量T1的值在寄存器R7 和内存单元T1中 2025/4/2 8/11
2025/4/2 地址描述 p283 ◼ 地址描述 ◆目的 动态地记录各变量现行值的存放位置 ◆内容 描述每个变量现行值所在位置状况 只在寄存器 只在内存 同时在寄存器和内存 ◆数据结构 数组 AVALUE . B C . T1 ◼ 举例 AVALUE[B]={R1}——变量B的值在寄存器R1中 R1 AVALUE[C]={C}——变量C的值在内存单元C中 C AVALUE[T1]={R7,T1}——变量T1的值在寄存器R7 和内存单元T1中 R7,T1 8/11
目标代码简单生成算法使用举例 三地址代码 目标代码 寄存器描述 地址描述 (1)T:=A-B LD Ro,A Ro空闲 SUB Ro,B Ro含T T在Ro (2U:=A-C LD R1,A Ro含T Ro,R1 T在Ro T以后 R1空闲 SUB R1,C R1含UJ均非空 U在R1 不用 (3)V:=T+U ADD Ro,R1 R1含U U在R1V以后 ROT不活跃 Ro含V V在RO 不用 (4)W:=V+U ADD Ro, R1 RoW存内存 ST Ro,W Ro含W W在Ro,W 假设只有R0,R1两个寄存器可用，出口处只有W活跃 2025/4/2 国D 9/11
2025/4/2 目标代码简单生成算法使用举例 三地址代码 (1)T:=A-B (2)U:=A-C (3)V:=T+U (4)W:=V+U 目标代码 寄存器描述 地址描述 假设只有R0 ,R1两个寄存器可用，出口处只有W活跃 R0空闲 LD R0 ,A SUB R0 ,B R0含T T在R0 R1空闲 LD R1 ,A SUB R1 ,C R0含T R1含U T在R0 U在R1 R0,R1 均非空 R0 T不活跃 ADD R0 , R1 R1含U R0含V U在R1 V在R0 T以后 不用 ADD R0 , R1 R0 ST R0,W R0含W W在R0，W W存内存 V以后 不用 9/11
目标代码简单生成算法课堂练习 例：赋值语句T4:=A+B-(E-(C+D)) BEGIN 三地址代码 目标代码 寄存器描述 地址描述 (1)T1:=A+B (1)LD Ro,A Ro空闲 (2)ADD Ro,B Ro含T1 T1在Ro 2T2:=C+D (3)LD R1,C Ro含T1lRo,R1 T1在Ro R1空闲 (4)ADD R1,D R1含T2了均非空 T2在R1 (3)T3:=ET2 (5)STR0,T1 T1存入内存 Ro (6)LD Ro,E R1含T2 T2在RT2以后 T1最远用到 (7)SUB Ro,R1 Ro含T3 T3在R0 不用 4)T4:T3 (8)LD R1,T1 取T1存入R1 是否可优化？ (9)SUB R1,Ro T4存入内存 (10)STR1,T4 R1含T4 T4在R1,T4 假设只有R0,R1两个寄存器可用，出口处只有T4活跃 请给出目标代码及生成过程中寄存器和地址描述 2025/4/2
2025/4/2 目标代码简单生成算法课堂练习 三地址代码 (1)T1:=A+B (2)T2:=C+D (3)T3:=E-T2 (4)T4:=T1-T3 目标代码 寄存器描述 地址描述 假设只有R0 ,R1两个寄存器可用，出口处只有T4活跃 请给出目标代码及生成过程中寄存器和地址描述 R0空闲 (1)LD R0 ,A (2)ADD R0,B R0含T1 T1在R0 R1空闲 (3)LD R1 ,C (4)ADD R1,D R0含T1 R1含T2 T1在R0 T2在R1 R0,R1 均非空 R0 T1最远用到 (5)ST R0 ,T1 (6)LD R0 ,E (7)SUB R0,R1 R1含T2 R0含T3 T2在R1 T3在R0 T1存入内存 R1 (9)SUB R1,R0 (10)ST R1,T4 T4存入内存 R1含T4 T4在R1，T4 T2以后 不用 (8)LD R1 ,T1 取T1存入R1 例：赋值语句T4:=A+B-(E-(C+D)) 是否可优化？ BEGIN 10/11