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

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

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这样的变量在dataflow-theory/compiler-theory中有一个名字吗？哪些静态数据流分析技术可用于发现它们？

有关这方面的学术文献的参考将特别感激。

来源

2014-06-12 Raul Bertone

假设编译器可以区分这两类变量，它可以对这些信息做些什么？我认为你一般不会认为调用'save-log-to-disk'并不比函数结果重要。 –

@内部服务器错误：在考虑某个程序时，从功能的角度来看，您通常只将某些输入和输出视为有趣的。该计划可能会计算/做其他事情，但你不在乎。日志文件适合这个类别。 –

即使对于以下非常窄的特例，您陈述的问题通常是不可判定的：给定一个例程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

所以，这是非常困难的一个编译器，以决定是否一个变量实际上不影响日常的返回值;在你的例子中，“副作用例程”可能会操纵它的一个值（或者甚至无限循环，这肯定会改变例程的返回值;-) 当然，过度使用仍然是可能的。例如，有人可能会得出这样的结论：如果一个变量没有出现在例程体中，它就不会影响返回值。您还可以看到一些经典的编译器分析（如表达式简化，常量传播），这些分析具有消除此类冗余变量外观的副作用。

来源

2016-01-27 00:13:46 Pachelbel

帕切贝尔已经讨论过你无法完美地完成这一事实。好的，我是一名工程师，我愿意接受我的答案中的一些污点。

回答你问题的经典方法是做数据流从程序输出回溯到程序输入。 A 数据流是将程序分配（或副作用）与变量值连接到应用程序中消耗该值的位置。

如果您关心的程序输出（在您的示例中为打印文本流）中存在（传递式）数据流，那么该输入会影响输出。从您的观点来看，不会从输入流向所需输出的变量是无用的。

如果您只关注数据流中涉及的计算并显示它们，则会得到通常称为“程序片”的内容。有（很少）商业工具可以显示给你。Grammatech在C和C++方面享有盛誉。

有构建这样的数据流图的标准编译器算法;看任何有能力的编译器书。

由于Pachelbel指出Turing的不可行性证明，它们都受到一些限制。当你实现这样的数据流算法时，会有一些地方不知道正确的答案;只需选择一个。

如果您的算法选择在某些不确定的地方回答“没有数据流”，那么它可能会错过有效的数据流，并且可能会报告变量不会错误地影响答案。（这被称为“假否定”）。如果该算法具有其他一些很好的属性，例如它在数百万的代码上运行速度非常快，这种偶然的错误可能会令人满意。（琐细算法简单地说，在所有的地方“没有数据流”，这是真的快速 :)

如果你的算法选择回答“是的，有一个数据流”，那么它可能会要求一些变量影响当它没有时回答。（这被称为“误报”）。

你可以决定哪个更重要;许多人在寻找问题时更喜欢误报，因为那样你就必须至少查看工具检测到的可能性。假否定意味着它没有报告你可能关心的事情。因人而异。

这是一个起始参考：http://en.wikipedia.org/wiki/Data-flow_analysis 该页面上的任何书籍都会非常好。我有Muchnick的书，喜欢它很多。另见本页面：（http://en.wikipedia.org/wiki/Program_slicing）

你会发现，对于任何真正的语言来说，实现这个功能都是很大的努力。你可能更适合找到一个工具框架，它已经为你做了大部分或全部工作。

来源

2016-01-27 04:54:14

我使用以下算法：如果变量是参数，或者它出现在表达式中的任何位置（不包括作为LHS的赋值），则使用变量。首先，计算所有变量的使用次数。删除未使用的变量并将其分配给未使用的变量。重复，直到没有变量被删除。

该算法只实现了OP的一个子集，它的效率非常低，因为它需要多次通过。垃圾收集可能会更快，但难于编写：我的算法只需要一个包含使用次数的变量列表。每个程序的大小都是线性的。该算法通过消除分配中结束的流尾，有效地进行有限的数据流分析。

对于我的语言来说，消除RHS中对未使用变量赋值的副作用是由语言规范强制的，因此可能不适用于其他语言。通过在内联之前运行来降低内联未使用的函数应用程序的成本，然后再次运行它，从而消除内联函数的参数，从而提高了效率。

正如语言规范实用程序的一个例子，该库构造了一个线程池并为其指定了一个指向全局变量的指针。如果不使用线程池，则分配将被删除，因此线程池的构造将消失。

恕我直言，编译器优化几乎总是启发式，其性能比实现理论目标（如去除未使用的变量）更有效。简单的减少是有用的，不仅因为它们快速且易于编写，而且因为使用了解编译器操作基础的语言的程序员可以利用这些知识来帮助编译器。最着名的例子可能是重构递归函数以将递归放在尾部位置：除非程序员知道编译器可以执行尾递归优化，否则毫无意义的练习。

来源

2016-01-28 19:34:49 Yttrill

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

回答

相关问题