標籤：

編譯器生成的彙編語句執行順序為什麼與C代碼順序不同？

01-04

來自CSAPP 3.5.4書中沒有解釋原因。C語言不是按順序執行的嗎？難道編譯器是知道改變執行順序不影響計算結果的情況下才這麼做的？編譯器有那麼神嗎？

先把題主截的圖引用進來保存著上下文：

不影響語義的前提下編譯器可以任意重排代碼順序；

在亂序執行（Out-of-Order）的CPU里，機器碼的執行也可以不按照你在「彙編」層面上看到的順序執行，只要不影響語義。

所以說這些中間步驟的順序，作為底層細節平時不需要那麼在意——它們多半跟原始源碼的順序是不一樣的。

現代優化編譯器優化的思路之一是「基於依賴的優化」（dependence-based optimization）。題主引用的CSAPP的例子：

int arith(int x, int y, int z) {
int t1 = x + y;
int t2 = z * 48;
int t3 = t1 0xFFFF;
int t4 = t2 * t3;
return t4;
}

所有涉及運算的值都是局部標量變數（local scalar variable），這是最便於編譯器做分析的情況，所有依賴都可以顯式分析。

由於整個函數沒有分支，這裡也不需要討論控制依賴（control dependence），只要討論數據依賴（data dependence）就好。

把數據依賴圖畫出來是個DAG（這裡正好是棵樹，特例了）：

x y z 48
/ /
t1 0xFFFF t2
/ /
t3 /
/
t4

優化必須要滿足的約束是：每個節點求值之前，其子節點（依賴的數據源）必須要先求了值。

顯然，t1和t2之間沒有依賴關係，它們的相對求值順序怎樣重排都沒關係。

有本我很喜歡的書，裡面講的是各種基於依賴的優化：Optimizing Compilers for Modern Architectures - A Dependence-based Approach

以上是理論部分。

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

下面來看例子。

我們可以用一個實際編譯器來看看CSAPP的例子編譯出來的結果：

.text
# -- Begin arith
.p2align 4,,15
.globl arith
.type arith, @function
arith:
.p2align 4,,7
/*.L0:*/ /* Block BB[54:2] preds: none, freq: 1.000 */
movl 8(%esp), %edx /* ia32_Load T[139:10] -:1:22 */
addl 4(%esp), %edx /* ia32_Add Iu[141:12] -:2:14 */
movzwl %dx, %edx /* ia32_Conv_I2I Iu[142:13] -:4:15 */
imull 12(%esp), %edx /* ia32_IMul Iu[143:14] -:5:15 */
leal (%edx,%edx,2), %eax /* ia32_Lea Iu[144:15] -:5:15 */
shll $0x4, %eax /* ia32_Shl Iu[146:17] -:5:15 */
ret /* ia32_Return X[152:23] -:6:3 */
.size arith, .-arith
# -- End arith

這裡用的是libFirm。可見它跟CSAPP書里所說的彙編的順序又有所不同。這也是完全合理的。

這個編譯結果的順序是：

edx = y;
edx += x;
edx = zeroextend dx; // edx = edx 0xFFFF
edx *= z;
eax = edx * 3;
eax &<&<= 4; // eax = eax * 16

也是完全符合依賴關係的約束的一種順序。

之所以用libFirm舉例是因為它的中間表示（Intermediate Representation）是一種程序依賴圖（Program Dependence Graph），可以很方便的看出控制與數據依賴。把CSAPP那裡例子對應的libFirm IR畫出來，是這個樣子的：

（這張圖跟我前面畫的數據依賴圖正好是左右翻轉的，不過意思一樣。

Arg 0、1、2分別代表x、y、z。白色方塊是普通數據節點，黃色方塊是常量節點，藍色方塊是內存相關節點，紅色方塊是控制流節點，粉紅色方塊是特殊的開始/結束節點。）某版LLVM生成的代碼：

; ModuleID = "/tmp/webcompile/_16355_0.bc"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-ellcc-linux"

