# MIPS 指令集概述

MIPS 指令集設計遵循 RISC 原則，每條指令的長度固定（32-bit），且指令種類精簡，主要分為以下幾類：

# 1. R 型（Register 型）

• 純寄存器運算（不涉及記憶體存取）

• 通常用於算術與邏輯運算

• 格式：

opcode | rs | rt | rd | shamt | funct

31      26 25    21 20    16 15    11 10     6 5        0
+----------+--------+--------+--------+--------+----------+
|  opcode  |   rs   |   rt   |   rd   | shamt  |  funct   |
+----------+--------+--------+--------+--------+----------+
    6位元     5位元    5位元    5位元    5位元     6位元

• 範例：

add $t0, $t1, $t2  # $t0 = $t1 + $t2
sub $s1, $s2, $s3  # $s1 = $s2 - $s3

# 2. I 型（Immediate 型）

• 來源或目標包含一個立即值（constant）

• 常用於記憶體存取、條件分支與數學運算

• 格式：

opcode | rs | rt | immediate

31      26 25    21 20    16 15                        0
+----------+--------+--------+---------------------------+
|  opcode  |   rs   |   rt   |        immediate          |
+----------+--------+--------+---------------------------+
    6位元     5位元    5位元             16位元

• 範例：

addi $t0, $t1, 10  # $t0 = $t1 + 10
lw   $s1, 4($s2)   # $s1 = Memory[$s2 + 4]
beq  $t0, $t1, LABEL # 若 $t0 == $t1 則跳轉到 LABEL

# 3. J 型（Jump 型）

• 用於跳轉（Jump）

• 格式：

opcode | address

31      26 25                                          0
+----------+---------------------------------------------+
|  opcode  |                  address                    |
+----------+---------------------------------------------+
    6位元                     26位元

• 範例：

j  MAIN   # 直接跳轉到 MAIN
jal FUNC  # 跳轉到 FUNC 並存返回地址（$ra）

# MIPS 指令分類

# 1. 算術與邏輯指令

您說得對，我的表格中確實缺少了一些 MIPS 指令，包括剛才我們討論的 NOR 指令。讓我補充一個更完整的算術與邏輯指令表格：

# 2. 記憶體存取指令

# 3. 流程控制指令

# MIPS 註冊表（Registers）

MIPS 共有 32 個通用寄存器，通常以 $0~$31 表示，部分寄存器有特殊用途：

# C 語言轉換成組合語言

# 陣列的實現

• C code:

A[12] = h + A[8];

h in $s2 ,base address of A in $s3

• Compiled MIPS code:

lw $t0, 32($s3)
add $t0, $s2, $s0
sw $t0, 48($s3)

# copy variable

• C code:

a = b;

• Compiled MIPS code:

add $t0, $s1, $zero

# NOT Operation

MIPS 裡沒有 NOT 這個指令但可以特過 NOR 搭配 $zero 來達成功能

• C code:

a = ~b;

~b = ~(b | 0)

• Compiled MIPS code:

nor $t0, $t1,$zero

# if else

# if(a == b)

• C code:

if(a == b) f = g + h

else f = g - h

// f,g,h,a,b = $s0,$s1,$s2,$s3,$s4

• Compiled MIPS code:

    bne $s3, $s4, Else
    add $s0, $s1, $s2
    j Exit
Else:
    sub $s0, $s1, $s2
Exit: ...

注意這邊 Else 或是其他 Label 都是與指令同一行的

# if(a != b)

• C code:

if(a != b) f = g + h

else f = g - h

// f,g,h,a,b = $s0,$s1,$s2,$s3,$s4

• Compiled MIPS code:

    beq $s3, $s4, Else
    add $s0, $s1, $s2
    j Exit
Else:
    sub $s0, $s1, $s2
Exit: ...

# if(a <= b)

• C code:

if(a <= b) f = g + h

else f = g - h

// f,g,h,a,b = $s0,$s1,$s2,$s3,$s4

• Compiled MIPS code:

    slt $t0, $s3, $s4
    bne $t0, $zero, Then
    beq $s3, $s4, Then
    sub $s0, $s1, $s2
    j Exit
Then:
    add $s0, $s1, $s2
Exit:

a <= b 反過來就是判斷 b > a => b < a

    slt $t0, $s4, $s3    # $t0 = (b < a) 檢查是否 b < a
    bne $t0, $zero, Else # 如果 b < a，跳到 Else (即 a > b)
    add $s0, $s1, $s2    # 執行 f = g + h (當 a <= b)
    j Exit
Else:
    sub $s0, $s1, $s2    # 執行 f = g - h (當 a > b)
