编译原理代码生成8.ppt

《编译原理代码生成8.ppt》由会员分享，可在线阅读，更多相关《编译原理代码生成8.ppt（59页珍藏版）》请在三一文库上搜索。

1、第八章 代 码 生 成,本章内容 一个简单的代码生成算法 涉及存储管理，指令选择，寄存器分配和计算次序选择等基本问题,8.1 代码生成器的设计中的问题,8.1.1 目标程序 可执行目标模块 可重定位目标模块 允许程序模块分别编译 调用其它先前编译好的程序模块 汇编语言程序 免去编译器重复汇编器的工作 从教学角度，增加可读性,8.1 代码生成器的设计中的问题,8.1.2 指令的选择 目标机器指令系统的性质决定了指令选择的难易程度，指令系统的统一性和完备性是重要的因素 指令的速度和机器特点是另一些重要的因素,8.1 代码生成器的设计中的问题,若不考虑目标程序的效率，指令的选择是直截了当的 三地址语

2、句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 MO

3、V 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、.4 计算次序的选择 某种计算次序可能会比其它次序需要较少的寄存器来保存中间结果,8.2 目 标 机 器,8.2.1 目标机器的指令系统 选择可作为几种微机代表的寄存器机器 四字节组成一个字，有n个通用寄存器R0,R1, ,Rn-1。 二地址指令 op 源，目的 MOV 源传到目的 ADD 源加到目的 SUB 目的减去源,8.2 目 标 机 器,地址模式和它们的汇编语言形式及附加代价 模式 形式 地址 附加代价 绝对地址 M M 1 寄存器 R R 0 变址 c(R) c + contents(R) 1 间接寄存器 R contents(R) 0 间接变址 c(R) contents(c +

5、contents(R) 1 直接量 #c c 1,8.2 目 标 机 器,指令实例 MOV R0, M MOV 4(R0), M contents(4 + contents(R0) MOV 4(R0), M contents(contents (4 + contents(R0) ) ) MOV #1, R0,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都静态分配内

6、存单元 MOV b, R0 ADD c, R0 代价= 6 MOV R0, a,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的地址，则 MOV R1, R0 ADD R2, R0 代价= 2,8.2 目 标 机 器,a = b + c， a、b和c都静态分配内存单元 若R0，R1和R2分别含a，b和c的地址，则 MOV R1, R0 A

7、DD R2, R0 代价= 2 若R1和R2分别含b和c的值，并且b的值在这个 赋值后不再需要，则 ADD R2, R1 MOV R1, a 代价= 3,8.3 基本块和流图,怎样为三地址语句序列生成目标代码？ |(1) prod = 0 prod = 0; |(2) i = 1 i = 1; |(3) t1 = 4 i do |(4) t2= at1 prod = prod + ai bi; |(5 ) t3 = 4 i i = i +1; |(6 ) t4 = bt3 while (i = 20); |(7 ) t5 = t2 t4 |(8 ) t6 = prod + t5 |(9 ) p

8、rod = t6 |(10) t7 = i +1 |(11) i = t7 |(12 ) if i = 20 goto (3),8.3 基本块和流图,8.3.1 基本块 基本块：连续的语句序列，控制流从它的开始进入，并从它的末尾离开 再用有向边表示基本块之间的控制流信息，就能得到程序的流图,8.3 基本块和流图,三地址语句序列的划分基本块 首先确定所有的入口语句 序列的第一个语句是入口语句 能由条件转移语句或无条件转移语句转到的语句是入口语句 紧跟在条件转移语句或无条件转移语句后面的语句是入口语句 每个入口语句到下一个入口语句之前的语句序列构成一个基本块,8.3 基本块和流图,(1) prod

9、 = 0 (2) i = 1 (3) t1 = 4 i (4) t2= at1 (5 ) t3 = 4 i (6 ) t4 = bt3 (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.2 基本块的优化 三地址语句x = y + z引用y和z并对x定值 一个名字的值在基本块的某一点以后还要引用的话，则说这个名字在该点是活跃的 基本块的等价 两个基本块计算一组同样的表达式 这些表达式的值分别代表同样的活跃名字的值

10、 有很多等价变换可用于基本块 局部变换 全局变换,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

11、.3 基本块和流图,8.3.3 流图 把控制流信息加到基本块集合，形成一个有向图来表示程序 首结点、前驱、后继,8.3 基本块和流图,什么是循环? 所有结点是强连通的 唯一的循环入口 外循环和内循环,8.3 基本块和流图,8.3.4 下次引用信息 为每个三地址语句x = y op z决定x、y和z的下次引用信息 i: x = y op z . . . 没有对x的赋值 j: = x . . . 没有对x的赋值 k: = x,8.3 基本块和流图,8.3.4 下次引用信息 为每个三地址语句x = y op z决定x、y和z的下次引用信息 i: x = y op z . . . 没有对x的赋值 j:

12、 = x . . . 没有对x的赋值 k: = x,8.3 基本块和流图,对每个基本块从最后一个语句反向扫描到第一个语句，可以得到下次引用信息 i: x = y op z . . . 没有对x的赋值 j: = x . . . 没有对x的赋值 k: = x,8.3 基本块和流图,对每个基本块从最后一个语句反向扫描到第一个语句，可以得到下次引用信息 i: x = y op z . . . 没有对x的赋值 j: = x . . . 没有对x的赋值 k: = x 利用下次引用信息，可以压缩临时变量需要的空间,8.4 一个简单的代码生成器,依次考虑基本块的每个语句，为其产生代码 假定三地址语句的每种算符

13、都有对应的目标机器算符 假定计算结果留在寄存器中尽可能长的时间, 除非： 该寄存器要用于其它计算，或者 到基本块结束,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 一个简单的代码生成器,在代码生成过程中，需要跟

14、踪寄存器的内容和 名字的地址 寄存器描述记住每个寄存器当前存的是什么 在任何一点，每个寄存器保存若干个(包括零个)名字的值 名字的地址描述记住运行时每个名字的当前值可以在哪个场所找到 这个场所可以是寄存器、栈单元、内存地址、甚至是它们的某个集合 这些信息可以存于符号表中 这两个描述在代码生成过程中是变化的,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的当前场所之一 如果

15、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 一个简单的

16、代码生成器,赋值语句d = (a b) + (a c) + (a c) 编译产生三地址语句序列： t1 = a b t2 = a c t3 = t1 + t2 d = t3 + t2,8.4 一个简单的代码生成器,8.4 一个简单的代码生成器,前三条指令可以修改，使执行代价降低 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 一个简

17、单的代码生成器,8.4.5 条件语句 实现条件转移有两种方式 根据寄存器的值是否为下面六个条件之一进行分支：负、零、正、非负、非零和非正 用条件码来表示计算的结果或装入寄存器的值是负、零还是正,8.4 一个简单的代码生成器,根据寄存器的值是否为下面六个条件之一进行 分支：负、零、正、非负、非零和非正 例如：if x y goto z 把x减y的值存入寄存器R 如果R的值为负，则跳到z,8.4 一个简单的代码生成器,用条件码的例子 if x y goto z x = y + w 的实现： if x 0 goto z CMP x, y 的实现： CJ z MOV y， R0 ADD w， R0 M

18、OV R0，x CJ z,本 章 要 点,代码生成器设计中的主要问题：存储管理、计算次序的选择、寄存器的分配、指令的选择等 目标机器几种常用的地址模式和一些常用的指令 基本块和程序流图 简单的代码生成算法,例 题 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 = %dn“, fact(); ,例 题 2,下

19、面的程序在X86/Linux机器上编译后的运行结 果是7，而在SPARC/SUNOS机器上编译后的运 行结果是6。试分析运行结果不同的原因。 main() long i; i = 0; printf(“%ldn“, (+i)+(+i)+(+i) ); ,例 题 2,按一般的代码生成，i = i +1的计算结果保留在 寄存器中，因此这三个i = i +1的计算次序不会 影响最终的结果。结果应该是6。,例 题 2,按一般的代码生成，i = i +1的计算结果保留在 寄存器中，因此这三个i = i +1的计算次序不会 影响最终的结果。结果应该是6。 结果是7的话，一定是 某个i = i +1的结果未

20、保 留在寄存器中。上层 计算对它的引用落在 计算另一个i = i +1的 后面,例 题 2,如果机器有INC指令的话，编译器极可能产生一条INC指令来完成i = i +1 X86/Linux机器上果真是这么做的,例 题 2,将表达式改成(+i)+(+i)+(+i), 结果会怎样？,例 题 2,将表达式改成(+i)+(+i)+(+i), 结果会怎样？ 在SPARC/SUNOS机器上的结果仍然是6。 在X86/Linux机器上的结果是9。,例 题 3,下面C语言程序如下, 运行时输出105, 为什么？ main() long i; i=10; i=(i+5) + (i=i5); printf(“%

21、dn“,i); ,例 题 3,下面C语言程序如下, 运行时输出105, 为什么？ main() long i; i=10; i=(i+5) + (i=i5); printf(“%dn“,i); ,例 题 4,下面是一个C语言程序和在X86/Linux机器上编译（未使用优化）该程序得到的汇编代码见下页（为便于理解，略去了和讨论本问题无关的部分，并改动了一个地方） main() long i,j; if ( j ) i+; else while ( i ) j+; ,例 题 4,main() incl -4(%ebp) jmp .L3 long i,j; .L2: .L4:(写在一行以省空间) i

22、f ( 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？从控制流语句的中间代码结构加以解释。 条件语句和循环语句的中间代码结构如下： 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，它的作用是什么，为什么本函数没有引用该标号的地方？ .L1标号定义的入口是返回调用者时该执行的指令，在函数内部有return语句时就会跳转到.L1。,习 题,第一次：8.4（只为8.1(e)生成代码）,