程式的機器級表示練習題 (Practice - Machine-Level Programs)

Key Patterns (click to expand)

關鍵字 / 情境	答案
定址模式 `Imm(rb,ri,s)`	EA = Imm + R[rb] + R[ri]×s;s 只能是 1/2/4/8
`movl` 寫入暫存器	高 4 bytes 一律清 0;`movb`/`movw` 其餘 bytes 不變
mov 兩 operand 限制	不可同為 memory;memory-to-memory 需經暫存器兩步
`leaq`	只算位址不碰記憶體;不改 condition codes
`cmp S1,S2` / `test S1,S2`	依 S2−S1 / S1&S2 設旗標,不寫回
signed vs unsigned 條件	`l/g/ge/le` 用 SF^OF 組合;`a/b/ae/be` 用 CF/ZF
PC-relative 跳轉	目標 = 下一條指令位址 + 二補數 offset
`call` / `ret`	push 返回位址(call 下一條指令)並跳轉 / pop 回 PC
前 6 個整數引數	`%rdi %rsi %rdx %rcx %r8 %r9`;回傳值 `%rax`
callee-saved	`%rbx` `%rbp` `%r12`–`%r15`(共 6 個)
陣列元素位址	`&A[i] = xA + Li`;二維 `&D[i][j] = xD + L(C*i + j)`
指標 cast	改 type 不改 value,但改指標算術縮放
浮點參數 / 回傳	`%xmm0`–`%xmm7`(與整數分開計數);回傳 `%xmm0`;全 caller-saved
FP→int 轉換	`vcvttsd2si(q)` 一律截斷(round toward zero)
buffer overflow 三道防線	ASLR、canary(stack protector)、NX bit

Question 1 - mov 指令限制 [recall]

同事寫了一行組語 movq (%rax), (%rbx),想把一個 quad word 從某記憶體位置直接複製到另一個記憶體位置,結果組譯失敗。
請說明原因,以及正確的做法。

查看答案

mov 指令的兩個 operand 不可同時是 memory reference。
memory-to-memory 複製必須經過暫存器分兩步:先 load 再 store,例如:
movq (%rax), %rdx → movq %rdx, (%rbx)。
這是 mov 系列的三大限制之一(另兩個:字尾須與暫存器大小一致;movq 的 immediate 限 32-bit 符號延伸,任意 64-bit 需 movabsq)。

Question 2 - 部分暫存器寫入慣例 [recall]

已知 %rax = 0x0011223344556677。分別執行以下三條指令(各自獨立,都從此初始值開始),%rax 最後的值是多少?

movb $-1, %al
movw $-1, %ax
movl $-1, %eax

查看答案

movb:0x00112233445566FF(產生 1-byte 結果,其餘 bytes 不變)
movw:0x001122334455FFFF(產生 2-byte 結果,其餘 bytes 不變)
movl:0x00000000FFFFFFFF(產生 4-byte 結果時高 4 bytes 一律清 0)
這也是為什麼沒有 movzlq——4B→8B 零延伸直接用 movl 即可。

Question 3 - 定址模式計算 [application]

已知 %rdx = 0xf000、%rcx = 0x0100,記憶體 M[0xf400] = 0xAB。
求下列各 operand 的值:(a) $0x100 (b) 0xf000 (c) (%rdx,%rcx) (d) 0x300(%rdx,%rcx,4)

查看答案

(a) 0x100(有 $ 是 immediate 常數本身)
(b) M[0xf000](無括號的純數字是 Absolute 定址,取記憶體值)
(c) M[0xf000 + 0x100] = M[0xf100]
(d) EA = 0x300 + 0xf000 + 0x100×4 = 0xf700,operand 值為 M[0xf700]
通用公式:EA = Imm + R[rb] + R[ri]×s,s ∈ {1,2,4,8}。

Question 4 - leaq 的算術用途 [application]

函式參數 x 在 %rdi、y 在 %rsi。編譯器產生:

leaq (%rdi,%rsi,4), %rax
leaq (%rax,%rax,2), %rax

執行完後 %rax 是 x 與 y 的什麼運算式?這兩條指令有讀取記憶體嗎?

查看答案

