c語言求階乘和的流程圖_Introduction to CSAPP（十四）：流程控制指令與 C 語言條件判斷與循環

條件碼

在之前的内容中，我們提到EFLAGS 寄存器中有一些條件碼。這些條件碼為流程控制的跳轉提供了一定的能力。

• CF

  進位辨別。最近的操作使得最高位産生的了進位。

• ZF

  零辨別。最近的操作所得的結果為0。

• SF

  符号辨別。最近的操作所得的結果為負數。

• OF

  溢出辨別。最近的操作導緻補碼溢出。

比如，對于C語言表達式

t = a + b

，我們假設彙編後的指令是一條ADD指令。在執行ADD指令的同時，計算機同時會根據一下規則為上述的四個辨別位指派：

會改變條件碼的算術邏輯指令有

特殊地：

1. leaq 用來進行位址計算，不會進行任何條件碼的修改
2. 所有邏輯操作，CF 和 OF 會被标記為0
3. 移位操作，CF 被設定成為最後一個被移出的位，OF 被置為0
4. INC & DEC，不會設定CF辨別

除了這些算術邏輯指令，還有兩個特殊的指令

CMP

和

TEST

，這兩個指令專門用來改變條件碼。

1. CMP S1, S2

   ，計算

   S2-S1

   的結果，根據結果更新條件碼。即如果S1=S2，零标志會被設定為1；如果不相同，則可以利用其它标志判斷兩數大小關系。

2. TEST S1, S2

   ，計算

   S2&S1

   的結果，根據結果更新條件碼。典型用法是兩個操作數一樣，來通過條件碼得到這個數是正數，零還是負數。

條件碼的使用分為三類：

1. 根據條件碼，通過某些指令來将一個位元組設定成為0或者1；
2. 進行條件跳轉到程式的其他部分
3. 可以有條件地傳送資料

支援第一種情況的指令是SET指令，如下：

SET類指令的字尾的意思不再是長度，而是某些不同的條件

一個簡單的比較第一個參數是否小于第二個參數的程式:

int comp(long a, long b){
    return a < b;
}
// a in %rdi, b in %rsi
           

寫成彙編如下:

comp:
    cmpq %rsi, %rdi        # 執行a - b.
    setl %al            # 如果ZF == 1，%al(%rax或%eax的低位)會被設定為1
    movzbl %al, %eax    # 将%al零擴充更新到%eax, 同時把%eax和%rax的高位清零
    ret
           

練習：

題目

答案

分析：彙編語言是不會直接标記它的類型的，但是會标記它的資料的位數；我們需要根據其他的操作指令，來确認它的類型與符号

跳轉指令

類似C語言的goto關鍵字，是

jmp

指令。後可跟

1. 标号（Label）： 會被彙編器轉成對應彙編指令的位址，直接跳轉。寫法

   jmp .L1

   ，跳轉到 L1 标号；
2. 操作符訓示數：可以是寄存器或者記憶體位址，間接跳轉。寫法：

• jmp *%rax

  ， 跳轉到%rax的值代表的目标

• jmp *(%rax)

  ，跳轉到%rax中的指針指向的記憶體位址中的的目标

除了

jmp

指令之外的跳轉指令都是有條件的——根據條件碼來跳轉。條件跳轉隻能是直接跳轉。

一個例子：

這個例子可以幫助我們了解跳轉指令在編譯之後的結果中的編碼情況：

• PC-relative 編碼，
  • 反彙編版本中，檢視實際的位元組編碼，line 2， 跳轉指令的目标編碼是0x03，把它加上下一個PC，即0x5可以得到，0x8，也就是line 4的指令
  • 反彙編版本中，檢視實際的位元組編碼，line 5， 跳轉指令的目标編碼是0xf8，編碼方式是補碼（十進制為-8），把它加上下一個PC，即0xd（十進制13）可以得到，0x5，也就是line 5的指令
• 絕對位址編碼
  • 反彙編版本中，根據最右注釋，line 2， 跳轉指令的跳轉目标指明是是0x8
  • 反彙編版本中，根據最右注釋，line 5， 跳轉指令的跳轉目标指明是是0x5

這些例子說明：

• 當執行PC-relative尋址時，程式計數器的值是跳轉指令的下一條指令的位址值。這個是對計算機早期實作的延續和相容。
• 跳轉指令之後接的大小數字， 要按照補碼的形式去解釋

一個練習：

題目與答案

條件分支的實作

有兩種方式：

• 通過「條件控制」實作條件分支
• 通過「條件傳送」實作條件分支

條件控制

即将條件分支流轉換成等價的goto方式，再進一步轉換成由jmp指令實作跳轉的條件分支。其中等價的goto版本僅是幫助人對生成的彙編代碼進行分析時使用。

// C語言中的if-else的通用模闆如下
if (test_expr) // 一個整數表達式。取值為0表示「假」
  then_statement; // 分支語句
else
  else_statement; // 分支語句

// 對于這種情況通常轉換為以下 句子對應的彙編代碼
t = test_expr;

if (!t)
  goto FALSE;
then_statement;
goto DONE;

FALSE:
    else_statement
DONE:
// ...
           

C與其等價的goto版本 和 彙編指令

這個方法中，實作條件分支的核心是通過

控制語句，對應于上例的

test_expr

。這種機制：

• 優點：簡單，通用
• 缺點：在現代CPU上，可能會比較低效

條件傳送

條件傳送的核心是

分支預測。

條件控制來實作條件分支在現代CPU上，可能會比較低效的原因在于，現代CPU的執行過程是

流水線（pipeline）

的，使用條件控制不易将指令流水線化，導緻效率變低。

當機器遇到條件跳轉的時候，機器

