活变量分析,我的解释正确吗?
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的语句中同时存在的变量是
- p, s, u
- r, s, u
- r, u
- 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."
我的看法是这样的:
在 进入 块 2 之前,语句 v = r + u
是
已执行(想象一个无操作的空语句作为入口插入到
每个块,另一个作为块的出口),然后 r
并且 u
必须 在线,因为存在即将发布的声明
两者都使用,并且代码中有一条从入口到
该语句不包含任何中间分配。
与其想象这些额外的空语句,不如使用
定义的原始语义,那么我们只是在谈论
Si == Sj
的情况,因为两者都引用了 v = r + u
声明 - 从声明到自身有一条简单的路径
在这个意义上不包含额外的任务。我觉得更容易
用额外的空进入和退出语句来考虑它,
不过
执行后v = r + u
,然而,在虚
块退出空语句,现在可以安全地认为 u
不是
活的(或者死的),因为块 4 中没有任何东西使用它,并且
它在块 1 中重新分配,然后再在任何一个中再次使用
块 2 或 3.
所以,部分混淆似乎是在考虑变量是否存在 在特定块 中,这并不符合定义 - 你需要思考关于变量是否在特定语句 处。你可以假设变量 u
在块 2 中既是活的又是死的,这取决于你是在执行单独的语句之前查看它,还是在...
之后查看它
由于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的语句中同时存在的变量是
- p, s, u
- r, s, u
- r, u
- 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."
我的看法是这样的:
在 进入 块 2 之前,语句
v = r + u
是 已执行(想象一个无操作的空语句作为入口插入到 每个块,另一个作为块的出口),然后r
并且u
必须 在线,因为存在即将发布的声明 两者都使用,并且代码中有一条从入口到 该语句不包含任何中间分配。 与其想象这些额外的空语句,不如使用 定义的原始语义,那么我们只是在谈论Si == Sj
的情况,因为两者都引用了v = r + u
声明 - 从声明到自身有一条简单的路径 在这个意义上不包含额外的任务。我觉得更容易 用额外的空进入和退出语句来考虑它, 不过执行后
v = r + u
,然而,在虚 块退出空语句,现在可以安全地认为u
不是 活的(或者死的),因为块 4 中没有任何东西使用它,并且 它在块 1 中重新分配,然后再在任何一个中再次使用 块 2 或 3.
所以,部分混淆似乎是在考虑变量是否存在 在特定块 中,这并不符合定义 - 你需要思考关于变量是否在特定语句 处。你可以假设变量 u
在块 2 中既是活的又是死的,这取决于你是在执行单独的语句之前查看它,还是在...