现代C／C++编译器有多智能？能做出什么厉害的优化？

话题太大，码字花时间…

先放传送门好了。

请看Google的C++编译器组老大Chandler Carruth的演讲。这个演讲是从编译器研发工程师的角度出发，以Clang/LLVM编译C++为例，向一般C++程序员介绍理解编译器优化的思维模型。它讲解了C++编译器会做的一些常见优化，而不会深入到LLVM具体是如何实现这些优化的，所以即使不懂编译原理的C++程序员看这个演讲也不会有压力。

Understanding Compiler Optimization - Chandler Carruth - Opening Keynote Meeting C++ 2015

演示稿：https://meetingcpp.com/tl_files/mcpp/2015/talks/meetingcxx_2015-understanding_compiler_optimization_themed_copy.pdf

录像：https://www.youtube.com/watch?v=FnGCDLhaxKU（打不开请自备工具…）

Agner Fog写的优化手册也永远是值得参考的文档。其中的C++优化手册：

要稍微深入一点的话，GCC和LLVM的文档其实都对各自的内部实现有不错的介绍。

GCC：

LLVM：

========================================

反模式（anti-patterns）

1. 为了“优化”而减少源码中局部变量的个数

这可能是最没用的手工“优化”了。特别是遇到在高级语言中“不用临时变量来交换两个变量”这种场景的时候。

看另一个问题有感：

2. 为了“优化”而把应该传值的参数改为传引用

（待续…）

举个微小的例子，一到一百求和

#include <stdio.h> 
int sum(){
  int ret=0;
  int i;
  for(i=1; i <=100; i++) ret+=i;
  return ret;
}
int main(){
  printf("%d\
", sum());
  return 0;
}

不开优化编译，汇编代码还挺正常的，乖乖做loop
.LBB0_1: #=>This Inner Loop Header: Depth=1
cmpl $100, -8(%rbp)
jg .LBB0_4
# BB#2: # in Loop: Header=BB0_1 Depth=1
movl -8(%rbp), %eax
movl -4(%rbp), %ecx
addl %eax, %ecx
movl %ecx, -4(%rbp)

开优化再看看汇编，clang -O2 -S sum.c
output:
# BB#0:
movl $5050, %eax # imm=0x13BA
ret
...
.Ltmp2:
.cfi_def_cfa_offset 16
movl $.L.str, %edi
movl $5050, %esi # imm=0x13BA
xorl %eax, %eax
callq printf
xorl %eax, %eax
popq %rdx
ret

卧槽，5050是个什么鬼！编译器大哥你能不能严肃点，直接把结果算出来是怎么回事。
编译器：算一加到一百都要写循环，妈的智障。

介于编译器会高斯求和法，估计大约是高斯十岁的水平【大误

利用C++11的range-based for loop语法可以实现类似python里的range生成器，也就是实现一个range对象，使得

for(auto i : range(start, stop, step))

功能上相当于

for(auto i = start, i < stop; i += step) 

一个简单的实现如下：

#include<iostream>
using std::cout;

class range_iterator {
public:
    range_iterator(int value, int step): value(value), step(step) {}
    range_iterator& operator++() { value += step; return *this; }
    bool operator!=(const range_iterator& other) { return value < other.value; }
    int& operator*() { return value; }
private:
    int value, step;
};

class range {
public:
    range(int start, int stop, int step): start(start), stop(stop), step(step) {}
    range_iterator begin() { return range_iterator(start, step); }
    range_iterator end() { return range_iterator(stop, step); }
private:
    int start, stop, step;
};


int main() {
    int op, ed, step;
    std::cin >> op >> ed >> step;

    for (int i : range(op, ed, step)) {
        std::cout << i << std::endl;
    }
    system("pause");
}

用VS2015在release下编译，看下反汇编：

可以发现根本没有实例化过任何range和range_iterator对象，for循环里的内容已经被优化成了

for(int i=op; i < ed; i +=step)

我所知道的现在两个compiler大的方向是LTO跟autoFDO

link time optimization 简单来说就是在link stage的时候再做一遍优化。现在所有的优化都是在生成.o 文件的时候做的，在链接的时候其实可以做更多的优化。 llvm给的例子如下

