编译原理 8
代码生成
- 要解决的问题
- 输入IR的选择: 四元式, 三元式, 字节代码, 堆栈机代码, 后缀表示, 抽象语法树, DAG
- 输出: RISC, CISC, 可重定向代码, 汇编语言
目标语言
- 目标机模型
- 使用三地址机器的模型
- 指令
- 加载: LD dst,addr addr内存的内容加载到dst寄存器
- 保存: ST x,r 寄存器r到x
- 计算: OP dst,src1,src2 两个值运算后到dst
- 无条件跳转: BR L 控制流转到标号L的指令
- 条件跳转: Bcond r,L 对r种的值进行测试, 为真转向L
- 寻址模式
- 变量x: 指向分配x的内存位置
- a(r): 地址是a的左值加上寄存器r中的值
- constant(r): 寄存器中内容加上前面的常数即地址
- *r: 寄存器的内容所表示的位置上, 存放的内容位置
- *constant(r): 寄存器中内容加上前面的常数所代表的位置, 上的内容所表示的位置
- #constant: 常量
- 程序及指令的代价
- 不同的目的有不同的度量
- 不可判定一个目标程序是否最优
目标语言中的地址
- 目标代码中的地址
- 如何为过程调用和返回生成代码
- 如何将变量名和函数名转换为地址? 不同区域的名字采用不同寻址方式
- 活动记录的静态分配
- 每个过程静态地分配一个数据区域, 用staticArea表示
- call callee
- ST callee.staticArea, #here+20
- BR callee.codeArea
- callee中的return
- BR *callee.staticArea: 跳转到静态区起始, 指向的地方(返回地址)
- 活动记录的栈式分配
- 寄存器SP指向栈顶
- 第一个过程main初始化栈区
- 过程调用指令序列
- ADD SP, SP, #caller.recordSize
- ST 0(SP), #here + 16
- BR callee.codeArea
- 返回指令序列
- BR *0(SP)
- SUB SP, SP, $caller.recordSize
- 名字的运行时刻地址
- 在三地址语句中使用名字: 实际上是指向符号表条目来引用变量
- 语句x = 0
- x在静态区, 且静态区开始位置为static, 则直接访问即可
- x在栈区, 且相对地址为12
- 基本块和流图
- 中间代码的流图表示法
- 中间代码划分为基本块
- 控制流只能从基本块的第一条指令进入
- 除基本块的最后一条指令外, 控制流不会跳转/停机
- 流图的结点是基本块, 边指明了哪些基本块可以在当前基本块后运行
- 流图可以作为优化的基础
- 指出了基本块之间的控制流
- 根据流图了解到一个值是否会被使用等信息
- 划分基本块的算法
- 方法
- 确定首指令leader
- 第一个三地址指令
- 任意一个转移指令的目标指令
- 紧跟在一个转移指令之后的指令
- 确定基本块: 每个首指令对应一个基本块, 从一个首指令到下一个首指令
- 后续使用信息
- 变量值的使用
- 三地址语句i向x赋值, 如果另一个语句j的运算分量为x, 且从i开始有一条路径到j, 且路径上没有对x赋值, 那么j就使用了i处计算得到的x值
- 我们说变量x在语句i后的程序点上活跃
- 程序执行完i, x中存放的值将被后面的语句使用
- 不活跃是指值不会被使用, 而不是变量不被只用
- 用于代码生成: 如果不活跃, 且x占用了一个寄存器, 则可以将这个寄存器用于其他目的
- 确定基本块中的活跃性
- 方法
- 从B的最后一个语句开始反向扫描
- 对于每个语句i: x = y + z
- 令语句i和x, y, z的当前活跃性信息/使用信息关联
- 设置x为不活跃和无后续使用
- 设置y和z为活跃, 并指明他们下一次使用设置为语句i
- 流图的构造
- 流图的结点是基本块
- 两个结点B和C之间有一条有向边iff基本块C的第一个指令可能在B的最后一个指令之后执行
- 存在边的原因
- B的结尾指令是跳转到C的开头的条件/无条件语句
- C紧跟在B之后, 且B的结尾不是无条件跳转语句
- B是C的前驱, C是B的后继
- 入口/出口结点
- 不和任何中间指令对应; 入口到第一条指令有一条边, 任何可能最后执行的基本块到出口有一条边
- 循环
- 程序中的大部分时间都花在循环上
- 循环的定义
- 循环L是一个结点集合
- 存在一个循环入口, 是唯一的, 前驱可以在这个循环之外, 到达循环的其余结点的路径必然经过这个入口
- 其余结点都存在到达入口的非空路径, 即路径在L中
基本块优化
- 基本块的优化
- 针对基本块的优化(局部优化)
- DAG图可以反应变量及其值对其他变量的依赖关系
- 构造方法
- 每个变量都有一DAG结点表示其初始值
- 每个语句s有一个相关的结点N, 代表此计算得到的值
- N的子节点对应于(得到其运算分量当前值的)其他语句
- N的标号是s中的运算符, 同时还有一组变量被关联到N, 表示s是最晚对这些变量进行定值的语句\
- DAG构造
- 为基本块中出现的每个变量建立结点(表示初始值)
- 顺序扫描各个三地址指令
- 指令x = y op z
- 为该指令建立结点N, 标号op, 令x和N关联
- N的子节点为y,z当前关联的结点
- 指令x=y
- 扫描结束后, 出口处活跃的变量x, 其关联的结点设置为输出结点
- DAG的作用
- 以DAG为基础, 对代码进行转换
- 寻找局部公共子表达式
- 局部公共子表达式的发现
- 建立某个结点M之前, 检查是否存在一个结点N, 它和M具有相同的运算符和子节点(顺序也相同)
- 如果存在, 则不需要生成新结点, N代替M
- 消除死代码
- DAG图上, 消除没有附加活跃变量的根节点, 即消除死代码
- 代数恒等式的使用
- 消除计算步骤(加减乘除, 01的特殊)
- 降低强度: 例如乘2变为加
- 常量合并: 常量计算变赋值
- 数组引用的表示
- 从数组取值的运算, 对应于=[]的结点
- 这个结点的子节点是数组对应初始值a和下标i
- 变量x是这个结点的标号之一
- 对数组赋值的运算对应于[]=的结点
- 这个结点的三个子节点分别表示a, 下标i和值y
- 杀死所有依赖于a的变量
- 指针赋值和过程调用
- 通过指针进行取值/赋值: x=*p, q*=y
- x使用了任意变量, 因此无法消除死代码
- *q=y对任意变量赋值, 因此杀死了全部其他节点
- 可通过(全局/局部)指针分析, 部分解决该问题
- 过程调用类似
- 使用了可访问范围内的所有变量
- 修改了课访问范围内的所有变量
- 从DAG到基本块
- 重构的方法
- 每个结点构造一个三地址语句, 计算对应的值
- 结果尽量赋值给一个活跃的变量
- 如果结点有多个关联的变量, 则需要用赋值语句进行赋值
- 多个变量可选作为参数时, 尽量使用已经活跃的变量, 尽量少地将不活跃的变量变成活跃
- 重组的规则
- 注意求值顺序
- 指令必须遵守DAG中结点的顺序
- 对数组赋值要跟在原来之前的赋值/求值之后
- 对数组求值要跟在原来的赋值指令之后
- 对变量的使用必须跟在所有原来在他之前的过程调用和指针间接复制之后
- 任何过程调用或指针间接赋值必须跟在原来它之前的变量求值之后
- 即保证
代码生成器
- 根据三地址指令序列生成机器指令
- 假设每个三地址指令只有一个对应的机器指令
- 主要目标是减少加载LD和保存ST指令, 即最大限度地利用寄存器
- 寄存器的使用方法
- 执行运算时, 运算分量必须放在寄存器中
- 存放临时变量
- 存放全局的值
- 进行运行时刻管理(比如栈顶指针)
- 算法的基本思想和数据结构
- 依次考虑各个三地址指令, 尽可能把值保留在寄存器中, 以减少寄存器/内存之间的数据交换
- 为一个三地址指令生成机器指令时
- 只有当运算分量不在寄存器中时, 才从内存载入
- 尽量保证只有当寄存器中的值不被使用时, 才覆盖掉
- 数据结构
- 寄存器描述符: 跟踪各个寄存器存放了哪些变量的当前值
- 地址描述符: 各个变量当前值存放在哪些位置上(内存/寄存器位置)
- 代码生成算法
- 重要子函数getReg(I)
- 根据寄存器描述符和地址描述符等数据流信息, 为三地址指令I选择最佳的寄存器
- 得到的机器指令的指令依赖于getReg函数选取寄存器的算法
- 代码生成算法逐个处理三地址指令
- 运算语句: x = y + z
- getReg(x = y + z)为xyz选择寄存器Rx Ry Rz
- 检查Ry的描述符, 如果y不在Ry中, 则生成指令LD Ry,y’, y’为当前位置
- Rz类似
- 生成指令ADD Rx,Ry,Rz
- 复制语句: x = y
- getReg(x = y)为xy选择相同的寄存器
- 如果y不在Ry中, 则生成指令LD Ry, y
- 基本块的收尾
- 如果x活跃, 且不在内存中, 则生成指令ST x,Rx
- 代码生成的同时, 更新寄存器和地址描述符
- 处理指令时生成的LD R, x
- R的寄存器描述符: 只包含x
- x的地址描述符: R作为新位置加入到x的位置集合中, 从任何不同于x的变量描述符中删除R
- 生成的ST x,R
- ADD Rx,Ry,Rz
- Rx的寄存器描述符: 只包含x
- x的地址描述符: 只包干Rx
- 从任何不同于x的变量的地址描述符中删除Rx
- 处理x=y时
- 如果生成LD Ry,y, 按照第一个规则处理
- 把x加入到Ry的寄存器描述符中
- x的地址描述符: 只包含Ry
- getReg函数
- 目标: 减少LD/ST指令
- 任务: 为运算分量和结果分配寄存器
- 为x= y op z的运算分量yz分配寄存器
- 如果y已经在某一个寄存器中, 不需要进行处理, 选择这个寄存器Ry
- 如果不在, 且有空闲寄存器, 选择一个空闲寄存器
- 如果不在且无空闲, 寻找一个寄存器R, 其寄存器描述符表示v在R中
- 如果v的地址描述符表明, 还可以在别的地方找到v, DONE
- 如果v就是x, 且x不是运算分量z, DONE
- 如果v在此之后不会被使用(不活跃), DONE
- 生成保存指令ST v,R, 并修改v的地址描述符, 如果R中存放了多个变量的值, 那么需要生成多条ST指令
- 为x = y op z结果选择寄存器Rx的方法和上面要把y从内存LD一样, 但是
- 只存放x值的寄存器总是可以接受的
- 如果y在指令之后不再使用, 且Ry仅仅保存了y值, 那么Ry同时也可作为Rx
- 处理x=y时, 先选择Ry, 然后让Rx = Ry
- 窥孔优化
- 使用一个滑动窗口, 来检查目标指令, 在窥孔内实现优化
- 冗余指令消除
- 控制流优化
- 代数化简, 强度消减
- 机器特有指令的使用
- 冗余指令的消除
- 多余的LD, ST指令: LD R0,a; ST a,R0; 且后者无标号
- 级联跳转代码
- IF GOTO反转条件优化
- 如果条件已知是0或1, 那么替换为一个跳转即可
- (if x op y) goto L1; … L1:goto L2: 优化为goto L2; … L1:goto L2
- 代数化简/强度消减.机器特有指令
- 代数恒等式: +0 *1
- 机器特有指令: INC, DEC
寄存器分配
- 寄存器分配和指派
- 寄存器分配: 确定程序的每个点上, 哪个值应该存放在寄存器中
- 寄存器指派: 各个值应该给存放在哪个寄存器
- 简单方法: 特定类型的值分配给特定的寄存器(专存专用)
- 全局寄存器分配
- 循环中频繁使用的值存放在固定寄存器
- 可以通过计数的方法, 估算把一个值放到寄存器里面会带来多大好处
- 树重写实现指令选择
- 某些机器上, 某一个三地址指令可以使用多种机器指令实现, 有时多个三地址指令可以使用一个机器指令实现
- 指令选择
- 实现中间表示形式中出现的运算符, 选择适当的机器指令
- 用树来表示中间代码, 按照特定的规则不断覆盖这颗树, 生成机器指令
- 目标指令选择
- 重写规则 replacement <- template [ action ]: 替换结点: 是一个结点, 模板是一颗子树, 动作类似语法制导翻译的代码片段
- 一组树重写规则被称作一个翻译方案
- 只剩一个结点则重写结束
- 树翻译方案的工作模式
- 给定一颗输入树, 树重写规则中的模板被用来匹配输入树的子树
- 如果匹配到, 则将这个子树替换为替换节点, 执行相应动作(生成机器指令)
- 不断匹配, 直到变成单一节点, 或者找不到可以匹配的模板为止
- 此方案中得到的指令代码序列就是树翻译方案对于给定输入树的输出
- 如何完成树匹配
- 把树重写规则替换成相应的上下文无关文法的产生式
- 右部是其指令模板的前缀表示
- 如果在某个时刻有多个模板匹配, 则大树优先
扫一扫，分享到微信
{title}
