《8编译原理之代码生成》由会员分享，可在线阅读，更多相关《8编译原理之代码生成（64页珍藏版）》请在金锄头文库上搜索。
1、第八章 代码生成,湖南大学计算机与通信学院（软件学院）,代码生成器的位置,根据中间表示生成代码代码生成器之前可能有一个优化组件代码生成器的三个任务指令选择：选择适当的指令实现IR语句寄存器分配和指派：把哪个值放在哪个寄存器中指令排序：按照什么顺序安排指令执行,主要内容,代码生成器设计中的问题目标机模型静态/栈式数据区分配基本块相关的代码生成简单的代码生成算法窥孔优化,8.1代码生成器设计中的问题,设计目标：生成代码的正确性（最重要）易于实现、测试和维护输入输出指令选择寄存器分配计算顺序,代码生成器设计中的问题,输入前端生成的源代码的IR(中间表示形式）及符号表信息中间表示形式的选择四元式、三元
2、式、字节代码、堆栈机代码、后缀表示、抽象语法树、DAG图、输出RISC、CISC；可重定向代码、汇编语言,代码生成器设计中的问题,指令选择代码生成器将中间表示形式映射为目标机代码映射的复杂性由下列因素决定：IR的层次高：用代码模板翻译，但代码质量不高，需优化低：利用低层次细节生成更高效的代码指令集体系结构本身的特性期望的目标代码质量,代码生成器设计中的问题,指令选择映射的复杂性由下列因素决定：IR的层次指令集体系结构本身的特性指令的统一性、完整性指令速度和机器惯用语(idioms)期望的目标代码质量,代码生成器设计中的问题,指令选择映射的复杂性由下列因素决定：IR的层次指令集体系结构本身的特性
3、期望的目标代码质量同一IR程序可用不同代码序列实现，它们的代价不同,示例：a=a+1可实现为两种,INC a,LD R0,aADD R0,R0,#1ST a，R0,8.2 目标机模型,本书使用三地址机器模型，指令如下：加载LD dst, addr；把地址addr中的内容加载到dst所指寄存器。addr：内存地址/寄存器保存ST x, r；把寄存器r中的内容保存到x中。计算OP dst, src1, src2；把src1和scr2中的值运算后将结果存放到dst中。无条件跳转BR L；控制流转向标号L的指令条件跳转Bcond r, L；对r中的值进行测试，如果为真则转向L。,寻址模式,变量x：指向
4、分配x的内存位置a(r)：地址是a的左值加上r中的值（可类比一维数组方便记忆）constant(r)：寄存器中内容加上前面的常数即其地址；（可类比一维数组方便记忆）*r：寄存器r的内容为其地址*constant(r)：r中内容加上常量的和所指地址中存放的值为其地址（可类比一维数组方便记忆）常量#constant56,例子,x=y-zLDR1, y/R1=yLDR2, 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)
5、STb, R2/b = R2,程序及指令代价,不同的目的有不同的度量最短编译时间、目标程序大小、运行时间、能耗不可判定一个目标程序是否最优指令代价指令固定代价(设为1)运算分量寻址模式代价，例：LD R0, R1；代价为1LD R0, M；代价是2LD R1, *100(R2)；代价为2,常数和内存地址增加代价1，寄存器增加代价为0。,8.3 目标代码中的地址,Q:如何将IR中的名字转换成目标代码中的地址？A：程序运行时环境划分为4个区域：代码区Code、静态区Static、栈区Stack和堆区Heap。不同区域中的名字采用不同寻址方式。如何为过程调用和返回生成代码静态分配栈式分配,活动记录静
6、态分配,每个过程静态地分配一个数据区域，开始位置用staticArea表示call callee的实现STcallee.staticArea, #here+20/保存返回地址BRcallee.codeArea .callee中的语句returnBR*callee.staticArea,*为突出重点，经常将活动记录中其它的部分忽略。,常量1字长,实际为一个常量1字长,常量1字长,一个指令1字长,一个指令1字长,返回地址,例子,三地址代码action1call paction 2halt/p的代码action3return,活动记录栈式分配,寄存器SP指向栈顶第一个过程（main）初始化栈区过程调
7、用指令序列ADD SP, SP, #caller.recordSize/增加栈指针,越过调用者自身的活动记录ST 0(SP), #here+16 /保存返回地址BR callee.codeArea /转移到被调用者返回指令序列BR *0(SP)/被调用者最后执行，返回调用者SUP SP, SP, #caller.recordSize /调用者中减低栈指针34,例：快速排序,未完，转下页,例:快速排序,接上页,名字的运行时刻地址,在三地址语句中使用名字（实际上是按符号表条目提供的信息）来引用变量三地址语句x=0如果x分配在开始位置为static静态区域，且符号表中保存的相对地址为12，则可以译为
8、：static12 = 0设静态区从100开始，则也可译为LD 112 #0如果x分配在栈区，且相对地址为12，则LD 12(SP) #0,基本块和流图,中间代码的流图表示法中间代码划分成为基本块(basic block)，其特点是单入口单出口，即：控制流只能从第一个指令进入除了基本块最后一个指令，控制流不会跳转/停机流图中结点是基本块，边指明了哪些基本块可以跟在一个基本块之后运行流图可作为优化的基础它指出了基本块之间的控制流可根据流图了解一个值是否会被使用等信息,划分基本块的算法,输入：三地址指令序列输出：基本块的列表方法：确定leader指令（基本块的第一个指令）符合以下任一条：中间代码的
9、第一个三地址指令任意一个条件或无条件转移指令的目标指令紧跟在一个条件/无条件转移指令之后的指令确定基本块每个首指令对应于一个基本块：从首指令（包含）开始到下一个首指令（不含）,基本块划分举例,第一个指令1跳转指令的目标3、2、13跳转指令的下一条指令10、12基本块：1-1；2-2；3-9(包括跳转语句)；10-11(包括跳转语句) ；12-12；13-17 (包括跳转语句),下次引用信息,变量值的使用如果三地址语句i对x赋值、三地址语句j的运算分量含x，且从i到j有一条路径，且路径上无对x的重新赋值，则称j使用了语句i计算得到的x值，称x在语句i处活跃（以后有用）x(i)=y或n。下次引用和
10、活跃信息可用于代码生成如果x在i处不活跃，且x占用了一个寄存器，则该寄存器在i后可用于其它目的。,活跃变量与非活跃变量,变量的定值点和使用点：设有四元式：q(w B C A )B,C的使用点(q)A的定值点(q)活跃变量与非活跃变量【活跃变量】一个变量从某时刻(q)起,到下一个定义点止，其间若有使用点，则称该变量在q是活跃的(y),否则称该变量在q是非活跃的(n)。简单的说，Q活跃就是指Q定义的值被使用过。 q一般为各个行号,确定基本块中的活跃性、下次引用,输入：基本块B，开始时B的所有非临时变量都是活跃的；输出：每个语句i中变量的活跃性、下次使用信息方法：所有的非临时变量初始化为活跃的，从B
11、的最后一个语句开始反向扫描, 对于每个语句i：x=y+z。令语句i和x、y、z的当前活跃性信息/使用信息关联设置x为不活跃、无下次引用设置y和z为活跃，并指明它们的下一次使用为语句i注意二和三顺序不能错，查看基本块a=a+b,a最终是活跃还是？,流图的构造,流图的顶点是基本块两个顶点B和C之间有一条有向边，当且仅当基本块C的第一个指令有可能在B的最后一个指令之后执行。原因：B的结尾指令是一条跳转到C的开头的条件/无条件语句在原来的序列中，C紧跟在B之后，且B的结尾不是无条件跳转语句B是C的前驱，C是B的后继流图中增加额外的入口，出口结点各一个不对应于实际的中间指令（是增加）。入口到第一条指令有
12、一条边从任何可能最后执行的基本块到出口有一条边,流图绘制举例,流图的例子,因跳转而生成的边B3B3B4B2B6B6因为顺序而生成的边其它,循环,程序的大部分运行时间花费在循环上因此循环是识别的重点循环的定义循环L是一个结点集合存在一个循环入口（loop entry）节点，其唯一的前驱可以是循环L之外的结点其余结点都存在到达L的入口的非空路径，且路径都在L中。,循环的例子,循环B3B6B2,B3,B4,8.5 基本块的几种优化,一个基本块可用一个DAG图表示(基本的DAG图)每个变量对应于一个结点，表示初始值每条语句s有一个相关结点N,具有子结点：对应于其它语句,是在s之前，最后一个对s所使用的
13、某个运算分量进行定值的语句。标记：s的运算符附加标记：一组变量，表明s是在此基本块内最晚对该变量定值某些输出结点：结点对应的变量在基本块出口处活跃（出口活跃属于全局数据流分析）,DAG示例,语句S的结点N和子结点,s运算符当结点标记,附加标记,变量的结点,DAG图的构造,为基本块中出现的每个变量建立结点（表示基本值）顺序扫描各个三地址指令如果指令为x=y op z为这个指令建立结点N，标号为op；N的子结点为y、z当前关联的结点；X和N关联；如果指令为x=y；不建立新结点；设y关联到N，那么x现在也关联到N扫描结束后，对于所有在出口处活跃的变量x，将x所关联的结点设置为输出结点,DAG的作用,
14、DAG图描述了基本块运行时各个值之间的关系。可以DAG为基础，对代码进行转换消除局部公共子表达式消除死代码对语句重新排序重新排序运算分量的顺序,局部公共子表达式,局部公共子表达式的发现建立某个结点M之前，首先检查是否存在一个结点N，它和M具有相同的运算符和子结点（顺序相同）。如果存在，则不需要生成新的结点，用N代表M；例如：a=b+cb=a-dc=b+cd=a-d找出公共的表达式？注意：两个b+c实际上并不是公共子表达式,消除死代码,在DAG图上消除没有附加活跃变量的根结点（没有父结点的结点），即可消除死代码如果图中c、e不是活跃变量，则可以删除标号为e、c的结点。,DAG方法的不足,为了计算
15、第四式的e值，而有的2,3式实际上是冗余的，也就是第一式和第四式等价。该代码本可优化，但发现不了,在DAG上应用代数恒等式的优化,消除计算步骤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图上寻找特定的模式56,数组引用避免误优化,注意：aj可能改变ai的值，因此不能和普通的运算符一样构造相应的结点x=aiaj=yz=ai从数组取值的运算x=ai对应于“=”的结点，x作为这个结点的标号之一；对数组赋值的运算对应于 “=”的结点；没有关联的变量、且杀死所有依赖于a的变量；Kille
16、d节点不能成为公共子表达式,杀手,被杀者,杀手,引入新的运算符,数组引用的DAG的例子,b=12+ax=bibj=y注意a是被杀死结点的孙结点。,x,如果没有杀手的出现则被杀者本可以象前述一样进行优化。杀死的意思指不能参加优化,指针赋值/过程调用,通过指针进行取值/赋值：x=*p *q=y。最粗略地估计：x使用了任意变量，因此无法消除死代码而*q=y对任意变量赋值，因此杀死了全部其他结点(可类似引出新的运算符“=*”与“*=”帮助分析)杀的范围过大。可以通过（全局/局部）指针分析,缩小范围；比如针对p=&x*p=y可以只杀死那些以x为附加变量的结点过程调用也类似，为了安全：必须假设它使用了访问范围内所有变量假设修改了访问范围内的所有变量 。杀谁？全杀 !,
