現代C/C++編譯器有多智能？能做出什麼厲害的優化？

01-03

最近在搞C/C++代碼的性能優化，發現很多時候自以為的優化其實編譯器早就優化過了，得結合反彙編才能看出到底要做什麼樣的優化。
請熟悉編譯器的同學結合操作系統和硬體談一談現代c/c++編譯器到底有多智能吧。哪些書本上的優化方法其實早就過時了？
以及程序員做什麼會讓編譯器能更好的自動優化代碼？
舉個栗子：

1，循環展開，大部分編譯器設置flag後會自動展開；
2，順序SIMD優化，大部分編譯器設置flag後也會自動優化成SIMD指令；
3，減少中間變數，大部分編譯器會自動優化掉中間變數；
etc.
查看代碼對應的彙編：
Compiler Explorer

舉個微小的例子，一到一百求和

#include & 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是個什麼鬼！編譯器大哥你能不能嚴肅點，直接把結果算出來是怎麼回事。

編譯器：算一加到一百都要寫循環，媽的智障。

介於編譯器會高斯求和法，估計大約是高斯十歲的水平【大誤

我所知道的現在兩個compiler大的方向是LTO跟autoFDO

LLVM Link Time Optimization: Design and Implementation

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 &

#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簡直讓人抓狂

GitHub - google/autofdo: AutoFDO

FDO 是feedback driven optimization。很多Java的人都吹說jvm可以一邊跑一邊自動優化，現在通過FDO，c++的compiler也可以啦！

FDO的壞處是：

設置特別麻煩，對小公司來說現在還是太昂貴了。大公司基本上得在自己的伺服器上定時去搜集這些信息，然後在編譯時間總結一下。這個系統這是得大把真金白銀砸出來的

舉個之前看過的例子：

int calc_hash(signed char *s) { static const int N = 100003; int ret = 1; while (*s) { ret = ret * 131 + *s; ++ s; } ret %= N; if (ret &< 0) ret += N; //注意這句 return ret; }

這是一個典型的計算字元串bkdr hash的過程，注釋這句會被優化掉，因為編譯器認為它是廢代碼，編譯器是這麼想的：C規定int溢出是ub，那我就假設不會溢出，ret一開始是正數，*s範圍是[-128, 127]，就算*s是-128這個最小值，正數乘以131加它也還是正數，所以永遠為正，所以最後對N取模還是為零或者正數，所以你判斷ret&<0就根本是tmd廢話

然而寫這代碼的人不知道int溢出是ub，所以加了這行保證ret返回非負……然後他一開始很不幸在低版本編譯器沒有碰到這個優化策略，所以測試通過……於是正常運行了很多年……於是突然有次他升級了gcc……於是出事了……

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

補充：他那次好像是gcc 4.1升級到4.8，也就是說低版本的沒有做到這種程度的優化

類似的一個例子是for (int i = 1; i &> 0; ++ i);，編譯器可以直接優化成：L4:jmp L4，死循環，gcc 4.4下是這樣

gcc有編譯選項可以禁止編譯器對overflow的assume，對代碼沒有信心的最好加上，畢竟這個ub是很難發現的，尤其是維護一些老代碼時候

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

睡前再補充個例子吧，函數的參數計算和入棧順序，比如：

void f(int a, int b);

調用的時候，一般都認為是a和b依次入棧，vs下工作的同志們可能馬上就反應出「計算-push-計算-push……」這個過程，但是對f的一次調用來說，棧其實是個固定的數組，我先把b塞進去再塞a也是可以的，只要保證a在b前面就好，比如：

void f(int, int, int, int);

f(a, b, a + 1, b + 1);

如果按順序進行，為保證a和b只load一次，需要兩個寄存器（偽碼）：

eax = a

ebx = b

push eax

push ebx

eax ++

ebx ++

push eax

push ebx

如果不按順序就可以只要一個寄存器：

eax = a

stack[0] = eax

eax ++

stack[2] = eax

eax = b

stack[1] = eax

eax ++

stack[3] = eax

當然如果你實際在gcc測試，因為寄存器很多，所以還是編譯為上面這種形式，那麼我們增加變數數量，改成f(a,b,c,d,a+1,b+1,c+1,d+1)呢，這貨把eip什麼的都用上了還不肯屈服，那麼繼續增加數量，只要數量足夠，你就能在彙編裡面看到，gcc對函數參數是會跳著入棧的，為了減少load次數

P.S.某些機器比如power pc的cpu據說有256個寄存器，如果這種平台上重現實驗結果，請保持足夠的耐心，C應該沒有限制參數個數。。。

利用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& 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)

推薦讀一讀這裡的幾個文檔：

Software optimization resources. C++ and assembly. Windows, Linux, BSD, Mac OS X

其中第一篇：http://www.agner.org/optimize/optimizing_cpp.pdf

講解了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++優化手冊：

Optimizing software in C++ - An optimization guide for Windows, Linux and Mac platforms - Agner Fog

要稍微深入一點的話，GCC和LLVM的文檔其實都對各自的內部實現有不錯的介紹。

GCC：GNU Compiler Collection (GCC) Internals

LLVM：LLVM』s Analysis and Transform Passes

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

反模式（anti-patterns）

