代码优化

代码优化的目标 提高最终目标代码的运行效率（性能） － 时间：运行的更快 － 空间：降低内存需求 保持源程序的语义

代码优化（续） － 全局数据流分析技术 2019/1/18 《编译原理与技术》之代码优化

全局数据流分析 基本块 IN[B] GEN[B] KILL[B] OUT[B] 到达基本块入口处的相关数据流信息 基本块“产生”的相关数据流信息 基本块 GEN[B] 基本块“注销”的相关数据流信息 KILL[B] 到达基本块出口处的相关数据流信息 OUT[B] 2019/1/18 《编译原理与技术》之代码优化

全局数据流分析 数据流的“方向” － 正向（向前）数据流：与控制流方向一致 － OUT[B]由IN[B]来计算 － IN[B]则由B的所有前驱结 点的OUT来决定 前驱1 前驱2 基本块B 表示数据流信息交汇（合流）处 控制流 数据流 2019/1/18 《编译原理与技术》之代码优化

全局数据流分析 数据流的“方向” － 反向（向后）数据流：与控制流方向相逆 － IN[B]由OUT[B] 来计算 － OUT [B]则由B的所有后继结 点的IN来决定 基本块B 表示数据流信息交汇（合流）处 后继1 后继2 控制流 数据流 2019/1/18 《编译原理与技术》之代码优化

全局数据流分析 向前流 向后流 任意 路径 全路径 表1. 数据流分析方程 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) OUT[B] = ∩IN[S] , S∈Succ(B) 表1. 数据流分析方程 2019/1/18 《编译原理与技术》之代码优化

全局数据流方程求解 迭代计算：直至某先后两次迭代计算结果一样 迭代次序 － 向前流：流图深度优先次序 － 向后流：流图深度优先次序的逆序 － 流图深度优先次序： － 对流图进行深度优先遍历，得到流图深度 优先扩展树；对该树进行前序遍历时最后 访问结点的逆序 迭代初始计算（值） 2019/1/18 《编译原理与技术》之代码优化

1 2 3 4 5 6 7 8 9 10 1 2 3 4 6 7 8 10 9 5 e.g.深度优先扩展树 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 2019/1/18 《编译原理与技术》之代码优化

全局数据流方程求解 向前流 向后流 问题 初始值 任意 路径 到达-定值/ud链 ∅ 活跃变量 未初始化变量 所有变量 du链 全路径 可用表达式 非常忙表达式 复写传播 表2. 常用的数据流分析 2019/1/18 《编译原理与技术》之代码优化

流图中有路径d---->u，且该路径上没有x的其它（无二义）定值。 到达－定值数据流分析 定值与引用 d : x := y + z // 语句d 是变量x的一个定值点 u : w := x + v // 语句u 是变量x的一个引用点 变量x在d点的定值到达u点 流图中有路径d---->u，且该路径上没有x的其它（无二义）定值。 2019/1/18 《编译原理与技术》之代码优化

到达－定值数据流分析 解决的问题 数据流归属 数据流应用 － 定值“传播” － 任意路径、向前流的数据流分析 － IN[B]，到达基本块入口处定值集合 － OUT[B]，到达基本块出口处定值集合 － GEN[B]，基本块产生且能到达基本块出口的定值集合 － KILL[B]，由基本块注销的定值集合（这些定值不能传播或到达到块出口） 数据流应用 － ud链，即引用－定值链。可以据此判断基本块内的某变量引用，其值来自何方（定值）。如应用于循环不变式的寻找。 2019/1/18 《编译原理与技术》之代码优化

前驱1 前驱2 OUT: dm : x:= … OUT: dn : x:= … IN[B] … ds : s := …x… dt : x := … du : x := … 控制流 OUT[B] = ? 2019/1/18 《编译原理与技术》之代码优化

英雄惜英雄，dm 和 dn相会在汇流点，共赴IN[B] 前驱1 前驱2 OUT: dm : x:= … OUT: dn : x:= … 英雄惜英雄，dm 和 dn相会在汇流点，共赴IN[B] IN[B] … ds : s := …x… dt : x := … du : x := … OUT[B] = ? 2019/1/18 《编译原理与技术》之代码优化

