<style>
.red {
color: red;
font-weight: bold;
}
.blue {
color: blue;
font-weight: bold;
}
.green {
color: green;
font-weight: bold;
}
.gb {
background-color: lightgreen;
}
</style>
# Instructions: Language of the Computer
## Introduction
- To command a computer’s hardware
- ***Instructions***: the words of a computer’s language
- ***Instruction set***: vocabulary of a computer’s language
- Computer languages are quite similar
- All computers are constructed from hardware technologies based on similar underlying principles
- There are a few basic operations that all computers must provide
- A common goal for computer designers
- To find a language that makes it **easy to build the hardware and the compiler**
- To **maximize performance** and **minimize cost** and energy
- **MIPS** (**M**icroprocessor without **I**nterlocked **P**ipeline **S**tages) instruction set
- **Stored-program** concept
- **Instructions** and **data** of many types can be **stored in memory as numbers**
## Operations of the Computer Hardware
### MIPS Arithmetic Instruction
- **add/sub** *a, b, c*
- To add/subtract variables *b* and *c* and to put their sum/difference in *a* (`a=b+c`)
- Example: `a = b + c + d + e`
```
add a,b,c
add a,a,d
add a,a,e
```
- Example: `f = (g + h) – (i + j)`
```
add t0, g, h
add t1, i, j
sub f, t0, t1
```
- **Compiler creates temporary variable** `t0` and `t1` to store immediate results
:::info
**Design principle 1**: ***Simplicity favors regularity*** 簡單有助於一致性
- Requiring every MIPS **arithmetic instruction** to **have exactly <font class="red">three</font> operands**
$\Rightarrow$ **keep the hardware simple**
- Hardware for a variable number of operands is more complicated
:::
:::success
**Notes for MIPS language**
- Each line can contain at most **one** instruction
- Sharp symbol (`#`) is used for **comments**
- Comments always terminate at the end of a line
:::
## Operands of the Computer Hardware
### Variables vs. Operands
- Unlike programs in high-level languages, the operands of arithmetic instructions are restricted
- Operands must be from a limited number of special locations called registers
- ***Word***: the natural unit of access in a computer, usually a group of **32 bits**
- MIPS has 32 32-bit registers (1 word = 32 bits)
:::info
**Design principle 2: *Smaller is faster*** 小就是快
- Larger number of registers may increase the clock cycle time and the number of bits required in the instruction format
- To balance between the designer’s desire and the limitation of hardware
:::
- 在 MIPS assembly 中，`$` 開頭表示暫存器
- E.g., 暫存器 *v0*，在 MIPS 的 assembly code 中是 `$v0`
- Example: `f = (g + h) - (i + j)`
- (f, g, h, i, j) are in (\$s0, \$s1, \$s2, \$s3, \$s4)
- 方便書寫用，正式場合不能這樣寫。
```
add $t0, $s1, $s2
add $t1, $s3, $s4
sub $s0, $t0, $t1
```
### Memory Operands
- Registers only keep small amount of data, but memory contains millions of data elements
- Memory is a large **single-dimensional array**
- ***Address*** acts as the index to the memory, starting at 0
- Byte addressing
- 每一個 byte 都有自己的 address
- **Data transfer instructions**
- Arithmetic operations occur only on registers in MIPS instructions
- A command that moves data between memory and registers
- <font class="red">`lw $des, offset($base)`</font>
- ***Load word***, memory $\rightarrow$ register
- <font class="red">`sw $source, offset($base)`</font>
- ***Store word***, register $\rightarrow$ memory
- ***Memory address*** = contents of the ==***base register*** + ***offset***==
- *Base register*: the second register of the instruction
- *Offset*: the constant portion of the instruction
- 這樣設計是為了方便陣列存取
- Base: 陣列的起始位址
- Offset: 作用等同 index
- Most data items use words not bytes
- word address 與 byte address
- 1 word = 4 bytes = 32 bits
- The address of a word matches the address of one of the 4 bytes within the word
- Addresses of sequential words differ by 4
- ***Alignment restriction***
- A requirement that data be aligned in memory on natural boundaries
- Words must **start at address** that are **multiples of 4 in MIPS**
- Many architectures, including MIPS, have to satisfied the alignment restriction
- 優點: word address 最右兩位 bit 都會是 0，在必要時可以省略以節省空間
- ***Big endian vs. Little endian***
- [Big-Endian 與 Little-Endian 的差異與判斷程式碼](https://blog.gtwang.org/programming/difference-between-big-endian-and-little-endian-implementation-in-c/)
- Example: `A[12] = h + A[8]`
- `h` is in `$s2`, base address of `A` is in `$s3`
- ```
lw $t0, 32 ($s3) # 以 word 為單位, 8 (words) * 4 = 32 (bytes)
add $t0, $s2, $t0
sw $t0, 48 ($s3)
```
- **Spilling** registers
- Registers take less time to access and have higher throughput than memory
- To put **less commonly** used variables **into memory**
- To keep the **most frequently** used variables **in registers**
- [暫存器組態 - 維基百科](https://zh.wikipedia.org/zh-tw/暫存器配置)
### Constant or immediate operands
- Constant operand occurs frequently.
- Using only **`lw`** and arithmetic instructions
- Constants are placed in memory and loaded by program when necessary
- Example
- Assume that `$s1 + AddrConstant4` is the memory address of the constant 4
```
lw $t0, AddrConstant4($s1) # $t0 = constant 4
add $s3, $s3, $t0 # $s3 = $s3 + $t0 ($t0 == 4)
```
- ***Design principle: ==Make the common case fast==***
- ***Add immediate*** instruction <font class="red">`addi`</font>
- The **second** operand of `addi` ==must== be a **constant**
```
addi $s3, $s3, 4 #$s3 = $s3 + 4
```
- MIPS 沒有 `subi`，要用減法可以在 second operand 使用**負數**
- MIPS dedicates a register <font class="red">`$zero`</font> to be hard-wired to the value zero
```
add $s2,$s1,$zero # $s2=$s1, move operation
```
## Representing Instructions in the Computer
### Instruction Format
- The layout of the instruction
- A form of representation of an instruction composed of fields of binary numbers
- MIPS instruction takes **exactly 32 bits**
- The same size as a data word
- To keep with **design principle 1**: ==simplicity favors regularity== (簡單有利於規律性)
### Machine Language
- The **numeric version** of instructions
- **Binary representation** used for communication **within a computer system**
- **Machine Code**: a sequence of machine instructions
- Register names $\rightarrow$ numbers
- `$t0`~`$t7` $\rightarrow$ 8~15
- `$s0`~`$s7` $\rightarrow$ 16~23
### MIPS Fields
- **指令在設計時就會指定是什麼 type**，需要按照對應格式使用（不會根據情況改變 type）
- ***R-type (R-format)*** (<font class='red'>for register</font>)
- ==要記下來== <!-- 哭R == -->
- 
- op (***opcode***): basic operation of the instruction
- rs (**source register**): the first register **source** operand
- rt (**target register**): the second register **source** operand
- rd (**destination register**): the register **destination** operand, to get the results of the operation
- shamt (***shift amount***) (==沒有用到時填 0==)
- funct (***function code***): to **select the specific variant** of the operation in the op field
- op and funct fields in combination determines a specific instruction
- ==R-type 的 `op` 全是 0==，由 `funct` 來辨別是哪個指令。
- Example: `add $t0(8), $s1(17), $s2(18)`
- 
- If an instruction needs longer fields?
- The 5-bit field is too small to specify a constant ($5^2 = 32$)
:::info
**Design principle 3: *Good design demands good compromises*** (好的設計需要好的妥協。)
- To keep all instructions the same length, thereby requiring more than one instruction format
:::
- ***I-type (I-format)*** (<font class='red'>for immediate</font>)
- 
- op (***opcode***): basic operation of the instruction
- rs: the **base register** for `lw/sw`, the first register operand for `addi`
- rt: the **destination register** for `lw/addi`, the **source register** for `sw`
- constant or address: constant for `addi`, address for `lw/sw`
- Region of `lw` instruction: rs $\pm$ $2^{15}$ or 32768 bytes ($2^{13}$ or 8192 words)
- Constant for `addi` instruction: $\pm$ $2^{15}$ or 32768
- Example: `lw $t0, 32($s3)`
- **Keeping the formats similar**
- Formats are distinguished by the values in the **opcode**.
- The first three fields of the R-type and I-type have the same sizes and names.
- The length of the $4^\text{th}$ field in I-type is equal to the sum of the lengths of the last three fields of R-type.
- Example: `A[300] = h + A[300]`
- `h` is in `$s2`, base address of `A` is in `$t1`
- ```
lw $t0, 1200($t1)
add $t0, $s2, $t0
sw $t0, 1200($t1)
```
### Store-program concept
- Key principles
- Instructions are **represented as numbers**
- Programs are stored in memory to be read or written, just **like data**
- ***Fetch*** and ***execute*** cycle
- Instructions are fetched and put into a **special register**
- Bits in the register control the subsequent actions
- Fetch the next instruction and continue
（只是說明 memory 可以分不同區塊，不用背）
## Logical Operations
### Shifts
- **Shift left logical** (<font class="red">sll</font>), **shift right logical** (<font class="red">srl</font>)
- To move all the bits in a word to the left or right
- To fill the emptied bits with 0s
- Example
- Register `$s0` contains $0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 1001_2 = 9_{10}$
- $\Rightarrow$ To shift left by 4: $0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 1001_2\ 0000 = 144_{10}$
- R-format instructions
- Using the ***shamt*** field to specify the number of bits been shifted
- The **rs** field is unused and thus is set to 0
- **Example**:
```
sll $t2, $s0, 4 # reg $t2 = reg $s0 << 4 bits
```
- Shifting left by $i$ bits gives the same result as multiplying by $2^i$
- Above shift left by 4 example: $144 = 9 \times 16 = 9 \times 2^4$
### Bit-by-bit operations
- ***AND*** (`and`), ***AND immediate*** (`andi`)
- ***Mask*** instruction
```
and $t0, $t1, $t2 # reg $t0 = reg $t1 & reg $t2
andi $t0, $t1, 100 # reg $t0 = reg $t1 & constant 100
```
- ***OR*** (`or`), ***OR immediate*** (`ori`)
```
or $t0, $t1, $t2 # reg $t0 = reg $t1 | reg $t2
ori $t0, $t1, 100 # reg $t0 = reg $t1 | constant 100
```
- ***NOT OR*** (`nor`), ***NOT OR immediate*** (`nori`)
- To keep with the **three-operand format**
- If one operand is **zero**, then it is equivalent to NOT
```
nor $t0, $t1, $t2 # reg $t0 = ~(reg $t1 | reg $t2)
nori $t0, $t1, 100 # reg $t0 = ~(reg $t1 | constant 100)
```
## Instructions for Making Decisions
### Decision-making instructions
- Based on the input data and the values created during computation, different instructions execute
- Important both for
- Choosing between two alternatives: **if statements**
- Iterating a computation: **loops**
- **Conditional branches**
- An instruction that
- To requires the comparison of two value
- To allow for a subsequent transfer of control **to a new address in the program** based on the outcome of the comparison
- Branch if equal: `beq register1, register2, L1`
- Branch if not equal: `bne register1, register2, L1`
- **Unconditional branch**
- The processor always follows the **branch**
- Jump: `j L1`
（提到 branch 指有條件 + 無條件）
### if-then-else
- Example: `if (i == j) f = g + h; else f = g - h;`
- `(f, g, h, i, j)` are in `($s0, $s1, $s2, $s3, $s4)`
```
bne $s3, $s4, Else # go to Else if i != j
add $s0, $s1, $s2 # f = g + h (skipped if i != j)
j Exit
Else: sub $s0, $s1, $s2 # f = g – h (skipped if i == j)
Exit:
```
- Branch addresses are **calculates by the assembler**
- Compiler and assembly language programmer don’t need to do this tedious works
### Loops
- Example: `while (save[i] == k) i += 1;`
- `(i, k)` are in `($s3, $s5)`, base address of `save` is in `$s6`
```
Loop: sll $t1, $s3, 2 # $t1 = i * 4
add $t1, $t1, $s6 # $t1 = address of save[i]
lw $t0, 0($t1) # $t0 = save[i]
bne $t0, $s5, Exit # go to Exit if save[i] != k
addi $s3, $s3, 1
j Loop
Exit:
```
- Basic block
- A sequence of instructions
- 符合以下條件
- Without branches (except possibly at the end)
- Without branch targets or branch labels (except possibly at the beginning)
- One of the **first early phase** of compilation is breaking the program into basic blocks
- 先分成 basic block 再進行其他優化
- ==只能從頭到尾執行完==
### Register comparison
- To compare two registers and set a third register to 1 if the first is less than the second; otherwise, it is set to 0
- For signed integers
- **Set on less than**:
```
slt $t0, $s3, $s4 # $t0 = 1 if $s3 < $s4
```
- **Set on less than immediate**:
```
slti $t0, $s3, 10 # $t0 = 1 if $s3 < 10
```
- 數字以二補數儲存
- MIPS compilers use the `slt`, `slti`, `beq`, `bne`, and the fixed value 0 to create all relative conditions
- Register <font class='red'>`$zero`</font> always contains the fixed value 0
- For unsigned integers
- ***Set on less than unsigned*** (<font class='red'>`sltu`</font>)
- ***Set on less than immediate unsigned*** (<font class='red'>`sltiu`</font>)
- Example: Signed vs. Unsigned comparison
- ```
$s0: 1111 1111 1111 1111 1111 1111 1111 1111
$s1: 0000 0000 0000 0000 0000 0000 0000 0001
```
- ```
slt $t0, $s0, $s1 => (-1) < 1 => $t0 = 1
```
- ```
sltu $t0, $s0, $s1 => 4,294,967,295 > 1 => $t0 = 0
```
### Case/switch statement
- To select one of many alternatives depending on a single value
- ***Jump address table (jump table)***
- A table of address of alternative instruction sequences
- To index into the table and then jump to the appropriate sequence
- ***Jump register (<font class="red">jr</font>)***
- Unconditional jump to the address specified in a register
- `jr $s0`
## Supporting Procedures in Computer Hardware
### Procedure
- A stored subroutine that performs a specific task based on the parameters with which it is provided
- **Caller**: the calling program
- **Callee**: the procedure itself
- Execution of a procedure
- Put parameters in a place where the callee can access them
- Transfer control to the callee
- Acquire the storage resources needed for the callee
- Perform the desired task
- Put the result value in a place where the caller can access it
- Return control to the caller
- Registers for procedure calling
- **$a0 ~ $a3**: four argument registers in which to pass parameters
- **$v0 ~ $v1**: two value registers in which to return value
- **$ra**: one return address register to return to the point of origin
- ***Jump-and-link*** instruction <font class="red">`jal`</font>
- `jal ProcedureAddress`
- To jump to an address and simultaneously save the ***return address (PC + 4)*** in register `$ra`
- ***Program counter (PC)***
- Execution steps
- The caller puts parameter values in `$a0` ~ `$a3`
- `jal X`
- The callee performs the calculations and places results in `$v0` ~ `$v1`
- `jr $ra`
### Using more registers
- A compiler may needs more registers for a procedure
- **Stack**
- A data structure for spilling registers organized as a last-in-first-out queue
- **Stack pointer** (`$sp`)
- A value denoting the most recently allocated address in a stack
- **Push**: `$sp` is decreased
- **Pop**: `$sp` is increased
- Example: Compiling a C procedure that doesn't call another procedures
- `(f, g, h, i, j)` are in `($s0, $a0, $a1, $a2, $a3)`
- To avoid saving and restoring a register whose value is never use
- `$t0` ~ `$t9`: **temporary registers**, not preserved by the callee on a procedure call
- 隨時有可能被洗掉
- `$s0` ~ `$s7`: **saved registers**, preserved on a procedure call
### Nested procedures
- ***Leaf*** procedure: a procedure do not call other
- Recursive procedure call
- Conflict over $a0 ~ $a3 and $ra
- Solution: to push all the other registers that must be preserved onto the stack
- Example: Compiling a recursive C procedure, showing nested procedure linking
- `n` is in `$a0`
```c
int fact (int n) {
if (n < 1) return (1);
else return (n * fact(n - 1));
}
```
==PPT p.33 要自己練習一次==
- A C variable is generally a location in storage
- Type: integers, characters,...
- Storage classes
- ***Automatic*** 區域變數
- Local to a procedure and be discarded when the procedure exits
- ***Static*** 全域變數
- Will exist across exits from and entries to procedures
- To be declared outside all procedures
- To be declared using the keyword static
- ***Global pointer*** (<font class="red">`$gp`</font>)
- 存全域變數資料的位址
- The register reserved to point to static data
- Procedure frame (**activation record**)
- The segment of the stack containing a procedure’s saved registers and local variables
- ***Frame pointer*** (<font class="red">`$fp`</font>)
- To point to the first word of the frame of a procedure
- To offer a stable base register within a procedure for local memory references
- `$sp` might change during the procedure
- Using `$sp` to reference to a local variable in memory might have **different offsets** depending on where they are in the procedure.
> 因為 `$sp` 在 procedure 過程中會變動，所以不適合當作基準點，因此利用 `$fp` 當作基準點方便使用。
---
- The MIPS memory allocation （數字僅供參考，會隨處理器而不同）
- Reserved ($\rm 0 \sim 003FFFFF_{hex}$)
- **Text segment** ($\rm 00400000_{hex} \sim 0FFFFFFF_{hex}$)
- **Static data segment** ($\rm 10000000_{hex} \sim 1000FFFF_{hex}$)
- Constants and static variables
- `$gp`: initialized to $\rm 1008000_{hex}$ (中間)
- (因為從 0000 ~ FFFF 需要一個無號數加法器才爬的到，放在中間就可以利用一般的加法器達成。)
- **Stack** and **dynamic data** ($\rm 10010000_{hex} \sim 7FFFFFFC_{hex}$)
- Stack: `$sp` is initialized to $\rm 7FFFFFFFC_{hex}$ and grows down
- Dynamic data structure (**heap**)
- To start at $\rm 10010000_{hex}$ and grow up
- **`Malloc()`, `free()`**
- To allow the stack and heap to grow toward each other
### Elaboration
- If there are **more than four parameters**, these extra parameters are placed on the stack just above the frame pointer in MIPS
- Frame pointer `$fp` is not necessary
- **`jal`** will save the address of the instruction that follow **`jal`** into register `$ra`
## Communicating with People
- Instructions to move **bytes** and **halfword** (8 bit)
- ```
lb/lbu/sb $t0, 0($sp)
```
- Memory $\leftrightarrow$ the rightmost 8-bits of a register
- `lb` sign extends the byte, `lbu` zero extends the byte
- ```
lh/lhu/sh $t0, 0($sp)
```
- Memory $\leftrightarrow$ the rightmost 16-bits of a register
- Characters (ASCII code) $\rightarrow$ strings
- Three choices for representing a string
- The first position of the string is reserved to give the length of a string
- An accompanying variable has the length of the string
- Java includes a word that gives the length of the string
- The last position of a string is indicated by a character used to mark the end of a string
- In C, a string is terminated with a byte whose value is 0
- Example: Compiling a string copy procedure, showing how to use C strings
- `i` is in `$s0`, base address of `(x, y)` is in `($a0, $a1)`
- strcpy is a leaf procedure, `i` can be allocated to a temporary register instead of `$s0`
```c
void strcpy(char x[], char y[]) {
int i;
i = 0;
while ((x[i] = y[i]) != ‘\0’)
i += 1;
}
```
## MIPS Addressing for 32-Bit Immediates and Addresses
### Address in branches and jumps
- ***J-type format (J-format)***
- 
- op (**opcode**): basic operation of the instruction
- Target address: $2^{26}$ words
- For **jump** (`j`) and **jump-and-link** (`jal`) instructions
- Example
```
j 10000 # go to location 10000
```
- Conditional branch
- **I-type** instruction
- Example
```
bne $s0, $s1, Exit # go to Exit if $s0 != $s1
```
- Program counter = register + branch address
- Branch range: $\pm 2^{15}$ words
- The program to be as large as $2^{32}$ words
- **PC-relative addressing**
- The address is the sum of the program counter (PC) and a constant in the instruction
- Conditional branch instructions can branch within $\pm 2^{15}$ words of the current instruction
- Almost all loops and if statements are much smaller than $2^{16}$ words
- The 26-bit field in jump instructions is also a word address
- Example: Showing branch offset in machine language
- Loop starting at location 80000 in memory
==必考==
- Example: Branching far away
- The target address of a conditional branch instruction exceeds $2^{16}$ words
- To **insert an unconditional jump** to the branch target and invert the condition
- ```
beq $s0, $s1, L1
```
- 如果 `beq` 跳不到，可改寫成
```
bne $s0, $s1, L2
j L1
L2:
```
### MIPS addressing mode summary
- **Immediate addressing**
- The operand is a constant within the instruction itself
- **Register addressing**
- The operand is a register
- **Base or displacement addressing**
- The operand is at the memory location
- Address = base register + constant (in the instruction)
- **PC-relative addressing**
- Branch address = PC + constant (in the instruction)
## Translating and Starting a Program
（隨便看就好）
## Fallacies and Pitfalls
（隨便看就好）
- Fallacies
- More powerful instructions mean higher performance
- Example: to move data in memory (Intel x86)
- Solution 1: using a move instruction with the repeat prefix
- Solution 2: using standard load and store instructions
- Solution 3: using the larger floating-point registers instead of the integer registers
$\Rightarrow$ Speed: solution 1 : solution 2 : solution 3 = 1 : 1.5 : 2
- Write in assembly language to obtain the highest performance
- The increasing sophistication of compilers means the gap between compiled code and code produced by hand is closing fast
- The dangers of writing in assembly language
- The longer time spent coding and debugging
- The loss in portability
- The difficulty of maintaining such code
- When a program becomes popular, someone has to update the code and make it work with new releases of operating systems and new models of machines
- Writing in higher-level language
- To allow future compilers to tailor the code to future machines
- To make the software easier to maintain
- To allow the program to run on more brands of computers
Sign in with Wallet
Connect another wallet