代码生成哈工大王宏志.ppt

第9章 代码生成,School of Software Harbin Institute of Technology,重点：代码生成器设计中的问题,目标语言，一个简单的代码生成器,寄存器的分配和指派难点：寄存器的分配和指派,2023/10/9,2,第9章代码生成,9.1 代码生成器设计中的问题9.2 目标语言9.3 一个简单的代码生成器9.4 窥孔优化9.5 寄存器分配与指派9.6 本章小结,2023/10/9,3,第9章代码生成,代码生成是编译的最后一个阶段，由代码生成器完成。其任务是把中间代码转换为等价的、具有较高质量的目标代码，以充分利用目标机器的资源。当然，代码生成器本身也必须具有较高的运行效率。目标代码可以是绝对地址的机器代码，或相对地址的机器代码，也可以是汇编代码。本章用微型机的汇编指令来表示目标代码。,2023/10/9,4,9.1 代码生成器设计中的问题,虽然代码生成器的具体实现依赖于目标机器的体系结构、指令系统和操作系统，但存储管理、指令选择、寄存器分配和计算顺序等问题却是设计各种代码生成器都要考虑的问题，本节讨论这类共性问题。,2023/10/9,5,9.1.1 代码生成器的输入,代码生成器的输入包括中间代码和符号表信息，符号表信息主要用来确定中间代码中的变量所代表的数据对象的运行时地址。假设在代码生成前，编译器的前端已经将源程序扫描、分析和翻译成为足够详细的中间代码，其中变量的值已经可以表示为目标机器能够直接操作的量(位、整数、实数、指针等)；已经完成了必要的类型检查；在需要的地方已经插入了类型转换符；明显的语义错误(如试图把浮点数作为数组下标)也都已经被检测出来了。,2023/10/9,6,9.1.2 目标代码的形式,代码生成器的输出是目标代码。目标代码的形式主要有如下3种：绝对机器语言代码。所有地址均已定位，可以立即被执行。适于小程序的编译，因为它们可以迅速地被执行。可重定位的机器语言代码。允许分别将子程序编译成一组可重定位模块，再由连接装配器将它们和某些运行程序连接起来，转换成能执行的机器语言程序。好处是比较灵活，并能利用已有的程序资源，代价是增加了连接和装配的开销。汇编语言代码。生成汇编语言代码后还需要经过汇编程序汇编成可执行的机器语言代码，但其好处是简化了代码生成过程并增加了可读性。,2023/10/9,7,9.1.3 指令选择,所谓指令选择是指寻找一个合适的机器指令序列来实现给定的中间代码。目标机器指令系统的性质决定了指令选择的难易程度指令系统的一致性和完备性是两个重要的因素特殊机器指令的使用和指令速度是另一些重要的因素,2023/10/9,8,9.1.3 指令选择,若不考虑目标程序的效率，指令的选择将非常简单：如：三地址语句x:=y+z翻译成如下代码序列：（x，y和z都是静态分配）MOVy,R0/*把y装入寄存器R0*/ADDz,R0/*z加到R0上*/MOVR0,x/*把R0存入x中*/逐个语句地产生代码，常常得到低质量的代码,2023/10/9,9,9.1.3 指令选择,语句序列 a:=b+c d:=a+e的代码如下MOV b,R0ADD c,R0MOVR0,a-若a不再使用，第三条也多余MOVa,R0-多余的指令ADD e,R0MOVR0,d,2023/10/9,10,9.1.3 指令选择,如果目标机器有加l指令(INC)，则a:a+1的最有效实现是：INC a而不是MOV a,R0ADD#1,R0MOV R0,a,2023/10/9,11,9.1.4 寄存器分配,将运算对象放在寄存器中的指令通常要比将运算对象放在内存中的指令快且短，因此，要想生成高质量的目标代码，必须充分使用目标机器的寄存器，寄存器的使用包括：寄存器分配：为程序的某一点选择驻留在寄存器的一组变量寄存器指派：确定变量将要驻留的具体寄存器,2023/10/9,12,9.1.4 寄存器分配,选择最优的寄存器指派方案是一个NP完全问题，如果考虑到目标机器的硬件和(或)操作系统对寄存器的使用约束，该问题还会进一步复杂。有关寄存器分配和指派的策略将在9.5节再进行详细讨论。,2023/10/9,13,9.1.5 计算顺序选择,计算执行的顺序同样会影响目标代码的效率。后面将会看到，某些计算顺序比其它顺序需要较少的寄存器来保存中间结果，因而其目标代码的效率也要高。选择最佳计算顺序也是一个NP完全问题。为简单起见，只讨论如何按给定的三地址码的顺序生成目标代码。,2023/10/9,14,9.2 目标语言,9.2.1 目标机模型选择可作为几种微机代表的寄存器机器字节寻址，四字节组成一个字，具有n个通用寄存器R0,R1,Rn-1。二地址指令：op源，目的MOV 将源移到目的中ADD 将源加到目的中SUB 在目的中减去源,2023/10/9,15,9.2 目标语言,寻址模式和它们的汇编语言形式及相关开销寻址模式 汇编形式 地址 增加的开销绝对地址 M M 1寄存器 R R 0下标 c(R)c+contents(R)1间址寄存器*Rcontents(R)0间址下标*c(R)contents(c+contents(R)1 直接量#c c 1,2023/10/9,16,9.2 目标语言,指令实例MOVR0,MMOV4(R0),Mcontents(4+contents(R0)MOV*4(R0),Mcontents(contents(4+contents(R0)MOV#1,R0,2023/10/9,17,9.2 目标语言,9.2.2 程序和指令的开销指令开销:=1+源和目的寻址模式的附加开销指令开销MOV R0，R1 1MOV R5，M 2ADD#1，R3 2SUB 4(R0),*12(R1)3,2023/10/9,18,程序和指令的开销,a:=b+c，a、b和c都静态分配内存单元MOV b,R0ADD c,R0开销=6MOV R0,a,2023/10/9,19,程序和指令的开销,a:=b+c，a、b和c都静态分配内存单元MOV b,R0ADD c,R0开销=6MOV R0,aMOV b,aADD c,a开销=6,2023/10/9,20,程序和指令的开销,a:=b+c，a、b和c都静态分配内存单元若R0，R1和R2分别含a，b和c的地址，则MOV*R1,*R0ADD*R2,*R0开销=2,2023/10/9,21,程序和指令的开销,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/10/9,22,9.2.3 变量的运行时刻地址,存储分配策略以及过程的活动记录中局部数据的布局决定了如何访问变量所对应的内存位置前面假设三地址码中的变量实际上是一个指向符号表表项的指针，在代码生成阶段，变量必须被替换为运行时的内存地址例9.1 考虑三地址码x:=0，假设处理完过程的声明部分之后，x在符号表中的相对地址为12,2023/10/9,23,9.2.3 变量的运行时刻地址,如果x被分配在一个地址从static开始的静态内存区域中，则x的运行时刻地址为static+12。如果静态区从地址100开始，x:=0的目标代码为：MOV#0,112。如果采用栈式存储分配策略，则只有等到运行时刻才能知道一个过程的活动记录位置。此时，x:=0的目标代码为：MOV#0,12(SP)。,2023/10/9,24,9.3 一个简单的代码生成器,依次考虑基本块的每个语句，为其产生代码假定三地址语句的每种算符都有对应的目标机器算符假定计算结果留在寄存器中尽可能长的时间,除非：该寄存器要用于其它计算，或者到达基本块末尾后续的目标代码也要尽可能地引用保存在寄存器中的变量值,2023/10/9,25,9.3.1 后续引用信息,为了在代码生成过程中能充分合理地使用寄存器，应把基本块中还会再被引用的变量的值尽量保留在寄存器中，而把基本块内不会再被引用的变量所占用的寄存器及早释放。为此，对于每个形如a:=b op c的三地址码，需要知道变量a、b和c在基本块内是否还会再被引用以及会在哪里被引用，这些信息称为后续引用信息。,2023/10/9,26,9.3.1 后续引用信息,如果在一个基本块中，语句i定义了x，语句j要引用x的值，且从i到j之间没有x的其它定义，则称i中x的定义能够到达j。从j所能到达的每一个x的引用点都称为i点定义的变量x的后续引用信息，所有这样的j所组成的引用链则称为变量x的后续引用信息链。,2023/10/9,27,后续引用信息的计算,初始时，将基本块中各变量的符号表表项的后续引用信息域置为“无后续引用”，并根据该变量在基本块的出口是否活跃，将其活跃信息域置为“活跃”或“不活跃”；从基本块出口向入口反向扫描，并对每个形如i:a:=b op c的三地址码依次执行如下操作：将符号表中a的后续引用信息和活跃信息附加到i上 将符号表中a的后续引用信息和活跃信息分别置为“无后续引用”和“不活跃”将符号表中b和c的后续引用信息和活跃信息附加到i上 将符号表中变量b和c的后续引用信息均置为i，活跃信息均置为“活跃”注意，上述次序不能颠倒，因为b和c也可能就是a。此外，因为过程调用可能带来副作用，所以在划分基本块时将过程调用也作为基本块的入口。,2023/10/9,28,9.3 一个简单的代码生成器,在没有收集全局信息前，暂且以基本块为单位来生成代码,2023/10/9,29,9.3.2 寄存器描述符与地址描述符,例：对a:=b+c如果寄存器Ri含b，Rj含c，且b此后不再活跃产生ADD Rj,Ri，结果a在Ri中如果Ri含b，但c在内存单元，b仍然不再活跃产生ADD c,Ri，或者MOV c,RjADD Rj,Ri若c的值以后还要用,第二种代码比较有吸引力,2023/10/9,30,9.3.2 寄存器描述符与地址描述符,在代码生成过程中，需要跟踪寄存器的内容和名字的地址寄存器描述符记录每个寄存器当前存的是什么在任何一点，每个寄存器保存若干个(包括零个)名字的值名字的地址描述符记录运行时每个名字的当前值存放的一个或多个位置该位置可能是寄存器、栈单元、内存地址或者是它们的某个集合这些信息可以存放在符号表中这两个描述符在代码生成过程中是变化的。,2023/10/9,31,9.3.3 代码生成算法,对每个三地址语句i:x:=y op z调用函数getreg(i:x:=y op z)确定可用于保存y op z的计算结果的位置L查看y的地址描述符以确定y值当前的一个位置y。如果y值当前既在内存单元中又在寄存器中，则选择寄存器作为y。如果y的值还不在L中，则生成指令MOV y，L 生成指令op z，L，其中z是z的当前位置之一如果y和/或z的当前值没有后续引用，在块的出口也不活跃，并且还在寄存器中，则修改寄存器描述符以表示在执行了x:=y op z 之后，这些寄存器分别不再包含y和(或)z的值。,2023/10/9,32,9.3.3 代码生成算法,寄存器选择函数getreg函数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。,2023/10/9,33,9.3.3 代码生成算法,赋值语句d:=(a b)+(a c)+(a c)编译产生的三地址码序列为：t1:=a bt2:=a ct3:=t1+t2d:=t3+t2 d在基本块的出口是活跃的。,2023/10/9,34,9.3.3 代码生成算法,2023/10/9,35,9.3.3 代码生成算法,前三条指令可以修改，使执行代价降低MOV a,R0MOV a,R0SUB b,R0 MOV R0，R1 MOV a,R1SUB b,R0SUB c,R1 SUB c,R1.,2023/10/9,36,9.3.4 常用三地址码的代码生成,复制：a:=b如果b的当前值在寄存器R中，则不必生成代码，只要将a添加到R的寄存器描述符中，并把a的地址描述符置为R即可。如果b在基本块中不会再被引用且在基本块的出口也不活跃，则还要从R的寄存器描述符中删除b，并从b的地址描述符中删除R。但若b的当前值只在内存单元中，如果只是简单地将a的地址描述符置为b的内存地址，那么，若不对a的值采取保护措施，a的值将会为b的再次定义所影响。此时，生成一条形如MOV b,R的指令会较为稳妥。,2023/10/9,37,9.3.4 常用三地址码的代码生成,一元运算：a:=op b 与二元运算的处理类似。数组元素引用：a:=bi。假设a在基本块中还会再被引用，而且寄存器R是可用的，则将a保留在寄存器R中。于是，如果i的当前值不在寄存器中，则生成如下指令序列：MOV i,RMOV b(R),R 开销=4如果i的当前值在寄存器Ri中，则生成如下指令：MOV b(Ri),R 开销=2,2023/10/9,38,9.3.4 常用三地址码的代码生成,数组元素赋值：ai:=b假设a是静态分配的。如果i的当前值不在寄存器中，则生成如下指令序列：MOV i,RMOV b,a(R)开销=5如果i的当前值在寄存器Ri中，则生成如下指令：MOV b,a(Ri)开销=3,2023/10/9,39,9.3.4 常用三地址码的代码生成,指针引用：a:=*p同样假设a在基本块中还会再被引用，而且寄存器R是可用的，则将a保留在寄存器R中。于是，如果p的当前值不在寄存器中，则生成如下指令：MOV p,RMOV*R,R 开销=3如果p的当前值在寄存器Ri中，则可生成如下指令：MOV*Ri,a 开销=2,2023/10/9,40,9.3.4 常用三地址码的代码生成,指针赋值：*p:=a假设a是静态分配的。如果p的当前值不在寄存器中，则生成如下指令：MOV p,RMOV a,*R 开销=4如果p的当前值在寄存器Ri中，则可生成如下指令：MOV a,*R 开销=2,2023/10/9,41,9.3.4 常用三地址码的代码生成,无条件转移：goto L假设L为三地址语句的序号，则生成指令JMP L。其中，L为序号为L的三地址语句的目标代码首址。,2023/10/9,42,9.3.4 常用三地址码的代码生成,条件转移：if a rop b goto L 同样假设L为三地址语句的序号，则生成如下的指令序列：CMP a,bCJrop L其中，L的含义与中相同，CMP为比较指令，Cjrop为条件码跳转指令，CMP根据rop取、或=而将条件码分别置为正、负或零。如果a和/或b的当前值在寄存器中，则在生成目标代码时应尽量使用寄存器寻址模式。,2023/10/9,43,9.4 窥孔优化,窥孔优化是一种简单有效的局部优化方法，它通过检查目标指令中称为窥孔的短序列，用更小更短的指令序列进行等价代替，以此来提高目标代码的质量。窥孔是放在目标程序上的一个移动的小窗口。孔中的代码不需要是连续的。该技术的特点是每次优化后的结果可能又为进一步的优化带来了机会。所以有时会对目标代码重复进行多遍优化。下面介绍几种典型的窥孔优化技术。,2023/10/9,44,9.4 窥孔优化,9.4.1 冗余指令消除如果遇到如下的指令序列：MOV R0,a MOV a,R0(9.1)则可以删除指令。但是，如果带有标号，通常是不能删除的。,2023/10/9,45,9.4 窥孔优化,9.4.2 不可达代码消除删除紧跟在无条件跳转指令后的无标号指令称为不可达代码删除。,2023/10/9,46,9.4 窥孔优化,9.4.3 强度削弱强度削弱是指在目标机器上用时间开销小的等价操作代替时间开销大的操作。例如用x*x实现x2要比调用一个指数过程快很多。用移位操作实现乘以2或除以2的定点运算要更快一些。用乘法实现(近似)浮点除法也可能会更快一些。,2023/10/9,47,9.4 窥孔优化,9.4.4 特殊机器指令的使用为了提高效率，目标机器有时会使用一些硬件指令来实现某些特定的操作。例如，有一些机器具有自动加1和自动减1的寻址模式。这些模式的运用可以大大提高参数传递过程中压栈和出栈的代码质量，它们还可以用在形如i:=i+1的语句的代码中。,2023/10/9,48,9.4 窥孔优化,9.4.5 其他处理也可以利用其他一些途经进行窥孔优化。例如，通过删除那些不必要的连续转移；利用代数恒等性质删除形如x:=x+0或x:=x*1的代码的代数化简。,2023/10/9,49,9.5 寄存器分配与指派,由于只涉及寄存器运算对象的指令要比那些涉及内存运算对象的指令短且快，因此有效地利用寄存器非常重要。寄存器分配的任务是为程序的某一点选择应该驻留在寄存器中的一组变量寄存器指派则负责挑出变量将要驻留的具体寄存器。,2023/10/9,50,9.5.1 全局寄存器分配,由于程序的大多数时间都花在内层循环上，因此一种比较自然的全局寄存器分配方法是在整个循环中将经常引用的值保存在固定的寄存器中。假设已经利用第10章的技术找出了流图中的循环结构，而且知道基本块中计算出的哪些值要在该块外被引用，则有一种简单的全局寄存器分配策略，那就是分配固定数目的寄存器来保存每个内部循环中最活跃的值。不同循环选中的值也会有所不同。未被分配的寄存器可用于存放9.4节讨论的基本块的局部值。该方法的缺点是：固定的寄存器数目对全局寄存器分配来说可能不够用，但实现简单。,2023/10/9,51,9.5.2 引用计数,如果x在寄存器中，则对x的每次引用都将节省一个单元的开销。于是可以采用一种简单的方法来确定执行循环L时将变量x保存在寄存器中所节省的开销。计算循环L中为x分配寄存器所节省开销的近似公式：(9.5)其中，use(x,B)是定义x之前，块B中对x的引用次数。如果x在B的出口处是活跃的，而且B中含有对x的赋值，则live(x,B)为1，否则live(x,B)为0。注意，(9.5)是个近似公式。这是因为循环中的块的迭代次数可能是不一样的，而且我们还假设循环会迭代许多次。,2023/10/9,52,9.5.2 引用计数,例9.3 考虑图9.2中内层循环中的基本块，块中的跳转语句均已删除。假设用寄存器R0、R1和R2来保存循环中的值。为方便起见，图中还列出了在每个块入口和出口活跃的变量。e和f在B1的末尾都是活跃的，但只有e在B2的入口是活跃的，只有f在B3的入口是活跃的。一般地，块末尾活跃的变量是其后继块入口活跃变量的并集。,2023/10/9,53,例9.3,2023/10/9,54,例9.3,首先计算x=a时(9.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时(9.5)式的值为4。亦即，将a存入某个全局寄存器可以节省4个单元的开销。由于x=b、c、d、e和f时(9.5)式的值分别为6、3、6、4和4，因此可以将a、b和d放入寄存器R0、R1和R2。使用R0存放e或f而不是a可以节省相同的开销。,2023/10/9,55,例9.3,图9.3 使用全局寄存器分配的代码序列,2023/10/9,56,9.5.3 外层循环的寄存器指派,为内层循环分配了寄存器并生成代码之后，可以将同样的方法应用到外层循环上。如果外层循环L1包含内层循环L2，则在L2中分配了寄存器的变量不必再在L2-L1中分配寄存器。如果变量x是在循环L1中而不是在L2中分配了寄存器，则必须在L2的入口处保存x并在离开L2进入块L1-L2之前装载x。,2023/10/9,57,9.5.3 外层循环的寄存器指派,如果在L2而不是L1中为x分配了寄存器，则必须在L2的入口装载x，并在L2的出口保存x。如果计算时需要寄存器但所有可用的寄存器均被占用，则必须将某个正被使用的寄存器中的内容存放(溢出)到内存中以释放一个寄存器。图染色法是一种简单的用于寄存器分配和寄存器溢出管理的系统技术。,2023/10/9,58,本章小结,1.目标代码的生成需要尽力开发利用机器提供的资源，特别是根据开销选用恰当的指令和寄存器，以提高其执行效率；2.稀缺资源寄存器的有效利用涉及到后续引用问题，寄存器描述符用来记录每个寄存器当前的内容；地址描述符记录运行时存放变量当前值的一个或多个位置，用来确定对变量的存取方式；3.使用引用计数能够良好地实现寄存器的分配和指派；4.不同形式的三地址码对应不同的目标代码，且具有不同的执行代价；5.不可达和冗余指令删除、控制流优化、强度削弱、代数化简、特殊指令使用等都是有效的窥孔优化方法；,