控制流 (Control Flow)

Overview Table

機器碼實作條件行為的兩種低階機制 (p.236):測試資料值後改變控制流 (control flow) 或 改變資料流 (data flow)。前者較通用常見,後者在受限情況下更符合現代處理器特性。

3.6.1 Condition Codes(條件碼)(p.237)

CPU 在整數暫存器之外,另維護一組單一位元的 condition code registers,描述最近一次算術或邏輯運算的屬性,供後續條件分支測試:

各類指令對旗標的影響(必背例外):

• leaq 不改變任何 condition code(它是位址計算用途);Figure 3.10 其餘算術/邏輯指令都會設定旗標。
• 邏輯運算(如 xor):CF 與 OF 設為 0。
• 移位運算:CF = 最後被移出的位元,OF = 0。
• inc/dec:設定 OF 與 ZF,但不動 CF。

兩類「只設旗標、不寫入目的地」的指令 (Figure 3.13, p.238),各有 b/w/l/q 四種尺寸:

3.6.2 存取 Condition Codes(p.238–241)

不直接讀旗標,而是三種使用方式:(1) 依旗標組合把單一位元組設為 0/1(set 指令);(2) 條件跳轉;(3) 條件資料轉移(cmov)。

set 指令 (Figure 3.14):目的地為單一位元組暫存器(如 %al)或 1-byte 記憶體。後綴表示「條件」而非運算元大小(setl = set less,不是 set long)。要得到 32/64-bit 結果,必須再清高位,典型序列:

    int comp(long a, long b)   // return a < b
    cmpq   %rsi, %rdi     ; Compare a:b
    setl   %al            ; %al = (a < b)
    movzbl %al, %eax      ; 清 %eax 其餘 3 bytes(且連 %rax 上半 4 bytes 一併清零)
    ret

各條件的旗標組合公式(set/jXX/cmovXX 三族共用,設 t = a - b):

為何 setl 用 SF ^ OF (p.240):無溢位 (OF=0) 時 a<b ⟺ a−b<0 ⟺ SF=1;負溢位時 a<b 但結果變正 (SF=0, OF=1);正溢位時 a>b 但結果變負 (SF=1, OF=1)。兩位元的互斥或恰在所有情況給出正確的 a<b 判定。Unsigned 比較則靠 cmp 在 a−b<0(借位)時設定的 CF 與 ZF 組合。

• 同一機器指令可有多個同義名 (synonyms),如 setg = setnle;編譯器/反組譯器任意擇一。
• 機器碼不為值附帶型別:signed/unsigned 多數共用相同指令(位元層次行為相同),僅右移、乘除法、與條件碼組合需要區分(Practice 3.13/3.14 即考從 setl vs setb、setg vs seta 反推 data_t 型別與比較子)。

3.6.3 Jump 指令(p.241–243)

jmp 無條件跳轉,分兩種:

• Direct jump:目標編碼在指令內,組語寫 label,如 jmp .L1。
• Indirect jump:目標從暫存器或記憶體讀出,寫法為 * + 運算元:
  • jmp *%rax — 以 %rax 的值為跳轉目標
  • jmp *(%rax) — 以 %rax 為位址讀記憶體取得目標

條件跳轉 jXX(Figure 3.15)之條件名稱與旗標公式完全對應上表的 set 指令。

3.6.4 Jump 指令編碼(p.243–244)

最常用編碼是 PC-relative:編碼「目標位址 − 跳轉指令下一條指令位址」的差值,可用 1、2、4 bytes;另一種是 4-byte「絕對位址」。組譯器與連結器自動選擇。

位址   機器碼        組語               offset 計算
 0:   48 89 f8     mov  %rdi,%rax
 3:   eb 03        jmp  8             0x03 + 0x5(下一指令位址) = 0x8 ──┐
 5:   48 d1 f8     sar  %rax      <───────────────────────────────────┼─┐
 8:   48 85 c0     test %rax,%rax <─────────────────────────────────── ┘ │
 b:   7f f8        jg   5             0xf8(= -8) + 0xd = 0x5 ────────────┘
 d:   f3 c3        repz retq

• 向後跳用負偏移量(如 0xf8 = −8 的 1-byte 二補數;4-byte 版依 little-endian 由低到高排列)。
• PC 值取「下一條指令位址」是歷史慣例:早期處理器執行指令的第一步就是更新 PC。
• 好處:指令編碼精簡(僅 2 bytes),且連結重定位後 offset 不變 → 目的碼可整段搬移而無須修改(Practice 3.15 專考這種位址算術)。

3.6.5 用條件控制實作條件分支(p.245–249)

