# 計算機組織與結構 L1 指令 : 計算機的語言

## 基本概念

- **計算機的 Command 等於 :**
- **Statements :** in high level language
- **Instructions :** in low level language

- **Instruction & Instruction Set & Instruction Set Architecture:**
- **Instruction :** CPU 可執行的最基本運算
- **Intruction Set :** 計算機可執行的指令集合，相同 Instruction Set 建構的 CPUs 是 compatible
- **Instruction Set Architecture :** 又叫 ISA。ISA = 基本硬體架構 + 指令集

- **RISC & CISC :**

| RISC (Reduced Instruction Set Computer) | CISC(Complicated Instruction Set Computer) |
| -------- | -------- |
| 以 CPU 執行效率為主要考量 | 以減輕程式設計者的負擔為主要考量 |
| 提供簡單的基本指令以求較快</br>的執行速度 | 提供較佳程式設計環境，除了基</br>本指令，還有較強的複雜指令 |
| 指令長短相同 (擷取指令快) | 指令長短不同 |
| 只有少數幾種 addressing mode | 支援多種 addressing mode |
| 只有少數幾種 instruction format | 支援多種 instruction format |
| **算術指令的運算元只能來自暫存器** | **算術指令的運算元能來自記憶體** |

## 內儲式程式概念

- **Stored-program (Von Neuman Machine) 建構原則:**

- 指令以數字的形式表示
- 要被執行的程式先放置在記憶體中，像數字一樣被存取
</br>
> buttleneck :
> an instruction fetch and a data operation cannot occur at the same time for they share the same bus

## 指令集架構

- **ISA 分成 :**
- **Instruction Set**
- **Hardware Information**
- **Memory**
- **Register**
- **Instruction Format :**
- R-Type
- I-Type
- J-Type

- **Addressing Mode :**
- Immediate Addressing
- Register Addressing
- Base or Displacement Addressing
- PC-relative Addressing
- Pseudodirect Addressing

- **Computer 的五個 components :**
- **Control Unit :** 解碼指令，產生控制訊號線
- **Datapath :** 真正執行指令，處理資料的電路
- **Memory**
- **Input Device**
- **Output Device**
</br>
> **Processor(CPU) = Control Unit + Datapath**

- **Byte-Order or Endianness**
- **Big Endian :** MSB 在最低記憶體位置
- **Little Endian :** LSB 在最低記憶體位置

- **Register & Memory :**
- **Register :**
- Register 在 Processor 裡的 Datapath 中
- 又分為
- **一般目的暫存器 :** 32 個 32 bits


- **特殊目地暫存器 :** 如 Program Counter (PC) 32 bits、Hi (存乘積高位元或除法餘數) 32 bits、Lo (存乘積低位元或除法商數) 32 bits

- **Spilling Register :** Compiler 將不常用的變數存在 memory 的程序

- **Memory :**
- byte addressing 或 word addressing
- 使用 $n$ bits 表示記憶體位址，代表記憶體最大容量為 $2^n$ bytes
- **Alignment :** 所有 word 都要按照 byte address 為 4 的倍數放

- **Register & Memory :**
- 一個程式在記憶體的 address space


- Memory 的一般目的暫存器

## 不同的指令集

- 4 種不同型態的 **Instruction Set**

| Accumulator | Memory - Memory | Stack | Load - Store |
| -------- | -------- | -------- | -------|
| 所有運算都在一個</br>暫存器和記憶體之間 | 運算指令有三個運</br>算元都在記憶體裡 | 所有運算都在</br>stack 頂端 | 所有運算都在</br>暫存器中 |
| 1 open | 3 open | 0 open | 3 open |
| CISC | CISC | CISC | RISC

圖示
- **Accumulator**

        load  AddressB
        add   AddressC
        store AddressA


- **Memory - Memory**

        add AddressA, AddressB, AddressC


- **Stack**

        push AddressB
        push AddressC
        add
        pop  AddressA


- **Load - Store**

        load  $1, AddressB
        load  $2, AddressC
        add   $3, $1, $2
        store $3, AddressA


## 程式之轉譯與執行


