1、matrix編譯器中飽和算術(shù)指令映射的設(shè)計(jì)與實(shí)現(xiàn)       摘要：是一款面向軟基站的高性能 ，飽和算術(shù)指令是 體系結(jié)構(gòu)中很重要的一種指令，它使得 算法更加安全、準(zhǔn)確、高效。因此，編譯器對飽和算術(shù)指令的映射支持就尤為關(guān)鍵。編譯器的開發(fā)平臺(tái)是，現(xiàn)有的版本只支持的飽和算術(shù)指令，不支持整數(shù)和浮點(diǎn)的飽和算術(shù)指令。首先分析了內(nèi)部指令映射的機(jī)制，在此基礎(chǔ)上提出了一種基于擴(kuò)展的飽和算術(shù)指令映射實(shí)現(xiàn)方案，并通過實(shí)現(xiàn)飽和加法指令的映射來驗(yàn)證所提出的方案。實(shí)驗(yàn)結(jié)果表明，該方案能夠高效、準(zhǔn)確地實(shí)現(xiàn)飽和算術(shù)指令的映射。關(guān)鍵詞：；飽和算術(shù)；指令映射 

2、  引言當(dāng)前，芯片在多媒體、信號(hào)處理等領(lǐng)域中的應(yīng)用越來越廣泛，由于嵌入式芯片功耗和成本的限制，芯片對編譯器指令映射的精確性和高效性的要求也越來越高，同時(shí)選擇快速、有效、低成本的編譯器開發(fā)平臺(tái)也越來越重要。是一款面向軟基站的、自主指令集的高性能，編譯器的開發(fā)平臺(tái)是，它是一個(gè)開發(fā)運(yùn)行在不同系統(tǒng)平臺(tái)的高效快速的開源的編譯系統(tǒng)。對于特定的目標(biāo)體系結(jié)構(gòu)，通過移植可以開發(fā)出這個(gè)平臺(tái)的編譯系統(tǒng)，是一種快速、有效、低成本的方案。目前只支持基于數(shù)據(jù)類型飽和算術(shù)指令映射。由于指令集的飽和指令是基于整數(shù)和浮點(diǎn)的，所以需要移植，使其支持整數(shù)和浮點(diǎn)的飽和算術(shù)指令的映射。飽和算術(shù)指令使得數(shù)字信號(hào)處理算法更加準(zhǔn)確

3、、更加高效，是指令集中很重要的一種指令。對進(jìn)行移植，使得在編譯器支持飽和算術(shù)指令的映射。本文對指令映射過程的分析以及實(shí)現(xiàn)飽和算術(shù)指令映射的思路，對于其他指令映射的實(shí)現(xiàn)具有一定的借鑒作用。本文第節(jié)介紹了飽和算術(shù)的定義和特征；第節(jié)介紹了中指令映射的一般過程；第節(jié)給出了飽和算術(shù)指令映射的實(shí)現(xiàn)過程；第節(jié)描述了飽和加法指令映射實(shí)驗(yàn)結(jié)果；第節(jié)對全文總結(jié)。飽和算術(shù)簡介飽和算術(shù)使得一些算法更加準(zhǔn)確、更加高效，尤其是在算法中。例如：調(diào)整聲量可能導(dǎo)致聲音信號(hào)溢出，而飽和算術(shù)可以明顯減少對信號(hào)的扭曲。把兩個(gè)數(shù)的補(bǔ)碼形式相加，會(huì)導(dǎo)致環(huán)繞現(xiàn)象（），這可能會(huì)對系統(tǒng)的信噪比造成災(zāi)難性結(jié)果，運(yùn)用飽和算術(shù)則可以避免。飽和算術(shù)運(yùn)

4、算是一種值被限定在固定范圍內(nèi)的運(yùn)算操作，有最大值和最小值。比如飽和加法操作：如果兩個(gè)數(shù)相加后的結(jié)果比最大值要大，那么最終的結(jié)果就等于最大值；如果相加后的結(jié)果比最小值要小，最終結(jié)果就等于最小值；如果相加后的結(jié)果在最大值和最小值之間，這就是最終的結(jié)果。對于這樣的語言描述，目前只能完成基于數(shù)據(jù)類型的映射。因此，在中實(shí)現(xiàn)基于整數(shù)和浮點(diǎn)類型的飽和算術(shù)指令的映射會(huì)使得編譯器更加高效。指令映射機(jī)制分析的編譯流程是：詞法分析語法分析中間代碼生成代碼優(yōu)化代碼生成。詞法分析和語法分析稱之為前端，中間代碼生成和部分優(yōu)化稱之為中端，部分優(yōu)化、機(jī)器描述（）和代碼生成稱之為后端。前端處理過程在內(nèi)，前端預(yù)處理、詞法分析、語

