# 課程資訊
禮拜一非同步教學
禮拜三面授

評分:
程式作業: 50%
小考: 3%
手寫作業: 12%
期中考: 15%
期末考: 15%
點名: 5%

# introduction
* 編譯器廣義來說是一種轉換工具；包含高階語言跟組合語言之間的轉換、不同系統執行檔間的轉換 (binary translation) 等等
* 設計編譯器時需要考慮以下重點
* 翻的內容須保證正確
* 翻出來的程式執行效率高 (翻出來的程式要能充分利用硬體資源)
* 翻譯時間必須在合理時間內
* compiler vs interpreter
* compiler: 先翻譯，再執行
* interpreter: 邊翻譯，邊執行
* static time vs dymanic time
* static time: 編譯時間
* dymanic time: 執行時間
## compiler 架構

### 前端
#### Lexical Analyzer
* 目的是將程式語言的 statement 轉換成 token
#### Syntax Analyzer
* 分析程式語法，並建構 syntax tree

* 中間節點: 運算子
* 中間節點的子節點: 運算元
#### Semantic Analyzer
* 語意分析，確認程式是否符合邏輯

ex: type checking 會把 a[-100] 判定成錯誤
### 中間層
#### Intermsdiate Code Generator
* 將 syntax tree 轉成
* 中間表示式可以視為組合語言的 psudo code


### 後端
#### Code Optomizer
* 在不改變邏輯的情況下，進一步優化中間表示式


#### Code Generator
* 轉成真正的組合語言輸出


# Lexical Analyzsis
* 在這個步驟中，會透過 Lexical Analyzer (又稱為 scanner) 將 statement 切成 token

## 工作原理
* Parser (Syntax Analyzer) **主動**向 Lexical Analyzer 要下一個 token
* Lexical Analyzer 回傳一個 token
* 兩者互動間透過 Symbol table 紀錄需要的訊息
## 名詞解釋
* token
* 是程式語言語法的最小單位
* 某種程式語言的 token 種類是一個有限集合
* 通常會由 \<token name (type), attribute value> 的形式來描述一個 token
* token name: 這個 token 的種類名稱
* attribute: token 的實際內容會存放至 symbol table 中，attribute-value 則是指向該 table 的指標
* pattern
* 針對某種 token 的定義與描述
* ex: 變數: 由大小寫字母或數字或底線組成，第一個字不能是數字
* Lexeme
* 符合某種 token 定義與描述的實際字串


* 實際例子

補充:
Semantic values: 就是一個 token 的 attribute value，將會影響 semantic analysis

## 設計流程 (必考)
### 第一步: 定義 token 種類
決定哪些 token 種類是必要的

### 第二步: 定義符合這個 token 的條件 (pattern)
使用 regular expression 進行定義

名詞定義
* alphabet (字母表): 可以用來組成 Lexeme 的字元
* string: 由 alphabet 中的字元組成的字串
* language: string 的集合。language 允許我們用有限的描述來定義一個集合。language 可以用以下方式產生

regular expression (RE)可以被視作用於描述 token type 的一種 language
regular expression 規則:
* |: or
* *: 重複任意 0~無限次
* 次方: 重複指定次
* (): 優先決定

推廣規則:
* +: 重複任意 1~無限次
* ?: 重複任意 0~1次
* []: 裡面的元素任意挑一個
* -: 連續
* ^: 除此之外

regular expression 範例:
* language -> 代表的集合

regular definition: 用來定義別名
* 別名 -> 實際代表的 RE
* ex:
* letter_ -> [A-Za-z_]
* digit -> [0-9]
* id (變數命名規則) -> letter_(letter_ | digit)*

補充: match 演算法
* lexemeBegin 將作為 match 的起始位置
* forward 將不斷往後找，直到 match 其中一個 token 的規則
### 第三步: 定義 pattern match algorithm (Lexeme)
* 此階段目標: 將 RE 的規則轉成程式碼
* 總結整體流程: 將 RE 轉成 NFA -> 將 NFA 轉成 DFA -> 拿 DFA 與實際的字串嘗試進行匹配
* NFA 跟 DFA 都是一種 Transition diagrams
* Transition diagrams 可以直接被程式實作

#### Transition diagrams
* 使用 Transition diagrams 可以表示 RE 的匹配過程
* 能實現 input string 的比對
* 著重在 case 之間的轉換