最通用的翻譯法:條件跳轉 + 無條件跳轉的組合。書中以 goto code(用 C 的 goto 模擬組語控制流)呈現。if (test-expr) then-statement else else-statement 的標準模板:

        t = test-expr;
        if (!t) goto false;   <-- 條件「反轉」跳過 then
        then-statement
        goto done;
    false:
        else-statement
    done:

範例 absdiff_se(含副作用:遞增全域計數器 lt_cnt/ge_cnt,p.246):

    cmpq  %rsi, %rdi         ; Compare x:y
    jge   .L2                ; if x >= y goto else 區塊(條件反轉!)
    addq  $1, lt_cnt(%rip)   ; then: lt_cnt++
    movq  %rsi, %rax
    subq  %rdi, %rax         ; result = y - x
    ret
.L2:
    addq  $1, ge_cnt(%rip)   ; else: ge_cnt++
    ...

• 編譯器為 then/else 各生成獨立程式區塊,插入條件與無條件分支確保只執行其一。
• 另一種等價模板(Practice 3.17):if (t) goto true; else-statement; goto done; true: then-statement; done:。
• C 的 && 短路求值會產生多個條件跳轉(Practice 3.16:一個 if (a && *p < a) 對應兩個條件分支)。

3.6.6 用 Conditional Move 實作條件分支(p.250–256)

替代策略:條件資料轉移 — 把兩種結果都算出來,再依條件選一個。v = test-expr ? then-expr : else-expr; 的抽象碼:

    v  = then-expr;
    ve = else-expr;
    t  = test-expr;
    if (!t) v = ve;    <-- 這行就是單一條 cmovXX 指令

範例 absdiff(無副作用版,p.250):

    movq   %rsi, %rax
    subq   %rdi, %rax    ; rval = y - x
    movq   %rdi, %rdx
    subq   %rsi, %rdx    ; eval = x - y
    cmpq   %rsi, %rdi    ; Compare x:y
    cmovge %rdx, %rax    ; if x >= y: rval = eval
    ret

為何更快 — pipeline 與 branch prediction (p.251):

 條件跳轉(control transfer):        條件移動(data transfer):
        cmp                              兩路結果都先計算
       /    \                                 |
  branch prediction 猜方向                cmp -> cmovXX 選值
   |- 猜對 -> pipeline 滿載,~T_OK            |
   |- 猜錯 -> 丟棄已做的工作、重填 pipeline   控制流不依賴資料
            罰 15–30 cycles              -> 固定 ~8 cycles,pipeline 恆滿

• 處理器靠 pipelining 重疊執行連續指令,需提前確定指令序列;遇到條件跳轉 (branch) 時用 branch prediction 猜方向(現代設計目標成功率約 90%)。
• Misprediction penalty 公式 (Aside, p.252):$T_{avg}(p)=(1-p)T_{OK}+p(T_{OK}+T_{MP})=T_{OK}+p{T}_{MP}$;當 p = 0.5(隨機分支)時 $T_{ran}=T_{OK}+0.5T_{MP}$,故 $T_{MP}=2(T_{ran}-T_{OK})$。
• 書中 Haswell 實測:$T_{OK}=8$、$T_{ran}=17.5$ → $T_{MP}=19$ cycles(單次呼叫介於 8~27 cycles);cmov 版恆為 ~8 cycles,與資料無關。(Practice 3.19 同型計算)

cmovXX S, R 指令特性 (Figure 3.18, p.253):

• 條件名稱/旗標公式同 set、jXX;來源 S 可為暫存器或記憶體,目的 R 必為暫存器。
• 運算元長度 16/32/64-bit,不支援單一位元組 cmov。
• 指令名不帶長度後綴:組譯器由目的暫存器名稱推斷長度(與 movw/movl 不同)。
• 處理器執行 cmov 無須預測:讀來源、查條件碼、決定寫或不寫目的暫存器。

3.6.7 Loops(p.256–268)

C 的 do-while、while、for 在機器碼沒有對應指令,全部由「條件測試 + 跳轉」組合而成;gcc 依兩種基本 loop pattern 產生程式碼。

Do-While(p.256)

loop:
    body-statement
    t = test-expr;
    if (t) goto loop;      <-- body 至少執行一次

範例 fact_do(n!,Figure 3.19):迴圈核心即 imulq %rdi,%rax + subq $1,%rdi + cmpq $1,%rdi + jg .L2——回跳的條件跳轉是實作迴圈的關鍵指令。

