什么是还原变量？任何人都可以给我一些例子吗？

Question

什么是还原变量？ 任何人都可以给我一些例子吗？

Answer 1

下面是在计算阵列的总和的类C语言的简单示例：

int x = 0; 
for (int i = 0; i < n; i++) { 
    x += a[i]; 
} 

在这个例子中，

• i是归纳变量 - 在每个迭代它改变了一些常数。它可以是+1（如上例）或*2或/3等，但关键是在所有的迭代中数字是相同的。

  换言之，在每次迭代中i_new = i_old op constant，其中op是+，*等，并且迭代之间既不op不constant变化。

• x是减少可变 - 它积累数据从一个迭代到下一个。它始终有一些初始化（在这种情况下为x = 0），虽然每次迭代中累积的数据可能不同，但操作员保持不变。

  换句话说，在每次迭代中，x_new = x_old op data和op在所有迭代中保持不变（尽管data可能会改变）。

在许多语言中there's a special syntax for performing something like this - 通常被称为“折叠”或“减少”或“积聚”（以及它具有其他名称） - 但在LLVM IR的情况下，感应的变量将通过表示phi节点在循环内部的二进制操作和其之前的初始化值之间的循环中。

对于优化编译器而言，约化变量（如加法）中的交换*操作特别有趣，因为它们似乎在迭代之间显示出比实际更强的依赖关系;例如上面的例子可以被重写成一个矢量化的形式 - 每次添加4个数字，然后是一个小的循环，将最终的矢量求和成单个值。

_{*有更多的实际条件减小变量必须满足可应用这样的量化之前，但是这是真的在这里的范围之外}