針對(duì)gem5 指令集實(shí)現(xiàn)及其功能測試的自動(dòng)代碼生成

趙紫微 涂 航 劉 芹 李 莉 余 濤

（武漢大學(xué)國家網(wǎng)絡(luò)安全學(xué)院 武漢 430072）

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

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

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

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

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

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

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

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

本文的主要貢獻(xiàn)包括3 個(gè)方面:

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

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

3）實(shí)現(xiàn)了一個(gè)指令集功能測試框架.根據(jù)指令的測試描述，使用框架中的模板為每條指令生成功能測試用例，在gem5 上運(yùn)行測試程序并輸出測試報(bào)告.

1 相關(guān)工作

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

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

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

2 指令集描述

gem5 中已經(jīng)實(shí)現(xiàn)了一個(gè)領(lǐng)域特定語言（domain specific language, DSL），用于描述指令集中各個(gè)指令的功能及其譯碼函數(shù)，文件后綴為.isa.在編譯過程中，項(xiàng)目構(gòu)建工具SCons[17]會(huì)調(diào)用Python 腳本對(duì)所編譯的目標(biāo)架構(gòu)的*.isa 文件進(jìn)行詞法和語法分析，從而生成包含指令定義和譯碼函數(shù)的C++文件，最后SCons 將這些生成的文件添加到編譯任務(wù)中.

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

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

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

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

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

2.1 編碼描述

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

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

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

2.2 功能描述

功能描述用于說明指令功能的實(shí)現(xiàn)和標(biāo)注信息，用于生成指令功能代碼和提供仿真所需的控制信息和計(jì)數(shù)信息.本文方案將功能抽象為由特定功能代碼和模板組成的結(jié)構(gòu).下面結(jié)合實(shí)例來說明其具體實(shí)現(xiàn).

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

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

指令功能函數(shù)代碼存放在一個(gè)字典結(jié)構(gòu)中，代碼塊所對(duì)應(yīng)的序號(hào)會(huì)作為參數(shù)傳入FORMAT 語句.FORMAT 語句用于處理C++模板替換過程，定義在構(gòu)造函數(shù)描述之后.例如，CODE { 0: {{ inta=0; }} }說明指令功能代碼為inta=0，其對(duì)應(yīng)序號(hào)為0.

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

2.3 測試描述

測試描述用于說明指令功能測試的參數(shù)要求，用于輔助生成指令功能測試.本文方案將功能測試抽象為由測試參數(shù)和測試模板組成的結(jié)構(gòu).下面結(jié)合實(shí)例來說明其具體實(shí)現(xiàn).

指令測試的所需的信息由TEST 語句負(fù)責(zé)處理，用于生成該指令的功能測試用例.TEST 語句的參數(shù)對(duì)應(yīng)于該指令的匯編表示，例如指令t1_and_imm 的匯編表示包括可選的標(biāo)記S和條件cond，以及2 個(gè)寄存器類型Rx 和1 個(gè)立即數(shù)類型Constant.類型Rx 和類型Constant 定義于TEST_MAP 中，設(shè)置了其取值范圍和函數(shù)名，在測試用例生成時(shí)會(huì)調(diào)用類型所對(duì)應(yīng)的函數(shù)來生成數(shù)值.

3 譯碼決策樹生成

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

3.1 基本概念

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

Table 1 An Example of Decoding Entries表1 譯碼項(xiàng)示例

3.1.1 譯碼項(xiàng)

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

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

3.1.2 譯碼項(xiàng)中的排除條件

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

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

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

3.1.3 譯碼決策樹

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

譯碼決策樹示例如圖3 所示.內(nèi)部節(jié)點(diǎn)由包含其標(biāo)識(shí)符nid和下標(biāo)集合I的方框表示，邊框?yàn)榛【€表示該節(jié)點(diǎn)在優(yōu)化過程中被修改過.葉節(jié)點(diǎn)由包含其標(biāo)識(shí)符nid、譯碼項(xiàng)名稱m和譯碼項(xiàng)編碼d的方框表示.每條從內(nèi)部節(jié)點(diǎn)所出的邊的標(biāo)簽p和所指向的子節(jié)點(diǎn)vchild由該內(nèi)部節(jié)點(diǎn)中的各個(gè)元組(p,vchild)得出.

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