Transition diagrams 範例
* 留意 case 4 與 case 8，的部分，other 會抓到下一個 token 的字元，故抓完後要還回去

實作過程
* 在進行 token 的比對的時候，遵循 "最長比對原則"
* 即使比對到了 final state，仍繼續往下比對，直到進入 dead state 為止
* 同時維護三個變數 (因為有可能遇到，離開 final state 後，過幾步又回到 final state 的情況)
* C: **用來紀錄當前的 state**
* L: 用來紀錄 "上一個遇到的 final state"，**該 final state 的編號**
* P: 用來紀錄 "上一個遇到 final state 時，比對到哪一個字元"，紀錄**該字元的位置** (1-indexed) (由於比對結束後，需要退回去 "上一個遇到 final state 的那個字元" 的位置，供下一個 token 得比對，故需要此變數紀錄)

#### NFA
* NFA (非確定性有限自動機): 利用 Transition diagrams，來檢測某個字串是否符合該 Transition diagrams 所代表之 RE 描述的技術
* NFA 可以被視作是一種 Transition diagrams
* 規則:
* **給定狀態跟輸入，下一個狀態可能有多種組合**
* ex: 給定 Transition function: (1,a) = {1,2} (給定狀態 1 跟輸入 a)，下一個可能的狀態可能是狀態 1 或 2
* **可以有 ε-move**，在不需要任何輸入的情況下，便可跳至其他的 state 中
* ε-closure(s): 某個 state 在不需要任何輸入的情況下，能移動到的 state 集合

* 演算法整體流程: 判斷一個字串是否符合 NFA 的描述
1. 擴展起點能走到的地方
2. 利用下一個遇到的字元進行移動
3. 移動後擴展新的 state 能走到的地方
4. 不斷重複 2, 3，直到所有字元都消耗完畢
5. 判斷最終走到的那些 state 是否跟 Final state 有交集。便可判斷某個字串是否符合 RE 的規則

* 演算法應用舉例
* 在計算上，需要把所有可能的 state 都寫出來，當遇到 Transition diagrams 未指定的行為時，則視作匹配失敗(即不可能走到終點)
* 上圖說明了 "aaba" 在 Transition diagrams 的匹配過程

* 當 Transition diagrams 包含 ε-move 時，在移動每一步後，都需要透過 ε-closure(s) 擴展 state

#### DFA
* DFA (確定性有限自動機): 利用 Transition diagrams，來檢測某個字串是否符合該 Transition diagrams 所代表之 RE 描述的技術
* **給定狀態跟輸入，下一個狀態只可能有一種組合**
* **不可以有 ε-move**

* 演算法整體流程
* 跟 NFA 相比，不需要進行 ε-move，且下一個狀態只可能有一種組合，故每個步驟中只可能有一個可能的 state

## Lexical analyzer generator
功能: 將使用者用 RE 定義的 token，轉換成 lexical analyzer 的 sourse code

### RE to NFA (必考)
* 使用 Thompson’s construction algorithm，便可有系統性的將 RE 轉成 Transition diagrams

針對 ε

針對一般字元

針對 s | t (or 運算)
* 開頭與結尾各新增一個 state，並用 ε-move 連結到 s 跟 t

針對 st (concat 運算)
* 將 s 的結尾與 t 的頭連接在一起

針對 s* (重複0~無限次運算)
* 開頭與結尾各新增一個 state，並用四個 ε-move 連接

舉例: (a|b)*abb

