这张幻灯片显示了用于计算in[n]
和out[n]
控制流图节点的算法。我很难理解它是如何工作的。我已经看到了一些其他的变化,也很难理解它们。我以前从未处理过定点的东西。
for each n
in[n] := {}; out[n] = {}
repeat
for each n
in’[n] := in[n]; out’[n] := out[n]
in[n] := use[n] ∪ (out[n] - def[n])
out[n] := ∪ {in[s] | s ε succ[n]}
until in’[n] = in[n] and out’[n] = out[n]
for all n
问题是,这个算法在做什么/对它的更直观的解释。我不明白什么in'
和out'
是,以及结束条件是什么意思(until in'...
)。不遵循嵌套循环。我对 JavaScript 实现的尝试显示了我缺少的部分:
var in = {}
var out = {}
var in2 = {}
var out2 = {}
var use = {}
var out = {}
var def = {}
for (var i = 0, n = nodes.length; i < n; i++) {
var node = nodes[i]
in[node] = []
out[node] = []
// assume these are already filled out:
use[node] = []
out[node] = []
def[node] = []
}
while (true) {
for (var i = 0, n = nodes.length; i < n; i++) {
var node = nodes[i]
in2[node] = in[node]
out2[node] = out[node]
// assume ∪ and - work on arrays
in[node] = use[node] ∪ (out[node] - def[node])
// ? not sure the ∪
out[node] = ∪ {in[s] | s ε succ[n]}
}
// until in’[n] = in[n] and out’[n] = out[n]
// for all n
}
任何帮助将不胜感激。谢谢你。