8个编译器代码生成代码.ppt

代数化简/强度消减 应用代数恒等式进行优化 消除x=x+0 x=x*1 x*x替换x2 使用机器特有指令 INC，DEC，… 8.8 寄存器分配与指派 目的：有效利用寄存器； 简单的基本方法：把特定类型的值分配给特定的寄存器 数组基地址指派给一组寄存器 算术计算分配给一组寄存器 栈顶指针分配一个寄存器 。。。 缺点：寄存器的使用效率较低 * 调用序列中3个常量加2条指令，共5个字，20个字节 8.5 基本块的几种优化 一个基本块可用一个DAG图表示(基本的DAG图) 每个变量对应于一个结点，表示初始值 每条语句s有一个相关结点N,具有 子结点：对应于其它语句,是在s之前，最后一个对s所使用的某个运算分量进行定值的语句。 标记：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的作用 DAG图描述了基本块运行时各个值之间的关系。 可以DAG为基础，对代码进行转换 消除局部公共子表达式 消除死代码 对语句重新排序 重新排序运算分量的顺序 局部公共子表达式 局部公共子表达式的发现 建立某个结点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-0=x x*1=1*x=x x/1=x 降低计算强度 X2=x*x 2*x=x+x 常量合并 2*3.14可以用6.28替换 实现这些优化时，只需要在DAG图上寻找特定的模式56 数组引用－避免误优化 注意：a[j]可能改变a[i]的值，因此不能与普通的运算符一样构造相应的结点 x=a[i] a[j]=y z=a[i] 从数组取值的运算x=a[i]对应于“=[]”的结点，x作为这个结点的标号之一； 对数组赋值的运算对应于 “[]=”的结点；没有关联的变量、且杀死所有依赖于a的变量；Killed节点不能成为公共子表达式 杀手 被杀者 杀手 引入新的运算符 数组引用的DAG的例子 b=12+a x=b[i] b[j]=y 注意a是被杀死结点的孙结点。 x 如果没有杀手的出现则被杀者本可以象前述一样进行优化。 杀死的意思－－指不能参加优化 指针赋值/过程调用 通过指针进行取值/赋值：x=*p *q=y。最粗略地估计： x使用了任意变量，因此无法消除死代码 而*q=y对任意变量赋值，因此杀死了全部其他结点(可类似引出新的运算符“=*”与“*=”帮助分析) 杀的范围过大。可以通过（全局/局部）指针分析,缩小范围；比如针对 p=x *p=y可以只杀死那些以x为附加变量的结点 过程调用也类似，为了安全： 必须假设它使用了访问范围内所有变量 假设修改了访问范围内的所有变量 。杀谁？ 全杀 !! 从DAG到基本块 重构的方法 对每个结点构造一个三地址语句来计算对应的值 结果应该尽量赋给一个活跃的变量 一般为出口活跃，如果不确定则假设所有非临时变量都出口活跃 如果结点有多个关联的变量，则需要用复制语句进行赋值。 重组基本块的例子 原三地址码 a=b+c b=a-d c=b+c d=a-d 根据DAG构造是结点产生的顺序 a=b+c d=a-d b=d c=d+c 重组的规则 重组时应该注意求值的顺序 指令的顺序必须遵守DAG中结点的顺序 对数组的赋值必须跟在所有原来在它之前的赋值/ 求值操作之后。 对数组元素的求值必须跟在所有原来在它之前的赋值指令之后 对变量的使用必须跟在所有原来在它之前的过程调 用与指针间接赋值之后 任何过程调用或者指针间接赋值必须跟在原来在它 之前的变量求值之后。 总的来说，必须保证：如果两个指令之间可能相互影响，那么它们的顺序