While — 兩種翻譯策略(p.259–263)

 Jump to middle:                Guarded do:
     goto test;                     t = test-expr;
 loop:                              if (!t) goto done;
     body-statement             loop:
 test:                              body-statement
     t = test-expr;                 t = test-expr;
     if (t) goto loop;              if (t) goto loop;
                                done:

• while 與 do-while 的差異:test-expr 先求值,body 可能一次都不執行(如 fact_while 正確算出 0! = 1)。
• Guarded-do 的細節(Figure 3.21):fact_while 在 -O1 下,迴圈內測試由 n > 1 被改寫為 n != 1(jne)——編譯器推得進入迴圈時必有 n>1,遞減後只可能 n>1 或 n=1,兩測試等價。反向工程時別被這種變形誤導。

For(p.264–268)

for (init-expr; test-expr; update-expr) body-statement 依 C 標準(僅一例外,見下)等價於:

init-expr;
while (test-expr) {
    body-statement
    update-expr;
}

再套用 jump-to-middle 或 guarded-do 其中之一(依最佳化等級)。fact_for 在 -Og 下:init(result=1; i=2)→ jmp .L8(test)→ loop 內 imulq %rdx,%rax; addq $1,%rdx → cmpq %rdi,%rdx; jle .L9。

3.6.8 Switch 陳述(p.268–274)

switch 提供依整數索引的多路分支 (multiway branch),以 jump table 高效實作:jump table 是一個陣列,第 i 項存「switch 索引等於 i 時應執行之程式區塊的位址」。

• 優點:執行 switch 的時間與 case 數量無關——即使數百個 case 也只需一次 jump table 存取,勝過一長串 if-else。
• gcc 依 case 數量與值的疏密 (sparsity) 決定翻譯方式:case 較多(約 4 個以上)且值域跨度小時用 jump table;否則退化為 if-else 鏈。

範例 switch_eg(cases 100, 102–104, 106;缺 101、105;104/106 共用;102 fall through,p.270–271):

 n ---> subq $100, %rsi        index = n - 100(平移到 0..6)
         |
         cmpq $6, %rsi
         ja   .L8  --------->  default        <-- ja 是 unsigned 比較:
         |                                        負 index 視為極大正數,
         jmp  *.L4(,%rsi,8)                       一條指令同時攔 <0 與 >6
         |
         v  jump table (.rodata, 8-byte entries)
 .L4: +----------+
   [0]| .quad .L3| case 100 -> loc_A: val = 13*x
   [1]| .quad .L8| case 101 -> default   <-- 缺的 case 填 default 標籤
   [2]| .quad .L5| case 102 -> loc_B: x += 10, fall through(區塊尾不放 jmp)
   [3]| .quad .L6| case 103 -> loc_C: val = x + 11
   [4]| .quad .L7| case 104 -> loc_D: val = x * x
   [5]| .quad .L8| case 105 -> default
   [6]| .quad .L7| case 106 -> loc_D  <-- 重複 case 共用同一標籤
      +----------+

• 索引跳轉:jmp *.L4(,%rsi,8) 為 indirect jump,以 label .L4 為基底、index×8 取出 8-byte 目標位址。
• Jump table 宣告於目的檔的 .rodata(read-only data)段:.align 8 對齊後放七個 .quad,每項值為對應組語 label 的指令位址。
• gcc 的 C 語言擴充:&&label 運算子建立「程式碼位置」的指標(類比 & 取資料指標),配合 computed goto goto *jt[index]; 可用 C 描述 jump table 行為(Figure 3.22(b) 的 switch_eg_impl)。
• Fall through(case 102 → 103):組語中該區塊尾端省略 jmp .L2,自然流入下一區塊;C 版對應區塊尾無 goto。
• 範圍檢查技巧:index 以 unsigned 看待——二補數的負數映為極大正數,單一 ja $6(above)即涵蓋「index < 0 或 index > 6」兩種出界情況。
• 反向操作(Practice 3.30/3.31):由入口的 addq $2, %rdi(偏移量 = −最小 case 值)、table 長度、與 table 中重複/指向 default 的項目,可反推 case 標籤值、多重標籤與 fall-through 結構。

Exam/Test Patterns

Related Notes

• 03-Machine-Level-Programs/01-Program-Encodings-and-Data-Formats
• 03-Machine-Level-Programs/02-Data-Movement-and-Arithmetic
• 03-Machine-Level-Programs/04-Procedures-and-the-Stack
• 03-Machine-Level-Programs/05-Arrays-and-Data-Structures
• 02-Information-Representation/03-Integer-Arithmetic
• 04-Processor-Architecture/04-Pipelining-Principles
• 05-Program-Optimization/02-Modern-Processor-Operation
• 07-Linking/02-Symbol-Resolution-and-Relocation