Matrix編譯器中飽和算術指令映射的設計與實現＊

淡孝強，陳躍躍，孫海燕，陽 柳，羅 杰，辛乃軍，王 霽

（國防科學技術大學計算機學院，湖南 長沙410073）

1 引言

當前，DSP芯片在多媒體、信號處理等領域中的應用越來越廣泛，由于嵌入式芯片功耗和成本的限制，DSP芯片對編譯器指令映射的精確性和高效性的要求也越來越高，同時選擇快速、有效、低成本的編譯器開發(fā)平臺也越來越重要。

Matrix是一款面向軟基站的、自主指令集的高性能DSP，Matrix編譯器的開發(fā)平臺是gcc，它是一個開發(fā)運行在不同系統平臺的高效快速的開源的編譯系統。對于特定的目標體系結構，通過移植gcc可以開發(fā)出這個平臺的編譯系統，是一種快速、有效、低成本的方案。

gcc目前只支持基于Fixed－point數據類型飽和算術指令映射。Fixed－point是一種精度介于整數和浮點之間的數據類型，有別于整數類型和浮點類型［1］。由于Matrix指令集的飽和指令是基于整數和浮點的，所以需要移植gcc，使其支持整數和浮點的飽和算術指令的映射。飽和算術指令使得數字信號處理算法更加準確、更加高效，是Matrix指令集中很重要的一種指令。對gcc進行移植，使得在Matrix編譯器支持飽和算術指令的映射。本文對gcc指令映射過程的分析以及實現飽和算術指令映射的思路，對于其他指令映射的實現具有一定的借鑒作用。

本文第2節(jié)介紹了飽和算術的定義和特征；第3節(jié)介紹了gcc中指令映射的一般過程；第4節(jié)給出了飽和算術指令映射的實現過程；第5節(jié)描述了飽和加法指令映射實驗結果；第6節(jié)對全文總結。

2 飽和算術簡介

飽和算術使得一些算法更加準確、更加高效，尤其是在DSP算法中。例如：調整聲量可能導致聲音信號溢出，而飽和算術可以明顯減少對信號的扭曲。把兩個數的補碼形式相加，會導致環(huán)繞現象（wrap－around），這可能會對DSP系統的信噪比造成災難性結果，運用飽和算術則可以避免。

飽和算術運算是一種值被限定在固定范圍內的運算操作，有最大值和最小值［2］。比如飽和加法操作：如果兩個數相加后的結果比最大值要大，那么最終的結果就等于最大值；如果相加后的結果比最小值要小，最終結果就等于最小值；如果相加后的結果在最大值和最小值之間，這就是最終的結果。對于這樣的C語言描述，gcc目前只能完成基于Fixed－point數據類型的映射。因此，在gcc中實現基于整數和浮點類型的飽和算術指令的映射會使得編譯器更加高效。

3 gcc指令映射機制分析

gcc的編譯流程是：詞法分析→語法分析→中間代碼生成→代碼優(yōu)化→代碼生成。詞法分析和語法分析稱之為前端，中間代碼生成和部分優(yōu)化稱之為中端，部分優(yōu)化、機器描述 MD（Machine Description）和代碼生成稱之為后端。

3.1 前端處理過程

在gcc內，前端預處理、詞法分析、語法分析三個過程統稱為解析過程。gcc前端的主要任務是對輸入的C代碼進行解析并記錄有效信息，形成抽象語法樹AST（Abstract Syntax Tree）。解析過程的依據是C標準，C標準在前端的信息可以分為基本詞匯符號和語法規(guī)則兩類。一般以hash表的形式把基本詞匯符號的信息組織起來，供解析過程查詢。語法規(guī)則實際是基本詞匯符號排列組合的規(guī)則，一般體現在語法分析過程中。前端大致分為兩個階段：預處理和詞法分析把輸入代碼轉換成gcc的內部表示（內碼），語法分析再根據內碼來建立抽象語法樹，兩個過程都伴隨著出錯處理。

3.1.1 前端中的C標準基本詞匯符號