; Function Attrs: nounwind readnone
define i32 @arith(i32 %x, i32 %y, i32 %z) #0 {
entry:
%add = add nsw i32 %y, %x
%mul = mul nsw i32 %z, 48
%and = and i32 %add, 65535
%mul1 = mul nsw i32 %mul, %and
ret i32 %mul1
}

attributes #0 = { nounwind readnone "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.ident = !{!0}

!0 = !{!"ecc 0.1.10 based on clang version 3.7.0 (trunk) (based on LLVM 3.7.0svn)"}

最終生成的x86彙編：

.text
.file "/tmp/webcompile/_15964_0.c"
.globl arith
.align 16, 0x90
.type arith,@function
arith: # @arith
# BB#0: # %entry
movl 8(%esp), %eax
addl 4(%esp), %eax
movzwl %ax, %eax
imull 12(%esp), %eax
shll $4, %eax
leal (%eax,%eax,2), %eax
retl
.Ltmp0:
.size arith, .Ltmp0-arith

.ident "ecc 0.1.10 based on clang version 3.7.0 (trunk) (based on LLVM 3.7.0svn)"
.section ".note.GNU-stack","",@progbits

GCC 4.9.2 x86-64：

arith(int, int, int):
leal (%rdx,%rdx,2), %eax
addl %edi, %esi
movzwl %si, %esi
sall $4, %eax
imull %esi, %eax
ret

Zing VM Server Compiler x86-64：

# edi: x
# esi: y
# edx: z
movl %edx, %eax
shll $0x4, %eax
leal (%rsi, %rdi, 1), %ecx
shll $0x5, %edx
addl %edx, $eax
movzwl %ecx, %edx
imull %edx, %eax

微軟Visual C++ 19.10.24629 for x64：

# ecx: x
# edx: y
# r8d: z
lea eax, DWORD PTR [rcx+rdx] # eax = t1 = x + y
movzx ecx, ax # ecx = t3 = t1 0xFFFF
imul ecx, r8d # ecx = t3 * z
lea eax, DWORD PTR [rcx+rcx*2] # eax = (t3 * z) * 3
shl eax, 4 # eax = (t3 * z) * 3 * 16
ret 0

非常幹練，贊。這組指令的構成跟GCC的做法很相似。

編譯器不僅僅會亂序，還會展開，合併，移除代碼（如果發現代碼沒有用到），，，，

C語言不錯了，C++編譯器經常編譯出連上帝都不認識的結果出來。

是的。

有那麼神。

我從硬體的角度試著來分析一下。

還是以最經典的MIPS五級流水線為例（其實我只會這個……），一條指令在CPU中被分為「取指，解碼，執行，訪存，回寫」五個階段，X86的雖然不是如此，但是也可以類比。

