如前面的部分所示,数据流分析是通过提供格和约束规则来指定的。从示例中可以看出一些模式,这使得可以以不同的方式对数据流分析进行分类。
- 前向分析 forward analysis:是指对于每个程序点,计算有关过去行为的信息。这包括符号分析和可用表达式分析。它们可以通过约束的右侧仅依赖于控制流图节点的前驱来进行描述。因此,分析基本上从入口节点开始,在控制流图中向前传播信息。对于这种分析,JOIN函数使用前驱pred进行定义,而dep(如果使用工作列表算法)可以通过succ进行定义。
- 后向分析 backward analysis:是指对于每个程序点,计算有关未来行为的信息。这包括活跃变量分析和非常繁忙表达式分析。它们可以通过约束的右侧仅依赖于控制流图节点的后继来进行描述。因此,分析从退出节点开始,在控制流图中向后移动。对于这种分析,JOIN函数使用后继succ进行定义,而dep可以通过前驱进行定义。
前向和后向的区别适用于任何流敏感的分析。对于基于幂集格的分析,我们还可以区分may和must分析。
- may分析:may分析是描述可能为真的信息,并因此计算出一个过度逼近的分析。活跃变量分析和到达定义分析是其中的例子。它们可以通过格序为集合的$\subseteq$,并且使用集合的$\bigcup$运算符来组合信息的约束函数来进行描述。
- must分析:must分析是描述必须确实为真的信息,并因此计算出一个欠逼近的分析。可用表达式分析和非常繁忙表达式分析是其中的例子。它们可以通过使用$\supseteq$作为格序,并且使用$\bigcap$运算符来组合信息的约束函数来进行描述。
因此,本章的四个例子包含了幂集合晶格的每一种组合情况:
这些分类主要是朴素直观的,但对它们的了解可能会为构建新的分析提供灵感。