compiler-theory - 如何识别不影响程序输出的变量？

Question

有时，在程序的控制流中访问的变量值不可能对其输出产生任何影响。例如:

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 等变量在数据流理论/编译器理论中有名称吗？
可以使用哪些静态数据流分析技术来发现它们？

引用有关该主题的学术文献将特别受欢迎。

Answer 1

你说的问题一般来说是不可判定的，
即使对于以下非常狭窄的特殊情况:
给定单个例程 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

因此，编译器很难判断一个变量是否真的不影响例程的返回值；在您的示例中，“副作用例程”可能会操纵其值之一(甚至无限循环，这肯定会改变例程的返回值；-)
当然，过度近似仍然是可能的。例如，人们可能会得出结论，如果一个变量根本没有出现在例程体中，它就不会影响返回值。您还可以看到一些经典的编译器分析(如表达式简化、常量传播)具有消除此类冗余变量出现的副作用。