补充二 信息流分析.ppt

补充二数据流分析技术 复习 1 什么是元程序 程序的程序元程序的组成及元程序的作用 2 预处理 掌握三种中间表示3 掌握4种文法规则 结构规则 选择规则 表规则 词法规则 4 能用规则表示其程序源码 要点 了解什么是数据流分析技术理解对数据流的十种定义 找出下列程序的错误voidf1 int p1 intp2 intp3 p1 p3 p2 main inta x y printf Typeinavaluefora scanf d 数据流分析技术 数据流分析技术是对源程序分析 获取程序中变量定值和传播的情况 帮助理解程序中的数据流动情况 数据流分析的用途编译优化 程序维护程序安全性的检查数据流分析所得结论同程序运行时的情况一致需要定义机器模型和操作语义 证明所得结论对操作语义可靠数据流分析收集的信息同基本块和控制流有关 通常和变量值无关 数据流分析的最基本点 掌握赋值操作改变哪些变量的值 1 如果没有引用变量 直接读取变量赋值 2 如果有引用变量 则很难静态分析什么变量被赋值 数据流方程定义 定义一 基本块是一个顺序执行的命令序列 进入一个基本块 必须从第一条命令进入 退出基本块 必须由最后一条命令退出 特点 后续执行情况可判断 例1 x x 1 y y 1 z z 1 定义二 程序图是一个有向图 它的结点为基本块 有一个入口结点 无前驱结点 和一个出口结点 无后续结点 扩展 常用的程序图有三种表示 流程图N S图PAD图 定义三 定值在基本块当中对变量x的赋值 若有d x e e代表一个表达式 则称有对x的定值 d 为x的定值点 注 d 为程序中引入的标识 对程序无影响 定义四 注销若有对变量x的赋值x 则程序注销了x的原定值 用kill B 表示B中被注销的所有变量之集 定义五 向下暴露的定值设 Bi di 为x的一个定值 若从di 1到Bi的出口再无对x的定值 则称x的di的定值为向下暴露的定值 并用def Bi 表示Bi中的所有向下暴露定值的变量之集 定义六 可能到达的定值说在 Bi di 点x定值可能到达 Bj dj 点 若从 Bi di 存在一条路 且在该路上无x的定值 用符号in Bi 和out Bi 分别表示可能到达Bi块入口处和出口处的所有变量定值的集合 可到达的定值数据流方程in B B 为入口块 out B def B in B kill B in B out Bi i 1 2 n Bi为B的前驱结点其中in B 表示在B入口处有定值的变量之集out B 表示定值可到达B出口处的变量定值之集 实例 找出每个块中的可能到达的定值集合 定义七 定义性出现 使用性出现称第一次出现在赋值命令左部的变量出现 即x 第一次出现 为变量 x 的定义性出现 而称其他部位中的变量出现为其使用性出现定义八 向上暴露的使用在 Bi di 有x的使用性出现 若从Bi的入口到di 1点无对x的赋值 则称x在 Bi di 点的出现为向上暴露的使用 用use live B 表示B中所有向上暴露的使用 定义九 变量的活跃性说变量x在 Bi di 点活跃 若 1 存在一点 Bj dj 有x的使用性出现 且2 从 Bi di 到 Bj dj 存在一条通路 且在该路上无对x的定值 定义十 注销活跃性若在某一点 Bk dk 有X E 则称注销X的活跃性 思考 如何求各个基本块入口处和出口处上活跃变量集 显然 在Bi块的入口处活跃的一定在前驱出口处活跃 1 Bi块的局部向上暴露使用的变量 2 Bi块出口处活跃且不被Bi块所注销的变量 活跃变量的数据流方程表示方法in live B use live B out live B kill live B out live B in live Bi Bi为B的后续out live B B 为出口块其中in live B 在B入口处活跃的所有变量的集合 out live B 在B出口处活跃的所有变量的集合 use live B Bi中所有局部向上暴露使用的变量集合 kill live B x B注销其活跃性的变量集合 如果含有过程 该如何表达和分析数据流 定义十一 过程调用块把过程调用P e1 en 定义为一个独立的基本块 称为过程调用块 定义十二 过程的返回块调用块的接续为返回块 或return的后续块 难点 下标变量的分析别名问题 数据流分析技术应用 数据流分析的基础把各种数据流模式作为一个整体来抽象地研究 然后可以形式地回答数据流算法的下列几个基本问题 在什么情况下数据流分析中使用的迭代算法是正确的 该迭代算法所得解的精度如何 该迭代算法是否收敛 数据流方程的解的含义是什么 第一个应用 检测数据流异常 数据流异常情况 变量无定值而使用 变量重复定值 变量定值无使用 检测 针对第一种情况 无定值而使用 in d B 表示在B入口处所有定值的变量之集 out d B 表示B在出口处所有定值的变量之集 def d B 表示B中所有定值的变量之集 数据流方程 in d B B 为入口块in d B 或 i 1 2 n out d Bi Bi为B的前驱块out d B def d B in d B 结论 若in live B in d B 则必有变量无定值而使用 特例 若in live B 则必有变量无定值而使用 针对第2和3中情况 in dd Bi 表示块B入口处所有定值而未使用的变量之集 out dd Bi 表示块B出口处所有定值而未使用的变量之集 def dd1 Bi x x在 B di 点定值 且从 B d1 B di 无x的使用性出现 def dd2 Bi x x在 B di 点定值 且从 B di 1 到B出口 无x的使用性出现 in dd B B 为入口块in dd B 或 out dd B out dd B def dd2 B in dd B use B 结论 若in dd B def dd1 B 则有变量重复定值 若in dd B in live Bi 则有变量定值而未使用 或重复定值 若out dd B B 为出口块 则有变量定值而未使用 第二个应用 程序优化 全局常表达式节省 程序优化 全局常表达式节省问题 利用的信息不充分如何解决 程序优化中 我们感兴趣的是什么 对于每个块要知道哪些常量定值是一定能到达其出口处的 定义 常量定值若在块B中有x c 其中c是常数 且该定值是向下暴露的 则称x有一个常量定值 记为x c 定义 注销常量定值若有x E 则称注销了x的常量定值 定义 广义常量定值若块B中有向下暴露的定值x E 且E的值可计算为一个常量c 则称产生一个广义常量定值x c 定义 注销广义常量定值若有x 则称注销了广义常量定值 数据流方程 in ac B0 B0为入口块in ac Bi j 1 2 nout ac Bj Bj为Bi的前驱out ac Bi def ac Bi U in ac Bi kill ac Bi 其中 in ac Bi 定能达到Bi入口的所有常量定值的集合out ac Bi 定能达到Bi出口的所有常量定值的集合def ac Bi Bi所产生且对块外有效的常量定值kill ac Bi Bi所注销的所有常量定值的集合 优化过程 建立数据流方程求解对每一基本块进入优化把in ac B 填入vvl按原方法优化 例题 in ac B1 out ac B1 x 1 y 2 in ac B2 x 1 y 2 out ac B2 x 1 y 2 z 3 b 4 in ac B3 x 1 y 2 out ac B3 x 1 y 2 z 3 b 4 in ac B4 x 1 y 2 z 3 b 4 out ac B4 x 1 y 2 z 3 b 4 k 7 u 9 r 16 第三个应用 公共子表达式节省 定义 表达式定值在块B中 若有d x E 则称有表达式E的定值 d为定值点若从di 1到B的出口没有对表达式E中变量的赋值 则称B定值了表达式E定义 注销表达式定值若有x E 且x出现在表达式E中 注销了E的定值 数据流方程 in e B0 B0为入口块out e Bi def e Bi in e Bi kill e Bi in e Bi Bj pre Bi out e Bj Bj为Bi的前驱 K 需要注意的两个问题 形式相同的表达式未必能节省 已解决 形式不同的表达式也可能节省 未解决 定义 等式定值在块B中 若有x y 且从di 1到B出口无对x或y的赋值 则称B有了一个等式定值 即x y定义 注销等式定值