编译器（特别是rustc）是否能真正简化三角形求和过程，避免使用循环？如何实现？

Question

在Blandy和Orendorff的《Programming Rust》的322页上提到了如下说法：

......Rust认识到，计算从1到n的数字的和有一种更简单的方法：总和始终等于n *（n + 1）/ 2。

当然，这是一个相当著名的等式，但编译器如何识别它呢？我猜这是在LLVM优化中完成的，但LLVM是否从基本原理推导出该等式，还是仅拥有一些可以简化为算术运算的“常见循环计算”集合？

- Kyle Strand

---

Haskell 在 LLVM 启动之前会发生一些类似的事情。但据我所知，Rust 编译器完全可以采用不同的方法。（在 rustc 源代码中没有一个文件夹的名称让我想到“这是要查看的文件夹”） - Jeremy List

@JeremyList 哦，那么这可能比我想象的更具有语言特定性。我已经添加了 rust 标签。 - Kyle Strand

这个等价关系实际上是其他几种等价关系的组合——（部分）循环展开、常量折叠、算术运算的重新排序——这些优化器（实际上是LLVM的优化器）都能够完成。我不确定你是否认为这是“从第一原理”得出的，但我并不觉得它能够自行发现这种等价关系有多惊讶。 - trent

@trentcl：我有疑虑。我可以看到一个“愚蠢”的优化器计算任何在编译时已知参数的纯函数；但是，推导出这样的公式稍微复杂一些。推导封闭形式需要进行一些符号推理。 我的翻译：我有疑虑。我可以想象一个“简单”的优化器能够计算那些在编译时已知参数的纯函数；但是推导出这样的公式则要更加复杂一些。推导封闭形式需要进行一些符号推理。 - Matthieu M.

@trentcl：我修改了我的答案，感谢Krister Walfridsson的这篇文章（https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geometric-sums.html）。看起来LLVM会进行一部分工作：通过模式匹配来建立递归链，然后将其“简化”为封闭形式，从而使其能够应用于大量循环的优化。 - Matthieu M.

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的声明。

---

关于这是如何发生的，我的理解是这全部发生在LLVM中的ScalarEvolution.cpp。不幸的是，那个文件有12,000多行，所以导航起来有点复杂；不过，头注释暗示我们应该在正确的位置，并指向了它所使用的论文，其中提到了优化循环和闭式函数¹：

 //===----------------------------------------------------------------------===//
 //
 // 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]范围内数字总和的闭式函数。

- Matthieu M.