經過
- **Compiler**
- **Assembler** 包含
- **Header :** 描述目的暫存器的內容，包含大小及位置資訊
- **Text Segment**
- **Static Data Segment**
- **Relocation Information :** 當程式載入記憶體時，指令和資料的相對位址
- **Symbol Table :** 儲存參考資料等等未定義標籤
- **Debug Information :** 連結原始程式碼

- **Linker :** 連結多個目的模組及資料庫解決位址的參考問題
- **步驟一 :** 將程式碼和資料模組放置在記憶體中
- **步驟二 :** 決定資料與 instruction label 的位址
- **步驟三 :** 決定內部與外部指令參考

- **Loader :** 將 machine code 放置在適當的記憶體位址以供 processor (CPU) 處理執行
- **步驟一 :** 讀 executable file 的 header 決定 text 和 data segment 的大小
- **步驟二 :** 產生足夠的記憶體空間
- **步驟三 :** copy executable file 的 instruction 和 data 至記憶體
- **步驟四 :** copy parameters 到 stack 中
- **步驟五 :** initialize registers，並將 \$sp 指向 stack 的第一個可用空間
- **步驟六 :** 將 PC 指向 start-up routine，啟動 start-up routine，呼叫要被執行的程式，結束程式後，再用 exit 這個 system call 終結程式

> 有些系統以 linking loader (linker + loader) 執行最後兩個步驟

> Java
> 
>
> 因為 JVM 太慢，所以常常利用 JIT 加速
> - JVM 是直譯，翻譯出來的 bytecode 跑起來比 machine code 慢很多
> - JIT 把常見的 bytecode 轉乘 machine code 存在 cache 中

## 一般指令類別

**MIPS 指令類別**有 :
- **Data Movement** (load and store)
- **Arithmetic** (add, sub, mul ...)
- **Logical** (sra, sll, srl)
- **Flow Control** (branch and jump)
- **Procedure Call** (jal and return)


## 算術指令

- **Addition**
- **add rs, rt, rd**
- add \$1, \$2, \$3

- **Subtraction**
- **sub rs, rt, rd**
- sub \$1, \$2, \$3

## 資料轉移指令

採用 base-offset 表示方式

- **Load**
- **lw** (load word)
- **lb** (load byte) : 從記憶體載入 1 byte，存到 register 的最右邊的 byte，左邊看目前最左位元是 1 或 0，填 1 或 0
- **lbu** (load byte unsign) : 從記憶體載入 1 byte，存到 register 的最右邊的 byte，左邊全填 0
- **lw rt, immediate*4(rs)**
- lw \$t0, 32(\$s0) → $A[8]$
- **Store**
- **sw** (store word)
- **sb** (store byte)
- ~~sbu (store byte unsign)~~ : 因為沒有擴充性問題存在
- **sw rt, immediate*4(rs)**
- sw \$t0, 48(\$s0) → $A[12]$

## 流程控制指令

- **Branch**
- occurs when **if statement** or **loops**
- 可跳 $2^{16} * 4B$ ($2^{16} word$)
- 利用 **PC-relative addressing (PC 相對定址法)**
- **beq rs, rt, address*4**

- 用 MIPS 現有 Instruction 實現 Pseudo Instruction

| Pseudo Instruction | MIPS Instruction |
| -------- | -------- |
| blt \$s1, \$s2, L | slt \$t0, \$s1, \$s2 </br> bne \$zero, \$t0, L |
| bgt \$s1, \$s2, L | slt \$t0, \$s2, \$s1 </br> bne \$zero, \$t0, L |
| ble \$s1, \$s2, L | slt \$t0, \$s2, \$s1 </br> beq \$zero, \$t0, L |
| bge \$s1, \$s2, L | slt \$t0, \$s1, \$s2 </br> beq \$zero, \$t0, L |

</br>

> **Basic Block :**
> - 編譯程式要最佳化的最基本單位 (先 Basic Block 內最佳化，再 Basic Block 間最佳化)
> - 一連串
> **沒有分支**(如果有只能出現在區塊最後一個指令處)，
> **沒有分支目的**(如果有只能出現在區塊第一個指令處)
> 的指令

