第八章代码生成

《第八章代码生成》由会员分享，可在线阅读，更多相关《第八章代码生成（65页珍藏版）》请在装配图网上搜索。

1、第八章 代码生成南京大学计算机系赵建华代码生成器的位置根据中间表示生成代码代码生成器之前可能有一个优化组件代码生成器的三个任务指令选择：选择适当的指令实现IR语句寄存器分配和指派：把哪个值放在哪个寄存器中指令排序：按照什么顺序安排指令执行主要内容要解决的问题机器模型静态/栈式数据区分配基本块相关的代码生成简单的代码生成算法窥孔优化要解决的问题正确性：正确的机器指令易于实现、测试和维护输入IR的选择四元式、三元式、字节代码、堆栈机代码、后缀表示、抽象语法树、DAG图、输出RISC、CISC；可重定向代码、汇编语言目标机模型使用三地址机器的模型指令加载：LD dst,addr；把地址addr中的内

2、容加载到dst所指寄存器。addr：内存地址/寄存器保存：ST x,r；把寄存器r中的内容保存到x中。计算：OP dst,src1,src2；把src1和scr2中的值运算后将结果存放到dst中。无条件跳转：BR L；控制流转向标号L的指令条件跳转：Bcond r,L；对r中的值进行测试，如果为真则转向L。寻址模式变量x：指向分配x的内存位置a(r)：地址是a的左值加上r中的值constant(r)：寄存器中内容加上前面的常数即其地址；*r：寄存器r的内容为其地址*constant(r)：r中内容加上常量所指地址中存放的值为其地址常量#constant例子x=y-zLDR1,y/R1=yLDR

