CS:APP Ch3 Machine-level Representation of Programs

透過高級語言開發效率更高也更可靠，用高級的語言開發可以在不同的機器上編譯和執行，而 assembly code 則是與特定機器密切相關。

為什麼還需要學習 assembly code 呢？

1. 通過閱讀 assembly code ，可以了解編譯器如何優化、理解電腦如何執行程式並分析其中的低效率之處。
2. 試圖最大化一段關鍵程式碼效率的過程中，可以透過不斷修改程式碼，並觀察編譯器產生的 assembly code 來了解如何最大化效率。
3. 高級語言提供的抽象層會隱藏我們想了解的程式運行行為。例如了解 thread 之間是如何共享資料或是如何管理私有資料等。

重要名詞

• Instruction Set Architecture (ISA) : 必須理解 ISA 才能夠撰寫 assembly code 或是 machine code ，裏面定義處理器狀態、指令的格式以及每個指令應該執行所發生的行為。
  • Machine code: byte-level programs that a processor executes
  • Assembly code: A text representation of machine code
  • ISA 的例子有 x86, x86-64, ARM or RISC V
  • Instruction Set 是一個 software 和 hardware 之間的 interface。 (延伸閱讀: 計算機組織結構)
• Micro architecture: Implementation of ISA in processor
  • examples: cache size and core frequency
  • 一般我們在看組合語言會發現裏面是不會去控制 cache 的。
    • machine-level program 是由 ISA 所組成的，而 micro architecture 的概念包含的是處理器內部的構成和這些構成如何執行 ISA ，可以理解為 micro architecture 負責去實作出 ISA ，因此我們是無法透過 ISA 去控制 micro architecture 。
    • 另外一個概念是不同的 processor 是可能支援相同的 ISA ，例如 intel 和 AMD 的處理器就都支援 x86 的 ISA ，但可想而知，Intel 和 AMD 的 microarchitecture 是不同的。

Assembly / Machine Code View

我們知道 assembly code 和 C code 之間是有所差別的，有很多細節是在編寫 C code 無法去控制的，但對於程式設計師來說，這些概念應該要能夠了解

• Program counter ( PC ) : 下一個要執行 instruction 在記憶體中的位址。
• Integer Register file : 在 x86-64 的架構下，有 16 個暫存器可以使用，每個可以儲存 64 bits 的值，可以用來儲存 address （對應於 C 的 pointer ）或整數資料。
• Condition codes : 儲存 arithmetic or logical operation （例如 if 和 while） 的狀態資訊。
• Memory : 在 Ｃ 語言中我們可以使用各式各樣的資料結構、 signed / unsigned 或是指針，但對於 machine code 來說這些都只是一連串的 byte-addressed array 。

Turning C into Object Code

gcc 利用一整套工具將原始程式碼轉換為可執行的程式。

Compiler

• C preprocessor 插入所有 #include 所指定的標頭檔，並擴展所有 #define 指定的 macro ，接著產生 assembly code 。

Assembler

• 將 .s 轉為 .o
• 將 instruction 轉換為二進位格式。
• object code 是 machine code 的一種，差別在於不同檔案的程式碼尚未有 linkage 。

Linker

• resolve reference between files
• Combine with static run-time libraries. ex: malloc , printf
• Some libraries are dynamically linked
• 所產生的 machine code 可以被處理器直接執行。
  可以參考： CS:APP CH7 Linking 筆記

Disassembling object code

使用 GDB

• 進入到 GDB 之後，可以針對個別 procedure 進行 disassembling

指令	效果
$ disas	disassemble 當前函式
$ disas funcA	disassemble 函式 funcA
$ disas 0x005566	disassemble 位址 0x005566 附近的函式
$ disas 0x001234, 0x005566	disassemble 指定位址內的程式碼
$ print /x $rip	以 16進制輸出 program counter 內容

使用 objdump

• 會顯示每個 instruction 的 bit pattern
• 製造出幾乎一樣的 assembly code ( disassembler 所使用的指令命名規則可能和 GCC 產生的 assembly code 有些微不同 )
• 可以對完整的執行檔 (a.out) 或是 .o file 來直接執行，且 objdump 不需要知道原始 source code 就能夠 disassemble 。

