软件开发过程与项目管理综述 - 天津大学

1、代码生成代码生成授课：胡静授课：胡静2022-2-16编译技术编译技术2编译器的结构编译器的结构出出错错处处理理语法分析程序语法分析程序语义分析程序语义分析程序目标代码生成程序目标代码生成程序词法分析程序词法分析程序中间代码生成程序中间代码生成程序代码优化程序代码优化程序表表格格管管理理2022-2-16编译技术编译技术3概述概述代码生成阶段的功能代码生成阶段的功能输入：编译器前端生成的中间表示（输入：编译器前端生成的中间表示（IR）和相关的符）和相关的符号表信息号表信息输出：输出：的目标程序的目标程序对代码生成器的要求：对代码生成器的要求：语义等价语义等价高质量高质量有效的利用目标机器上的可

2、用资源有效的利用目标机器上的可用资源高效率高效率代码生成器本身运行效率要高代码生成器本身运行效率要高前端前端代码代码优化器优化器代码代码生成器生成器源程序源程序中间中间代码代码中间中间代码代码目标目标程序程序2022-2-16编译技术编译技术4代码生成器中的优化问题代码生成器中的优化问题从数学上来讲，为给定源程序生成一个最右的目标从数学上来讲，为给定源程序生成一个最右的目标程序是不可判定的问题，在代码生成中碰到的很多程序是不可判定的问题，在代码生成中碰到的很多子问题（比如寄存器分配问题）都具有难以处理的子问题（比如寄存器分配问题）都具有难以处理的计算复杂度。计算复杂度。在实践中在实践中 ，我们

3、需要使用那些能够产生，我们需要使用那些能够产生的代码的启发性技术。的代码的启发性技术。局部最优：指令条数、指令执行顺序、寄存器分配、局部最优：指令条数、指令执行顺序、寄存器分配、内存分配内存分配设计良好的代码生成器产生的代码比那些简单的代码设计良好的代码生成器产生的代码比那些简单的代码生成器产生的代码快好几倍。生成器产生的代码快好几倍。2022-2-16编译技术编译技术5代码生成器和代码优化器的关系代码生成器和代码优化器的关系代码优化和代码生成步骤通常称为编译器的后端代码优化和代码生成步骤通常称为编译器的后端优化器的功能优化器的功能把一个把一个IR映射成另一个可用于产生高效代码的映射成另一个可

4、用于产生高效代码的IR可能在生成目标程序之前对可能在生成目标程序之前对IR做多遍处理。做多遍处理。减少中间代码量、计算顺序减少中间代码量、计算顺序不论代码是否被优化过，都可以使用代码生成器。不论代码是否被优化过，都可以使用代码生成器。2022-2-16编译技术编译技术6代码生成器的主要任务代码生成器的主要任务指令选择：选择适当的目标机指令来实现指令选择：选择适当的目标机指令来实现IR语句。语句。寄存器分配和指派：考虑把哪个值放在哪个寄存器寄存器分配和指派：考虑把哪个值放在哪个寄存器中。中。指令排序：按照什么顺序来安排指令的执行。指令排序：按照什么顺序来安排指令的执行。2022-2-16编译技术

5、编译技术7本章内容结构本章内容结构1.代码生成器设计中的问题代码生成器设计中的问题代码生成器的任务的重要性概述代码生成器的任务的重要性概述2.目标语言目标语言一个简单的机器模型一个简单的机器模型把输入的把输入的IR翻译成简单寄存器机器的目标语言指令序翻译成简单寄存器机器的目标语言指令序列的算法列的算法3.目标代码中的地址目标代码中的地址给出一个编译器需要生成什么样的目标代码，以支持给出一个编译器需要生成什么样的目标代码，以支持常见源语言中所包含的抽象机制常见源语言中所包含的抽象机制概述静态和栈式数据区分配的实现方法概述静态和栈式数据区分配的实现方法说明如何把说明如何把IR中的名字转换成为目标代