Exit:

# if(a > b)

• C code:

if(a > b) f = g + h

else f = g - h

// f,g,h,a,b = $s0,$s1,$s2,$s3,$s4

• Compiled MIPS code:

    slt $t0, $s4, $s3
    bne $t0, $zero, Else
    add $s0, $s1, $s2
    j Exit
Else:
    sub $s0, $s1, $s2
Exit: ...

# while

• C code:

while (save[i] == k) i+= 1;

// i in $s3, k in $s5, address of save in $s6

• Compiled MIPS code:

Loop: 
    sll $t1, $s3, 2    # i * 4（因為每個 word = 4 bytes）
    add $t1, $t1, $s6  # 計算 save[i] 的記憶體地址
    1w $t0, 0($t1)     # 讀取 save[i] 的值
    bne $t0, $s5, Exit # 如果 save[i] != k，跳出迴圈
    addi $s3, $s3, 1   # i += 1
    j Loop             # 迴圈繼續執行
Exit: ...

# function

• C code:

int leaf_example (int g, h, i, j){ 

    int f;

    f = (g + h) - (i + j);

    return f;

}

// Arguments g, ..., j in $a0, ..., $a3

// f in $s0 (hence, need to save $s0 on stack)

// Result in $v0

• Compiled MIPS code:

leaf_example:
    addi $sp, $sp, -4    # 堆疊指標減 4，為保存 $s0 創建空間
    sw $s0, 0($sp)       # 將 $s0 的原始值保存到堆疊
    add $t0, $a0, $a1    # 計算 $t0 = $a0 + $a1
    add $t1, $a2, $a3    # 計算 $t1 = $a2 + $a3
    sub $s0, $t0, $t1    # 計算 $s0 = $t0 - $t1 (這裡修改了 $s0)
    add $v0, $s0, $zero  # 將結果放入 $v0 (返回值)
    lw $s0, 0($sp)       # 恢復 $s0 的原始值
    addi $sp, $sp, 4     # 恢復堆疊指標
    jr $ra               # 返回呼叫者

# 遞迴 (recursion)

int fact (int n){

    if (n < 1) return 1;

    else return n * fact(n-1);

}

// Argument n in $a0

// Result in $v0

• Compiled MIPS code:

fact:
    addi $sp, $sp, -8
    sw $ra, 4($sp)
    sw $a0, 0($sp)
    slti $t0, $a0, 1
    beq  $t0, $zero, L1
    addi $v0, $zero, 1
    addi $sp, $sp, 8
    jr $ra
L1: addi $a0, $a0, -1
    jal fact
    lw $a0, 0($sp)
    lw $ra, 4($sp)
    addi $sp, $sp, 8
    mul &v0 ,$a0 ,$v0
    jr $ra

fact:
    slti $t0, $a0, 1
    bne  $t0, $zero, base_case

    addi $sp, $sp, -8
    sw $ra, 4($sp)
    sw $a0, 0($sp)
    addi $a0, $a0, -1
    jal fact
    lw $a0, 0($sp)
    lw $ra, 4($sp)
    addi $sp, $sp, 8
    mul $v0, $a0, $v0
    jr $ra

base_case:
    li $v0, 1
    jr $ra

# 字串 copy

void strcpy(char a[], char y[]){ 

    int i;

    i = 0;

    while ((x[i]=y[i])!='\0')

        i += 1;

}

// Addresses of x, y in $a0, $a1

// i in $s0

• Compiled MIPS code:

strcpy:
    addi $sp, $sp, -4
    sw $s0, 0($sp)
    add $s0, $zero, $zero
L1: add $t1, $s0, $a1  # 處理y[] a1
    lbu $t2, 0($t1)
    add $t3, $s0, $a0  # 處理x[] a0
    sb $t2, 0($t3)
    beq $t2 ,$zero, L2
    addi $s0, $s0, 1
    j L1
L2: lw $s0, 0($sp)
    addi $sp, $sp,4
    jr $ra

# 組合語言撰寫相關觀念

# 為什麼減少 lw/sw 是好的？

1. 記憶體存取比暫存器慢非常多
   暫存器（如 $t0~$t9, $s0~$s7）是 CPU 內部的高速記憶體，存取速度是 幾個 cycle。

而讀取記憶體（使用 lw/sw）可能會：

觸發 cache read → 如果 hit，可能還 OK

如果 miss，要去 main memory，會慢上 上百倍

👉 所以 lw/sw 會成為 performance bottleneck。