### NFA to DFA (必考)
演算法推演
1. 從 1 出發，1 的 ε-closure 為 {1, 2, 3, 5, 8}，把這個集合重新定義成 A
2. 定義 State A 的下一步
* 執行 move(A, a)，move(A, a)={4, 9}
* {4, 9} 的 ε-closure 為 {2, 3, 4, 5, 7, 8, 9}，因為這個集合之前沒有出現過，把這個集合重新定義成 B
* 執行 move(A, b)，move(A, b)={6}
* {6} 的 ε-closure 為 {2, 3, 5, 6, 7, 8}，因為這個集合之前沒有出現過，把這個集合重新定義成 C。至此，State A 定義完成
3. 定義 State B 的下一步
* 執行 move(B, a)，move(B, a)，move(B, a)={4, 9}
* {4, 9} 的 ε-closure 為 {2, 3, 4, 5, 7, 9}，即回到 State B
* 執行 move(B, b)，move(B, b)，move(B, b)={6, 10}
* {6, 10} 的 ε-closure 為 {2, 3, 5, 6, 7, 8, 10}，因為這個集合之前沒有出現過，把這個集合重新定義成 D。至此，State B 定義完成
4. 定義 State C 的下一步
* 執行 move(C, a)，move(C, a)={4, 9}
* {4, 9} 的ε-closure 為 {4, 9}，即回到 State B
* 執行 move(C, b)，move(C, b)={6}
* {6} 的ε-closure 為 {2, 3, 5, 6, 7, 8}，即回到 State C
5. 定義 State D 的下一步
* 執行 move(D, a)，move(D, a)={4, 9}
* {4, 9} 的ε-closure 為 {4, 9}，即回到 State B
* 執行 move(D, b)，move(D, b)={6, 11}
* {6, 11} 的ε-closure 為 {2, 3, 5, 6, 7, 8, 11}，因為這個集合之前沒有出現過，把這個集合重新定義成 E
6. 定義 State E 的下一步
* 執行 move(E, a)，move(E, a)={4, 9}
* {4, 9} 的ε-closure 為 {4, 9}，即回到 State B
* 執行 move(E, b)，move(E, b)={6}
* {6} 的ε-closure 為 {2, 3, 5, 6, 7, 8}，即回到 State C
7. 全部 State 的下一步都知道了，結束

根據重新定義的結果，畫出 DFA
* 有包含 NFA final state 的那些新 State，便是新的 final state

### Minimizing DFA states (不考)
* 如果有兩個 State，move 的動作完全一致，則可以合併之

# syntax Analysis
* 相較於 Lexical Analyzer，處於主動的角色
* 設計目標:
* 必須要能正確解析錯誤
* 必須能正確的 recover 錯誤發生的過程
* 速度應該要夠快
* error recovery 策略:
* Panic mode: 把發生錯誤的那行 statement 去掉
* error production: 將錯誤情況一併列舉進語法分析中
* global correction: 僅可能的在執行最小改變的狀況下，進行全域變動讓程式變正確
* phrase level: 修改局部內容(ex: 加一個分號)

## Context-Free Grammars (CFG)
* 可以視作類似 RE 的工具，用來描述 "語法"
* RE 能描述的東西，CFG 也可以描述
* 由以下四個元素組成:
* Terminals: 不會再轉換的 Context (小寫字母)
* NonTerminals: 還可以再轉換的 Context (大寫字母、小寫斜體)
* Productions: 轉換關係式
* Start symbol: 起始式 (ex: S)
* derivation step 指的是透過 Productions 重寫當前結果一次，a sequence of derivation step 稱為 derivation
* 當前的 Context 有多個可以展開的項時，有兩種思路可以展開
* leftmost derivation: 每次都挑選最左邊的 NonTerminals 去展開
* rightmost derivation: 每次都挑選最右邊的 NonTerminals 去展開

### Parse Trees
* 使用 "樹" 保留 CFG 展開的過程
* 如果尊崇 leftmost 或 rightmost derivation，則 Parse Trees 保證唯一，且 leftmost 及 rightmost derivation 建構出的 Parse Trees 相同

將展開的過程，轉換成樹

### Push Down Automata (PDA)
* 用於自動化生成 Parse Trees 的程式

ex: 使用 left derivation 建構一棵 parse tree，嘗試匹配 cad

* 從 S 開始，將 S 轉換成 c, A, B
* A 可能有兩種轉換方式(由於是 leftmost，故先挑 A 而非 B 展開)，先將 A 轉換成 a, b -> 匹配失敗，backtrack
* 再將 A 轉換成 a
* 將 B 轉換成 d
* 觀察葉節點 cad，以成功匹配到所求字串，結束

PDA 還有一個未解的難題，也就是當遇到多個 production rule 可選擇時，不知道要選哪個

LL(k) Parsing: 使用 leftmost derivation，且往前偷看 k 個 input，以決定要使用哪個 production rule

### LL(1) Parsing
用於將 CFG 轉成程式

預處理:
* FIRST(): **某條 production rule 不斷推到底後，有可能排在第一個位置的 terminal** 有哪些
* 心法:
1. 直接看
* ex: FIRST(S) = {if}
2. 若是某個 production rule 推到底後，排在第一位的可能是其他 nonTerminal，則該 nonTerminal 擁有的所有 FIRST() 都是這個 production rule 的 FIRST()
ex: FIRST(L) = {if} (因為 L 可以推到 S)
3. 如果推到底後，ε 也可能出現的話也要記
* ex: FIRST(L) = {ε}

