資料搬移與算術運算 (Data Movement & Arithmetic)

Overview Table

3.4 存取資訊:16 個整數暫存器 (p.215-216)

x86-64 CPU 有 16 個 64-bit 通用暫存器,名稱皆以 %r 開頭,存放整數與指標。歷史演進:8086 的 8 個 16-bit 暫存器(%ax–%bp)→ IA32 擴為 32-bit(%eax–%ebp)→ x86-64 擴為 64-bit(%rax–%rbp)並新增 %r8–%r15。指令可操作各暫存器的低位 1、2、4、8 bytes。

 63              31          15      7      0
 +---------------+-----------+-------+------+
 |            %rax            (64-bit)      |   <- movq 存取全部
 |               |        %eax (32-bit)     |   <- movl(高 4 bytes 清 0!)
 |               |           |  %ax (16-bit)|   <- movw(其餘 bytes 不變)
 |               |           |       | %al  |   <- movb(其餘 bytes 不變)
 +---------------+-----------+-------+------+

• %rsp 最特殊:指向 run-time stack 的頂端位置,部分指令隱含讀寫它;其餘 15 個用途較彈性,但受標準程式慣例(stack 管理、傳參、回傳值、暫存資料)約束。
• 參數傳遞順序:%rdi, %rsi, %rdx, %rcx, %r8, %r9,回傳值在 %rax(細節見 03-Machine-Level-Programs/04-Procedures-and-the-Stack)。

3.4.1 Operand Specifiers:三類運算元與定址模式 (p.216-218)

運算元(operand)有三型:immediate(常數,ATT 格式寫 $Imm,如 $-577、$0x1F;不同指令允許不同範圍,assembler 自動選最精簡編碼)、register(R[ra],把暫存器組視為以識別碼索引的陣列 R)、memory reference(依計算出的 effective address 存取記憶體,記為 M[Addr];b-byte 值寫作 $M_b[\text{Addr}]$,通常省略下標 b)。

• 最一般形式 Imm(rb,ri,s) 的 effective address 公式:$\text{EA}=\text{Imm}+R[r_b]+R[r_i]\cdot s$
• scale factor s 只能是 1, 2, 4, 8;base 與 index 必須是 64-bit 暫存器。
• 其他形式都是此一般式省略某些成分的特例;常用於存取陣列/結構元素(見 03-Machine-Level-Programs/05-Arrays-and-Data-Structures)。

3.4.2 資料搬移指令 (p.218-222)

mov class 是最常用的指令類:movb(1B)、movw(2B)、movl(4B)、movq(8B),把資料由來源複製到目的地,不做任何轉換。來源可為 immediate / register / memory;目的可為 register / memory。

 來源 -> 目的 的 5 種合法組合:
 Imm --> Reg     movl $0x4050,%eax
 Imm --> Mem     movb $-17,(%rsp)
 Reg --> Reg     movw %bp,%sp
 Reg --> Mem     movq %rax,-12(%rbp)
 Mem --> Reg     movb (%rdi,%rcx),%al
 Mem -X-> Mem    禁止!需經暫存器分兩步:load -> store

movl 例外:目的地為暫存器時,movl 會把高 4 bytes 設為 0(p.219)。示範(p.220 Aside):

movabsq $0x0011223344556677, %rax    %rax = 0011223344556677
movb    $-1, %al                     %rax = 00112233445566FF   (其餘不變)
movw    $-1, %ax                     %rax = 001122334455FFFF   (其餘不變)
movl    $-1, %eax                    %rax = 00000000FFFFFFFF   (高 4B 清零!)
movq    $-1, %rax                    %rax = FFFFFFFFFFFFFFFF

零延伸與符號延伸(小 → 大複製)

• 指令名最後兩字元:第一個是來源大小、第二個是目的大小(如 movzbq = byte → quad word,零延伸)。
• 沒有 movzlq!4-byte → 8-byte 零延伸直接用 movl(利用「產生 32-bit 值即清高 4 bytes」的性質);符號延伸則三種來源大小(b/w/l)到 64-bit 皆有支援。
• 三種 byte 搬移的差異(p.222 Aside),設 %rax = 0011223344556677、%dl = AA:
  • movb %dl,%al → %rax = 00112233445566AA(只改 1 byte)
  • movsbq %dl,%rax → %rax = FFFFFFFFFFFFFFAA(0xAA 最高位為 1,符號延伸填 FF)
  • movzbq %dl,%rax → %rax = 00000000000000AA(一律填 0)

