数据流分析

定义

数据流分析(Data-Flow Analysis)是一类静态分析框架:在控制流图上为每个程序点计算某种事实集合(如哪些变量活跃、哪些定值可达),通过传递函数沿边传播并迭代至不动点。

经典问题

到达定值分析(支撑常量传播)、活跃变量分析(支撑死代码消除与寄存器分配)、可用表达式分析(支撑公共子表达式消除)、忙表达式分析(支撑代码提升)。按信息流向分为前向与后向分析,按路径汇合方式分为 may 与 must 分析。

理论基础

分析建立在格(lattice)与单调函数之上:若格高度有限且传递函数单调,迭代必然收敛,这由不动点定理保证。

应用

数据流分析不仅服务编译优化,也是静态缺陷检测(空指针、未初始化变量)、污点分析等程序分析工具的共同理论根基。