優(yōu)化C++代碼（4）：消除冗余代碼

作者：@米可_GO譯 2013-09-05 09:50:11

這篇文章講述了消除冗余代碼（Dead Code Elimination）的優(yōu)化方法，我簡寫為DCE。顧名思義：只要其計算結(jié)果沒有被程序所使用，該計算就被丟棄。

這時你可能會說，你的代碼只會計算有用的結(jié)果，從沒有無用的東西，只有白癡才會平白無故地添加那些無用的代碼—–例如，會在做一些有用事情的同時，還在計算著圓周率的前1000位。那么消除冗余代碼的優(yōu)化，到底什么時候才有用呢?

我之所以這么早就開始講述DCE的優(yōu)化，是因為如果不清楚DCE的話，在探索其他一些更有趣的優(yōu)化方法中會造成一些破壞和混亂。看一下下面的小例子，文件Sum.cpp：

int main() { 
    long long s = 0; 
    for (long long i = 1; i <= 1000000000; ++i) s += i; 
}

我們對于在計算這十億個數(shù)的和時，循環(huán)的執(zhí)行速度很感興趣。（的確，這種做法太愚蠢了，我們高中時就學過有一個閉公式可以計算出結(jié)果，但這不是重點）

使用命令 CL /Od /FA Sum.cpp 來構(gòu)建這個程序，并用Sum命令來運行程序。注意這個構(gòu)建使用/Od開關(guān)禁用了代碼優(yōu)化。在我的PC機上，運行這個程序花費了4秒。現(xiàn)在試著使用CL /O2 /FA Sum.cpp 來編譯優(yōu)化過的代碼。這次運行很快，幾乎察覺不到有延遲。編譯器對我們的代碼的優(yōu)化有這么出色嗎？答案是否定的（但它的確是以一種奇怪的方式改變了我們的代碼）

我們看一下/Od版本生成的代碼，它保存在Sum.asm里。我精減了一些代碼并注釋了一些文本，讓它只顯示循環(huán)體：

這些指令跟你預料中的差不多。變量i保存以在RSP為寄存器，i$1為偏移量的棧上；在asm文件的其他地方，我們發(fā)現(xiàn)i$1=0. 使用RAX寄存器讓i自增長。同樣地，變量s保存在RSP為寄存器，S$為偏移量的棧上，s$=8. 并在RCX中來計算每次循環(huán)的累積和。

我們注意到每次循環(huán)時，先從棧上獲取i的值，再把新值寫回去，變量s同樣如此。可以說這段代碼很幼稚—–它是由很愚蠢的編譯器生成的（也就說，優(yōu)化被禁用了）。例如，我們本來可以將變量i和s一直保存在寄存器中，而不用每次循環(huán)迭代時都要訪問內(nèi)存。

關(guān)于未優(yōu)化的代碼就說這么多了。那么進行優(yōu)化后所生成代碼是什么樣呢? 來看一下使用/O2構(gòu)建的程序?qū)?yīng)的Sum.asm文件，再一次把文件精簡到只剩下循環(huán)體的實現(xiàn)，

結(jié)果是：

;; there’s nothing here!

對，它是空的，沒有任何計算s的指令。

你可能會說，那這個答案肯定錯了.但是我們怎么知道這個答案就是錯的呢?因為優(yōu)化器已經(jīng)推斷出程序在任何時候都沒用到S，所以才懶得計算它。你不能說答案是錯的，除非你需要核對該答案，對吧？

我們這不是被DCE優(yōu)化給耍了嗎？如果你不需要觀察計算結(jié)果，程序是不會進行計算的。

優(yōu)化器的這個問題其實跟量子物理學的基本原理很類似，可以用大眾科普文章里經(jīng)常提到的一句話來解釋，“如果森林里一棵樹倒下了，但是如果周圍都沒人，它還會有聲音嗎？”。

我們可以在代碼里添加打印變量s的語句來觀察計算結(jié)果，代碼如下：

#include <stdio.h> 
int main() { 
    long long s = 0; 
    for (long long i = 1; i <= 1000000000; ++i) s += i; 
    printf("%lld ", s); 
}