6、码中的地址中的名字转换成为目标代码中的地址2022-2-16编译技术编译技术8本章内容结构（本章内容结构（cont.）4.基本块和流图基本块和流图如何把代码划分为基本块如何把代码划分为基本块每个基本块由一组总是每个基本块由一组总是一起执行的指令组成。一起执行的指令组成。5.基本块的优化基本块的优化针对基本块的一些简单的局部转换方法，从而得到更针对基本块的一些简单的局部转换方法，从而得到更加高效的代码加高效的代码已经是代码优化的初步形式已经是代码优化的初步形式例如：寻找公共子表达式，相应的把算术运算替换为例如：寻找公共子表达式，相应的把算术运算替换为更简单的拷贝运算。更简单的拷贝运算。2022-

7、2-16编译技术编译技术9本章内容结构（本章内容结构（cont.）6.一个简单的代码生成器一个简单的代码生成器给出一个简单的代码生成算法给出一个简单的代码生成算法依次为每个语句生成代码，并把运算分量尽可能长时间的保存依次为每个语句生成代码，并把运算分量尽可能长时间的保存在寄存器中。在寄存器中。可以很容易的使用窥孔优化技术进行优化可以很容易的使用窥孔优化技术进行优化7.窥孔优化窥孔优化讨论窥孔优化技术讨论窥孔优化技术指令选择和寄存器分配：指令选择和寄存器分配：8.寄存器分配和指派寄存器分配和指派9.通过树重写来选择指令通过树重写来选择指令10.表达式的优化代码的生成表达式的优化代码的生成11.使

8、用动态规划的代码生成使用动态规划的代码生成2022-2-16编译技术编译技术101.代码生成器设计中的问题代码生成器设计中的问题代码生成器的主要任务：指令选择、寄存器分配和代码生成器的主要任务：指令选择、寄存器分配和指派以及指令排序指派以及指令排序代码生成器的设计依赖于中间表示形式、目标语言代码生成器的设计依赖于中间表示形式、目标语言和运行时刻系统的特定细节，但上述任务在几乎所和运行时刻系统的特定细节，但上述任务在几乎所有的代码生成器设计中都会碰到。有的代码生成器设计中都会碰到。代码生成器的标准代码生成器的标准易于实现、测试和维护。易于实现、测试和维护。2022-2-16编译技术编译技术111

9、.1代码生成器的输入代码生成器的输入代码生成器的输入代码生成器的输入前端生成的源程序的中间表示形式：前端生成的源程序的中间表示形式：四元式、三元式、间接三元式等：四元式、三元式、间接三元式等虚拟机表示方式：字节代码和堆栈机代码虚拟机表示方式：字节代码和堆栈机代码线性表示方法：后缀表达式等线性表示方法：后缀表达式等：语法树和：语法树和DAG图图符号表中的信息符号表中的信息确定确定IR中的名字所指的数据对象的运行时中的名字所指的数据对象的运行时刻地址。刻地址。认为代码生成器的输入没有词法、语法、静态语义错误。完认为代码生成器的输入没有词法、语法、静态语义错误。完成了必要的类型检查，类型转换运算已经

10、被插入倒必要的地成了必要的类型检查，类型转换运算已经被插入倒必要的地方。方。2022-2-16编译技术编译技术121.2目标程序目标程序实现高质量的机器代码的代码生成器的难度受到目标机器的实现高质量的机器代码的代码生成器的难度受到目标机器的指令集体系结构的极大影响。指令集体系结构的极大影响。常见的目标体系结构：常见的目标体系结构：RISC（精简指令集计算机）：很多寄存器、三地址指令、简单（精简指令集计算机）：很多寄存器、三地址指令、简单的寻址方式和一个相对简单的指令集体系结构。的寻址方式和一个相对简单的指令集体系结构。CISC（复杂指令集计算机）：较少寄存器、两地址指令、多种（复杂指令集计算机

11、）：较少寄存器、两地址指令、多种寻址方式、多种类型的寄存器、可变长度的指令和具有副作用寻址方式、多种类型的寄存器、可变长度的指令和具有副作用的指令的指令基于堆栈的结构：运算是通过把运算分量压入一个栈，然后再基于堆栈的结构：运算是通过把运算分量压入一个栈，然后再对栈顶的运算分量进行运算而完成的。栈顶元素可以保存在寄对栈顶的运算分量进行运算而完成的。栈顶元素可以保存在寄存器中。存器中。2022-2-16编译技术编译技术131.2目标程序（目标程序（cont.）输出使用绝对地址的及其语言程序的优点是程序可以放在内输出使用绝对地址的及其语言程序的优点是程序可以放在内存中的某个固定位置上，并立即执行。存

