编译器(特别是rustc)真的可以简化三角求和以避免循环吗?如何?

Question

在Blandy和Orendorff的Programming Rust的第322页上是这样的声明：

。锈。。。认识到有一种更简单的方法可以将数字从 1 求和到n：总和始终等于n * (n+1) / 2。

这当然是一个相当著名的等价，但是编译器如何识别它呢？我猜它是在 LLVM 优化传递中，但 LLVM 是否以某种方式从第一原理推导出等价性，或者它只是有一些可以简化为算术运算的"公共循环计算"？

Answer 1

首先，让我们证明这确实发生了。

从以下代码开始：

pub fn sum(start: i32, end: i32) -> i32 {
let mut result = 0;
for i in start..end {
result += i;
}
return result;
}

在发布中编译，我们得到：

; playground::sum
; Function Attrs: nounwind nonlazybind readnone uwtable
define i32 @_ZN10playground3sum17h41f12649b0533596E(i32 %start1, i32 %end) {
start:
%0 = icmp slt i32 %start1, %end
br i1 %0, label %bb5.preheader, label %bb6
bb5.preheader:                                    ; preds = %start
%1 = xor i32 %start1, -1
%2 = add i32 %1, %end
%3 = add i32 %start1, 1
%4 = mul i32 %2, %3
%5 = zext i32 %2 to i33
%6 = add i32 %end, -2
%7 = sub i32 %6, %start1
%8 = zext i32 %7 to i33
%9 = mul i33 %5, %8
%10 = lshr i33 %9, 1
%11 = trunc i33 %10 to i32
%12 = add i32 %4, %start1
%13 = add i32 %12, %11
br label %bb6
bb6:                                              ; preds = %bb5.preheader, %start
%result.0.lcssa = phi i32 [ 0, %start ], [ %13, %bb5.preheader ]
ret i32 %result.0.lcssa
}

我们确实可以观察到不再有循环。

因此，我们证实了Bandy和Orendorff的说法。

---

至于这是如何发生的，我的理解是这一切都发生在ScalarEvolution中.cpp在LLVM中。不幸的是，该文件是一个 12,000+ 行的怪物，因此导航它有点复杂;尽管如此，Head 评论暗示我们应该在正确的位置，并指出它使用的论文提到了优化循环和闭式函数¹：

//===----------------------------------------------------------------------===//
//
// There are several good references for the techniques used in this analysis.
//
//  Chains of recurrences -- a method to expedite the evaluation
//  of closed-form functions
//  Olaf Bachmann, Paul S. Wang, Eugene V. Zima
//
//  On computational properties of chains of recurrences
//  Eugene V. Zima
//
//  Symbolic Evaluation of Chains of Recurrences for Loop Optimization
//  Robert A. van Engelen
//
//  Efficient Symbolic Analysis for Optimizing Compilers
//  Robert A. van Engelen
//
//  Using the chains of recurrences algebra for data dependence testing and
//  induction variable substitution
//  MS Thesis, Johnie Birch
//
//===----------------------------------------------------------------------===//

根据Krister Walfridsson的这篇博客文章，它建立了递归链，可用于获得每个归纳变量的闭式公式。

这是完全推理和完全硬编码之间的中间点：

• 模式匹配用于构建递归链，因此 LLVM 可能无法识别表达某种计算的所有方式。
• 可以优化各种各样的公式，而不仅仅是三角形和。

文章还指出，优化最终可能会使代码悲观：如果"优化"代码需要比循环内部主体更多的操作，那么少量迭代可能会更快。

¹n * (n+1) / 2是用于计算[0, n]中数字之和的闭式函数。