Understand the world on C.S.
當程式需要操作對底層的做操作，或者需要追求極致的執行效能/檔案大小，這時候通常就會使用 組合語言 (Assembly Language) 來發開程式。原則上來說，所有程式都可以用組合語言來開發 (因為所有程式最後都是執行機械碼，而機械碼可以反編譯成組合語言)， 然而不是每個人都會想要用組合語言來開發程式，原因在於組合語言高度平台相關： 每個不同的平台 (尤其是 CPU) 需要用不同的 指令集 (Instruction Set) 來實做不同的邏輯。
正常來說，常見的數學運算邏輯在設計上只需要在 register 間做運算即可。用下面的數學式為例 $2+3*5-7/4$，按照正常的數學運算來說， 需要先計算 $3*5$ 接著計算 $7/4$ 最後在計算 $2 + (3*5) - (7/4)$。按這樣的邏輯，我們可以寫出下面的程式碼：
mov $reg1, 2
mov $reg2, 3
mov $reg3, 5
mul $reg2, $reg3
mov $reg4, 7
mov $reg5, 4
div $reg4, $reg5
add $reg1, $reg2
sub $reg1, $reg4
在這個程式中總共需要 5 個 register 來暫存過程中的結果。當然，也可以經過一些優化來降低 register 的使用，但是不優化的情況下， 不太表這個程式碼是可以使用的。原因在於 div 這個指令集要求 quotient 跟 remainder 需要分別是 ax 與 dx： 這表示 div 後的結果已經被限制在特定的 register。在這種因為指令集有特定的限制，所以需要將程式碼中未知的 register 給一定的限制：
mov $reg1, 2
mov $reg2, 3
mov $reg3, 5
mul $reg2, $reg3
mov $rax, 7
mov $reg5, 4
div $rax, $reg5 ## only consider quotient
add $reg1, $reg2
sub $reg1, $rax
所以在上述的例子中，剩下四個 register 需要確定，這樣我們就可以隨意的填入想要的 register。但如果 register 在這個 CPU 架構中只有 4 個可以使用 (rax / rcx / rdx / rbx) 的話，則我們需要額外考慮如何處理如何紀錄運算中的過程：
mov $reg1, 2
mov $rbx, 3
mov $rcx, 5
mul $rbx, $rcx
mov $rax, 7
mov $rdx, 4
div $rax, $rdx ## only consider quotient
add $reg1, $rbx
sub $reg1, $rax
當然，我們也可以經過一些優化，讓執行的順序重新排列而 rcx 可以空出來給 $reg1 使用，但我們依然先無視這種優化的可能性。 在這種情況下，我們就需要將 register 的內容儲存在記憶體當中，並且等到後續的運算中在拿出來使用：
mov $rbx, 2 ## First value: 2
mov $rax, 3
mov $rcx, 5
mul $rax, $rcx
push $rax ## Cache the result for 3*5, and $rax is free to used
mov $rax, 7
mov $rdx, 4
div $rax, $rdx ## only consider quotient: 7/4
pop $rcx ## Get the previous result: 3*5
add $rbx, $rcx
sub $rbx, $rax
然而，如何判斷哪些 register 需要放入到記憶體當中是一個經典的演算法問題： Register Allocation ，這個問題可以等價的替換成 著色問題 。
然而在一些比較特殊的例子 instruction set 需要特定 register 來使用，像是 shr 這個指令後面可以接 IMM8、cl 以及 1 (在 x86_64 的環境下)， 在這種比較特殊的情況下，我們就不可以隨意的指定 register。思考下面的運算式： x = y » z，我們會根據 z 的值而會有不同的指令集選擇。 當問題比較是比較簡單的常數時，就可以使用 IMM8 或者是 1 這兩種 case。然而如果 z 是之前運算的結果時，我們就無法預測他的值而需要先放到 register 當中。這時候就被強迫使用 cl。在之前的例子中，我們知道變數可以被隨意的塞到任意的 register，只要滿足著色問題即可。然而在這裡， 這個節點則是被強迫先行填入 cl，導致著色問題可能無法得到最佳解，或者讓問題變得更加複雜。下面就是一種簡單的解決方法之一：
## assmue x = y (0x5) >> z (0x3)
mov $rax, 0x5 ## var y
mov $rdx, 0x3 ## var z
## Workaround method
push $rcx
mov $rcx, rdx
shr $rax, $cl
pop $rcx
Instruction Set
在 x86_64 的世界當中，他擁有不定長度的指令集：在此架構中，每個指令集的實際機械碼長度都不一樣。 他可能的指令可能是
[ Prefix ] [ REX ] [ Opcode ] [ ModR/M ] [ SIB ] [ Displacement ] [ Immediate ]
除了 opcode 之外還可能擁有 VEX Prefix 、SIB (scale-index-base byte) 等額外描述的部分。 這兩個都是用來在一個指令中描述兩個運算元 (operand) 的方式：可能是 register 或者是有效的記憶體位址。而且都是用一樣的方式來描述： 2-bits、3-bits、3-bits。用 SIB 為例：當需要指到特定的記憶體空間 (e.g. [base + index*scale])，就可以用下面的規則來指定。
- 開頭兩個 bits (most-significant 2 bits) 用來描述 scale。
- 接下來三個 bits 用來索引 (index)。
- 最後三個 bits 用來當做起始位址 (base)。
其實這個章節需要翻的是 x86_64 的手冊，但主要又不是要做 CPU 或者是 Compiler。所以就上網找了一下 這個 跟 那個 來補充一下基本知識。
Legacy Prefix
在 x86_64 的世界當中，指令集的開頭可能是 1~4 byte 的 prefix：包含了如何解釋接下來 register size 以及 two-byte instruction 的可能性。在 legacy prefix 當中，會用一個 byte 來描述接下來的 register 或者是 memory 的大小，或者是偏移量：
- 使用的時候必定含有 0x40
- REX.W (0x08) 代表接下來的 register 包含著 64-bit 用的 register。
- REX.R (0x04) 代表會擴充 ModR/W 這個 Field，可能是使用到擴充的 register (r8~r15)。
- REX.X (0x02) 代表會擴充 SIB 這個 Field，可能是 memory 位址中第二個 register 使用到擴充的 register。
- REX.B (0x01) 代表會擴充 R/M、base 或者是 register field，通常是 memory 位址中 第一個 register 使用到擴充 register。
例如 0x48 是用來接下來的描述會有 64-bits register 存在。
0x66 則是用來表示運算元 (operand) 的大小有被覆寫。
Two-Byte Instruction
額外的 prefix (0x0F) 用來表示使用到另一組的 Instruction set。
Mod R/W and SIB
Mod R/W 以及 SIB 是用來將兩個運算元編碼 (encode) 成一個 byte 的方式。它可以是一個 register 或者是有效的記憶體位址。Mod R/W 是當指令集需要對記憶體做操作說明尋址的模式。 Mod R/W 的組合規則是：
7 0
+-------+-------+----+
| mod | reg | rm |
+-------+-------+----+
- mod (2-bits)：當值為 0b11 的時候表示 register-direct addressing 模式，否則則是 indirect 模式。
- reg (3-bits)：在某些指令集可以用來擴充 opcode。
- rm (3-bits)：根據指令集會作用在來源 (source) 或者是目的 (destination) 操作元。
例如 0b 10 000 001 表示：mem + disp32 (10)、沒有擴充使用 (000)、第二個 register (001)
當 Mod R/W 的尋址模式，有時候需要使用 SIB 來補充尋址的方式。例如需要讀取兩個 register 來尋址時， 就需要額外使用 SIB 來表示。SIB 的結構也跟 Mod R/W 一樣：
:::bash
7 0
+-------+-------+------+
| scale | index | base |
+-------+-------+------+
- SIB.scale (2-bits)：用來表示 SIB 的大小 (2 的冪次)。
- SIB.index (3-bits)：指定哪一個 index register 的即將被使用。
- SIB.base (3-bits)：指定哪一個 base register 的即將被使用。
例如 0b 00 010 000：沒有擴充大小 (00)、rdx 為 index register (010)、rax 為 base register (000)
例如 0b 01 001 010：擴充兩倍 (01)、rcx 為 index register (001)、rdx 為 base register (010)
上述兩個例子中都需要 Mod R/W (04)，這是用來指示後面的 SIB 為尋址的方式，其中 Mod R/W.mod 用來表示後面接的 Displacement 的大小 (0 byte、disp8、disp32)。
Displacement / Immediate
Displacement 的用途相對簡單，他可以是 1、2、4 或者 8 bytes 的偏移量。在 8-bytes 的 Displacement 使用時， 將不使用後續的 Immediate 值。當 Mod R/W 或者是 SIB 指定需要使用 disp 的時候，或者在特定的指令集 (moffset、moffs) 的情況下，Displacement 則會被當作是指令集的一部份。
而某些指令集會需要常數 (Immediate) 的使用，而指令以及運算元的大小會決定 Immediate 的大小。當 Immediate 需要用到 8-bytes 的時候，Displacement 則不會被使用。
[To Be Continue….]