到达一定值数据流分析 ■定值与引用 d:X:=y+z∥语句d是变量x的一个定值点 流图中有路径d->u, 且该路径上没有x的其 它(无二义)定值 U:W:=Ⅹ+V∥语句u是变量x的一个引用点 ■变量x在d点的定值到达u点 2021/2/11 《编译原理与技术》之代码优化 11
2021/2/11 《编译原理与技术》之代码优化 11 •到达－定值数据流分析 定值与引用 d : x := y + z // 语句d 是变量x的一个定值点 u : w := x + v // 语句u 是变量x的一个引用点 变量x在d点的定值到达u点 流图中有路径d---->u， 且该路径上没有x的其 它（无二义）定值
到达一定值数据流分析 解决的问题 定值“传播 数据流归属 任意路径、向前流的数据流分析 NEB],到达基本块入口处定值集合 OUT[B,到达基本块出口处定值集合 GEN[B],基本块产生且能到达基本块出口的定值集合 KLB由基本块注销的定值集合(这些定值不能传 播或到达到块出口 ■数据流应用 ud链,即引用一定值链。可以据此判断基本块内的某 变量引用,其值来自何方(定值)。如应用于循环不变式 的寻找 2021/2/11 《编译原理与技术》之代码优化 12
2021/2/11 《编译原理与技术》之代码优化 12 •到达－定值数据流分析 解决的问题 － 定值“传播” 数据流归属 － 任意路径、向前流的数据流分析 － IN[B]，到达基本块入口处定值集合 － OUT[B]，到达基本块出口处定值集合 － GEN[B]，基本块产生且能到达基本块出口的定值集合 － KILL[B]，由基本块注销的定值集合（这些定值不能传 播或到达到块出口） 数据流应用 － ud链，即引用－定值链。可以据此判断基本块内的某 变量引用，其值来自何方（定值）。如应用于循环不变式 的寻找
前驱1 前驱2 ouT. d,x= oUT: d:X'= INBI ds:s d1:|X u:|X:= 控制流 OUT[B=? 2021/2/11 《编译原理与技术》之代码优化
2021/2/11 《编译原理与技术》之代码优化 13 OUT: dm : x:= … OUT: dn : x:= … 前驱1 前驱2 … ds : s := …x… … dt : x := … … du : x := … … IN[B] OUT[B] = ? 控制流
前驱1 前驱2 oUT: dm.x'= OUT: do:X= 英雄惜英雄,dn和dn 相会在汇流点,共赴 N[BY INB d。:s X 2021/2/11 OUTB]锋原理与技术》之代码优化 14
2021/2/11 《编译原理与技术》之代码优化 14 OUT: dm : x:= … OUT: dn : x:= … 前驱1 前驱2 … ds : s := …x… … dt : x := … … du : x := … … IN[B] OUT[B] = ? 英雄惜英雄，dm 和 dn 相会在汇流点，共赴 IN[B]
前驱1 前驱2 oUT: dm.x'= OUT: do:X= dm和dn:一路无险 ANBY 遇ds d。:s X 2021/2/11 OUTB]锋原理与技术》之代码优化 15
2021/2/11 《编译原理与技术》之代码优化 15 OUT: dm : x:= … OUT: dn : x:= … 前驱1 前驱2 … ds : s := …x… … dt : x := … … du : x := … … IN[B] OUT[B] = ? dm和dn ：一路无险 遇 ds