第一條:%rax = x + 4y;第二條:%rax = (x+4y) + 2(x+4y) = 3(x + 4y) = 3x + 12y。
完全沒有記憶體存取——leaq 只把來源 operand 的 effective address 複製到目的暫存器(目的地必須是暫存器),編譯器常拿它做 Imm + rb + ri*s 形式的精簡算術。
另外 leaq 是 Figure 3.10 中唯一不改 condition codes 的算術類指令。

Question 5 - Condition codes 與 cmp/test [recall]

說出 x86-64 四個 condition code 旗標的名稱與意義,並說明 cmpq %rsi, %rdi 與 testq %rax, %rax 各依據什麼運算設定旗標。

查看答案

四旗標:CF(carry,unsigned overflow)、ZF(結果為零)、SF(結果為負)、OF(signed overflow)。
cmp S1,S2 依 S2 − S1(同 sub 但不寫回目的地),故 cmpq %rsi,%rdi 依 %rdi − %rsi 設旗標。
test S1,S2 依 S1 & S2(同 and 但不寫回);testq %rax,%rax 是判斷 %rax 為負/零/正的慣用寫法。

Question 6 - set 指令與完整結果 [recall]

組語中出現 setl %al。後綴 l 是表示 operand 大小為 4 bytes 嗎?若要把比較結果變成完整的 32-bit int 回傳值,後面還需要哪條指令?

查看答案

不是。set 的後綴表示「條件」而非大小——setl = set less(signed <,旗標公式 SF ^ OF),目的地固定是 1 byte。
要得到完整結果需再用 movzbl %al, %eax 零延伸清高位(且寫 4-byte 結果會連 %rax 上半 4 bytes 一併清零)。

Question 7 - PC-relative 跳轉計算 [application]

反組譯輸出如下(左為位址、中為機器碼):

  4004d0: 48 89 f8    mov  %rdi,%rax
  4004d3: eb 03       jmp  XXXXXX
  4004d5: 48 d1 f8    sar  %rax

jmp 指令的目標位址 XXXXXX 是多少?若 offset byte 是 0xf8 而非 0x03,目標又是多少?

查看答案

PC-relative 編碼:目標 = 下一條指令位址 + 二補數 offset。
jmp 的下一條指令在 0x4004d5,offset = 0x03 → 目標 = 0x4004d8。
若 offset = 0xf8(1-byte 二補數 = −8)→ 目標 = 0x4004d5 − 8 = 0x4004cd(向後跳)。
這種編碼的好處:精簡,且連結器搬移程式碼後 offset 不需修改。

Question 8 - call/ret 與返回位址 [recall]

main 中位址 0x400563 處有一條 5-byte 的指令 callq 400540 <multstore>,執行前 %rsp = 0x7fffffffe840。
執行 callq 後:(a) %rsp 是多少?(b) M[%rsp] 存什麼值?(c) 這個返回位址屬於誰的 stack frame?

查看答案

(a) %rsp = 0x7fffffffe838(call 先將 %rsp 減 8 再 push)
(b) 0x400568 —— 返回位址是 call 的下一條指令位址(0x400563 + 5),不是 call 本身的位址
(c) 屬於呼叫者 (caller) 的 stack frame,因為它保存的是 caller 的狀態
ret 則 pop 出此位址回 PC,%rsp 加 8 復原。

Question 9 - 參數傳遞慣例 [recall]

函式 void proc(long a, int b, char c, short d, long e, int f, long g, char *h) 共 8 個引數。
前 6 個引數各放在哪個暫存器(注意大小)?第 7、8 個引數放哪?被呼叫者透過什麼位址存取它們?

查看答案

依序:a→%rdi、b→%esi、c→%dl、d→%cx、e→%r8、f→%r9d(名稱依大小換用子暫存器)。
第 7 個以後由 caller 放入自己 frame 的 argument build area,引數 7 在最低位址,每個引數向上取整至 8 bytes。
call 之後(return address 佔 0(%rsp)),callee 看到 g 在 8(%rsp)、h 在 16(%rsp)。回傳值放 %rax。

Question 10 - callee-saved 暫存器 [recall]

哪些暫存器是 x86-64 的 callee-saved?若函式 P 有一個值需要跨越對 Q 的呼叫仍然存活,有哪兩種做法?

查看答案

