Scalar evolution技术与i^n求和优化
（如果不想看一开始的引例，想直接看Scalar evolution，可以直接跳过这个“引例”部分。）
引例
考虑\(i^3\)求和
\[S=\sum_{i=1}^n{i^3} \]其C语言代码为
#include <stdio.h>
int main() {
int n, s = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
s += i * i * i;
}
printf("%d\n", s);
return 0;
}
非常神奇的是，这个算法本身的时间复杂度是\(O(n)\)的。但是观察打开\(O3\)优化下的汇编指令可以发现，编译器将该算法优化成了\(O(1)\)复杂度的直接公式求解。本文将介绍分析该优化的具体表现，并介绍该优化的本质——标量演化编译优化技术。值得一提的是，虽然我们人为知道\(\sum i^3\)的求和公式为\((\frac{n(n+1)}{2})^2\)，但是编译器并不是靠”死记公式”去进行优化，而是以一种具有普遍意义的优化方式，循环幂次求和只是这种优化的很多种适用对象之一。
使用clang -S -O3观察其在O3优化下产生的汇编码，其计算\(s\)的主要部分为
leal -1(%rax), %ecx
leal -2(%rax), %edx
imulq %rcx, %rdx
leal -3(%rax), %ecx
imulq %rdx, %rcx
shrq %rdx
leal (%rdx,%rdx,8), %esi
leal (%rdx,%rsi,2), %edx
leal (%rdx,%rax,8), %edx
addl $-4, %eax
imulq %rcx, %rax
shrq %rcx
leal (%rcx,%rcx,2), %ecx
leal (%rdx,%rcx,2), %ecx
shrq $2, %rax
andl $-2, %eax
leal -7(%rax,%rcx), %ebx
可以分析出输入的n被存储在寄存器rax当中。n占据4个字节，所以其实eax当中已经被存有完整的n。我们用\(N\)来表示rax寄存器的值，于是我们可以假设
\[N=n \]然后首先分析前两行，
leal -1(%rax), %ecx
leal -2(%rax), %edx
64位x86处理器的寻址模式如下图所示
这里GPR表示通用寄存器（General Purpose Register）。而lea指令表示取有效地址，将有效地址的运算结果存储到一个寄存器中。所以，lea字面意思是取有效地址，实际上还可以用来做一些简单的计算。
在这个代码中，
leal -1(%rax), %ecx
相对rax寄存器偏移量为-1的有效地址就是\(rax-1\)。也就是说这一句话等价于
\[ecx\leftarrow N-1 \]因为ecx是32位的寄存器，实际上是把\(rax-1\)的低32位放入\(ecx\)。我们将\(rcx\)记为一个临时变量\(t1\)。进一步翻译为
\[t_1\leftarrow N-1 \]下一行代码等价于
\[t_2\leftarrow N-2 \]然后是一条有符号乘法指令
imulq %rcx, %rdx
等价于
\[t_2\leftarrow t_2\times t_1 \]利用相同的方法对剩余的代码进行翻译。最后得到等价的算法为
\[N=n \\ t_1\leftarrow N-1 \\ t_2\leftarrow N-2 \\ t_2\leftarrow t_2\times t_1 \\ t_1\leftarrow N-3 \\ t_1\leftarrow t_1\times t_2 \\ t_2\leftarrow \frac{t_2}{2} \\ t_3\leftarrow t_2+8t_2=9t_2 \\ t_2\leftarrow t_2+2t_3 \\ t_2\leftarrow t_2+8N \\ N\leftarrow N-4 \\ N\leftarrow N\times t_1 \\ t_1\leftarrow \frac{t_1}{2} \\ t_1\leftarrow t_1+2t_1=3t_1 \\ t_1\leftarrow t_2+2t_1 \\ N\leftarrow \frac{N}{4} \\ N\leftarrow N\&(-2) \\ result\leftarrow N+t_1-7 \]为了验证我们的人工转换是否正确，我们将这个算法写成另外一份C代码，
#include <stdio.h>
int main() {
int N, n, s = 0;
scanf("%d", &n);
long long t1, t2, t3, result;
N = n;
t1 = N - 1;
t2 = N - 2;
t2 = t2 * t1;
t1 = N - 3;
t1 = t1 * t2;
t2 = t2 / 2;
t3 = 9 * t2;
t2 = t2 + 2 * t3;
t2 = t2 + 8 * N;
N = N - 4;
N = N * t1;
t1 = t1 / 2;
t1 = 3 * t1;
t1 = t2 + 2 * t1;
N = N / 4;
N = N & (-2);
result = N + t1 - 7;
printf("%lld\n", result);
return 0;
}
测试了几组我们发现完全正确。那么这个算法是如何计算\(i^3\)求和的呢？分析如下：
\[N\leftarrow n \\ t_1\leftarrow N-1\leftarrow n-1 \\ t_2\leftarrow N-2\leftarrow n-2 \\ t_2\leftarrow t_2\times t_1 \leftarrow(n-1)(n-2) \\ t_1\leftarrow N -3 \leftarrow n-3\\ t_1\leftarrow t_1\times t_2 \leftarrow (n-3)(n-1)(n-2) \\ t_2\leftarrow \frac{t_2}{2} \leftarrow \frac{(n-1)(n-2)}{2} \\ t_3\leftarrow t_2+8t_2=9t_2 \leftarrow \frac{9(n-1)(n-2)}{2} \\ t_2\leftarrow t_2+2t_3 \leftarrow \frac{(n-1)(n-2)}{2}+9(n-1)(n-2) \leftarrow \frac{19(n-1)(n-2)}{2} \\ t_2\leftarrow t_2+8N \leftarrow \frac{19(n-1)(n-2)}{2}+8n \\ N\leftarrow N-4 \leftarrow (n-4)\\ N\leftarrow N\times t_1\leftarrow (n-1)(n-2)(n-3)(n-4) \\ t_1\leftarrow \frac{t_1}{2}\leftarrow \frac{(n-1)(n-2)(n-3)}{2} \\ t_1\leftarrow t_1+2t_1=3t_1\leftarrow \frac{3(n-1)(n-2)(n-3)}{2} \\ t_1\leftarrow t_2+2t_1 \leftarrow \frac{19(n-1)(n-2)}{2}+8n+3(n-1)(n-2)(n-3) \\ N\leftarrow \frac{N}{4} \leftarrow \frac{(n-1)(n-2)(n-3)(n-4)}{4}\\ \]下面还剩
\[N\leftarrow N\&(-2) \\ result\leftarrow N+t_1-7 \]没有分析，因为我们卡在了\(N\leftarrow N\&(-2)\)上。这一句是什么意思？
考虑\(-2\)这个二进制数。\(-2\)的原码为\((10)_2\)，反码为\((1111...01)_2\)，则补码为\((11111111110)_2\)。\(\&\)运算符是按每一个二进制位与。所以，\(N\leftarrow N\&(-2)\)，本质上就是把\(N\)的前面的位都保持不变，而最后一位强制变为0。
实际上，因为我们知道，因为现在\(N\)已经被设置为
\[\frac{(n-1)(n-2)(n-3)(n-4)}{4} \]当\(n=2k\)的时候，\(N=(k-1)(k-2)(2k-1)(2k-3)\)。容易知道，\((k-1)(k-2)\)必然为偶数，而\((2k-1)(2k-3)\)必然为奇数。所以，\(N\)为偶数，而偶数的最后一位为0，也就是\(N\&(-2)=N\)。
当\(n=2k+1\)的时候，\(N=(2k-1)k(2k-3)(k-1)\)。同理，这个数仍然是偶数。也有\(N\&(-2)=N\)。
所以现在这个\(N\)一定是一个偶数。偶数的最后一位二进制位本来就是0。于是，这一句\(N\leftarrow N\&(-2)\)，实际上并不会改变\(N\)的值。
最后一句，就相当于
\[result\leftarrow N+t_1-7=\frac{(n-1)(n-2)(n-3)(n-4)}{4}+\frac{19(n-1)(n-2)}{2}+8n+3(n-1)(n-2)(n-3)-7 \]下面证明
\[1^3+2^3+...+n^3=\frac{(n-1)(n-2)(n-3)(n-4)}{4}+\frac{19(n-1)(n-2)}{2}+8n+3(n-1)(n-2)(n-3)-7 \]设\(F(n)=\frac{(n-1)(n-2)(n-3)(n-4)}{4}+\frac{19(n-1)(n-2)}{2}+8n+3(n-1)(n-2)(n-3)-7\)。
考虑数学归纳法。
当\(n=1\)的时候，\(1=F(1)=1\)，结论成立。
当\(n=k\)的时候，需要证明
\[1^3+2^3+...+k^3=F(k) \]即证明
\[F(k-1)+k^3=F(k) \]即证明
\[k^3=F(k)-F(k-1) \]容易知道
\[F(k)-F(k-1)=\frac{(k-2)(k-3)(k-4)(k-1-(k-5))}{4}+\frac{19(k-2)(k-1-(k-3))}{2}+8+3(k-2)(k-3)(k-1-(k-4)) \\ =(k-2)(k-3)(k-4)+19(k-2)+8+9(k-2)(k-3) \\ =k^3-9k^2+26k-24+19k-30+9k^2-45k+54\\ =k^3 \]可以看出，编译优化之后，编译器使用公式进行了求和，并且公式与直接求和是等价的。
本质探究
标量演化技术概述
Scalar evolution（SCEV）技术是一种现代化的高级编译优化技术。该技术主要用于分析循环中变量是如何被更新的，然后根据这个信息来进行优化。
引入
SCEV的核心是下列表示：
\[var=\{start,\phi,step\} \]我们将这种表示称为循环链（chrec，Chains of Recurrences），至于为什么这么称呼，在后面就会介绍。其中，\(\phi\)为一个二元运算符且\(\phi\in\{+,*\}\)。也就是说，循环里的每一个标量变量\(var\)，都可以用起始值（\(start\))，步长（\(step\)）和更新方式（\(\phi\)）三个参数来体现。值得注意的是，SCEV仅适用于标量（往往只针对整数类型）。而整数类型的变量在循环中用到的几率是非常大的。可以说，这种优化技术是“加速大概率事件”伟大思想的一种体现。
下面举个例子，考虑下面的循环：
int j = 10;
for (int i = 0; i < n; i++) {
k = i + j;
printf("%d\n", k);
j = j + 2;
}
这种表示方式可以清晰地体现一个变量在循环中的变化。\(i\)是一个变量，它从0开始，每次+1，于是记\(i=\{0,+,1\}\)。\(j\)是一个变量，从10开始，每次+2，则记\(j=\{10,+,2\}\)。
\[i=\{0,+,1\} \\ j=\{10,+,2\} \\ \]那么\(k\)怎么表示呢？实际上，循环链算式可以进行代数运算：
\[k=i+j=\{0,+,1\}+\{10,+,2\}=\{10,+,3\} \]直观角度讲这也是显然的。\(k=i+j\)，说明\(k\)将会从\(i+j\)的初值，也就是10开始，步长为\(i\)、\(j\)步长的和。
这样一来，循环就可以改写为：
int j = 10, k = 10;
for (int i = 0; i < n; i++) {
printf("%d\n", k);
k = k + 3;
j = j + 2;
}
这样你可能会说，这有什么意义呢？比如在MIPS汇编中，这个\(k=k+3\)，和\(k=i+j\)，都对应了一条加法指令，占用着一个时钟周期，看起来也没啥优化呀。但是万一情况变成下面这样，
int p = 1, q = 2, r = 3, s = 4;
for (int i = 0; i < n; i++) {
k = p + 2 * q + 3 * r + s;
printf("%d\n", k);
p = p + 2;
q = q + 3;
r = r + 1;
s = s + 5;
}
使用标量演化，则可知
\[k=p+2q+3r+s \\ =\{1,+,2\}+2\{2,+,3\}+3\{3,+,1\}+\{4,+,5\} \\ =\{1,+,2\}+\{4,+,6\}+\{9,+,3\}+\{4,+,5\} \\ =\{18,+,16\} \]则代码可以被优化为
int p = 1, q = 2, r = 3, s = 4, k = 18;
for (int i = 0; i < n; i++) {
printf("%d\n", k);
k = k + 16;
p = p + 2;
q = q + 3;
r = r + 1;
s = s + 5;
}
这下优化就明显了！原本计算\(k\)需要3条加法指令，2条乘法指令。而现在，只需要1条加法指令！这一点在矩阵运算中，有更明显的优势。比如计算矩阵加法时：
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
c[i][j] = a[i][j] + b[i][j];
}
}
编译器首先将数组运算转换为地址运算
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
p = i * n + j;
*(c + p) = *(a + p) + *(b + p);
}
}
对于内层循环，我们发现i和n是与这层循环的循环变量\(j\)无关的，我们称\(i\)、\(n\)为关于\(j\)的循环不变量（Loop invariant）。于是，考虑\(p\)的chrec：
\[p=j+i*n=\{0,+,1\}+i*n=\{i*n,+,1\} \]于是，循环可以被优化为
for (int i = 0; i < n; i++) {
p = i * n;
for (int j = 0; j < n; j++) {
*(c + p) = *(a + p) + *(b + p);
p = p + 1;
}
}
下面对外层循环优化。此时，只有\(n\)为循环不变量。考虑\(p\)的chrec：
\[p=i*n=\{0,+,1\}*n=\{0,+,n\} \]于是，将\(p\)进一步优化，
p = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
*(c + p) = *(a + p) + *(b + p);
p = p + 1;
}
p = p + n;
}
我们分析一下，优化前，为了计算\(p\)地址，需要进行\(n^2\)次乘法运算，\(n^2\)次加法运算。而优化之后，只需要进行\(n^2+n\)次加法运算。并且我们知道，乘法运算的时钟周期数大于加法运算的周期数（乘法运算电路耗时较大）。可以看出，使用了标量演化优化之后，性能提升还是非常大的！
对于更加复杂的情况，又怎么办呢？比如这样的循环：
int j = 10;
for (int i = 0; i < n; i++) {
printf("%d\n", x);
x = i * j;
j = j + 2;
}
我们先从直观上理解。\(i\)和\(j\)的变化我们非常清楚。而\(x\)的变化（步长）怎么去体现？显然，
\[x_k=i_kj_k \]其中\(i_k\)表示循环到第\(k\)次时\(i\)的值，\(j_k\)表示循环到第\(k\)次时\(j\)的值。那么，\(x\)的步长应该是
\[step_x=x_k-x_{k-1}=i_kj_k-i_{k-1}j_{k-1}=(i_{k-1}+1)(j_{k-1}+2)-i_{k-1}j_{k-1}=2i_{k-1}+j_{k-1}+2 \]可以看出，如果引入新的一个中间变量
\[t=2i+j+2 \]那么\(x\)的步长可以表示为\(t\)。也就是
\[x=\{0,+,t\} \]而对于\(t\)，有
\[t\\ =2i+j+2\\ =2\{0,+,1\}+\{10,+,2\}+2\\ =\{0,+,2\}+\{10,+,2\}+2\\ =\{10,+,4\}+2\\ =\{12,+,4\} \]于是，可以记
\[x=\{0,+,\{12,+,4\}\} \]在刚才，我们还有一个重要发现，也就是考虑
\[\{\phi_0,+,\phi_1\}*\{\delta_0,+,\delta_1\} \]设\(x=\{\phi_0,+,\phi_1\}\)，\(y=\{\delta_0,+,\delta_1\}\)，则
\[start_{xy}=\phi_0\delta_0 \] \[step_{xy}=x_ky_k-x_{k-1}y_{k-1}=(x_{k-1}+\phi_1)(y_{k-1}+\delta_1)-x_{k-1}y_{k-1} \\ =\delta_1x_{k-1}+\phi_1y_{k-1}+\phi_1\delta_1 \]故
\[xy=\{\phi_0\delta_0,+,\delta_1x+\phi_1y+\phi_1\delta_1\} \\ =\{\phi_0\delta_0,+,\delta_1\{\phi_0,+,\phi1\}+\phi_1\{\delta_0,+,\delta_1\}+\phi_1\delta_1\} \]也就是说，我们得到了公式
\[\{\phi_0,+,\phi_1\}*\{\delta_0,+,\delta_1\}=\{\phi_0\delta_0,+,\delta_1\{\phi_0,+,\phi1\}+\phi_1\{\delta_0,+,\delta_1\}+\phi_1\delta_1\} \]如果\(\delta_1\)和\(\phi_1\)为常数，则公式还可以表示为
\[\{\phi_0,+,\phi_1\}*\{\delta_0,+,\delta_1\}=\{\phi_0\delta_0,+,\{\delta_1\phi_0+\phi_1\delta_0+\phi_1\delta_1,+,2\delta_1\phi1\}\} \]我们将嵌套的大括号的层数成为标量演化公式的阶数。也就是说，乘积形式（高次）的循环链，可以被展开成高一阶的和形式的循环链。出于简化书写，将
\[\{X,\phi_1,\{Y,\phi_2,Z\}\} \]简写为
\[\{X,\phi_1,Y,\phi_2,Z\} \]类似地，
\[\{X,\phi_1,\{Y,\phi_2,\{Z,\phi_3,M\}\}\} \]被简写为
\[\{X,\phi_1,Y,\phi_2,Z,\phi_3,M\} \]此时，如果\(\delta_1\)和\(\phi_1\)为常数，刚才的乘积公式就变成
\[\{\phi_0,+,\phi_1\}*\{\delta_0,+,\delta_1\}=\{\phi_0\delta_0,+,\delta_1\phi_0+\phi_1\delta_0+\phi_1\delta_1,+,2\delta_1\phi1\} \]我们发现，这种结构是一种链式的结构。对于一个循环链，它的步长要么为一个常数，要么为另一个循环链。这就是“循环链”名字的含义（个人理解）。
深入
首先我们对刚才的研究做一些总结。我们定义几个基本公式：
循环链
\[\{\alpha,\phi,\beta\} \]其中\(\alpha\)必须要是一个常数，\(\phi\)是一个二元运算符，\(\phi\in\{+,*\}\)。\(\beta\)可能是一个循环链，也可能是一个常数。
线性
对于常数\(\alpha\)和\(\beta\)，
\[\alpha*\{\phi_0,+,\phi_1\}+\beta*\{\delta_0,+,\delta_1\}=\{\alpha\phi_0+\beta\delta_0,\alpha\phi_1+\beta\delta_1\} \]乘积形式
\[\{\phi_0,+,\phi_1\}*\{\delta_0,+,\delta_1\}=\{\phi_0\delta_0,+,\delta_1\{\phi_0,+,\phi1\}+\phi_1\{\delta_0,+,\delta_1\}+\phi_1\delta_1\} \]有了这些定义，我们做一些更复杂的考虑。实际上，如果多项式次数更高，我们仍然可以用循环链来刻画。比如，
for (int i = 1; i <= n; i++) {
s = i * i * i;
printf("%d\n", s);
}
（注意这里讨论的是\(s=\)，而不是前面那个+=）
此时，\(s=i^3\)，考虑\(s\)，
\[s=i^3=\{1,+,1\}^3 \\ =(\{1,+,1\}\{1,+,1\})\{1,+,1\} \\ =\{1,+,\{3,+,2\}\}\{1,+,1\} \\ =\{1,+,\{1,+,1\}*\{3,+,2\}+\{1,+,3,+,2\}*1+\{3,+,2\}*1\} \\ =\{1,+,\{3,+,7,+,4\}+\{1,+,3,+,2\}+\{3,+,2\}\} \\ =\{1,+,\{4,+,\{10,+,6\}\}+\{3,+,2\}\} \\ =\{1,+,\{7,+,2+\{10,+,6\}\}\} \\ =\{1,+,\{7,+,\{12,+,6\}\}\} \\ =\{1,+,7,+,12,+,6\} \]太优美了！于是，我们可以将其优化为
int t1 = 1, t2 = 7, t3 = 12;
int n = 5;
for (int i = 1; i <= n; i++) {
printf("%d\n", t1);
t1 += t2;
t2 += t3;
t3 += 6;
}
对比一下，之前需要\(2n\)条乘法指令，而现在，只需要\(3n\)条加法指令。而乘法指令比加法指令慢的远不止1.5倍。显然快多了。
s = 0;
for (int i = 1; i <= n; i++) {
s += i * i * i;
}
我们发现，
\[s=\{0,+,i^3\}=\{0,+,1,+,7,+,12,+,6\} \]体现到代码上，
int t0 = 0, t1 = 1, t2 = 7, t3 = 12;
int n = 5;
for (int i = 1; i <= n; i++) {
t0 = t0 + t1;
t1 += t2;
t2 += t3;
t3 += 6;
}
最终的运算结果，将在\(t0\)当中保存。但是我们发现，这样虽然性能有很大提升，但还没有到之前连循环都没了的程度啊。这样实际上也是\(O(n)\)的，只不过复杂度当中的常数更小了。
我们需要观察这个求和。我们发现，这个求和的过程中，这个循环中间尽管\(s\)在不断变化，但是我们不需要追踪它的变化（也就是说我们不需要知道\(s\)的中间值），只需要知道循环结束之后\(s\)是多少！
现在再回来考虑我们的循环链
\[var=\{\alpha,\phi,\beta\} \]当我们不在意\(var\)的中间变化的时候，实际上我们完全可以用数学方法推出，该循环过程执行了\(k\)次之后，\(var\)是多少。而不需要借助于程序。比如最简单的
\[var=\{0,+,3\} \]我们可以直接得到循环3次后，\(var=9\)。那么对于一般情况
\[var=\{\alpha,\phi,\beta\} \]为了方便从高中的数列递推角度考虑，我们设该循环链为\(n\)阶，并改写为
\[var=a_n=\{\alpha_n,\phi,a_{n-1}\} \]其中\(a_0\)为一个常数\(c\)。并且，用\(a_n^{(k)}\)表示循环变量\(a_n\)在循环\(k\)次之后的值。可以列出等式
\[a_n^{(i)}-a_n^{(i-1)}=a_{n-1}^{(i-1)} \]全部写出来，
\[a_n^{(i)}-a_n^{(i-1)}=a_{n-1}^{(i-1)} \\ a_n^{(i-1)}-a_n^{(i-2)}=a_{n-1}^{(i-2)} \\ a_n^{(i-2)}-a_n^{(i-3)}=a_{n-1}^{(i-3)} \\ ... \\ a_n^{(1)}-a_n^{(0)}=a_{n-1}^{(0)} \]将上面这组算式求和得到
\[a_n^{(i)}=\alpha_n+\sum_{k=0}^{i-1}a_{n-1}^{(k)} \\ =\alpha_n+a_{n-1}^{(0)}+a_{n-1}^{(1)}+a_{n-1}^{(2)}+\cdots+a_{n-1}^{(i-1)} \]写到这里有的读者可能已经懵了，建议先展开算几项找找感觉再继续看。如果你写了几项，就会发现，最后的答案，一定是\(\alpha_1\)，\(\alpha_2\)，\(...\)，\(\alpha_{n}\)的一个线性组合。
接下来就可以从每一个\(\alpha\)对答案的贡献考虑了。
对于\(\alpha_n\)，只会在最开始被加1次。而\(1=C_i^0\)。
对于\(\alpha_{n-1}\)，在\(a_{n-1}^{(0)}\)、\(a_{n-1}^{(1)}\)、\(\cdots\)、\(a_{n-1}^{(i-1)}\)中分别被加1次，故总共被加\(i=C_i^1\)次。
对于\(\alpha_{n-2}\)，在\(a_{n-1}^{(1)}\)中被加1次，在\(a_{n-1}^{(2)}\)中被加2次，\(\cdots\)，在\(a_{n-1}^{(i-1)}\)被加\(i-1\)次，故总共被加\(\frac{i(i-1)}{2}=C_i^2\)次。
数学直觉告诉我们，不妨猜想\(\alpha_{n-k}\)的贡献为\(C_i^k\alpha_{n-k}\)次。实际上事实就是这样。但是笔者还没有想出严谨的证明方式，只是直观理解。
于是，可知\(a_n^{(i)}=\sum_{j=0}^iC_i^j\alpha_{n-j}\)。
如果写成更加好看的形式，也就是设
\[var=\{\phi_0,+,\phi_1,+,\phi_2,+,\cdots,+,\phi_n\} \]则可知\(var\)在第\(i\)次循环中的值为
\[var_i=\phi_0C_i^0+\phi_1C_i^1+\phi_2C_i^2+\cdots+\phi_{min\{i,n\}}C_i^{min\{i,n\}} \]这是非常精妙的结论。于是，对于刚才的三次求和的\(s\)，
\[s=\{0,+,1,+,7,+,12,+,6\} \]可知\(s\)在\(n\)次循环后的值为
\[s=n+\frac{7n(n-1)}{2}+\frac{12n(n-1)(n-2)}{6}+\frac{6n(n-1)(n-2)(n-3)}{24} \]于是，编译器只要生成计算上面这个式子的代码即可。我们发现，这个式子和之前给出的三次方求和，我们人为反编译出来看到的式子是神似的（可能有些细节不同，但是是完全等价的）。可以说明编译器优化求和的本质原理就在这里。