第八章 代 码 生 成 本章内容 一个简单的代码生成算法 涉及存储管理,指令选择,寄存器分配和计算次序选择等基本问题 前端 代 码 优 化

Slides:



Advertisements
Similar presentations
第八章 互换的运用.
Advertisements

7.4 用矩阵初等行变换 解线性方程组 主要内容: 一.矩阵的行初等变换 二.用行初等变换求逆矩阵 三.用矩阵法求线性方程组.
第三节 格林公式及其应用(2) 一、曲线积分与路径无关的定义 二、曲线积分与路径无关的条件 三、二元函数的全微分的求积 四、小结.
余角、补角.
探索三角形相似的条件(2).
C++中的声音处理 在传统Turbo C环境中,如果想用C语言控制电脑发声,可以用Sound函数。在VC6.6环境中如果想控制电脑发声则采用Beep函数。原型为: Beep(频率,持续时间) , 单位毫秒 暂停程序执行使用Sleep函数 Sleep(持续时间), 单位毫秒 引用这两个函数时,必须包含头文件
EBNF与操作语义 请用扩展的 BNF 描述 javascript语言里语句的结构;并用操作语义的方法描述对应的语义规则
代码生成.
EBNF 请用扩展的 BNF 描述 C语言里语句的结构; 请用扩展的 BNF 描述 C++语言里类声明的结构;
强连通分量 无向图 1、任意两顶点连通称该图为连通图 2、否则将其中的极大连通子图称为连通分量 A D C B E 有向图
第六章 运行时存储空间的组织和管理 术语 本章内容 讨论一个活动记录中的数据布局 程序执行过程中,所有活动记录的组织方式 过程的活动
代码生成.
编译原理与技术 2018/11/30 《编译原理与技术》讲义.
陈香兰 助教:陈博、李春华 Spring 2009 嵌入式操作系统 陈香兰 助教:陈博、李春华 Spring 2009.
走进编程 程序的顺序结构(二).
辅导课程六.
元素替换法 ——行列式按行(列)展开(推论)
Zhao4zhong1 (赵中) C语言指针与汇编语言地址.
Zhao4zhong1 (赵中) C语言指针与汇编语言地址.
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
第二章 Java语言基础.
逆向工程-汇编语言
动态规划(Dynamic Programming)
CPU结构和功能.
中国科学技术大学计算机系 陈香兰(0551- ) Spring 2009
《编译原理与技术》 期末复习 计算机科学与技术学院 郑启龙 李 诚 25/12/2018.
28.1 锐角三角函数(2) ——余弦、正切.
第4章 PHP流程控制语句.
第7章 在C/C++中使用汇编 罗文坚 中国科大 计算机学院
C++语言程序设计 C++语言程序设计 第七章 类与对象 第十一组 C++语言程序设计.
1.3 C语言的语句和关键字 一、C语言的语句 与其它高级语言一样,C语言也是利用函数体中的可执行 语句,向计算机系统发出操作命令。按照语句功能或构成的不 同,可将C语言的语句分为五类。 goto, return.
C语言程序设计 主讲教师:陆幼利.
EBNF与操作语义 请用扩展的 BNF 描述 javascript语言里语句的结构;并用操作语义的方法描述对应的语义规则
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
微机原理与接口技术 微机原理与接口技术 朱华贵 2015年11月13日.
用计算器开方.
<编程达人入门课程> 本节内容 内存的使用 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群: ,
Web安全基础教程
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
本节内容 内存复制指令 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
第九节 赋值运算符和赋值表达式.
iSIGHT 基本培训 使用 Excel的栅栏问题
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
目标代码生成.
本节内容 结构体 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
Chapter 18 使用GRASP的对象设计示例.
College of Computer Science & Technology
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
第二章 Java基本语法 讲师:复凡.
第7章 代码优化 学习目标: 掌握:基本块的划分、基本块的DAG优化 理解:什么是局部优化、循环优化、全局优化 了解:循环优化技术.
上杭二中 曾庆华 上杭二中 曾庆华 上杭二中 曾庆华.
临界区问题的硬件指令解决方案 (Synchronization Hardware)
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
本节内容 C语言的汇编表示 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
第二节 函数的极限 一、函数极限的定义 二、函数极限的性质 三、小结 思考题.
3. 逻辑运算指令 A、简单逻辑操作指令 CLR A. (不影响CY、AC、 OV标志) CPL A
本节内容 Windows线程切换_时钟中断切换 视频提供:昆山滴水信息技术有限公司 官网地址: 论坛地址: QQ交流 :
本节内容 通用寄存器 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
基于列存储的RDF数据管理 朱敏
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
本节内容 动态链接库 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
C++语言程序设计 C++语言程序设计 第九章 类的特殊成员 第十一组 C++语言程序设计.
编译原理 第十一章 代码生成 编译原理.
第三节 数量积 向量积 混合积 一、向量的数量积 二、向量的向量积 三、向量的混合积 四、小结 思考题.
本节内容 进程 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
使用Fragment 本讲大纲: 1、创建Fragment 2、在Activity中添加Fragment
§4.5 最大公因式的矩阵求法( Ⅱ ).
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
Presentation transcript:

第八章 代 码 生 成 本章内容 一个简单的代码生成算法 涉及存储管理,指令选择,寄存器分配和计算次序选择等基本问题 前端 代 码 优 化 第八章 代 码 生 成 本章内容 一个简单的代码生成算法 涉及存储管理,指令选择,寄存器分配和计算次序选择等基本问题 前端 代 码 优 化 器 中间 代码 源程序 生成 目标 程序

8.1 代码生成器的设计中的问题 8.1.1 目标程序 绝对机器语言程序 可重定位目标模块 目标程序将装入到内存的固定地方 粗略地说,相当于现在的可执行目标模块(第11章介绍) 可重定位目标模块 代码中含重定位信息,以适应重定位要求

8.1 代码生成器的设计中的问题 8.1.1 目标程序 可重定位目标模块 可重定位目标模块中, 需要有绿色部分的重定 位信息 .L7: testl %eax,%eax je .L3 testl %edx,%edx je .L7 movl %edx,%eax jmp .L7 .L3: leave ret 可重定位目标模块中, 需要有绿色部分的重定 位信息

8.1 代码生成器的设计中的问题 8.1.1 目标程序 绝对机器语言程序 可重定位目标模块 目标程序将装入到内存的固定地方 粗略地说,相当于现在的可执行目标模块(第11章介绍) 可重定位目标模块 代码中含重定位信息,以适应重定位要求 允许程序模块分别编译 调用其它先前编译好的程序模块

8.1 代码生成器的设计中的问题 8.1.1 目标程序 绝对机器语言程序 可重定位目标模块 汇编语言程序 代码中含重定位信息,以适应重定位要求 允许程序模块分别编译 调用其它先前编译好的程序模块 汇编语言程序 免去编译器重复汇编器的工作 从教学角度,增加可读性

8.1 代码生成器的设计中的问题 8.1.2 指令的选择 目标机器指令系统的性质决定了指令选择的难易程度,指令系统的统一性和完备性是重要的因素 指令的速度和机器特点是另一些重要的因素

8.1 代码生成器的设计中的问题 若不考虑目标程序的效率,指令的选择是直截了当的 例 三地址语句x = y + z (x,y和z都静态分配) MOV y, R0 / 把y装入寄存器R0 / ADD z, R0 / 把z加到R0上 / MOV R0, x / 把R0存入x中 / 逐条语句地产生代码,常常得到低质量的代码

8.1 代码生成器的设计中的问题 语句序列 a = b + c d = a + e 的代码如下 MOV b, R0 ADD c, R0 MOV R0, a MOV a, R0 ADD e, R0 MOV R0, d

