# 計組 - ch2
###### tags: `Computer Organization`

## 二 . MIPS指令
### (一) . R-format
- $Instrcution\ 1$ : $add$
1. 格式 ： ```add $rd, $rs, $rt```。
2. 功用 ： 將```$rs```和```$rt```的和放到```$rd```。
- $Instrcution\ 2$ : $sub$
1. 格式 ： ```sub $rd, $rs, $rt```。
2. 功用 ： 將```$rs```和```$rt```的差放到```$rd```。
- $Instrcution\ 3$ : $srl$ (shift right logicly)
1. 格式 ： ```srl $rs, $rt, shamt```。
2. 功用 ： 將```$rt```進行『shift right』shamt個bit的值放到```$rs```。
3. 補充 ： 『shift right』 n個bit ，就是乘以 $2^n$ 。
- $Instrcution\ 4$ : $sll$ (shift left logicly)
1. 格式 ： ```sll $rs, $rt, shamt```。
2. 功用 ： 將```$rt```進行『shift left』shamt個bit的值放到```$rs```。
3. 補充 ： 『shift right』 n個bit ，就是除以 $2^n$ 。
- $Instrcution\ 5$ : $and$
1. 格式 ： ```and $rd, $rs, $rt```。
2. 功用 ： 將```$rs```和```$rt```的and放到```$rd```。

- $Instrcution\ 6$ : $or$
1. 格式 ： ```or $rd, $rs, $rt```。
2. 功用 ： 將```$rs```和```$rt```的or放到```$rd```。
- $Instrcution\ 7$ : $nor$
1. 格式 ： ```nor $rd, $rs, $rt```。
2. 功用 ： 將```$rs```和```$rt```的nor放到```$rd```。

### (二) . Conditional Instruction

- $Instrcution\ 1$ : $beq$ (branch if equal)
1. 格式 ： ```beq $rs, $rt, Labe```。
2. 功用 ： 如果```$rs```和```$rt```相等，則切換到Label的code。
- $Instrcution\ 2$ : $beq$ (branch if non-equal)
1. 格式 ： ```bne $rs, $rt, Label```。
2. 功用 ： 如果```$rs```和```$rt```不相等，則切換到Label的code。
- $Instrcution\ 3$ : $j$ (jump to label)
1. 格式 ： ```j Label```。
2. 功用 ： 切換到Label的code。
- $Instrcution\ 4$ : $slt$ (set one if right is bigger)
1. 格式 ： ```slt $rd, $rs, $rt```。
2. 功用 ： 如果```$rs```$<$```$rt```，則將```$rd```設為1。
- $Instrcution\ 5$ : $slti$ (set one if right is bigger)
1. 格式 ： ```slti $rt, $rs, const```。
2. 功用 ： 如果```$rs```$<$ ```const```，則將```$rt```設為1。
- $Instrcution\ 6$ : $lw$ (load word)
1. 格式 ： ```lw $rt, offset [$rs]```。
2. 功用 ： 在記憶體中，以```$rs```為起始位置的offset個地方load進去```$rt```。
- $Instrcution\ 7$ : $sw$ (read word)
1. 格式 ： ```sw $rt, offset [$rs]```。
2. 功用 ： 在記憶體中，以```$rs```為起始位置的offset個地方寫進去```$rt```。

- $Practice\ Condition$ : $if$
1. 概念 ： 處理```Not```的情況。
2. ```C code``` :
3. MISP code :

          bne $s3 ,$s4 ,ELSE 
          add $s0 ,$s1 ,$s2
          j EXIT
    ELSE: sub $s0 ,$s1 ,$s2 
    EXIT:  .....

- $Practice\ Condition$ : $Loop$
1. 概念一 ： 當不滿足condition時，跳出loop。
2. 概念二 ： 儲存記憶體指標的地方，需要仔細處理。
3. ```C code``` :
3. MISP code :

    LOOP: sll $t0, $s3, 2      
          add $t0, $t0, $s6
          lw  $t1, 0($t0)
          bne $t1, $s3, EXIT
          addi $s3, $s3, 1
          j LOOP
    EXIT: ....    

## 三 . Procedure Call
### (一) . Function call
- Leaf Procedure and Nested Procedure :
1. $Leaf\ Procedure$ : 一個function不會call其他function。
2. $nonleaf\ Procedure$ : 一個function會call其他的function。
3. C中的function call : 就是non-leaf呼叫其他的Procedure。
- Caller和Callee :
1. Caller : 呼叫其他function的角色。
2. Callee : 被呼叫的function的角色。
- function call下系統幫我們處理的事 ：
1. 將```Caller```目前的```register```變數儲存。
2. 將```Callee```需要的變數放到```$a```的暫存器。
3. 將控制全放到```Callee```下 ： 使用```j```的指令。
4. 執行```Callee```的程式碼。
5. 將```Callee```執行完的值存到```$v```內。
6. 回到```Caller``` : 使用```jr $ra```。

### (二) . Procedure Maintain - Example
- 假設有一個C的function被呼叫，系統需要處理的行為。
1. 假設此時的```g h i j```都已經存在```$a```中了。
2. 宣告的變數需要放到```$s```中。

int Leaf_Procedure(int g,int h,int i,int j){
      int f ;
      f = (g+h) - (i+j);
      return f;
}