* FOLLOW(): **緊跟在這個 Nonterminals 的 terminal 有可能是誰，由其他 production rule 推得**
* 心法:
1. 針對某條 production rule 代表的 nonTernimal，直接看 "->" 右邊出現的該 nonTerminal 中，後一個 terminal 是什麼
* ex: FOLLOW(S) = {else}
2. 針對某條 production rule 代表的 nonTernimal，直接看 "->" 右邊出現的該 nonTerminal 中，後一個 nonTerminal 的 FIRST() 有哪些
3. 若 A → α B，則 FOLLOW(B) 包含所有 FOLLOW(A) 的 terminal (出現在 A 後面的 terminal 也會出現在 B) (α 代表一堆任意數量的 Terminal 與 nonterminal)
* ex: FOLLOW(E) = {else}
4. 若 A → α B β 且 β 可能變成 ε，則 FOLLOW(B) 包含所有 FOLLOW(A) 的 terminal (出現在 A 後面的 terminal 也會出現在 B)
5. ε 也可能出現的話不需要記
6. 如果這個 Nonterminals 是 start state，則多記一個 "$" 符號
* ex: FOLLOW(S) = {$}

#### Recursive Descent Parsing
根據 FIRST() 跟 FOLLOW()，直接推出程式碼

match function
* 用來配對一個 terminal

nonternimal 寫法
* 假設 First(L) = {IF, BEGIN, PRINT, ε}
* 假設 Follow(L) = {end}
* 針對某個 nonterminal 的函式規則:
1. 若是某個 terminal 存在於 該 nonterminal 的 FIRST() 中，則新增 "case 該terminal"，並在後面跟著對應的 CFG
* ex: case PRINT: S(); match(SEMI);L();break;
3. 若是該 nonterminal 包含 ε，則針對存在於該 nonterminal Follow() 中的 terminal，新增"case 該terminal"，並在後面跟著對應的 CFG
* ex: case END: break;

#### Table-Driven Predictive Parsing (必考)
根據 FIRST() 跟 FOLLOW()，建立 Parsing table

建立規則
1. Parsing table 的左邊放 Nonterminals，上面放 terminal，紀錄的是 "當 Nonterminals 遇到 terminal 時，該怎麼轉換"
2. 對於每條 grammer A -> ...
* 若某個 terminal 在 First(A) 中，table[A, 該 terminal] = 該 grammer
* 若 ε 在 First(A) 中，table[A, follow(A)中的 terminal] = 該 grammer ($ 也要)

parsing table 範例:

有了 Parsing table 後，便可以開始匹配 input
* Matched: 當前匹配成功的部分
* Stack: 初始化為 start state + $
* Input: 想要匹配的字串
* 每一步的動作中
* 當 Stack 的 Top 是 Nonterminals 時，利用 parsing table 轉換 Stack 中的 grammers
* 當 Stack 的 Top 是 terminal 時，進行 match 的動作

### ambiguous grammers
某些 CFG 可能導致建構出來的 parse tree 不只一種

例如:

解決方法為
1. 重寫整個 grammer
2. 新增一些額外的限制規則

### left recursion
left recursion 會導致 LL(1) Parsing 失敗

例如
A -> A α | β 在嘗試匹配 βααα 時，不知道要選 A α 還是 β 好

解決方法: 新增一個 nonternimal，將原本的 grammer 等價轉換

ex:

注意: left recursion 也可能是非直接的
* 將 A -> Sd 替換成 A -> Aad | bd 時，才出現 left recursion

### left factoring
left factoring 會導致 LL(1) Parsing 失敗

例如
A -> α β1
A -> α β2

這時候會不知道要選哪一條 statement

解決方法: 新增一個 nonternimal A'，將原本的 grammer 等價轉換

ex:

### error recovery
發生匹配失敗的情況時的處理方式

預處理:
* 把所有在 Follow(A) 中的 token，對應於 parsing table 中的位置設成 sync (若該位置不為空)

