《编译原理》课程教学课件（2023讲稿）cha10_2 代码生成_阅读（含生成算法简介）

第10章(2)目标代码生成 n基本问题 n且标机器模型 n一个简单的代码生成器 n寄存器分配（略） nDAG的目标代码（略） n作业 2023/2/28 课程目录)1V16

2023/2/28 第10章(2) 目标代码生成 n 基本问题 n 目标机器模型 n 一个简单的代码生成器 n 寄存器分配(略) n DAG的目标代码(略) n 作业 课程目录 1/16

代码生成概述p279 n逻辑阶段 编译程序的最后一个阶段 n输入和输出中间代码 等价的目标代码 n目标代码的一般形式 u汇编语言代码 「优点：目标程序好读、可移植 F缺点：需经汇编器辅助代码生成 n代码生成器的设计环境 u要依赖于目标机器、指令系统和操作系统。 n指令选择指令集丰富、选择合适。 n 寄存器分配有效合理使用寄存器、提高代码质量。 n计算顺序选择影响代码的有效性。 2023/2/28 国② 2/16

2023/2/28 代码生成概述 p279 n 逻辑阶段 编译程序的最后一个阶段 n 输入和输出 中间代码 等价的目标代码 n 目标代码的一般形式 u 汇编语言代码 F 优点:目标程序好读、可移植 F 缺点:需经汇编器辅助代码生成 n 代码生成器的设计环境 u 要依赖于目标机器、指令系统和操作系统。 n 指令选择 指令集丰富、选择合适。 n 寄存器分配 有效合理使用寄存器、提高代码质量。 n 计算顺序选择 影响代码的有效性。 2/16

目标代码生成器的基本设计要求 n使所生成的目标代码尽可能的短 n能较充分地发挥目标计算机可用资 源的效率 例如： u尽可能地使用执行速度快的指令 u充分利用计算机的寄存器和变址器， 以节省访问内存的时间 2023/2/28 章节目录国216

2023/2/28 目标代码生成器的基本设计要求 n 使所生成的目标代码尽可能的短 n 能较充分地发挥目标计算机可用资 源的效率 例如： u 尽可能地使用执行速度快的指令 u 充分利用计算机的寄存器和变址器， 以节省访问内存的时间 章节目录 3/16

10.4.1目标机模型假想的计算机模型p280 n常备指令arc—源操作数 dst一目的操作数 指令形式 意义 举例 LD dst,arc (arc)▣dst LD R1,B (B)R MOVE LD R1,#1 10 R LDR1,米(4(RO)(Ro)+4)口R1 ST arc,dst (arc)☐dst ST R1,B (R1)B ADD dst,arc (dst)+(arc)dst ADD R1,Ro (Ri)+(Ro)RI SUB dst,arc (dst)-(arc)口dst SUB RI,T1(R)-(①)口R MUL dst,arc(dst)*(arc)口dst MUL R,D(Ri)*(D)口R DIV dst,arc (dst)/(arc)dst DIV R1,A (R1)/(A)R 2023/2/28 章节目录国 4/16

2023/2/28 10.4.1 目标机模型 假想的计算机模型 p280 n 常备指令 arc—源操作数 dst—目的操作数 指令形式 意 义 举 例 LD dst,arc (arc)￾ dst LD R1,B (B)￾ R1 MOVE LD R1,#1 1￾ R1 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 章节目录 4/16

执行代价p280 n衡量目标程序工作效率的指标 u目标程序的长短 u目标程序的执行时间一取决于访问内存的次数 n一条指令执行代价 u定义：执行该指令所需访问内存的总次数 u值=该指令访问内存的次数+1（取指令访问一次内存） n目标程序的执行代价 u定义：各条指令执行代价总和 u特点：该值越低目标程序的执行效率越高 产生目标代码时，应尽可能选用执行代价较小的指令 2023/2/28

2023/2/28 5 执行代价 p280 n 衡量目标程序工作效率的指标 u 目标程序的长短 u 目标程序的执行时间——取决于访问内存的次数 n 一条指令执行代价 u 定义：执行该指令所需访问内存的总次数 u 值=该指令访问内存的次数+1(取指令访问一次内存) n 目标程序的执行代价 u 定义：各条指令执行代价总和 u 特点：该值越低目标程序的执行效率越高 产生目标代码时，应尽可能选用执行代价较小的指令

执行代价举例 n对三地址代码A:=B+C n 指令 执行代价 n若B,C分别在Ro,R1,且B值 以后不用，则 n LD Ro,R1 (0+1) 1 (1)ADD Ro,R1 (0+1)1 n LD R1,M (1+1) 2 n若B在Ro,C在内存，且B值 n ST RL,TI (1+1) 2 以后不用，则 ADD R1,#1 n (1+1) 2 (2)ADD Ro,C (1+1)2 n ADD Ro,*R1 （1+1)2 或(3)LDR1,C n LD Ro,*M (2+1)3 ADD Ro,R1 (1+2) 3 n第(3)种特别适合于C值在块内还要被引用的情况， 虽然它的执行代价比前两种形式都高，但由于以 后可从寄存器中取得C值，故从总程序的执行代价 上看，仍是合算的 2023/2/28 章节目录国)6

