《8编译原理之代码生成.ppt

8.5 基本块的几种优化 一个基本块可用一个DAG图表示(基本的DAG图) 每个变量对应于一个结点，表示初始值 每条语句s有一个相关结点N,具有 子结点：对应于其它语句,是在s之前，最后一个对s所使用的某个运算分量进行定值的语句。 标记：s的运算符 附加标记：一组变量，表明s是在此基本块内最晚对该变量定值 某些输出结点：结点对应的变量在基本块出口处活跃 （出口活跃属于全局数据流分析） DAG示例 语句S的结点N和子结点 s运算符当结点标记 附加标记 变量的结点 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. DAG图的构造 为基本块中出现的每个变量建立结点（表示基本值） 顺序扫描各个三地址指令 如果指令为x=y op z 为这个指令建立结点N，标号为op； N的子结点为y、z当前关联的结点； X和N关联； 如果指令为x=y； 不建立新结点； 设y关联到N，那么x现在也关联到N 扫描结束后，对于所有在出口处活跃的变量x，将x所关联的结点设置为输出结点 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. DAG的作用 DAG图描述了基本块运行时各个值之间的关系。 可以DAG为基础，对代码进行转换 消除局部公共子表达式 消除死代码 对语句重新排序 重新排序运算分量的顺序 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 局部公共子表达式 局部公共子表达式的发现 建立某个结点M之前，首先检查是否存在一个结点N，它和M具有相同的运算符和子结点（顺序相同）。 如果存在，则不需要生成新的结点，用N代表M； 例如： a=b+c b=a-d c=b+c d=a-d 找出公共的表达式？ 注意：两个b+c实际上并不是公共子表达式 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 消除死代码 在DAG图上消除没有附加活跃变量的根结点（没有父结点的结点），即可消除死代码 如果图中c、e不是活跃变量，则可以删除标号为e、c的结点。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. DAG方法的不足 为了计算第四式的e值，而有的2,3式实际上是冗余的，也就是第一式和第四式等价。该代码本可优化，但发现不了 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 在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 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 数组引用－避免误优化 注意：a[j]可能改变a[i]的值，因此不能和普通的运算符一样构造相应的结点 x=a[i] a[j]=y z=a[i] 从数组取值的运算x=a[i]对应于“=[]”的结点，x作为这个结点的标号之一； 对数组赋值的运算对应于 “[]=”的结点；没有关联的变量、且杀死所有依赖于a的变量；Killed节点不能成为公共子表达式 杀手 被杀者 杀手 引入新的运算符 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 数组引用的DAG的例子 b=12+a x=b[i