编译原理 代码优化2.ppt

代码优化 代码优化的目标 提高最终目标代码的运行效率 性能 时间 运行的更快 空间 降低内存需求保持源程序的语义 2020 4 8 编译原理与技术 之代码优化 3 代码优化 续 全局数据流分析技术 2020 4 8 编译原理与技术 之代码优化 4 全局数据流分析 基本块 in b out b kill b gen b 到达基本块入口处的相关数据流信息 到达基本块出口处的相关数据流信息 基本块 产生 的相关数据流信息 基本块 注销 的相关数据流信息 2020 4 8 编译原理与技术 之代码优化 5 全局数据流分析 数据流的 方向 正向 向前 数据流 与控制流方向一致 out b 由in b 来计算 in b 则由b的所有前驱结点的out来决定 控制流 数据流 前驱1 前驱2 基本块b 表示数据流信息交汇 合流 处 2020 4 8 编译原理与技术 之代码优化 6 全局数据流分析 数据流的 方向 反向 向后 数据流 与控制流方向相逆 in b 由out b 来计算 out b 则由b的所有后继结点的in来决定 控制流 数据流 基本块b 后继1 后继2 表示数据流信息交汇 合流 处 2020 4 8 编译原理与技术 之代码优化 7 全局数据流分析 表1 数据流分析方程 2020 4 8 编译原理与技术 之代码优化 8 全局数据流方程求解 迭代计算 直至某先后两次迭代计算结果一样迭代次序 向前流 流图深度优先次序 向后流 流图深度优先次序的逆序 流图深度优先次序 对流图进行深度优先遍历 得到流图深度优先扩展树 对该树进行前序遍历时最后访问结点的逆序迭代初始计算 值 2020 4 8 编译原理与技术 之代码优化 9 e g 一个流图 前序遍历 1 2 3 4 6 7 8 10 8 9 8 7 6 4 5 4 3 2 1深度优先次序 1 2 3 4 5 6 7 8 9 10 2020 4 8 编译原理与技术 之代码优化 10 全局数据流方程求解 表2 常用的数据流分析 2020 4 8 编译原理与技术 之代码优化 11 到达 定值数据流分析 定值与引用d x y z 语句d是变量x的一个定值点u w x v 语句u是变量x的一个引用点变量x在d点的定值到达u点 流图中有路径d u 且该路径上没有x的其它 无二义 定值 2020 4 8 编译原理与技术 之代码优化 12 到达 定值数据流分析 解决的问题 定值 传播 数据流归属 任意路径 向前流的数据流分析 in b 到达基本块入口处定值集合 out b 到达基本块出口处定值集合 gen b 基本块产生且能到达基本块出口的定值集合 kill b 由基本块注销的定值集合 这些定值不能传播或到达到块出口 数据流应用 ud链 即引用 定值链 可以据此判断基本块内的某变量引用 其值来自何方 定值 如应用于循环不变式的寻找 2020 4 8 编译原理与技术 之代码优化 13 out dm x out dn x 前驱1 前驱2 ds s x dt x du x in b out b 控制流 2020 4 8 编译原理与技术 之代码优化 14 out dm x out dn x 前驱1 前驱2 ds s x dt x du x in b out b 英雄惜英雄 dm和dn相会在汇流点 共赴in b 2020 4 8 编译原理与技术 之代码优化 15 out dm x out dn x 前驱1 前驱2 ds s x dt x du x in b out b dm和dn 一路无险遇ds 2020 4 8 编译原理与技术 之代码优化 16 out dm x out dn x 前驱1 前驱2 ds s x dt x du x in b out b dm和dn 再走一程见dt 2020 4 8 编译原理与技术 之代码优化 17 out dm x out dn x 前驱1 前驱2 ds s x dt x du x in b out b dm和dn 我们被dt所 屏蔽 不知何时上了 注销 榜 dt 你们歇着吧 我要gogogo 2020 4 8 编译原理与技术 之代码优化 18 out dm x out dn x 前驱1 前驱2 ds s x dt x du x in b out b dt 等等 我咋也上榜了 唉 既生t 何生u du 数 流 人 还看 2020 4 8 编译原理与技术 之代码优化 19 out dm x out dn x 前驱1 前驱2 ds s x dt x du x in b out b du 顺利过关 嗯 要是没有我和dt的阻击 现在站在这里的就是dm和dn 只可惜了dt 2020 4 8 编译原理与技术 之代码优化 20 到达 定值数据流分析 d1 i m 1d2 j nd3 a u1 d4 i i 1d5 j j 1 d6 a u2 d7 i u3 b1 b2 b3 b4 gen b1 d1 d2 d3 kill b1 d4 d5 d6 d7 gen b2 d4 d5 kill b2 d1 d2 d7 gen b3 d6 kill b3 d3 gen b4 d7 kill b5 d1 d4 例1 求解到达 定值的数据流图 2020 4 8 编译原理与技术 之代码优化 21 迭代计算 计算次序 深度优先序 即b1 b2 b3 b4 初始值 forallb in b out b gen b 第一次迭代 in b1 b1无前驱结点out b1 gen b1 in b1 kill b1 gen b1 d1 d2 d3 in b2 out b1 out b4 d1 d2 d3 d7 d1 d2 d3 d7 out b2 gen b2 in b2 kill b2 d4 d5 d3 d3 d4 d5 in b3 out b2 d3 d4 d5 out b3 d6 d3 d4 d5 d3 d4 d5 d6 in b4 out b3 out b2 d3 d4 d5 d6 out b4 d7 d3 d4 d5 d6 d1 d4 d3 d5 d6 d7 2020 4 8 编译原理与技术 之代码优化 22 第二次迭代in b1 b1无前驱结点out b1 gen b1 in b1 kill b1 gen b1 d1 d2 d3 in b2 out b1 out b4 d1 d2 d3 d3 d5 d6 d7 d1 d2 d3 d5 d6 d7 out b2 gen b2 in b2 kill b2 d4 d5 d3 d5 d6 d3 d4 d5 d6 in b3 out b2 d3 d4 d5 d6 out b3 d6 d3 d4 d5 d6 d3 d4 d5 d6 in b4 out b3 out b2 d3 d4 d5 d6 out b4 d7 d3 d4 d5 d6 d1 d4 d3 d5 d6 d7 经过第二次迭代后 in b 和out b 不再变化 2020 4 8 编译原理与技术 之代码优化 23 ud链 考察流图中变量i j的引用 定值情况 在基本块b2中有相应的引用 d4 i i 1 i 1中的i在引用前无定值 该引用的ud链仅来自于in b2 中i的有关定值集合 即 d1 i m 1 d7 i u3 类似地 d5 j j 1中的j引用 定值链为 d2 j n d5 j j 1 如果某变量引用前有定值 则该引用的ud链仅包含该变量的最后定值 2020 4 8 编译原理与技术 之代码优化 24 活跃变量分析 活跃变量d x 语句d是变量x的定值点 从d点开始的某条路径上 有该x值的引用 则称x在 d点活跃u x 2020 4 8 编译原理与技术 之代码优化 25 活跃变量分析 解决问题 在基本块出口处变量的活跃情况数据流归属 任意路径 向后流数据流分析数据流应用 无用赋值的删除 出口非活跃变量 无需存储 寄存器剥夺 2020 4 8 编译原理与技术 之代码优化 26 2020 4 8 编译原理与技术 之代码优化 27 x y 原来这里也有我们的身影哦 2020 4 8 编译原理与技术 之代码优化 28 y 我走不动了 逆 流 行船 累啊 x 坚持就是胜利 2020 4 8 编译原理与技术 之代码优化 29 x 又觅 活 踪 2020 4 8 编译原理与技术 之代码优化 30 x 终于出头啦 2020 4 8 编译原理与技术 之代码优化 31 活跃变量分析 1 a 1 2 b 2 b1 3 c a b 4 d c a b2 8 b a b 9 e c a b5 5 d b d b3 6 d a b 7 e e 1 b4 10 a b d 11 b a d b6 2020 4 8 编译原理与技术 之代码优化 32 基本块出口活跃变量 迭代计算out b in s s succ b in b use b out b def b use b 基本块b中有引用且该引用前无定值的变量集合 def b 基本块b中有定值且该定值前无引用的变量集合 计算次序 结点深度优先序的逆序 向后流 b6 b5 b4 b3 b2 b1 2020 4 8 编译原理与技术 之代码优化 33 基本块出口活跃变量 各基本块use和def如下 use b1 def b1 a b use b2 a b def b2 c d use b3 b d def b3 use b4 a b e def b4 d use b5 a b c def b5 e use b6 b d def b6 a 初始值 allb in b out b6 出口块 2020 4 8 编译原理与技术 之代码优化 34 基本块出口活跃变量 第一次迭代计算 1 a 1 2 b 2 b1 3 c a b 4 d c a b2 8 b a b 9 e c a b5 5 d b d b3 6 d a b 7 e e 1 b4 10 a b d 11 b a d b6 b d 2020 4 8 编译原理与技术 之代码优化 35 基本块出口活跃变量 第一次迭代计算 1 a 1 2 b 2 b1 3 c a b 4 d c a b2 8 b a b 9 e c a b5 5 d b d b3 6 d a b 7 e e 1 b4 10 a b d 11 b a d b6 b d b d a b c d 2020 4 8 编译原理与技术 之代码优化 36 基本块出口活跃变量 第一次迭代计算 1 a 1 2 b 2 b1 3 c a b 4 d c a b2 8 b a b 9 e c a b5 5 d b d b3 6 d a b 7 e e 1 b4 10 a b d 11 b a d b6 b d b d a b c d a b e 2020 4 8 编译原理与技术 之代码优化 37 基本块出口活跃变量 第一次迭代计算 1 a 1 2 b 2 b1 3 c a b 4 d c a b2 8 b a b 9 e c a b5 5 d b d b3 6 d a b 7 e e 1 b4 10 a b d 11 b a d b6 b d b d a b c d a b e a b c d e a b c d e 2020 4 8 编译原理与技术 之代码优化 38 基本块出口活跃变量 第一次迭代计算 1 a 1 2 b 2 b1 3 c a b 4 d c a b2 8 b a b 9 e c a b5 5 d b d b3 6 d a b 7 e e 1 b4 10 a b d 11 b a d b6 b d b d a b c d a b e a b c d e a b c d e a b c d e a b e 2020 4 8 编译原理与技术 之代码优化 39 基本块出口活跃变量 第一次迭代计算 1 a 1 2 b 2 b1 3 c a b 4 d c a b2 8 b a b 9 e c a b5 5 d b d b3 6 d a b 7 e e 1 b4 10 a b d 11 b a d b6 b d b d a b c d a b e a b c d e a b c d e a b c d e a b e a b e e 2020 4 8 编译原理与技术 之代码优化 40 基本块出口活跃变量 第二次迭代计算 1 a 1 2 b 2 b1 3 c a b 4 d c a b2 8 b a b 9 e c a b5 5 d b d b3 6 d a b 7 e e 1 b4 10 a b d 11 b a d b6 b d b d a b c d a b e a b c d e a b c d e a b c d e a b e a b e e 2020 4 8 编译原理与技术 之代码优化 41 基本块出口活跃变量 第二次迭代计算 1 a 1 2 b 2 b1 3 c a b 4 d c a b2 8 b a b 9 e c a b5 5 d b d b3 6 d a b 7 e e 1 b4 10 a b d 11 b a d b6 b d a b d e a b c d a b e a b c d e a b c d e a b c d e a b e a b e e 2020 4 8 编译原理与技术 之代码优化 42 基本块出口活跃变量 第二次迭代计算 1 a 1 2 b 2 b1 3 c a b 4 d c a b2 8 b a b 9 e c a b5 5 d b d b3 6 d a b 7 e e 1 b4 10 a b d 11 b a d b6 b d a b d e a b c d a b c d e a b c e a b c d e a b c d e a b c d e a b e a b e e 2020 4 8 编译原理与技术 之代码优化 43 基本块出口活跃变量 第二次迭代计算 1 a 1 2 b 2 b1 3 c a b 4 d c a b2 8 b a b 9 e c a b5 5 d b d b3 6 d a b 7 e e 1 b4 10 a b d 11 b a d b6 b d a b d e a b c d a b c d e a b c e a b c d e a b c d e a b c d e a b e a b e e