活变量分析,我的解释正确吗?

Live variable analysis , is my explanation correct?

由于stackexchange没有更多关于编译器标签的标签,所以我在这里发布这个问题。


如果同时满足以下三个条件,则称变量 x 存在于程序中的语句 Si 中:

1. There exists a statement Sj that uses x
2. There is a path from Si to Sj in the flow
   graph corresponding to the program
3. The path has no intervening assignment to x 
   including at Si and Sj 

在上述控制流图的基本块2和基本块3的语句中同时存在的变量是

  1. p, s, u
  2. r, s, u
  3. r, u
  4. q, v

我试着解释一下:


正如 wikipedia 所说 "Stated simply: a variable is live if it holds a value that may be needed in the future."

根据相关定义,如果变量在未来任何新赋值之前被使用,则它是有效的。 块 2 将“r”和“v”都作为活动变量。因为它们在分配给它们的任何新值之前在块 4 中使用。请注意,变量“u”不在块 2 中,因为“u”在块 3 中使用之前在块 1 中分配了一个新值。变量“p”、“s”和“q”也不在块中2 由于同样的原因。 块 3 只有“r”作为活动变量,因为每个其他变量在使用前都被分配了一个新值。


另一种解释为:


只有 r.

p,s,u在1中赋值,之前没有中间使用。因此 p、s 和 u 并不同时存在于 2 和 3 中。 q 在 4 中被赋值,因此在 2 和 3 中都不存在。

v 在 3 点直播,但在 2 点不直播。 只有 r 在 2 和 3 都存在。

但是官方的GATE key说的是r和u。

我看到两件事可能至少是您困惑的一部分。

首先,在活变量的条件列表中,没有限制说明Si != Sj,所以这让我的定义有点不精确。

第二个是你的断言"Note that variable ‘u’ is not live in block 2 as ‘u’ is assigned a new value in block 1 before it is used in block 3."

我的看法是这样的:

  1. 进入 块 2 之前,语句 v = r + u 是 已执行(想象一个无操作的空语句作为入口插入到 每个块,另一个作为块的出口),然后 r 并且 u 必须 在线,因为存在即将发布的声明 两者都使用,并且代码中有一条从入口到 该语句不包含任何中间分配。 与其想象这些额外的空语句,不如使用 定义的原始语义,那么我们只是在谈论 Si == Sj 的情况,因为两者都引用了 v = r + u 声明 - 从声明到自身有一条简单的路径 在这个意义上不包含额外的任务。我觉得更容易 用额外的空进入和退出语句来考虑它, 不过

  2. 执行后v = r + u,然而,在虚 块退出空语句,现在可以安全地认为 u 不是 活的(或者死的),因为块 4 中没有任何东西使用它,并且 它在块 1 中重新分配,然后再在任何一个中再次使用 块 2 或 3.

所以,部分混淆似乎是在考虑变量是否存在 在特定块 中,这并不符合定义 - 你需要思考关于变量是否在特定语句 处。你可以假设变量 u 在块 2 中既是活的又是死的,这取决于你是在执行单独的语句之前查看它,还是在...

之后查看它