Ch2：Instructions: Language of the Computer

本筆記只有抄到 2-12，因為後面的出題機率過低就不寫了
之後應該會補上

本章主要在讓讀者理解電腦真正能「聽懂」的是什麼語言——也就是機器指令（machine instructions），本章將從高階語言一路深入到底層的指令集結構。

2-1 Instruction

• Instruction set（指令集）：
  • 不同電腦有不同的指令集（但大部分相同）
  • 早期電腦使用較簡單的指令集

MIPS 指令集

本書所有指令都參考 MIPS

• 是 RISC 結構的代表
• 被廣泛運用在嵌入式系統
• 是許多現代指令集的經典

2-2 Operations of the Computer Hardware

2-3 Operands of the Computer Hardware

Regigster Operands

• 用於算數操作
• MIPS 共有 32 * 32-bit 的 register file
  • 用於高頻率存取資料
  • 編號從 0 ~ 31
  • 32-bit 的資料稱為一個 word
• Assembler name
  • Temporary Value：$t0 到 $t9
  • Static variables：$s0 到 $s7
  • $zero：MIPS register 中的預留常數，不可被 overwrite

Memory Operands

• Main memory 用來儲存複合資料
  • Array, Structure, Dynamic Data
• 每一個 memory address 對應到一個 bytes
• MIPS 是 Big Endian 的
  • Big Endian：MSB first
  • Little Endian：LSB first
    
• 範例：
  • h in $s2, A in $s3
  • C code
  ​​​​A[12] = h + A[8];
  

  • MIPS
  ​​​​lw $t0, 32($s3)
  ​​​​add $t0, $s2, $t0
  ​​​​sw $t0, 48($s3)
  

Immediate Operands

注意：Immediate Operands 不可以進行減法

• 在指令中的常數資料
• 不可被用於減法，可以透過加負數來進行減法

addi $s2, $s1, -1

2-4 Unsigned and Signed

Unsigned

• 無號數 -> 可以直接轉換
• e.g.
  $0000000000000000000000000000{1011}_2={11}_{10}$
• 範圍：
  $0$ ~
  $2^n-1$

2's-Complement

• 有號數
• 轉換方式：
  • 範例：-14(8-bit)
  • 先把無號數轉成 2 進位：
    $14=0000{1110}_2$
  • 0 -> 1, 1 -> 0：
    $0000{1110}_2=1111{0001}_2$
  • 加一：
    $1111{0010}_2$
• 範圍：
  $-2^{n-1}$ ~
  $2^{n-1}-1$
• Sign Extension：
  • 當我們要用更大容量的資料型態儲存我們的數字時，就必須做 sign extension
  • 正數補 0，負數補 1

Sign-magnitude

• 有號數，把 sign 和 magnitude 分開表示
• 轉換方式：
  • 範例：-14(8-bit)
  • Sign = 1（Negative）
  • Magnitude =
    $14=000{1110}_2$
  • Sign + Magnitude：
    $-14=1000{1110}_2$
• 範圍：
  $-2^{n-1}+1$ ~
  $2^{n-1}-1$

2-5 Representing Instructions in the Computer

• 所有 MIPS 指令大小都是 32-bits

R-format

• op: operation code (opcode)
  • R-format 一律放 0
• rs: first source register number
• rt: second source register number
• rd: destination source register number
• shamt: shift amount
• funct: function code (extend opcode)
  • R-format 放 opcode
• 範例：
  

I-format

• rt: destination or source register number

J-format

2-6 Logical Operation

• sll：左移
• srl：右移

2-7 Conditional Operations

條件判斷

• 條件判斷：當條件符合時跳到指定的 instruction
• 若不符合：繼續往下執行
• beq：if
  ​​​​beq rs, rt, L1
  

  • if (rs == rt) branch to instruction labeled L1
• bne：if not
  ​​​​bne rs, rt, L1
  

  • if (rs != rt) branch to instruction labeled L1
• slt：
  • MIPS：
    ​​​​​​​​slt rd, rs, rt
    

  • C code:
    ​​​​​​​​if (rs < rt) rd = 1; else rd = 0;
    

• sle：
  • MIPS：
    ​​​​​​​​slti rt, rs, constant
    

  • C code:
    ​​​​​​​​if (rs < constant) rt = 1; else rt = 0;
    

• j：jump
  • 直接跳到指定的 instruction

Loop statement

• C code：
  ​​​​while (save[i] == k) i += 1;
  

• MIPS：
  • i in $s3, k in $s5, address of save in $s6

