建站
咨詢
售后
建站咨詢
新聞中心
這篇文章講述了消除冗余代碼（Dead Code Elimination）的優(yōu)化方法，我簡(jiǎn)寫(xiě)為DCE。顧名思義：只要其計(jì)算結(jié)果沒(méi)有被程序所使用， 該計(jì)算就被丟棄。
成都創(chuàng)新互聯(lián)專注于網(wǎng)站建設(shè)|企業(yè)網(wǎng)站維護(hù)|優(yōu)化|托管以及網(wǎng)絡(luò)推廣，積累了大量的網(wǎng)站設(shè)計(jì)與制作經(jīng)驗(yàn)，為許多企業(yè)提供了網(wǎng)站定制設(shè)計(jì)服務(wù)，案例作品覆蓋成都茶樓設(shè)計(jì)等行業(yè)。能根據(jù)企業(yè)所處的行業(yè)與銷售的產(chǎn)品，結(jié)合品牌形象的塑造，量身定制品質(zhì)網(wǎng)站。
這時(shí)你可能會(huì)說(shuō)，你的代碼只會(huì)計(jì)算有用的結(jié)果，從沒(méi)有無(wú)用的東西，只有白癡才會(huì)平白無(wú)故地添加那些無(wú)用的代碼—–例如，會(huì)在做一些有用事情的同時(shí)，還在計(jì)算著圓周率的前1000位。那么消除冗余代碼的優(yōu)化，到底什么時(shí)候才有用呢?
我之所以這么早就開(kāi)始講述DCE的優(yōu)化，是因?yàn)槿绻磺宄﨑CE的話，在探索其他一些更有趣的優(yōu)化方法中會(huì)造成一些破壞和混亂?？匆幌孪旅娴男±?，文件Sum.cpp：
- int main() {
- long long s = 0;
- for (long long i = 1; i <= 1000000000; ++i) s += i;
- }
我們對(duì)于在計(jì)算這十億個(gè)數(shù)的和時(shí)，循環(huán)的執(zhí)行速度很感興趣。（的確，這種做法太愚蠢了，我們高中時(shí)就學(xué)過(guò)有一個(gè)閉公式可以計(jì)算出結(jié)果，但這不是重點(diǎn)）
使用命令 CL /Od /FA Sum.cpp 來(lái) 構(gòu)建這個(gè)程序，并用Sum命令來(lái)運(yùn)行程序。注意這個(gè)構(gòu)建使用/Od開(kāi)關(guān)禁用了代碼優(yōu)化。 在我的PC機(jī)上，運(yùn)行這個(gè)程序花費(fèi)了4秒。 現(xiàn)在試著使用CL /O2 /FA Sum.cpp 來(lái)編譯優(yōu)化過(guò)的代碼。這次運(yùn)行很快，幾乎察覺(jué)不到有延遲。編譯器對(duì)我們的代碼的優(yōu)化有這么出色嗎？答案是否定的（但它的確是以一種奇怪的方式改變了我們的 代碼）
我們看一下/Od版本生成的代碼，它保存在Sum.asm里。我精減了一些代碼并注釋了一些文本，讓它只顯示循環(huán)體：
這些指令跟你預(yù)料中的差不多。 變量i保存以在RSP為寄存器，i$1為偏移量的棧上；在asm文件的其他地方，我們發(fā)現(xiàn)i$1=0. 使用RAX寄存器讓i自增長(zhǎng)。同樣地，變量s保存在RSP為寄存器，S$為偏移量的棧上，s$=8. 并在RCX中來(lái)計(jì)算每次循環(huán)的累積和。
我們注意到每次循環(huán)時(shí)，先從棧上獲取i的值，再把新值寫(xiě)回去，變量s同樣如此?？梢哉f(shuō)這段代碼很幼稚—–它是由很愚蠢的編譯器生成的（也就說(shuō)，優(yōu)化被禁用了）。 例如，我們本來(lái)可以將變量i和s一直保存在寄存器中，而不用每次循環(huán)迭代時(shí)都要訪問(wèn)內(nèi)存。
關(guān)于未優(yōu)化的代碼就說(shuō)這么多了。那么進(jìn)行優(yōu)化后所生成代碼是什么樣呢? 來(lái)看一下使用/O2構(gòu)建的程序?qū)?yīng)的Sum.asm文件，再一次把文件精簡(jiǎn)到只剩下循環(huán)體的實(shí)現(xiàn)，
結(jié)果是：
- ;; there’s nothing here!
對(duì)，它是空的，沒(méi)有任何計(jì)算s的指令。
你可能會(huì)說(shuō)，那這個(gè)答案肯定錯(cuò)了.但是我們?cè)趺粗肋@個(gè)答案就是錯(cuò)的呢?因?yàn)閮?yōu)化器已經(jīng)推斷出程序在任何時(shí)候都沒(méi)用到S， 所以才懶得計(jì)算它。你不能說(shuō)答案是錯(cuò)的，除非你需要核對(duì)該答案，對(duì)吧？
我們這不是被DCE優(yōu)化給耍了嗎？ 如果你不需要觀察計(jì)算結(jié)果，程序是不會(huì)進(jìn)行計(jì)算的。
優(yōu)化器的這個(gè)問(wèn)題其實(shí)跟量子物理學(xué)的基本原理很類似，可以用大眾科普文章里經(jīng)常提到的一句話來(lái)解釋，“如果森林里一棵樹(shù)倒下了，但是如果周圍都沒(méi)人，它還會(huì)有聲音嗎？”。
我們可以在代碼里添加打印變量s的語(yǔ)句來(lái)觀察計(jì)算結(jié)果，代碼如下：
- #include
- int main() {
- long long s = 0;
- for (long long i = 1; i <= 1000000000; ++i) s += i;
- printf("%lld ", s);
- }
運(yùn)行/Od版本的程序打印出了正確結(jié)果，還是花費(fèi)了4秒，/O2版本打印出同樣的結(jié)果，速度卻快得多（具體快多少，可以看下下面的可選部分，實(shí)際上，速度高達(dá)7倍多）。
到現(xiàn)在為止，我已經(jīng)講述了這篇文章的主要觀點(diǎn)：在進(jìn)行編譯器優(yōu)化分析的時(shí)候一定要十分小心，衡量它們的優(yōu)點(diǎn)時(shí)，千萬(wàn)不要被DCE給誤導(dǎo)了。 下面是使用DCE優(yōu)化時(shí)需要注意的四個(gè)步驟：
- 檢查計(jì)時(shí)，確保沒(méi)有突然提高一個(gè)數(shù)量級(jí)；
- 檢查生成的代碼（使用 /FA）
- 如果不太確定，可以添加一個(gè)printf語(yǔ)句
- 把你感興趣的代碼放到一個(gè)獨(dú)立的.CPP文件里，和含有main函數(shù)的文件分開(kāi)。只要你不進(jìn)行整個(gè)程序的優(yōu)化，就一定會(huì)奏效（使用/GL，我們后面會(huì)講到）。
不管怎么樣，我們從這個(gè)例子中還是學(xué)到了一些很有意思的東西，下面四個(gè)小節(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)化版本一樣多的指令，為什么會(huì)快很多呢？那是因?yàn)閮?yōu)化后的循環(huán)體的指令使用的是寄存器，而不是內(nèi)存地址。 我們都知道，寄存器的訪問(wèn)速度比內(nèi)存快得多。 下面的延遲就展示了內(nèi)存訪問(wèn)時(shí)如何將你的程序降到蝸牛般的速度：
Location | 延時(shí) |
Register | 1 cycle |
L1 | 4 cycles |
L2 | 10 cycles |
L3 | 75 cycles |
DRAM | 60 ns |
所以，未優(yōu)化版本是在棧上進(jìn)行讀寫(xiě)的，比起在寄存器中進(jìn)行計(jì)算慢多了（寄存器的存取時(shí)間只需一個(gè)周期）。
但是還有其他原因的，注意/Od版本的執(zhí)行循環(huán)的時(shí)候計(jì)數(shù)器每次加1，/O2版本的計(jì)數(shù)器（保存在RAX寄存器中）每次加4。
優(yōu)化器已經(jīng)展開(kāi)循環(huán)，每次迭代都會(huì)把四項(xiàng)加起來(lái)，像這樣：
s = (1 + 2 + 3 + 4) + (5 + 6 + 7 + 8) + (9 + 10 + 11 + 12) + (13 + . . .
通過(guò)展開(kāi)這個(gè)循環(huán)，可以看到每四次迭代才對(duì)循環(huán)做一個(gè)判斷，而不是每次都進(jìn)行判斷，這樣CPU可以節(jié)省更多的時(shí)間做一些有用的事，而不是在不停地進(jìn)行循環(huán)判斷。
還有，它不是將結(jié)果存在一個(gè)地方，而是使用了四個(gè)獨(dú)立的寄存器，分別求和，像這樣：
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é)束時(shí)，再把四個(gè)寄存器的和加起來(lái)，得到最終結(jié)果。
（讀者朋友們可以思考下這個(gè)練習(xí)，如果循環(huán)總數(shù)不是4的倍數(shù)，那優(yōu)化器會(huì)怎么處理？）
可選2： 精確的性能測(cè)試
之前，我在沒(méi)有使用printf函數(shù)的/O2版本的程序中說(shuō)過(guò)，“運(yùn)行速度之快以致于你察覺(jué)不到有任何延遲”， 下面就用一個(gè)例子更準(zhǔn)確地描述下這種說(shuō)法：
- #include
- #include
- 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 來(lái)計(jì)算運(yùn)行時(shí)間（這就是我之前的博客里寫(xiě)到的精簡(jiǎn)版本的高分辨率計(jì)時(shí)器）。 在測(cè)量性能的時(shí)候，心中一定謹(jǐn)記一些注意事項(xiàng)（我以前有寫(xiě)過(guò)一個(gè)列表），但是對(duì)這個(gè)特殊的例子，其實(shí)也沒(méi)什么用，我們一會(huì)兒就能看到：
我在PC機(jī)上運(yùn)行了/Od版本的程序，打印diff的值，大約為7百萬(wàn)。（計(jì)算結(jié)果的單位并不重要，只需知道 這個(gè)值越大，程序運(yùn)行的時(shí)間就越長(zhǎng)）。而/O2版本，diff的值則為0.原因就得歸功于DCE優(yōu)化了。
我們?yōu)榱俗柚笵CE，添加一個(gè)printf函數(shù)，/Od版本的diff值大約為1百萬(wàn)—-速度提升了7倍。
可選3：x64 匯編程序 “擴(kuò)展”
我們?cè)诨仡^看看文章里的匯編代碼部分，在初始化寄存器部分，會(huì)發(fā)現(xiàn)有點(diǎ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++語(yǔ)言會(huì)使用long long類型的變量來(lái)保存循環(huán)計(jì)數(shù)器和總和。 在VC++編譯器中，會(huì)映射成64位的整數(shù)，所以我們會(huì)料到生成碼應(yīng)該會(huì)用x64的64位寄存器。
上一篇文章中，我已經(jīng)講過(guò)了，指令xor reg， reg是 用來(lái)將reg的值置為0的一種高效的方法。但是第一條指令是在對(duì)EDX寄存器（RDX寄存器的低32位字節(jié)）進(jìn)行xor運(yùn)算，下一條指令是將 EAX（也就是RAX寄存器的低32位字節(jié)）賦值為1。下面的三條指令也是同樣的方式。從表面來(lái)看，這樣每一個(gè)目標(biāo)寄存器的高32位字節(jié)都存儲(chǔ)的是一個(gè)任 意的隨機(jī)數(shù)，而循環(huán)體的計(jì)算部分是在擴(kuò)展的64位寄存器上進(jìn)行的，這樣的計(jì)算結(jié)果怎么可能是對(duì)的？
答案是因?yàn)樽畛跤葾MD發(fā)布的x64位指令集，會(huì)將64位的目標(biāo)寄存器的高32位字節(jié)自動(dòng)擴(kuò)展為零。 下面是該手冊(cè)的3.4.5小節(jié)的兩個(gè)知識(shí)點(diǎn)：
1. 32位寄存器的零擴(kuò)展： 如果寄存器為32位，自動(dòng)將通用目標(biāo)寄存器的高32位擴(kuò)展為零。
2. 8位和16位字節(jié)寄存器 無(wú)擴(kuò)展： 如果是8位和16位寄存器，則不對(duì)64位通用寄存器做改變。
最后，注意一下npad 13 這條指令（其實(shí)是一個(gè)偽操作，一條匯編指令）。用來(lái)確保下一條指令（從循環(huán)體開(kāi)始）遵循16字節(jié)的內(nèi)存對(duì)齊，可以提高性能(有時(shí)，用于微架構(gòu))。
可選4: printf 和 std::out
你也許會(huì)問(wèn)，在上個(gè)實(shí)驗(yàn)中，為什么我使用了C的printf函數(shù)，而不是C++的std::out呢? 試試看，其實(shí)兩者都可以，但是后者生成的asm文件要大很多，所以瀏覽起來(lái)不太方便: 相比前面的1.7K字節(jié)文件， 后者生成的文件達(dá)0.7M 字節(jié)。
文章名稱：優(yōu)化C++代碼（4）：消除冗余代碼
轉(zhuǎn)載注明：http://www.5511xx.com/article/cdsgded.html