處理邏輯:
* 若是 Stack 除了 $ 外只剩一個元素，則 pop input
* 若是遇到了 "synch" 的情況，則將一個 token 從 Stack 中移除
* 若是 Stack 跟 input 的 terminals 不相同，則將一個 token 從 Stack 中移除

# Semantic Analysis
## SDD (syntax-directed definition)
* syntax-directed definition 是一種 context-free grammer，但對於每個 grammar symbol，都新增一些 semantic attributes
* 例如 A 是 grammar symbol，a 是 semantic attributes，則可以寫成 A.a
* semantic attributes 又分成兩類
* synthesized attribute: 該屬性的值由其 parent 或是 siblings 得到
* inherited attribute: 該屬性的值由其 chuld 得到
* Terminals 不可以包含 inherited attribute
* 對於 context-free grammer 中的每條 production rule，都可包含數個 semantic rules
* F.val = digit.lexval 指的是將 digit 實際的數值，賦值給 F.val

### Annotated Parse Trees
* 包含 semantic attributes 的 parse tree 又被稱為 Annotated Parse Trees

#### 構築
1. 畫出一般的 Parse Trees
2. 根據 syntax-directed definition 的那張 "production 跟 semantic rules 對應關係" 的表格，計算出所有 grammar symbol 的 semantic attributes
* dependency: 在計算某些 grammar symbol 的 semantic attributes 前，可能需要先計算其他 grammar symbol 的 semantic attributes
* 計算 E.val 前，需先計算 E1.val 跟 T.val

範例:

#### Dependency Graphs
* 在 Annotated Parse Trees 上，進一步使用箭頭描述 semantic attributes 的依賴關係
* 當某個 semantic attributes A 需要另一個 semantic attributes B 才能計算時，我們稱 A depend on B

* 數字代表順序

## Syntax-directed translation scheme (SDT)
與 SDD 的唯一差別是，會指定 semantic attributes 用到的時機 (用大括號指明)

ex:
* 在處理完 T 後，處理 R 之前，便會立刻執行 {R.i := T.nptr}
* 在處理完 R 後，結束之前，便會立刻執行 {E.nptr :=R.s}

### 程式實作 (Top-Down Translators) --- 以 ANTLR 作為範例
* 若今天要以 ANTLR 來實作以下的 cfg
* 程式實作
* {ids.in:=type.t}: 將 type.t 作為參數，傳入 ids 中
* {declare.flag=ids.flag}: flag 將作為 declare 的回傳值
* {type.t:=1}: 在 type 中，使 t=1
* {type.t:=2}: 在 type 中，使 t=2
* {addSymtab(id.entry, ids.in)}: 使用 JAVA 的 HashMap.put() 來實現

## abstract syntax tree
* 是編譯器後端所需的中心資料結構，可以在 parsing 的過程中順便建立
* 省略了後端用不到的資訊
* 左邊為 Parse Trees
* 右邊為 abstract syntax tree
* 中間節點為 operator
* 葉節點為變數或常數
* abstract syntax tree api
* mknode(op, left, right)
* 創造一個 operator 為 op 的 abstract syntax tree 中間節點，並使其分別指向 left 跟 right 兩個 節點
* mkleaf(id, entry)
* 創造一個葉節點，用來儲存 id 的值是多少 (entry 是一個指向 symbol table 的指標)
* mkleaf(num, val)
* 創造一個葉節點，用來儲存 num 的值是多少

ex:
* 像這樣利用 SDT 語法，便可在 parsing 的過程中建立 abstract syntax tree

## type checking
* 每個 ID (變數) 都有一個 semantic attributes "type"
* 透過 semantic attributes，便可檢查 type 在操作上是否有不合法之處
* 此範例負責檢查進行 mod 操作的兩個變數，是否都是 int 型態

# intermediate code generator
## Three-Address Code
* 這種程式可以被視為轉成組合語言之前的前置語言
* Three-Address code 包含兩個重要觀念
* Address: 可以是變數 (ex: a)、常數 (ex: 3.14)、temp (ex: t1)三者之一
* instruction: 一條指令中，等號右邊最多只會包含一個 oprand
* 當原本的程式碼中包含多個運算的 statement 時，Three-Address Code 會將其拆開
* ex: a=b*c+d 拆成
* t1=b*c
* t2=t1+d
* 可以透過 parsing 時， 來順便產生，讓接下來的後端能夠使用

### Three-Address Code 儲存方式
#### Quadruples
* 每個 row 都是一條 instruction
* 四個欄位分別紀錄 oprand、第一個參數、第二個參數、該指令的計算結果

