趙紫微 涂 航 劉 芹 李 莉 余 濤

（武漢大學國家網絡安全學院 武漢 430072）

計算機系統(tǒng)模擬器[1]是運行于宿主機上的軟件，用于模擬目標機器的硬件和軟件環(huán)境，便于使用者研究目標機器的架構與執(zhí)行過程，減少硬件成本.嵌入式領域對于模擬器的需求量較大，并且在可擴展性和精確度方面有較多要求.因此，如何基于現有的模擬器快速開發(fā)原型并且在保證正確性的同時具有較好的執(zhí)行效率是一個值得研究的問題.

目前的模擬器從精確度方面可以分為功能級、指令級、周期級.功能級保證其執(zhí)行結果與目標機器相同，不考慮執(zhí)行過程的精確性，在性能上表現最好，接近宿主機的執(zhí)行速度，大多使用二進制翻譯等技術提升性能，例如QEMU[2].指令級保證每條指令按順序全部執(zhí)行，不考慮指令周期和流水線的問題，大多使用即時編譯（just-in-time compilation, JIT）等技術提升性能.周期級保證指令周期精確，可以仿真指令流水線，執(zhí)行速度最慢，但提供更多執(zhí)行細節(jié)信息，例如gem5[3].考慮到嵌入式開發(fā)中對周期精確的需求，本文選擇基于gem5 進行研究.gem5 是一個開源的計算機架構模擬器，由密歇根大學的m5 項目和威斯康星大學的GEMS 項目合并而來，在學術界和工業(yè)界應用廣泛.gem5 是模塊化并以事件驅動的周期精確模擬器，可擴展性強.gem5 的CPU 模塊采用解釋執(zhí)行技術，其譯碼模塊和指令集實現獨立于CPU 模塊，可以與不同精確度的CPU 模型相結合.以不考慮訪存延遲和流水線的AtomicSimpleCPU 模型為例，主要有3 個步驟：取指、譯碼和執(zhí)行.其中，譯碼過程是由各個指令集架構中的譯碼模塊負責.

gem5 中的指令集描述語言可以半自動地生成指令集功能代碼，但需要開發(fā)者手動處理指令編碼的判斷并為指令編寫模板替換函數.對于復雜的指令編碼，手動處理指令編碼的判斷過于繁瑣并且難以得到性能最優(yōu)的實現.沒有統(tǒng)一的指令模板替換函數導致邏輯復雜且存在冗余，總體開發(fā)效率較低.gem5 在取指過程后會由譯碼模塊對指令編碼進行預解析，之后再調用函數解析完整的指令編碼，這2 個解析過程存在部分重復.此外，在實現指令集和譯碼模塊后還需要對模擬器進行功能測試，但一些指令集沒有提供公開的標準測試集，這種情況下開發(fā)者需要根據指令集文檔自行編寫測試程序.其中，測試用例的編寫依賴于指令操作數的取值范圍描述和指令的功能描述.因此，可以依據gem5 中所使用的指令集描述語言來生成功能測試中的部分數據，提高開發(fā)效率.

前人[4-5]提出了一些指令集描述方法和譯碼過程的優(yōu)化算法，但不易與現有模擬器相結合，也沒有針對gem5 進行優(yōu)化.目前還沒有一套為現有模擬器提供的從指令集描述到生成具體實現和測試用例的完整方案.這對于有自定義的指令需求的用戶來說，在模擬器性能和項目開發(fā)效率方面有所欠缺.

本文的工作難點在于根據統(tǒng)一的指令集描述語言提供一個完整的開發(fā)與測試方案，并針對gem5 優(yōu)化譯碼過程.用戶可以根據指令集文檔直觀地描述出所有指令的信息，得到自動生成的指令集實現代碼、譯碼模塊代碼和功能測試用例.

gem5 原本未支持Cortex-M3 指令集架構，本文實現了該指令集架構并引入了優(yōu)化.主要工作包括指令集功能實現和內存管理單元的修改，難點在于優(yōu)化譯碼決策樹和譯碼模塊，意義在于提供一種更高效的指令集實現方案以及增加gem5 對嵌入式芯片的仿真支持.

本文方案與gem5 原方案的流程比較如圖1 所示.本文方案包括3 個階段，首先是用詞法和語法分析指令集描述文件，之后是根據指令的編碼描述生成譯碼決策樹，最后是使用統(tǒng)一的模板替換規(guī)則生成指令功能代碼和譯碼模塊代碼.與原方案相比，本文方案重新設計了指令集描述文件格式，修改了模板替換的邏輯，增加了譯碼決策樹生成功能并優(yōu)化譯碼模塊.此改進的作用在于簡化指令定義，自動化生成譯碼決策樹和譯碼模塊代碼，優(yōu)化譯碼執(zhí)行時間，提升開發(fā)效率.