12、中的某个固定位置上，并立即执行。输出可重定位的机器语言程序（目标模块）可以使各个子程输出可重定位的机器语言程序（目标模块）可以使各个子程序能够被分别编译。但是需要链接和加载。如果目标机没有序能够被分别编译。但是需要链接和加载。如果目标机没有自动处理重定位，编译器就必须向加载器提供明确的重定位自动处理重定位，编译器就必须向加载器提供明确的重定位信息，以便把分开编译的程序模块链接起来。信息，以便把分开编译的程序模块链接起来。本章中，我们输出汇编程序，使用一个非常简单的类本章中，我们输出汇编程序，使用一个非常简单的类RISC计计算机作为目标机：算机作为目标机：只要变量地址可以通过偏移量和存放于符号表

13、中的其他信息计只要变量地址可以通过偏移量和存放于符号表中的其他信息计算出来，代码生成器就可以为源程序中的名字生成可重定位地算出来，代码生成器就可以为源程序中的名字生成可重定位地址或绝对地址。址或绝对地址。RISC上加一下类上加一下类CISC的寻址方式就可以讨论的寻址方式就可以讨论CISC机器的代码机器的代码生成技术。生成技术。2022-2-16编译技术编译技术141.3指令选择指令选择代码生成器将代码生成器将IR映射成目标机上运行的代码序列，映射成目标机上运行的代码序列，其复杂性由如下因素决定：其复杂性由如下因素决定：IR的层次、指令集体系的层次、指令集体系结构本身的特性、想要达到的生成代码的

14、质量结构本身的特性、想要达到的生成代码的质量IR的层次的层次如果如果IR是高层次的，代码生成器就要使用代码模板把是高层次的，代码生成器就要使用代码模板把每个每个IR语句翻译成为机器指令序列。这种方式产生的语句翻译成为机器指令序列。这种方式产生的代码通常质量不佳，需要进一步优化代码通常质量不佳，需要进一步优化如果如果IR中反映了某些计算机底层次细节，那么就可以中反映了某些计算机底层次细节，那么就可以产生较高校的代码序列产生较高校的代码序列2022-2-16编译技术编译技术151.3指令选择（指令选择（cont.）指令集体系结构本身的特性指令集体系结构本身的特性指令集的统一性和完整性是很重要的两个

15、因素。指令集的统一性和完整性是很重要的两个因素。如果目标机没有以同一的方式支持每种数据类型，那如果目标机没有以同一的方式支持每种数据类型，那么总体规则的每个例外都需要进行特别处理。么总体规则的每个例外都需要进行特别处理。例如在某些机器上，浮点数运算使用单独的寄存器完例如在某些机器上，浮点数运算使用单独的寄存器完成成指令速度和机器的特有用法是另外一些重要因素。指令速度和机器的特有用法是另外一些重要因素。2022-2-16编译技术编译技术161.3指令选择（指令选择（cont.）指令集体系结构本身的特性（例子）指令集体系结构本身的特性（例子）不考虑目标程序的效率，可以对三地址生成一个代码骨架，不考

16、虑目标程序的效率，可以对三地址生成一个代码骨架，来定义对这个构造生成什么样的目标代码来定义对这个构造生成什么样的目标代码三地址语句：三地址语句：x=y+zLD R0,y/R0=y (把把y装载到寄存器装载到寄存器R0)ADDR0,R0,z /R0=R0+z (把把z加到加到R0)STx,R0/x=R0 (把把R0保存到保存到x)三地址语句：三地址语句：a=b+cd=a+eLD R0,b/R0=bADDR0,R0,c /R0=R0+cSTa,R0/a=R0LD R0,a/R0=aADDR0,R0,e /R0=R0+eSTd,R0/d=R02022-2-16编译技术编译技术171.3指令选择（指令

