3

定义问题是数据流分析中最基本的问题之一。给定一个包含变量定义和用途的控制流图，问题导致计算哪些变量定义可以达到特定用途。

例如考虑流程图：

                    ____________
                 1:|   x <- ... |
                    ------------
                     |            \
                     |              __________
                     |           2:| x <- ... |
                     |              -----------
                     |            /
                    ____________    
                 3:|  ... <- x  |
                    ------------

块 3 中变量 x 的使用可以通过块 1 或块 2 中的定义来实现。

计算哪些定义可以使用的算法是经典的数据流问题。使用龙编译器书（新版）中的符号，到达定义数据流问题如下：

域：定义集（例如 {x <- .., ...}）
方向：前向
传递函数：fb(x) = gen(B) U (x - kill(B)) 其中 gen(B) 是块 B 生成的定义集并 kill(B) 块 B 杀死
的
定义集流向块是前代块定义的联合。
方程：OUT[B] = fb(IN[B]), IN[B] = U(P in pred)OUT[P]
初始化：OUT[B] = {}

但是，并非所有定义都相同。例如，块 1 中的定义可能永远无法在块 3 中使用，因为它可能会被块 2 中的定义杀死。另一方面，块 2 中的定义如果被执行，将保留其值直到它在块中使用3.

我想找到从定义到用法的任何路径上都没有杀死定义的用法的到达定义。我的问题是是否存在类似的数据流问题（可能是传播等）。在数据流分析方面如何解决。

我确实有一个可能的解决方案，但如果解决方案已经存在，我不想重新发明轮子。

4

3 回答 3

0

相反，您可能想看看时间逻辑，计算树逻辑非常适合在控制流图中定义路径上的属性。本文展示了 CTL 中数据流属性的一些示例：

通过时序逻辑证明编译器优化的正确性

于 2011-10-03T18:09:26.730 回答
0

像这样更改问题定义：

满足运算符：∩(Intersect)，即流向块的定义是前代块定义的交集。

方程：OUT[B] = fb(IN[B]), IN[B] = ∩(P in pred)OUT[P]

于 2011-04-15T03:56:48.600 回答
0

这是我解决问题的方法。这可能不是最有效的方法，但我相信它有效。我将把这个问题称为保留定义的问题。首先，我计算到达定义。我正在对位集表示的定义集使用迭代数据流算法。

为此，我首先需要计算每个块的 gen(B) 和 kill(B)。这些是每个块分别生成和杀死的定义。请注意，kill(B) 是实际 kill(B) 的超集，因为我不知道真正被杀死的定义和块是什么，因为此时我没有考虑数据流。

应用到达定义后，我为控制流图中的每个块设置了 REACH_IN(B) 和 REACH_OUT(B)。我知道保留的定义是到达定义的子集。为了计算它们，我需要找出从程序进入每个块的过程中永远不会被杀死的定义。我将把这些集合称为非杀伤集，我将提供一种算法来计算图中每个块的 NO_KILL_IN(B) 和 NO_KILL_OUT(B)。这是数据流分析方面的算法。

域：定义集（例如 {x <- .., ...}）
方向：前向
传递函数：fb(x) = x - (kill(B) ∩ REACH_IN(B)) 其中 kill(B) 是阻止 B 的定义集杀死和 REACH_IN(B) 流入 B 的定义集。
边界：NO_KILL_OUT[ENTRY] = U（通用集），即所有定义都不会从函数的条目中被杀死
Meet 运算符：∩(intersection) ，即如果定义没有在任何前任块中被杀死，则不会被杀死。
方程：NO_KILL_OUT[B] = fb(IN[B]), NO_KILL_IN[B] = ∩(P in pred)NO_KILL_OUT[P]
初始化：NO_KILL_OUT[B] = U

请注意，在转移函数中，我们计算了 kill(B) ∩ REACH_IN(B)，它是在块 B 中被杀死的实际定义的集合。如果我们不使用它，我们将过于乐观。该算法计算在每个块之前和之后哪些定义不能被杀死，而不考虑它们是否已经生成。为了计算保留的定义，我们只需执行交集：

PRESERVE_IN(B) = REACH_IN(B) ∩ NO_KILL_IN(B)
PRESERVE_OUT(B) = REACH_OUT(B) ∩ NO_KILL_OUT(B)

于 2011-04-17T16:47:11.873 回答