南京大学计算机科学与技术系官网,第八章代码生成 - 南京大学计算机科学与技术系.ppt...

第八章代码生成 - 南京大学计算机科学与技术系

基于动态规划的最优代码生成算法 连续求值 对一个表达式的求值总是先求出一个子表达式的值、再求另一个子表达式的值，再计算出最终的值； 满足如下条件的机器保证了连续求值的方法具有最好的效率； 具有r各可互换的寄存器R0, … ,Rr-1； 加载、保存、运算指令； 代价向量 表达式树的每个结点对应于一个代价数组C，C的第i个元素C[i]表示有i各元素可用是，对相应子树求值，并放在一个寄存器中的代价；C[0]表示值放在内存； 计算C[i] 叶子结点：C[0]=0，C[i]=1，i>0 内部结点：求C[i]时，按照不同的顺序，第一个子结点 数组引用 注意：a[j]可能改变a[i]的值，因此不能和普通的运算符一样构造相应的结点 x=a[i] a[j]=y z=a[i] 从数组取值的运算x=a[i]对应于=[]的结点，x作为这个结点的标号之一； 对数组赋值的运算对应于[]=的结点；没有关联的变量、且杀死所有依赖于a的变量； 数组引用的DAG的例子 设a是数组，b是指针 b=12+a x=b[i] b[j]=y 注意a是被杀死的结点的孙结点 一个结点被杀死，意味着它不能被复用 考虑再有指令m=b[i]? 指针赋值/过程调用 通过指针进行取值/赋值：x=*p *q=y。最粗略地估计： x使用了任意变量，因此无法消除死代码 而*q=y对任意变量赋值，因此杀死了全部其他结点 可以通过(全局/局部)指针分析部分解决这个问题； 过程调用也类似，必须安全地假设它 使用了可访问范围内的所有变量 修改了可访问范围内的所有变量 从DAG到基本块 重构的方法 每个结点构造一个三地址语句，计算对应的值 结果应该尽量赋给一个活跃的变量 如果结点有多个关联的变量，则需要用复制语句进行赋值。 重组基本块的例子 根据DAG构造是结点产生的顺序 a=b+c d=a-d b=d c=d+c 重组的规则 重组时应该注意求值的顺序 指令的顺序必须遵守DAG中结点的顺序 对数组的赋值必须跟在所有原来在它之前的赋值/求值操作之后 对数组元素的求值必须跟在所有原来在它之前的赋值指令之后 对变量的使用必须跟在所有原来在它之前的过程调用和指针间接赋值之后 任何过程调用或者指针间接赋值必须跟在原来在它之前的变量求值之后。 总的来说，我们必须保证：如果两个指令之间可能相互影响，那么他们的顺序就不应该改变。 代码生成器 根据三地址指令序列生成机器指令 假设：每个三地址指令只有一个对应的机器指令 有一组寄存器用于计算基本块内部的值； 主要的目标是尽量减少加载和保存指令，即最大限度利用寄存器； 寄存器的使用方法 执行运算时，运算分量必须放在寄存器中； 用于临时变量 存放全局的值 进行运行时刻管理(比如：栈顶指针) 算法的基本思想的数据结构 依次考虑各三地址指令，尽可能把值保留在寄存器中，以减少寄存器/内存之间的数据交换 为一个三地址指令生成机器指令时， 只有当运算分量不在寄存器中时，才从内存载入； 尽量保证只有当寄存器中的值不被使用时，才把它覆盖掉。 数据结构：记录各个值对应的位置 寄存器描述符：跟踪各个寄存器都存放了哪些变量的当前值； 地址描述符：某个变量的当前值存放在哪个或哪些位置(包括内存位置和寄存器)上； 代码生成算法(1) 重要子函数：getReg(I) 根据寄存器描述符和地址描述符、数据流信息，为三地址指令I选择最佳的寄存器； 得到的机器指令的质量依赖于getReg函数选取寄存器的算法； 代码生成算法逐个处理三地址指令 代码生成算法(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=y getReg(x=y)总是为x和y选择相同的寄存器 如果y不在Ry中，生成机器指令LD Ry, y 基本块的收尾 如果变量x在出口处活跃，且x现在不在内存，那么生成指令ST x, Rx。 代码生成算法(3) 代码生成同时更新寄存器和地址描述符 处理普通指令时生成LD R x R的寄存器描述符：只包含x x的地址描述符：R作为新位置加入到x的位置集合中 从任何不同于x的变量的地址描述符中删除R ST x, R 修改x的地址描述符，包含自己的内存位置 代码生成算法(4) ADD Rx, Ry, Rz Rx的寄存器描述符只包含x x的地址描述符只包含Rx(不包含x的内存位置！) 从任何不同于x的变量的地址描述符中删除Rx。 处理x=y时， 如果生成LD Ry y，按照第一个规则处理； 把x加入到Ry的寄存器描述符中(Ry存放了x和y的当前值)； 修改x的地址描述符，使它只包含