O2优化如何计算faulhaber公式？

Question

考虑这样一个 C 程序

int fn(int n){
    int sum = 0;
    for(int i = 1; i <= n; i++)
        sum += i*i;
    return sum;
}

int main(){
    int n;
    scanf("%d",&n);
    printf("%d\n",fn(n));
    return 0;
}

在这个程序中，我使用循环来计算faulhaber的公式。

在数学中，我们知道对于任何 k 次方和，我们有一个公式可以在 O(1) 时间内计算它。

但是，编译器可以发现这是一个 faulhaber 的公式，并且可以非常有效地计算它。上面的程序可以像这样用O2翻译成IR

define dso_local i32 @fn(i32 %0) local_unnamed_addr #0 {
  %2 = icmp slt i32 %0, 1
  br i1 %2, label %22, label %3

3:                                                ; preds = %1
  %4 = add nsw i32 %0, -1
  %5 = zext i32 %4 to i33
  %6 = add nsw i32 %0, -2
  %7 = zext i32 %6 to i33
  %8 = mul i33 %5, %7
  %9 = add nsw i32 %0, -3
  %10 = zext i32 %9 to i33
  %11 = mul i33 %8, %10
  %12 = lshr i33 %11, 1
  %13 = trunc i33 %12 to i32
  %14 = mul i32 %13, 1431655766
  %15 = lshr i33 %8, 1
  %16 = trunc i33 %15 to i32
  %17 = mul i32 %16, 5
  %18 = add i32 %14, %17
  %19 = shl i32 %0, 2
  %20 = add i32 %18, %19
  %21 = add i32 %20, -3
  br label %22

22:                                               ; preds = %3, %1
  %23 = phi i32 [ 0, %1 ], [ %21, %3 ]
  ret i32 %23
}

翻译后的程序几乎不用时间计算和，即使我用

i*i*i

之类的，编译器也可以做到。

我对优化很感兴趣，但我不知道Clang/gcc是如何实现上述问题的。