Fig.1 Comparison of our scheme and original gem5 scheme圖1 本文方案與gem5 原方案的比較

本文的主要貢獻包括3 個方面:

1）設計了一種指令集描述語言和一個基于gem5的指令集代碼生成方案.根據指令集的編碼描述和功能描述，自動為模擬器生成指令集和譯碼模塊代碼，提升模擬器性能和開發(fā)效率.

2）提出了一個針對gem5 優(yōu)化的譯碼決策樹構建算法.該算法基于前人的算法進行擴展，并減少了gem5 中指令編碼預解析階段的重復判斷，提升模擬器運行性能.

3）實現了一個指令集功能測試框架.根據指令的測試描述，使用框架中的模板為每條指令生成功能測試用例，在gem5 上運行測試程序并輸出測試報告.

1 相關工作

前人的研究[4-5]提到很多針對處理器或系統(tǒng)仿真的描述語言的研究可以用于生成指令集功能的描述，例如Pydgin[6], LISA[7], nML[8]，但這些不是針對譯碼過程和指令功能的描述，也不易結合到現有的模擬器實現中.本文方案主要基于gem5 的指令集描述語言進行擴展，部分指令描述的設計參考了上述描述語言.

目前一些研究提出了構造決策樹來優(yōu)化譯碼分支的方法[9-11]，但在處理復雜指令結構時存在一些不能成功構建決策樹的情況.Okuda 等人[12]基于前人工作提出了對于不規(guī)則指令編碼的譯碼分支優(yōu)化算法，解決了復雜指令結構處理中的問題，可以生成平均高度低且內存占用小的決策樹，并在ARM 和MIPS指令集上取得了較好的結果.此算法可以用于自動化構建處理器仿真[13]，此外還有研究分析了譯碼決策樹的開銷問題[14].本文基于此算法構造譯碼決策樹，并針對gem5 譯碼模塊做出優(yōu)化，構建多個決策子樹來配合gem5 的處理流程，提升譯碼模塊性能.

指令集功能測試用于檢測指令功能是否正確，例如檢查單條指令執(zhí)行前后的寄存器和內存的讀寫情況或者多條指令的處理器流水線情況[15]等.RISCV 提供了一套標準測試集[16]，通過模板構建測試用例，能夠測試單條指令的功能.本文搭建的指令功能測試框架中測試用例的設計參考了此測試集.

2 指令集描述

gem5 中已經實現了一個領域特定語言（domain specific language, DSL），用于描述指令集中各個指令的功能及其譯碼函數，文件后綴為.isa.在編譯過程中，項目構建工具SCons[17]會調用Python 腳本對所編譯的目標架構的*.isa 文件進行詞法和語法分析，從而生成包含指令定義和譯碼函數的C++文件，最后SCons 將這些生成的文件添加到編譯任務中.

在實際使用中，我們發(fā)現該指令集描述語言存在2 個問題：

1）譯碼函數主要由開發(fā)者手動編寫.當指令數量較多且復雜時開發(fā)效率不高，并且手動編寫的譯碼函數可能存在冗余，在執(zhí)行效率方面有待優(yōu)化.

2）用于生成C++代碼的模板替換邏輯和待替換的數據沒有分離.Python 腳本會使用函數exec()來處理這些字符串.然而這些模板替換邏輯非常類似，這種實現方式不僅增加了不必要的復雜性，而且不易維護.

本文參考了該指令集描述語言的實現，并提出了一種包含指令編碼和指令功能信息的指令集描述語言，可以自動生成譯碼函數并自動完成指令功能代碼與C++代碼模板的替換.此外，對于不公開提供功能測試套件的指令集或是添加了自定義指令的情況，考慮到自行編寫指令功能測試時很多所需的信息可以由指令集描述提供，本文方案允許標注操作數限制等指令測試所需的信息，支持生成指令的功能測試用例.

本文方案包括編碼描述、功能描述和測試描述3 部分.這里以ARM Cortex-M3 的AND 指令為例來說明，如圖2 所示.

2.1 編碼描述

編碼描述用于說明指令編碼的結構與限制，用于構造譯碼決策樹.本文方案將編碼抽象為由固定位段和可變位段組成的結構，其中可變位段的取值可能存在一些限制.下面結合實例來說明其具體實現.