不能确定是否會進行跳轉

。處理器采用非常精密的

分支預測邏輯

來預測每一條條件跳轉指令到底會不會執行。隻要猜測還算可靠（現代處理器要求對條件跳轉的預測準确度在百分之九十以上），那麼流水線模型會運作得很好。一旦錯誤預測了一個條件跳轉指令，那麼意味着處理器要丢掉它為該跳轉指令後所有指令已經做的工作，去一個新的，正确的跳轉位置開始填充流水線。這意味着一個錯誤的預測會帶來嚴重的懲罰——大約20~40個時鐘周期的浪費。

對于上面的例子，條件傳送的改造是：

C與其等價的條件指派版本 和 彙編指令

C語言中的條件傳送通用形式模闆是這樣的：

vt = then_statement;
v = else_statement;
t = text_expr;
if(t) v = vt; // 隻有當測試條件滿足時，vt的值才會被複制
           

可以看到：執行條件傳送時，無需預測測試結果，而是把兩個分支的運算都完成。處理器隻是讀取值，然後檢查條件碼，然後要麼更新目标寄存器，要麼保持不變。這會使得工作效率變高，因為它規避了預測錯誤帶來的懲罰。

也不是所有的條件表達式都适合用條件傳送的。如果兩個表達式中有任意一個可能産生錯誤或者副作用，就會導緻非法的行為，例如：

int readpointer(int *xp)
 {
     return (xp ? *xp : 0);
 }
           

條件傳送也不會總是改進效率。如果兩個表達式需要做大量的計算，那麼當對應的條件不滿足時，所做的工作就白費了。編譯器必須權衡條件傳送多做的計算，和條件分支預測錯誤懲罰之間的相對性能。

但其實這個實作是錯誤的。因為條件傳送對指針 xp 的引用是一定會發生的，如果 xp 是一個空指針，會導緻一個間接引用空指針的錯誤。

乍一看似乎沒什麼問題：如果指針為空，則傳回0，否則傳回指針指向的整數。

傳送指令：

循環

C語言提供多種循環結構，for、while 和 do while。但看到這裡大家也明白，彙編裡沒有相應的進階抽象指令，而是通過用測試、條件碼、跳轉組合起來，形成循環的效果。

do-while

// do-while循環的通用結構是：
 do
     body_statement
 while (test_expr);
 ​
 // 等價的goto版本
 loop:
     body_statement
     t = test_expr  
     if (t)
         goto loop
           

一個求階乘的例子：

C與其等價的goto版本 和 彙編指令

while

// while循環的通用結構是：
 while (test_expr)
     body_statement;
 ​
 // 有兩種翻譯方法
 // 1. jump to middle
 // 一般GCC帶優化指令行選項-Og時産生這樣的翻譯
         goto test
 loop:
     body_statement
 test:
     t = test_expr  
     if (t)
         goto loop
 ​
 // 2. guarded-do
 // 首先使用條件分支，初始條件不成立就跳過循環，把代碼變換為do-while循環
 // 在使用較高優化等級編譯時，如-O1，GCC會使用這樣的政策
 ​
 // 等價的do-while形式      
         t = test_expr  
     if (!t)
         goto done
         do
           body_statement
     while (test_expr);
 done:
 ​
 // 對應的翻譯
 // goto 版本
     t = test-expr
     if(!t)
         goto done;
 loop:
     body_statement
     t = test_expr
     if(t) 
           goto loop;
 done:
           

一個

jump to middle

階乘的例子

C與其等價的goto版本 和 彙編指令

for

// for循環的通用結構是：
 for (init_expr; test_expr; update_expr)
     body_statement;
 ​
 // 等價于
 init_expr;
 while(test_expr){
         body_statement
     update_expr;
 }
 ​
 // 是以也有兩種翻譯方法
 // 1. jump to middle
         init_expr;
         goto test;
 loop:
     body_statement
     update_expr;  
 test:
     t = test_expr  
     if (t)
         goto loop
 ​
 // 2. guarded-do
     init_expr;
     t = test-expr
     if(!t)
         goto done;
 loop:
     body_statement
     update_expr;  
     t = test_expr
     if(t) 
           goto loop;
 done:
           

Switch

switch 語句可以根據一個整數索引值進行多重分支（multi-way branching）。處理具有多種預測可能的分支時，這種語句特别有用，而且提高了C語言代碼的可讀性。

通過使用一種資料結構，叫做

跳轉表

（jump table），使得實作 switch 十分的高效。跳轉表是一個數組，表項 i 是一個代碼段位址，代碼段是當索引值等于 i 時程式應采取的動作。開關索引值就是用來執行一個跳轉表内數組引用，來确定目标指令的情況。和用一組很長的 if-else 嵌套不同，使用跳轉表的優點是執行開關語句的時間和開關的數量無關。

GCC根據開關的數量和開關情況值的稀疏程度翻譯開關語句，例如開關情況數量在4個以上，且值的跨度較小時，會使用跳轉表。

下面是一個switch例子

C與其等價的goto版本

上述代碼的彙編指令

上述代碼的彙編指令

其中

&&

是gcc拓展C語言文法，表示代碼位置的指針。拓展C語言版本中，jt就是跳轉表。

執行switch語句的關鍵步驟是通過跳轉表來通路代碼位置。在C代碼中是第16行，一條goto語句引用了跳轉表jt。GCC支援計算goto(computed goto)，是對C語言的擴充。在我們的彙編代碼版本中，類似的操作是在第5行，jmp指令的操作數有字首

*

表明這是一個間接跳轉，操作數指定一個記憶體位置，索引由寄存器%rsi給出，這個寄存器儲存着index的值。