5、法分析三個(gè)過程統(tǒng)稱為解析過程。前端的主要任務(wù)是對輸入的代碼進(jìn)行解析并記錄有效信息，形成抽象語法樹（）。解析過程的依據(jù)是標(biāo)準(zhǔn)，標(biāo)準(zhǔn)在前端的信息可以分為基本詞匯符號(hào)和語法規(guī)則兩類。一般以表的形式把基本詞匯符號(hào)的信息組織起來，供解析過程查詢。語法規(guī)則實(shí)際是基本詞匯符號(hào)排列組合的規(guī)則，一般體現(xiàn)在語法分析過程中。前端大致分為兩個(gè)階段：預(yù)處理和詞法分析把輸入代碼轉(zhuǎn)換成的內(nèi)部表示（內(nèi)碼），語法分析再根據(jù)內(nèi)碼來建立抽象語法樹，兩個(gè)過程都伴隨著出錯(cuò)處理。前端中的標(biāo)準(zhǔn)基本詞匯符號(hào)標(biāo)準(zhǔn)的基本詞匯符號(hào)可以分為字符集和標(biāo)識(shí)符。字符集分為英文字母、阿拉伯?dāng)?shù)字和特殊符號(hào)。標(biāo)識(shí)符包括保留字、預(yù)定義標(biāo)識(shí)符、用戶定義標(biāo)識(shí)符。預(yù)處

6、理器和詞法分析將對源代碼中的所有詞匯符號(hào)（）進(jìn)行分類解析，不同類的信息在內(nèi)部用不同的變量。輸入代碼中所有字符在內(nèi)部都有對應(yīng)的內(nèi)碼來表示。下面初步介紹中的基本詞匯及其內(nèi)部表示。所有的保留字定義在的一個(gè)結(jié)構(gòu)體數(shù)組中，這個(gè)數(shù)組的成員在解析器初始化的過程中將根據(jù)名字被索引到表中，以供解析時(shí)查找匹配。其內(nèi)碼是一個(gè)枚舉數(shù)組中的值，一般形式為。對于用戶定義的標(biāo)識(shí)符，一般解析為。中各種符號(hào)的定義。以“”來說明定義過程。“”的內(nèi)部表示是枚舉數(shù)組（）中的一員。包含在宏定義中。對輸入代碼進(jìn)行分析時(shí)函數(shù)會(huì)將外部表示“”和內(nèi)碼對應(yīng)起來。其他的英文字母和阿拉伯?dāng)?shù)字包含在字符識(shí)別函數(shù)中。基本詞匯符號(hào)的信息在初始化時(shí)以靜態(tài)數(shù)

7、組的形式被組織進(jìn)表。詞法分析完成內(nèi)外信息轉(zhuǎn)換過程之后，進(jìn)入語法分析過程。根據(jù)本文需要，下面僅重點(diǎn)介紹語法分析中的數(shù)據(jù)類型。前端數(shù)據(jù)類型基本的數(shù)據(jù)類型節(jié)點(diǎn)對于編譯器至關(guān)重要，是編譯器將高級(jí)語言精確而高效地映射到匯編語言的基礎(chǔ)。整型數(shù)據(jù)節(jié)點(diǎn)是語言最基礎(chǔ)、最重要的部分，其使用頻率很高，必須保證對這些節(jié)點(diǎn)的訪問盡可能高效。因此，這些節(jié)點(diǎn)定義在全局?jǐn)?shù)組（）中。內(nèi)建節(jié)點(diǎn)的初始化過程實(shí)際上是對結(jié)構(gòu)中許多子成員的賦值過程。結(jié)構(gòu)是定義在淡孝強(qiáng)等：編譯器中飽和算術(shù)指令映射的設(shè)計(jì)與實(shí)現(xiàn)中的聯(lián)合，其成員涵蓋了語言的各種語法類型，因此結(jié)構(gòu)十分龐雜，所以對結(jié)構(gòu)的操作是通過函數(shù)和宏來進(jìn)行的。前兩小節(jié)所介紹的基本詞匯字符和基