指令編碼是一串由0、1 和小寫字母組成的字符串.其中，0 和1 表示指令編碼中取值確定的位，小寫字母表示指令編碼中取值可變的位.同一小寫字母必須相連，表示一個可變的位段.例如，指令t1_and_reg的編碼為0100000000mmmddd，說明第0 位和第2～9位為0，第1 位為1，第10～12 位為一個可變位段 {m}，第13～15 位為另一個可變位段 ci0yeuu.

對于不符合要求的編碼情況，使用EXCLUSION語句列出可變位段的所有例外表示，將其作為該指令編碼的排除條件.例如，指令t1_and_imm 的編碼排除了 {n}為13 到15 和 6gmsy0q為13 或15 的情況.

2.2 功能描述

功能描述用于說明指令功能的實現和標注信息，用于生成指令功能代碼和提供仿真所需的控制信息和計數信息.本文方案將功能抽象為由特定功能代碼和模板組成的結構.下面結合實例來說明其具體實現.

代碼塊由{{和}}來表示，在代碼塊中可變位段可以作為數值來使用，REPLACE_MAP 中定義替換詞可以在前后加上@作為代碼片段來使用.

指令構造函數代碼以代碼塊形式定義在指令編碼描述結束后，用于為指令基類定義的操作數變量根據實際編碼來賦值.例如，指令t1_and_imm 的基類為DataImm，其中定義了操作數寄存器的序號、立即數、其他參數和功能函數等.

指令功能函數代碼存放在一個字典結構中，代碼塊所對應的序號會作為參數傳入FORMAT 語句.FORMAT 語句用于處理C++模板替換過程，定義在構造函數描述之后.例如，CODE { 0: {{ inta=0; }} }說明指令功能代碼為inta=0，其對應序號為0.

FORMAT 語句會根據指令類型的格式從FORMAT_MAP 中得到對應的C++代碼模板和參數格式，之后通過字符串替換生成相應的指令類.例如，指令類型AND 的格式為PredProcessOp，其C++代碼模板為BasicDeclare, BasicConstructor, PredProcessExecute，分別用于指令類的聲明、構造函數和功能函數的生成,其參數格式為['process_code'].指令t1_and_imm 將[0, 3]傳入FORMAT 語句，即將序號為0 和3 的代碼拼接后的值作為process_code.

2.3 測試描述

測試描述用于說明指令功能測試的參數要求，用于輔助生成指令功能測試.本文方案將功能測試抽象為由測試參數和測試模板組成的結構.下面結合實例來說明其具體實現.

指令測試的所需的信息由TEST 語句負責處理，用于生成該指令的功能測試用例.TEST 語句的參數對應于該指令的匯編表示，例如指令t1_and_imm 的匯編表示包括可選的標記S和條件cond，以及2 個寄存器類型Rx 和1 個立即數類型Constant.類型Rx 和類型Constant 定義于TEST_MAP 中，設置了其取值范圍和函數名，在測試用例生成時會調用類型所對應的函數來生成數值.

3 譯碼決策樹生成

本節(jié)說明了譯碼決策樹生成過程中涉及的基本概念，并給出了譯碼決策樹生成算法的具體描述.本文方案對前人所提出的算法[12]進行了改進，并結合gem5的特性實現了針對性優(yōu)化.

3.1 基本概念

本節(jié)定義決策樹的輸入與輸出形式，以表1 中的譯碼項來說明基本概念.令指令集中的1 條指令編碼對應1 個譯碼項，算法的輸入為1 個譯碼項集合，算法的輸出為由該譯碼項集合生成的1 個譯碼決策樹.

Table 1 An Example of Decoding Entries表1 譯碼項示例

3.1.1 譯碼項

譯碼項e包括名稱m、編碼d和排除條件集合C，記為e=(m,d,C).其中，譯碼項的名稱和編碼是唯一的，排除條件可以為0 或多個，譯碼項集合記為E，E={e}.

本文方案將編碼定義為d∈{0,1,X}n.其中，X表示該位可以與0 或1 相匹配，用于表示可變位段，編碼長度為n位.給定一個位串s∈{0,1}n，定義位串s與編碼d的匹配規(guī)則為?i∈{0,1,…,n-1}，當且僅當s[i]=d[i]或d[i]=X時，位串s與編碼d匹配，記為s∈d.若該編碼所對應的譯碼項e無排除條件，則位串s與譯碼項e相匹配，記為s?e.例如，位串00001100匹配編碼00XXXX00.

3.1.2 譯碼項中的排除條件

