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