8、本數(shù)據(jù)節(jié)點(diǎn)大多是以靜態(tài)形式存在的，而整個(gè)詞法語法分析會(huì)將這些信息串聯(lián)起來。前端分析過程簡介函數(shù)是前端對一個(gè)文件開始解析的入口。處理變量聲明和函數(shù)定義，在此過程將調(diào)用更底層的函數(shù)來對輸入的程序進(jìn)行識(shí)別和分類并將信息記錄到相關(guān)的數(shù)據(jù)結(jié)構(gòu)中。函數(shù)對一個(gè)字符進(jìn)行分析，首先調(diào)用函數(shù)來確定字符的，在這里被進(jìn)一步調(diào)用，使得輸入字符和它們的內(nèi)碼對應(yīng)起來，比如，字符“”將返回的是。然后，根據(jù)得到的類型進(jìn)行分類處理，的分支中包含了對標(biāo)識(shí)符或者保留字的處理，保留字將被識(shí)別并用內(nèi)部的數(shù)據(jù)結(jié)構(gòu)表示。其他的外部信息也由相應(yīng)模塊來處理。外部信息表示成內(nèi)碼之后進(jìn)行語法解析。語法解析的主要任務(wù)是抽象語法樹的建立、出錯(cuò)處理、符號(hào)

9、表的建立。中所有語法樹都定義在中。在語法解析過程中，解析器會(huì)根據(jù)操作符的內(nèi)部表示映射到相應(yīng)的樹節(jié)點(diǎn)，如映射為。更為復(fù)雜的語法樹建立是由中的族函數(shù)來完成的。抽象語法樹是一種語言相關(guān)的中間語言表示（），為了方便對其進(jìn)行優(yōu)化將進(jìn)一步轉(zhuǎn)化成語言無關(guān)的中間語言表示（）。中端分析是抽象語法樹的子集，兩者之間的不同之處就在于只含有順序和分支結(jié)構(gòu)，其 他 的 控 制 流 都 轉(zhuǎn) 化 成 這 兩 種 結(jié) 構(gòu)。階段最關(guān)鍵的步驟是轉(zhuǎn)化成。是機(jī)器無關(guān)的，而是機(jī)器相關(guān)的。到的轉(zhuǎn)化過程在函數(shù)中，此 函 數(shù) 包 含 一 個(gè) 巨 大 的，每一個(gè)的節(jié)點(diǎn)都會(huì)映射到后端的標(biāo)準(zhǔn)名（），這些標(biāo)準(zhǔn)名必須被編碼到中去。在中端，標(biāo)準(zhǔn)名實(shí)際上

10、是的一類變量。擴(kuò)展到的過程從函數(shù)聲明的頂部開始，深度優(yōu)先遍歷整個(gè)樹。選擇了某個(gè)后端的標(biāo)準(zhǔn)名之后就進(jìn)入到后端生成過程了。后端生成過程中端映射到標(biāo)準(zhǔn)名之后，會(huì)自動(dòng)根據(jù)模式（）去查找后端模板中是否有滿足條件的指令。所以，對于添加新的指令而言，標(biāo)準(zhǔn)名的定義和后端模板描述最值得關(guān)注，最后會(huì)在此基礎(chǔ)上簡要說明匹配過程以及最后的生成。標(biāo)準(zhǔn)名的添加標(biāo)準(zhǔn)名的添加包括以下幾個(gè)方面：（）在文件中定義操作符。（）中函數(shù)對庫函數(shù)的初始化。（）后端模板自動(dòng)生成程序的修改，增加成員，描述新操作下數(shù)據(jù)模式的映射規(guī)則。標(biāo)準(zhǔn)名添加之后，后端機(jī)器描述必須要使用該準(zhǔn)名來描述指令，才能完成匹配。下面介紹機(jī)器描述。機(jī)器描述（）機(jī)器描述包