前驱1 前驱2 OUT: dm : x:= … OUT: dn : x:= … dm和dn ：一路无险遇 ds IN[B] … ds : s := …x… dt : x := … du : x := … OUT[B] = ? 2019/1/18 《编译原理与技术》之代码优化

前驱1 前驱2 OUT: dm : x:= … OUT: dn : x:= … dm和dn ：再走一程见 dt， ^_^ IN[B] … ds : s := …x… dt : x := … du : x := … OUT[B] = ? 2019/1/18 《编译原理与技术》之代码优化

dm和dn ：我们被dt所“屏蔽”。不知何时上了“注销”榜？ 前驱1 前驱2 OUT: dm : x:= … OUT: dn : x:= … IN[B] dm和dn ：我们被dt所“屏蔽”。不知何时上了“注销”榜？ dt : 你们歇着吧。我要 Go Go Go … ds : s := …x… dt : x := … du : x := … OUT[B] = ? 2019/1/18 《编译原理与技术》之代码优化

dt：等等，我咋也上榜了？唉，既生t，何生u? 前驱1 前驱2 OUT: dm : x:= … OUT: dn : x:= … IN[B] … ds : s := …x… dt : x := … du : x := … dt：等等，我咋也上榜了？唉，既生t，何生u? du：数“流”人，还看… OUT[B] = ? 2019/1/18 《编译原理与技术》之代码优化

du : 顺利过关。嗯，要是没有我和dt的阻击，现在站在这里的就是dm和dn。 前驱1 前驱2 OUT: dm : x:= … OUT: dn : x:= … IN[B] … ds : s := …x… dt : x := … du : x := … du : 顺利过关。嗯，要是没有我和dt的阻击，现在站在这里的就是dm和dn。 只可惜了dt … OUT[B] = ? 2019/1/18 《编译原理与技术》之代码优化

到达－定值数据流分析 d1: i := m-1 d2: j := n d3: a := u1 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 } B1 d4: i := i +1 d5: j := j - 1 B2 B3 d6: a := u2 B4 d7: i := u3 例1. 求解到达－定值的数据流图 2019/1/18 《编译原理与技术》之代码优化

－ 计算次序，深度优先序，即 B1 -> B2 -> B3 -> B4 迭代计算 － 计算次序，深度优先序，即 B1 -> B2 -> B3 -> B4 － 初始值：for all B: 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 } 2019/1/18 《编译原理与技术》之代码优化

经过第二次迭代后，IN[B]和OUT[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 } ∪ { 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] 不再变化。 2019/1/18 《编译原理与技术》之代码优化

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链仅包含该变量的最后定值 2019/1/18 《编译原理与技术》之代码优化

活跃变量分析 活跃变量 d : x := … // 语句d是变量x的定值点 // 从d点开始的某条路径上 // 有该x值的引用，则称x在 u : := … x … 2019/1/18 《编译原理与技术》之代码优化

活跃变量分析 解决问题 － 在基本块出口处变量的活跃情况 数据流归属 － 任意路径、向后流数据流分析 数据流应用 － 无用赋值的删除 － 出口非活跃变量（无需存储、寄存器剥夺） 2019/1/18 《编译原理与技术》之代码优化

dm : := … x … dn : y := … 后继1 后继2 x活跃 y活跃 OUT[B] IN[B] 2019/1/18 《编译原理与技术》之代码优化

dm : := … x … dn : y := … 后继1 后继2 x活跃 y活跃 OUT[B] IN[B] 2019/1/18 《编译原理与技术》之代码优化

dm : := … x … dn : y := … 后继1 后继2 x活跃 y活跃 OUT[B] IN[B] 2019/1/18 《编译原理与技术》之代码优化

dm : := … x … dn : y := … 后继1 后继2 x活跃 y活跃 OUT[B] IN[B] x : 又觅“活”踪 2019/1/18 《编译原理与技术》之代码优化