17、选择（cont.）想要达到的生成代码的质量想要达到的生成代码的质量生成代码的质量通常是由它的运行速度和大小来确定生成代码的质量通常是由它的运行速度和大小来确定的。的。一个给定的一个给定的IR程序可以用多种不同的代码序列来实程序可以用多种不同的代码序列来实现，简单翻译产生的代码通常效率低的难以接受。现，简单翻译产生的代码通常效率低的难以接受。要设计良好的代码序列，我们必须知道指令的代要设计良好的代码序列，我们必须知道指令的代价，但是这个是难以精确得知的。对于给定的三地价，但是这个是难以精确得知的。对于给定的三地址构造，需要有关该构造的所在上下文的信息才能址构造，需要有关该构造的所在上下文的信息才

18、能决定哪个是最好的及其代码序列决定哪个是最好的及其代码序列可以用树模式匹配过程来建模可以用树模式匹配过程来建模2022-2-16编译技术编译技术181.3指令选择（指令选择（cont.）想要达到的生成代码的质量（例子）想要达到的生成代码的质量（例子）如果目标机由一个如果目标机由一个“加一加一”指令（指令（INC）三地址语句：三地址语句：a=a+1LD R0,a/R0=aADDR0,R0,#1/R0=R0+cSTa,R0/a=R0IDCa2022-2-16编译技术编译技术191.4寄存器分配寄存器分配代码生成的关键问题之一是决定哪个值放在哪个寄代码生成的关键问题之一是决定哪个值放在哪个寄存器中。

19、存器中。寄存器是目标机上运行速度最快的计算单元，但是数寄存器是目标机上运行速度最快的计算单元，但是数量较少。量较少。使用寄存器运算分量的指令总是比那些运算分量在内使用寄存器运算分量的指令总是比那些运算分量在内存中的指令短并且快。存中的指令短并且快。寄存器的使用通常分解为两个子问题：寄存器的使用通常分解为两个子问题：寄存器分配：对于源程序中的每个点，我们选择一组寄存器分配：对于源程序中的每个点，我们选择一组将被存放在寄存器中的变量。将被存放在寄存器中的变量。寄存器指派：我们指定一个变量被存放在哪个寄存器寄存器指派：我们指定一个变量被存放在哪个寄存器中中2022-2-16编译技术编译技术201.4

20、寄存器分配（寄存器分配（cont.）即使对于单寄存器机器，找到一个从寄存器到变量即使对于单寄存器机器，找到一个从寄存器到变量的最优指派也是很困难的。的最优指派也是很困难的。NP完全问题完全问题目标机的硬件和目标机的硬件和/或操作系统可能要求代码遵守特定或操作系统可能要求代码遵守特定的寄存器使用规则，这会使问题更加复杂。的寄存器使用规则，这会使问题更加复杂。2022-2-16编译技术编译技术211.4寄存器分配（寄存器分配（cont.）例子：有些机器要求为某些运算分量和结果使用寄存例子：有些机器要求为某些运算分量和结果使用寄存器对（即一个偶数号寄存器和相邻的奇数号寄存器对（即一个偶数号寄存器和相

21、邻的奇数号寄存器）。假设在某些机器上，整数乘法和整数除法就器）。假设在某些机器上，整数乘法和整数除法就涉及寄存器对。涉及寄存器对。乘法指令：乘法指令：M x,y其中被乘数其中被乘数x是寄存器对中的奇数号寄存器，是寄存器对中的奇数号寄存器，y可以在任意地方，乘法的结果占据了整个寄存器对。可以在任意地方，乘法的结果占据了整个寄存器对。除法指令：除法指令：D x,y其中被除数占据了整个寄存器对，其中被除数占据了整个寄存器对，x是其中的偶数号寄存器，除数是是其中的偶数号寄存器，除数是y。相除后偶数号寄存器保存余数，奇数号寄存器保存商。相除后偶数号寄存器保存余数，奇数号寄存器保存商。2022-2-16编

22、译技术编译技术221.4寄存器分配（寄存器分配（cont.）乘法指令：乘法指令：M x,y其中被乘数其中被乘数x是寄存器对中的奇数号寄存器，是寄存器对中的奇数号寄存器，y可以在任意地方，乘法的结果占据了整个寄存器对。可以在任意地方，乘法的结果占据了整个寄存器对。除法指令：除法指令：D x,y其中被除数占据了整个寄存器对，其中被除数占据了整个寄存器对，x是其中的偶数号寄存器，除数是是其中的偶数号寄存器，除数是y。相除后偶数号寄存器保存余数，奇数号寄存器保存商。相除后偶数号寄存器保存余数，奇数号寄存器保存商。t = a + bt = t * ct = t / dt = a + bt = t + c