11、括指令集、指令延遲、功能部件、流水線等。機(jī)器描述是一個(gè)內(nèi)容較豐富的部分，本文中只涉及到指令集的描述。在文件中描述指令集，編譯生成的過程會(huì)根據(jù)文件自動(dòng)生成一系列的和文件，供編譯過程更有效地獲取機(jī)器相關(guān)的信息。自動(dòng)生成的過程由一系列的文件來完成。在編譯生成時(shí)，文件會(huì)根據(jù)描述自動(dòng)生成文件，此文件集合了許多產(chǎn)生的函數(shù)，這些函數(shù)在運(yùn)行程序的時(shí)候使用。到 生成總結(jié)通過前面的描述，現(xiàn)在可以總結(jié)到生成的過程。（）目標(biāo)無關(guān)的函數(shù)集完成到的映射過程。（）目標(biāo)相關(guān)的函數(shù)集完成的具體生成過程。函數(shù)由自動(dòng)生成程序根據(jù)機(jī)器描述自動(dòng)生成。（）函數(shù)集和函數(shù)集的操作接口主要是：和。例如，針對為的表達(dá)式，其調(diào)用過程為：首先找到對

12、應(yīng)的；接著根據(jù)正確的來找到；再由找到 計(jì)算機(jī)工程與科學(xué)，（）；最后對應(yīng)上文件中的函數(shù)，調(diào)用該函數(shù)生成合適的。（）經(jīng)過的優(yōu)化遍，最后匯編輸出。指令映射過程總結(jié)內(nèi)部指令映射的過程本質(zhì)上是多種語言之間的轉(zhuǎn)化過程。首先是詞法分析將輸入的代碼轉(zhuǎn)化成內(nèi) 部表示，語法分析 在此 基礎(chǔ)上建 立，對進(jìn)行簡化生成，經(jīng)過優(yōu)化過程之后再映射到，經(jīng)過優(yōu)化遍之后就是匯編輸出。這些中間語言都有相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和變量來描述，它們是靜態(tài)的；的編譯流程是由一系列重要的函數(shù)實(shí)現(xiàn)的，它們控制了中間語言之間的轉(zhuǎn)化，是動(dòng)態(tài)的過程。所以，實(shí)現(xiàn)新的類型的指令映射，就是給中間表示增加靜態(tài)的變量成員，并控制相應(yīng)函數(shù)的動(dòng)態(tài)轉(zhuǎn)化過程。接下來將以飽和加

13、法的實(shí)現(xiàn)為例來簡要介紹飽和算術(shù)在中的設(shè)計(jì)與實(shí)現(xiàn)。飽和算術(shù)指令映射機(jī)制的實(shí)現(xiàn)將高級(jí)語言映射到匯編語言的過程，本質(zhì)上是幾種中間語言的轉(zhuǎn)化過程。因此，對于飽和這一新的數(shù)據(jù)類型，不同的中間語言需要增加描述它的詞匯，并在映射過程中控制中間語言之間的轉(zhuǎn)化過程，使之映射到正確的目標(biāo)代碼。對于飽和屬性，仿照語言中這個(gè)作為修飾作用的保留字，擴(kuò)展語言增加一個(gè)修飾保留字。針對這一擴(kuò)展，在前端、中端、后端的中間語言中增加新的數(shù)據(jù)變量，并控制這些變量之間的轉(zhuǎn)化，完成映射過程。本節(jié)將以飽和加法指令的實(shí)現(xiàn)過程為例來實(shí)現(xiàn)上述思路。飽和加法的基本目標(biāo)是：對標(biāo)準(zhǔn)進(jìn)行擴(kuò)展，用來描述數(shù)據(jù)類型（類似于保留字，修飾作用），那么，；能夠映

14、射到整數(shù)飽和有符號(hào)加法指令。前端設(shè)計(jì)與實(shí)現(xiàn)前端涉及的中間表示有兩種：詞法分析之后的內(nèi)碼以及語法分析建立的。首先要在這兩種中間表示中增加新的成員，然后控制新成員在前端的轉(zhuǎn)化過程。前端增加新的保留字所有的保留字定義在的一個(gè)結(jié)構(gòu)體數(shù)組中，以保留字“”為例作簡要說明：“”，成員一代表保留字在輸入代碼中的寫法；成員二是該保留字在內(nèi)部的表示，是一個(gè)枚舉數(shù)字的成員，定義在的枚舉數(shù)組中；第三個(gè)成員是一個(gè)數(shù)字，表示該保留字是為哪種標(biāo)準(zhǔn)所有。（）在的一個(gè)結(jié)構(gòu)體數(shù)組中，增加保留字""：""，。（）的枚舉中增加。增加內(nèi)建數(shù)據(jù)節(jié)點(diǎn)整數(shù)的內(nèi)建數(shù)據(jù)節(jié)點(diǎn)定義在（）的全局?jǐn)?shù)組中，而不像其