C標準的基本詞匯符號可以分為字符集和標識符。字符集分為英文字母、阿拉伯數字和特殊符號。標識符包括保留字、預定義標識符、用戶定義標識符［3］。預處理器和詞法分析將對源代碼中的所有詞匯符號（token）進行分類解析，不同類的信息在gcc內部用不同的變量。輸入代碼中所有字符在gcc內部都有對應的內碼來表示。下面初步介紹gcc中的基本詞匯及其內部表示。

所有的保留字定義在c－parser.c的一個結構體數組reswords［］中，這個數組的成員在解析器初始化的過程中將根據名字被索引到hash表中，以供解析時查找匹配。其內碼是一個枚舉數組中的值，一般形式為RID＿＊。對于用戶定義的標識符，一般解析為CPP＿NAME。

C中各種符號的定義。以“＋”來說明定義過程?！埃钡膅cc內部表示CPP＿PLUS是枚舉數組cpp＿ttype（in cpplib.h）中的一員。CPP＿PLUS包含在宏定義TTYPE＿TABLE中。對輸入代碼進行分析時函數cpp＿lex＿direct會將外部表示“＋”和內碼CPP＿PLUS對應起來。其他的英文字母和阿拉伯數字包含在字符識別函數＿cpp＿lex＿direct中?；驹~匯符號的信息在初始化時以靜態(tài)數組的形式被組織進hash表。詞法分析完成內外信息轉換過程之后，進入語法分析過程。根據本文需要，下面僅重點介紹語法分析中的數據類型。

3.1.2 前端C數據類型

基本的數據類型節(jié)點對于編譯器至關重要，是編譯器將高級語言精確而高效地映射到匯編語言的基礎。整型數據節(jié)點是C語言最基礎、最重要的部分，其使用頻率很高，必須保證對這些節(jié)點的訪問盡可能高效。因此，這些節(jié)點定義在全局數組integer＿types［］（in tree.h）中。

內建節(jié)點的初始化過程實際上是對tree結構中許多子成員的賦值過程。tree結構是定義在tree.h中的聯合，其成員涵蓋了C語言的各種語法類型，因此tree結構十分龐雜，所以對tree結構的操作是通過函數和宏來進行的。

前兩小節(jié)所介紹的基本詞匯字符和基本數據節(jié)點大多是以靜態(tài)形式存在的，而整個詞法語法分析會將這些信息串聯起來。

3.1.3 前端分析過程簡介

函數c＿parse＿file是前端對一個文件開始解析的入口。c＿parser＿declaration＿or＿fndef處理變量聲明和函數定義，在此過程將調用更底層的函數來對輸入的程序進行識別和分類并將信息記錄到相關的數據結構中。c＿lex＿one＿token函數對一個字符進行分析，首先調用函數c＿lex＿with＿flags來確定字符的type，＿cpp＿lex＿direct在這里被進一步調用，使得輸入字符和它們的gcc內碼對應起來，比如，字符“＋”將返回的type是CPP＿PLUS。然后，根據得到的類型進行分類處理，CPP＿NAME的case分支中包含了對標識符或者保留字的處理，保留字將被識別并用gcc內部的數據結構表示。其他的外部信息也由相應模塊來處理。

外部信息表示成內碼之后進行語法解析。語法解析的主要任務是抽象語法樹的建立、出錯處理、符號表的建立。gcc中所有語法樹都定義在tree.def中［4］。在語法解析過程中，解析器會根據操作符的內部表示映射到相應的樹節(jié)點，如CPP＿PLUS映射為PLUS＿EXPR。更為復雜的語法樹建立是由tree.c中的build＿＊族函數來完成的。

抽象語法樹是一種語言相關的中間語言表示IR（Intermediate Representation），為了方便對其進行優(yōu)化將進一步轉化成語言無關的中間語言表示（GIMPLE）。

3.2 gcc中端分析