23、t = t / dL R1 , aA R1 , bM R1 , cD R0 , dST R1 , tL R0 , aA R0 , bA R0 , cSRDA R0 , 32D R0 , dST R1 , tSRDASRDA表示双算数右表示双算数右移。这句话表示把移。这句话表示把除数从除数从R0R0中移入中移入R1R1并把并把R0R0清空清空2022-2-16编译技术编译技术231.5求值顺序求值顺序计算执行的顺序会影响目标代码的效率。计算执行的顺序会影响目标代码的效率。某些计算顺序相对于其他的计算顺序而言对用于存某些计算顺序相对于其他的计算顺序而言对用于存放中间结果的寄存器的需求更少。放中间结

24、果的寄存器的需求更少。找到这个最好顺序的问题是一个找到这个最好顺序的问题是一个NP完全问题完全问题2022-2-16编译技术编译技术242.目标语言目标语言为了给某个目标机器上的一个完整的源语言生成高为了给某个目标机器上的一个完整的源语言生成高质量的代码，我们需要了解该目标机的许多细节。质量的代码，我们需要了解该目标机的许多细节。本章中，我们将使用一个简单计算机的汇编代码作本章中，我们将使用一个简单计算机的汇编代码作为目标语言。为目标语言。2022-2-16编译技术编译技术252.1 一个简单的目标机模型一个简单的目标机模型目标机是一个三地址机器的模型，具有的功能：目标机是一个三地址机器的模型

25、，具有的功能：加载、保存操作加载、保存操作计算操作计算操作跳转操作跳转操作条件跳转条件跳转内存按照字节寻址内存按照字节寻址具有具有n个通用寄存器个通用寄存器R0,R1,Rn-1。使用一个很有限的指令集，并假设所有的运算分量都是整数使用一个很有限的指令集，并假设所有的运算分量都是整数大部分指令包含一个运算符，然后是一个目标地址，最后是大部分指令包含一个运算符，然后是一个目标地址，最后是一个源运算分量的列表。一个源运算分量的列表。指令之前可能有一个标号指令之前可能有一个标号2022-2-16编译技术编译技术262.1 一个简单的目标机模型一个简单的目标机模型可用的指令：可用的指令：加载运算：加载运

26、算：LD dst , addr 把位置把位置addr上的值加载到上的值加载到位置位置dst。这个指令表示赋值。这个指令表示赋值dst=addr。LD r,x，表示把位置，表示把位置x中的值加载到寄存器中的值加载到寄存器r中。中。LD r1,r2，是寄存器到寄存器的拷贝运算，将寄存器，是寄存器到寄存器的拷贝运算，将寄存器r2的内容拷贝到寄存器的内容拷贝到寄存器r1中。中。保存运算：保存运算：ST x,r 把寄存器把寄存器r中的值保存到位置中的值保存到位置x。这个指令表示赋值这个指令表示赋值 x=r。计算运算计算运算2022-2-16编译技术编译技术272.1 一个简单的目标机模型（一个简单的目标

27、机模型（cont.）可用的指令：可用的指令：计算运算：计算运算：OP dst,src1,src2。其中。其中OP是一个诸如是一个诸如ADD或或SUB的运算符，而的运算符，而dst、src1和和xrc2是内存位是内存位置。这些位置不一定要互不相同。这个计算的作用是置。这些位置不一定要互不相同。这个计算的作用是把把OP所代表的运算作用在位置所代表的运算作用在位置src1和和src2中的值上，中的值上，然后把这次运算的结果放到位置然后把这次运算的结果放到位置dst上。上。SUB r1,r2,r3：r1=r2-r3只需要一个运算分量的单目运算符没有只需要一个运算分量的单目运算符没有src2。2022-