為了能夠編碼更多指令，在設計指令集時某些編碼被添加了排除條件，即對編碼中的可變位段設置了取值限制.若位串的某些可變位段等于特定常數時，則與該編碼不匹配.

一個排除條件包括一個下標集合Iex和 一個排除項pex，記為(Iex,pex).其中，下標是從小到大排列，且與排除項的各位按序一一對應，即將應排除的值的第i位記為pex[i′].本文方案定義位串s使得排除條件(Iex,pex)成立的判定規(guī)則為：?i∈Iex，當且僅當s[i]=pex[i′]時，位串s使得排除條件(Iex,pex)成立，記為exclude(s,(Iex,pex)).例如，譯碼項的排除條件({6,7},00)表示應排除第6 位和第7 位都為0的位串.

因此，本文方案定義位串s與具有排除條件的譯碼項ec=(mc,dc,Cc)的匹配規(guī)則為：當且僅當s∈dc且?(Ic,pc)∈Cc,?exclude(s,(Ic,pc))時，位串s與譯碼項ec相匹配，記為s?ec.例如，位串10100000雖然與名稱為I 的譯碼項和名稱為J 的譯碼項的編碼匹配，但由于名稱為I 的譯碼項的排除條件({6,7},00)成立，所以該位串是與名稱為J 的譯碼項匹配.

3.1.3 譯碼決策樹

譯碼過程是通過逐步查詢位串中特定位段的值來獲得該位串所匹配的譯碼項.本文將這個過程用譯碼決策樹來表示，記為T=(VT,ET).其中，VT表示節(jié)點的集合，ET表示邊的集合.每個節(jié)點有唯一標識符，記為nid.本文將節(jié)點分為內部節(jié)點和葉節(jié)點.內部節(jié)點表示譯碼選擇分支，包含一個特定位的下標集合I和一個元組集合，每個元組由標簽和子節(jié)點組成，記為(p,vchild).其中，下標集合中的元素從小到大排列，且與標簽的各位按次序一一對應，l為下標集合的長度，標簽p∈{0,1}l為葉節(jié)點，其表示譯碼查詢所匹配的最終結果，包含一個譯碼項.

譯碼決策樹示例如圖3 所示.內部節(jié)點由包含其標識符nid和下標集合I的方框表示，邊框為弧線表示該節(jié)點在優(yōu)化過程中被修改過.葉節(jié)點由包含其標識符nid、譯碼項名稱m和譯碼項編碼d的方框表示.每條從內部節(jié)點所出的邊的標簽p和所指向的子節(jié)點vchild由該內部節(jié)點中的各個元組(p,vchild)得出.

Fig.3 An example of a decoding decision tree圖3 譯碼決策樹示例

3.2 算法描述

本節(jié)詳細說明了構造譯碼決策樹的算法.首先，分析了前人的工作[12]并提出了本文方案的譯碼決策樹構造算法，擴展了前人對于內部節(jié)點的構造方法并增加了2 個優(yōu)化策略.此外，本文方案還針對gem5的譯碼過程對譯碼決策樹和生成的代碼做了優(yōu)化.最后，給出一個示例來說明每種優(yōu)化策略所針對的情況和優(yōu)化效果.

3.2.1 基礎算法Okuda 等人[12]的算法主要包含3 個過程：1) 過程MakeTree根據給定的譯碼項集合E遞歸創(chuàng)建譯碼決策樹的節(jié)點及其子節(jié)點.2) 過程MakeNode創(chuàng)建一個無排除條件的內部節(jié)點，并將譯碼項集合E劃分為多個子譯碼項集合，為每個子譯碼項集合創(chuàng)建子譯碼決策樹.3) 過程MakeConditionNode創(chuàng)建一個有排除條件的內部節(jié)點，并將譯碼項集合根據是否符合排除條件劃分為2 個子譯碼項集合，分別為這2 個子譯碼項集合創(chuàng)建子譯碼決策樹.此外，該算法是通過與指令長度相等的編碼格式來劃分子譯碼項集合.例如，使用以0 開頭和以1 開頭的4 位編碼格式來劃分包含編碼為0101 和1 101 的譯碼項集合.

Okuda 等人[12]的算法存在2 個問題：

1）過程MakeConditionNode在劃分子譯碼項集合時僅根據其是否符合排除條件分為2 類.對于不符合排除條件但也可被區(qū)分的子譯碼項來說，可能會再次處理該相同位段，導致譯碼決策樹的高度增加.

2）算法根據與指令長度相等的編碼格式來劃分譯碼項集合，不便于添加額外的優(yōu)化策略，例如處理個別位的合并或移除操作.

