PL-2-Data-Flow-Analysis
内容提要
本文介绍了数据流分析的核心概念，即数据如何在控制流图（CFG）的节点和边上流动。详细阐述了三种经典分析：到达定值分析（检测变量定义）、活跃变量分析（判断变量未来是否被使用）和可用表达式分析（识别可复用的计算结果）。每种分析都涉及数据抽象、转移方程、控制流处理及迭代算法，并说明了初始化策略和终止条件（不动点）。
延伸解读
数据流分析的本质：抽象与近似
数据流分析的核心在于对程序状态进行抽象，并用安全近似（safe-approximation）策略处理流动信息。不同分析（如到达定值、活跃变量、可用表达式）选择不同的数据抽象和转移函数，但都遵循统一的框架：在CFG节点上应用转移方程，在边上通过meet算子处理控制流汇合。理解这一共性有助于掌握各类分析的推导与实现。
迭代算法与不动点：终止性的保证
三种分析均采用迭代算法求解，其终止依赖于数据流值集合的单调变化。例如，到达定值分析中OUT集合单调增长且有上界，最终达到不动点；活跃变量分析则从空集开始，逐步收敛。初始化策略至关重要：may analysis（如到达定值）通常置空，而must analysis（如可用表达式）需置为全集以避免环路导致的错误收敛。
前向与后向分析：方向决定应用
数据流分析分为前向（如到达定值、可用表达式）和后向（如活跃变量）两类。前向分析从入口向出口传播信息，适合检测定义可达性；后向分析从出口向入口传播，适合判断变量未来是否被使用。方向的选择直接影响转移方程和控制流处理（并集或交集），也决定了分析能解决的具体问题，如寄存器分配依赖活跃变量分析。
Q&A
数据流分析的核心是什么？
数据流分析的核心是研究应用特定的数据如何在控制流图（CFG）的节点和边上流动，包括数据抽象、流动安全近似策略、转移函数和控制流处理。
到达定值分析中，一个定值到达某点的条件是什么？
如果存在一条从定值点之后的路径到达该点，且路径上没有该变量的其他定值，则该定值到达该点。若路径上有其他定值，则原定值被杀死。
到达定值分析可以用来做什么？
到达定值分析可以用来检测未定义的变量。通过在程序入口为每个变量引入一个假定值，如果程序出口某变量的定值仍为假定值，则说明该变量未被定义。
活跃变量分析中，变量在程序点p上活跃的条件是什么？
变量x在程序点p上活跃，当且仅当存在一条从p出发的路径，该路径的末端使用了x，且路径上没有对x进行重新定义（即没有kill）。
活跃变量分析有什么实际用途？
活跃变量分析可用于寄存器分配。当一个变量不再活跃（即未来不会被使用），就可以将其占用的寄存器腾出来，用于存储新值。
可用表达式分析中，表达式x+y在p点可用的条件是什么？
从流图入口结点到达p的每条路径都对x+y求了值，且在最后一次求值之后再没有对x或y赋值。
可用表达式分析可以用来做什么？
可用表达式分析可用于全局公共子表达式的计算。如果一个表达式上次计算的值到当前点仍然可用，就可以直接利用该值，避免重复计算。
在数据流分析中，may analysis和must analysis的初始化策略有何不同？
May analysis（如到达定值、活跃变量）通常将内部基本块的输出初始化为空集，因为不确定有哪些数据流值；而must analysis（如可用表达式）将内部基本块的输出初始化为全集，以避免因空集导致迭代过早收敛。
