PAAG（ParallelArrayArchitectureGPU）是西安郵電大學自主開發(fā)的高性能圖形、圖像處理器[1]。為了給PAAG處理器實現(xiàn)并行C語言編譯系統(tǒng)，采用移植已有的并行C語言編譯器CPCC[2]的方法。CPCC產(chǎn)生的是針對堆棧機器的偽代碼（其作用相當于目標機器的匯編碼），堆棧機代碼是一種單地址碼[3]，但目標處理器PAAG的匯編指令是三地址形式。

　　摘要：為了便于代碼優(yōu)化及指令生成，在并行C語言編譯器CPCC（ConcordiaParallelCCompiler）將源程序的抽象語法樹（AbstractSyntaxTree，AST）轉(zhuǎn)換成目標機PAAG（ParallelArrayArchitectureGPU）處理器的匯編代碼時，采用了三地址碼作為中間表示形式�；�于CPCCAST的結(jié)構(gòu)特點，將AST到三地址碼的轉(zhuǎn)換分為三類，即一般表達式的翻譯、布爾表達式的翻譯以及語句的翻譯，并給出了其詳細設計思路及是實現(xiàn)方法。實驗結(jié)果表明，該方案實現(xiàn)了從源碼的抽象語法樹到三地址碼的轉(zhuǎn)換。

　　關(guān)鍵詞：編譯器,中間表示,抽象語法樹,三地址碼

　　為了將CPCC移植到目標機PAAG上，我們以CPCC編譯產(chǎn)生源代碼的AST形式為基礎，將其轉(zhuǎn)換為PAAG的匯編碼。首先將AST轉(zhuǎn)換成一種更接近PAAG匯編碼的線性中間表示形式——三地址碼，再經(jīng)過代碼生成模塊實現(xiàn)從三地址碼到匯編碼的轉(zhuǎn)換。三地址碼不僅在形式上與目標機器的匯編指令集更加接近，從三地址碼生成匯編碼要更容易些；更重要的是，目前有很多成熟的與機器無關(guān)的編譯優(yōu)化技術(shù)都是在程序的三地址碼這種線性中間表示形式上來處理的[4]，在生成三地址碼后，可以利用這些技術(shù)進行與機器無關(guān)的優(yōu)化，以生成更加緊湊高效的代碼，這對于提高編譯器的性能是非常有意義的。

　　本文一共分為四個部分，第一部分和第二部分分別介紹CPCC的中間表示—AST和所要翻譯成的三地址碼及其格式；第三部分介紹從AST到三地址碼的翻譯；第四部分是實驗結(jié)論。

　　1CPCC的AST

　　抽象語法樹（AbstractSyntaxTree，AST）是對被編譯源程序語法分析的圖表示[5]。CPCC的AST由4類節(jié)點構(gòu)成，分別是SYMBOL、LINK、VALUE和STMT節(jié)點。其中SYMBOL節(jié)點用來描述源程序中聲明部分出現(xiàn)的標識符；以VALUE節(jié)點為根的子樹描述源程序中對應的表達式，通常它可以求得一個值；LINK節(jié)點用來描述SYMBOL節(jié)點以及VALUE節(jié)點的類型；以STMT節(jié)點為根的子樹表示源程序中出現(xiàn)的由各種表達式按照某種語法規(guī)則組成的語句，如各種控制流語句（if_else等）。各個節(jié)點連接起來形成的AST實現(xiàn)對源程序的語法描述。

　　2三地址碼

　　三地址碼包含一個操作符，兩個源操作數(shù)跟一個目的操作數(shù)。目的操作數(shù)用來存放源操作數(shù)經(jīng)過操作符對應操作處理后生成的結(jié)果，或者對于轉(zhuǎn)移操作，目的操作數(shù)代表要轉(zhuǎn)移的目的地址。三地址碼中源操作數(shù)的數(shù)目可以小于兩個[3-6]。所謂“地址”就是三地址碼的操作數(shù)，它可以是源碼中變量的名字；可以是一個整型常量；也可以是一個帶下標的t，如t3。這些t表示由編譯器計算產(chǎn)生的臨時變量。