8.1 代码生成器的设计中的问题 语句序列 a = b + c d = a + e 的代码如下 MOV b, R0 ADD c, R0 MOV R0, a MOV a, R0 -- 多余的指令 ADD e, R0 MOV R0, d

8.1 代码生成器的设计中的问题 语句序列 a = b + c d = a + e 的代码如下 MOV b, R0 ADD c, R0 MOV R0, a MOV a, R0 -- 多余的指令 ADD e, R0 -- 若a不再使用, MOV R0, d -- 第三条指令也多余

8.1 代码生成器的设计中的问题 8.1.3 寄存器分配 运算对象处于寄存器和处于内存相比,指令要短一些,执行也快一些 寄存器分配 选择驻留在寄存器中的一组变量 寄存器指派 挑选变量要驻留的具体寄存器

8.1 代码生成器的设计中的问题 8.1.4 计算次序的选择 程序中计算的执行次序会影响目标代码的执行效率 例 对表达式的计算而言,一种计算次序可能会比其它次序需要较少的寄存器来保存中间结果(见后面例题3) 选择最佳计算次序是一个NP完全问题

8.2 目 标 机 器 8.2.1 目标机器的指令系统 选择可作为几种微机代表的寄存器机器 8.2 目 标 机 器 8.2.1 目标机器的指令系统 选择可作为几种微机代表的寄存器机器 四个字节组成一个字,有n个通用寄存器R0,R1, …,Rn-1 二地址指令: op 源,目的 MOV {源传到目的} ADD {源加到目的} SUB {目的减去源}

8.2 目 标 机 器 地址模式和它们的汇编语言形式及附加代价 模式 形式 地址 附加代价 绝对地址 M M 1 寄存器 R R 0 8.2 目 标 机 器 地址模式和它们的汇编语言形式及附加代价 模式 形式 地址 附加代价 绝对地址 M M 1 寄存器 R R 0 变址 c(R) c + contents(R) 1 间接寄存器 R contents(R) 0 间接变址 c(R) contents(c + contents(R)) 1 直接量 #c c 1

8.2 目 标 机 器 例 指令实例 MOV R0, M MOV 4(R0), M MOV 4(R0), M MOV #1, R0 8.2 目 标 机 器 例 指令实例 MOV R0, M MOV 4(R0), M 4(R0)的值:contents(4 + contents(R0)) MOV 4(R0), M 4(R0)的值:contents(contents(4 + contents(R0))) MOV #1, R0

8.2 目 标 机 器 8.2.2 指令的代价 指令代价简化为 1 + 指令的源和目的地址模式的附加代价

8.2 目 标 机 器 地址模式和它们的汇编语言形式及附加代价 模式 形式 地址 附加代价 绝对地址 M M 1 寄存器 R R 0 8.2 目 标 机 器 地址模式和它们的汇编语言形式及附加代价 模式 形式 地址 附加代价 绝对地址 M M 1 寄存器 R R 0 变址 c(R) c + contents(R) 1 间接寄存器 R contents(R) 0 间接变址 c(R) contents(c + contents(R)) 1 直接量 #c c 1

8.2 目 标 机 器 8.2.2 指令的代价 指令代价简化为 1 + 指令的源和目的地址模式的附加代价 指令 代价 MOV R0,R1 1 8.2 目 标 机 器 8.2.2 指令的代价 指令代价简化为 1 + 指令的源和目的地址模式的附加代价 指令 代价 MOV R0,R1 1 MOV R5,M 2 ADD #1, R3 2 SUB 4(R0), 12(R1) 3

8.2 目 标 机 器 例 a = b + c, a、b和c都静态分配内存单元 - 可生成 MOV b, R0 8.2 目 标 机 器 例 a = b + c, a、b和c都静态分配内存单元 - 可生成 MOV b, R0 ADD c, R0 代价= 6 MOV R0, a - 也可生成 MOV b, a ADD c, a 代价= 6