Data types in Assembly code

• Integer : 最一開始是由 16 bit 擴展為 32 bit 的架構， Intel 定義 "word" 為 16-bits 的 data type 。而 "double word" or "long word" 代表 32-bits 大小的資料，"quad word" 代表 64-bits。在 assembly code 中的 integer 大小可以為 1, 2, 4 or 8 bytes.
• Floating Point : 4 (對應到 c 的 float ), 8 (對應到 c 的 double ) 和 10 bytes（對應到 long double ，但不建議使用他，並不是所有類型的機器都支援，且執行起來低效）

x86-64 integer Register

資料來源： https://www.cs.cmu.edu/~fp/courses/15213-s07/misc/asm64-handout.pdf

每個 x86-64 的 CPU 都包含 16 個暫存器來儲存資料和 pointer 。這些暫存器也可以只使用其 low-order 的 4, 2 or 1 bytes ，暫存器名稱可以由圖得知。在早期的 32 bit 架構下，例如 IA-32 ，只有 8 個暫存器且以 e 開頭來命名各暫存器，例如 %eax , %esp 。

Operand Type in Assembly code

有三種 operand type ，分別是 Immediate, Register and Memory

• Immediate : 內含常數，其表示方式開頭必定有 '$' ，ex: $0x5566, $-123

• Register : 為 x86-64 integer type ，ex: %rax, $r14

• Memory : 根據 register 給定的位址再到該記憶體位址讀出 data 。

  Register Indirect addressing: (%rax) 代表的是先從暫存器 %rax 讀出內容，該內容只是一個 memory address，接著到 memory 中該位址讀出資料，這樣的動作如同在 C 中 dereferencing pointer 。

  這樣的 memory addressing Mode 還有許多種格式，可以參考 wikipedia 或書中 p121 ，下面投影片提供 general form。

❓Scale 為什麼只能夠是 1, 2, 4 or 8 呢？