　　在本文出現(xiàn)的三地址碼主要有以下形式：

　　3AST到三地址碼的翻譯

　　CPCC的AST將C程序分為兩種語法范疇：表達式（對應AST中以VALUE節(jié)點為根的子樹）以及由表達式組成的語句（對應AST中以STMT節(jié)點為根的子樹）。因此我們很自然的將程序的翻譯分為兩類：表達式的翻譯和語句的翻譯。但是，當表達式作為決定程序流向的判斷條件時，如在關(guān)鍵詞while后充當判斷循環(huán)結(jié)束的條件，其作用只是實現(xiàn)程序的跳轉(zhuǎn)，此時它的翻譯又不同于在其它地方的處理，這類通過判斷真假來控制程序流向的表達式稱為布爾表達式。因此我們將表達式的翻譯又分為一般表達式的翻譯和布爾表達式的翻譯。下面將分別闡述對一般表達式、布爾表達式和語句等三類翻譯的設計方案。

　　3.1一般表達式的翻譯

　　一般表達式能夠計算出一個值，對表達式的翻譯應該完成兩個功能：1生成表示該表達式語義動作的三地址碼；2返回表達式的計算結(jié)果，該結(jié)果可能被用于更高一層表達式的運算。這種處理由intspit_expr（VALUE*v，intrlv）函數(shù)完成。參數(shù)VALUE類型指針v代表要處理的表達式；參數(shù)rlv表示表達式是被當做左值還是右值處理的。spit_expr（）函數(shù)的流程圖如圖1所示（圖中v→code代表表達式的類型，逗號表達式中相鄰兩個子表達式對應的VALUE節(jié)點用next指針相連）。

　　一般表達式中最難翻譯的是數(shù)組引用的翻譯，在此我們以數(shù)組引用的翻譯來說明處理的方法。要訪問（引用）某個數(shù)組元素，就要確定該元素的地址。如何由AST來獲得數(shù)組的起始地址和偏移量，進而計算出該元素的絕對地址是問題的關(guān)鍵。首先來看數(shù)組引用在CPCC中的AST表示，以三維數(shù)組為例說明。已知整型數(shù)組a[2][2][3]和表達式b=a[1][0][2]，該表達式在CPCC中的AST如圖2所示。

　　圖中V_ARRAY_ACCESS類型節(jié)點的size字段記錄該維上一個單位的大小是數(shù)組類型大小的倍數(shù)。如圖中跟a相連的V_ARRAY_ACCESS節(jié)點的size值是6，表示該層上一個單位的大小等于6個整型的大小。expr2指針對應的VALUE節(jié)點的值與size之積表示該維上地址的偏移量，因6*1+3*0+1*2即為總的偏移量，總偏移量乘以數(shù)組類型對應的字節(jié)數(shù)就是偏移量的字節(jié)數(shù)。其中數(shù)組類型的字節(jié)數(shù)由連接最上層V_ARRAY_ACCESS節(jié)點的LINK節(jié)點的select.s.noun字段得出。數(shù)組引用的絕對地址即為數(shù)組基地址（此處為數(shù)組名a）與總偏移量字節(jié)數(shù)之和。圖3為數(shù)組引用翻譯出的三地址碼。3.2布爾表達式的翻譯

　　在CPCC中布爾表達式的形式化描述為：

　　產(chǎn)生跳轉(zhuǎn)三地址碼時還不能確定要跳轉(zhuǎn)到哪里，翻譯時需要先記錄下這兩條跳轉(zhuǎn)三地址碼，當生成跳轉(zhuǎn)目的對應的程序段時，將該程序段第一條三地址碼的索引號（生成的三地址碼是從零號地址開始順序存放的）回填（Backpatch）至跳轉(zhuǎn)三地址碼要跳轉(zhuǎn)的目的操作數(shù)中去。從布爾表達式的形式化描述可以看出布爾表達式是可以遞歸定義的，如B→B1‖B2，因此在一個復合布爾表達式中會存在多條跳轉(zhuǎn)三地址碼跳轉(zhuǎn)到同一目的地址的情況。為了一次回填多條具有相同目的地址的跳轉(zhuǎn)三地址碼，將返回值設計為含有兩個鏈表的結(jié)構(gòu)體[7]。返回值的結(jié)構(gòu)體定義為：

