全局数据流分析

全局数据流分析的各种算法,都是求布尔方程组的最小解。求解中的主要困难来自“对角线项”。本文证明,这种“对角线项”对最小解实际上并没有影响,因此在求最小解的过程中可以略去。利用这个结果,我们引进对布尔方程组的两种变换,并得到数据流分析的新算法。这个算法不用考虑流图是否可以归约。 还可以利用这些变换来说明Cocke及Allen算法及Kennedy算法的实质。我们还将指出,这些变换作为流图变换,是Hecht及Ullman的变换的扩充。