運行/Od版本的程序打印出了正確結(jié)果，還是花費了4秒，/O2版本打印出同樣的結(jié)果，速度卻快得多（具體快多少，可以看下下面的可選部分，實際上，速度高達7倍多）。

到現(xiàn)在為止，我已經(jīng)講述了這篇文章的主要觀點：在進行編譯器優(yōu)化分析的時候一定要十分小心，衡量它們的優(yōu)點時，千萬不要被DCE給誤導了。下面是使用DCE優(yōu)化時需要注意的四個步驟：

檢查計時，確保沒有突然提高一個數(shù)量級；
檢查生成的代碼（使用 /FA）
如果不太確定，可以添加一個printf語句
把你感興趣的代碼放到一個獨立的.CPP文件里，和含有main函數(shù)的文件分開。只要你不進行整個程序的優(yōu)化，就一定會奏效（使用/GL，我們后面會講到）。

不管怎么樣，我們從這個例子中還是學到了一些很有意思的東西，下面四個小節(jié)為可選部分。

xor    edx, edx 
mov    eax, 1 
mov    ecx, edx 
mov    r8d, edx 
mov    r9d, edx 
npad   13 
$LL3@main: 
inc    r9 
add    r8, 2 
add    rcx, 3 
add    r9, rax                           ;; r9  = 2  8 18 32 50 ... 
add    r8, rax                           ;; r8  = 3 10 21 36 55 ... 
add    rcx, rax                          ;; rcx = 4 12 24 40 60 ... 
add    rdx, rax                          ;; rdx = 1  6 15 28 45 ... 
add    rax, 4                            ;; rax = 1  5  9 13 17 ... 
cmp    rax, 1000000000                   ;; i <= 1000000000 ? 
jle    SHORT $LL3@main                   ;; yes, so loop back

注意看循環(huán)體包含了和未優(yōu)化版本一樣多的指令，為什么會快很多呢？那是因為優(yōu)化后的循環(huán)體的指令使用的是寄存器，而不是內(nèi)存地址。我們都知道，寄存器的訪問速度比內(nèi)存快得多。下面的延遲就展示了內(nèi)存訪問時如何將你的程序降到蝸牛般的速度：

Location	延時
Register	1 cycle
L1	4 cycles
L2	10 cycles
L3	75 cycles
DRAM	60 ns

所以，未優(yōu)化版本是在棧上進行讀寫的，比起在寄存器中進行計算慢多了（寄存器的存取時間只需一個周期）。

但是還有其他原因的，注意/Od版本的執(zhí)行循環(huán)的時候計數(shù)器每次加1，/O2版本的計數(shù)器（保存在RAX寄存器中）每次加4。

優(yōu)化器已經(jīng)展開循環(huán)，每次迭代都會把四項加起來，像這樣：

