全局数据流分析 ■数据流的“方向” 反向(向后)数据流:与控制流方向相逆 ↓↓ NB]由OUT[B]来计算 基本块B OUT[B]则由B的所有后继结 点的N来决定 表示数据流信息交汇(合流)处 后继1 后继2 —→控制流 2021/2/11 数握 理与技术》之代码优化 6
2021/2/11 《编译原理与技术》之代码优化 6 •全局数据流分析 数据流的“方向” － 反向（向后）数据流：与控制流方向相逆 － IN[B]由OUT[B] 来计算 － OUT [B]则由B的所有后继结 点的IN来决定 控制流 数据流 基本块B 后继1 后继2 表示数据流信息交汇（合流）处
全局数据流分析 向前流 向后流 OUT[B]= GEN[B] U(INBI-KILLIBI) B]= GEN[B] U(OUT[BI-KILL[BD) 任意 路径NB= UOUTIPI, PEEred OUT[B]= U INS, SE Succ(B) OUTB=GENB]∪( NB]KILL[B)NB]=GENB]∪( OUT[BKILL[B 全路径 INB]=∩oUTP],P∈Pred(B) OUTB]=∩NS],S∈succ(B) 表1.数据流分析方程 2021/2/11 《编译原理与技术》之代码优化 7
2021/2/11 《编译原理与技术》之代码优化 7 •全局数据流分析 向前流 向后流 任意 路径 OUT[B] = GEN[B] ∪ (IN[B]-KILL[B]) IN[B] = ∪OUT[P] , P∈Pred(B) IN[B] = GEN[B] ∪(OUT[B]-KILL[B]) OUT[B] = ∪IN[S] , S∈Succ(B) 全路径 OUT[B] = GEN[B] ∪(IN[B]-KILL[B]) IN[B] = ∩OUT[P] , P∈Pred(B) IN[B] = GEN[B] ∪(OUT[B]-KILL[B]) OUT[B] = ∩IN[S] , S∈Succ(B) 表1. 数据流分析方程
仝局数据流方程求解 迭代计算:直至某先后两次迭代计算结果一样 迭代次序 向前流:流图深度优先次序 向后流:流图深度优先次序的逆序 流图深度优先次序: 对流图进行深度优先遍历,得到流图深度 优先扩展树;对该树进行前序遍历时最后 访问结点的逆序 迭代初始计算(值) 2021/2/11 《编译原理与技术》之代码优化 8
2021/2/11 《编译原理与技术》之代码优化 8 •全局数据流方程求解 迭代计算：直至某先后两次迭代计算结果一样 迭代次序 － 向前流：流图深度优先次序 － 向后流：流图深度优先次序的逆序 － 流图深度优先次序： － 对流图进行深度优先遍历，得到流图深度 优先扩展树；对该树进行前序遍历时最后 访问结点的逆序 迭代初始计算（值）
3 4 5 8 8 10 eg深度优先扩 展树 eg.一个流图 前序遍历: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 2021/2/11 《编译原理与技术》之代码优化 9
2021/2/11 《编译原理与技术》之代码优化 9 1 2 3 4 5 6 7 8 9 10 e.g. 一个流图 1 2 3 4 6 7 8 10 9 5 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
全局数据流方程求解 向前流 向后流 问题 初始值 问题 初始值 任意到达定值/链 活跃变量 路径未初始化变量所有变量 du链 全路可用表达式 0非常忙表达式0 径 复写传播 表2.常用的数据流分析 2021/2/11 《编译原理与技术》之代码优化 10
2021/2/11 《编译原理与技术》之代码优化 10 •全局数据流方程求解 向前流 向后流 问题 初始值 问题 初始值 任意 路径 到达-定值/ud链 ∅ 活跃变量 ∅ 未初始化变量 所有变量 du链 ∅ 全路 径 可用表达式 ∅ 非常忙表达式 ∅ 复写传播 ∅ 表2. 常用的数据流分析