GIMPLE IR是抽象語法樹的子集，兩者之間的不同之處就在于GIMPLE IR只含有順序和分支結構，其他的控制流都轉化成這兩種結構。GIMPLE階段最關鍵的步驟是GIMPLE轉化成RTL。GIMPLE是機器無關的，而RTL是機器相關的。GIMPLE到RTL的轉化過程在函數expand＿expr中，此函數包含一個巨大的switchcase，每一個GIMPLE的節(jié)點都會映射到后端的標準名（SPN），這些標準名必須被編碼到gcc中去。在中端，標準名實際上是＊＿optab的一類變量。擴展到RTL的過程從函數聲明的頂部開始，深度優(yōu)先遍歷整個GIMPLE樹［5］。

選擇了某個后端的標準名之后就進入到后端RTL生成過程了。

3.3 后端RTL生成過程

中端映射到標準名之后，gcc會自動根據模式（mode）去查找后端模板中是否有滿足條件的指令。所以，對于添加新的指令而言，標準名的定義和后端模板描述最值得關注，最后會在此基礎上簡要說明匹配過程以及最后的RTL生成。

3.3.1 標準名的添加

標準名的添加包括以下幾個方面：（1）在rtl.def文件中定義RTL操作符。（2）optabs.c中函數init＿optabs對庫函數的初始化。（3）后端模板自動生成程序genopinit.c的修改，增加optabs成員，描述新操作下數據模式的映射規(guī)則。

標準名添加之后，后端機器描述必須要使用該準名來描述指令，才能完成匹配。下面介紹機器描述。

3.3.2 機器描述（MD）

機器描述包括指令集、指令延遲、功能部件、流水線等［4］。機器描述MD是一個內容較豐富的部分，本文中只涉及到指令集的描述。在MD文件中描述指令集，gcc編譯生成CC1的過程會根據MD文件自動生成一系列的insn－＊.c和insn－＊.h文件，供編譯過程更有效地獲取機器相關的信息。自動生成的過程由一系列的gen＊.c文件來完成［6］。

在編譯生成CC1時，genemit.c文件會根據MD描述自動生成文件insn－emit.c，此文件集合了許多產生rtx的函數，這些函數在CC1運行C程序的時候使用。

3.3.3 GIMPLE到RTL生成總結

通過前面的描述，現在可以總結GIMPLE到RTL生成的過程。

（1）目標無關的expand＿＊函數集完成GIMPLE到RTL的映射過程。

（2）目標相關的gen＿＊函數集完成RTX的具體生成過程。gen＿＊函數由自動生成程序根據機器描述自動生成。

（3）expand＿＊函數集和gen＿＊函數集的操作接口主要是：optab＿table［］和insn＿data［］。例如，針對CODE為PLUS的表達式，其調用過程為：首先找到PLUS對應的optab＿table［code］；接著根據正確的 mode來找到optab＿table［code］.handlers［mode］.insn＿code；再由insn＿code找到insn＿data［insn＿code］；最后insn＿data［insn＿code］.genfun對應上insn－emit.c文件中的gen＿addsi3函數，調用該函數生成合適的RTL。

（4）經過RTL的優(yōu)化遍，最后匯編輸出。

3.4 指令映射過程總結

gcc內部指令映射的過程本質上是多種語言之間的轉化過程。首先是詞法分析將輸入的C代碼轉化成內部表示，語法分析在此基礎上建立AST，對AST進行簡化生成GIMPLE，經過優(yōu)化過程之后再映射到RTL，經過RTL優(yōu)化遍之后就是匯編輸出。這些中間語言都有相應的數據結構和變量來描述，它們是靜態(tài)的；gcc的編譯流程是由一系列重要的函數實現的，它們控制了中間語言之間的轉化，是動態(tài)的過程。所以，實現新的類型的指令映射，就是給中間表示增加靜態(tài)的變量成員，并控制相應函數的動態(tài)轉化過程。接下來將以飽和加法的實現為例來簡要介紹飽和算術在gcc中的設計與實現。

4 飽和算術指令映射機制的實現

gcc將高級語言映射到匯編語言的過程，本質上是幾種中間語言的轉化過程。因此，對于飽和這一新的數據類型，不同的中間語言需要增加描述它的詞匯，并在映射過程中控制中間語言之間的轉化過程，使之映射到正確的目標代碼。對于飽和屬性，仿照C語言中signed這個作為修飾作用的保留字，擴展C語言增加一個修飾保留字sat。針對這一擴展，在前端、中端、后端的中間語言中增加新的數據變量，并控制這些變量之間的轉化，完成映射過程。本節(jié)將以飽和加法指令的實現過程為例來實現上述思路。

