有时,在程序的控制流中访问的变量值不可能对其输出产生任何影响。例如:
global var_1
global var_2
start program hello(var_3, var_4)
if (var_2 < 0) then
save-log-to-disk (var_1, var_3, var_4)
end-if
return ("Hello " + var_3 + ", my name is " + var_1)
end program
这里只有 var_1 和 var_3 对输出有任何影响,而 var_2 和 var_4 仅用于副作用。
var_1 和 var_3 等变量在数据流理论/编译器理论中有名称吗?
可以使用哪些静态数据流分析技术来发现它们?
引用有关该主题的学术文献将特别受欢迎。
最佳答案
你说的问题一般来说是不可判定的,
即使对于以下非常狭窄的特殊情况:
给定单个例程 P(x),其中 x 是整数类型的参数。 P(x) 的输出是否与 x 的值无关,即
P(0) = P(1) = P(2) = ...?
我们可以将停机问题的以下仍然不可判定的版本简化为上述问题:给定图灵机 M(),程序是否
永远不要停在空输入上?
我假设我们使用一种(图灵完备的)语言来构建“图灵机模拟器”:
给定程序 M(),构造此例程:
P(x):
if x == 0:
return 0
Run M() for x steps
if M() has terminated then:
return 1
else:
return 0
现在:
P(0) = P(1) = P(2) = ...
=>
M() does not terminate.
M() does terminate
=> P(x) = 1 for a sufficiently large x
=> P(x) != P(0) = 0
因此,编译器很难判断一个变量是否真的不影响例程的返回值;在您的示例中,“副作用例程”可能会操纵其值之一(甚至无限循环,这肯定会改变例程的返回值;-)
当然,过度近似仍然是可能的。例如,人们可能会得出结论,如果一个变量根本没有出现在例程体中,它就不会影响返回值。您还可以看到一些经典的编译器分析(如表达式简化、常量传播)具有消除此类冗余变量出现的副作用。
关于compiler-theory - 如何识别不影响程序输出的变量?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24184811/