本文方案的算法基于Okuda 等人[12]的算法做了擴展和優(yōu)化.在構造內部節(jié)點時，本文方案使用下標集合I所確定的多個標簽來劃分譯碼項集合，每個譯碼項根據其編碼在該下標集合I處的取值情況劃分到不同的標簽p下.本文方案為每個標簽的譯碼項集合構造譯碼決策樹，并將其作為該內部節(jié)點的子樹.此外，本文方案修改了過程MakeConditionNode的實現，使其能夠根據排除條件的下標集合Iex來區(qū)分多個子譯碼項集合.并且，本文方案以能夠區(qū)分出最多子譯碼項集合的下標集合I來創(chuàng)建節(jié)點，這樣可以避免重復判斷相同位段的值并減少譯碼決策樹的高度.

3.2.2 擴展算法

本文方案的算法對過程MakeNode和過程Make-ConditionNode做了擴展和優(yōu)化，見算法1.

算法1.譯碼決策樹構建算法.

過程MakeNode用于創(chuàng)建一個不使用排除條件的內部節(jié)點.首先，過程GetS igni ficantBits根據譯碼項集合E找出一個下標集合Isig，使得所有譯碼項可以用標簽區(qū)分.過程S elOptBits根據下標集合劃分各個標簽對應的子譯碼項集合，將結果記為子節(jié)點信息In fo.之后檢查是否可以通過擴增下標集合以減少譯碼決策樹高度，如果可以優(yōu)化，則更新下標集合Isig和子節(jié)點信息In fo.過程MakeChild會調用過程Make-Tree并根據子節(jié)點信息和尚未處理的下標集合來遞歸創(chuàng)建子節(jié)點譯碼決策樹，將結果記為Tchild.如果創(chuàng)建的子節(jié)點譯碼決策樹中存在已優(yōu)化的節(jié)點，則需要通過過程ReselOptBits再次更新下標集合Isig、子節(jié)點信息In fo和子節(jié)點譯碼決策樹Tchild.最后，過程CreateNode創(chuàng)建此內部節(jié)點，記錄其下標集合Isig和子節(jié)點譯碼決策樹Tchild，并設置節(jié)點類型是否為已優(yōu)化節(jié)點.圖4 展示了優(yōu)化后的效果，將下標2 增加到根節(jié)點的判斷中，減少了名稱為G 的譯碼項和名稱為M 的譯碼項所在的層數.

Fig.4 The decoding decision tree optimized by process MakeNode圖4 使用過程MakeNode 優(yōu)化的譯碼決策樹

過程MakeConditionNode用于創(chuàng)建使用排除條件的內部節(jié)點.首先，過程S elConditionBits根據譯碼項集合E從各個譯碼項的排除條件中找出一個排除條件(Iex,pex)，使得根據此下標集合Iex劃分得到的標簽數量最多，將結果記為子節(jié)點信息In fo.這里沒有使用過程MakeNode中的優(yōu)化方法是因為使用排除條件所得到的標簽中一定包含default，之前的優(yōu)化不適用于這種情況.之后執(zhí)行過程MakeChild，將結果記為Tchild.最后，過程CreateConditionNode創(chuàng)建此內部節(jié)點，記錄其下標集合Iex和子節(jié)點譯碼決策樹Tchild，并設置節(jié)點類型是否為使用排除條件的節(jié)點.圖5 說明了Okuda 等人[12]的算法對于條件節(jié)點的處理，僅判斷是否滿足排除條件，未考慮相同下標對應多個可區(qū)分編碼的情況，導致冗余判斷.本文使用下標集合來劃分子譯碼項集合，因此在確定下標集合后，其劃分方式與常規(guī)內部節(jié)點相同，如圖3 所示.

Fig.5 The condition node of Okuda et al’s algorithm圖5 Okuda 等人所提算法的條件節(jié)點

此外，本文方案新增了過程OptimizeTree、過程OptimizeNode、過程FixNode和過程FixTree對譯碼決策樹進行整體優(yōu)化和調整，見算法2.

算法2.譯碼決策樹優(yōu)化算法.

