编译器（特别是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;
}

并在Release中进行编译，我们得到：

; 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行，因此导航它有点复杂。仍然，主要评论暗示我们应该在正确的位置，并指向它使用的论文，其中提到了优化循环和闭式函数¹：

; 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
}

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

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

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

本文还指出，优化可能最终会使代码变得悲观：与循环内部相比，如果“优化”代码需要大量操作，则少量迭代可能会更快。

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