15、它類型節(jié)點(diǎn)被放在哈希表里。這只是一個(gè)簡單的結(jié)構(gòu)數(shù)組的聲明。函數(shù)和函數(shù)完成了所有的內(nèi)建數(shù)據(jù)節(jié)點(diǎn)的初始化過程。把已經(jīng)初始化的節(jié)點(diǎn)類型和它們的輸入名稱聯(lián)系起來。（）在中增加。枚舉中增加。（）函數(shù)中增加對新增內(nèi)建節(jié)點(diǎn)的初始化過程。 （，）（）函數(shù)是確定數(shù)據(jù)的有無符號(hào)屬性，在此函數(shù)中增加參數(shù)來判斷是否為飽和屬性。（，）函數(shù)體內(nèi)增加代碼：（）（）；需要類似修改。調(diào)用這兩個(gè)函數(shù)的地方都要做出相應(yīng)修改。（）的修改：用函數(shù)把外部語法“”與新增數(shù)據(jù)節(jié)點(diǎn)對應(yīng)起來。前端解析過程移植詞法分析和語法分析過程都是在函數(shù)中進(jìn)行的。是函數(shù)中記錄聲明特征的變量，其中包括描述屬性的許多標(biāo)志 位，如 有 無 符 號(hào)，是 否 為，是

16、否 是等。函數(shù)會(huì)根據(jù)的信息并結(jié)合標(biāo)準(zhǔn)來判斷不同保留字組合的合法性，不合法就報(bào)警告或者錯(cuò)誤，合法就進(jìn)一步完淡孝強(qiáng)等：編譯器中飽和算術(shù)指令映射的設(shè)計(jì)與實(shí)現(xiàn)善的信息。記錄在中的數(shù)據(jù)類型的信息傳遞是通過函數(shù)來完成的。根據(jù)中的信息可以判斷對于當(dāng)前的一個(gè)變量是一個(gè)什么類型的內(nèi)建數(shù)據(jù)節(jié)點(diǎn)。（）函數(shù)修改：時(shí)修改使得合法不報(bào)錯(cuò)，并且記錄有效信息。（）修改使得新增加的節(jié)點(diǎn)被使用。時(shí)增加一個(gè)飽和屬性的分支情形：（？：）中端設(shè)計(jì)與實(shí)現(xiàn)轉(zhuǎn)化成首先是由樹節(jié)點(diǎn)（）結(jié)合機(jī)器模式信息映射到后端數(shù)組的成員（包含在其中），再由中的信息找到后端生成的函數(shù)。這個(gè)過程是用標(biāo)準(zhǔn)名聯(lián)系起來的。以的轉(zhuǎn)化過程為例簡要說明。前端已經(jīng)解析得到：（）

17、、為有符號(hào)的整數(shù)；（）“”的表示為。由到的轉(zhuǎn)化是由函數(shù)集來完成的。函數(shù)包含加法操作的轉(zhuǎn)化過程，在此函數(shù)可以根據(jù)操作符的操作數(shù)情況做相應(yīng)的轉(zhuǎn)化，可以轉(zhuǎn)化為其他的，也可以根據(jù)操作數(shù)來確定。加法的過程是進(jìn)一步調(diào)用函數(shù)才確定的，在這個(gè)函數(shù)里，可以根據(jù)加法的性質(zhì)（有無符號(hào)，是否飽和）來選擇相應(yīng)的。中端修改使得能選擇新增的，在函數(shù)做以下修改：時(shí)根據(jù)是否飽和、有無符號(hào)判斷返回對應(yīng)的。后端設(shè)計(jì)與實(shí)現(xiàn)標(biāo)準(zhǔn)名的添加首先要分析，結(jié)合其內(nèi)容來添加相應(yīng)的定義。以加法為例來分析：（）在被宏定義轉(zhuǎn)換成數(shù)組的一個(gè)成員。（）（）跟蹤查看如圖所示（有省略）。是 一 個(gè) 結(jié) 構(gòu) 體。是 一 個(gè)操 作，定 義 在：圖操作表中的標(biāo)準(zhǔn)名

