###### tags: `計算機組織_戴碧如`
## Chapter 2 - Instructions: Language of the Computer

[TOC]

#### Instruction Set
- 比較通用的是 Simplified implementation
- 設計一套最簡單的指令，需要複雜的動作時，用這些簡單的指令組合而成

#### Arithmetic Operations
- Two sources and one destination
> add a, b, c => a = b + c (a gets b + c)
:::success
Design Principle 1: Simplicity favors regularity
:::

#### Register Operands
- MIPS has a 32 x 32-bit register file
- 32-bit data called a "word"
- Assembler names
- $t0, $t1, ...,$t9 for temporary values (專門拿來暫存的)
- $s0, Ss1, ...,$s7 for saved variables (專門拿來存要長期持有的變數)
:::success
Design Principle 2: Smaller is faster
:::

#### Memory Operands
- To apply arithmetic operations
- **Load** values from memory into registers
- **Stor** result from register to memory
- Memory is **bytes addressed**
- Words are aligned in memory (每個 word 的第一個 byte 一定是 4 的倍數)
- MIPS is Big Endian
- Most-significant byte at least address of a word

#### Example1
- C code:

g = h + A[8];

- MIPS code:

lw $t0, 32($s3)
add $s1, $s2, $t0

#### Example2
- C code:

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

- MIPS code:

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

#### immediate Operands
- Constant data specified in an instruction

addi $s3, $s3, 4

- No subtract immediate instruction
可以加上 負數
:::success
Design Principle 3: Make the common case fast
:::

#### The Constant Zero
- MIPS register 0 ($zero) is the constant 0
- cannot be ovwewritten
- 用於 copy， a = b

`add $t2, $s1, $zero` => `$t2` = `$s1`

#### MIPS Instruction Encoding
有兩種表示法 R-Type, I-Type
- **R-format**：通常用於算術和邏輯操作
- op: operation code (opcode)
- rs: first source register number
- rt: second source register number
- rd: destination register number
- shamt: shift amount (00000 for now)
- funct: function code (extends opcode)

- **I-format**：通常用於加載和存儲數據，以及分支和跳轉操作
- Immediate arithmetic and load/store instructions
- rt: destination or source register number
- Constant: -2^15 to 2^15-1 (常數可以表示 16-bit 的有號數)
- Address: offset added to base in rs (要跳轉的位址會是放入與 rs 位址之間差了多少的 instruction 數量 => 指令位移量)

:::success
Design Principle 4: Good design demands good compromises
:::

#### Stored Program Computer
- Instruction cycle 指令的循環週期
- Fetch（抓取到 CPU ）, Decode（解析）, Execute（執行）
- Memory 雖然是以 8-bit (1 byte) 為單位，但是每個指令 (word) 是以 32-bit (4 byte) 為單位，故每個指令會需要用到 4 byte 的記憶體空間儲存。
- Program Counter (PC) => 程式指令計數器，用來記錄下一個要執行的指令位址。每當開始執行該指令時，PC 會直接更新至 **下一個** 指令位址。
- 以此範例來說，lw 會從 1200($t1) 的這個位址當中，取得 value。
- $t1 儲存的是位址 (address) = 10008000 (hex)
- $t0 儲存的是值 (value) = 0000A111 (hex)

#### Shift Operation

sll $t2, $s0, 4

t2 是要寫入的 Register
s0 是要位移的目標
4 是要位移的量

#### AND Operation
跟 0 作 and 都會變成 0
跟 1 作 and 會是 自己

and $t0, $t1, $t2

#### OR Operation
跟 0 作 or 會是 自己
跟 1 作 or 都會變成 1

and $t0, $t1, $t2

#### NOT Operation
- 用 NOR 實現 NOT

nor $t0, $t1, $zero

> Register 0: always read as zero

#### Conditional Operation
- branch if equal

beq rs, rt, L1

- branch if not equal

bne rs, rt, L1

- jump

j L1

#### Loop Statements

#### Compiling Loop Statements

#### Basic Blocks
- 沒有跳來跳去的區塊，稱為 Basic Blocks
- 就可以對他做最佳化

#### More Conditional Operations

slt rd, rs, rt

=> if (rs < rt) then rd = 1; else rd = 0

ex.

slt $t0, $s1, $s2
bne $t0, $zero, L

#### Signed vs Unsigned

#### Procedure Calling
- Steps required
1. Place parameters in registers 把需要引入的參數先放到暫存器
2. Transfer control to procedure 跳轉至 Procedure
3. Acquire storage for procedure 配置空間
4. Perform procedure's opreation 執行程式
5. Place result in register for caller 回傳值至 caller
6. Return to place of call 跳轉回去主要的程式執行的地方

