编译 第八节 代码生成.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 优化应用的时间 优化可以在编译的每阶段分别执行。一般将完成主要的优化工作。 中间代码生成时的优化 优化用来转换语法树本身，其中某些子树被删除或替换为简单的子树 中间代码生成后的优化 对很多优化而言，语法树不适合收集信息及实现优化，优化将在中间代码上实现 目标代码生成时 优化依赖于目标机器结构 优化应用的范围 可分为: 局部优化 全局优化 过程间优化 局部优化 局部优化是应用于代码的线性部分, 即, 代码中没有跳进或跳出语句 一个最大的线性代码序列被称为 基本块 局部优化是在基本块中的优化。 全局优化 全局优化是扩展超出基本块，但是限制在单个过程中的优化 过程间优化 过程间优化是扩展出过程边界到整个程序的优化 8.4.3 优化的数据结构和实现技术 优化的两种数据结构 流图 流图是执行全局优化的过程中间代码的图形表示 DAG(无环有向图) DAG 是为每个基本块构造的，执行局部优化的无环有向图 1 流图 流图用于表示每个过程代码的全局信息 流图的结点是基本块 边是条件转或无条件转 (目的是作为其他基本块的开始) 流图的构造 A flow graph, together with each of its basic blocks, can be constructed by a single pass over the intermediate code. Each new basic block is identified as follows: The first instruction begins a new basic block Each label that is the target of a jump begins a new basic block Each instruction that follows a conditional jump begins a new basic block (1) read X (2) read Y (3) R=X mod Y (4) if R=0 goto (8) (5) X=Y (6) Y=R (7) goto (3) (8) write Y (9) halt 流图 三地址码 read X read Y R:=X mod Y if R=0 goto (8) X:=Y Y:=R goto (3) write Y halt read X R:=X mod Y X:=Y write Y 解释: 流图是数据流分析的主要数据结构，积累信息用于优化。 不同的信息要求对流图作不同处理，而且收集的信息各不相同，对应于不同的优化要求。 基本块的DAG DAG数据结构跟踪基本块中值和变量的计算和赋值 块中Leaf nodes are values that are used in 格的来自别处的值表示为叶子结点 值上的操作表示为内部结点 新值的赋值表示为将目标变量或临时变量的名字附加到表示赋值的结点上。 2 DAG(无环有向图) 例如 基本块 label L2 t2=fact*x fact=t2 t3=x-1 x=t3 t4=x==0 if_false t4 goto L2 这个基本块的DAG * - == fact x fact,t2 x,t3 1 0 t4 标记基本块的开始和最后的跳转一般不包括在DAG中。Labels at the beginning of basic blocks and jumps at the end are usually not included in the DAG 拷贝操作不生成新的结点，仅仅在表示拷贝值的结点处增加新标记 相同值的重复使用也在DAG中表示 DAG 的构造 轮流处理块中的每条语句 形如 x=y+z的语句 查找表示y和z的“当前”值的结点 若y 和 z 是常量, 则生成一个结点表示y+z 的结果值，并标记为结点x。若x和y已生成则删除该结点，否则生成一个标记为+，且两个孩子分别为y和z的结点，标记这个结点为+ 然而，若已经存在一个结点表示y+z相同的值，则我们不需要在DAG中增加新的结点，而只需要在已存在的结点处再标记x 需要注意三个细节 对于 x=y+z, 如果 y 和 z 是常数, 不需要生成为+的内部结点, 而执行 y+z (常量合并) 对于 x=y+z, 若已经有结点表示y