8.2 目 标 机 器 例 a = b + c, a、b和c都静态分配内存单元 - 若R0,R1和R2分别含a,b和c的地址,则可生成 8.2 目 标 机 器 例 a = b + c, a、b和c都静态分配内存单元 - 若R0,R1和R2分别含a,b和c的地址,则可生成 MOV R1, R0 ADD R2, R0 代价= 2 - 若R1和R2分别含b和c的值,并且b的值在这个赋值后不再需要,则可生成 ADD R2, R1 MOV R1, a 代价= 3

8.3 基本块和流图 怎样为三地址语句序列生成目标代码? 先给出本节用例 prod = 0; i = 1; do { prod = prod + a[i]  b[i]; i = i +1; } while (i <= 20); 其三地址代码见右边 (1)prod = 0 (2) i = 1 (3) t1 = 4  i (4) t2= a[t1] (5) t3 = 4  i (6) t4 = b[t3] (7) t5 = t2  t4 (8) t6 = prod + t5 (9) prod = t6 (10) t7 = i +1 (11) i = t7 (12) if i <= 20 goto (3)

8.3 基本块和流图 8.3.1 基本块 基本块 流图 (1)prod = 0 (2) i = 1 连续的语句序列,控 制流从它的开始进入, 并从它的末尾离开 流图 再用有向边表示基本块 之间的控制流信息,就 能得到程序的流图 (1)prod = 0 (2) i = 1 (3) t1 = 4  i (4) t2= a[t1] (5) t3 = 4  i (6) t4 = b[t3] (7) t5 = t2  t4 (8) t6 = prod + t5 (9) prod = t6 (10) t7 = i +1 (11) i = t7 (12) if i <= 20 goto (3)

8.3 基本块和流图 划分基本块的方法 (1)prod = 0 (1) 首先确定所有入口语句 (2) i = 1 序列的第一个语句是 能由转移语句转到的 语句是入口语句 紧跟在转移语句后面 的语句是入口语句 (1)prod = 0 (2) i = 1 (3) t1 = 4  i (4) t2= a[t1] (5) t3 = 4  i (6) t4 = b[t3] (7) t5 = t2  t4 (8) t6 = prod + t5 (9) prod = t6 (10) t7 = i +1 (11) i = t7 (12) if i <= 20 goto (3)

8.3 基本块和流图 划分基本块的方法 (1)prod = 0 (2) 每个入口语句到下一个 (2) i = 1 入口语句之前(或到程序 结束)的语句序列构成一 个基本块 (1)prod = 0 (2) i = 1 (3) t1 = 4  i (4) t2= a[t1] (5) t3 = 4  i (6) t4 = b[t3] (7) t5 = t2  t4 (8) t6 = prod + t5 (9) prod = t6 (10) t7 = i +1 (11) i = t7 (12) if i <= 20 goto (3) 24

8.3 基本块和流图 (1) prod = 0 (1)prod = 0 (2) i = 1 B1 (2) i = 1 (3) t1 = 4  i (4) t2= a[t1] (5 ) t3 = 4  i (6 ) t4 = b[t3] (7 ) t5 = t2  t4 (8 ) t6 = prod + t5 (9 ) prod = t6 (10) t7 = i +1 (11) i = t7 (12 ) if i <= 20 goto (3) (1)prod = 0 (2) i = 1 (3) t1 = 4  i (4) t2= a[t1] (5) t3 = 4  i (6) t4 = b[t3] (7) t5 = t2  t4 (8) t6 = prod + t5 (9) prod = t6 (10) t7 = i +1 (11) i = t7 (12) if i <= 20 goto (3) B1 B2

8.3 基本块和流图 8.3.2 基本块的优化 术语 基本块的等价 有很多等价变换可用于基本块 三地址语句x = y + z引用y和z并且对x定值 一个名字的值在基本块的某一点以后还要引用的话,则说这个名字(变量)在该点是活跃的 基本块的等价 两个基本块的出口点有同样的活跃变量集合 对其中每个变量,定义其值的两个表达式相等 有很多等价变换可用于基本块 局部变换 全局变换(下一章介绍)