#### Triples
* 每個 row 都是一條 instruction
* 三個欄位分別紀錄 oprand、第一個參數、第二個參數
* (0) 代表其值來自第 0 條指令的計算結果，其他如 (1)、(2) 等以此類推

#### Indirect Triples
* 相較於 Triples，多了一個欄位，用來紀錄指令的執行順序
* 第 35 條指令的執行結果存在 (0)、第 36 條指令的執行結果存在 (1)...
* 在日後的優化中，編譯器可能會調動指令的執行順序，此時新增的欄位將會非常有用 (只需交換 "紀錄指令的執行順序" 的那個欄位，而不需動到存放 op 的那個 table)
* 交換第 1、2 條指令後的結果

### Static single-assignment form (SSA form)
* 目的是讓 conpiler 在程式碼更動時，能夠清楚識別要改哪些地方
* 在這種格式中，每個變數只能被賦值一次

* 可以觀察到，Three-Address Code 的變數 p 在 SSA form 的格式中，分成 p1, p2, p3

### 利用 syntax-directed definition (SDD) 產生 Three-Address Code
* 名詞解釋
* Temp(): 呼叫後，將會回傳一個獨一無二的暫時變數名 (如 t1, t2 等等)
* newlabel(): 呼叫後，將會回傳一個獨一無二的 label (用於 if, goto 等等)
* S.code: 該 attribute 用來紀錄 S 的 Three-Address Code
* E.addr: 該 attribute 用來紀錄 E 的 Address (即 Three-Address code 中的 Address)
* top.get(id): 取得 id 所代表的實際變數名
* ||: 代表緊跟在後，可以視作 "+"
* 為了能進一步的簡化，我們可以假設 gen() 生成的新 code 會加在原先產生的 code 之後；如此一來，上面的 grammer rule 便可以進一步改寫成

## 其他應用
* Array access: 計算轉成組合語言時所需的 base 跟 bias
* Type Conversion: 當 operator 兩端的變數型態不一樣時，進行型態轉換
* Flow-Control: 生成 label，進行流程控制
* Boolean Expression: 實作 boolean 運算 (如邏輯 and、邏輯 or 等等)

# runtime evironment

## 儲存變數相關資訊
offset: 目的是用來記錄下一個變數，在記憶體中的存放位置
top.put(): 將變數、資料型態、
offset 存至 symbol table 中

## 儲存 struct 相關資訊
* 當儲存 struct 時，會先將原本的 symbol table 跟 offset 用 stack 存起來
* 新配置一個 symbol table，且使 offset = 0
* 像紀錄變數一樣，紀錄 struct 中的元素
* 將新的 symbol table 以及 offset 的資訊存起來，如此一來便可紀錄 struct 的相關資訊

## symbol table 詳細介紹
* 前端通常會將資料寫進 symbol table 中
* 後端通常會存取 symbol table 中的內容，以幫助其產生組合語言
* symbol table 中通常會紀錄
* 變數名稱
* 型態
* 位置

## scope 問題
* 當有兩個變數名稱相同，但層級不同時 (ex: 全域變數與區域變數)，此時需要額外做處理
* 處理方式:
* 每一個 struct block 都包含一個 symbol table，用來紀錄這個區域中宣告的變數
* 先看最裡面的 struct block，如果找不到，再看外一層的 struct block，以此類推

實作:
* 每創建一個 symbol table 時，會有一個指標 prev，指向上一個 symbol table
* 對新的 symbol table 進行正常的寫入操作
* 遇到 scope 問題時，便可以先檢查當前的 symbol table，若找不到便可透過 prev 指標來檢查外一層的 symbol table

# Code generator
## controll flow graph (必考)
原本的 three address code，不適合分析與優化，故需將原程式進一步轉成 controll flow graph
* 一個 controll flow graph 可能包含許多 basis graph
* 每一個 basis graph 一定是 "single entry, single exit"

### 決定 basis block
* 首先，找出每個 basis block 的 leader
* 所有指令的第一道指令
* jump 指令的 target
* 緊跟在 jump 指令之後的指令
* 畫出程式執行流程，在不同的 basis block 間的跳轉關係


## Call Graph
描述了不同 fucntion call 之間的關係

