TW569138B - A method for improving instruction selection efficiency in a DSP/RISC compiler - Google Patents

Description

569138 五、發明說明（1) 發明領域 本發明係有關於一種用以改進數位信號處理器/精簡 才曰集運异編譯裔（DSP/RISC compiler)之指令選擇效能 之方法，以同時得到最佳化執行效能及空間使用率。 相關技術說明

第1圖是一典型編譯器的結構。在第1圖中，該結構包 含一人類可讀取的原始碼11、一編譯器丨2及一目標性目的 碼13。上述編譯器12又包含一前端器2〇〇、一最佳化器 202、一語法處理器204、一圖案表產生器206及一碼產生 器208。如第1圖所示，該前端器2〇〇接收該人類可讀取原 始碼11，例如，使用C、C + +、VB或PASCAL高階語言（這些 可儲存於一如内部記憶體或外部硬碟的儲存元件中）所撰 寫的一原始碼並執行一符號分析。該最佳化器2〇2翻譯該 原始碼11成為一最佳化的中間表述（intermediate representation，IR)。該語法處理器2〇4執行一語法分析 且其執行結果被輸入至一圖案表產生器中，以產生一組圖 案匹配表（pattern matching tables，PMTs)。根據上述 中間表述（IR)及圖案匹配表（PMTs)，執行語義樹圖案的匹 配’以使该碼產生器2 0 8輸出一目的碼1 3。那些熟知此項

技術之人士應了解，該目的碼1 3係如期待的可包括組合語 言碼（assembly code)或二進制碼（binary c〇de)。、’ 口叩 上述中間表述（IR)包含一些基本方塊（basic block)。一個基本方塊係在頂部有一單入口而在底部 單出口的一系列中間指令。每個基本方塊可代表一或更多

569138 五、發明說明（2) 獨立的資料相依圖形，每個圖形包含一或更 t d es)。每個節點大致上代表在—目標機器（未顯示）中 ΪΉ令’可使該目標機器執行-與該指令相關的功 :及料相依圖τ一節點的操作會隨產生的水 =或U 1點（其中如此稱呼該前—節點是因它先於 γ一郎點被執行）中所產生的一變數而定。然而，該 二郎點的操作不隨產生的資料及/或其在下—節點（除非存 在一迴圈使得下一節點會先於前一節點執行）中所產生 一變數而定。 傳統上’該機器獨有的資訊（例如指令特性、指Α延 遲、指令所使用的暫存器數量及型態等等）被嵌入至:譯 器中。因此，在該編譯器12中的最佳化器2〇2係隨機器種 類而定。這個隨機器種類而定的最佳化器2〇2不斷地執行 指令選擇、暫存器分配及指令重組與平行化的工作。下舉 一例子以說明對一語義樹的指令選擇上，習知技術盥本二 明之間的差別。 η ^ 第2圖是一基本方塊例及其利用第1圖的編譯器所操作 的語義樹的圖形。如第2圖所示，本例顯示一具有一獨立 資料相依圖形的基本方塊，該獨立資料相依圖形含一運算 式 pRO = abs(pRl - pR2) + (pR3 - pR4)及它的語義樹，其中， pRO-4係為暫存器。為了完成這個語義樹，該碼產生器208 執行該樹圖案匹配操作。該樹圖案匹配係在暫存器分配操 作之前所執行的自底部往上的指令選擇操作。如第3圖所 示’節點暫存器pR5及pR7先分別選擇一由該圖案表產生器

0697-8165TWF(n);P2002-018;sue.ptd

569138 五、發明說明（3) 所提供的配對圖案（match pattern)來形成，接著，節點 暫存器pR6及pR8利用跟其前一節點暫存器相同的方式來形 成。最後，在節點暫存器pR〇被形成並由該碼產生器2〇8輸 出時完成這個語義樹。然而，像第i圖丨2這樣的一傳統式 編譯器存在著無法同時提供最佳化空間使用率及最佳化執 行效能的問題。在上述情形下，大多會犧牲最佳化空間使 用率。例如，在該最佳化器202中，有二個方案來形成節 點PR6或PR8。第一方案示於第4a圖中，使用一條件式指令 (conditional instruction)及執行時需要6個時脈的一跳 躍指令（jump instruction)。該第一方案產生一2個指令 大小（空間使用率）及一平均4個時脈（執行效能）的結果。 第二方案示於第4b圖中，使用互斥、32次的帶符號位移及 減法運算。該第二方案產生一3個指令大小及一平均3個時 脈的結果。因此，當使用前者來產生最佳化空間使用率 時，它需要如第5a圖所示的11個時脈及7個指令。又，當 Ϊ。用後者來產生最佳化執行效能時，它需要如第讣圖所田示 個時脈及9個指令。如上述，可看到效能與空間使用率 :::谷的。如第6圖所示，它呈現出一種負線性關係（一 = 的直線）並在其左下方（點3處）具有一較佳的 二質而在其右下方（點b處）具有一較差的品質。舉例來 =當-使用者需要-12K大小的空間時’因為 说處理器的是以2n來成長，故該使用去"a日塞四ict, 田 人π 故成便用者必須購買一 16Κ容 ^大小的數位信號處理器’其中，η係為一整數。這個方 式將浪費上述1 6 Κ容量中的1 / 4。该個pq日s κ左# JA/4坆個問題隨著將該編譯器