28、2-16编译技术编译技术282.1 一个简单的目标机模型（一个简单的目标机模型（cont.）可用的指令：可用的指令：无条件跳转：无条件跳转：BR L使得控制流转向标号为使得控制流转向标号为L的机器的机器指令指令条件跳转：条件跳转：Bcond r, L其中其中r 是一个寄存器，是一个寄存器，L是一是一个标号，而个标号，而cond代表了对寄存器代表了对寄存器r中的值所做的某个中的值所做的某个常见测试。常见测试。BLTZ r,L：当寄存器：当寄存器r中的值小于中的值小于0时，这个使得控制时，这个使得控制流跳转到标号流跳转到标号L；否则执行下一个机器指令。；否则执行下一个机器指令。2022-2-16编

29、译技术编译技术292.1 一个简单的目标机模型（一个简单的目标机模型（cont.）寻址模式寻址模式在指令中，一个位置可以是一个变量名在指令中，一个位置可以是一个变量名x，它指向分配给，它指向分配给x的内的内存位置（存位置（x的左值）。的左值）。一个位置可以是一个带有下标的形如一个位置可以是一个带有下标的形如a(r)的地址。其中的地址。其中a是一个是一个变量，而变量，而r是一个寄存器。其代表的内存地址如下方式计算得是一个寄存器。其代表的内存地址如下方式计算得到：到：a的左值加上存放在寄存器的左值加上存放在寄存器r中的值。中的值。适用于数组访适用于数组访问。问。LD R1，a(R2)：R1=con