x : 终于出头啦！ dm : := … x … dn : y := … 后继1 后继2 x活跃 y活跃 OUT[B] IN[B] 2019/1/18 《编译原理与技术》之代码优化

活跃变量分析 (1) a := 1 B1 (2) b := 2 (3) c := a + b B2 (4) d := c – a B3 (5) d := b * d (8) b := a + b (9) e := c – a B5 (6) d := a + b (7) e := e + 1 B4 (10) a := b * d (11) b := a – d B6 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 迭代计算 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 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 各基本块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 } 初始值，all B, IN[B] = { }, OUT[B6]={ }//出口块 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 第一次迭代计算 (1) a := 1 (2) b := 2 B1 (3) c := a + b (4) d := c – a B2 B3 (5) d := b * d (8) b := a + b (9) e := c – a B5 (6) d := a + b (7) e := e + 1 B4 { b, d } (10) a := b * d (11) b := a – d B6 { } 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 第一次迭代计算 (1) a := 1 (2) b := 2 B1 (3) c := a + b (4) d := c – a B2 B3 (5) d := b * d { a,b,c,d } (8) b := a + b (9) e := c – a B5 { b, d } (6) d := a + b (7) e := e + 1 B4 { b, d } (10) a := b * d (11) b := a – d B6 { } 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 第一次迭代计算 (1) a := 1 (2) b := 2 B1 (3) c := a + b (4) d := c – a B2 B3 (5) d := b * d { a,b,c,d } (8) b := a + b (9) e := c – a B5 { a,b,e } { b, d } (6) d := a + b (7) e := e + 1 B4 { b, d } (10) a := b * d (11) b := a – d B6 { } { } 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 第一次迭代计算 (1) a := 1 (2) b := 2 B1 (3) c := a + b (4) d := c – a B2 { a,b,c,d,e } B3 (5) d := b * d { a,b,c,d } { a,b,c,d,e } (8) b := a + b (9) e := c – a B5 { a,b,e } { b, d } (6) d := a + b (7) e := e + 1 B4 { b, d } (10) a := b * d (11) b := a – d B6 { } { } 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 第一次迭代计算 (1) a := 1 (2) b := 2 B1 { a,b,e } (3) c := a + b (4) d := c – a B2 { a,b,c,d,e } { a,b,c,d,e } B3 (5) d := b * d { a,b,c,d } { a,b,c,d,e } (8) b := a + b (9) e := c – a B5 { a,b,e } { b, d } (6) d := a + b (7) e := e + 1 B4 { b, d } (10) a := b * d (11) b := a – d B6 { } { } 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 第一次迭代计算 { e } (1) a := 1 (2) b := 2 B1 { a,b,e } { a,b,e } (3) c := a + b (4) d := c – a B2 { a,b,c,d,e } { a,b,c,d,e } B3 (5) d := b * d { a,b,c,d } { a,b,c,d,e } (8) b := a + b (9) e := c – a B5 { a,b,e } { b, d } (6) d := a + b (7) e := e + 1 B4 { b, d } (10) a := b * d (11) b := a – d B6 { } { } 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 第二次迭代计算 { e } (1) a := 1 (2) b := 2 B1 { a,b,e } { a,b,e } (3) c := a + b (4) d := c – a B2 { a,b,c,d,e } { a,b,c,d,e } B3 (5) d := b * d { a,b,c,d } { a,b,c,d,e } (8) b := a + b (9) e := c – a B5 { a,b,e } { b, d } (6) d := a + b (7) e := e + 1 B4 { b, d } (10) a := b * d (11) b := a – d B6 { } { } 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 第二次迭代计算 { e } (1) a := 1 (2) b := 2 B1 { a,b,e } { a,b,e } (3) c := a + b (4) d := c – a B2 { a,b,c,d,e } { a,b,c,d,e } B3 (5) d := b * d { a,b,c,d } { a,b,c,d,e } (8) b := a + b (9) e := c – a B5 { a,b,e } { a,b,d,e } (6) d := a + b (7) e := e + 1 B4 { b, d } (10) a := b * d (11) b := a – d B6 { } { } 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 第二次迭代计算 { e } (1) a := 1 (2) b := 2 B1 { a,b,e } { a,b,e } (3) c := a + b (4) d := c – a B2 { a,b,c,d,e } { a,b,c,d,e } B3 (5) d := b * d { a,b,c,d } { a,b,c,d,e } (8) b := a + b (9) e := c – a B5 { a,b,c,e } { a,b,d,e } (6) d := a + b (7) e := e + 1 B4 { b, d } (10) a := b * d (11) b := a – d B6 { a,b,c,d,e } { } 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 第二次迭代计算 { e } (1) a := 1 (2) b := 2 B1 { a,b,e } { a,b,e } (3) c := a + b (4) d := c – a B2 { a,b,c,d,e } { a,b,c,d,e } B3 (5) d := b * d { a,b,c,d } { a,b,c,d,e } (8) b := a + b (9) e := c – a B5 { a,b,c,e } { a,b,d,e } (6) d := a + b (7) e := e + 1 B4 { b, d } (10) a := b * d (11) b := a – d B6 { a,b,c,d,e } { } 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 第二次迭代计算 { e } (1) a := 1 (2) b := 2 B1 { a,b,e } { a,b,e } (3) c := a + b (4) d := c – a B2 { a,b,c,d,e } { a,b,c,d,e } B3 (5) d := b * d { a,b,c,d } { a,b,c,d,e } (8) b := a + b (9) e := c – a B5 { a,b,c,e } { a,b,d,e } (6) d := a + b (7) e := e + 1 B4 { b, d } (10) a := b * d (11) b := a – d B6 { a,b,c,d,e } { } 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 第二次迭代计算 { e } (1) a := 1 (2) b := 2 B1 { a,b,e } { a,b,e } (3) c := a + b (4) d := c – a B2 { a,b,c,d,e } { a,b,c,d,e } B3 (5) d := b * d { a,b,c,d } { a,b,c,d,e } (8) b := a + b (9) e := c – a B5 { a,b,c,e } { a,b,d,e } (6) d := a + b (7) e := e + 1 B4 { b, d } (10) a := b * d (11) b := a – d B6 { a,b,c,d,e } { } 2019/1/18 《编译原理与技术》之代码优化