569138 五、發明說明（4) " -- ^用於廣泛使用的多媒體，尤其是於影像處理用的一數位 佗號處理器/精簡指令集運算系統的發展中，漸漸變的嚴 重。 發明概述 據此’本發明之一目的係提供一種用以改進數位信號 處理器/精簡指令集運算編譯器之指令選擇效能之方法， 以同時獲得最佳化執行效能及空間使用率。 ，本發明提供一種用以改進數位信號處理器/精簡指令 ，運算編譯器（DSP/RISC comp i ler)之指令選擇效能之方 法，其在一使用者所選擇的有限使用空間内決定一最佳化 碼尺寸，藉以同時產生最佳化執行效能及空間使用率。本 ^法，3下列步驟：決定一基本方塊（basic bi〇ck)的一 語義樹（semantic tree);經由參考一組圖案找到所有匹 配=上述語義樹的組合（aU matching c〇[nbinati〇ns); 決定各組合的時脈數（cycle number)及指令長度 (instruction length);根據一預定的時脈數及指令長 度，過濾上述時脈數中，超過該預定的時脈數者與具 3 :寺=數及指令長度中的多餘者；以及從上述過濾後剩下 、、’且a中，選出一組具有最少時脈數的組合做為輸出，當 做所期待的目的碼（〇bject c〇(je)。 較佳實施例之詳細說明 全文中之相同功能元件係以相同參考號代表之。 第7圖是一根據本發明用以改進改進在一數位 理器/精簡指令集運算編譯器（DSP/RISC compiler)w^^

569138 五、發明說明（5) 令選擇效能之方法的流程圖。在第7圖中，該方法 列步驟：決定一基本方塊（basic bl〇ck)的一語義3下 (semantic tree)(S1);經由參考一組圖案找到所有匹配 於上述語義樹的組合（al 1 matching combinations)(S2);決定各組合的時脈數（cycle nuniber·)及指令長度（instructi〇n length)(s3);根 ，定的時脈數及指令長度，過濾、上述時脈數中，超過該預 疋的時脈數者與具有相同時脈數及指令長度中的多餘 (S4^以及從上述過濾後剩下的組合中選出一組具 >、時脈數的組合做為輸出，當做所期待的目的碼（〇叫“七 )。如第7圖所不，當比較本發明與習知的指令選 :寺’後者在沒有尋找所有可能組合以決定最佳的空間的 ^形下完成它的基本方塊的語義樹。對上述相同例子（si) 相；r根ί本發明’其指令選擇邏輯是以第2圖中所示的 相同範例為基礎。 ^ 圖崇中，一組圖案被選取。如第8圖所示，該組 圖案81在郎點暫存器_中具有4種圖案分別為 ^(P^l)、abs(Prl)、pRl+pR2 及州—⑽。符號如 (fbsl )，4’ 2代表需要4時脈數及2指令的一第一絕對值運算 sj同樣地，符號（abs2)，4, 2代表需要4時脈數及2指令 f&對值運算―2。X —加法或減法運算需要1 ::數及1指令。在習知例子中’所示係為只使用該第一 或第一絕對值運算來完成該語義樹。然而，根據本發明， 配置該語義樹可具有如第9圖所示的四種組合91，分別具

569138

五、發明說明（6) 有11時脈數及7指令；9時脈數及9指令； 令；及10時脈數及8指令（S3)。因為最後二數及8指 時脈數及指令，因此捨去一組，如最後且γ具有相同 8指令空間的預定指令長度限制下 述且。合。在考慮 二組合刪除(S4)。剩下來的結合中二上Λ有有9指令的第