- 所以，在Leaf Procedure被呼叫的時候，系統應該 ： 保存需要用到的變數空間。
1. 要用到```$t```做**計算**：保存變數於記憶體，並在結束時回複(2-5行)。
2. 要用到```$t```做**變數宣告**：保存```$s```的變數於記憶體，並在結束時回複(9-13行)。

    Leaf_Procedure : 
        addi $sp, $sp, -12
        sw   $t0, 8($sp)
        sw   $t1, 4($sp)
        sw   $s0, 0($sp)
        add  $t0, $a0, $a1
        add  $t1, $a2, $a2
        sub  $s0, $t0, $t1
        addi $v0, $s0, $zero
        lw   $t0, 8($sp)
        lw   $t1, 4($sp)
        lw   $s0, 0($sp)
        addi $sp, $sp, 12
        ja   $ra

- 優化 ： 所有的事都由```Callee```來做，會使的Callee負擔很大。
1. ```Caller```負責保存```$t```的變數(自己的)。
2. ```Callee```負責保存```$s```的變數(caller的)。
3. 問題 ： 那其他的register變數呢，要如何儲存？
- 總結 ： 下表為一個procedure被呼叫的時候，register的變數應該由誰維護。
1. ```Perserved``` : 必須保留，由```callee```負責。
2. ```non-perserved``` : 不一定保留，由```caller```視情況保留。

## 四 . Adressing Modal
### (一) . MISP的記憶體layout:
- 記憶體分類 ：
1. $Static\ Text$ : 儲存程式碼。
3. $Static\ Data$ : 儲存靜態變數或全域變數的。
4. $Heap$ : 動態的記憶體。
5. $Stack$ : 區域變數。
- 記憶體的指標 ：
1. ```pc``` : 下一個指令的位址。
2. ```$sp``` : ```stack pointer```，代表stack的位置。
3. ```$gp``` : ```gobal pointer```，操作gobal var，位於Static Data。
- ```$fp``` : 基準指標。
1. 因為：```$sp```會在程式執行中變化。
2. 所以：新增一個指標為```$fp```當為基準變化的地方。
- MISP的記憶體格式 ： 是一個**32bit*32bit**的空間。
1. address-value : 分成個別32個位元儲存。
2. 造成的問題 ： 記憶體的位址有$2^{32}$個，但是很多MISP操作記憶體的指令並沒有辦法有$2^{32}$個的移動空間，因此需要不同的『address modal』。

### (二) . 位元運算
- $Instrcution\ 1$ : $lb$
1. 格式 ： ```lb $rt, offset($rs)```。
2. 功用 ： 將```$rs```offset後的『一個byte』放到```$rt```。
- $Instrcution\ 2$ : $sb$
1. 格式 ： ```sb $rt, offset($rs)```。
2. 功用 ： 將```$rt```的『一個byte』放到```$rs```的offset之後。
- $Instrcution\ 3$ : $lh$
1. 格式 ： ```lh $rt, offset($rs)```。
2. 功用 ： 將```$rs```offset後的『半個word』放到```$rt```。
- $Instrcution\ 4$ : $sh$
1. 格式 ： ```sh $rt, offset($rs)```。
2. 功用 ： 將```$rt```的『半個word』放到```$rs```的offset之後。
- 例子 ： 存入一個32位元的整數。

### (三) . Adress Modal
- 什麼是『Adress Modal』：
1. 問題 ： 有時候記憶裝置(記憶體等等)的定址空間的範圍大於一個MISP的I/O指令可以操作的範圍，甚至大於32個bit。
2. 所以 ： 我們必須在僅有的資源下，使用不同的定址模型，幫助我們操作儲存空間。
- $Immediate\ addressing$ : 帶有常數的操作時。
- 例：帶有『 i 』的指令時。
- $Register\ addressing$ : 只有用到暫存器的操作。
- 例：```add sub```等等。
- $Base\ or\ displacement\ addressing$ : 有關記憶體的操作。
- 例：```lw sw```等等。
- $PC\ Relative$:也是有關記憶體的，但是開始的位置為```$pc```的位置。
- 特別用於```beq bne```等等指令。
- $Direct\ jump\ addressin$ : 可以使用整個32bit的大小轉換，但其實用的方法和PC relative差不多。
- 特別用於```j jal```等等指令。

### (四) . PC-Relative和Direct jump addressin
- PC-Relative
1. offest代表 ： ```$pc```的相對位址**除以4**(注意，```$pc```會一直變化)。
2. 使用format : ```L-format```，offset最高可以有$2^{16}*2^{2}=2^{18}$個bit。
3. 範圍 ： ```$pc```的正負$128K$個位置。

- Direct jump addressin :
1. offest代表 ： 要轉移的絕對位址**除以4**，但一定不足，所以再向```$pc```拿取前面4個bit。
2. 使用format : ```j-format```，offset最高可以有$2^{26}*2^{2}=2^{28}$個bit。
3. 範圍 ： ```$pc```的正負$256M$個位置。

- 例子 ： 如果$pc=40000000(16進位)$下。下面指令是jump到多少。
- 對pc拿4個bit : 即一個16進位的大小。
- 再把其加上j-format的offset。
- **比較不會有錯的方法**：全畫成2進位相加減

        PC     : 0010 0000 0000 0000 0000 0000 0000 0000
        offset : 0000 0000 0000 0000 0000 0010 0000 0001
        end    : 0010 0000 0000 0000 0000 0010 0000 0001

- 例子 ： 預測終點
- 用展開的方法，比較不會有問題。
- PC在```1ffff004```的地方，若目標在```20014924```上，可以用branch切換到嗎？
- 可以 ： 用相減跟最大就可以知道。

   Target : 0010 0000 0000 0000 0100 1001 0010 0100
   PC     : 0001 1111 1111 1111 1111 0000 0000 0100
   相減   :  0000 0000 0000 0001 0100 1001 0010 0000
   最大   :  0000 0000 0000 0011 1111 1111 1111 1111

## 五. MISP 解碼方法
### (一) . MISP指令的型態
- 一個Forrmat可以用多個address model。