是标题党了啦。这是应对
VS为什么会生成这样的C++反汇编代码？ - 程序员问题而写个一个小例子。并没有啥高深新奇的知识，纯科普而已。
演示用的代码例子
先来看用于演示的C代码例子：
#include <stdint.h>
uint32_t gLastI;
uint32_t foo(uint32_t lo, uint32_t hi) {
uint32_t sum = 0; // (1)
for (uint32_t i = lo; i < hi; i++) { // (2)
uint32_t y = 2 * i; // (3)
if ((hi & 1) == 0) { // (4)
sum += i; // (5)
gLastI = i; // (6)
} else {
sum += y; // (7)
}
}
return sum; // (8)
}
挺简单的函数。有啥好优化的呢？——对于不熟悉编译原理的同学来说，最可能让他们意外的可能就是优化后代码的顺序与原程序的巨大差异。
ICC 17在Linux/x86-64上在-O3优化级别会把这个例子优化为等价于下面的形式：
uint32_t foo(uint32_t lo, uint32_t hi) {
uint32_t sum = 0;
if (lo < hi) {
uint32_t n = hi - lo;
if ((hi & 1) != 0) {
for (uint32_t i = 0; i < n; i++) {
sum += lo * 2; // folded into lea
sum += i * 2; // folded into lea
}
} else {
uint32_t last_i;
for (uint32_t i = 0; i < n; i++) {
sum += lo;
last_i = lo;
lo++;
}
gLastI = last_i;
}
}
return sum;
}
实际生成的汇编长这样：
foo:
mov edx, esi #5.35
xor eax, eax #6.11
cmp edi, edx #7.29
jae ..B1.9 # Prob 50% #7.29
mov esi, edx #5.35
mov ecx, eax #7.3
sub esi, edi #5.35
test dl, 1 #9.15
je ..B1.7 # Prob 50% #9.21
..B1.4: # Preds ..B1.2 ..B1.4
lea eax, DWORD PTR [rax+rdi*2] #7.3
lea eax, DWORD PTR [rax+rcx*2] #8.17
inc ecx #7.3
cmp ecx, esi #7.3
jb ..B1.4 # Prob 82% #7.3
jmp ..B1.9 # Prob 100% #7.3
..B1.7: # Preds ..B1.2 ..B1.7
inc ecx #7.3
add eax, edi #10.7
mov edx, edi #11.7
inc edi #7.3
cmp ecx, esi #7.3
jb ..B1.7 # Prob 82% #7.3
mov DWORD PTR gLastI[rip], edx #11.7
..B1.9: # Preds ..B1.4 ..B1.8 ..B1.1
ret #16.10
它为什么可以这样做？下面就让我简单民科科普一下。
先放个传送门：编译器生成的汇编语句执行顺序为什么与C代码顺序不同？ - RednaxelaFX 的回答。这个传送门里我的回答提到了编译器在优化代码的时候，只要保证最终的结果满足程序中各种依赖关系就可以了，而不必总是维持跟输入的源码相同的顺序（“program order”）。不过这个传送门中涉及的例子非常简单，只有纯直线代码，没有跳转 / 条件跳转，也没有对内存的读写，所以只要用“数据依赖”（data dependence）就足以讲解了。
而本文所用的例子则稍微复杂一点，可以涉及稍微多一些的优化的讲解。
首先在(2)开始有一个典型的for循环，在(4)有一个条件分支；这两个都是控制流操作，使这个例子涉及“控制依赖”（control dependence）。然后在(6)有一个对全局变量gLastI的写操作，这是一个内存写操作，使这个例子涉及“内存依赖”（memory dependence）——或者说正好演示了冗余写操作的情况。
============================================
副作用？
对编译器中的优化器来说，所谓“副作用”就是在当前编译单元中无法做足够分析的运算结果。这跟上层的源语言中所说的“副作用”并不总是一回事。所以当看到对程序中的副作用的讨论时，要注意清楚讨论的上下文是什么，免得误解了对方的意思。
例如说，对编译器中端的优化器来说，C语言的一个标量类型的局部变量，如果它在整个函数中都没有被取过地址，那么所有对它自身的读写运算都可以认为是“无副作用”的。这是因为这些变量是活动记录（activation record，或者说栈帧）的一部分，而一个函数被调用一次的活动记录里的内容都是这次调用独享访问的，除非程序主动通过取局部变量地址的方式来暴露出机会让别的代码能操作这些局部变量。这样编译器的优化器就可以对其做足够分析，将它们涉及的副作用都分析出来，并转换为没有副作用的形式。
而对原本的C语言来说，一般会把对局部变量的赋值（写）运算叫做“有副作用”的。
这个差异主要是来自编译器各部分的分工，以及优化器对程序的分析能力。
回顾一下一个典型的带优化的编译器的工作流程：
源代码
-> [ 词法分析 ]
-> 单词流
-> [ 语法分析 ]
-> 语法树 / 抽象语法树 编译器前端
-> [ 语义分析 ]
-> 带标注的语法树
-> [ 中间代码生成 ]
-> 中间代码 -------------------------
-> [ 平台无关优化 ]
-> 优化的中间代码 编译器中端
-> [ 平台相关lowering ]
-> 平台相关中间代码 --------------------------
-> [ 平台相关优化 ]
-> 优化的平台相关中间代码 编译器后端
-> [ 代码生成 ]
-> 目标代码在这个流程中，编译器前端更关心源语言的语义，后端更关心目标平台的特性，而位于中间的中端则主要关心相对不那么语言相关、也不那么平台相关的优化。
当我们讨论源语言层面上的“副作用”，编译器前端的“语义分析”部分是必须要能正确理解这些副作用的含义（并在副作用不合理时给出警告）。然后在“中间代码生成”的部分，这些“副作用”会在中间表示中用更显式的方式表现出来，于是到编译器中端拿到中间表示的时候，就不用关心这些源语言层面的副作用了。
例如说，一个经典的不好的C代码：
int foo() {
int i = 0;
int j = i + i++;
return j;
}在 i + i++ 的地方有一个纯粹的对局部变量i的读操作，以及一个带有副作用（自增）的对局部变量i的读写操作，而这两个操作之间没有sequence point所以它们俩的求值顺序是未定义的。
在Clang中，语义分析的部分会对这个情况给出警告：
foo.c:3:16: warning: unsequenced modification and access to 'i' [-Wunsequenced]
int j = i + i++;
~ ^
然后Clang在生成中间代码（LLVM IR）时，会根据自己的理解选择一种求值顺序——后做i++，生成出每个操作都简单明确的中间代码，然后编译器中端（LLVM）在拿到LLVM IR之后就能根据代码的顺序准确地理解前端所做的选择：
; Function Attrs: nounwind
define i32 @foo() #0 {
%i = alloca i32, align 4 ; int i
%j = alloca i32, align 4 ; int j
store i32 0, i32* %i, align 4 ; i = 0
%3 = load i32, i32* %i, align 4 ; tmp3 = i
%4 = load i32, i32* %i, align 4 ; tmp4 = i
%5 = add nsw i32 %4, 1 ; tmp5 = tmp4 + 1
store i32 %5, i32* %i, align 4 ; i = tmp5
%6 = add nsw i32 %3, %4 ; tmp6 = tmp3 + tmp4
store i32 %6, i32* %j, align 4 ; j = tmp6
%7 = load i32, i32* %j, align 4 ; tmp7 = j
ret i32 %7 ; return tmp7
}
也就是Clang选择拆解副作用的方式，对应这样的C代码：
int foo() {
int i = 0;
int j = i + i;
i = i + 1; // side-effect of i++
return j;
}可以看到这里生成的LLVM IR还是“有副作用”的——那3条store指令就是“副作用”。但是LLVM可以对所有没有被取地址的标量类型的局部变量都可以做完全的分析——可以找到所有对这些局部变量的读写操作并分析其中的副作用的效果——然后将IR转换到对这些局部变量来说没有副作用的形式。
例如说对上述LLVM IR跑一次mem2reg pass（或者包含mem2reg的sroa pass），会得到：
; Function Attrs: nounwind
define i32 @foo() #0 {
%1 = add nsw i32 0, 1 ; tmp1 = 0 + 1
%2 = add nsw i32 0, 0 ; tmp2 = 0 + 0
ret i32 %2 ; return tmp2
}
这里就没有任何副作用了，只有对局部值的简单运算。进一步做常量折叠和无用代码消除之后，就只剩下：
; Function Attrs: nounwind
define i32 @foo() #0 {
ret i32 0 ; return 0
}
了。
同一个例子用GCC 4.9.2来看编译器前端的理解（生成的GIMPLE）：
foo ()
{
int i.0;
int D.1748;
int i;
int j;
i = 0;
i.0 = i;
i = i.0 + 1; // side-effect of i++
j = i.0 + i;
D.1748 = j;
return D.1748;
}
这GCC选择的求值顺序就跟Clang正好相反，先做了i++。
然后中端在分析完局部变量涉及的副作用之后，所生成的无副作用的中间代码（Tree SSA形式的GIMPLE）：
foo ()
{
int j;
int i;
int D.1748;
int i.0;
int i.0_2;
int _5;
<bb 2>:
i_1 = 0;
i.0_2 = i_1;
i_3 = i.0_2 + 1;
j_4 = i.0_2 + i_3;
_5 = j_4;
<L0>:
return _5;
}
每个局部变量最多被赋值一次，从赋值到使用直接不用考虑别的副作用影响该变量的值，所以说“没有副作用”。
============================================
副作用与控制依赖
先说结论：没有副作用的运算可以无视控制依赖，只要满足数据依赖即可执行。
什么是控制依赖？控制依赖是说，某个运算Y的执行与否，依赖于某个带有控制流语义的运算X的结果。
例如说，
int foo(int a, int b, int cond) {
int c = b + 1;
int x = 0;
if (cond) {
x = a + c;
}
return x;
}这个例子里，"x = a + c"就控制依赖于"if (cond)"的运算结果，只有当cond为真值的时候，x = a + c才执行。
但是"a + c"是一个没有副作用的运算，它其实放在foo()中的什么位置执行都可以——只要它所依赖的数据输入a和c都已经求好值了即可——而不必依赖于"if (cond)"的结果。这跟本文开头提到的传送门里“数据依赖”的例子一样。
所以把上述代码的a + c提取到if外面，转换成下面这样也是一样的：
int foo(int a, int b, int cond) {
int c = b + 1;
int x = 0;
int tmp = a + c;
if (cond) {
x = tmp;
}
return x;
}
又或者再向前挪一点：
int foo(int a, int b, int cond) {
int c = b + 1;
int tmp = a + c;
int x = 0;
if (cond) {
x = tmp;
}
return x;
}
也可以。
那么"x = "的部分呢？这个赋值会根据"if (cond)"的结果而影响局部变量x的值，所以要先看作有控制依赖的有副作用的操作，分析清楚之后再转换到无副作用的形式。
但是所谓“无副作用”的形式要如何表达一个变量可能经由不同的分支执行后得到不同的值呢？一种办法是SSA形式的“phi”伪函数。让我们把这个例子转成SSA形式来看：
int foo(int a, int b, int cond) {
int c = b + 1;
int x0 = 0;
if (cond) goto condtrue; else goto condfalse;
condtrue:
int x1 = a + c;
goto aftercond;
condfalse:
goto aftercond;
aftercond:
int x2 = phi(condfalse x0, condtrue x1);
return x2;
}
这个“phi”伪函数会显式指明“如果控制来自某个分支，则选用某个值”。这就把副作用与控制依赖显式结合在一起表达出来了。
回到本文开头的例子，位于(3)的"2 * i"是一个无副作用的运算，所以它的运算位置可以被移动。例如说它可以被向下移动（sink），到真正使用它的地方，变成：
#include <stdint.h>
uint32_t gLastI;
uint32_t foo(uint32_t lo, uint32_t hi) {
uint32_t sum = 0;
for (uint32_t i = lo; i < hi; i++) {
if ((hi & 1) == 0) {
sum += i;
gLastI = i;
} else {
uint32_t y = 2 * i;
sum += y;
}
}
return sum;
}
============================================
循环不变量与循环不变量外提（LICM）
就跟上一节提到的思路一样，如果通过分析可以发现在循环中有运算的值不受循环的影响，那么就可以把它提升到循环的外面。这种优化叫做循环不变量外提（LICM，loop-invariant code motion）。
以本文开头的例子来说，通过分析可以发现从(2)开始的for循环，在循环体中没有对变量hi赋过值，所以hi的值在循环内不会改变。递推出去，hi & 1 是一个无副作用的运算，它的值在循环中也不会改变。同理 (hi & 1) == 0 的值在循环中也不会改变。
所以这个例子就可以把(4)的条件运算提取到循环外面，变成（在上一节的基础上）:
#include <stdint.h>
uint32_t gLastI;
uint32_t foo(uint32_t lo, uint32_t hi) {
uint32_t sum = 0;
_Bool tmpcond = (hi & 1) == 0;
for (uint32_t i = lo; i < hi; i++) {
if (tmpcond) {
sum += i;
gLastI = i;
} else {
uint32_t y = 2 * i;
sum += y;
}
}
return sum;
}
============================================
循环判断外提（loop unswitching）
作为LICM的一种扩展，如果我们发现循环里有条件是对循环不变量来做判断的，那么就可以选择把这个判断提升到循环的外面 ，并且把原循环拆分为两个特化的版本，分别对应条件为真以及为假的情况。
这样每个版本的循环都会比原本的更简单，而假定循环是耗时的操作，是我们要有针对性优化的目标，把循环拆分成特化的版本后就可以减小循环的开销。
还是回到本文开头的例子，在上一节版本的基础上，可以进一步变换为：
#include <stdint.h>
uint32_t gLastI;
uint32_t foo(uint32_t lo, uint32_t hi) {
uint32_t sum = 0;
if ((hi & 1) == 0) {
for (uint32_t i = lo; i < hi; i++) {
sum += i;
gLastI = i;
}
} else {
for (uint32_t i = lo; i < hi; i++) {
uint32_t y = 2 * i;
sum += y;
}
}
return sum;
}
跟开头演示的优化后的结果是不是越来越相似了？
============================================
内存写的下沉（store sinking）
嗯这个读起来有点怪。简单来说就是如果有连续多次对同一个位置的内存写操作，那么只有最后一个才是有意义的，前面那些只要没被用到都是无意义的，可以消除。所以这种优化也叫做“冗余内存写消除”（redundant store elimination）。
应用到循环中，如果我们在循环体中不断对某个位于内存中的变量做赋值，但却没有在循环中使用过这个赋值的结果，那么这个赋值就没有意义，可以被消除。
例如说：
for (int i = 0; i < 3; i++) {
globalVariable = i;
}全局变量globalVariable的实体必须要被分配在内存中，所以对它的赋值是一个内存写操作（memory store）。如果我们分析一下循环的执行过程 ，就会发现这个例子实际上会执行3次对globalVariable的赋值：
- globalVariable = 0
- globalVariable = 1
- globalVariable = 2
但在这个循环中其实并没有用到这些赋值的结果，而在循环结束时需要给外界留下的副作用只需要是globalVariable = 2。所以我们可以把这个内存写操作“下沉”（sink）到循环的后面去，变成：
for (int i = 0; i < 3; i++) {
/* empty loop body */
}
globalVariable = 2; // constant-folded condition: if (0 < 3)或者稍微没那么优化的版本：
int i;
for (i = 0; i < 3; i++) {
/* empty loop body */
}
globalVariable = i - 1; // constant-folded condition: if (0 < 3)
但要注意的是：一个for循环其实是有可能一次也不执行的，所以在循环体里的赋值如果被下沉到循环后面的话，要保证该循环至少执行过一次才正确。
回到本文开头的例子，在上一节版本的基础上，把(6)对全局变量gLastI的赋值下沉到循环后面，可以变换成：
#include <stdint.h>
uint32_t gLastI;
uint32_t foo(uint32_t lo, uint32_t hi) {
uint32_t sum = 0;
if (lo < hi) {
if ((hi & 1) == 0) {
for (uint32_t i = lo; i < hi; i++) {
sum += i;
}
gLastI = hi - 1;
} else {
for (uint32_t i = lo; i < hi; i++) {
uint32_t y = 2 * i;
sum += y;
}
}
}
return sum;
}
具体到ICC所选用的优化形式，它没能彻底优化掉循环中的运算，不过至少在循环中用一个局部变量来替代了全局变量作为赋值的目标，然后在循环之后才做最终的内存写操作：
uint32_t last_i;
for (uint32_t i = lo; i < hi; i++) {
sum += i;
last_i = i;
}
gLastI = last_i;
这仍然算是store sinking——局部变量可以被分配到寄存器里，对局部变量的赋值就不会内存写了，所以还是比对全局变量的赋值更快。
经过store sinking优化后，代码的形式已经跟ICC优化的结果非常相似了。
============================================
循环归纳变量优化（loop induction variable optimizations）
本文开头所给出的ICC优化后的版本，剩下的一些优化是跟循环归纳变量相关的。所谓“循环归纳变量”，就是值与循环轮次成线性关系的变量。
例如说最典型的for循环：
for (int i = 0; i < max; i++) {
int x = arr[i + 2];
/* ... */
}局部变量i就是一个循环归纳变量，它的值跟循环轮次正好相等。我们可以分析出这个变量i的性质为：
- init = 0
- limit = max
- cmp = <
- step = 1
而表达式 i + 2 的值也是跟循环轮次成线性关系的，关系为 1 * i + 2。于是这个表达式的性质就可以从变量i推算出来。
GCC与Clang对循环归纳变量的分析与优化叫做“Scalar evolutions”（简称SCEV）。
这边就不专门说明ICC是如何通过循环归纳变量分析来把本文开头的例子从上一节的版本优化到最终版本了。同学们有兴趣的话可以自己动手推推看 ^_^
事实上，既然这是一个等差数列求和的例子，比例子中ICC编译结果更简短的形式应该是这样的：
#include <stdint.h>
uint32_t gLastI;
uint32_t foo(uint32_t lo, uint32_t hi) {
if (lo < hi) {
uint32_t n = hi - lo;
if ((hi & 1) == 0) {
gLastI = hi - 1;
return (lo & 1) == 0 ? (n >> 1) * (lo + hi - 1)
: ((lo + hi - 1) >> 1) * n;
} else {
return (lo + hi - 1) * n;
}
} else {
return 0;
}
}
直接连循环都不要了。这个形式是否比ICC的编译结果更优化还是得看情况。应用怎样的编译分析与优化能得到这个形式，就留作课后习题吧。
把非常量的循环加法变换为非循环的乘法形式是实际编译器实现中比较少见的做法。更常见的反过来的优化：“强度削减”（strength reduction），把本来是乘法的运算变成加法，之类。
============================================
这次就先科普到这里。欢迎对本文的科普和分析拾遗补阙 ^_^
注：GCC与Clang与本文开头的例子编译出来的结果比ICC的更复杂一些，相关分析也留作课后作业啦。
专栏：编程语言与高级语言虚拟机杂谈（仮）
探讨编程语言的设计与实现