callee-saved 共 6 個:%rbx、%rbp、%r12–%r15(%rsp 特殊,不屬兩類)。
兩種做法:(1) 放進 callee-saved 暫存器——callee 若要用必須 push 保存、返回前反序 pop 還原;(2) caller 自己在呼叫前把值存到 stack。
其餘暫存器(%rax、六個參數暫存器、%r10、%r11)皆為 caller-saved,callee 可任意覆寫。

Question 11 - 二維陣列位址反推 [analysis]

某函式 int f(long i, long j) 回傳 A[i][j],其中 A 是 int A[M][N]。gcc 產生:

leaq (%rdi,%rdi,2), %rax      # i 在 %rdi、j 在 %rsi
leaq (%rdi,%rax,4), %rax
addq %rsi, %rax
movl A(,%rax,4), %eax

由這段組語能否推出 N?N 是多少?請說明由組語反推二維陣列維度的一般方法(M 能否推出?)。

查看答案

逐步追蹤:第一條 %rax = 3i;第二條 %rax = i + 4*(3i) = 13i;第三條 %rax = 13i + j;最後存取 M[xA + 4*(13i + j)]。
對照 row-major 公式 &A[i][j] = xA + L*(N*i + j):L = 4(movl 的 scale)、乘在列索引 i 上的係數 = N = 13(每列元素數)。
一般方法:把 leaq/位移鏈化簡成 xA + L*(C*i + j),C 即第二維大小;第一維 M 不參與位址計算,無法從這段組語推出(只能由範圍檢查等其他線索得知)。

Question 12 - 指標 cast 與縮放 [application]

p 是 char *,其值為位址 p。以下兩個 C 運算式各計算出什麼位址?

(a) (int *) p + 7 (b) (int *) (p + 7)

查看答案

(a) p + 28:cast 優先於 +,先變成 int *(縮放單位 4),再 +7 → 前進 7×4 = 28 bytes
(b) p + 7:括號內先做 char * 算術(縮放 1)前進 7 bytes,cast 只改 type 不改 value
核心原則:casting 改變指標的 type 與後續算術縮放,但不改變 value;指標算術 p+i 的值 = p + L×i(L 為所指型別大小)。

Question 13 - buffer overflow 機制與防禦 [recall]

函式內有 char buf[8] 位於 %rsp(stack top),return address 在 %rsp+24,中間 16 bytes 未使用。程式用 gets 讀入字串。
(a) 輸入幾個字元會覆寫 return address?(b) 說出現代系統的三道防禦機制。

查看答案

(a) 24–31 個字元時覆寫 return address(0–7 安全;9–23 只破壞未用空間;32+ 波及 caller 狀態)。根本原因:C 不做邊界檢查,且區域緩衝區與 return address 同在 stack。
(b) 三道防線:ASLR / stack 隨機化(每次執行位址不同)、canary / stack protector(buf 與其餘狀態間放隨機 guard 值,返回前用 xorq %fs:40 比對,被改則 __stack_chk_fail)、NX bit(stack 可讀寫但不可執行)。
改善寫法:用 fgets 取代 gets;strcpy/strcat/sprintf 同屬危險函式。

Question 14 - cmov 的適用限制 [analysis]

以下函式被學生手動「最佳化」成 conditional move 版本:

long cread(long *xp) {
    return (xp ? *xp : 0);
}

cread_cmov:
  movq (%rdi), %rax      # v = *xp
  testq %rdi, %rdi
  movl $0, %edx
  cmove %rdx, %rax       # if (xp==NULL) v = 0
  ret

這段 cmov 版本有什麼致命問題?並歸納哪兩類情況不能或不該用 conditional move。

查看答案

cmov 策略會把兩邊的值都先算出來:movq (%rdi), %rax 在 xp == NULL 時仍會執行,造成 null pointer dereference 直接崩潰——即使 cmove 事後不採用該值也來不及。必須用條件跳轉版(先測試再決定是否解參考)。
兩類不適用情況:(1) 任一邊運算式有副作用或可能出錯(如本例、全域計數器遞增);(2) 任一邊計算量大時,條件不成立那邊的計算全數浪費,效率反而更差。gcc 只在兩邊都極簡單時才用 cmov。
cmov 的優勢來源:控制流不依賴資料,無須 branch prediction,pipeline 恆滿。

