编译器(特别是rustc)真的可以简化三角求和以避免循环吗？多么? [英] Can compilers (specifically rustc) really simplify triangle-summation to avoid a loop? How?

问题描述

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

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

这当然是众所周知的等价物，但是编译器如何识别它呢？我猜它是在LLVM优化过程中进行的，但是LLVM是以某种方式从基本原理中推导出等价性，还是它只有一组可以简化为算术运算的"公共循环计算"？

推荐答案

首先，让我们演示一下实际发生的情况。

以此代码开始：

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

和compiling in 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多行，所以导航有点复杂；尽管如此，标题注释提示我们应该在正确的位置，并指向它使用的提到优化循环和封闭形式函数的论文¹：

 //===----------------------------------------------------------------------===//
 //
 // 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的this blog article，它建立了递归链，可以用来获得每个归纳变量的闭合公式。

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

• 模式匹配用于构建递归链，因此LLVM可能无法识别表示特定计算的所有方式。
• 可以优化的公式种类很多，而不仅仅是三角和。

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

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

这篇关于编译器(特别是rustc)真的可以简化三角求和以避免循环吗？多么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！