--- a.h ---
extern int foo1(void);
extern void foo2(void);
extern void foo4(void);

--- a.c ---
#include "a.h"

static signed int i=0;

void foo2(void){
  i=-1;
}

static int foo3(){
  foo4();
  return 10;
}

int foo1(void){
  int data=0;

  if (i < 0)
    data=foo3();

  data=data + 42;
  return data;
}

--- main.c ---
#include <stdio.h>
#include "a.h"

void foo4(void){
  printf("Hi\
");
}

int main(){
  return foo1();
}

linker在看到所有文件之后发现

1. foo2() 永远不会被调用，可以把foo2删掉

2. i 永远是0哦，没有人会改i 了

2. 那么i 永远不会小于0， foo3 也不回被调用，if 和foo3 全部删！删！删！

3.最后foo4 也可以被删掉，因为没人调用

这里给的例子相对trivial，但是大家可以大致理解为什么LTO厉害了吧。有上帝视角哦。

LTO的坏处是：

编译实在是太慢了！太慢了！大的软件上面要用LTO简直让人抓狂

FDO 是feedback driven optimization。很多Java的人都吹说jvm可以一边跑一边自动优化，现在通过FDO，c++的compiler也可以啦！

FDO的坏处是：

设置特别麻烦，对小公司来说现在还是太昂贵了。大公司基本上得在自己的服务器上定时去搜集这些信息，然后在编译时间总结一下。这个系统这是得大把真金白银砸出来的

看到高票答主

的回答提到了整数求和累加的优化，

我来说明下编译器的实现原理吧。

以如下代码为例，省略了其他无关代码：

int sum = 0;
for (int i = 0; i < 100; i++)
{
  sum += i;
}
return sum;// 任意一条使用sum的语句

首先我们先转换为SSA形式(

)的IR，这才能体现出编译器做的优化。

EntryBB:
i_0=0
sum_0=0

condBB:
i_2=phi(i_0, i_1)      # i_0来自于基本块EntryBB, i_1来自于基本块bodyBB
sum_2=phi(sum_0, sum_1)
br i_2 < 100, bodyBB, endBB  #　当条件i_2 < 100为真时，跳转到bodyBB,否则跳转到endBB

bodyBB:
r1=sum_2 + i_2
sum_1=r1
i_1=i_2 + 1
goto condBB

endBB:
return sum_2

为了得到

所示代码中的结果，编译器会执行归纳标量简化优化(

)。但是在执行这项优化之前，编译器会执行一趟分析趟——标量演化(Scalar Evolution)，该项优化是针对循环链(chain of recurrencce)来处理的

1.

2.

3.

4.

5.

6.

用于确定每个标量在每次循环迭代的时候，值是多少，循环的迭代次数等。

那么以上述代码为例，我们可以知道变量i_2的chrec（chain of recurrence的缩写）的形式为{i_1, +, 1}，也就是说i_2的值的变化公式为i_2=i_1 + 1*x (x为循环的迭代次数)，因为i_1为常量，带入得到为i_2={0, +, 1}=x。

sum_2={sum_0, +, i_2}={sum_0, +, i_1, +, 1}={0, +, 0, +, 1}=0 + 0*x + 1* x(x-1)/2!=x^2/2 + x/2。

知道上述scalar evolution的信息之后，编译器会执行归纳变量化简。

又因为我们知道了循环的迭代次数为100，因为循环判断条件是循环不变式(Loop Invariant)，那么我们就可以知道循环退出时sum_2的值，带入上述公式，得到sum_2的最终值为100 * 99 / 2=4950。然后直接替换endBB基本块中return sum_2为　

return 4950。

那么在执行替换之后，循环就变为无用了，会被LoopDeletion趟(

)进行删除，最后优化完的IR为：

endBB:
return 4950

缺点：

可能很多人看了上述代码之后，感觉编译器好牛逼啊。但是上述方法的应用是有很多限制条件的。

1. 循环终结条件必须是Loop invariant，这样才能确定循环迭代次数(trip count)。

2. 所处理的变量是整数，目前无法对浮点数进行处理，chrec只能处理整数。

3. 迭代次数有限制，这个视不同编译器不同。LLVM 2.6中初始最大迭代次数是100次。