- **Jump**
- occurs when **procedure calls and returns** or **case/switch statement**
- 可跳 **256MB**
- 最左邊 4 bits : MIPS 將 4GB 記憶體切為 16 個大小相等的 256MB 的區塊，Jump只能在同一區塊，所以最左邊 4 bits 是相同的
- 最右邊 2 bits : 因為要符合 Alignment，所以最右邊兩個 bits 都是 0

## 邏輯運算


- **Shift**
- **sll** (shift left logically)
- **srl** (shift right logically)
- **sra** (shift right arithematically)

- **And**
- 一種 **mask**，將感興趣位元保留，其餘清為零

- **Or**
- 一種 **set**，將感興趣位元設為1，其餘保持不變

- **Not**
- MIPS 用 **nor** 代替 **not** 運算
- A NOR 0 → NOT A

## 常數

- **Immediate Instruction**
- **lui** (load upper immediate) : 將 16 位元的常數載入到暫存器左半部 16 位元，再將右半部 16 位元清為 0，配合 ori 可將 32 位元常數存入暫存器

## MIPS 指令格式

**Instruction Format : 指令不同欄位的排列方式**

| 參與運算的元素 | 組合語言指令 | 機器語言格式指令 |
| -------- | -------- | -------- |
| 3 registers | add, sub, and, srl, sll, ... | R-Type |
| 2 registers & 1 constant/address | lw, sw, bne, addi, ... | I-Type |
| 26 bit address | j, jal, ... | J-Type |





- 常見 OP Code 和 Funct Code
| Operation | OPCode |
| -------- | -------- |
| lw | 35 |
| sw | 43 |
| bne | 5 |
| beq | 4 |
| j | 2 |

| Operation | funct code |
| -------- | -------- |
| add | 32 |
| sll | 0 |

## 程序呼叫


- **程序呼叫常用暫存器**
- **\$a0 - \$a3 :** arguments
- **\$v0 - \$v1 :** return value
- **\$ra :** return address
- 當讀到 jal (jump and link) 時，會先跳到 callee 程序起始位址，同時將 caller 下一個指令的位址存在 \$ra
- 當 callee 程序執行結束，會有一行 jr 供程序返回 caller 時使用

- **常考 MIPS Assembly**
- Factorial

C Code

        int fact (int n) {
            if (n < 1)
                return 1;
            else
                return n * fact(n - 1);
        }

MIPS Assembly Code

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

- Sum

C Code

        int sum(int n) {
            if (n == 0)
                return 0;
            else
                return n + sum(n - 1);
        }

MIPS Assembly Code

        sum : addi $sp, $sp, 8
              sw $ra, 4($sp)
              sw $a0, 0($sp)
              bne $a0, $zero, ELSE
              addi $v0, $zero, 0
              addi $sp, $sp, 8
              jr $ra
        ELSE : addi $a0, $a0, -1
               jal sum
               lw $a0, 0($sp)
               lw $a0, 4($sp)
               addi $sp, $sp, 8
               add $v0, $a0, $v0
               jr $ra

## MIPS 定址模式

**Addressing Mode : 指令取得運算元或計算目的位址的方法**

- **Addressing Mode 包含:**
- **Immediate Addressing :** 運算元包含 16 位元的常數


- **Register Addressing :** 運算元在暫存器中


- **Base or Displacement Addressing :** 運算元在記憶體中


- **PC-relative Addressing :** 目的位址是 PC 加上指令中的常數


- **Pseudodirect Addressing :** 跳躍目的位址為址中的 26 位元與 PC 的結合


- **\$jr** 非 Pseudodirect Addressing，而是 **Register Addressing** (因為 \$ra 是一般目的暫存器)

## 指令集設計原則

- **五大指令集設計原則**
- **Simplicity favors regularity**
- Instruction size same
- Arithematic instruction always needs 3 registers
- Different instruction format has same register fields
- **Smaller is faster**
- Smaller registers, faster speed
- **Make the common case fast**
- PC-relative addressing is used in branches
- Immediate addressing is used to get the constant
- **Good design demands good compromises**
- provides 3 type of instruction format instead of 1
→ compromises between larger memory address and keep all the instruction size the same