8.3 基本块和流图 删除局部公共子表达式 a = b + c a = b + c b = a  d b = a  d c = b + c c = b + c d = a  d d = b 删除死代码 定值x = y + z以后不再引用,则称x为死变量 可变换成

8.3 基本块和流图 交换相邻的独立语句 t1 = b + c t2 = x + y t2 = x + y t1 = b + c 可变换成 当且仅当t1和t2不相同,x和y都不是t1, 并且b和c都不是t2 代数变换 x = x + 0 可以删除 x = x  1 可以删除 x = y  2 改成x = y  y 可变换成

8.3 基本块和流图 8.3.3 流图 把控制流信息加到 基本块集合,形成 一个有向图来表示 程序 流图中的节点 首结点、前驱、后继 prod = 0 i = 1 t1 = 4  i t2= a[t1] t3 = 4  i t4 = b[t3] t5 = t2  t4 t6 = prod + t5 prod = t6 t7 = i +1 i = t7 if i <= 20 goto B2 B1 B2 29

8.3 基本块和流图 什么是循环? 外循环和内循环 prod = 0 B1 i = 1 所有结点是强连通的 唯一的循环入口 t1 = 4  i t2= a[t1] t3 = 4  i t4 = b[t3] t5 = t2  t4 t6 = prod + t5 prod = t6 t7 = i +1 i = t7 if i <= 20 goto B2 B1 B2

8.3 基本块和流图 8.3.4 下次引用信息 为每个三地址语句x = y op z决定x、y和z的下次引用信息 i: x = y op z j: … = x … k: … = … x

8.3 基本块和流图 对每个基本块从最后一个语句反向扫描到第一个语句,可以得到下次引用信息 i: x = y op z j: … = x … k: … = … x 利用下次引用信息,可以压缩临时变量需要的空间

8.4 一个简单的代码生成器 在没有收集全局信息 前,暂且以基本块为 单位来生成代码 prod = 0 B1 i = 1 t1 = 4  i t2= a[t1] t3 = 4  i t4 = b[t3] t5 = t2  t4 t6 = prod + t5 prod = t6 t7 = i +1 i = t7 if i <= 20 goto B2 B1 B2 在没有收集全局信息 前,暂且以基本块为 单位来生成代码

8.4 一个简单的代码生成器 基本考虑: 依次考虑基本块的每个语句,为其产生代码 假定三地址语句的每种算符都有对应的目标机器算符 假定计算结果留在寄存器中尽可能长的时间, 除非: 该寄存器要用于其它计算,或者 到基本块结束 为此,在生成代码过程中需要记录一些信息

8.4 一个简单的代码生成器 8.4.1 寄存器描述和地址描述 例 对a = b + c 如果寄存器Ri含b,Rj含c,且b此后不再活跃 产生ADD Rj, Ri,结果a在Ri中 如果Ri含b,但c在内存单元,b仍然不再活跃 产生ADD c, Ri,或者产生 MOV c, Rj ADD Rj, Ri 若c的值以后还要用,第二种代码较有吸引力

8.4 一个简单的代码生成器 在代码生成过程中,需要跟踪寄存器的内容和名字的地址 寄存器描述记住每个寄存器当前存的是什么 在任何一点,每个寄存器保存若干个(包括零个)名字的值 例 // 语句前,R0保存变量a的值 b = a // 不为该语句产生任何指令 // 语句后,R0保存变量a和b的值

8.4 一个简单的代码生成器 在代码生成过程中,需要跟踪寄存器的内容和名字的地址 寄存器描述记住每个寄存器当前存的是什么 在任何一点,每个寄存器保存若干个(包括零个)名字的值 名字(变量)的地址描述记住运行时每个名字的当前值可以在哪个场所找到 这个场所可以是寄存器、栈单元、内存地址、甚至是它们的某个集合 例 产生MOV c, R0后,c的值可在R0和c的存储单元找到