2. lw/sw 是記憶體與 CPU 的橋樑，有延遲風險
   在 MIPS 中是典型的 load/store architecture，只有 lw /sw 會與記憶體直接溝通

這會牽涉到「load-use hazard」：

當你剛 lw 一個值，下一個指令馬上用這個值時，可能會 資料尚未準備好，pipeline stall

3. 指令空間寶貴，應善用暫存器重用
   寫得好看的 assembly，應該盡量利用暫存器儲存中間結果，避免不必要的載入與存回

# 為什麼沒有 subi

因為 addi 可以加負值

addi $s3, $s3, -4

# 符號擴展 (Sign Extension)

符號擴展是將一個較小位元寬度的數值轉換為較大位元寬度時，保留其數值（包括正負號）的一種技術。方法是：將原始數值的最高位（符號位）複製到所有新增的高位中。

1. addi 指令中的立即值擴展
   在 addi $rt, $rs, imm 指令中，立即值 imm 是一個 16 位元的數值，但 MIPS 處理器內部運算是在 32 位元上進行的。

例子：

addi $t0, $t1, 5   # 立即值 5 (0000 0000 0000 0101) 擴展為 (0000 0000 0000 0000 0000 0000 0000 0101)
addi $t0, $t1, -5  # 立即值 -5 (1111 1111 1111 1011) 擴展為 (1111 1111 1111 1111 1111 1111 1111 1011)

2. lb 和 lh 指令中的載入值擴展
   當使用 lb $rt, offset($rs) 或 lh $rt, offset($rs) 指令從記憶體載入較小的資料時：

lb（載入位元組）：

• 從記憶體載入 8 位元（1 個位元組）
• 取這 8 位元的最高位（第 7 位）
• 將這個位元複製到高 24 位（位置 8-31）
• 最終在 $rt 寄存器中存儲一個 32 位元值

lh（載入半字）：

• 從記憶體載入 16 位元（2 個位元組）
• 取這 16 位元的最高位（第 15 位）
• 將這個位元複製到高 16 位（位置 16-31）
• 最終在 $rt 寄存器中存儲一個 32 位元值

3. beq 和 bne 指令中的位移量擴展
   在 beq $rs, $rt, label 或 bne $rs, $rt, label 指令中，位移（displacement）也需要符號擴展：
   擴展過程：

• 指令中的 label 被編譯為一個 16 位元的相對位移量
• 這個位移量表示從 ** 當前位置（PC+4）** 跳轉到目標位置需要移動的距離（以字為單位）
• 這個 16 位元位移量也需要符號擴展為 32 位元，然後左移 2 位（乘以 4）得到位元組位移量
• 最後加到 PC+4 上得到跳轉目標地址

4. 對比無符號擴展

無符號擴展（用於 lbu 和 lhu 等指令）則完全不同，它總是用 0 填充高位，而不是複製符號位。

因為 unsigned 所以不用特別處理是要補 0 還是補 1，所以零擴展並不是沒有擴展，而是不用特別判斷都補零。

# 載入無符號位元組，假設記憶體值為 250 (1111 1010)
lbu $t0, 0($t1)    # $t0 = 0000 0000 0000 0000 0000 0000 1111 1010 (而不是 1111...1010)
符號擴展確保了有符號數在擴展位寬後仍然保持原始的數值，這對於 MIPS 指令集的正確功能至關重要。

# 容易搞混的 rs rt rd

指令類型 | 範例 | rs | rt | rd/immediate
R-type | add rd, rs, rt | ✔️ | ✔️ | ✔️（rd）
I-type | lw rt, offset(rs) | ✔️ | ✔️ | ✔️（immediate）

# j Loop

Loop 跳到的位址要除 4

# bne $t0, $t1, 2

跳到的位址是當前的下個指令與目標記憶體位址 後減前/4

# 乘法器實作

# 基本的寫法

# 優化過的寫法

範例：

假設我們有：

• 被乘數 = 11 (二進制 1011)
• 乘數 M = 7 (二進制 0111)
• 乘積 P 初始為 0

為了更清楚地顯示，我們將 P 表示為 64 位（實際上不需要這麼多位），分為兩部分：高 32 位和低 32 位。

# 初始狀態

P = [00000000 00000000 00000000 00000000] [00000000 00000000 00000000 00000111]
    |---------- 高32位 (左側) ----------| |---------- 低32位 (右側) ----------|
M = 00000000 00000000 00000000 00000111 (7)

# 第 1 次迭代

1. 檢查 M 的最低位：M 最低位 = 1