abs2的這個結合具有10時脈數，其時脈數：於：=J 數的另一結合，因此輸出具有一absl&abs2這 人傲 為期待的目的碼（S5)。 们、個…合做 用來執行上述步驟的邏輯法則如下： comp_C(v) Ον=Φ for all peP, if p can match v then i/=v+rl (p) ; tf2=v-fi:2 (p)；' for all Cn,±eCn and all C/2rjeC/2 if s ize (C/ifi) +s ize (c/2,j) +s ize (p) then

Cv=insert (Cv, (p , s ize (C〜i) +size (C/Zr j) +s ize (p) , cycle (C/i,i) + cycle (C/2, j) +cycle (p) Ά i2)); return Cv 如上述，該程序副程式名稱為comp_C(v)。Cv是一用 於每個節點v的候選組，開始時設定為空集合（Φ )。P是一

0697-8165TWF(n);P2002-018;sue.ptd 569138 五、發明說明（7) ----- 組預置圖案。p是—所選圖案。是在該組G内從圖案根 部至最左邊節點中的第i個元素而〜A在該組Cv内從圖案 根部至最右邊節點中的第】個元素一限定的記憶體 空間。設定(：νΛ =(圖案名稱（p)、時脈數（cycle)、指令 長度（s 1 ze )、左運算節點（打）、右運算節點（扣）），其 中，C^i代表經由花費η長度大小及m時脈數以結合左節點 及右節點來完成該語義樹上的圖案而完成該組匕中的第i 個元=。得到該組Cv的方式可以不只是一種圖案。因此， 當一節點上的一向量具有一範圍落在所限記憶體空間 (也就是，總指令長度為 sizj(cw HSiZe(c^Hsize(p)W )内的長度大小時，該 向量將被插入至該候選組cv中。上述邏輯（程序副程式）被 遞迴性地執行，直到完成該惟一的根部r運算。例如，如 第1 0圖所不，一具有節點u、V、χ、y及…的語義樹丁分別具 有下列可能的指令選擇組為Cu={(-，1，1，a，b)丨、 、

Cv={(-，l，l，c，d)}、Cx={(absl，5,3，u，Φ)、 (abs2,4,4，u，Φ)}、Cy={(absl，5,3，v，φ)、 (abs2,4,4，v，0)}&Cw={( +，li，7,x，y)、（ +，1Q，8，x，y)、 ( +，9,9，x，y)}。藉由上述最佳化的指令選擇，如第丨1圖所 示’比較在該根部組Cw中的所有候選者，在一區域邊界 (如虛線所示’並非如習知技術中的一直線邊界）限制下， 從底部Cu={(-，1，1，a, b)}及Cv={( —，！，；[，c，d)}經

569138 五、發明說明（8) »

Cx={(absl，5,3，u，φ)}及Cy={(abs2 C:-二(+，1〇, 8, χ’ y)}的一條路徑被輸’：Φ)}至根部 的碼（如第1圖所示的相同結構）。士口此，，亥蝙譯器的目 小下，可達到較習知技術高的執行效能。相同記憶體大 雖然本發明已以一較佳實# 本發明，任何熟知此技術之人：如=，然其並非用 範圍當視後附之申請 /、 _，因此本發明之# 1 明專利軌圍所界定者為準。 保5楚 0697-8165TWF(n);P2002-018;sue.ptd 第12頁 138 圖式簡單說明 圖示之簡單說明 ，讓本發明之上述及其它目的、特徵、 而易見，下文鸫與 炎”、έ此更顯 細說明如； 較貫例，並配合所附圖式，作詳 第1圖是一典型編譯器的結構； =2圖是一基本方塊例及它的語義樹的圖形； 點的ϊ 3Λ是Γ經編譯器分解至第2圖的語義樹上的所有r 的基本方塊例圖形； J所有即 義樹ϊ4/ ®是—具有由編譯器所作的第—種指令選摆的在 我树的部分圖案圖形； 曰7選擇的浯 義抖Ϊ?圖是一具有由編譯器所作的第二種指令選摞的也 義枒的部分圖案圖形； 7選擇的浯 第5a圖是一經第4圖的第一 樹的圖形； 罘種扣令選擇所完成的語義 第5b圖是一經第4b圖的第— 樹的圖形； 幻罘一種乳令選擇所完成的語義 一第2圖的時脈數對空間的曲線圖； 理5| /铲羚：八2 = 士發明用以改進改進在-數位信號處 王為/精簡指令集運算編譯器（ ·、丄 令潠摆外处—士 a 、SP/RISC compiler)中的指 7選擇效能之方法的流程圖； 第8圖是一根據本發明用 組圖案範例； ；第2圖中的基本方塊例的一 第9圖是一根據本發明經第二 義樹的圖形； 罘一種私7選擇所完成的浯

569138 圖式簡單說明 第1 0圖是一在執行本發明上述選擇邏輯後的結果說明 例；及 第11圖是一根據本發明的時脈數對空間的曲線圖。 [符號說明] 1 1 :人類可讀取原始碼 12 :編譯器 13 :目的碼 2 0 0 :前端器 202 :最佳化器 2 0 4 ··語法處理器 206 :圖案表產生器 2 0 8 :碼產生器

0697-8165TWF(n);P2002-018;sue.ptd 第 14 頁

Claims (1)

1. 569138 六、申請專利範圍 1 · 一種用以改進數位信號處理器/精簡指令集運算編 譯器（DSP/RISC compiler)之指令選擇效能之方法，包括 下列步驟： 決疋一基本方塊（basic block)的一語義樹（semantic tree)； 經由參考一組圖案找到所有匹配於上述語義樹的組合 (all matching combinations)； 決定各組合的時脈數（CyCle number)及指令長度 (instruction length)； 根據一預定的時脈數及指令長度，過濾上述時脈數 中’超過該預定的時脈數者與具有相同時脈數及指令長度 中的多餘者；以及 從上述過濾後剩下的組合中，選出一組具有最少時脈 數的組合做為輸出，當做所期待的目的碼（〇bject code) ° 斤2 ·如申請專利範圍第丨項之用以改進數位信號處理器/ 精簡指令集運算編譯器（DSP/RISC c〇mpiler)之指令選^ 效能之方法，其中，該基本方塊係代表一或更多獨立 相依圖形，每一個包含一或更多節點。 / 3·如申請專利範圍第2項之用以改進數位信號 精簡指令集運算編譯器（DSP/RISC c〇mpUer)之指令 效能之方法，其中，該每一個節點代表一指令。7 、 4·如申請專利範圍第丨項之用以改進數位信號 精簡指令集運算編譯器（DSP/RISC coinpiler)之指令選

   0697-8165TWF(n);P2002-018;sue.ptd 第15頁 569138

   六、申請專利範圍 效能之方法，其中，該圖案中的每一個包括一在該頂部的 入口節點及一連接至該入口節點之節點。 5 ·如申請專利範圍第1項之用以改進數位信號處理器/ 精簡指令集運算編譯器（DSp/RISC compiler)之指令選擇 效能之方法’其中，該圖案中的每一個包括一在該頂部的 入口節點及連接至該入口節點之多個節點。 6 ·如申請專利範圍第1項之用以改進數位信號處理器/ 精簡指令集運算編譯器（DSP/RISC compi ier)之指令選擇 效能之方法，其中，該組圖案係為機器相依的。 7 ·如申請專利範圍第1項之用以改進數位信號處理器/ 精簡指令集運算編譯器（DSP/RISC compi ler)之指令選擇 效能之方法，其中，該指令長度係為機器相依的。 ,々%如申請專利範圍第1項之用以改進數位信號處理器/ 精簡心々集運算編譯器（DSP/risc compiler)之指令選擇 $能之方法，纟中，該預定指令長度係由該數位信號處理 裔/精簡指令集運算編譯器的容量來決定。 # 9 ·如申睛專利範圍第丨項之用以改進數位信號處理器/ f =指令集運算編譯器（DSP/RISC compiler)之指令選擇 月b之方法其中’該期待的目的碼係為一組合語言碼。 /笋4 :凊ί利範圍第1項之用以改進數位信號處理器 效^夕W、運算編澤器（DSP/RISC compiler)之指令選擇 效'，方法，其中，該期待的目的碼係為一二進制碼。 /浐t m利範圍第1項之用以改進數位信號處理器 、月θ曰v集運算編譯器（DSP/RISc c〇mpiier)之指令選擇

   〇697.8165TW(n)；P2〇〇2.〇i8;sue>ptd 第16頁 569138 六、申請專利範圍 1 效能之方法，其中，該語義樹匹配係從底部開始執行至完 成該基板方塊配置所在的一單根部為止。 1 2 ·如申請專利範圍第1項之用以改進數位信號處理器 /精簡才曰令集運算編譯器（DSP/risC compiler)之指令選擇 效能之方法，其中，進一步包括使用一最佳化器來配置本 方法。 1 3 ·如申請專利範圍第11項之用以改進數位信號處理

   以輸出該期待的目 的码。 -螞譯器（DSP/RISC compiler)之指令選 —步包括使用一碼產生器來執行本方法

   第17頁