三地址码简介
三地址碼簡介
三地址碼（Three Address Code）是一種最常用的中間語言，編譯器可以通過它來改進代碼轉換效率。每個三地址碼指令，都可以被分解為一個四元組（4-tuple）的形式：（運算符，操作數1，操作數2，結果）。由于每個陳述都包含了三個變量，即每條指令最多有三個操作數，所以它被稱為三地址碼。
編譯器
編譯器（compiler），是一種計算機程序，它會將用某種編程語言寫成的源代碼（原始語言），轉換成另一種編程語言（目標語言）。
它主要的目的是將便于人編寫、閱讀、維護的高級計算機語言所寫作的源代碼程序，翻譯為計算機能解讀、運行的低階機器語言的程序，也就是可執行文件。編譯器將原始程序（source program）作為輸入，翻譯產生使用目標語言（target language）的等價程序。源代碼一般為高級語言（High-level language），如Pascal、C、C++、C# 、Java等，而目標語言則是匯編語言或目標機器的目標代碼（Object code），有時也稱作機器代碼（Machine code）。
一個現代編譯器的主要工作流程要通常要經過預處理、編譯、匯編、鏈接等步驟。關于編譯器的工作流程的介紹，可參考：從C源代碼到可執行文件的四個過程：預處理、編譯、匯編、鏈接
中間語言
中間語言（Intermediate language），有時也稱為中間表示（Intermediate Rrepresentation，IR）在計算機科學中，是指一種應用于抽象機器（abstract machine）的編程語言，它設計的目的，是用來幫助我們分析計算機程序。這個術語源自于編譯器，在編譯器將源代碼編譯為目的碼的過程中，會先將源代碼轉換為一個或多個的中間表述，以方便編譯器進行最佳化，并最終產生出目的機器的機器語言。通常，中間語言的設計與一般的機器語言有三個不同之處：
- 每個指令代表僅有一個基本的操作。舉例來說，在微處理器中出現的 shift-add 定址模式在中間語言不會出現。
- 指令集內可能不會包含控制流程的資訊。
- 暫存器可用的數量可能會很大，甚至沒有限制。
最常見的中間語言表述形式，是三位址碼（Three address code），常簡稱為 TAC 或 3AC。
這個術語也同時用來代稱一些作為中間層的語言，有些高級語言不會輸出為機器語言，它們僅會輸出這種中間語言，而這些中間語言則會像一般語言一樣，提交給編譯器，編譯為機器語言。這通常被用于讓最佳化的過程更簡單，也用于增進可移植性的能力，改進移植的方式則是利用中間語言的編譯器，可以編譯出許多中央處理器及操作系統可使用的機器碼，例如C語言。中間語言的復雜度，通常介于高階語言及低級語言之間，例如匯編語言。
四元式
四元式主要由四部分組成：OP，arg1，arg2，result，即（操作符，操作數1，操作數2，結果），
其中，OP是運算符，arg1，arg2分別是第一和第二個運算對象，result是編譯程序為存放中間運算結果而引進的變量，常稱為臨時變量。當OP是一目運算時，常常將運算對象定義為arg1。
例如 X = a*b+c/d 的四元式序列：
- 四元式出現的順序和語法成份的計值順序相一致。
- 四元式之間的聯系是通過臨時變量實現的，這樣易于調整和變動四元式。
- 便于優化處理。
三地址碼
三地址代碼是四元式的另一種表示形式。每個三地址碼指令，都可以被分解為一個四元式（4-tuple）。因為每個陳述都包含了三個變量，所以它被稱為三地址碼。
上面例子 X = a*b+c/d 的三地址序列：
常用的三地址碼（三地址碼形式和四元組形式）
| 1 | 賦值指令 | x = y op zx = op y | op為運算符 |
| 2 | 復制指令 | x = y | |
| 3 | 條件跳轉 | if x relop y goto n | relop為關系運算符 |
| 4 | 非條件跳轉 | goto n | 跳轉到地址n的指令 |
| 5 | 參數傳遞 | param x | 將x設置為參數 |
| 6 | 過程調用 | call p,n | p為過程的名字n為過程的參數的個數 |
| 7 | 過程返回 | return x | |
| 8 | 數組引用 | x=y[i] | i為數組的偏移地址，而不是下標 |
| 9 | 數組賦值 | x[i]=y | |
| 10 | 地址及指針操作 | x=&yx=*y *x=y |
將上表的三地址指令用四元式表示
| x = op y | ( op , y , _ , x) |
| x = y | ( = , y , _ , x) |
| if x relop y goto n | ( relop , x , y , n) |
| goto n | ( goto , _ , _ , n) |
| param x | ( param , _ , _ , x) |
| call p,n | ( call , p , n , _) |
| return x | ( return , _ , _ , x) |
| x=y[i] | ( =[] , y , i , x) ps: y為基地址，i為偏移地址 |
| x[i]=y | ( []= , y , x , i) |
| x=&y | ( & , y , _ , x) |
| x=*y | ( =* , y , _ , x) |
| *x=y | ( *= , y , _ , x) |
每一個指令只有一個操作符，那么只完成一個動作，這樣看來，三地址指令序列唯一確定了運算完成的順序。
中間代碼生成的例子
while a<b doif c<5 thenwhile x>y doz=x+1;else x=y;100到112為指令的編碼，從100到112順序執行。
| 101: ( j , -, -, 112 ) | 該指令為無條件指令，跳轉到112 |
| 102: ( j<, c, 5, 104 ) | 如果c<5 ,那么跳轉到104指令，否則繼續執行103指令 |
| 103: ( j , -, - , 110 ) | 該指令為無條件指令，跳轉到110 |
| 104: ( j>, x, y, 106 ) | 如果x>y ,那么跳轉到106指令，否則繼續執行105指令 |
| 105: ( j , -, - , 100 ) | 該指令為無條件指令，跳轉到100 |
| 106: ( + , x, 1 , t1 ) | x+1的值賦值給t1 |
| 107: ( = , t1, - , z ) | t1的值賦值給z，106和107完成了一條語句 |
| 108: ( j , -, - , 104 ) | 該指令為無條件指令，跳轉到104 |
| 109: ( j , -, - , 100 ) | 該指令為無條件指令，跳轉到100 |
| 110: (= , y, - , x ) | 把y賦值給x，然后執行111指令 |
| 111: ( j , -, - , 100 ) | 該指令為無條件指令，跳轉到100 |
| 112: | 結束 |
中間表示IR的演變歷史
計算機科學家提出三地址代碼的理由如下：三地址代碼是一種線性IR。由于輸入源程序及輸出目標程序都是線性的，因此，線性IR有著其他形式無法比擬的優勢。另外，相對于其他表示形式而言，程序員對于線性表示形式通常會有一種莫名的親切感，編譯器設計者當然也不例外。早期編譯器設計者往往都是匯編語言程序設計的高手，可以非常自然、流暢地閱讀線性的三地址代碼形式。同時，線性表示形式也會降低輸入輸出的實現難度。隨著編譯器"端"、"遍"等概念的出現，IR已經不僅僅是一種存儲在內存中的數據結構。有時它也需要以文件形式轉存輸出，作為接口供其他系統讀取使用。
那么，一定有讀者會心存疑問：為什么將其設計為"三地址"的形式呢？實際上，這是計算機科學家經過多年實踐探索后才得到共識的。三地址代碼并不是唯一的線性IR，只能說是最為常見的而已。在編譯技術領域，二地址代碼、單地址代碼（即棧式機代碼）都曾出現過，也曾在某些應用領域盛行一時，尤其是單地址代碼。
二地址代碼比較簡單，就是選擇其中一個對象同時充當運算分量與目標操作數。在早期，二地址代碼主要就是著眼于x86機器而提出的。不過，實踐證明，這只是人們的一廂情愿而已，即使是針對x86機器，二地址的優勢也并不明顯，它反而可能會給編譯器帶來一定的麻煩，所以這種表示形式已經逐步被淘汰了。
然而，單地址代碼的情況則截然不同了，在現代編譯器設計中，單地址代碼也是應用比較廣泛的一種IR。尤其是近年隨著混合語言的日漸壯大，單地址代碼也重新進入了人們的視野。由于執行單地址代碼程序的棧式機架構相對比較簡單，可以非常方便地構造相關的解釋器或虛擬機，所以單地址代碼深受混合語言設計者的歡迎。讀者熟悉的Java字節碼、.NET的IL都是單地址代碼。棧式機或者單地址代碼與常見的x86體系結構相差甚遠，可能讀者所知不多。不過，單地址代碼還是一種比較有意思的表示形式，因此，筆者想通過一個簡單的實例讓讀者對單地址代碼有所了解。
三地址代碼是在二地址代碼的基礎上發展而來的。二地址代碼的不足之處在于它通常會給其中一個源操作分量帶來一定副作用。當然，這種設計的靈感最初是來源于x86指令系統的，但是卻忘了一個重要的區別：x86指令中往往都是以寄存器作為暫存空間的。而暫存空間對于二地址代碼卻是一個棘手的問題。為了解決二地址代碼的不足，人們提出了一個對源操作分量不產生任何副作用的形式，那就是三地址代碼。也就是說，在一行三地址代碼中，任何運算都不會改變兩個源操作分量。這是三地址代碼與二地址代碼的主要區別。這個特性是非常重要的，它將使得編譯器更自由地復用名字與值，不必考慮代碼帶來的副作用。
一般來說，三地址代碼的大多數操作都是由四項組成，即一個操作碼和三個地址。不過，三地址代碼同樣存在級別差異。隨著語言復雜性的提高，在現代編譯器設計中，三地址代碼的級別概念顯得尤其重要。根據編譯器設計的需要，有些三地址代碼可能近似于源語言，而有些三地址代碼則更接近于目標語言。當然，級別主要就是取決于三地址代碼的操作符及操作分量的復雜性。下面，筆者就操作符及操作分量這兩個話題來討論三地址代碼。
操作符是用于標識三地址代碼操作含義的元素。根據源語言、目標語言的特點，三地址代碼操作符的集合以及抽象程度是各不相同的。其中，抽象程度是三地址代碼設計中的重要因素之一。一般而言，三地址代碼將包含大部分低級操作，即目標機所支持的指令。不過，這并不意味著三地址代碼就是機器指令系統的映射。設計者應該從便于后端處理的角度考慮，盡可能地發揮三地址代碼作為中間語言的作用。
Ref：
https://zh.m.wikipedia.org/wiki/%E4%B8%89%E4%BD%8D%E5%9D%80%E7%A2%BC
https://baike.baidu.com/item/%E4%B8%89%E5%9C%B0%E5%9D%80%E7%A0%81/23121007
https://blog.csdn.net/starter_____/article/details/90146048
https://jishuin.proginn.com/p/763bfbd55cbd
https://book.51cto.com/art/201206/340208.htm
總結
- 上一篇： 沂源醉美双泉酒庄生产什么酒？
- 下一篇： 1万块余额宝一天多少