過程OptimizeTree和過程OptimizeNode用 于前序遍歷譯碼決策樹中的節(jié)點并做優(yōu)化.首先，過程Get-OptimizableBits檢查節(jié)點N的內部子節(jié)點的下標集合Isig是否僅包含1 個元素，將滿足條件的下標集合取并集作為待選下標集合.遍歷待選下標集合，檢查其他各個內部子節(jié)點下的所有譯碼項是否在該下標處取值相同.如果存在這樣的下標，則將其加入到Iopt中.之后，對于節(jié)點N的每個葉子子節(jié)點Nleaf，使用過程GetLeaf Pattern修改指向此Nleaf的標簽，將結果更新到Tchild中.遍歷下標集合Iopt，對節(jié)點N的每個內部子節(jié)點Ninner用過程GetInnerPattern確認是否需要移除此內部節(jié)點，并修改指向此Ninner或其子節(jié)點的標簽，將結果更新到Tchild中.最后過程UpdateOptimizableNode修改節(jié)點N的下標集合為Iopt，更新子節(jié)點譯碼決策樹Tchild，并設置節(jié)點類型是否為已優(yōu)化節(jié)點.圖6 展示了優(yōu)化后的效果，將下標4 增加到2 號節(jié)點的判斷中，減少了名稱為C 的譯碼項和名稱為D 的譯碼項所在的層數.

Fig.6 The decoding decision tree optimized by process OptimizeTree based on fig.4圖6 在圖4 的基礎上使用過程OptimizeTree優(yōu)化的譯碼決策樹

過程FixTree和過程FixNode與前2 個過程類似，用于修正指向譯碼決策樹中葉子節(jié)點的邊，將重復分支的標簽合并為default.圖7 展示了優(yōu)化后的效果，由于根節(jié)點下的分支數已達到最大且僅有名稱為A的譯碼項對應多個標簽，所以本文方案將這些標簽合并為default.

Fig.7 The decoding decision tree optimized by process FixTree based on fig.6圖7 在圖6 的基礎上使用過程FixTree優(yōu)化的譯碼決策樹

3.2.3 gem5 中的譯碼過程

在gem5 的實現中，CPU 在譯碼階段會先將取指階段得到的數據傳給譯碼模塊，然后調用譯碼模塊來解析指令并得到一個基類指針，在執(zhí)行階段會調用其所指向的具體指令對象的執(zhí)行函數，具體處理流程如圖8 所示.

Fig.8 The decode and execute processes in gem5圖8 gem5 中的譯碼和執(zhí)行流程

譯碼模塊中的指令解析過程分為2 個階段：預解析階段（圖8 ①）和譯碼階段（圖8 ②）.首先，預解析階段的函數moreBytes() 會根據大小端和指令長度對取指階段得到的數據塊進行處理，得到符合譯碼要求的具體指令位串.之后，譯碼階段會調用譯碼函數對該指令位串進行解析.其中，譯碼函數的源文件是根據指令集描述語言在編譯過程中生成的，其函數體為一個多層嵌套的switch-case 結構.

指令長度是根據位串中特定位的值來判斷，這個過程與之后譯碼函數中的操作存在重復，即預解析階段和譯碼階段都會對同一段指令編碼進行判斷.以Cortex-M3 指令集為例，16 位Thumb 指令和32 位Arm 指令是由指令編碼的前5 位來區(qū)分的，因此預解析階段和譯碼階段都會判斷這前5 位.此外，條件指令IT 因為其條件執(zhí)行功能涉及對譯碼模塊的操作，所以會在預解析階段中被完整解析，但在之后的譯碼階段仍會被再次解析以獲得一個指向該指令對象的指針.

為了解決上述問題，本文方案將原方案的譯碼函數拆分為多個譯碼函數，并使用函數指針優(yōu)化調用過程.具體來說，本文方案的算法會根據指令集描述文件中設置的指令長度下標集合及其取值情況來構造多個譯碼決策樹，從而生成多個譯碼函數.此外，本文方案的算法會自動生成預解析階段所需的指令長度判斷函數，以便根據判斷結果選擇對應的譯碼函數.

4 測試用例生成

本文方案搭建了一個對指令進行功能測試的框架，能夠根據指令集描述為每條指令生成功能測試用例，并在gem5 上運行所生成的測試程序得到測試報告.該框架主要包括3 部分：操作數數據生成、期望值數據計算和測試程序模板.

以ARM Cortex-M3 的AND 指令為例，其操作數生成和期望值計算見算法3.該指令的匯編表示有2 種，即AND{S}{cond}Rn,#constant和AND{S}{cond}Rn,Rm,shi ft.其中，S表示是否更新狀態(tài)位，cond表示執(zhí)行的條件，Rn表示寄存器，#constant表示滿足特定格式的立即數，Rm和shi ft表示寄存器及其移位信息.

算法3.功能測試用例生成算法.

輸入：指令測試描述info、測試范圍range和測試用例數量num；