18、變量（，""，""，）中，是中用到的值。、是庫函數(shù)調(diào)用的接口信息，如果在后端模板中沒有匹配到合適的信息，這些信息將被用來匹配庫函數(shù)。這幾個(gè)成員的初始化是由的函數(shù)完成的。是一個(gè)結(jié)構(gòu)體數(shù)組，每一個(gè)成員代表某一個(gè)模式下后端是否有相應(yīng)的指令來匹配，如果有，數(shù)組中的值的名稱就是操作和模式下的一 個(gè) 組 合。例 如，加 法 的 整 數(shù) （）模 式 為（為操作數(shù)個(gè)數(shù)），如果沒有值就是。這個(gè)數(shù)組是機(jī)器指令描述信息的體現(xiàn)。從上面的值可以看出，該加法只有整數(shù)（）和浮點(diǎn)單雙精度模式（、）有指令模板供匹配。程序自動(dòng)將后端模板描述信息映射到的數(shù)組中。中的數(shù)組記錄了不同操作不同數(shù)據(jù)

19、類型映射的規(guī)則，函數(shù)會(huì)根據(jù)這些信息來完成映射。根據(jù)以上分析，做出如下修改：（）中新增飽和有符號(hào)加法的操作符；（）新增：（）；（）在中增加；（）修改函數(shù)，使得初始化（包括和庫函數(shù)名稱的初始化）；（）修改中的數(shù)組，使之建立后端整數(shù)飽和加法機(jī)器描述的自動(dòng)映射過程；（）機(jī)器描述中新增有符號(hào)飽和加法的擴(kuò)展規(guī)則（）和指令描述（）。描述了中端向的擴(kuò)展規(guī)則。是一種機(jī)器描述構(gòu)造的方式，用來為新增標(biāo)準(zhǔn)名操作，描述機(jī)器指令。映射過程總結(jié)本節(jié)以飽和加法指令映射過程為例說明了本文飽和算術(shù)指令在中的實(shí)現(xiàn)方案。首先對 計(jì)算機(jī)工程與科學(xué)，（）語言擴(kuò)展增加描述飽和屬性的保留字，在前端增加保留字的內(nèi)碼表示，增加新的數(shù)據(jù)類型，在中

20、端增加新的操作，在后端增加新的標(biāo)準(zhǔn)名以及新的機(jī)器描述。在完成靜態(tài)信息的添加的基礎(chǔ)上，進(jìn)一步改變前端、中端函數(shù)的映射路徑，使得前端對飽和屬性數(shù)據(jù)的操作最終能映射到后端相應(yīng)的機(jī)器描述上去，從而完成整個(gè)飽和加法的映射過程。與已有的基于數(shù)據(jù)類型飽和算術(shù)指令映射比較，本文的飽和指令映射實(shí)現(xiàn)過程更加簡潔。原因在于是一種新的數(shù)據(jù)類型，為支持新的數(shù)據(jù)類型，需要在中構(gòu)建新的框架，這本身就是一個(gè)浩大的工程。本文是基于整數(shù)類型的飽和指令的實(shí)現(xiàn)，同時(shí)也借鑒了基于飽和指令映射的方法，方案實(shí)現(xiàn)的可操作性和復(fù)雜性就相對較低。與已有飽和指令映射過程的不同點(diǎn)在于：擴(kuò)展的關(guān)鍵字不同，映射過程變量數(shù)據(jù)模式不同；映射過程相對單一簡潔。實(shí)驗(yàn)結(jié)果根據(jù)上節(jié)描述的方案和過程，基于版本實(shí)現(xiàn)了指令集中整數(shù)飽和加法的映射過程。版本支持?jǐn)?shù)據(jù)類型飽和算術(shù)指令，不支持整數(shù)和浮點(diǎn)數(shù)據(jù)類型飽和算術(shù)指令映