8.4 一个简单的代码生成器 在代码生成过程中,需要跟踪寄存器的内容和名字的地址 寄存器描述记住每个寄存器当前存的是什么 在任何一点,每个寄存器保存若干个(包括零个)名字的值 名字(变量)的地址描述记住运行时每个名字的当前值可以在哪个场所找到 这个场所可以是寄存器、栈单元、内存地址、甚至是它们的某个集合 名字的地址信息存于符号表,另建寄存器描述表 这两个描述在代码生成过程中是变化的

8.4 一个简单的代码生成器 8.4.2 代码生成算法 对每个三地址语句x = y op z 调用函数getreg决定放y op z计算结果的场所L 查看y的地址描述,确定y值当前的一个场所y。如果y的值还不在L中,产生指令MOV y,L 产生指令op z,L,其中z是z的当前场所之一 如果y和/或z的当前值不再引用,在块的出口也不活跃,并且还在寄存器中,那么修改寄存器描述

8.4 一个简单的代码生成器 8.4.3 寄存器选择函数 函数getreg返回保存x = y op z的x值的场所L 如果名字y在R中,这个R不含其它名字的值,并且在执行x = y op z后y不再有下次引用,那么返回这个R作为L 否则,如果有的话,返回一个空闲寄存器 否则,如果x在块中有下次引用,或者op是必须用寄存器的算符,那么找一个已被占用的寄存器R(可能产生MOV R,M指令,并修改 M的描述 ) 否则,如果x在基本块中不再引用,或者找不到适当的被占用寄存器,选择x的内存单元作为L

8.4 一个简单的代码生成器 赋值语句d = (a  b) + (a c) + (a  c) 编译产生三地址语句序列: t1 = a  b t2 = a  c t3 = t1 + t2 d = t3 + t2

8.4 一个简单的代码生成器 语 句 生成的代码 寄存器描述 名字的地址描述 寄存器空 t1 = a  b MOV a, R0 语 句 生成的代码 寄存器描述 名字的地址描述 寄存器空 t1 = a  b MOV a, R0 SUB b, R0 R0含t1 t1在R0中 t2 = a  c MOV a, R1 SUB c, R1 R1含t2 t2在R1中 t3 = t1+ t2 ADD R1,R0 R0含t3 t3在R0中 d = t3 + t2 R0含d d在R0中 MOV R0, d d在R0和内存中

8.4 一个简单的代码生成器 语 句 生成的代码 寄存器描述 名字的地址描述 寄存器空 t1 = a  b MOV a, R0 语 句 生成的代码 寄存器描述 名字的地址描述 寄存器空 t1 = a  b MOV a, R0 SUB b, R0 R0含t1 t1在R0中 t2 = a  c MOV a, R1 SUB c, R1 R1含t2 t2在R1中 t3 = t1+ t2 ADD R1,R0 R0含t3 t3在R0中 d = t3 + t2 R0含d d在R0中 MOV R0, d d在R0和内存中

8.4 一个简单的代码生成器 语 句 生成的代码 寄存器描述 名字的地址描述 寄存器空 t1 = a  b MOV a, R0 语 句 生成的代码 寄存器描述 名字的地址描述 寄存器空 t1 = a  b MOV a, R0 SUB b, R0 R0含t1 t1在R0中 t2 = a  c MOV a, R1 SUB c, R1 R1含t2 t2在R1中 t3 = t1+ t2 ADD R1,R0 R0含t3 t3在R0中 d = t3 + t2 R0含d d在R0中 MOV R0, d d在R0和内存中