3、2,z/R2=xSUB R1,R1,R2/R1=R1-R2STx,R1/x=R1b=aiLRR1,I/R1=iMULR1,R1,8/R1=R1*8LDR2,a(R1)/R2=contents(a+contents(R1)STb,R2/b=R2程序及指令的代价不同的目的有不同的度量最短编译时间、目标程序大小、运行时间、能耗不可判定一个目标程序是否最优我们假设：每个指令有固定的代价，设定为1加上运算分量寻址模式的代价LD R0,R1；代价为1LD R0,M；代价是2LD R1,*100(R2)；代价为2目标代码中的地址如何将IR中的名字转换成为目标代码中的地址不同的区域中的名字采用不同的寻址方式。

4、如何为过程调用和返回生成代码静态分配栈式分配活动记录的静态分配每个过程静态地分配一个数据区域，开始位置用staticArea表示call callee的实现STcallee.staticArea,#here+20/存放返回地址BRcallee.codeAreaCallee中的语句returnBR*callee.staticArea例子三地址代码action1call paction 2halt/p的代码action3return 活动记录栈式分配寄存器SP指向栈顶第一个过程（main）初始化栈区过程调用指令序列ADD SP,SP,#caller.recordSize/增加栈指针ST 0(SP)

5、,#here+16/保存返回地址BR callee.codeArea/转移到被调用者返回指令序列BR *0(SP)/被调用者执行，返回调用者SUP SP,SP,#caller.recordSize /调用者减低栈指针例子名字的运行时刻地址在三地址语句中使用名字（实际上是指向符号表条目）来引用变量语句x=0如果x分配在静态区域，且静态区开始位置为static。static12=0ST 112#0如果x分配在栈区，且相对地址为12，则ST 12(SP)#0基本块和流图中间代码的流图表示法中间代码划分成为基本块(basic block)。控制流只能从第一个指令进入除基本块的最后一个指令外，控制流不会

6、跳转/停机流图的结点是基本块。流图的边指明了哪些基本块可以跟在一个基本块之后运行流图可以作为优化的基础它指出了基本块之间的控制流可以根据流图了解到一个值是否会被使用等信息划分基本块的算法输入：三地址指令序列输出：基本块的列表方法：确定leader指令（基本块的第一个指令）第一个三地址指令任意一个条件或无条件转移指令的目标指令紧跟在一个条件/无条件转移指令之后的指令确定基本块每个首指令对应于一个基本块：从首指令开始到下一个首指令基本块划分的例子第一个指令1跳转指令的目标3、2、13跳转指令的下一条指令10、12基本块：1-1；2-2；3-9；10-11；12-12；13-17后续使用信息变量值的

7、使用三地址语句i向x赋值、如果j的运算分量为x，且从i开始有一条路径到达j，且路径上没有对x赋值，那么j就使用了i处计算得到的x的值。我们说x在语句i后的程序点上活跃即在程序执行完语句i的时刻，x中存放的值将被后面的语句使用不活跃是指变量中存放的值不会被使用，而不是变量不会被使用；这些信息可以用于代码生成如果x在i处不活跃，且x占用了一个寄存器，我们可以把这个寄存器用于其它目的。确定基本块中的活跃性、后续使用输入：基本块B，开始时B的所有非临时变量都是活跃的；输出：各个语句i上的变量的活跃性、后续使用信息方法：从B的最后一个语句开始反向扫描对于每个语句i：x=y+z。令语句i和x、y、z的当前

8、活跃性信息/使用信息关联设置x为不活跃、无后续使用设置y和z为活跃，并指明它们的下一次使用为语句i例子假设i,j,a不是临时变量。它们在出口处活跃，其余变量不活跃在8之前的程序点上，i,j,a仍然活跃；且j在8上被使用在7之前的程序点上，i,j,a,t4活跃；且t4被7使用；在6之前的程序点上，i,j,a,t3活跃，t4不活跃，t3被6使用；在5之前的程序点上，i,j,a,t2活跃，t3不活跃；在4之前的程序点上，流图的构造流图的顶点是基本块两个顶点B和C之间有一条有向边 iff 基本块C的第一个指令可能在B的最后一个指令之后执行。存在边的原因：从B的结尾指令是一条跳转到C的开头的条件/无条件

9、语句在原来的序列中，C紧跟在B之后，且B的结尾不是无条件跳转语句我们称B是C的前驱，C是B的后继入口，出口结点流图中额外添加的边，不对应于中间代码（基本块）对应入口到第一条指令有一条边从任何可能最后执行的基本块到出口有一条边流图的例子因跳转而生成的边B3B3B4B2B6B6因为顺序而生成的边其它循环程序的大部分运行时间花费在循环上因此循环是识别的重点循环的定义循环L是一个结点集合存在一个循环入口（loop entry）结点。是唯一的、前驱可以在循环L之外的结点，到达其余结点的路径必然先进国这个入口结点；其余结点都存在到达入口结点的非空路径，且路径都在L中。循环的例子循环B3B6B2,B3,B4

10、对于B2,B3,B4的解释B2为入口结点B1，B5，B6不在循环内的理由到达B1可不经过B2B5，B6没有到达B2的结点基本块的优化针对基本块的优化可以有很好的效果基本块中各个指令要么都执行，要么都不执行基本块可以用DAG图表示每个变量对应于DAG图的结点，代表初始值；每个语句s有一个相关的结点N，代表计算得到的值N的子结点对应于（其运算分量当前值的）其它语句。结点N的标号是s的运算符N和一组变量关联，表示s是在此基本块内最晚对它们定值的语句。输出结点：结点对应的变量在基本块出口处活跃从DAG图，我们可以知道各个变量最后的值和初始值的关系；DAG图的构造为基本块中出现的每个变量建立结点（表示初

11、始值），各变量和相应结点关联顺序扫描各个三地址指令，进行如下处理：如果指令为x=y op z为这个指令建立结点N，标号为op；N的子结点为y、z当前关联的结点；令x和N关联；如果指令为x=y；不建立新结点；设y关联到N，那么x现在也关联到N扫描结束后，对于所有在出口处活跃的变量x，将x所关联的结点设置为输出结点例子指令序列a=b+cb=a-dc=b+c过程：结点b0，c0和d0对应于b，c和d的初始值；它们和相应结点关联；a=b+c:构造第一个加法结点，a与之关联b=a-d：构造减法结点，b与之关联c=b+c：构造第二个加法结点，c与之关联（注意第一个子结点对应于减法结点）如果还有第四条指令c

12、=a，流图会如何处理？DAG的作用DAG图描述了基本块运行时各变量的值（和初始值）之间的关系。我们可以以DAG为基础，对代码进行转换消除局部公共子表达式消除死代码对语句重新排序重新排序运算分量的顺序局部公共子表达式局部公共子表达式的发现建立某个结点M之前，首先检查是否存在一个结点N，它和M具有相同的运算符和子结点（顺序也相同）。如果存在，则不需要生成新的结点，用N代表M；例如：a=b+cb=a-dc=b+cd=a-d注意：两个b+c实际上并不是公共子表达式消除死代码在DAG图上消除没有附加活跃变量的根结点（没有父结点的结点），即消除死代码如果图中c、e不是活跃变量，则可以删除标号为e、c的结点

13、。应用代数恒等式的优化消除计算步骤x+0=0+x=xx-0=xx*1=1*x=xx/1=x降低计算强度X2=x*x2*x=x+x常量合并2*3.14可以用6.28替换实现这些优化时，只需要在DAG图上寻找特定的模式数组引用注意：aj可能改变ai的值，因此不能和普通的运算符一样构造相应的结点x=aiaj=yz=ai从数组取值的运算x=ai对应于=的结点，x作为这个结点的标号之一；对数组赋值的运算对应于=的结点；没有关联的变量、且杀死所有依赖于a的变量；数组引用的DAG的例子设a是数组，b是指针b=12+ax=bibj=y注意a是被杀死的结点的孙结点一个结点被杀死，意味着它不能被复用考虑再有指令m

14、=bi?指针赋值/过程调用通过指针进行取值/赋值：x=*p *q=y。最粗略地估计：x使用了任意变量，因此无法消除死代码而*q=y对任意变量赋值，因此杀死了全部其他结点可以通过（全局/局部）指针分析部分解决这个问题；过程调用也类似，必须安全地假设它使用了可访问范围内的所有变量修改了可访问范围内的所有变量从DAG到基本块重构的方法每个结点构造一个三地址语句，计算对应的值结果应该尽量赋给一个活跃的变量如果结点有多个关联的变量，则需要用复制语句进行赋值。重组基本块的例子根据DAG构造是结点产生的顺序a=b+cd=a-db=dc=d+c重组的规则重组时应该注意求值的顺序指令的顺序必须遵守DAG中结点的

15、顺序对数组的赋值必须跟在所有原来在它之前的赋值/求值操作之后对数组元素的求值必须跟在所有原来在它之前的赋值指令之后对变量的使用必须跟在所有原来在它之前的过程调用和指针间接赋值之后任何过程调用或者指针间接赋值必须跟在原来在它之前的变量求值之后。总的来说，我们必须保证：如果两个指令之间可能相互影响，那么他们的顺序就不应该改变。代码生成器根据三地址指令序列生成机器指令假设：每个三地址指令只有一个对应的机器指令有一组寄存器用于计算基本块内部的值；主要的目标是尽量减少加载和保存指令，即最大限度利用寄存器；寄存器的使用方法执行运算时，运算分量必须放在寄存器中；用于临时变量存放全局的值进行运行时刻管理（比如

16、：栈顶指针）算法的基本思想的数据结构依次考虑各三地址指令，尽可能把值保留在寄存器中，以减少寄存器/内存之间的数据交换为一个三地址指令生成机器指令时，只有当运算分量不在寄存器中时，才从内存载入；尽量保证只有当寄存器中的值不被使用时，才把它覆盖掉。数据结构：记录各个值对应的位置寄存器描述符：跟踪各个寄存器都存放了哪些变量的当前值；地址描述符：某个变量的当前值存放在哪个或哪些位置(包括内存位置和寄存器）上；代码生成算法（1）重要子函数：getReg(I)根据寄存器描述符和地址描述符、数据流信息，为三地址指令I选择最佳的寄存器；得到的机器指令的质量依赖于getReg函数选取寄存器的算法；代码生成算法逐

17、个处理三地址指令代码生成算法（2）x=y+z调用getReg(x=y+z)，为x,y,z选择寄存器Rx,Ry,Rz查Ry的寄存器描述符，如果y不在Ry中则生成指令：LD Ry y(y表示存放y值的当前位置)类似地，确定是否生成LD Rz,z生成指令ADD Rx,Ry,Rz复制语句：x=ygetReg(x=y)总是为x和y选择相同的寄存器如果y不在Ry中，生成机器指令LD Ry,y基本块的收尾如果变量x在出口处活跃，且x现在不在内存，那么生成指令ST x,Rx。代码生成算法（3）代码生成同时更新寄存器和地址描述符处理普通指令时生成LD R xR的寄存器描述符：只包含xx的地址描述符：R作为新位置

18、加入到x的位置集合中从任何不同于x的变量的地址描述符中删除RST x,R修改x的地址描述符，包含自己的内存位置代码生成算法（4）ADD Rx,Ry,RzRx的寄存器描述符只包含xx的地址描述符只包含Rx（不包含x的内存位置！）从任何不同于x的变量的地址描述符中删除Rx。处理x=y时，如果生成LD Ry y，按照第一个规则处理；把x加入到Ry的寄存器描述符中（Ry存放了x和y的当前值）；修改x的地址描述符，使它只包含Ry。例子（1）a、b、c、d在出口处活跃t、u、v是局部临时变量t=a-bu=a cv=t+ua=dd=v+u例子（2）例子（3）getReg函数（1）getReg的目标：减少LD

19、/ST指令任务：为运算分量和结果分配寄存器为运算分量分配寄存器如果已经在某个寄存器中，不需要进行处理，选择这个寄存器；如果不在寄存器中，且有空闲寄存器，选择一个空闲寄存器如果不在寄存器中，且没有空闲寄存器？getReg函数（2）为运算分量分配寄存器如果不在寄存器中，且没有空闲寄存器寻找一个寄存器R，且R的寄存器描述符表示v在R中如果v的地址描述符表明还可以在别的地方找到v，DONEv就是x（即结果），且x不是运算分量之一，DONE如果v在此之后不会被使用，DONE生成保存指令ST v R；（溢出操作）并修改v的地址描述符；如果R中存放了多个变量的值，那么需要生成多条ST指令；getReg函数（

20、3）为x选择寄存器Rx的方法基本上和上面要把y从内存LD时一样；但是只存放x的值的寄存器总是可接受的；如果y在指令I之后不再使用，且Ry仅仅保存了y的值，那么Ry同时也可以作为Rx；处理x=y时，我们总是让Rx=Ry。窥孔优化使用一个滑动窗口（窥孔）来检查目标指令，在窥孔内实现优化冗余指令消除控制流优化代数简化机器特有指令的使用冗余指令多余的LD/ST指令LD a R0ST R0 a且没有指令跳转到第二条指令处级联跳转代码if debug=1 goto L1；goto L2if debug!=1 goto L2;如果已知debug一定是0，那么替换成为goto L2；控制流优化gotoL1;L1：goto L2goto L2;goto L2if ab goto L1;L1:goto L2if a0内部结点：求Ci时，按照不同的顺序，第一个子结点