2. 積 P 左側加上被乘數：

   被乘數 = 00000000 00000000 00000000 00001011 (11)
   P的高32位 = 00000000 00000000 00000000 00000000
   加法結果 = 00000000 00000000 00000000 00001011
   

   所以 P 變成：

   P = [00000000 00000000 00000000 00001011] [00000000 00000000 00000000 00000000]
   

3. 檢查 P 的最後一位：P 的最後一位（最右邊）= 0，等於 0

4. P 右移 1 位：

   右移前：P = [00000000 00000000 00000000 00001011] [00000000 00000000 00000000 00000111]
   右移後：P = [00000000 00000000 00000000 00000101] [10000000 00000000 00000000 00000011]
                                               ↑ 
                                       注意這個1從高位移到了低位
   

5. 計數器 i = 1

# 第 2 次迭代

1. 檢查 M 的最低位：M 最低位 = 1（我們假設 M 也在右移，現在檢查的是原來的第二位）

2. 積 P 左側加上被乘數：

   被乘數 = 00000000 00000000 00000000 00001011 (11)
   P的高32位 = 00000000 00000000 00000000 00000101
   加法結果 = 00000000 00000000 00000000 00010000
   

   所以 P 變成：

   P = [00000000 00000000 00000000 00010000] [10000000 00000000 00000000 00000001]
   

3. 檢查 P 的最後一位：P 的最後一位 = 0，等於 0

4. P 右移 1 位：

   右移前：P = [00000000 00000000 00000000 00010000] [10000000 00000000 00000000 00000001]
   右移後：P = [00000000 00000000 00000000 00001000] [01000000 00000000 00000000 00000000]
   

5. 計數器 i = 2

# 第 3 次迭代

1. 檢查 M 的最低位：M 最低位 = 1（檢查原來的第三位）

2. 積 P 左側加上被乘數：

   被乘數 = 00000000 00000000 00000000 00001011 (11)
   P的高32位 = 00000000 00000000 00000000 00001000
   加法結果 = 00000000 00000000 00000000 00010011
   

   所以 P 變成：

   P = [00000000 00000000 00000000 00010011] [01000000 00000000 00000000 00000000]
   

3. 檢查 P 的最後一位：P 的最後一位 = 0，等於 0

4. P 右移 1 位：

   右移前：P = [00000000 00000000 00000000 00010011] [01000000 00000000 00000000 00000000]
   右移後：P = [00000000 00000000 00000000 00001001] [10100000 00000000 00000000 00000000]
   

5. 計數器 i = 3

# 第 4 次迭代

1. 檢查 M 的最低位：M 最低位 = 0（檢查原來的第四位，其值為 0）

2. 跳過加法步驟

3. 檢查 P 的最後一位：P 的最後一位 = 0，等於 0

4. P 右移 1 位：

   右移前：P = [00000000 00000000 00000000 00001001] [10100000 00000000 00000000 00000000]
   右移後：P = [00000000 00000000 00000000 00000100] [11010000 00000000 00000000 00000000]
   

5. 計數器 i = 4

我們可以提前停止，因為已經處理完乘數的所有有效位（對於 7 來說只需要 3 位）。

# 最終結果

將 P 的高 32 位和低 32 位合併（截取相關部分）：

P = 00000000 00000000 00000000 00000100 11010000 00000000 00000000 00000000

將其轉換為十進制，得到 01001101 = 64 + 8 + 4 + 1 = 77，這確實是 11 * 7 的結果。

在這個算法中，"P 左側加上被乘數" 指的是將被乘數加到 P 的高 32 位部分。這樣做是因為在優化的乘法算法中，P 的高位部分存儲當前的部分乘積，而低位部分用於移位操作。每次右移操作後，結果的一部分會從高位移入低位，最終形成完整的乘積。
3. 兩種乘法實現的主要差異
兩種乘法實現的主要差異
基本長乘法（第一張圖）：

• 接模擬手工長乘法算法
• 每次檢查乘數的一位，若為 1 則加上被乘數
• 被乘數左移，乘數右移
• 簡單直觀，但效率較低

優化後的乘法（第二張圖）：

• 增加了檢查積最後一位的步驟
• 根據積的最後一位決定是否執行特殊處理（步驟 2a）
• 積右移而不是乘數右移
• 更複雜但效率更高

# 指令差異對比

# MIPS 實現上的主要差異

1. 寄存器使用：

• 基本長乘法：需要分別保存被乘數、乘數和乘積
• 優化後乘法：使用 P 和 M 兩個寄存器同時處理乘積和乘數

2. 指令序列：