2023/2/28 6 执行代价举例 n 指令 执行代价 n LD R0,R1 (0+1) 1 n LD R1,M (1+1) 2 n ST R1,T1 (1+1) 2 n ADD R1,#1 (1+1) 2 n ADD R0,*R1 (1+1) 2 n LD R0,*M (2+1) 3 n 对三地址代码A:=B+C n 若B,C分别在R0,R1，且B值 以后不用，则 (1)ADD R0,R1 (0+1) 1 n 若B在R0，C在内存，且B值 以后不用，则 (2)ADD R0,C (1+1) 2 或(3)LD R1,C ADD R0,R1 (1+2) 3 n 第(3)种特别适合于C值在块内还要被引用的情况， 虽然它的执行代价比前两种形式都高，但由于以 后可从寄存器中取得C值，故从总程序的执行代价 上看，仍是合算的 章节目录

10.4.2一个简单的代码生成器p282 n概述 n寄存器描述和地址描述 n简单代码生成算法 2023/2/28 章节目录国16

2023/2/28 10.4.2 一个简单的代码生成器 p282 n 概述 n 寄存器描述和地址描述 n 简单代码生成算法 章节目录 7/16

概述p283 n算法策略 u依次把每条中间代码变换成目标代码 u在一个基本块范围内充分利用寄存器 n如何充分利用寄存器—做到 u尽可能地让变量（存结果）的值保留在寄存器中 ù尽可能引用变量（操作数）在寄存器中的值，直到 该寄存器必须用来存放别的变量值或者已到达基本 块出口为止 n为了生成高效的目标代码，充分利用寄存器， 代码生成器需要了解如下信息 u哪些变量以后还会被引用一待用信息 u 变量的值当前在何处一 寄存器描述和地址描述 2023/2/28 8/16

2023/2/28 概述 p283 n 算法策略 u 依次把每条中间代码变换成目标代码 u 在一个基本块范围内充分利用寄存器 n 如何充分利用寄存器——做到 u 尽可能地让变量(存结果)的值保留在寄存器中 u 尽可能引用变量(操作数)在寄存器中的值，直到 该寄存器必须用来存放别的变量值或者已到达基本 块出口为止 n 为了生成高效的目标代码，充分利用寄存器， 代码生成器需要了解如下信息 u 哪些变量以后还会被引用——待用信息 u 变量的值当前在何处——寄存器描述和地址描述 8/16

目 三地址代码 目标代码 寄存器描述 地址描述 标 (1)T1:=A+B LD Ro,A R空闲 ADD Ro,B Ro含T1 T1在R0 ②T2:=T1-C LD R1 Ro Ro含T1 Ro2 R1 T1在R, 生 R1空闲 SUB R1,C R1含T2均非空 T2在R1 成 (③)T3:=D+E ST Ro,Ti RT1存入内存 T1在T1 Ro 举 LD Ro,D R含T2 T2在R1T2以后 T最远用到 ADD Ro,E Ro含T3 T3在RO 不用 例 (4④T3:①2yT3R MUL R1,Ro R1含T3 I3在RT在 (⑤)T4:T3 LD Ro,T1 R1含T3 T3在R1T3以后 R0T1存入R0 ADD Ro,Ri Ro含T4 T4在R0不用 (6)T5:=T3-ER1 SUB R1,E R1含T5R含T4 T5在R1T4在Ro (⑦)F:=T4*T5 MUL Ro,Ri T4以后 RoF存内存 ST Ro,F RO含F F在RO,F 不用 假设只有Ro,R1两个寄存器可用，出口处只有F活跃 2023/2/28 节目绿国D 9/16

2023/2/28 目 标 代 码 生 成 举 例 三地址代码 (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 节目录 9/16

寄存器描述 p283 n寄存器描述 u目的动态地记录各寄存器分配信息 u内容描述每个寄存器当前的状况 F空闲已分配某个变量 已分配给某些变量 数据结构 u 数组 Ro R1 R RVALUE 空闲 B D,T1 n举例 u RVALUE[Ro]={}—寄存器R空闲 u RVALUE[R]={B}—R1中持有B的值 u RVALUE[R]={D,T}—R7中持有D,T的值 2023/2/28 ☒> 10/16

2023/2/28 寄存器描述 p283 n 寄存器描述 u 目的 动态地记录各寄存器分配信息 u 内容 描述每个寄存器当前的状况 F 空闲 已分配某个变量 已分配给某些变量 u 数据结构 数组 RVALUE . R0 R1 . R7 n 举例 u RVALUE[R0]={ }——寄存器R0空闲 空闲 u RVALUE[R1]={B}——R1中持有B的值 B u RVALUE[R7]={D,T1}——R7中持有D,T1的值 D,T1 10/16