1. 為了「優化」而減少源碼中局部變數的個數

這可能是最沒用的手工「優化」了。特別是遇到在高級語言中「不用臨時變數來交換兩個變數」這種場景的時候。

看另一個問題有感：有什麼像a=a+b;b=a-b;a=a-b;這樣的演算法或者知識？ - 編程

2. 為了「優化」而把應該傳值的參數改為傳引用

（待續…）

一份比較老的slides：

http://www.fefe.de/source-code-optimization.pdf

看到高票答主 @蘇遠的回答提到了整數求和累加的優化，

我來說明下編譯器的實現原理吧。

以如下代碼為例，省略了其他無關代碼：

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

首先我們先轉換為SSA形式(wikipedia.org 的頁面)的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

為了得到 @蘇遠所示代碼中的結果，編譯器會執行歸納標量簡化優化(Induction variable)。但是在執行這項優化之前，編譯器會執行一趟分析趟——標量演化(Scalar Evolution)，該項優化是針對循環鏈(chain of recurrencce)來處理的

1. GNU Compiler Collection (GCC) Internals

2. http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf

3. http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf

4. http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15745-s13/public/lectures/L6-LLVM-Detail-1up.pdf

5. Re: Identifying Chain of Recurrence

6.https://github.com/gcc-mirror/gcc/blob/master/gcc/tree-scalar-evolution.c

用於確定每個標量在每次循環迭代的時候，值是多少，循環的迭代次數等。

那麼以上述代碼為例，我們可以知道變數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趟(LoopDeletion.cpp Source File)進行刪除，最後優化完的IR為：

endBB: return 4950

缺點：

可能很多人看了上述代碼之後，感覺編譯器好牛逼啊。但是上述方法的應用是有很多限制條件的。

1. 循環終結條件必須是Loop invariant，這樣才能確定循環迭代次數(trip count)。

2. 所處理的變數是整數，目前無法對浮點數進行處理，chrec只能處理整數。

3. 迭代次數有限制，這個視不同編譯器不同。LLVM 2.6中初始最大迭代次數是100次。

人有多大膽，編譯器多大產

有些智能並不能保證代碼變換前後語義是等價的

每次編譯poco庫的時候我都覺得很為難GCC

雖然題主內容里是想問編譯器代碼性能優化方面的內容，但題目里既然說到編譯器的的智能，我就偏一下方向來說吧。

有什麼更能展示編譯器的強大和智能？

自然是c++的模版元編程

template meta programming

簡單解釋的話就是寫代碼的代碼，寫的還是c++，但能讓編譯器在編譯期間生成正常的c++代碼。

沒接觸過的話，是不是聽上去感覺就是宏替換的加強版？感覺不到它的強大呢？

只是簡單用的話，效果上這樣理解也沒什麼

但是一旦深入下去，尤其翻看大神寫的東西，這明明看著就是c++的代碼，但TM怎麼完全看不懂他在幹什麼？後來才知道這其實完全是另外一個世界，可是明明是另外一個世界的東西但它又可以用來做很多正常c++能做的事....

什麼？你說它好像不能做這個，不能做那個，好像做不了太多東西，錯了，大錯特錯。就像你和高手考試都考了100分的故事一樣，雖然分數一樣，但你是努力努力再努力才得了滿分，而高手只是因為卷面分只有100分.....在元編程面前，只有想不到，沒有做不到。

再回頭看看其他答案，編譯器順手幫你求個和，丟棄下無用代碼，就已經被驚呼強大了，那模板元編程這種幾乎能在編譯期直接幫你「生成」包含複雜邏輯的c++代碼，甚至還能間接「執行」一些複雜邏輯，這樣的編譯器是不是算怪獸級的強大？

一個編譯器同時支持編譯語法相似但結果不同卻又關聯的兩種依賴語言，這個編譯器有多強大多智能？

寫的人思維都要轉換幾次，編譯器轉著圈嵌著套翻著番兒地編譯代碼的代碼也肯定是無比蛋疼的，你說它有多強大多智能？

一個代碼創造另外一個代碼，自己能按照相似的規則生成自己，是不是聽上去已經有人工智慧的發展趨勢了？

上帝說，要有光，於是有了光。

老子曰，一生二，二生三，三生萬物。

信c++，得永生！

===

FBI WARNING：模板元編程雖然很強大，但也有不少缺點，尤其對於大型項目，為了你以及身邊同事的身心健康，請務必適度且謹慎的使用。勿亂入坑，回頭是岸。

編譯器智能到每次我都覺得自己很智障。

智能到開不同級別的優化，程序行為會不同 2333

忍不住抖個機靈。

私以為正常寫代碼情況下編譯器就能優化，才叫智能編譯器。要程序員絞盡腦汁去考慮怎麼寫代碼能讓編譯器更好優化，甚至降低了可讀性，那就沒有起到透明屏蔽的作用。

智能編譯器應該是程序猿要較勁腦汁才能讓編譯器不優化。

理論上是這樣的。摺疊我吧。

就想知道能不能優化for循環里的迭代器後置為前置？

實在是習慣後置了！

我覺得都不用現代。。。。寄存器分配和指令調度最智能了

gcc現在有fdo了

scala的編譯器是最厲害的

c++11的auto自動類型推斷算么....