輸出：測試用例列表G.

過程GenData(info,range,num)

過程GenData用于生成操作數數據，根據指令測試描述info、測試范圍range和測試用例數量num來隨機生成操作數，并在邊界附近多生成一些值，之后調用過程GenExpAND生成期望值expects，最后返回測試用例列表G.

過程GenExpAND用于生成期望值數據，根據指令測試描述info和操作數ops來計算期望值expects，最后返回結果.

此外，本文方案準備了一系列測試程序模板，以宏的方式組織匯編指令，能夠為每條指令生成相應的匯編文件作為測試程序.每個用例以宏的方式呈現，例如TEST_AND_R_OP2C(testnum,inst,expExec,expRes,expApsr,Apsr,Rn,Constant)是用于AND 指令的第1 種匯編表示的宏，參數包括用例編號、被測指令、期望值和操作數.

5 實驗結果

本文實驗環(huán)境的CPU 為Intel Core i5-10400 @2.90 GHz，內存為32 GB，系統(tǒng)為Linux Mint 20.1 Kernel 5.4.0-89-generic.本文的gem5 配置為系統(tǒng)調用仿真（system call emulation, SE）模式，CPU 模型為Atomic-SimpleCPU，編譯版本為fast.本文方案中的指令集描述語言使用SLY[18]作為詞法和語法分析工具①gem5 原詞法和語法分析工具為PLY（Python Lex-Yacc）, SLY（Sly Lex-Yacc）是其新版本.，并且修改了gem5 的編譯腳本，將本文方案整合到項目的構建過程中.

實驗選擇Cortex-M3 指令集作為待描述的指令集，該指令集在gem5 項目中未做實現.實驗分別使用gem5 原方案與本文方案實現該指令集，并比較這2 種方案的性能以及所生成的代碼的運行性能.此外，在實驗前使用第4 節(jié)的功能測試框架為其生成了指令功能測試用例并確保其能正確執(zhí)行，即保證所實現的Cortex-M3 指令集的譯碼和執(zhí)行過程是功能正確的.

5.1 方案性能比較

指令集中每條指令編碼的查找路徑的長度是在譯碼決策樹中根節(jié)點到其所對應葉節(jié)點的邊數，即葉節(jié)點v在譯碼決策樹T中的高度，記為HT(v).將各譯碼決策樹中葉節(jié)點高度的平均值記為，將譯碼決策樹集合中所有葉節(jié)點高度的平均值記為.

比較gem5 原方案與本文方案所生成的譯碼決策樹高度，結果如表2 所示.Cortex-M3 指令集共有226 個指令編碼.原方案生成的譯碼決策樹中葉節(jié)點的最大高度為10，最小高度為3，總平均高度為5.52.本文方案共生成4 個譯碼決策樹和1 個IT 指令的譯碼函數，總平均高度為2.87.其譯碼范圍是根據預解析階段所處理的指令前5 位取值以及是否為IT 指令來劃分的，表2 中標明了各個譯碼決策樹負責處理的譯碼范圍.其中，16 位指令的譯碼決策樹包含指令編碼數量最多，32 位指令（以11101 開頭）的譯碼決策樹的平均高度最大.與依賴開發(fā)者手動構造譯碼函數的原方案相比，本文方案在譯碼決策樹高度方面的優(yōu)化效果較好，并且很大程度上提升了開發(fā)效率.

Table 2 Comparison of the Height of the Generated Decoding Decision Tree Between Two Methods Under Cortex-M3表2 在Cortex-M3 指令集下2 種方案所生成的譯碼決策樹高度的比較

此外，統(tǒng)計這2 種方案生成譯碼決策樹及其C++源文件的時間和編譯后的可執(zhí)行文件gem5.fast 的代碼大小，結果如表3 所示.原方案需要開發(fā)者手動編寫譯碼決策樹，并且需要將模板替換邏輯與指令定義寫在同一指令集描述文件中，在解析的同時處理替換過程，耦合度較高.本文方案僅將指令定義寫在指令集描述文件中，之后根據編碼信息自動生成譯碼決策樹和C++源文件，所用的總時間比原方案減少了約64%，代碼大小減少了約407 KB.

5.2 在gem5 中的運行情況