8.4 一个简单的代码生成器 语 句 生成的代码 寄存器描述 名字的地址描述 寄存器空 t1 = a  b MOV a, R0 语 句 生成的代码 寄存器描述 名字的地址描述 寄存器空 t1 = a  b MOV a, R0 SUB b, R0 R0含t1 t1在R0中 t2 = a  c MOV a, R1 SUB c, R1 R1含t2 t2在R1中 t3 = t1+ t2 ADD R1,R0 R0含t3 t3在R0中 d = t3 + t2 R0含d d在R0中 MOV R0, d d在R0和内存中

8.4 一个简单的代码生成器 语 句 生成的代码 寄存器描述 名字的地址描述 寄存器空 t1 = a  b MOV a, R0 语 句 生成的代码 寄存器描述 名字的地址描述 寄存器空 t1 = a  b MOV a, R0 SUB b, R0 R0含t1 t1在R0中 t2 = a  c MOV a, R1 SUB c, R1 R1含t2 t2在R1中 t3 = t1+ t2 ADD R1,R0 R0含t3 t3在R0中 d = t3 + t2 R0含d d在R0中 MOV R0, d d在R0和内存中

8.4 一个简单的代码生成器 语 句 生成的代码 寄存器描述 名字的地址描述 寄存器空 t1 = a  b MOV a, R0 语 句 生成的代码 寄存器描述 名字的地址描述 寄存器空 t1 = a  b MOV a, R0 SUB b, R0 R0含t1 t1在R0中 t2 = a  c MOV a, R1 SUB c, R1 R1含t2 t2在R1中 t3 = t1+ t2 ADD R1,R0 R0含t3 t3在R0中 d = t3 + t2 R0含d d在R0中 MOV R0, d d在R0和内存中

8.4 一个简单的代码生成器 前三条指令可以修改,使执行代价降低 修改前 修改后 MOV a, R0 MOV a, R0 修改前 修改后 MOV a, R0 MOV a, R0 SUB b, R0 MOV R0,R1 MOV a, R1 SUB b, R0 SUB c, R1 SUB c, R1 . . . . . .

8.4 一个简单的代码生成器 8.4.4 为变址和指针语句产生代码 变址与指针运算的三地址语句的处理和二元算符的处理相同

8.4 一个简单的代码生成器 8.4.5 条件语句 实现条件转移有两种方式 根据寄存器的值是否为下面六个条件之一进行分支:负、零、正、非负、非零和非正 用条件码来表示计算的结果或装入寄存器的值是负、零还是正

8.4 一个简单的代码生成器 1、根据寄存器的值是否为下面六个条件之一进行分支:负、零、正、非负、非零和非正 例 if x < y goto z 把x减y的值存入寄存器R 如果R的值为负,则跳到z

8.4 一个简单的代码生成器 2、用条件码的例子 例 若if x < y goto z | 则:x = y + w 的实现是: | if x < 0 goto z CMP x, y | 的实现是: CJ< z | MOV y, R0 | ADD w, R0 | MOV R0,x | CJ< z

本 章 要 点 代码生成器设计中的主要问题:存储管理、计算次序的选择、寄存器的分配、指令的选择等 目标机器几种常用的地址模式和一些常用的指令 本 章 要 点 代码生成器设计中的主要问题:存储管理、计算次序的选择、寄存器的分配、指令的选择等 目标机器几种常用的地址模式和一些常用的指令 基本块和程序流图 简单的代码生成算法

