1、第第11章章 代码生成代码生成School of Computer Science&Technology Harbin Institute of Technology重点：重点：代码生成器设计中的问题代码生成器设计中的问题,目标语言，一目标语言，一个简单的代码生成器个简单的代码生成器,寄存器的分配和指派寄存器的分配和指派难点：难点：寄存器的分配和指派寄存器的分配和指派2023-4-262第第11章章 代码生成代码生成 11.1 代码生成器设计中的问题代码生成器设计中的问题11.2 目标语言目标语言11.3 一个简单的代码生成器一个简单的代码生成器11.4 窥孔优化窥孔优化11.5 寄存器分配与
2、指派寄存器分配与指派11.6 本章小结本章小结2023-4-263第第11章章 代码生成代码生成n代码生成是编译的最后一个阶段，由代码生成代码生成是编译的最后一个阶段，由代码生成器完成。其任务是把中间代码转换为等价的、器完成。其任务是把中间代码转换为等价的、具有较高质量的目标代码，以充分利用目标机具有较高质量的目标代码，以充分利用目标机器的资源。当然，代码生成器本身也必须具有器的资源。当然，代码生成器本身也必须具有较高的运行效率。较高的运行效率。n目标代码可以是绝对地址的机器代码，或相对目标代码可以是绝对地址的机器代码，或相对地址的机器代码，也可以是汇编代码。地址的机器代码，也可以是汇编代码。
3、n本章用微型机的汇编指令来表示目标代码。本章用微型机的汇编指令来表示目标代码。2023-4-26411.1 代码生成器设计中的问题代码生成器设计中的问题 n虽然代码生成器的具体实现依赖于目标机器的虽然代码生成器的具体实现依赖于目标机器的体系结构、指令系统和操作系统，但存储管理、体系结构、指令系统和操作系统，但存储管理、指令选择、寄存器分配和计算顺序等问题却是指令选择、寄存器分配和计算顺序等问题却是设计各种代码生成器都要考虑的问题，本节讨设计各种代码生成器都要考虑的问题，本节讨论这类共性问题。论这类共性问题。2023-4-26511.1.1 代码生成器的输入代码生成器的输入n代码生成器的输入包括
4、中间代码和符号表信息，符号代码生成器的输入包括中间代码和符号表信息，符号表信息主要用来确定中间代码中的变量所代表的数据表信息主要用来确定中间代码中的变量所代表的数据对象的运行时地址。对象的运行时地址。n假设在代码生成前，编译器的前端已经将源程序扫描、假设在代码生成前，编译器的前端已经将源程序扫描、分析和翻译成为足够详细的中间代码，其中变量的值分析和翻译成为足够详细的中间代码，其中变量的值已经可以表示为目标机器能够直接操作的量已经可以表示为目标机器能够直接操作的量(位、整位、整数、实数、指针等数、实数、指针等)；n已经完成了必要的类型检查；已经完成了必要的类型检查；n在需要的地方已经插入了类型转
5、换符；明显的语义错在需要的地方已经插入了类型转换符；明显的语义错误误(如试图把浮点数作为数组下标如试图把浮点数作为数组下标)也都已经被检测出也都已经被检测出来了。来了。2023-4-26611.1.2 目标代码的形式目标代码的形式 n代码生成器的输出是目标代码。目标代码的形式主要代码生成器的输出是目标代码。目标代码的形式主要有如下有如下3种：种：n绝对机器语言代码绝对机器语言代码。所有地址均已定位，可以立即被执行。所有地址均已定位，可以立即被执行。适于小程序的编译，因为它们可以迅速地被执行。适于小程序的编译，因为它们可以迅速地被执行。n可重定位的机器语言代码可重定位的机器语言代码。允许分别将子
6、程序编译成一组。允许分别将子程序编译成一组可重定位模块，再由连接装配器将它们和某些运行程序连可重定位模块，再由连接装配器将它们和某些运行程序连接起来，转换成能执行的机器语言程序。好处是比较灵活，接起来，转换成能执行的机器语言程序。好处是比较灵活，并能利用已有的程序资源，代价是增加了连接和装配的开并能利用已有的程序资源，代价是增加了连接和装配的开销。销。n汇编语言代码汇编语言代码。生成汇编语言代码后还需要经过汇编程序。生成汇编语言代码后还需要经过汇编程序汇编成可执行的机器语言代码，但其好处是简化了代码生汇编成可执行的机器语言代码，但其好处是简化了代码生成过程并增加了可读性。成过程并增加了可读性。
7、2023-4-26711.1.3 指令选择指令选择n所谓所谓指令选择指令选择是指寻找一个合适的机器指令是指寻找一个合适的机器指令序列来实现给定的中间代码。序列来实现给定的中间代码。n目标机器指令系统的性质决定了指令选择的目标机器指令系统的性质决定了指令选择的难易程度难易程度n指令系统的一致性和完备性是两个重要的因素指令系统的一致性和完备性是两个重要的因素n特殊机器指令的使用和指令速度是另一些重要的特殊机器指令的使用和指令速度是另一些重要的因素因素2023-4-26811.1.3 指令选择指令选择n若不考虑目标程序的效率，指令的选择将非常若不考虑目标程序的效率，指令的选择将非常简单：简单：n如：
8、三地址语句如：三地址语句x:=y+z翻译成如下代码序列：翻译成如下代码序列：（x，y和和z都是静态分配）都是静态分配）nMOV y,R0/*把把y装入寄存器装入寄存器R0*/nADDz,R0/*z加到加到R0上上*/nMOV R0,x/*把把R0存入存入x中中*/n逐个语句地产生代码，常常得到低质量的代码逐个语句地产生代码，常常得到低质量的代码2023-4-26911.1.3 指令选择指令选择语句序列语句序列 a:=b+c d:=a+e的代码如下的代码如下MOV b,R0ADD c,R0MOVR0,a -若若a不再使用，第三条也多余不再使用，第三条也多余MOVa,R0 -多余的指令多余的指令A
9、DD e,R0MOVR0,d2023-4-261011.1.3 指令选择指令选择n如果目标机器有加如果目标机器有加l指令指令(INC)，则，则a:a+1的的最有效实现是：最有效实现是：INC a而不是而不是MOV a,R0ADD#1,R0MOV R0,a 2023-4-261111.1.4 寄存器分配寄存器分配n将运算对象放在寄存器中的指令通常要比将运将运算对象放在寄存器中的指令通常要比将运算对象放在内存中的指令快且短，因此，要想算对象放在内存中的指令快且短，因此，要想生成高质量的目标代码，必须充分使用目标机生成高质量的目标代码，必须充分使用目标机器的寄存器，寄存器的使用包括：器的寄存器，寄存
10、器的使用包括：n寄存器分配：为程序的某一点选择驻留在寄存器的寄存器分配：为程序的某一点选择驻留在寄存器的一组变量一组变量n寄存器指派：确定变量将要驻留的具体寄存器寄存器指派：确定变量将要驻留的具体寄存器2023-4-261211.1.4 寄存器分配寄存器分配n选择最优的寄存器指派方案是一个选择最优的寄存器指派方案是一个NP完全问题，完全问题，如果考虑到目标机器的硬件和如果考虑到目标机器的硬件和(或或)操作系统对寄操作系统对寄存器的使用约束，该问题还会进一步复杂。有存器的使用约束，该问题还会进一步复杂。有关寄存器分配和指派的策略将在关寄存器分配和指派的策略将在11.5节再进行节再进行详细讨论。详
11、细讨论。2023-4-261311.1.5 计算顺序选择计算顺序选择n计算执行的顺序同样会影响目标代码的效率。计算执行的顺序同样会影响目标代码的效率。后面将会看到，某些计算顺序比其它顺序需要后面将会看到，某些计算顺序比其它顺序需要较少的寄存器来保存中间结果，因而其目标代较少的寄存器来保存中间结果，因而其目标代码的效率也要高。码的效率也要高。n选择最佳计算顺序也是一个选择最佳计算顺序也是一个NP完全问题。为简完全问题。为简单起见，只讨论如何按给定的三地址码的顺序单起见，只讨论如何按给定的三地址码的顺序生成目标代码。生成目标代码。2023-4-261411.2 目标语言目标语言 11.2.1 目标
12、机模型目标机模型选择可作为几种微机代表的寄存器机器选择可作为几种微机代表的寄存器机器n字节寻址，四字节组成一个字，具有字节寻址，四字节组成一个字，具有n个通用个通用寄存器寄存器R0,R1,Rn-1。n二地址指令：二地址指令：op源，目的源，目的MOV 将源移到目的中将源移到目的中ADD 将源加到目的中将源加到目的中SUB 在目的中减去源在目的中减去源 2023-4-261511.2 目标语言目标语言 寻址模式和它们的汇编语言形式及相关开销寻址模式和它们的汇编语言形式及相关开销寻址模式寻址模式 汇编形式汇编形式 地址地址 增加的开销增加的开销绝对地址绝对地址 M M 1寄存器寄存器 R R 0下
13、标下标 c(R)c+contents(R)1间址寄存器间址寄存器*Rcontents(R)0间址下标间址下标 *c(R)contents(c+contents(R)1 直接量直接量#c c 1 2023-4-261611.2 目标语言目标语言 指令实例指令实例MOVR0,MMOV4(R0),Mcontents(4+contents(R0)MOV*4(R0),Mcontents(contents(4+contents(R0)MOV#1,R02023-4-261711.2 目标语言目标语言 11.2.2 程序和指令的开销程序和指令的开销指令开销指令开销:=1+源和目的寻址模式的附加开销源和目的寻址
14、模式的附加开销指令指令开销开销MOV R0，R1 1MOV R5，M 2ADD#1，R3 2SUB 4(R0),*12(R1)32023-4-2618程序和指令的开销程序和指令的开销a:=b+c，a、b和和c都静态分配内存单元都静态分配内存单元MOV b,R0ADD c,R0开销开销=6MOV R0,a2023-4-2619程序和指令的开销程序和指令的开销a:=b+c，a、b和和c都静态分配内存单元都静态分配内存单元MOV b,R0ADD c,R0开销开销=6MOV R0,aMOV b,aADD c,a开销开销=6 2023-4-2620程序和指令的开销程序和指令的开销a:=b+c，a、b和和
15、c都静态分配内存单元都静态分配内存单元若若R0，R1和和R2分别含分别含a，b和和c的地址，则的地址，则MOV*R1,*R0ADD*R2,*R0开销开销=22023-4-2621程序和指令的开销程序和指令的开销 a:=b+c，a、b和和c都静态分配内存单元都静态分配内存单元若若R0，R1和和R2分别含分别含a，b和和c的地址，则的地址，则MOV*R1,*R0ADD*R2,*R0开销开销=2若若R1和和R2分别含分别含b和和c的值，并且的值，并且b的值在这个的值在这个赋值后不再需要，则赋值后不再需要，则ADD R2,R1MOV R1,a开销开销=3 2023-4-262211.2.3 变量的运行
16、时刻地址变量的运行时刻地址 n存储分配策略以及过程的活动记录中局部数存储分配策略以及过程的活动记录中局部数据的布局决定了如何访问变量所对应的内存据的布局决定了如何访问变量所对应的内存位置位置n前面假设三地址码中的变量实际上是一个指前面假设三地址码中的变量实际上是一个指向符号表表项的指针，在代码生成阶段，变向符号表表项的指针，在代码生成阶段，变量必须被替换为运行时的内存地址量必须被替换为运行时的内存地址n例例11.1 考虑三地址码考虑三地址码x:=0，假设处理完过程，假设处理完过程的声明部分之后，的声明部分之后，x在符号表中的相对地址为在符号表中的相对地址为122023-4-262311.2.3
17、 变量的运行时刻地址变量的运行时刻地址 n如果如果x被分配在一个地址从被分配在一个地址从static开始的静态内开始的静态内存区域中，则存区域中，则x的运行时刻地址为的运行时刻地址为static+12。如果静态区从地址如果静态区从地址100开始，开始，x:=0的目标代码的目标代码为：为：MOV#0,112。n如果采用栈式存储分配策略，则只有等到运如果采用栈式存储分配策略，则只有等到运行时刻才能知道一个过程的活动记录位置。行时刻才能知道一个过程的活动记录位置。此时，此时，x:=0的目标代码为：的目标代码为：MOV#0,12(SP)。2023-4-262411.3 一个简单的代码生成器一个简单的代
18、码生成器n依次考虑基本块的每个语句，为其产生代码依次考虑基本块的每个语句，为其产生代码n假定三地址语句的每种算符都有对应的目标假定三地址语句的每种算符都有对应的目标机器算符机器算符n假定计算结果留在寄存器中尽可能长的时间假定计算结果留在寄存器中尽可能长的时间,除非：除非：n该寄存器要用于其它计算，或者该寄存器要用于其它计算，或者n到达基本块末尾到达基本块末尾n后续的目标代码也要尽可能地引用保存在寄后续的目标代码也要尽可能地引用保存在寄存器中的变量值存器中的变量值 2023-4-262511.3.1 后续引用信息后续引用信息 n为了在代码生成过程中能充分合理地使用寄为了在代码生成过程中能充分合理
19、地使用寄存器，应把基本块中还会再被引用的变量的存器，应把基本块中还会再被引用的变量的值尽量保留在寄存器中，而把基本块内不会值尽量保留在寄存器中，而把基本块内不会再被引用的变量所占用的寄存器及早释放。再被引用的变量所占用的寄存器及早释放。为此，对于每个形如为此，对于每个形如a:=b op c的三地址码，的三地址码，需要知道变量需要知道变量a、b和和c在基本块内是否还会再在基本块内是否还会再被引用以及会在哪里被引用，这些信息称为被引用以及会在哪里被引用，这些信息称为后续引用信息后续引用信息。2023-4-262611.3.1 后续引用信息后续引用信息 n如果在一个基本块中，语句如果在一个基本块中，
20、语句i定义了定义了x，语句，语句j要引用要引用x的值，且从的值，且从i到到j之间没有之间没有x的其它定义，的其它定义，则称则称i中中x的定义能够的定义能够到达到达j。从。从j所能到达的每所能到达的每一个一个x的引用点都称为的引用点都称为i点定义的变量点定义的变量x的的后续后续引用信息引用信息，所有这样的，所有这样的j所组成的引用链则称所组成的引用链则称为变量为变量x的的后续引用信息链后续引用信息链。2023-4-2627后续引用信息的计算后续引用信息的计算 初始时，将基本块中各变量的符号表表项的后续引用信息域初始时，将基本块中各变量的符号表表项的后续引用信息域置为置为“无后续引用无后续引用”，
21、并根据该变量在基本块的出口是否活，并根据该变量在基本块的出口是否活跃，将其活跃信息域置为跃，将其活跃信息域置为“活跃活跃”或或“不活跃不活跃”；从基本块出口向入口反向扫描，并对每个形如从基本块出口向入口反向扫描，并对每个形如i:a:=b op c的的三地址码依次执行如下操作：三地址码依次执行如下操作：将符号表中将符号表中a的后续引用信息和活跃信息附加到的后续引用信息和活跃信息附加到i上上 将符号表中将符号表中a的后续引用信息和活跃信息分别置为的后续引用信息和活跃信息分别置为“无后无后续引用续引用”和和“不活跃不活跃”将符号表中将符号表中b和和c的后续引用信息和活跃信息附加到的后续引用信息和活跃
22、信息附加到i上上 将符号表中变量将符号表中变量b和和c的后续引用信息均置为的后续引用信息均置为i，活跃信息，活跃信息均置为均置为“活跃活跃”注意，上述次序不能颠倒，因为注意，上述次序不能颠倒，因为b和和c也可能就是也可能就是a。此外，因。此外，因为过程调用可能带来副作用，所以在划分基本块时将过程调为过程调用可能带来副作用，所以在划分基本块时将过程调用也作为基本块的入口。用也作为基本块的入口。2023-4-262811.3 一个简单的代码生成器一个简单的代码生成器在没有收集全局信息在没有收集全局信息前，暂且以基本块为前，暂且以基本块为单位来生成代码单位来生成代码prod:=0i:=1t1:=4*
23、it2:=at1t3:=4*It4:=bt3t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7if i、或或=而将条件码分别置为正、负或零。而将条件码分别置为正、负或零。如果如果a和和/或或b的当前值在寄存器中，则在生成的当前值在寄存器中，则在生成目标代码时应尽量使用寄存器寻址模式。目标代码时应尽量使用寄存器寻址模式。2023-4-264311.4 窥孔优化窥孔优化n窥孔优化是一种简单有效的局部优化方法，窥孔优化是一种简单有效的局部优化方法，它通过检查目标指令中称为窥孔的短序列，它通过检查目标指令中称为窥孔的短序列，用更小更短的指令序列进行等价代替，以此用更小更短
24、的指令序列进行等价代替，以此来提高目标代码的质量。来提高目标代码的质量。n窥孔是放在目标程序上的一个移动的小窗口。窥孔是放在目标程序上的一个移动的小窗口。孔中的代码不需要是连续的。孔中的代码不需要是连续的。n该技术的特点是每次优化后的结果可能又为该技术的特点是每次优化后的结果可能又为进一步的优化带来了机会。所以有时会对目进一步的优化带来了机会。所以有时会对目标代码重复进行多遍优化。下面介绍几种典标代码重复进行多遍优化。下面介绍几种典型的窥孔优化技术。型的窥孔优化技术。2023-4-264411.4 窥孔优化窥孔优化n11.4.1 冗余指令消除冗余指令消除n如果遇到如下的指令序列：如果遇到如下的
25、指令序列：MOV R0,a MOV a,R0 (11.1)则可以删除指令。但是，如果带有标号，则可以删除指令。但是，如果带有标号，通常是不能删除的。通常是不能删除的。2023-4-264511.4 窥孔优化窥孔优化n11.4.2 不可达代码消除不可达代码消除n删除紧跟在无条件跳转指令后的无标号指令删除紧跟在无条件跳转指令后的无标号指令称为不可达代码删除。称为不可达代码删除。2023-4-264611.4 窥孔优化窥孔优化n11.4.3 强度削弱强度削弱n强度削弱是指在目标机器上用时间开销小的强度削弱是指在目标机器上用时间开销小的等价操作代替时间开销大的操作。例如用等价操作代替时间开销大的操作。
26、例如用x*x实现实现x2要比调用一个指数过程快很多。用移要比调用一个指数过程快很多。用移位操作实现乘以位操作实现乘以2或除以或除以2的定点运算要更快的定点运算要更快一些。用乘法实现一些。用乘法实现(近似近似)浮点除法也可能会更浮点除法也可能会更快一些。快一些。2023-4-264711.4 窥孔优化窥孔优化n11.4.4 特殊机器指令的使用特殊机器指令的使用n为了提高效率，目标机器有时会使用一些硬为了提高效率，目标机器有时会使用一些硬件指令来实现某些特定的操作。例如，有一件指令来实现某些特定的操作。例如，有一些机器具有自动加些机器具有自动加1和自动减和自动减1的寻址模式。的寻址模式。这些模式的
27、运用可以大大提高参数传递过程这些模式的运用可以大大提高参数传递过程中压栈和出栈的代码质量，它们还可以用在中压栈和出栈的代码质量，它们还可以用在形如形如i:=i+1的语句的代码中。的语句的代码中。2023-4-264811.4 窥孔优化窥孔优化n11.4.5 其他处理其他处理n也可以利用其他一些途经进行窥孔优化。例也可以利用其他一些途经进行窥孔优化。例如，通过删除那些不必要的连续转移；利用如，通过删除那些不必要的连续转移；利用代数恒等性质删除形如代数恒等性质删除形如x:=x+0或或x:=x*1的的代码的代数化简。代码的代数化简。2023-4-264911.5 寄存器分配与指派寄存器分配与指派n由
28、于只涉及寄存器运算对象的指令要比那些由于只涉及寄存器运算对象的指令要比那些涉及内存运算对象的指令短且快，因此有效涉及内存运算对象的指令短且快，因此有效地利用寄存器非常重要。地利用寄存器非常重要。n寄存器分配的任务是为程序的某一点选择应寄存器分配的任务是为程序的某一点选择应该驻留在寄存器中的一组变量该驻留在寄存器中的一组变量n寄存器指派则负责挑出变量将要驻留的具体寄存器指派则负责挑出变量将要驻留的具体寄存器。寄存器。2023-4-265011.5.1 全局寄存器分配全局寄存器分配n由于程序的大多数时间都花在内层循环上，因此一由于程序的大多数时间都花在内层循环上，因此一种比较自然的全局寄存器分配方
29、法是在整个循环中种比较自然的全局寄存器分配方法是在整个循环中将经常引用的值保存在固定的寄存器中。将经常引用的值保存在固定的寄存器中。n假设已经利用第假设已经利用第10章的技术找出了流图中的循环结章的技术找出了流图中的循环结构，而且知道基本块中计算出的哪些值要在该块外构，而且知道基本块中计算出的哪些值要在该块外被引用，则有一种简单的全局寄存器分配策略，那被引用，则有一种简单的全局寄存器分配策略，那就是分配固定数目的寄存器来保存每个内部循环中就是分配固定数目的寄存器来保存每个内部循环中最活跃的值。最活跃的值。n不同循环选中的值也会有所不同。不同循环选中的值也会有所不同。n未被分配的寄存器可用于存放
30、未被分配的寄存器可用于存放11.4节讨论的基本块节讨论的基本块的局部值。的局部值。n该方法的缺点是：固定的寄存器数目对全局寄存器该方法的缺点是：固定的寄存器数目对全局寄存器分配来说可能不够用，但实现简单。分配来说可能不够用，但实现简单。2023-4-265111.5.2 引用计数引用计数n如果如果x在寄存器中，则对在寄存器中，则对x的每次引用都将节省一个单的每次引用都将节省一个单元的开销。于是可以采用一种简单的方法来确定执行元的开销。于是可以采用一种简单的方法来确定执行循环循环L时将变量时将变量x保存在寄存器中所节省的开销。保存在寄存器中所节省的开销。n计算循环计算循环L中为中为x分配寄存器所
31、节省开销的近似公式：分配寄存器所节省开销的近似公式：(11.5)n其中，其中，use(x,B)是定义是定义x之前，块之前，块B中对中对x的引用次数。的引用次数。如果如果x在在B的出口处是活跃的，而且的出口处是活跃的，而且B中含有对中含有对x的赋值，的赋值，则则live(x,B)为为1，否则，否则live(x,B)为为0。注意，。注意，(11.5)是个是个近似公式。这是因为循环中的块的迭代次数可能是不近似公式。这是因为循环中的块的迭代次数可能是不一样的，而且我们还假设循环会迭代许多次。一样的，而且我们还假设循环会迭代许多次。BLBxliveBxuse中的块),(*2),(2023-4-26521
32、1.5.2 引用计数引用计数n例例11.3 考虑图考虑图11.2中内层循环中的基本块，块中内层循环中的基本块，块中的跳转语句均已删除。假设用寄存器中的跳转语句均已删除。假设用寄存器R0、R1和和R2来保存循环中的值。为方便起见，图来保存循环中的值。为方便起见，图中还列出了在每个块入口和出口活跃的变量。中还列出了在每个块入口和出口活跃的变量。e和和f在在B1的末尾都是活跃的，但只有的末尾都是活跃的，但只有e在在B2的的入口是活跃的，只有入口是活跃的，只有f在在B3的入口是活跃的。的入口是活跃的。一般地，块末尾活跃的变量是其后继块入口一般地，块末尾活跃的变量是其后继块入口活跃变量的并集。活跃变量的
33、并集。2023-4-2653例例11.32023-4-2654例例11.3 n首先计算首先计算x=a时时(11.5)的值，由于的值，由于a在在B1的出口是活跃的出口是活跃的，的，B1中还含有对中还含有对a的赋值，而且的赋值，而且a在在B2、B3和和B4的的出口不活跃，因此出口不活跃，因此 因为因为a是在任何引用之前于是在任何引用之前于B1中定义的，所以中定义的，所以use(a,B1)=0。同理，。同理，use(a,B2)=use(a,B3)=1，而且，而且，use(a,B4)=0，于是，于是，综上，综上，x=a时时(11.5)式的值为式的值为4。亦即，将。亦即，将a存入某个存入某个全局寄存器可
34、以节省全局寄存器可以节省4个单元的开销。由于个单元的开销。由于x=b、c、d、e和和f时时(11.5)式的值分别为式的值分别为6、3、6、4和和4，因此，因此可以将可以将a、b和和d放入寄存器放入寄存器R0、R1和和R2。使用。使用R0存存放放e或或f而不是而不是a可以节省相同的开销。可以节省相同的开销。BLBlive中的2)(a,*2BLBuse中的2)(a,2023-4-2655例例11.3图图11.3 使用全局寄存器分配的代码序列使用全局寄存器分配的代码序列2023-4-265611.5.3 外层循环的寄存器指派外层循环的寄存器指派 n为内层循环分配了寄存器并生成代码之后，为内层循环分配
35、了寄存器并生成代码之后，可以将同样的方法应用到外层循环上。可以将同样的方法应用到外层循环上。n如果外层循环如果外层循环L1包含内层循环包含内层循环L2，则在，则在L2中分中分配了寄存器的变量不必再在配了寄存器的变量不必再在L2-L1中分配寄存中分配寄存器。器。n如果变量如果变量x是在循环是在循环L1中而不是在中而不是在L2中分配了中分配了寄存器，则必须在寄存器，则必须在L2的入口处保存的入口处保存x并在离开并在离开L2进入块进入块L1-L2之前装载之前装载x。2023-4-265711.5.3 外层循环的寄存器指派外层循环的寄存器指派 n如果在如果在L2而不是而不是L1中为中为x分配了寄存器，
36、则必分配了寄存器，则必须在须在L2的入口装载的入口装载x，并在，并在L2的出口保存的出口保存x。n如果计算时需要寄存器但所有可用的寄存器如果计算时需要寄存器但所有可用的寄存器均被占用，则必须将某个正被使用的寄存器均被占用，则必须将某个正被使用的寄存器中的内容存放中的内容存放(溢出溢出)到内存中以释放一个寄存到内存中以释放一个寄存器。器。n图染色法是一种简单的用于寄存器分配和寄图染色法是一种简单的用于寄存器分配和寄存器溢出管理的系统技术。存器溢出管理的系统技术。2023-4-2658本章小结本章小结1.目标代码的生成需要尽力开发利用机器提供的资源，目标代码的生成需要尽力开发利用机器提供的资源，特
37、别是根据开销选用恰当的指令和寄存器，以提高其特别是根据开销选用恰当的指令和寄存器，以提高其执行效率；执行效率；2.稀缺资源寄存器的有效利用涉及到后续引用问题，寄稀缺资源寄存器的有效利用涉及到后续引用问题，寄存器描述符用来记录每个寄存器当前的内容；地址描存器描述符用来记录每个寄存器当前的内容；地址描述符记录运行时存放变量当前值的一个或多个位置，述符记录运行时存放变量当前值的一个或多个位置，用来确定对变量的存取方式；用来确定对变量的存取方式；3.使用引用计数能够良好地实现寄存器的分配和指派；使用引用计数能够良好地实现寄存器的分配和指派；4.不同形式的三地址码对应不同的目标代码，且具有不不同形式的三
38、地址码对应不同的目标代码，且具有不同的执行代价；同的执行代价；5.不可达和冗余指令删除、控制流优化、强度削弱、代不可达和冗余指令删除、控制流优化、强度削弱、代数化简、特殊指令使用等都是有效的窥孔优化方法；数化简、特殊指令使用等都是有效的窥孔优化方法；考试要求考试要求n题型题型n选择、填空、判断、简答、证明、论述、设计、计算等选择、填空、判断、简答、证明、论述、设计、计算等n重点和难点重点和难点n已在课件各章的开始点明已在课件各章的开始点明n考试权重考试权重n平时成绩占平时成绩占20%n实验占实验占10%n期末考试占期末考试占70%n考前答疑考前答疑n考试前两天考试前两天5月月13号号-14号，地点：综合楼号，地点：综合楼808