由於我們從 memory 中讀出來的資料，必定是某一種的 data type (char, integer, long …） ，例如我們要讀出一個 integer ，他在 memory 上的 address 必定是對齊 4 的倍數，因此 scale 必須符合各種 data type 的大小，即 1, 2, 4 or 8 。

資料來源：http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf

Operations in Assembly code

Moving Data

	mov  src, dst

src 和 dst 可以是任何一種 operand type ，但在 x86-64 有一條限制，src 和 dst 不能同時都是 memory 的位址 。

load effective address

leaq  Src, Dst

這個指令等同於將 &Src 寫到 Dst 中，可以為後續的操作製作出指標。

但其實這個指令還有一個妙用，可以用來計算 x + k*y ，其中 k 為 1, 2, 4 or 8 ，為什麼 k 只能為這4個值呢？ 可以回憶前面學到的 complete memory addressing mode 搭配以下範例。

更多的 arithmetic operations 可見下圖：

Machine-Level Programming - Control

在 C 語言當中，我們有 if , while 等可以根據測試條件來決定執行順序，在 assembly code 中有兩種基本的機制來實現這樣的行為，

1. 計算測試條件，根據結果改變控制 flow ，在以下 Conditional Branch 章節探討。
2. 計算測試條件，根據結果改變資料 flow ，在以下 Conditional Moves 章節探討。

Condition Codes

除了 16 個 integer register ，CPU 還維護著一組 condition code register ，用來紀錄最近 arithmetic or logical operation 的結果，藉此來執行條件分支 （conditional branching）指令。常見的有以下：

• CF Carry Flag：用來檢查 unsigned 變數運算是否 overflow
• ZF Zero Flag：用來檢查運算結果是否為 0
• SF Sign Flag：用來檢查 signed 運算結果是否為負數
• OF Overflow Flag：用來檢查 signed 變數運算結果是否為負數

leadq 指令不會改變任何 condition codes, 他是用來進行地址計算的。

Jumping

正常情況下指令會照順序一條一條執行， jump 指令會導致執行順序切換到程式中的某個位置。在 assembly code 中， jump 指令的目的地通常會用一個 Label 來指明。

• jump 指令會 implicitly read condition codes 來決定是否執行 jump 。

Conditional Branch

以下圖程式碼為例，首先比較 x 跟 y 並設定 condition code，如果 x ≤ y 就 jump 到 Label .L4 。

資料來源：http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf

再將上圖的組合語言再轉換為 C 語言幫助理解（如下圖右邊程式碼），這樣的行為如同使用 C 中的 goto 。

source: http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf

這種根據測試條件來改變控制 flow 的作法使用在現代 CPU 上有可能會導致效能下降。

考慮到 CPU 使用 pipeline 技術，一條指令會被拆分為好幾個階段，如此 pipeline 內可以充滿待執行的指令來提升效能。 但是當遇到 conditional branch 的狀況，CPU 會採取 branch predict 方式，猜測接下來會執行哪個分支，才能夠在 pipeline 上預先放好待執行的指令 （現代 cpu 設計都試圖達到 90% 以上成功率），但是若預測失敗，也就代表許多已經執行的指令需要捨棄，造成效能上的浪費。

Conditional Moves

相較於 Conditional branch 可能造成效能的浪費，Conditional move 透過一次將兩種結果事先計算好，接著再根據條件是否滿足選取對應的結果，這樣子就不需要執行 branch predict ，可以依照指令順序執行，可見下圖範例。

source: http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf

但是 Conditional Move 並不總是提高效率，如果分支都需要執行大量的運算，那麼當相對應條件不滿足，不滿足分支所做的工作也是白費，同樣是效能上的浪費。或是分支的執行可能會造成無法預期的結果等（可見下圖）。

source: http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf

老實說，編譯器並沒有足夠多的資訊來判斷該使用何種 Conditional Branch 或是 Conditional Moves 才有效率，根據 GCC 的測試結果來看，只有當兩個分支的 expression 都很容易計算時，才會使用 Conditional move ，其餘還是採用 Conditional branch 。

Jump table structure

Switch statement 搭配 jump table 來實現， jump table 是一個 array ，內部存放著某個 code section 的 address ，當透過 index 來取得對應的 address，就可以 jump 過去，jump table 讓實現 multi-way branching 更加高效。

可見書 p159 的範例。

Machine-Level Programming - Procedures

procedure 是一種封裝程式碼的方式，用一組指定的參數和一個回傳值來實現特定功能，可以在任意地方呼叫使用 procedure 。在不同的程式語言中， procedure 有不同形式的呈現，可以是 function, method, subroutine 或 handler 等等。

x86-64 Stack structure

C 語言使用 procedure 過程中，可以透過 stack 來管理所需要操作的資料。

• 當 procedure 需要的記憶體空間超過 register 所能提供的，就會在 stack 上分配新空間，稱之為 stack frame，下圖即為 stack frame 的架構。

• stack 的記憶體是採取後進先出的原則。若是由 procedure P 呼叫 procedure Q ，此時 stack 中已經包含了 procedure P 的 stack frame，當 Q 執行時，透過 pushq 幫 procedure Q 向下新增他所需要的 stack frame，procedure Q 可以在 stack 中為 local variable 分配使用的空間，當 procedure Q 要回傳時，由 popq 指令來增加 %rsp ，值得注意的是，procedure Q 所使用的記憶體並不會被清空，單純透過移動 %rsp 指向的位置來分配 stack 。

• stack 是往 lower address 方向擴展，因此 %rsp 總是指向 the lowest address 。

• 事實上，許多 procedure 根本不需要分配 stack frame ，過程中所需要的參數可以都過 register 來傳遞即可 。 這邊也意味著一件事情，當我們在寫程式碼時候，應該避免傳遞不需要的參數，避免宣告不需要的記憶體，否則會造成 stack 空間的浪費，這樣的問題在遞迴使用過程更是嚴重，過多的 recursion 會造成 stack overflow 問題。 (延伸： tail recursion 透過參數來傳遞結果，減少不要 stack 的使用，來避免 stackoverflow 的具體例子)

假設 procedure P 呼叫 procedure Q, Q 執行完返回到 P 這樣的過程會發生以下機制：

Passing Control:

控制轉移到 procedure Q 前：

(1) 將 return address（ P 中呼叫 Q 的該條指令的後面位址） push 進 stack 中。

(2) 要將 program counter 設為 Q code section 的開始位址並 jump (在 x86-64 中為 call 指令)

在 procedure Q 執行完回傳時：

(1) 從 stack 中 pop 出 return address 並 jump (在 x86-64 中為 ret 指令)

(2) 再將 program counter 設為 P 中呼叫 Q 的該條指令的後面位址 。

Passing Data

例如 P 必須向 Q 提供一個或多個參數，Q 必須能夠向 P 回傳一個值。

總共有 6 個 register 可以用來存放參數，還有一個 register %rax 來存放 return value ，因此要是傳遞的參數超過 6 個，必須要在 stack frame 額外分配空間，這些空間將位於圖中的 "Argument build Area" 區塊，另外，通過 stack 傳遞的資料大小都向 8 的倍數對齊。

Managing Local Data

以下狀況發生時，必須將 local data 存放到 stack frame 中的 "Local Variables" 區塊，且 stack frame 在 call procedure 到 called procedure 回傳時都必須被存著。

1. register 不足以存放所有的 local variable 。
2. 對一個 local variable 使用 & ，必須為它產生一個位址。
3. 某些 local variable 為 array 或 struct ，因此必須能夠透過 array 或 struct 被訪問

以下圖遞迴為例，function who() 呼叫 amI() ， amI() 會再遞迴呼叫到 amI() ，可以觀察到 stack frame 是不斷的增長。

source: http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf

當 amI() 逐一回傳時，回到了 who() 時，從下圖可以知道此時 %rsp 指向的是 who() 的 stack frame 。

source: http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf

Register Saving Conventions

前面提到當 register 不敷使用時，才會在 stack frame 上分配記憶體，但若是遞迴的狀況下，這些 register 可能會不斷被多個 procedure 使用到，被呼叫者 (callee) 有可能將呼叫者 (caller) 所使用的 register 內資料覆蓋掉。因此 x86-64 採用統一的 register saving conventions 來避免這種狀況。

1. Caller Saved
   • caller 在呼叫 procedure 之前，會將 register 內資料存在自己的 stack frame 中
   • 可以理解為這類型的 register 內的值都可以自由被修改，因為 caller 本身必須負責去保存該 register 的資料。
2. Callee Saved
   • callee 在使用 register 之前，會先將該 register 資料存在自己的 stack frame 中
   • callee 在回傳到 caller 之前，再將資料恢復到 register 中
   • 舉例來說，procedure P 呼叫 procedure Q ， 在進入 procedure Q 時，callee-saved register 必須由 Q 先存在 stack frame 中或是完全不去使用它，當 Q 要回傳回 P 時，再將這些 register 內的資料恢復原狀。

下面圖中詳述 x86-64 架構中各 register 的類型

Observation about Recusion

stack frame 的機制讓我們使用遞迴時候不需要做任何額外的處理。

• stack frame 意味著每個 procedure 可以保有自己的 private storage
  • Saved register & local variables
  • Saved return pointer
• Register saving contentions 可以避免 procedure 呼相汙染彼此的資料
• Stack 在 procedure 被呼叫時候分配，在回傳時 deallocate ，這樣的機制很自然的符合 function 的 call / return 順序。

Machine-level Programming - Data

3.8 Array Access

T A[N]

上面是在 C 語言宣告一個 array 的方法，他在記憶體分配一塊 L * N bytes 的連續記憶體，其中 L 為 data type T 的大小。且引入 identifier A ，可以用 A 來表示一個指向 Array A 開頭的指標。

Pointer Access

• 每個指標都對應到一個 type 。 這個 type 表明指標該指向哪一類物件 ( object ) 。

int *ip;
char **cpp;

變數 ip 是一個指向 int type 物件的指標，而 cpp 指向的物件，其本身就是一個指向 char type 物件的指標。

• 每個指標都有一個值，這個值是某個指定類型的物件的位址。

• & 可以產生指標，對於一個表示某個變數的表達式 Expr ， &Expr 給出該變數位址的一個指標。

• * 間接引用指標，對於一個表示位址的表達式 Expr ， *Expr 給出該位址處的值。
  表達式 Expr 與 * &Expr 是相等的。

• Array 和指標緊密關聯，一個 array 的名字等於其首位元素的位址，因此 Array 變數又等同於一個指向 Arr[0] 的指標。 而 array 名字搭配上指標運算就如同陣列引用有一樣的效果，也就是說 *(Arr + i ) 等同於 Arr[i] 。

• 陣列引用和指標運算都需要用物件大小對偏移量進行伸縮。當我們寫表達式 p+i ，這裡的指標 p 的值為 p ，得到的位址計算為 p+ L*i ，這裡 L 是與 p 相關連的 data type 的大小。

• 將指標由一種 data type 強制轉換成另一種 type ，只改變他的 type ，不改變他的值。

  強制類型轉換的一個效果其實就是改變指標運算的伸縮量。
  例如，p 是一個 char * type 的指標，他的值為 s ，那麼表達式 (int *) p+7 計算為 s+28 （強制類型轉換的優先級高於加法），而 (int *) (p+7) 計算為 s+7 。\

• 指標也可以指向函式，提供一個強大的儲存和向程式碼傳遞引用的功能。函式指標的值是該函式 machine code 的第一條指令的位址。

  ​​​​int (*f) (int*);
  

  這是一個函式指標的宣告，要從裡（從 "f" 開始）往外讀。 因此，我們看到像 "(* f)" 聲明的那樣，f 是一個指標，而 " (* f) (int )" 代表 f 是一個指向函式的指標，這個函式是以一個 int 作為參數。

  最後，我們看到，他是指向以 int* 為參數並回傳 int 的函式的指標。

  *f 兩邊的括號是必須的，否則宣告變成：

  ​​​​int *f (int *);
  

  會被解讀為

  ​​​​(int *) f (int *);
  

變為一個單純函式的宣告，以 int* 作為參數，並回傳 int * 。

Reference	Type	Value
&val[i] - val	long	i

val[i] 為 index 為 i 處的值，透過 & 來取得指向 val[i] 的指標，而 val 本身也是指標，兩個指標相減就等同相同 Array 中兩個值的 index 差距。

延伸閱讀： Pointer subtraction Confusion on stackoverflow 加

Alignment Principle

如果 primitive data type 需要 K bytes， 則位址必須是 K 倍數 （通常是 2, 4 or 8），這樣的設計簡化了 CPU 和 memory 之間接口的設計。

例如一個 CPU 總是從 memory 中讀 8 bytes ，則位址就必須是 8 的倍數。如果我們能保證所有 double type data 的 address 都對齊 8 的倍數，就可以用一個記憶體操作的指令來讀或寫。否則需要執行兩次 memory access ，因為資料可能被放在兩個 8 bytes 的 memory 區塊內。 儘管沒有對齊位址 CPU 仍舊能夠正常運動，但是會造成效能的降低，因此還是建議要做好對齊。

編譯器會於 assembly code 放入以下命令，來表明 global data 怎麼對齊：

.align 8

Struct Alignment

在一個 struct 內會有各種不同 data type ，必須要能夠滿足每種 type 的 alignment 需求，同時 initial address 也必須滿足 alignment 要求，因此 struct 最終都以內部最大的 data type 來作為 alignment 的標準。

在 struct 內可以將較大的 data type 先宣告，這樣可以避免空間浪費，參考下方投影片的例子。

投影片來源 :

1. http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/05-machine-basics.pdf
2. http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/06-machine-control.pdf
3. http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/07-machine-procedures.pdf
4. http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/08-machine-data.pdf
5. http://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/lectures/09-machine-advanced.pdf

tags: CS:APP