静态程序分析（五、六）:数据流分析基础理论

一、迭代算法 Iterative Algorithm Data Flow Analysis Foundations，数据流分析基础理论。掌握数据流分析 基础理论，才能自如的设计数据流分析算法来解决特定的静态分析问题。 下图是一个通用的数据流分析迭代算法，采用前向数据流，它用来得到一个 数据流问题的解 给定一个含有 k 个节点的程序 CFG，迭代算法每次迭代时更新每个 CFG 节点 的输出信息，即 OUT[n]。 假设数据流分析中数据 data facts 的集合是 V，这里的数据是指我们分析 问题的数据，数据的 domain 就是这些数据抽象值的域。比如，我们在分析到达 定值这个具体数据流问题时，V 就是程序所有变量的集合，domain 就是程序中所 有的变量可能取得的抽象值的集合{0,1}。再如，常量传播例子中，分析的数据 data facts 集合 V 就是程序中所有的变量，v 的 domain 就是{未定义、不是常 量、0、1、2、1.2、...} ，这个 domain 就是无穷的，因为作为常量可是任何数。 在到达定值中，我们用一个 bit vector 来表示节点的输出数据作为