飽和加法的基本目標是：對C標準進行擴展，用sat來描述數據類型（類似于C保留字signed，修飾作用），那么sat int a，b，c；c＝a＋b；能夠映射到整數飽和有符號加法指令SADD32。

4.1 前端設計與實現

前端涉及的中間表示有兩種：詞法分析之后的內碼以及語法分析建立的AST。首先要在這兩種中間表示中增加新的成員，然后控制新成員在前端的轉化過程。

4.1.1 前端增加新的保留字sat

所有的保留字定義在c－parser.c的一個結構體數組reswords［］中，以保留字“char”為例作簡要說明：｛“char”，RID＿CHAR，0｝，成員一代表保留字在輸入代碼中的寫法；成員二是該保留字在gcc內部的表示，是一個枚舉數字的成員，定義在ccommon.h的枚舉數組rid［］中；第三個成員是一個數字，表示該保留字是為哪種C標準所有。

（1）在c－parser.c的一個結構體數組reswords［］中，增加保留字"sat"：｛"sat"，RID＿SAT，0｝。

（2）c－common.h的枚舉中增加 RID＿SAT。

4.1.2 增加內建數據節(jié)點

整數的內建數據節(jié)點定義在integer＿types［］（in tree.h）的全局數組中，而不像其它類型節(jié)點被放在哈希表里。這只是一個簡單的tree結構數組的聲明。函數build＿common＿tree＿nodes和函數build＿common＿tree＿nodes2完成了所有的內建數據節(jié)點的初始化過程。record＿builtin＿type把已經初始化的節(jié)點類型和它們的輸入名稱聯系起來。

（1）在tree.h中增加sat＿integer＿type＿node。

＃define sat＿integer＿type＿node integer＿types［itk＿sat＿int］枚舉integer＿type＿kind中增加itk＿sat＿int。（2）build＿common＿tree＿nodes函數中增加對新增內建節(jié)點的初始化過程。

sat＿integer＿type＿node＝ make＿signed＿type（INT＿TYPE＿SIZE，1）

（3）函數 make＿signed＿type是確定數據的有無符號屬性，在此函數中增加satp參數來判斷是否為飽和屬性。make＿signed＿type（INT＿TYPE＿SIZE，satp）函數體內增加代碼：

if（satp）

TYPE＿SATURATING（type）＝1；

make＿unsigned＿type需要類似修改。調用這兩個函數的地方都要做出相應修改。

（4）c＿common＿nodes＿and＿builtins的修改：用函數record＿builtin＿type把外部 C語法“sat int”與新增數據節(jié)點對應起來。

4.1.3 前端解析過程移植

詞法分析和語法分析過程都是在函數c＿parser＿declaration＿or＿fndef中進行的。

specs是函數c＿parser＿declaration＿or＿fndef中記錄C聲明特征的變量，其中包括描述屬性的許多標志位，如有無符號，是否為long，是否是short等。函數declspecs＿add＿type會根據specs的信息并結合C標準來判斷不同保留字組合的合法性，不合法就報警告或者錯誤，合法就進一步完善specs的信息。記錄在specs中的數據類型的信息傳遞是通過函數finish＿declspecs來完成的。根據specs中的信息可以判斷對于當前的一個變量a是一個什么類型的內建數據節(jié)點。

（1）declspecs＿add＿type函數修改：

case RID＿SAT時修改使得sat int合法不報錯，并且記錄有效信息。

（2）修改finish＿declspecs使得新增加的節(jié)點被使用。case cts＿int時增加一個飽和屬性的分支情形：

specs→type＝ （specs→saturating＿p？sat＿integer＿type＿node：integer＿type＿node）

4.2 中端設計與實現

GIMPLE轉化成RTL首先是由樹節(jié)點（＊＿EXPR）結合機器模式信息映射到后端數組optabs［］的成員＊＿optab（SPN 包含在其中），再由＊＿optab中的信息找到后端生成RTL的函數gen＿＊。這個過程是用標準名聯系起來的。