在gem5 中運行一些測試程序并比較2 種方案的運行性能.實驗使用的測試程序來自Embench[19]，這是一個面向嵌入式設備的開源測試集，它包含22 個測試程序，支持對真實機器和模擬器的測試.該測試集原本是通過遠程調試器來獲取測試函數前后的指令周期數來評估處理器速度，而本文所研究的譯碼模塊優(yōu)化不影響模擬器中的周期數，所以我們改為獲取測試函數前后的實際時間來評估模擬器譯碼模塊的性能，即通過shell 命令獲取宿主機時間.為減少額外操作對時間的影響，我們將默認的測試循環(huán)次數由1 改為10，

每個用例用時大約在10 s 左右.此外，gem5 原本使用了一個譯碼表來緩存相同地址或相同指令編碼的譯碼結果.由于實驗所用的測試程序都依賴于循環(huán)，并且在開始計時前會先運行幾輪來預熱緩存，導致gem5 實際運行時2 種方案幾乎沒有區(qū)別.這與本文實驗目的不符，因此我們在測試時關閉了譯碼緩存功能.

測試結果如圖9 所示，原方案平均用時10.24 s，本文方案平均用時8.91 s，比原方案減少了大約13%.

Fig.9 Execution performance of two methods in gem5 Under Cortex-M3圖9 在Cortex-M3 指令集下2 種方案在gem5 中運行性能

5.3 方案效果分析

本文方案的譯碼決策樹生成算法采用劃分編碼位段的方式，通過計算位段的匹配情況和使用多個優(yōu)化策略來構建樹的節(jié)點，從而減少譯碼過程的時間開銷.

譯碼過程的搜索時間開銷與譯碼決策樹的高度呈正相關.樹的每個內部節(jié)點所處理的位數n決定了該節(jié)點的子節(jié)點數量上限 2n.對于相同的指令數量，樹中內部節(jié)點指向新子節(jié)點的分支數量越多，樹的高度越低.因此在樹的構造過程中需要充分考慮指令長度和編碼限制條件，處理節(jié)點之間的合并優(yōu)化.

為進一步說明改進效果，我們使用本文方案為RV64GC 指令集生成了譯碼決策樹并與gem5 原方案已實現的譯碼函數做比較，結果如表4 所示.RV64GC指令集的編碼設計較為規(guī)整，較少使用編碼的排除條件，因此其譯碼決策樹的高度整體較為平均.RV64GC 實驗結果與Cortex-M3 類似，本文方案有效降低了譯碼決策樹的最大高度并且優(yōu)化了平均高度.

Table 4 Comparison of the Height of the Generated Decoding Decision Tree Between Two Methods Under RV64GC表4 在RV64GC 指令集下2 種方案對于所生成的譯碼決策樹高度的比較

6 討 論

本文方案支持使用gem5 中提供的接口函數和類型定義（如向量操作），可以用于實現其他指令集架構，例如MIPS 和Cortex-A 等.從RV64GC 的實驗結果可以看出，自動化生成和優(yōu)化的預解析階段的輔助函數和譯碼決策樹可以在一定程度上降低譯碼決策樹的平均高度，提升執(zhí)行效率.此外，本文方案的指令集描述文件更易被編寫與修改，開發(fā)效率較高.

本文方案的編碼描述和譯碼決策樹生成算法具有通用性，能夠應用于指令譯碼過程，而功能描述和代碼生成階段則與模擬器的具體實現關系緊密.若要將本文方案推廣到其他模擬器，則還需從實現角度考慮模擬器是否可以采用這種譯碼和執(zhí)行流程，以及這種模板替換策略能否與模擬器其他模塊適配.

7 結 論

本文方案解決了模擬器的指令集實現及其功能測試的開發(fā)效率問題并提升了gem5 譯碼模塊的性能，為添加新指令集或自定義擴展指令的開發(fā)與測試提供了一套完整方案.本文方案設計的指令集描述中定義了指令集的編碼描述、功能描述和測試描述，用于生成模擬器的譯碼模塊代碼、指令集實現代碼和指令功能測試用例.本文提出了一個針對gem5優(yōu)化的譯碼決策樹構造算法和一個指令功能測試框架.該算法使用指令的特定位和排除條件位來判斷指令編碼，并且允許根據gem5 指令預解析階段的條件劃分各個決策樹的范圍，從而降低譯碼決策樹的平均高度并且減少了原方案中的重復判斷，提升執(zhí)行性能.此外，該指令功能測試框架可以根據指令集描述生成指令功能測試用例，提升開發(fā)效率.

作者貢獻聲明：趙紫微為論文工作的主要完成人，負責實驗設計與實施、論文撰寫；涂航和劉芹審閱論文的內容并提出意見；余濤協(xié)助論文功能測試的軟件實現；李莉對論文提出修改意見，完善論文思路和實驗設計，負責論文審校.