s = (1 + 2 + 3 + 4) + (5 + 6 + 7 + 8) + (9 + 10 + 11 + 12) + (13 + . . .

通過展開這個循環(huán)，可以看到每四次迭代才對循環(huán)做一個判斷，而不是每次都進行判斷，這樣CPU可以節(jié)省更多的時間做一些有用的事，而不是在不停地進行循環(huán)判斷。

還有，它不是將結(jié)果存在一個地方，而是使用了四個獨立的寄存器，分別求和，像這樣：

RDX = 1 + 5 + 9 + 13 + ... = 1, 6, 15, 28 ... R9 = 2 + 6 + 10 + 14 + ... = 2, 8, 18, 32 ... R8 = 3 + 7 + 11 + 15 + ... = 3, 10, 21, 36 ... RCX = 4 + 8 + 12 + 16 + ... = 4, 12, 24, 40 ...

循環(huán)結(jié)束時，再把四個寄存器的和加起來，得到最終結(jié)果。

（讀者朋友們可以思考下這個練習，如果循環(huán)總數(shù)不是4的倍數(shù)，那優(yōu)化器會怎么處理？）

可選2：精確的性能測試

之前，我在沒有使用printf函數(shù)的/O2版本的程序中說過，“運行速度之快以致于你察覺不到有任何延遲”，下面就用一個例子更準確地描述下這種說法：

#include <stdio.h> 
#include <windows.h> 
int main() { 
  LARGE_INTEGER start, stop; 
  QueryPerformanceCounter(&start); 
    long long s = 0; 
    for (long long i = 1; i <= 1000000000; ++i) s += i; 
  QueryPerformanceCounter(&stop); 
  double diff = stop.QuadPart - start.QuadPart; 
  printf("%f", diff); 
}

程序中使用了QueryPerformanceCounter 來計算運行時間（這就是我之前的博客里寫到的精簡版本的高分辨率計時器）。在測量性能的時候，心中一定謹記一些注意事項（我以前有寫過一個列表），但是對這個特殊的例子，其實也沒什么用，我們一會兒就能看到：

我在PC機上運行了/Od版本的程序，打印diff的值，大約為7百萬。（計算結(jié)果的單位并不重要，只需知道這個值越大，程序運行的時間就越長）。而/O2版本，diff的值則為0.原因就得歸功于DCE優(yōu)化了。

我們?yōu)榱俗柚笵CE，添加一個printf函數(shù)，/Od版本的diff值大約為1百萬—-速度提升了7倍。

可選3：x64 匯編程序 “擴展”

我們在回頭看看文章里的匯編代碼部分，在初始化寄存器部分，會發(fā)現(xiàn)有點奇怪：

xor    edx, edx                          ;; rdx = 0     (64-bit!) 
mov    eax, 1                            ;; rax = i = 1 (64-bit!) 
mov    ecx, edx                          ;; rcx = 0     (64-bit!) 
mov    r8d, edx                          ;; r8  = 0     (64-bit!) 
mov    r9d, edx                          ;; r9  = 0     (64-bit!) 
npad   13                                ;; multi-byte nop alignment padding 
$LL3@main:

記得原始C++語言會使用long long類型的變量來保存循環(huán)計數(shù)器和總和。在VC++編譯器中，會映射成64位的整數(shù)，所以我們會料到生成碼應(yīng)該會用x64的64位寄存器。

上一篇文章中，我已經(jīng)講過了，指令xor reg， reg是用來將reg的值置為0的一種高效的方法。但是第一條指令是在對EDX寄存器（RDX寄存器的低32位字節(jié)）進行xor運算，下一條指令是將 EAX（也就是RAX寄存器的低32位字節(jié)）賦值為1。下面的三條指令也是同樣的方式。從表面來看，這樣每一個目標寄存器的高32位字節(jié)都存儲的是一個任意的隨機數(shù)，而循環(huán)體的計算部分是在擴展的64位寄存器上進行的，這樣的計算結(jié)果怎么可能是對的？

答案是因為最初由AMD發(fā)布的x64位指令集，會將64位的目標寄存器的高32位字節(jié)自動擴展為零。下面是該手冊的3.4.5小節(jié)的兩個知識點：

1. 32位寄存器的零擴展：如果寄存器為32位，自動將通用目標寄存器的高32位擴展為零。

2. 8位和16位字節(jié)寄存器無擴展：如果是8位和16位寄存器，則不對64位通用寄存器做改變。

最后，注意一下npad 13 這條指令（其實是一個偽操作，一條匯編指令）。用來確保下一條指令（從循環(huán)體開始）遵循16字節(jié)的內(nèi)存對齊，可以提高性能(有時，用于微架構(gòu))。

可選4: printf 和 std::out

你也許會問，在上個實驗中，為什么我使用了C的printf函數(shù)，而不是C++的std::out呢? 試試看，其實兩者都可以，但是后者生成的asm文件要大很多，所以瀏覽起來不太方便: 相比前面的1.7K字節(jié)文件，后者生成的文件達0.7M 字節(jié)。

原文鏈接：http://blog.jobbole.com/47231/

譯文鏈接：http://blog.jobbole.com/47231/

責任編輯：陳四芳來源：伯樂在線

C++代碼優(yōu)化