以c＝a＋b的轉化過程為例簡要說明。前端已經解析得到：（1）a、b、c為有符號的整數；（2）“＋”的GIMPLE表示為PLUS＿EXPR。由GIMPLE到RTL的轉化是由expand＿＊函數集來完成的。expand＿expr＿real＿1函數包含加法操作的轉化過程，在此函數可以根據操作符的操作數情況做相應的轉化，可以轉化為其他的＊＿EXPR，也可以根據操作數來確定＊＿optab。加法的過程是進一步調用函數optab＿for＿tree＿code才確定的，在這個函數里，可以根據加法的性質（有無符號，是否飽和）來選擇相應的＊＿optab。

中端修改使得PLUS＿EXPR能選擇新增的ssadd＿optab，在函數optab＿for＿tree＿code做以下修改：case PLUS＿EXPR：時根據是否飽和、有無符號判斷返回對應的＊＿optab。

4.3 后端設計與實現

標準名的添加首先要分析＊＿optab，結合其內容來添加相應的定義。以加法為例來分析：

（1）add＿optab在tree.h被宏定義轉換成數組optab＿table的一個成員。

＃define add＿optab （＆optab＿table［OTI＿add］）

（2）跟蹤查看optab＿table［OTI＿add］如圖1所示（有省略）。

Figure 1 Standard pattern names in optab圖1 操作表中的標準名變量

optab＿table是一個結構體。code是一個RTL操作，定義在rtl.def：DEF＿RTL＿EXPR（PLUS，"plus"，"ee"，RTX＿COMM＿ARITH）中，PLUS是optab＿table中用到的值。

libcall＿basenam、libcall＿gen是庫函數調用的接口信息，如果在后端模板中沒有匹配到合適的信息，這些信息將被用來匹配庫函數。這幾個成員的初始化是由optabs.c的函數init＿optabs完成的。

handlers是一個結構體數組，每一個成員代表某一個模式下后端是否有相應的指令來匹配，如果有，數組中insn＿code的值的名稱就是操作和模式下的一個組合。例如，加法的整數（SI）模式為CODE＿FOR＿addsi3（3為操作數個數），如果沒有值就是CODE＿FOR＿nothing。這個數組是機器指令描述信息的體現。從上面的值可以看出，該加法只有整數（SI）和浮點單雙精度模式（SF、DF）有指令模板供匹配。程序genopinit.c自動將后端模板描述信息映射到optab＿table的handlers數組中。genopinit.c中的數組optabs記錄了不同操作不同數據類型映射的規(guī)則，函數gen＿insn會根據這些信息來完成映射。

根據以上分析，做出如下修改：

（1）rtl.def中新增飽和有符號加法的rtl操作符SS＿PLUS；

（2）新增ssadd＿optab：＃define ssadd＿optab（＆optab＿table［OTI＿ssadd］）；

（3）在enum optab＿index中增加 OTI＿ssadd；

（4）修改init＿optabs函數，使得ssadd＿optab初始化（包括code和庫函數名稱的初始化）；

（5）修改genopinit.c中的數組optabs，使之建立后端整數飽和加法機器描述的自動映射過程；

（6）機器描述中新增有符號飽和加法的擴展規(guī)則（define＿expand）和指令描述（define＿insn）。

define＿expand描述了中端GIMPILE向RTL的擴展規(guī)則。define＿insn是一種機器描述構造的方式，用來為gcc新增標準名操作，描述機器指令。

4.4 映射過程總結

本節(jié)以飽和加法指令映射過程為例說明了本文飽和算術指令在gcc中的實現方案。首先對C語言擴展增加描述飽和屬性的保留字sat，在前端增加保留字的內碼表示，增加新的數據類型，在中端增加新的操作，在后端增加新的標準名以及新的機器描述。在完成靜態(tài)信息的添加的基礎上，進一步改變前端、中端函數的映射路徑，使得前端對飽和屬性數據的操作最終能映射到后端相應的機器描述上去，從而完成整個飽和加法的映射過程。