Loop:
    sll $t1, $s3, 2
    add $t1, $t1, $s6
    lw $t0, 0($t1)
    bne $t0, $s5, Exit
    addi $s3, $s3, 1
    j Loop
Exit:...

Basic block

• 定義：Basic block 是一連串代碼，包含以下兩個特性：
  • 沒有內部分支（embedded branches），除了結尾（例如跳躍或條件分支）。
  • 沒有分支目標（branch targets），除了在區塊開頭。
• Compiler 會辨別程式裡的 Basic block 進行優化
  
  

Unsigned and Sign Comparison

• Signed：slt, slti
• Unsigned：sltu,sltui
  
  

2-8 Supporting Procedures in Computer Hardware

Register 使用

• $a0 ～ $a3: 參數暫存器（arguments）

  • 對應 register 4 ~ 7。
  • 用來傳遞函式的參數。

• $v0, $v1: 回傳值暫存器（result values）

  • 對應 register 2 和 3。
  • 用來存放函式的回傳值。

• $t0 ~ $t9: 暫時暫存器（temporary values）

  • 用來儲存臨時計算結果。
  • 可以被呼叫者覆寫（callee 可以自由使用，不用保留）。

• $s0 ~ $s7: 保存暫存器（saved variables）

  • 用來儲存需要保留的資料。
  • 必須由被呼叫者保存與恢復（callee 必須在進入與離開時處理）。

• $gp: global pointer

  • Register 28。
  • 指向靜態資料的全域指標。

• $sp: stack pointer

  • Register 29。
  • 指向目前 stack 的頂端，管理函式呼叫時的堆疊空間。

• $fp: frame pointer

  • Register 30。
  • 協助存取目前函式的參數與區域變數。

• $ra: return address

  • Register 31。
  • 儲存函式呼叫的返回位址（通常由 jal 指令自動寫入）。

Procedure call

• jal：jump and link
  • 語法：
    ​​​​​​​​jal ProcedureLabel
    

  • 功能：
    • 把下一條指令的 address 存到 $ra 裡，儲存跳回來的地方
    • 跳到 ProcedureLabel 所代表的副程式位置執行。
    • 執行完副程式後會自己跳回來
• jr：Jump register
  • 語法：
    ​​​​​​​​jr $ra
    

  • 功能：
    • 把 $ra 的內容複製到 PC(program counter)
    • 放在副程式裡面，這樣就會跳回主程式
• 比較：

  指令	全名	功能描述	是否儲存 return address	用途範例
  j	jump	無條件跳轉到指定的標籤（Address）	否	跳過一段程式碼
  jal	jump and link	跳轉到副程式並儲存返回 Address 至 $ra	是	呼叫副程式（function call）
  jr	jump register	跳轉到暫存器指定的 Address（通常是 $ra）	否	副程式返回、switch-case

Local Data on the Stack

注意，Stack 是倒過來長的

• Local data 會被 callee 分配的

• Procedure frame：

  • 用來存放副程式執行所需的資料
  • MIPS 會使用 $fp, $sp，來標記 procedure frame 的位置
  • 程式可以存取 procedure frame 內部的資料
    
    

• 以下資料需要用 stack 存：

  • $s0 ~ $s7
  • $ra
  • 第五個以上的 argument（$a0 ~ $a3 不夠存）

Leaf procedure

• 定義：不呼叫任何其他函式的函式
• Example：
  • C code：
    ​​​​​​​​ int leaf_example (int g, h, i, j){
    ​​​​​​​​ int f;
    ​​​​​​​​ f = (g + h) - (i + j);
    ​​​​​​​​ return f;
    ​​​​​​​​ }
    

  • MIPS code：
    • Arguments g, …, j in $a0, …, $a3
    • f in $s0 (hence, need to save $s0 on stack)
    • result in $v0
    ​​​​​​​​leaf_example:
    ​​​​​​​​    # Save $s0 on stack
    ​​​​​​​​    addi $sp, $sp, -4
    ​​​​​​​​    sw $s0, 0($sp)
    ​​​​​​​​    
    ​​​​​​​​    # Body
    ​​​​​​​​    add $t0, $a0, $a1
    ​​​​​​​​    add $t1, $a2, $a3
    ​​​​​​​​    sub $s0, $t0, $t1
    ​​​​​​​​    
    ​​​​​​​​    # Result
    ​​​​​​​​    add $v0, $s0, $zero
    ​​​​​​​​    
    ​​​​​​​​    # Restore $s0
    ​​​​​​​​    lw $s0, 0($sp)
    ​​​​​​​​    addi $sp, $sp, 4
    ​​​​​​​​    
    ​​​​​​​​    # return
    ​​​​​​​​    jr $ra
    

    • sw：把 register 的資料 store 到 memory 中
    • lw：把 memory 的資料 load 到 register 中