3.4.3 資料搬移範例 (p.222-225)

long exchange(long *xp, long y) {      exchange:                  xp in %rdi, y in %rsi
    long x = *xp;                        movq (%rdi), %rax        取 *xp,設為回傳值
    *xp = y;                             movq %rsi, (%rdi)        把 y 寫入 xp 指向處
    return x;                            ret
}

• C 的 pointer 就是位址:dereference = 把指標複製進暫存器,再用該暫存器做 memory reference(indirect 定址)。
• 區域變數常放在暫存器而非記憶體——暫存器存取遠快於記憶體。
• &(address-of)產生指標;* 做 dereference,讀(右值)寫(左值)皆可;把指標傳入函式即可讓函式修改遠端位置的資料(p.224 New to C)。
• 帶大小與 signedness 同時轉換的 cast:先改大小、再改 signedness(p.224,呼應 02-Information-Representation/02-Integer-Representations 2.2.6)。

3.4.4 Push 與 Pop (p.225-227)

Stack 是 LIFO(last-in, first-out)結構:push 加入、pop 移除,pop 出的一定是最近 push 且仍在 stack 上的值。x86-64 的 program stack 存於記憶體某區域,向低位址成長——stack 頂端元素的位址是所有元素中最低的;%rsp 保存頂端元素位址。習慣上把 stack 圖畫成上下顛倒(top 在下)。

     初始                pushq %rax             popq %rdx
  %rax 0x123           %rax 0x123             %rax 0x123
  %rdx 0               %rdx 0                 %rdx 0x123
  %rsp 0x108           %rsp 0x100             %rsp 0x108

  高位址 (stack bottom)
      |    ...    |       |    ...    |          |    ...    |
0x108 |___________|<-rsp  |___________|    0x108 |___________|<-rsp
      (top)         0x100 |__0x123____|<-rsp     |__0x123____|  <- 值仍留在記憶體,
  低位址 (成長方向 ↓)        (new top)                但已不屬於 stack

• pushq %rbp 等價於 subq $8,%rsp + movq %rbp,(%rsp),但 pushq 機器碼只需 1 byte(兩指令組合共 8 bytes)。
• popq %rax 等價於 movq (%rsp),%rax + addq $8,%rsp。
• pop 後值仍留在原記憶體位置直到被覆寫;stack top 永遠以 %rsp 為準。
• stack 與程式碼、其他資料同在一個記憶體,可用標準定址存取 stack 內任意位置:movq 8(%rsp),%rdx 取 stack 第二個 quad word。

3.5 算術與邏輯運算總表 (p.227-228)

分四組:load effective address、unary、binary、shift。除 leaq 外皆為指令類(各有 b/w/l/q 四種大小,如 add 類 = addb/addw/addl/addq)。

3.5.1 Load Effective Address:leaq (p.227-229)

leaq 形式上像「從記憶體讀到暫存器」的 movq 變體,但完全不存取記憶體——它把第一運算元的 effective address 直接複製到目的地(即 C 的 &S)。用途:(1) 產生之後要用的指標;(2) 精簡表達算術:一條指令算出 $\text{Imm}+r_b+r_i\cdot s$。

• 例:%rdx 存 x,則 leaq 7(%rdx,%rdx,4), %rax → %rax = 5x + 7。
• 目的地必須是暫存器;編譯器常把 leaq 用在與定址完全無關的巧妙運算上。
• 編譯範例 scale(p.229):t = x + 4*y + 12*z 用三條 leaq 完成:

leaq (%rdi,%rsi,4), %rax      x + 4*y
leaq (%rdx,%rdx,2), %rdx      z + 2*z = 3*z
leaq (%rax,%rdx,4), %rax      (x+4*y) + 4*(3*z) = x + 4*y + 12*z

3.5.2 一元與二元運算 (p.230)