• 基本長乘法：

  andi $t3, $t1, 1    # 檢查乘數最低位
  beq $t3, $zero, shift  # 如果是0，跳過加法
  add $v0, $v0, $t0   # 加上被乘數
  sll $t0, $t0, 1     # 被乘數左移
  srl $t1, $t1, 1     # 乘數右移
  

• 優化後乘法：

  andi $t3, $t1, 1    # 檢查乘數最低位
  beq $t3, $zero, check_product  # 如果是0，跳過加法
  addu $t4, $v0, $t0  # 積左側加上被乘數
  
  check_product:
  andi $t5, $v0, 1    # 檢查積最後一位
  beq $t5, $zero, shift  # 如果是0，直接移位
  # 步驟2a: 相加值覆蓋積前32位元的實現
  
  shift:
  srl $v0, $v0, 1     # 積右移
  

這張圖解釋了 MIPS 處理器中乘法運算的積暫存器架構和相關指令。

在 MIPS 乘法實現中，為了處理 32 位元整數相乘產生的 64 位元結果，系統使用了兩個 32 位元暫存器來存儲完整的乘積：

# 除法器

# 架構組件說明

• 32 位元 ALU ：執行減法和加法運算
• 64 位元餘 Remainder ：儲存中間計算結果，前 32 位元存放部分餘數，後 32 位元存放被除數 / 商
• 32 位元 divisor ：儲存除數

# 演算法步驟詳解

# 步驟 0：初始配置

範例:

13 / 3 = 4 ... 1

除數 : 3
被除數 : 13

• Divisor : 0011
• Remaindor : 0000 1101

# 步驟 1：餘數左移 1 位元

• Remaindor : [0000 1101] -> [0001 1010]
• 0001 - 0011 = -2 < 0 : 商位元是 0

# 步驟 2：餘數左移 1 位元

• Remaindor : [0001 1010] -> [0011 0100]
• 0011 - 0011 = 0 = 0 : 商位元是 1

# 步驟 3：更新商位元

• [0011 0100] -> [0000 0101]

# 步驟 4：餘數左移 1 位元

• Remaindor : [0000 0101] -> [0000 1010]
• 0000 - 0011 = -3 < 0 : 商位元是 0

# 步驟 5：餘數左移 1 位元

• Remaindor : [0000 1010] -> [0001 0100]
• 0001 - 0011 = -2 < 0 : 商位元是 0

# 結果

• 總共左移 4 位元
• 0100 => 代表商為 4
• 0001 => 代表餘數為 1

# 關鍵觀念

1. 左移操作：每次左移 1 位元相當於將被除數的下一位元帶入計算

2. 減法判斷：用部分餘數減去除數，判斷是否夠減

3. 商的形成：夠減時商的對應位元為 1，不夠減時為 0

4. 非回復式：不夠減時不需要恢復，直接進行下一步

# 積暫存器結構

• HI 暫存器：用於存儲乘積的最高有效 32 位（most-significant 32 bits）
• LO 暫存器：用於存儲乘積的最低有效 32 位（least-significant 32-bits）

這種設計允許 MIPS 處理器處理兩個 32 位數相乘產生的完整 64 位結果，避免了溢位問題。

# 相關指令

圖中列出了幾個與乘法相關的指令：

1. mult rs, rt / multu rs, rt

   • 這些指令執行有符號乘法 (mult) 或無符號乘法 (multu)
   • 將寄存器 rs 和 rt 中的值相乘
   • 64 位元乘積自動分配到 HI/LO 暫存器中

2. mfhi rd / mflo rd

   • mfhi (Move From HI)：將 HI 暫存器的值移動到目標寄存器 rd 中
   • mflo (Move From LO)：將 LO 暫存器的值移動到目標寄存器 rd 中
   • 這些指令用於讀取乘法結果
   • 可以通過檢查 HI 的值來判斷乘積是否超過 32 位（如果 HI 不為 0，則表示溢位）

3. mul rd, rs, rt

   • 這是一個偽指令，執行乘法並只保留結果的低 32 位
   • 將結果直接存入 rd 寄存器，忽略高 32 位
   • 相當於執行 mult 後再執行 mflo

# 使用方式

這種架構的使用流程通常是：

1. 執行 mult/multu 指令進行乘法運算
2. 系統自動將 64 位結果分別存入 HI 和 LO 暫存器
3. 程式可以根據需要使用 mfhi 和 mflo 指令來讀取完整結果
4. 如果只需要低 32 位結果，可以直接使用 mul 指令或僅讀取 LO 暫存器

這種設計使 MIPS 處理器能夠有效處理 32 位整數乘法，同時保留完整的 64 位結果，為程式員提供了處理大數乘法的靈活性。

#