基本块出口活跃变量 第三次迭代与前一次 结果一样，计算结束 (1) a := 1 B1 (2) b := 2 { a,b,e } (3) c := a + b (4) d := c – a B2 { a,b,c,d,e } B3 (5) d := b * d { a,b,c,d,e } (8) b := a + b (9) e := c – a B5 { a,b,d,e } (6) d := a + b (7) e := e + 1 B4 (10) a := b * d (11) b := a – d B6 { a,b,c,d,e } { } 2019/1/18 《编译原理与技术》之代码优化

2019/1/18 《编译原理与技术》之代码优化

可用表达式数据流分析 如果从流图入口结点到达程序点p的每一条路径上均对表达式x+y求值，且每条路径上最后一个这样的求值之后到p点的路径上没有对x或y赋值，那么称x+y在点p可用（available）。 显然，可用表达式分析属于 全路径数据流问题。 ENTRY u = x + y u = x + y u = x + y p

可用表达式数据流分析 数据流应用：寻找公共子表达式。如果在基本块中需要计算某个表达式，而此表达式恰好在其入口处可用，且这之间该表达式的值未被修改，则基本块中无需再计算此表达式。 数据流值域：全体（右值）表达式集合U的幂集 数据流方向： 全路径、前向数据流分析 传递函数： －语义约束与控制流约束 －首先，考察基本块中单个语句的语义约束，其次，推广到整个基本块（所有语句），最后考察基本块之间的约束关系。