## Next-Use information
* 若在一個 basis block 中，有一個變數 x 在第 i 行被賦值，且被第 j 行使用前，都沒有被重新賦值，則稱 "a_{i} is live at j"
* 第 i 行一定要有該變數的賦值操作
* 第 j 行一定要有該變數的使用操作

舉例
* 變數 a 在第 1 行被賦值，且被第 3 行使用前，都沒有被重新賦值，則稱 "a_{1} is live at 3"

## code generator
* 一切操作都是在同一個 block 進行的，跳至不同 block 時，用來紀錄的 descriptor 接會刷新
* code generator 需要持續追蹤哪個變數在哪個 register 中，以避免不必要的 load/store 操作
* Redister descriptor: 紀錄 register 目前存放的變數
* Address descriptor: 紀錄變數最新的值放在哪裡 (可以連結 symbol table)
* getReg(instruction): 輸入給定一條 Instruction，選擇並分配適當的 register 給該指令會用到的變數 (需要查看 Redister descriptor、Address description、其他訊息來決定)
* load 原則: 當變數需要被用到，但沒有被 Redister descriptor 紀錄時
* LD R, x:
* 使得 Redister descriptor 中的 register R 只包含 x
* 將 register R 視作額外的 address，交由 Address descriptor 紀錄
* store 原則: 當變數離開某個 basis block 時還活著，需要把其值存起來
* ST x, R:
* 使 Address descriptor 紀錄變數 x 自己的記憶體位址

ex:
* 算術運算操作:
* 初始化時，所有 register 都沒有在使用，各變數都存在自己的 address 上
* t=a-b:
* 呼叫 getReg()，該 api 告訴我們各變數分配的 register 是誰，a=>R1, b=>R2, t=>R2
* 由於 a 最新的值不在 register 中，於是生成一條 load 指令，將 a 的值 load 至 r1
* 更新 Redister descriptor: R1 = a
* 更新 Address description: 變數 a 最新的值存在 a 跟 R1
* 變數 b 同理
* 進行減法運算，並將計算結果 t 放在 R2
* 更新 Redister descriptor: R2 = t
* 更新 Address description: 變數 b 最新的值只存在 b
* 更新 Address description: 變數 t 最新的值存在 R2
* 賦值操作
* 此範例的初始化 Redister descriptor 跟 Address descriptor
* a=d
* 呼叫 getReg()，該 api 告訴我們各變數分配的 register 是誰，a, d =>R2
* 由於 d 最新的值不在 register 中，於是生成一條 load 指令，將 d 的值 load 至 r2
* 更新 Redister descriptor: R2 = d
* 進行賦值運算，更新 Redister descriptor: R2 = a, d
* 更新 Address description: 變數 a 最新的值只存在 R2
* 儲存操作
* 此範例的初始化 Redister descriptor 跟 Address descriptor
* 當 Exit the basic block 時
* 由於變數 a 跟 d 最新的值不在 Address 中，故將 a 最新的變數值存在 Address a，d 最新的變數值存在 Address d

### getReg(instruction) 邏輯
1. 若某變數已經在 Redister descriptor 中了，則直接沿用
2. 若某變數不在 Redister descriptor 中，但 Redister descriptor 還有空閒空間，則將該空閒空間配置出去
3. 若 Redister descriptor 沒有空閒空間配置出去，則必須移除其中一個已經在 Redister descriptor 中的變數
1. 若移除的變數，在其他地方還保有最新的值的話，則直接移除
2. 若移除的變數本來這輪就會更新，則直接移除
3. 若移除的變數，在未來不在被使用，則直接移除
4. 先把要移除的變數用 Store 指令存起來，接著再移除

### graph coloring
* register 的分配是個抽象的難題，但可以轉成 graph coloring 方便進一步計算
* 可以將各變數存活時間畫出來
*　接著畫圖，點為各變數，若兩變數存活時間有重合，則建立一條邊；接著為每個點著色，顏色即代表分配給該變數的 register ID

## Data Dependence
* 目的是要確認兩條 instruction 是否能對調
* 若調整之後，Data Dependence 不變，則對調操作合法
* **若程式碼包含 if-else 等條件判斷，則所有可能的情況都要確認過**
### Flow dependence
* **先定義再使用**
* 語法展示

### Anti-dependence
* **先使用再(重新)定義**
* 語法展示

### Output dependence
* **連續兩次重新定義**
* 語法展示

### 範例