Non Leaf Procedure

• 定義：有呼叫其他函式的函式
• Example:
  • C code：
    ​​​​​​​​int fact (int n){
    ​​​​​​​​    if (n < 1) return 1;
    ​​​​​​​​    else return n * fact(n - 1);
    ​​​​​​​​}
    

  • MIPS：
    • Argument n in $a0
    • Result in $v0
    ​​​​​​​​fact:
    ​​​​​​​​    addi $sp, $sp, -8
    ​​​​​​​​    sw $ra, 4($sp)
    ​​​​​​​​    sw $a0, 0($sp)
    ​​​​​​​​    
    ​​​​​​​​    # test for n < 1
    ​​​​​​​​    slti $t0, $a0, 1
    ​​​​​​​​    beq $t0, $zero, L1
    ​​​​​​​​    
    ​​​​​​​​    addi $v0, $zero, 1
    ​​​​​​​​    addi $sp, $sp, 8
    ​​​​​​​​    jr $ra
    ​​​​​​​​    
    ​​​​​​​​L1:
    ​​​​​​​​    # recursive call
    ​​​​​​​​    jar fact
    ​​​​​​​​    
    ​​​​​​​​    lw $a0, 0($sp)
    ​​​​​​​​    lw $ra, 4($sp)
    ​​​​​​​​    addi $sp, $sp, 8
    ​​​​​​​​    
    ​​​​​​​​    mul $v0, $a0, $v0 
    ​​​​​​​​    
    ​​​​​​​​    jr $ra
    

    • 呼叫在其他函式後，register 中的 $a0, $ra 會被改變，需要用 lw 來還原

Memory layout

• Text：code
• Static data：Global variables
• Dynamic data：儲存於 heap，屬於動態分配的記憶體
  • e.g. malloc
• Stack：自動存取
  
  

2-9 Communicating with People

• ASCII：128 characters
• Unicode：256 characters
  
  

2-10 MIPS Addressing for 32-bit Immediates and Addresses

Byte/Halfword Operations

• 主要處理較小單位的應用
  • byte = 8 bit
  • halfword = 16 bit
• lb：讀取 8 bits 擴充有號數到 32 bits

lb rt, offset(rs)

• lh：讀取 16 bits 擴充有號數到 32 bits

lh rt, offset(rs)

• lbu：讀取 8 bits 擴充無號數到 32 bits

lbu rt, offset(rs)

• lhu：讀取 16 bits 擴充無號數到 32 bits

lhu rt, offset(rs)

• sb：只儲存最低 byte

sb rt, offset(rs)

• sb：只儲存最低 byte

sb rt, offset(rs)

• sh：只儲存最低 halfword

sh rt, offset(rs)

32-bit Constant

• 大部分的常數都只有 16 bit
• 我們可以透過下方方式來組合出一個 32 bit 常數
  ​​​​lui $s0 upper_16_bits
  ​​​​ori $s0 $s0 lower_16_bits
  

  • lui：把 16 bit 存到高 16 位
  • ori：利用 or 運算儲存低 16 位
    
    

Branch Addressing

Branch Addressing 用於目標 address 在 PC 附近的情況（移動範圍：16 bit）

• 大部分的目標都在鄰近的 branch 上
  • 可以用前進、後退的方式查找
    
    
• PC-relative addressing：
  • 目標 address = PC（現在的 address） + offset
    $\times$ 4

Jump Addressing

Jump Addressing 用於目標 address 離 PC 很遠的情況（移動範圍：26 bit）

• Jump（j, jal）指令可以允許程式移動到 Text segment 中的任何地方
• J format：
  • 目標 address = PC31…28 : (address
    $\times$ 4)

Branch Far Away

我們可以使用 j 指令來取代 branch 太遠的情形

• 改善前：
  ​​​​beq $s0, $s1, L1 # 16 bits
  

  • L1 太遠，我們抓不到
• 改善後：
  ​​​​bne $s0, $s1, L2 # 16 bits
  ​​​​j L1             # 26 bits
  ​​​​
  ​​​​L2: ...
  

  • 使用 j 來存取 L1

MIPS 存址的五大模式

2-12 Translating and Starting a Program