　　結(jié)構(gòu)體中data字段記錄跳轉(zhuǎn)三地址碼的索引號。假設當整個復合布爾表達式為假時，將要執(zhí)行程序的第一條三地址碼序號為F；為真時，將要執(zhí)行的第一條三地址碼的序號為T。那么falselist指向的鏈表記錄了復合表達式對應三地址碼中所有跳轉(zhuǎn)到F的三地址碼的索引號；同理truelist指向的鏈表記錄了所有跳轉(zhuǎn)到T的三地址碼的索引號。例如B=B1‖B2&&B3的翻譯如圖4所示，其中B1，B2，B3都為ErelE形式。

　　3.3語句的翻譯

　　語句的翻譯與布爾表達式的翻譯是不可分割的，下面是CPCC中幾種語句的形式化定義：

　　其中S為語句，B為布爾表達式，E為表達式，定義中允許語句的嵌套。

　　常見的分支和循環(huán)語句翻譯產(chǎn)生三地址碼的結(jié)構(gòu)舉例如圖6所示：（for，while，if-else）。

　　圖（a）中從B.code代碼塊的“真”出發(fā)的箭頭指向代碼塊S1表示當布爾表達式B為真時，程序?qū)��?zhí)行S1的第一條三地址碼。同理，從“假”出發(fā)和break_list合并的箭頭指向整個for循環(huán)之后，表示當B為假時，或遇到break語句時程序跳出循環(huán)。其中break_list表示S1中所有break語句對應跳轉(zhuǎn)代碼組成的鏈表；continue_list跟s1_nextlist發(fā)出的箭頭指向E2.code代碼段表示在執(zhí)行完s1或者遇到continue語句時，程序?qū)��?zhí)行E2的第一條三地址碼。類似break_list，continue_list是continue語句對應跳轉(zhuǎn)代碼組成的鏈表；goto連接的箭頭表示程序要跳轉(zhuǎn)到測試條件B.code處。圖（b）圖（c）的解釋類似。

　　語句的翻譯是由Link*trace_stmt（STMT*s）函數(shù)來完成的。參數(shù)為指向STMT結(jié)構(gòu)體的指針，由于不同類型的語句本身就是程序中各種控制流的抽象表示（如C_IF_ELSE類型語句是S→if（B）S1elseS2分支結(jié)構(gòu)的表示），由語句翻譯出的程序也會出現(xiàn)跳轉(zhuǎn)三地址碼（以下簡稱跳轉(zhuǎn)代碼）。處理所有跳轉(zhuǎn)代碼的方法都是統(tǒng)一的：生成該跳轉(zhuǎn)代碼時先用鏈表記錄下它的索引號，待到跳轉(zhuǎn)目的對應的第一條三地址碼生成前，用next_index（表示三地址碼索引號的全局靜態(tài)變量，每生成一條三地址碼后其值加一）來回填對應的跳轉(zhuǎn)代碼。

　　注意，S生成的一部分跳轉(zhuǎn)代碼的跳轉(zhuǎn)目的在S內(nèi)部，此種情況下，一旦生成跳轉(zhuǎn)目的程序段，便用其第一條三地址碼的索引號回填對應它的跳轉(zhuǎn)代碼；另一部分跳轉(zhuǎn)代碼的跳轉(zhuǎn)目的在整個S語句之后，包括由S中包含的break語句生成的跳轉(zhuǎn)代碼，這時將所有以S語句后第一條三地址碼為跳轉(zhuǎn)目的的跳轉(zhuǎn)代碼構(gòu)成一條Link型的鏈表，稱該鏈表為s_nextlist，作為trace_stmt（）函數(shù)的返回值。若S的s_nextlist不為空，且S之后仍有未處理的語句。在處理S的后繼語句前，用next_index回填鏈表s_nextlist。trace_stmt（）函數(shù)的整體流程如圖7所示。