#### Register Usage
- $a0 – $a3: arguments (reg’s 4 – 7)
- $v0, $v1: result values (reg’s 2 and 3)
- $t0 – $t9: temporaries
- Can be overwritten by callee 因為是 暫時的 覆蓋掉沒關係
- $s0 – $s7: saved
- Must be saved/restored by callee
- $gp: global pointer for static data (reg 28)
- $sp: stack pointer (reg 29)
- $fp: frame pointer (reg 30)
- $ra: return address (reg 31) 紀錄 return 的位址，才知道 return 時要跳回去哪裡

#### Procedure Call Instructions
- Procedure Call: jump and link (jal)

jal ProcedureLabel

- Procedure Return: jump register

jr $ra

#### Using More Registers
- Stack
- 位址會從**高位址至低位址**
- 兩個指標：`$fp`（頭）、`$sp`（尾）
- 通常都會直接使用 `$sp` 做操作

#### Memory Layout
- 一般來說會把記憶體空間切成以下的圖示

#### Leaf Procedure

#### Non-Leaf Procedures

#### Character Data
- 字元資料
- 一個 Byte (16-bit) 儲存一個字元
- ASCII: 128 個字元
- Latin-1: 256 個字元
- Unicode: 32-bit 儲存一個字元

#### Byte/Haldword Operations

#### String Copy Example

:::info
重點：
因為是對字串做複製，所以每一個字元在複製時，會使用到`lbu $t2, 0($t1)`把字元 load 進來，再使用`sb $t2 0($t3)`把複製的字元丟給目的地。
:::

#### 32-bit Constants
- 大部分情況 16-bit 就能夠表示常數了
- 但如果還想要表示更大的常數，可以使用`lui rt, constant`這個語法
- `lui` => load upper immediate
- 因為一個 word 會使用 32-bit 儲存，所以使用`lui`會把這個constan 的 16-bit 丟到 32-bit 的前半部。
- 再使用`ori $s0, $s0, constant`把原本後半部分的 16-bit 取代成 constant，就能夠用 32-bit 表示常數了。

#### Branch Addressing
- 在使用 Branch 指令時，會需要定義 Label 的位址，但是那個位址不會直接儲存在機器語言表示的指令裡，而通常要跳去的 Label 位址不會離現在的 PC (Programing Counter) 太遠，所以會直接紀錄目前 PC 位址和 Label 之間差了多少個 word。
- Target Address = PC + offset x 4
:::danger
PC 此時已經 +4 了，因為在執行此段 branch 指令時，PC 會先 +4，準備下一個指令。
:::

#### Jump Addressing
- 因為一段指令（word）只能用 32-bit 表示，所以包含 op code 只剩下 26-bit 可以表示要 Jump 的位址
- 因為一個指令要 4bytes 所以記憶體在儲存時，位址一定會 4 的倍數，所以最後 32-bit 的位址後兩位元一定是0。（只需要花 30 bit 表示）
- 最高位元 4-bit 用 PC的前 4 位元，因為跳的位址也不會太遠，所以直接複製 PC 的前 4 位元。（只需要使用 26-bit 表示，也是最大能夠表示的範圍）


#### Target Example

#### Assembler Pseudoinstructions

#### 指令對應的 Type

| R-Type | I-Type | J-Typr |
|:------------------- |:------------------ |:-------- |
| `add rd, rs, rt` | `addi rt, rs, imm` | - |
| `sll rd, rt, shamt` | `slti rt, rs, imm` | - |
| - | `lw rt, imm(rs)` | - |
| - | `sw rt, imm(rs)` | - |
| `jr rs` | `beq rs, rt, imm` | `j addr` |

- R-Type

| op | rs | rt | rd | shamt | func |
|:---:|:---:|:---:|:---:|:-----:|:----:|
| 6 | 5 | 5 | 5 | 6 | 6 |

- I-Typr

| op | rs | rt | constant / address |
|:---:|:---:|:---:|:------------------:|
| 6 | 5 | 5 | 16 |

- J-Type

| op | address |
|:---:|:-------:|
| 6 | 26 |

#### 組合語言 指令統整
:::spoiler 統整內容
`add a, b, c` => a = b + c
- Register File
- MIPS 有 32 x 32-bit 的 register file
- 1 個 word 等於 32 bits
- $t0 ~ $t9 是專屬給 temporary values
- $s0 ~ $s7 是專屬給 saved variables

- Memory
- **Load** => from memory into register
- **Store** => from register to memory
- 以 byte 為單位，等於是 8 bits
- 存入 word 的位址，位址一定是 4 的倍數，因為一個 word 是 32 bits

`lw $t0, 32($s3)` => 從 s3 的位址往後 32 個 byte 的值，存入暫存變數 $t0。(如果 $s3 代表陣列 A[0] => 則 32($s3) 代表 A[8])

`sw $t0, 48($s3)` => $t0 的 data 存入 A[12] ($s3 代表 A[0])
`slt rd, rs, rt` => if (rs < rt) rd = 1; else rd = 0;
slt => set on less than
:::