/************************************************我叫目錄***************************************************/

  • 流水線暫停
    • 訪存
    • 分支
      • 分支預測
      • 循環展開
  • 數據的競爭與冒險
      • 名稱冒險
      • 結構冒險
      • 數據冒險
  • 亂序執行
  • 多線程
  • 基於編譯器的靜態優化（總結）

    • /*************************************************************************************************************/

    /*******************************************第一章：流水線暫停*******************************************/

    Q:流水線暫停是什麼？

    A:（此處應該有兩張圖）

    在正常情況下，流水線的五級分別執行著五條指令的不同階段，就像這樣。但是會有某些原因導致CPU不得不去等待一些事情處理完成才能繼續進行工作，此時，五級之間的流水線寄存器會保存流水線當前的工作狀態直到流水線暫停結束。（CS應該也會學數電吧……）就像D觸發器一樣，時鐘一直給，暫停期間相當於關閉使能，暫停結束給使能信號，輸入信號又能愉快的流向輸出了。

    Q:流水線為什麼會暫停？

    A:主要有以下兩點原因

    • 訪存導致的暫停：

    眾所周知，存儲器的速度是要低於處理器的速度的。所以當CPU想要從內存中讀取或寫入數據時，內存說：「我還沒有準備好！」（向CPU發送未完成信號），CPU乾瞪眼，CD沒到即使滿藍也放不出來技能啊。於是就只能暫停（等效於插入no operate指令）等了。

    /*不能放在這*/

    • 分支導致的暫停：

    這裡需要先給一個概念，就是分支指令要在執行階段（第三個階段）才能得出是否要跳轉和跳轉的目標地址，而此時（指令存儲地址意義上的）下一條指令已經在解碼階段了，下下條指令剛把指令碼拿出來。按照我（應該也是絕大多數人）寫彙編的習慣，下一條指令是不跳轉分支的指令，跳轉分支的指令存在另一個遙遠的地方。但是如果萬一跳轉了呢……這兩個時鐘周期就白白浪費掉了啊。那有什麼辦法……這兩條指令作廢（相當於變為NOP指令），重新從跳轉目標地址取指令重新運行吧（此所謂「刷流水線」是也）。

    Q:勞資不服！真的就沒有解決辦法了么？！

    A:還是有的。

    • 訪存暫停的解決方案

    現代CPU為了彌補CPU與內存間的速度差距，加了一種叫Cache的東西（L1，L2，L3；位於CPU晶元內部，速度顯然比內存快得多，但是容量很小），就是把CPU看起來常用的東西在Cache中保留一份鏡像，需要用到該數據時直接在Cache中讀取就好，速度比內存快個幾十倍吧。

    • 分支暫停的解決方案
      • 分支預測：講道理的話，分支這個是硬傷，從物理上講根本無解，畢竟是未來的東西（兩個周期後的執行結果）決定現在的選擇（到底是跳呢？還是不跳呢？）。然而窩們程序猿的腦洞是無限的：既然兩個周期後才能得到分支的結果，那麼我們讓CPU在得到結果之前先蒙一下呢？

    我就問在座的各位：你們誰做選擇題沒蒙過答案？！

    好，我們開始走一下蒙答案的流程。首先，這道題以前見過沒有？（根據歷史分支猜測當前分支結果）什麼？你們都沒有錯題本的么？【歷史分支記錄表，分為

    全科（全局歷史記錄，每一條分支的記錄都保存在一起） 和

    單科（一張表只記錄該條指令或者該類指令的分支歷史）】

    OK，通過查表，我們大概有八成的把握這道題選A（跳轉的正確率為80%）。那就選A吧！

    或者我們偷個懶，所有題都選D（分支總是預測不跳轉）或者選C（分支總是預測跳轉），講道理這樣也是可以的，而且對於小部分測試正確率能到99%+。

      • 循環展開：我們看一下這段C代碼（媽蛋你乎怎麼打代碼？）

    for(i=100;i&>0;i--)

    {

    //想幹啥幹啥

    }

    變成彙編。我用MIPS彙編了，X86我還得現翻書寫……差距不大~你們能看懂的。

    BNE $1 $0 L // $1存變數i,$0寸常數0,L行標為循環體指令

    // 我記得X86也有BNE指令，不相等即跳轉

    //這裡的指令不重要

    L: //想幹啥幹啥

    SUB $1,$1,1 // $1 = $1 - 1

    顯然這樣要執行好多好多好多好多的BNE指令，所以我們（叫我編譯器！）可以進行一下優化。優化完是這個樣子的。

    BNE $1 $0 L

    //這裡的指令依然不重要

    L: //想幹啥幹啥*2

    SUB $1,$1,2 // $1 = $1 - 2

    我們把循環體重新組合，在一個新的循環體中包含了兩個原來的循環體，這樣我們直接把BNE執行的次數減了一半！選擇題題量少了一半自然就更好蒙咯o(*￣︶￣*)o

    • 數據的競爭與冒險
      • 名稱冒險

    舉個栗子：緊挨著的前後兩條指令都要用到$1（EAX，通用寄存器就對了）寄存器，但是這兩條指令是孤立的，即相互沒有數據流動，與其他指令也沒有數據流動。這時，我們把任意一條指令用到的$1寄存器換成$2（EBX）寄存器（寄存器重命名），這兩條指令就可以並行（超標量/亂序），彙編出來的指令順序發生變更也就很正常了。

        • WAW寫後寫

    再看這一段代碼

    DIV S0,S2,S4

    ADD S6,S0,S8

    MUL S6,S10,S8

    ADD必須等待DIV指令完成後才能進行計算，而目前看起來MUL指令和前兩條指令之間沒有相關。ADD和MUL指令的順序決定了必須先完成ADD再完成MUL，在順序執行的處理器中這很正常，但是在亂序處理器中這就是一個問題了，因為ADD可能會在MUL之後才能完成。我們稱這種情況為WAW冒險。解決方案會在之後的亂序執行中寫出。

        • WAR讀後寫

    另一段代碼

    ADD S6,S0,S8

    SUB S8,S10,S14

    還是在亂序處理器中，我們必須保證SUB不能在ADD取得操作數之前給出結果，否則指令順序就會變成SUB,ADD。這是WAR冒險。

      • 結構冒險

    除法的栗子：連續兩條需要多個周期才能得出結果的除法指令，顯然中間要通過等待的方式順序執行的話開銷太大，在一個亂序執行的處理器中，我們可以在兩條指令中間插入其他與這兩條除法指令無關的指令，以消除指令氣泡。

      • 數據冒險

    講道理的話，數據冒險是完全可以消除的，不必也不能通過編譯器優化解決，權當做寫「為什麼這一段不能變換指令順序」吧。

    注意與名稱冒險的區別。名稱冒險是兩條指令沒有數據流動，數據冒險是兩條指令間有數據流動。

        • RAW寫後讀

    對於任意寄存器或存儲器地址，前一條指令要寫，後一條指令要讀前一條指令的寫入的結果。顯然這兩條指令的順序不能交換。後面兩個情況可以類比。

    • 亂序執行

    （此處應該有圖）

    Q:什麼是亂序執行？

    A:剛才我們舉過一個除法的栗子。兩條除法指令之間可以插入其他的指令，但是這需要硬體支持，簡單地講就是需要多個ALU（邏輯運算單元？忘記怎麼翻譯了，總之就是CPU裡面算數的那個東西），或者把ALU拆開，有多個加法器，乘法器，除法器這樣的。亂序的執行過程是：順序取指，亂序執行，順序提交。

    順序decode出來，（接下來每一個逗號是一個時鐘周期）把除法指令A扔到除法器A，把除法指令B扔到除法器B（現在兩條除法指令都在除法器里跑循環），把無關的加法指令A扔到加法器A（除法指令仍然在跑循環），加法器A得到結果並把結果放到結果保留站，除法器A得到結果，保留站中的加法結果A被提交（假設這裡沒有相關，允許直接提交），除法結果A提交，除法結果B提交。

    可以看到，輸入的指令順序是：DIV,DIV,ADD；但是輸出的指令順序是：ADD;DIV;DIV。

    Q:說好的WAW和WAR冒險解決方案呢？

    A:亂序執行再亂也是要按照基本法的，這個基本法叫Tomasulo演算法，在解決WAW和WAR冒險方面，它採用了寄存器重命名這種方案，上面說的那兩段代碼其實是《量化》亂序執行那一節的部分示例，原文如下

    DIV.D F0,F2,F4

    ADD.D F6,F0,F8

    S.D F6,0(R1)

    SUB.D F8,F10,F14

    MUL.D F6,F10,F8

    這段代碼直接給出了WAW,WAR兩種冒險（真數據相關就不說了），解決方案就是引入兩個新的寄存器S和T，對這一段代碼進行改寫

    DIV.D F0,F2,F4

    ADD.D S,F0,F8

    S.D S,0(R1)

    SUB.D T,F10,F14

    MUL.D F6,F10,T

    這些完全可以由編譯器靜態完成，直接看的話可能看不出來，畢竟它只改了寄存器名稱。

    關於Tomasulo演算法的更多信息，請參閱Tomasulo algorithm

    這裡只是給了一個最簡單的亂序執行栗子，擴展閱讀請參閱

    Out-of-order execution

    （可是這一段和編譯器對指令循序的調換有什麼關係呢？）

    • 多線程

    講道理的話，這一部分我很可能寫不好，學得不夠紮實。

    那就鴿了吧（微笑臉）

    Simultaneous multithreading

    嚇得我扔個wiki鏈接趕緊跑。

    • 基於編譯器的靜態優化

    上述內容有一些是在runtime完成的，但更多的還是在編譯階段就可以發現的冒險或者其他影響性能的東西，一個好的編譯器，必然需要能夠識別出哪些代碼可能影響性能，並進行優化，這就是為什麼C和彙編的指令順序會有區別。

    ---------------------------------------------------------------------------------------------------------------------------------

    兩次寫隔了好久……自控和電力電子掛了實在不開心……

    大概想不起來其他的了吧。如果還有沒涉及到的地方，請指明！

    完結撒花

    沒錯，就是「編譯器是知道改變執行順序不影響計算結果的情況下才這麼做的」，類似的，cpu也會有亂序執行的行為

    不是按順序執行，優化器會根據具體硬體來打亂順序，優化性能。而且如果你學了編譯器就會知道，這件事情並不神。

    是的，確實很神，還有很多更神的優化。

    我們比較熟悉的有除法優化為乘法之類的。不熟悉的就多了，大多見到這些代碼都不知道這是優化，一下子能想起來的有這幾種。為了更高效的利用UV流水線而故意挪動指令順序。為了減少數據衝突或者指令衝突而故意挪動指令順序。為了減少AGI（Address Generation Interlock）衝突而挪動指令順序以及生成一些看起來有些奇怪的彙編代碼。

    http://en.m.wikipedia.org/wiki/Compiler_optimization 這裡有各種你優化方法，算是除了書之外的補充。

    編譯器在認為不改變單線程邏輯語意的情況下可以自由調整代碼順序。這是編譯優化里很重要的一環啊。而且即便編譯器不這麼做，還有CPU指令亂序呢。

    所以有一些人工的屏障指令來控制別亂移動。以防多線程下有問題

    試一下 -O0

    這是開啟了編譯器優化是ATT彙編，其實這裡也沒做多少功能或者並非說多麼智能。只是把同一個變數的操作匯聚在一起了，不用來回的重複訪問。與之類似的是處理器優化有用到Cache line。就是一次從主存取儘可能多的數據以提高緩存命中率。舉個俗的例子，就比如你去接個水再順便上個廁所而往往不會先接完水回來又跑去上廁所再回來。

    編譯器的優化比你想的更神，不僅僅能改變順序

    在不影響結果的情況下，允許編譯器調整代碼以提高運行速度。

    因為編譯器有一個功能叫做「優化」，一般是 -O 參數。

    改變順序的理由太多了 比如考慮到rob大小有限 ，考慮到宏融合指令配對，考慮到解碼器的比如4111規則什麼的

    就是這麼神，這學期剛修完computer architecture, 計算機的終極目標就是最大化利用資源。樓主這部分的內容叫instruction level parallelism

    CSAPP里有說啊，開了編譯器優化後會有時產生亂序，目的是減少存儲器讀寫等等

    out of order execution. 加mem barrier 可以阻止

    推薦閱讀：

    ※編譯器能否對如下場景優化，以及如何檢查不同編譯器對此是否做了優化？
    ※C++如何判斷一個整數溢出?
    ※c語言中一個函數的聲明和定義有區別嗎？
    ※C++中生成隨機數的問題？
    ※*a.b()是什麼意思，運算符順序是怎麼看的？

    TAG:C編程語言 | 彙編語言 | CC | GCC | CSAPP |