可用表达式数据流分析 基本块语义传递函数 －e_genB：基本块B生成的表达式集合；如果基本块B对表达式x+y求值，且之后未对变量x或y重新定值，那么称基本块B生成表达式x+y。 －e_killB：被基本块B注销的表达式集合；如果基本块B中对变量x或y进行定值，且之后没有重新计算x+y，那么称基本块B杀死（或注销）了表达式x+y。 －IN[B]：基本块B入口点处可用表达式集。显然，在基本块B的每一个前驱块P的出口点处可用的表达式也将在B的入口点处可用。 －OUT[B]：基本块B出口点处可用表达式集。

基本块生成的表达式： 基本块中语句d：x = y + z的前、后点分别为点p与点q。设在点p处可用表达式集合为S（基本块入口点处S为空集），那么经过语句d之后，在点q处可用表达式集合如下构成： (1) S = S  { y+z } (2) S = S – { S 中所有涉及变量x的表达式 } 注意，步骤(1)和(2)不可颠倒，x可能就是y或z。 如此处理完基本块中所有语句后，可以得到基本块生成的可用表达式集合S； 基本块杀死的表达式：所有其他类似y+z的表达式，基本块中对y或z定值，但基本块没有生成y+z。

示例：基本块生成的表达式 语句 可用表达式 Ø a = b + c { b + c } b = a – d { a – d } // b+c被杀死 c = b + c d = a – d Ø // a – d 被杀死