　　跟其他分支循環(huán)語句不同，switch語句的翻譯要更加復雜些，下面來單獨分析switch語句的翻譯過程。圖8為例程中方框中程序?qū)�應的AST。

　　下面是針對圖8中例程和AST對switch語句翻譯的闡述：

　　掃描到SWITCH節(jié)點時，處理switch后的表達式a。接著產(chǎn)生一條無條件跳轉(zhuǎn)代碼用于跳轉(zhuǎn)到test_table處（該跳轉(zhuǎn)代碼的索引為1，記錄在jump2table_list中，該跳轉(zhuǎn)代碼在產(chǎn)生test_table時被回填），test_table對應的代碼用于測試應該執(zhí)行哪個case分支。

　　遇到case0：對應的節(jié)點，先將常量0壓入隊列case_queue，再將下一條三地址碼的索引號（例子中為2）壓入case_queue中，接著為表達式b=0生成三地址碼，之后的break語句產(chǎn)生一條無條件跳轉(zhuǎn)代碼，建立break_list鏈表記錄下它的索引號（為3）。break_list記錄所有跳出switch結(jié)構(gòu)的跳轉(zhuǎn)代碼。之后處理下面case1：b=0；break；與上面過程完全相同，即常量1及下一條代碼的索引號4進入隊列case_queue中。break_list記錄索引號為5的無條件跳轉(zhuǎn)代碼，對應該case后的break語句。然后處理default對應的語句：先用default_index記錄下一條代碼的索引（為6），即default對應的第一條代碼。再為default后的表達式b=-1生成三地址碼，最后產(chǎn)生一條無條件跳轉(zhuǎn)代碼（索引號為8），將其記錄在break_list中。

　　此后，生成test_table代碼段：先將第一條代碼的索引號回填到jump2tabel_list里記錄的跳轉(zhuǎn)代碼中。接著從隊列case_queue拿出兩個元素0和2，產(chǎn)生一條條件跳轉(zhuǎn)指令2=aif==goto0，之后又從case_queue讀出兩個值1和4，產(chǎn)生4=aif==goto1，此時case_queue為空，讀default_index，產(chǎn)生6=goto。test_table生成完畢。

　　最后用下一條代碼索引號（為12）來回填break_list鏈表中的跳轉(zhuǎn)代碼。

　　圖9是例程中用到的隊列以及鏈表等數(shù)據(jù)結(jié)構(gòu)和對switch結(jié)構(gòu)翻譯的結(jié)果：

　　4實驗結(jié)論

　　以C語言源程序?qū)�應的三地址碼為基礎，結(jié)合PAAG處理器的指令集，很容易實現(xiàn)編譯器代碼生成模塊。至此，整套C語言編

　　譯系統(tǒng)已經(jīng)完成了從C語言源程序到PAAG匯編程序的轉(zhuǎn)換。整個編譯系統(tǒng)對輸入的圖形算法生成的匯編文件，經(jīng)過在PAAG仿真環(huán)境下的調(diào)試和運行后，結(jié)果正確。證明從AST到三地址碼的轉(zhuǎn)換是正確的。

　　參考文獻：

　　[1]李濤，肖靈芝.面向圖形和圖像處理器的輕核陣列機結(jié)構(gòu)[J].西安郵電學院學報，2012，17（3）：41-45.

　　[2]AiKong.ConcordiaParallelC：DesignandImplementation[D].Montréal，Québec，Canada：TheDepartmentofComputerScience，ConcordiaUniversity，2000：43-70.

　　[3]KeithD.Cooper，LindaTorczon.EngineeringaCompiler[M].2ended.MorganKaufmannPublishersInc，2007.

　　[4]AlfredV.Aho，MonicaS.Lam，RaviSethi，JeffreyD.Ullman.CompilersPrinciples，Techniques，andTools[M].2ended.Addison-Wesley，2008.

---

轉(zhuǎn)載請注明來自：http://www.jinnzone.com/jisuanjiwangluolw/28947.html