3.2 算法描述

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

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

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

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

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

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

3.2.2 擴(kuò)展算法

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

算法1.譯碼決策樹構(gòu)建算法.

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

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

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

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

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

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

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

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

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

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

3.2.3 gem5 中的譯碼過程

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

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

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

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

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

4 測試用例生成

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

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

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

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

輸出：測試用例列表G.

過程GenData(info,range,num)

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

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

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

5 實(shí)驗(yàn)結(jié)果

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

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

5.1 方案性能比較

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

比較gem5 原方案與本文方案所生成的譯碼決策樹高度，結(jié)果如表2 所示.Cortex-M3 指令集共有226 個(gè)指令編碼.原方案生成的譯碼決策樹中葉節(jié)點(diǎn)的最大高度為10，最小高度為3，總平均高度為5.52.本文方案共生成4 個(gè)譯碼決策樹和1 個(gè)IT 指令的譯碼函數(shù)，總平均高度為2.87.其譯碼范圍是根據(jù)預(yù)解析階段所處理的指令前5 位取值以及是否為IT 指令來劃分的，表2 中標(biāo)明了各個(gè)譯碼決策樹負(fù)責(zé)處理的譯碼范圍.其中，16 位指令的譯碼決策樹包含指令編碼數(shù)量最多，32 位指令（以11101 開頭）的譯碼決策樹的平均高度最大.與依賴開發(fā)者手動(dòng)構(gòu)造譯碼函數(shù)的原方案相比，本文方案在譯碼決策樹高度方面的優(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)計(jì)這2 種方案生成譯碼決策樹及其C++源文件的時(shí)間和編譯后的可執(zhí)行文件gem5.fast 的代碼大小，結(jié)果如表3 所示.原方案需要開發(fā)者手動(dòng)編寫譯碼決策樹，并且需要將模板替換邏輯與指令定義寫在同一指令集描述文件中，在解析的同時(shí)處理替換過程，耦合度較高.本文方案僅將指令定義寫在指令集描述文件中，之后根據(jù)編碼信息自動(dòng)生成譯碼決策樹和C++源文件，所用的總時(shí)間比原方案減少了約64%，代碼大小減少了約407 KB.

5.2 在gem5 中的運(yùn)行情況

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

每個(gè)用例用時(shí)大約在10 s 左右.此外，gem5 原本使用了一個(gè)譯碼表來緩存相同地址或相同指令編碼的譯碼結(jié)果.由于實(shí)驗(yàn)所用的測試程序都依賴于循環(huán)，并且在開始計(jì)時(shí)前會(huì)先運(yùn)行幾輪來預(yù)熱緩存，導(dǎo)致gem5 實(shí)際運(yùn)行時(shí)2 種方案幾乎沒有區(qū)別.這與本文實(shí)驗(yàn)?zāi)康牟环虼宋覀冊(cè)跍y試時(shí)關(guān)閉了譯碼緩存功能.

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

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

5.3 方案效果分析

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

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

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

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

6 討 論

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

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

7 結(jié) 論

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

作者貢獻(xiàn)聲明：趙紫微為論文工作的主要完成人，負(fù)責(zé)實(shí)驗(yàn)設(shè)計(jì)與實(shí)施、論文撰寫；涂航和劉芹審閱論文的內(nèi)容并提出意見；余濤協(xié)助論文功能測試的軟件實(shí)現(xiàn)；李莉?qū)φ撐奶岢鲂薷囊庖姡晟普撐乃悸泛蛯?shí)驗(yàn)設(shè)計(jì)，負(fù)責(zé)論文審校.