编译原理第13章-目标代码生成及代码优化基础.pptx

; 基本块、流图和循环; 二者在编译程序中的逻辑位置;基本块、流图和循环;;;;;;;;;;;;;;; 到达-定值数据流分析;;;;;;;;;;;; 活跃变量数据流分析; 数据流方程求解算法（对n个结点的流图）;;;;;;;;;;;;; 计算基本块内变量的待用信息和活跃信息 从基本块出口到入口对每个TAC 语句 i: A:=B op C 依 次执行下述步骤： a) 把变量A的待用信息和活跃信息附加到 TAC 语句 i 上； b) 把变量A的待用信息栏和活跃信息栏分别置为“非待用”和“非活跃” （由于在 i 中对 A 的定值只能在 i 以后的TAC 语句才能引用，因 而对i 以前的TAC 语句来说 A 是不活跃也不可能是待用的） c) 把变量 B 和 C 的待用信息和活跃信息附加到 TAC 语句 i 上 d) 把变量 B 和 C 的待用信息栏置为“i” ，活跃信息栏置为 “活跃”。 注：以上a), b), c), d）的次序不能颠倒。; 计算基本块内变量的待用信息和活跃信息 举例 若用 A，B，C，D 表示变量，用 T，U，V 表示中间变量， 设有TAC 语句构成的如下基本块： T:=A-B U:=D-C V:=T+U D:=V+U 其名字表中的待用信息和活跃信息见下页的表中，用“F”表示“非 待用” 以及 “非活跃”，用 “L” 表示活跃 (1)，(2)，(3)，(4)表示TAC 语句序号;（接上页）;;;; 基本块 DAG 表示的构造; 基本块 DAG 表示的构造; 基本块 DAG 表示的构造; 基本块 DAG 表示的构造; 基本块 DAG 表示的构造; 基本块 DAG 表示的构造; 基本块 DAG 表示的构造; 基本块 DAG 表示的构造; 基本块 DAG 表示的构造; 基本块 DAG 表示的构造; 基本块 DAG 表示的构造; 基本块 DAG 表示的构造; 基本块 DAG 表示的构造; 基本块 DAG 表示的构造; 从基本块的 DAG 表示可得到等价的基本块; 从基本块的 DAG 表示可得到等价的基本块;;;;;;;; 一个简单的代码生成算法; 一个简单的代码生成算法; 一个简单的代码生成算法; 一个简单的代码生成算法; 一个简单的代码生成算法; 一个简单的代码生成算法举例; 高效使用寄存器;;;;; 表达式树的求值 Ershov 数：表达式求值时所??寄存器数目的最小值; 表达式树的求值 Sethi-Ullman算法; 简单的图着色物理寄存器分配算法; 基于寄存器相干图（register-interference graph） 的图着色寄存器分配算法 构造寄存器相干图 结点：每一个伪寄存器为一个结点 边：如果程序中存在某点，一个结点在该点被定义， 而另一个结点在该点是活跃的，则在这两个结 点间连一条边 对相干图进行着色（coloring） 使用k（物理寄存器数量）种颜色对相干图进行着色， 使任何相邻的结点具有不同的颜色（即两个相干的 伪寄存器不会分配到同一个物理寄存器）; 基于寄存器相干图; 一种启发式图着色算法 “一个图是否能用 k 种颜色着色”是 NP-完全问题 以下是一个简单的启发式 k-着色算法： 假设图 G 中某个结点 n 的度数小于 k，从G 中删除 n 及其邻边得到图 G’，对 G 的k-着色问题可转化为 先对G’ k-着色，然后给结点 n 分配一个其相邻结点 在 G’ 的k-着色中没有使用过的颜色 重复这个过程从图中删除度数小于 k 的结点，如果 可以到达一个空图，说明对原图可以成功实现 k-着 色；否则，原图不能成功实现 k-着色，可从 G 中选 择某个结点作为泄露候选，将其删除，算法可继续;;;;;;;;;;;;;;;;;;;代码优化技术;;