可用表达式数据流分析 传递方程： IN[B] =  P是B的前驱基本块(OUT[P]) OUT[B] = e_genB  ( IN[B] – e_killB ) 边界值：OUT[ENTRY] = ø；程序开始，无可用表达式！ 迭代算法： (1) OUT[ENTRY] = ø (2) for( 除ENTRY之外的每个基本块B) OUT[B]= U (3) while(某个OUT值发生变化) { (4) for(除ENTRY之外的每个基本块B ){ (5) IN[B] =  P是B的前驱基本块(OUT[P]) (6) OUT[B] = e_genB  ( IN[B] – e_killB ) } // end-of-for } // end-of-while

在可用表达式分析中，适宜将OUT的初值置为全体 表达式集合U而不是空集。令G和K为基本块B2 的生成与注销表达式集合，则： IN[B2] = OUT[B1] OUT[B2] OUT[B2] = G(IN[B2] – K ) 令Ij和Oj分别为B2在第j次迭代中 IN和OUT值；则： I j+1 = OUT[B1]  O j O j+1 = G  ( I j+1 – K ) 如果由O0 = ø开始，I1 = OUT[B1]  O 0 = ø 。 但从O0 = U开始，则I1 = OUT[B1]  O 0 = OUT[B1]， 事实上，如果OUT[B1]中某个表达式没有被B2注销， 则它在B2的出口处可用。这正是我们所希望的！ B1 B2

示例：可用表达式 ENTRY (1) D = 3 (2) G = 1 B1 (3) B ＝ D + D C = D * D A ＝ B＋ C B ＝ B + C F = A + G C ＝ B + C F = A * A B3 B4 G ＝ B + C D = D * D B5 EXIT

示例：可用表达式 基本块 前驱 后继 ENTRY － B1 ENRTY B2 B1 B5 B3 B4 B3 B5 B4 B2 EXIT

示例：可用表达式 基本块 e_gen e_kill ENTRY Ø B1 {3 1} { D+D, D*D, A+G } B2 {3 1} { D+D, D*D, A+G } B2 { D+D, D*D, B+C } { A*A, A+G } B3 { A+G } { B+C } B4 { A * A } B5 { A+G, D*D, D+D } EXIT 全部表达式U={ 3, 1, D+D, D*D, B+C, A+G, A*A }

第一次迭代：(all NON-ENTRY B) 可用表达式的迭代计算 － 计算次序，深度优先序， 即 B1 -> B2 -> B3 -> B4 -> B5 -> EXIT － 边界值：OUT[ENTRY] = ∅; －初始化：for all NON-ENTRY B: OUT[B] ＝ U ； 第一次迭代：(all NON-ENTRY B) (1) IN[B1] = OUT[ENTRY] = ∅; // B1 前驱仅为ENTRY OUT[B1] = e_GEN[B1] ∪( IN[B1] – e_KILL[B1] ) = e_GEN[B1] = { 3, 1 } //变化 (2) IN[B2] = OUT[B1] ∩OUT[B5] = { 3, 1 } ∩ U = { 3, 1 } OUT[B2] = e_GEN[B2] ∪( IN[B2] – KILL[B2] ) = { D+D, D*D, B+C } ∪ ({ 3, 1 } – {A*A, A+G }) = {3, 1, D+D, D*D, B+C } //变化

第一次迭代：(all NON-ENTRY B) (3) IN[B3] = OUT[B2] = {3, 1, D+D, D*D, B+C } OUT[B3] = e_gen[B3] ∪ ( IN[B3] – e_kill[B3] ) = { A+G } ∪ ( { 3, 1, D+D, D*D, B+C } – { B+C } ) = { 3, 1, D+D, D*D, A+G } //变化 (4) IN[B4] = OUT[B2] OUT[B4] = e_gen[B4] ∪ ( IN[B4] – e_kill[B4] ) = { A * A } ∪( { 3, 1, D+D, D*D, B+C } – { B+C } ) = { 3, 1, D+D, D*D, A * A } //变化

第一次迭代：(all NON-ENTRY B) (5) IN[B5] = OUT[B3] ∩OUT[B4] = { 3, 1, D+D, D*D, A+G } ∩ { 3, 1, D+D, D*D, A * A } = { 3, 1, D+D, D*D } OUT[B5] = e_gen[B5] ∪ ( IN[B5] – e_kill[B5] ) = {B+C}∪({3,1,D+D, D*D} – {A+G, D*D, D+D}) = { 3, 1, B+C } //变化 (6) IN[EXIT] = OUT[B5] = { 3, 1, B+C } OUT[EXIT] = e_GEN[EXIT] ∪ (IN[EXIT] –e_KILL[EXIT]) = ∅ ∪ ({ 3, 1, B+C } – ∅ ）

第二次迭代：(all NON-ENTRY B) (1) IN[B1] = OUT[ENTRY] = ∅; OUT[B1] = e_GEN[B1] ∪( IN[B1] – e_KILL[B1] ) = e_GEN[B1] = { 3, 1 } // 不变 (2) IN[B2] = OUT[B1] ∩ OUT[B5] = { 3, 1 } ∩ { 3, 1, B+C } = { 3, 1 } // 不变 OUT[B2] = e_GEN[B2] ∪( IN[B2] – e_KILL[B2] ) = { D+D, D*D, B+C } ∪ ({ 3, 1 } – {A*A, A+G }) = {3, 1, D+D, D*D, B+C } // 不变

第二次迭代：(all NON-ENTRY B) (3) IN[B3] = OUT[B2] = {3, 1, D+D, D*D, B+C } //不变 OUT[B3] = e_gen[B3] ∪ ( IN[B3] – e_kill[B3] ) = { A+G } ∪ ( { 3, 1, D+D, D*D, B+C } – { B+C } ) = { 3, 1, D+D, D*D, A+G } //不变 (4) IN[B4] = OUT[B2] OUT[B4] = e_gen[B4] ∪ ( IN[B4] – e_kill[B4] ) = { A * A } ∪( { 3, 1, D+D, D*D, B+C } – { B+C } ) = { 3, 1, D+D, D*D, A * A } //不变

第二次迭代：(all NON-ENTRY B) (5) IN[B5] = OUT[B3] ∩ OUT[B4] = { 3, 1, D+D, D*D, A+G } ∩{ 3, 1, D+D, D*D, A * A } = { 3, 1, D+D, D*D } //不变 OUT[B5] = e_gen[B5] ∪ ( IN[B5] – e_kill[B5] ) = {B+C}∪({3,1,D+D, D*D} – {A+G, D*D, D+D}) = { 3, 1, B+C } //不变 (6) IN[EXIT] = OUT[B5] = { 3, 1, B+C } //不变 OUT[EXIT] = e_GEN[EXIT] ∪ (IN[EXIT] –e_KILL[EXIT]) = ∅ ∪ ({ 3, 1, B+C } – ∅ ）