这是一个用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可能会改变).
在许多语言中,有一种特殊的语法可以执行类似的操作 - 通常称为"折叠"或"缩小"或"累积"(并且还有其他名称) - 但在LLVM IR的上下文中,归纳变量将由循环内的二进制操作与其前的初始化值之间的循环中的phi节点.
减少变量(例如加法)中的交换*运算对于优化编译器特别有意义,因为它们似乎在迭代之间显示出比实际更强的依赖性; 例如,上面的例子可以被重写为矢量化形式 - 例如,一次添加4个数字,然后是一个小循环,将最终矢量加到一个单独的值中.
*实际上,在应用这样的矢量化之前,还原变量必须满足更多条件,但这实际上超出了范围