與gcc已有的基于Fixed－point數據類型飽和算術指令映射比較，本文的飽和指令映射實現過程更加簡潔。原因在于Fixed－point是一種新的數據類型，為支持新的數據類型，需要在gcc中構建新的框架，這本身就是一個浩大的工程。本文是基于整數類型的飽和指令的實現，同時也借鑒了基于Fixed－point飽和指令映射的方法，方案實現的可操作性和復雜性就相對較低。與gcc已有飽和指令映射過程的不同點在于：C擴展的關鍵字不同，映射過程變量數據模式不同；映射過程相對單一簡潔。

5 實驗結果

根據上節(jié)描述的方案和過程，基于gcc－4.3.2版本實現了Matrix指令集中整數飽和加法的映射過程。gcc－4.3.2版本支持 Fixed－point數據類型飽和算術指令，不支持整數和浮點數據類型飽和算術指令映射。

Figure 2 Generation of saturation addition instruction圖2 飽和加法指令映射實驗結果

圖2 a是Matrix編譯器整數飽和加法的指令映射的示例。對于c＝a＋b的飽和加法程序，a、b、c均為整數類型，用關鍵字sat int來定義，表示通過Matrix編譯器編譯生成的匯編代碼中產生了預期的飽和加法指令SADD32。圖2b是gcc中支持的Fixed－point數據類型飽和加法指令映射示例。對于c＝a＋b的飽和加法程序，a、b、c均為Fixed－point類型，通過Matrix編譯器編譯會映射到代表Fixed－point類型加法的指令ADDF（Matrix指令集中不存在ADDF，為實驗對比添加）。

未實現飽和算術的編譯器中，飽和加法的描述需要兩個嵌套的if－else結構才能實現。對于實現了飽和算術的Matrix編譯器，只需要在定義變量時給變量增加一個飽和屬性的保留字sat，編譯器就能映射到一條有符號飽和加法指令——SADD32指令。這樣的設計大大減輕了編譯器飽和算術指令映射的復雜度，映射更加準確，且提高了效率。

6 結束語

飽和算術指令使得數字信號處理算法更加準確、更加高效，是Matrix指令集中很重要的一種指令。gcc目前只支持基于Fixed－point數據類型的飽和算術指令映射。Matrix指令集的飽和指令是基于整數和浮點的，所以需要移植gcc使其支持整數和浮點的飽和算術指令的映射。

本文首先針對飽和算術指令映射的實現，對gcc的一般加法指令映射過程從前端到后端做了針對性的分析，在此基礎上，設計并實現了一種基于C擴展關鍵字sat的飽和算術指令映射機制；然后基于Matrix編譯器實現了算術飽和指令的映射，并以飽和有符號的整數加法指令的映射為例介紹了本文提出的飽和算術指令映射方案具體的實現過程；最后的實驗結果驗證了實現策略和過程的正確性和簡潔性。本文對標準C的擴展方法也適用于對Embedded－C進行此類擴展；類似的策略和實現過程也可以用來實現其它的飽和算術指令的映射，對于其他類型指令的映射過程，有一定的借鑒作用。

［1］ http：／／gcc.gnu.org／wiki／FixedPointArithmetic.

［2］ http：／／en.wikipedia.org／wiki／Saturation＿arithmetic.

［3］ Huang Wei－tong，Lu Ming－yu.C programming language［M］.Beijing：Tsinghua University Press，2005.（in Chinese）

［4］ http：／／gcc.gnu.org／onlinedocs／gccint／.

［5］ Vichare A，Deshpande S.GCC 4.0.2—The implementation［EB／OL］.［2008－10－15］.http：／／www.iitb.ac.in.

［6］ Ren Shan－h(huán)ong，Zhao Ke－jia，Zhao Xiong－fang.The intermediate language and the back－end information translation in GCC［J］.Computer Engineering ＆ Science，1995，17（2）：74－82.（in Chinese）

附中文參考文獻：

［3］ 黃維通，魯明羽.C程序設計教程［M］.北京：清華大學出版社，2005.

［6］ 任珊虹，趙克佳，趙雄芳.GCC的中間語言以及后端信息的轉換［J］.計算機工程與科學，1995，17（2）：74－82.