例 题 1 先完成有函数调用的 子表达式的计算 在SPARC/SUNOS上,经某编译器编译,程序的结果 例 题 1 在SPARC/SUNOS上,经某编译器编译,程序的结果 是120。把第4行的abs(1)改成1的话,则程序结果是1 int fact(){ static int i=5; if(i==0) { return(1); } else { i=i-1; return((i+abs(1))  fact());} } main(){ printf("factor of 5 = %d\n", fact()); 先完成有函数调用的 子表达式的计算

例 题 2 下面的程序在X86/Linux机器上编译后的运行结 果是7,而在SPARC/SUNOS机器上编译后的运 例 题 2 下面的程序在X86/Linux机器上编译后的运行结 果是7,而在SPARC/SUNOS机器上编译后的运 行结果是6。试分析运行结果不同的原因。 main() { long i; i = 0; printf("%ld\n", (++i)+(++i)+(++i) ); } / ++i 就是i = i + 1 /

例 题 2 按一般的代码生成,++i 的计算结果保留在 寄存器中,因此这三个++i 的计算次序不会 影响最终的结果。结果应该是6 + = i 例 题 2 按一般的代码生成,++i 的计算结果保留在 寄存器中,因此这三个++i 的计算次序不会 影响最终的结果。结果应该是6 + = i 1

例 题 2 按一般的代码生成,++i 的计算结果保留在 寄存器中,因此这三个++i 的计算次序不会 影响最终的结果。结果应该是6 例 题 2 按一般的代码生成,++i 的计算结果保留在 寄存器中,因此这三个++i 的计算次序不会 影响最终的结果。结果应该是6 结果是7的话,一定是 某个++i 的结果未保 留在寄存器中。上层 计算对它的引用落在 另一个++i 的计算的 后面 + = i 1

例 题 2 如果机器有INC指令的话,编译器极可能产生一条INC指令来完成++i X86/Linux机器上果真是这么做的 + = i 1

例 题 2 将表达式改成(++i)+((++i)+(++i)), 结果会怎样? 在SPARC/SUNOS机器上的结果仍然是6 例 题 2 将表达式改成(++i)+((++i)+(++i)), 结果会怎样? 在SPARC/SUNOS机器上的结果仍然是6 在X86/Linux机器上的结果是9 + = i 1

例 题 3 下面C语言程序如下, 运行时输出105, 为什么? main() { long i; i=10; 例 题 3 下面C语言程序如下, 运行时输出105, 为什么? main() { long i;   i=10; i=(i+5) + (i=i5); printf("%d\n", i); } 寄存器分配策略可能导致先计算右子表达式 二元运算 表达式 需2个R 需3个R 需几个R

例 题 4 下面是一个C语言程序,在X86/Linux机器上编译(未使用优化)该程序得到的汇编代码见下页(为便于理解,略去了和讨论本问题无关的部分,并改动了一个地方) main() { long i,j; if ( j ) i++; else while ( i ) j++; }

例 题 4 main() { incl -4(%ebp) long i,j; jmp .L3 例 题 4 main() { incl -4(%ebp) long i,j; jmp .L3 long i,j; .L2: .L4: (写在一行以省空间) if ( j ) cmpl $0,-4(%ebp) i++; jne .L6 else jmp .L5 while ( i ) j++; .L6: } incl -8(%ebp) pushl %ebp jmp .L4 movl %esp,%ebp .L5: .L3: .L1: subl $8,%esp leave cmpl $0,-8(%ebp) ret je .L2

例 题 4 为什么会出现一条指令前有多个标号的情况,如.L2和.L4,还有.L5、.L3和.L1?从控制流语句的中间代码结构加以解释 例 题 4 为什么会出现一条指令前有多个标号的情况,如.L2和.L4,还有.L5、.L3和.L1?从控制流语句的中间代码结构加以解释 条件语句和循环语句的中间代码结构如下: if (E) then S1 else S2 while (E) do S E的代码 L4: E的代码 假转 L2 真转 L6 S1的代码 转 L5 转 L3 L6: S的代码 L2: S2的代码 转 L4 L3: L5: 当while语句作为条件语句的S2时,会出现所说情况

例 题 4 每个函数都有这样的标号.L1,它的作用是什么,为什么本函数没有引用该标号的地方? 例 题 4 每个函数都有这样的标号.L1,它的作用是什么,为什么本函数没有引用该标号的地方? . . . jmp .L4 .L5: .L3: .L1: leave ret .L1标号定义的入口是返回调用者时该执行的指令,在函数内部有return语句时就会跳转到.L1

习 题 第一次:8.4(只为8.1(e)生成代码)