30、tents(a+contents(R2)一个内存位置可以是一个以寄存器作为下标的整数。一个内存位置可以是一个以寄存器作为下标的整数。用于用于沿指针取值。沿指针取值。LD R1，100(R2)： R1=contents(100+contents(R2)2022-2-16编译技术编译技术302.1 一个简单的目标机模型（一个简单的目标机模型（cont.）寻址模式寻址模式间接寻址模式：间接寻址模式：*r表示在寄存器表示在寄存器r的内容所表示的位置上存放的内存位的内容所表示的位置上存放的内存位置置 LD R1,*100(R2)：把：把R1设置为设置为contents(contents(100+cont

31、ents(R2)也就是首先计算寄存器也就是首先计算寄存器R2中的内容加上中的内容加上100的和，取出和值所指的位置中的内容，再的和，取出和值所指的位置中的内容，再把这个内容代表的位置中的值加载到把这个内容代表的位置中的值加载到R1中。中。直接常数寻址模式：在常数前面加一个前缀直接常数寻址模式：在常数前面加一个前缀#LD R1,#100：把整数：把整数100加载到加载到R1中中ADD R1，R1, #100则把则把100加到寄存器加到寄存器R1上去。上去。2022-2-16编译技术编译技术312.1 一个简单的目标机模型（一个简单的目标机模型（cont.）例子：例子：x = y zLDR1 ,

32、y/R1=yLDR2 , z/R2=zSUBR1,R1,R2/R1=R1-R2STx, R1/x=R11.1. 如果如果y y或者或者z z可能已被计算出可能已被计算出来并存放在寄存器中，可以来并存放在寄存器中，可以避免避免LDLD步骤步骤2.2. 如果如果x x的值被存放在寄存器的值被存放在寄存器中，并且以后不会被用到，中，并且以后不会被用到，就不需要把这个值保存回就不需要把这个值保存回x x了。了。2022-2-16编译技术编译技术322.1 一个简单的目标机模型（一个简单的目标机模型（cont.）例子：例子：b=ai其中其中a是一个元素为是一个元素为8个字节值（例如实个字节值（例如实数）

33、的数组，且下标从数）的数组，且下标从0开始。开始。LDR1 , i/R1=iMULR1 , R1 , 8/R1=R1*8LDR2 , a(R1)/R2=contents(a+content(R1)STb , R2/b=R22022-2-16编译技术编译技术332.1 一个简单的目标机模型（一个简单的目标机模型（cont.）例子：例子：aj = cLDR1 , c/R1=cLDR2 , j/R2=jMULR2 , R2 , 8/R2=R2*8STa(R2) , R1/contents(a+contents(R2)=R12022-2-16编译技术编译技术342.1 一个简单的目标机模型（一个简单的

34、目标机模型（cont.）例子：例子：x = *pLDR1 , p/R1=pLDR2 , 0(R1)/R2=contents(0+content(R1)STx , R2/x=R2*p = yLDR1 , p/R1=pLDR2 , y/R2=yST0(R1) , R2/contents(0+content(R1)=R22022-2-16编译技术编译技术352.1 一个简单的目标机模型（一个简单的目标机模型（cont.）例子：例子：if xy goto LLDR1 , x/R1=xLDR2 , y/R2=ySUBR1 , R1 , R2 /R1=R1-R2BLTZ R1 , M/ if R10 ju

35、mp to M这里这里M是从标号为是从标号为L的三地址指令所产生的机器指令的三地址指令所产生的机器指令序列中的第一个指令的标号序列中的第一个指令的标号2022-2-16编译技术编译技术362.2 程序和指令的代价程序和指令的代价根据我们在优化一个程序时感兴趣的方面根据我们在优化一个程序时感兴趣的方面,可以对编可以对编译及运行一个程序所需代价给出不同的量度：编译译及运行一个程序所需代价给出不同的量度：编译时间的长短、目标程序的大小。运行时间和能耗。时间的长短、目标程序的大小。运行时间和能耗。为一个给定的源程序找到一个最优的目标程序是一为一个给定的源程序找到一个最优的目标程序是一个不可判定的问题，

36、很多相关子问题都是个不可判定的问题，很多相关子问题都是NP困难的困难的2022-2-16编译技术编译技术372.2 程序和指令的代价（程序和指令的代价（cont.）假设每个目标语言指令都有相应的代价，简单起假设每个目标语言指令都有相应的代价，简单起见，我们把一个指令的代价设定为见，我们把一个指令的代价设定为1加上与运算分量加上与运算分量寻址模式相关的代价（对应于指令中字的长度）。寻址模式相关的代价（对应于指令中字的长度）。寄存器寻址模式具有的附加代价为寄存器寻址模式具有的附加代价为0涉及涉及的附加代价为的附加代价为1。LD R0,R1：寄存器拷贝，指令代价为：寄存器拷贝，指令代价为1LD R0

37、,M：内存位置：内存位置M的值加载到的值加载到R0中，指令代价中，指令代价为为2LD R1，*100(R2)：指令代价为：指令代价为22022-2-16编译技术编译技术388.3 目标代码中的地址目标代码中的地址如何使用静态和栈式内存分配为简单的过程调用和返回生成如何使用静态和栈式内存分配为简单的过程调用和返回生成代码，依次将代码，依次将IR中的名字转化为目标代码中的地址。中的名字转化为目标代码中的地址。一个静态确定的代码区一个静态确定的代码区Code。存放可执行代码，大小可以在编。存放可执行代码，大小可以在编译时确定。译时确定。一个静态确定的静态数据区一个静态确定的静态数据区Static。存

38、放全局变量和编译器生成。存放全局变量和编译器生成的其他数据。大小可以在编译时刻确定。的其他数据。大小可以在编译时刻确定。动态管理的栈区动态管理的栈区Stack。存放过程的活动记录。大小不能在编译。存放过程的活动记录。大小不能在编译时确定。时确定。动态管理的堆区动态管理的堆区Heap。存放程序运行时刻分配和释放的数据对。存放程序运行时刻分配和释放的数据对象，大小不能在编译时确定。象，大小不能在编译时确定。2022-2-16编译技术编译技术393.1静态分配静态分配过程调用和返回的代码生成，简化后只关注如下三过程调用和返回的代码生成，简化后只关注如下三地址语句：地址语句：call calleereturnhaltaction：代表其他三地址语句的占位符。：代表其他三地址语句的占位符。在过程调用和返回时，都需要对活动记录的相应位在过程调用和返回时，都需要对活动记录的相应位置进行操作。置进行操作。过程调用时将返回地址放入被调用者的活动记录过程调用时将返回地址放入被调用者的活动记录过程返回时要活动记录中返回地址指向的位置过程返回时要活动记录中返回地址指向的位置2022-2-16编译技术编译技术403.1静态分配（静态分配（cont.）假设活动记录的第一个位置存放返回地址。假设活动记录的第一个位置存放返回地址。中间代码中间代码 call callee的指令序列：的指令序列