• Unary(inc/dec/neg/not):唯一 operand 同時是來源與目的,可為 register 或 memory。如 incq (%rsp) 直接把 stack 頂端 8-byte 值 +1。語法對應 C 的 ++ / --。
• Binary(add/sub/imul/xor/or/and):第二 operand 既是來源也是目的,對應 C 的複合指定(x -= y)。
  • subq %rax,%rdx 是 %rdx = %rdx − %rax(讀作「subtract %rax from %rdx」),非交換運算尤其易錯。
  • 第一 operand 可為 imm/reg/mem;第二可為 reg/mem;兩者不可同為 memory(同 mov 限制)。
  • 目的為 memory 時,處理器需 read → op → write back 三步。

3.5.3 位移運算 (p.230-231)

移位量在前、被移值在後。移位量可為 immediate 或單一 byte 暫存器 %cl——這是少數只允許特定暫存器當 operand 的指令。目的 operand 可為 register 或 memory。

• 左移:sal = shl(效果完全相同,右側補 0)。
• 右移:sar(arithmetic,補符號位)vs shr(logical,補 0),對應 C 中 signed vs unsigned 右移(位元行為見 02-Information-Representation/01-Information-Storage-and-Bits)。

3.5.4 討論:signed / unsigned 通用性 (p.232)

Figure 3.10 中絕大多數指令對 unsigned 與 two's-complement 運算通用,只有右移需要區分 signed(sar)/ unsigned(shr)版本——這正是 two's-complement 成為 signed 整數首選實作方式的原因之一(呼應 02-Information-Representation/03-Integer-Arithmetic)。

範例 arith(p.232):C 的 z*48 被編譯成 leaq (%rdx,%rdx,2),%rax(×3)+ salq $4,%rax(×16);同一暫存器 %rax 依序承載 3*z、48*z、t4——編譯器會讓單一暫存器輪流存放多個程式值,並在暫存器間搬移。

3.5.5 特殊算術:128-bit 乘除 (p.233-236)

兩個 64-bit 數相乘可能需 128 bits 表示(見 2.3)。Intel 稱 16-byte 量為 oct word;x86-64 以暫存器對 %rdx(高 64 bits):%rax(低 64 bits) 合成一個 128-bit 值,提供有限的 128-bit 支援。

• imulq 有兩種形態:雙運算元(Figure 3.10,積截斷成 64-bit,實作 *u64 與 *t64;截斷後 signed / unsigned 位元行為相同)與單運算元(128-bit 全積);assembler 以 operand 個數區分。
• 全乘法:一個因數必須放 %rax,另一個為指令 source operand;積存於 %rdx:%rax。
• 128-bit 積存回記憶體需兩條 movq:低 8B 存 (%rdi)、高 8B 存 8(%rdi)——little-endian,高位 bytes 放較高位址(p.235 store_uprod 範例)。
• 除法前準備 128-bit dividend(常見情況:被除數只有 64-bit,放 %rax):
  • Signed:執行 cqto,把 %rax 符號位複製滿整個 %rdx(無 operand,隱含使用)。
  • Unsigned:事先把 %rdx 清為 0。

 signed 除法 x / y 的資料流(remdiv, p.236):
        %rdx (高 64)      %rax (低 64)
 cqto:  [sign bits of x][      x      ]   <- 128-bit dividend
                   |  idivq S(除數 = S)
                   v
        %rdx = 餘數 (x mod S)    %rax = 商 (x ÷ S)

• remdiv 範例:因 %rdx 被除法徵用,原本放在 %rdx 的參數 qp 必須先搬到別的暫存器(movq %rdx,%r8),再 movq %rdi,%rax → cqto → idivq %rsi,最後把 %rax(商)、%rdx(餘)分別存回 *qp、*rp。

Exam/Test Patterns

Related Notes

• 03-Machine-Level-Programs/01-Program-Encodings-and-Data-Formats — 指令字尾與資料大小(b/w/l/q)的來源
• 03-Machine-Level-Programs/03-Control-Flow — 3.6 起:condition codes 與跳躍指令
• 03-Machine-Level-Programs/04-Procedures-and-the-Stack — push/pop 與參數傳遞慣例的完整應用
• 03-Machine-Level-Programs/05-Arrays-and-Data-Structures — scaled indexed 定址在陣列存取的應用
• 02-Information-Representation/03-Integer-Arithmetic — 截斷乘法、算術/邏輯右移的位元層行為
• 02-Information-Representation/02-Integer-Representations — 符號/零延伸與 casting 順序規則