Question 15 - 浮點呼叫慣例 [recall]

函式宣告為 double f(int x, double y, long z, float w)。
(a) 四個參數各放在哪個暫存器?(b) 回傳值放哪?(c) 若 f 內部要讓一個浮點值跨越函式呼叫存活,能放某個 callee-saved 的 XMM 暫存器嗎?

查看答案

(a) x→%edi、z→%rsi(整數/指標依序走通用暫存器);y→%xmm0、w→%xmm1(浮點依序走 XMM)。兩組計數各自獨立,與宣告中的整體位置無關。
(b) 浮點回傳值在 %xmm0。
(c) 不能——XMM 暫存器全部是 caller-saved,沒有任何 callee-saved;跨呼叫保留浮點值只能先存到 stack 或記憶體。

Question 16 - 浮點轉換與運算指令 [recall]

(a) C 的 (long) d(d 為 double)對應哪條指令?其捨入方式為何?
(b) vsubsd %xmm2, %xmm0, %xmm0 計算的是什麼?
(c) vmovaps 用於讀寫記憶體時要注意什麼?

查看答案

(a) vcvttsd2siq——一律截斷(round toward zero),指令名中第二個 t 即 truncation;反向 long→double 用三運算元的 vcvtsi2sdq(第二 source 只影響高位,可忽略)。
(b) %xmm0 ← %xmm0 − %xmm2:ATT 格式減/除是 D ← S2 − S1、D ← S2 / S1,反推 C 運算式時最易弄反。
(c) vmovaps/vmovapd(a = aligned)讀寫記憶體須 16-byte 對齊,否則觸發 exception;vmovss/vmovsd 則無對齊要求。

Pattern Summary (click to expand)

答題模式	要點
求 operand 值	先判型:`$`=immediate、純數字=absolute、括號=EA 公式 Imm+rb+ri×s
部分暫存器寫入	1/2-byte 結果:其餘不變;4-byte 結果:高 4 bytes 清 0
看到 `leaq`	翻成算術式 `Imm + base + index*s`,不讀記憶體、不改旗標
判斷 signed/unsigned	條件後綴 `l/g/ge/le`(SF^OF 系)vs `a/b/ae/be`(CF/ZF 系)
跳轉目標計算	下一條指令位址 + 二補數 offset(0xf8 = −8)
call/ret 追蹤	返回位址 = call 下一條指令;屬 caller 的 frame;%rsp ∓8
引數定位	前 6 個整數走 `%rdi %rsi %rdx %rcx %r8 %r9`;第 7 個起在 `8(%rsp)`
跨呼叫存活的值	callee-saved(%rbx %rbp %r12–%r15)或 caller 自存 stack
陣列/struct 反推	由縮放係數還原 `L(Ci+j)`;displacement = 欄位 offset
指標 cast 題	先看 cast 與括號的優先序,再套 p + L×i
overflow 題	算 buf 到 return address 的距離;防禦答 ASLR/canary/NX
cmov 判斷	有副作用/可能出錯/計算昂貴 → 必須用分支版
浮點慣例	XMM 參數與整數分開計數;回傳 %xmm0;全 caller-saved
FP 指令判讀	`vcvtt...` = 截斷;`vsub/vdiv` 是 S2 op S1;`vmovaps` 記憶體需 16B 對齊

Related Concepts

Question 1 - mov 指令限制 [recall]

Question 2 - 部分暫存器寫入慣例 [recall]

Question 3 - 定址模式計算 [application]

Question 4 - leaq 的算術用途 [application]

Question 5 - Condition codes 與 cmp/test [recall]

Question 6 - set 指令與完整結果 [recall]

Question 7 - PC-relative 跳轉計算 [application]

Question 8 - call/ret 與返回位址 [recall]

Question 9 - 參數傳遞慣例 [recall]

Question 10 - callee-saved 暫存器 [recall]

Question 11 - 二維陣列位址反推 [analysis]

Question 12 - 指標 cast 與縮放 [application]

Question 13 - buffer overflow 機制與防禦 [recall]

Question 14 - cmov 的適用限制 [analysis]

Question 15 - 浮點呼叫慣例 [recall]

Question 16 - 浮點轉換與運算指令 [recall]