基于圖神經(jīng)網(wǎng)絡(luò)的BWDSP指令選擇方法優(yōu)化研究

侯 璇，鳳維杰，鄭啟龍，2

1(中國科學(xué)技術(shù)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230026) 2(中國科學(xué)技術(shù)大學(xué) 高性能計算安徽省重點實驗室，合肥 230026) E-mail：hx970922@mail.ustc.edu.cn

1 引 言

BWDSP是由中國電子科技集團(tuán)第三十八研究所研制的一款數(shù)字信號處理器[1]，該處理器采用VLIW結(jié)構(gòu)以及SIMD數(shù)據(jù)格式，能夠在單周期內(nèi)并行執(zhí)行16條32位的指令.BWDSP采用了可讀性強(qiáng)的匯編指令系統(tǒng)，同時BWDSP提供了一套豐富的指令集，總共有7類約600余條指令，且通過指令緩沖池技術(shù)能使指令在存儲器中按照16字緊湊排列，節(jié)省存儲空間，減少分支程序的開銷.指令選擇在編譯過程中的作用是從目標(biāo)處理器的指令集中選擇指令用以實現(xiàn)與中間表示相同的功能.中間表示，Intermediate Representation，簡稱為IR，是一種與源代碼和目標(biāo)平臺機(jī)器架構(gòu)均無關(guān)的通用表示.常見的編譯系統(tǒng)可將支持的高級語言編寫的源代碼生成與后端機(jī)器架構(gòu)無關(guān)的中間表示，再通過特定平臺下的機(jī)器代碼轉(zhuǎn)換方法將中間表示轉(zhuǎn)換為相應(yīng)的機(jī)器碼.通常，從源代碼到機(jī)器碼的轉(zhuǎn)換過程可劃分為多個轉(zhuǎn)換階段，而主要作用對象就是IR，每個階段對IR不斷地優(yōu)化，得到不同階段優(yōu)化后的IR，最終經(jīng)過匯編和鏈接生成目標(biāo)機(jī)器的可執(zhí)行的機(jī)器碼.指令選擇也是轉(zhuǎn)換過程中可拆分、可優(yōu)化的一個階段，在編譯后端的代碼生成中是非常重要的環(huán)節(jié)，選擇出的指令的質(zhì)量高低決定程序的執(zhí)行代價的優(yōu)劣，對后端生成的機(jī)器碼有著非常重大的影響.因此，良好的指令選擇策略對現(xiàn)階段編譯系統(tǒng)至關(guān)重要.目前，一些常見的編譯器如GCC[2]、BURG[3]、GNU LIGHTING[4]、PCC[5]、HBURG[6]、JBURG[7]、CODESYN[8]、LLVM[9]、CBURG[10]、CHESS[11]、JHSC[12]等所采用的指令選擇策略依然是采用傳統(tǒng)的方法.如宏擴(kuò)展[13]、樹覆蓋[14]、DAG覆蓋[15]、圖覆蓋[16].表1為BWDSP指令集分類.

表1 BWDSP指令集分類Table 1 BWDSP instruction set classification

這些方法在現(xiàn)有的編譯器中有著非常良好的應(yīng)用，也是相對簡單成熟的.但就每一種方法而言都有其不足.對于宏擴(kuò)展，宏擴(kuò)展策略的優(yōu)點是簡單直觀：1)由于宏擴(kuò)展策略受限于每次只能擴(kuò)展單個IR語句，導(dǎo)致宏擴(kuò)展策略所選擇的指令的質(zhì)量較低；2)宏擴(kuò)展的可移植性較差，對新的高級語言則需重寫宏；3)宏一般使用專用語言編寫，因此宏難以維護(hù)和擴(kuò)展.對于圖覆蓋策略，該策略是對宏擴(kuò)展的改進(jìn)與拓展，在該策略中，IR被表示為圖，目標(biāo)機(jī)的機(jī)器指令也同樣被表示為圖結(jié)構(gòu).Pozzi[17]等人提出的基于圖匹配的方法在構(gòu)建IR時某些公共子表達(dá)式要么必須被切分成更小的子表達(dá)式，要么被重復(fù)計算.這將導(dǎo)致難以選擇更高效的指令.其中，大部分工作都是基于控制流圖(Control Flow Graph，簡稱為CFG)，或者包含數(shù)據(jù)流圖信息的有向無環(huán)圖(Directed Acyclic Graph，簡稱為DAG)，局部不完整的IR上進(jìn)行的，這也導(dǎo)致了所選擇出的指令在質(zhì)量和結(jié)構(gòu)上并不理想.

BWDSP的指令格式如式(1)所示，表示無符號定點16位加減法同時運算指令，{Macro}指所使用的宏，H表示選擇高16位，Rm_n表示雙源寄存器，U表示無符號運算，該指令將Rm和Rn同時加減后，送到雙源寄存器Rm_n中.

{Macro}HRm_n=HRm+/-HRn(U)

(1)

BWDSP內(nèi)部有4個基本執(zhí)行宏，每個宏包含15個部件，包含8個ALU、4個MUL、2個SHF、1個SPU.而指令主要由運算部件的數(shù)據(jù)運算、存儲器間同運算部件之間的數(shù)據(jù)調(diào)用或傳輸、存儲器間的數(shù)據(jù)調(diào)用或傳輸?shù)冉M成.由式(1)也可看到，對于在同一執(zhí)行行內(nèi)一次執(zhí)行的指令組，所選用指令的處理效率越高，其性能提升也越明顯.因此指令選擇的優(yōu)化在后端代碼優(yōu)化中的影響也是非常大的.

目前，圖神經(jīng)網(wǎng)絡(luò)，Graph Neural Networks[18]，簡稱為GNN，在處理非結(jié)構(gòu)化數(shù)據(jù)上顯示出越來越強(qiáng)大的優(yōu)勢.一方面，它能夠理解節(jié)點與節(jié)點之間的依賴關(guān)系，另一方面，與傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)模型不同的是，GNN能夠通過鄰域節(jié)點的信息聚合來更新節(jié)點的隱藏狀態(tài).常應(yīng)用于結(jié)構(gòu)化數(shù)據(jù)的場景和非結(jié)構(gòu)化場景中，其他應(yīng)用場景包括基于圖的NP-hard問題[19-21]等.

因此，現(xiàn)階段采用最廣泛的圖覆蓋策略為基礎(chǔ)，同時現(xiàn)代編譯器基于圖表示的指令選擇可以看作是一種圖形變換[22].因此，本文提出一種基于GNN的方法，收集完整的IR信息即將CFG與DAG結(jié)合起來構(gòu)成數(shù)據(jù)控制流圖，Control Data Flow Graph，簡稱為CDFG，以建立IR圖集.再通過對GNN模型的搭建與訓(xùn)練，用以完成基于圖集的相似性搜索，找到代價相對較小的復(fù)雜機(jī)器指令圖集合，最終通過模式匹配找到執(zhí)行代價最小的指令，結(jié)合BWDSP的VLIW指令架構(gòu)達(dá)到降低指令執(zhí)行代價的目的.本文基于LLVM及BWDSP模擬器平臺，具體的設(shè)計實現(xiàn)如下：1)建模源程序IR的CDFG；2)建模BWDSP指令集為指令圖集；3)基于圖集訓(xùn)練GNN指令選擇器模型.本文的整體設(shè)計思路如圖1所示.

圖1 GNN實現(xiàn)指令選擇整體設(shè)計圖Fig.1 Overall design of GNN instruction selection

2 GNN的設(shè)計與實現(xiàn)

本文確定了基于LLVM平臺和圖覆蓋策略來實現(xiàn)BWDSP的指令選擇.1)通過分析LLVM處理指令選擇的過程，驗證圖神經(jīng)網(wǎng)絡(luò)處理指令選擇的可行性.2)通過制定語義映射規(guī)則將CFG和DAG靜態(tài)連接成CDFG，并給出構(gòu)造CDFG的動態(tài)鏈接庫工具，建立程序和指令圖集；3)對比分析BWDSP指令集和LLVM虛擬指令集的特性、BWDSP所提供的IR格式和LLVM所提供的IR格式，確定了常見的數(shù)據(jù)處理對應(yīng)的IR及其對應(yīng)的指令規(guī)模.最后驗證了GNN在處理IR所表示的圖結(jié)構(gòu)中的可行性和有效性.

本文首先分析LLVM處理指令選擇的過程.源代碼經(jīng)過LLVM前端clang編譯器后生成平臺無關(guān)的中間表示IR，再通過Lowering pass，將IR構(gòu)造為平臺有關(guān)的SelectionDAG.Lowering Pass是一種LLVM趟，趟的作用是對IR進(jìn)行一次遍歷和操作，完成系統(tǒng)架構(gòu)或用戶所指定的轉(zhuǎn)換、分析或優(yōu)化等功能，如Dce Pass是將IR中一些無用的死代碼消除的趟.SelectionDAG，即是表示源程序所有信息的圖結(jié)構(gòu)，由兩類SDNode組成.SDNode，即為SelectionDAG的節(jié)點.每個SDNode包含一條指令的操作碼和數(shù)據(jù).根據(jù)不同的類型，每個SDNode又可包含3或4個子塊.擁有3個子塊的SDNode代表數(shù)據(jù)節(jié)點，3個子塊從上至下分別表示節(jié)點類型枚舉，節(jié)點編號和節(jié)點的數(shù)據(jù)類型；擁有4個子塊的SDNode表示為操作節(jié)點，從上至下分別表示操作符接受的輸入操作數(shù)的序號，節(jié)點類型枚舉，節(jié)點編號和節(jié)點的數(shù)據(jù)類型.

此時構(gòu)造出來的SelectionDAG是針對特定平臺下的源代碼的圖表示.但lowering Pass所創(chuàng)建的SelectionDAG并不一定全部被目標(biāo)架構(gòu)支持.所以，還需要對SelectionDAG多次進(jìn)行合法化優(yōu)化和合并優(yōu)化.合法化是對數(shù)據(jù)類型和操作兩個方面進(jìn)行優(yōu)化，如對于不支持sdiv指令的X86架構(gòu)，合法化優(yōu)化Pass則會將sdiv節(jié)點的操作碼轉(zhuǎn)換為X86架構(gòu)支持的sdivrem指令；如目標(biāo)平臺指令集下只支持64位數(shù)據(jù)類型，而SelectionDAG中數(shù)據(jù)類型只包括32位，合法化優(yōu)化Pass則會將SelectionDAG中的不合法的數(shù)據(jù)類型轉(zhuǎn)換為目標(biāo)平臺支持的節(jié)點數(shù)據(jù)類型.合并優(yōu)化則是為了合并或消除SelectionDAG中冗余的節(jié)點，目的是為指令選擇能夠生成更優(yōu)的指令提供更好的DAG.此時經(jīng)過這3種Pass的多次優(yōu)化之后得到最終的SelectionDAG，對于包含add和sub指令的優(yōu)化后的SelectionDAG如圖2所示.

圖2 包含add 和 sub指令的SelectionDAGFig.2 SelectionDAG with add and sub instructions

指令選擇是基于最終的SelectionDAG生成針對目標(biāo)平臺指令的機(jī)器指令節(jié)點的過程.在LLVM中，指令語義是以樹模式的方式描述，并通過tableGen工具將目標(biāo)平臺的指令集描述存儲在對應(yīng)的.td文件中.選擇的過程是通過調(diào)用SelectionCodeCommon()函數(shù)，首先接收SDNode判斷節(jié)點的屬性，判斷節(jié)點的類型來決定是否選擇機(jī)器指令，再加載匹配表對應(yīng)的.td文件進(jìn)行匹配，此時生成即是針對特定平臺的MachineDAG.

綜上，LLVM的指令選擇是基于優(yōu)化后的SelectionDAG與目標(biāo)指令集下的語義模式匹配完成.所以，可以將SelectionDAG作為切入點，首先通過IR構(gòu)造包含程序全局信息的CDFG，再編寫基于LLVM的優(yōu)化趟來生成對應(yīng)的SelectionDAG，并作為模型中源程序?qū)?yīng)的CDFG數(shù)據(jù)集，最后搭建和訓(xùn)練GNN模型，并將選擇出來的目標(biāo)平臺的機(jī)器指令作為真實的結(jié)果與預(yù)測的結(jié)果對比，反向傳播以更新GNN模型.因此，本文主要分為以下3步來實現(xiàn).

1)構(gòu)造源程序的CDFG數(shù)據(jù)集.通過制定相關(guān)語義映射規(guī)則將CFG和DAG組合成CDFG，與保存源程序局部信息的DAG相比，構(gòu)造出來的CDFG保存了源程序的全局結(jié)構(gòu)信息.

2)由于BWDSP所使用的編譯器同樣是基于LLVM的Clang編譯器，所以生成的中間代碼格式也統(tǒng)一于LLVM.同時分析BWDSP指令集和LLVM虛擬指令集的特性，每條LLVM虛擬指令都對應(yīng)至少一條BWDSP機(jī)器指令，保證后期匹配集合的可選性.通過前期的調(diào)研確定常見的數(shù)據(jù)處理方式對應(yīng)的IR中常用的LLVM虛擬指令集中的指令，即確定源程序數(shù)據(jù)集的規(guī)模.

3)本文用一種新的方式，即將GNN模型應(yīng)用到編譯后端的指令選擇過程，來模擬遍歷SelectionDAG，從機(jī)器指令集的語義描述中匹配指令，并通過后期實驗驗證了本文的可行性和有效性.

2.1 建模源程序IR的CDFG

LLVM的中間代碼格式是基于SSA的，BWDSP使用LLVM的前端編譯器，因此其中間代碼格式也是基于SSA的.SSA[23]，Static Single Assignment，靜態(tài)單變量賦值，它具有類型安全性、底層操作性、靈活性，能夠清楚表達(dá)絕大多數(shù)的高級語言，是運用在編譯技術(shù)等領(lǐng)域的高效數(shù)據(jù)流分析技術(shù).基于SSA中間表示能夠保證每個被使用的變量都有唯一的定義，因此SSA能帶來精確的“使用—定義”關(guān)系，故而利用“使用—定義”關(guān)系的能夠完成更有效的優(yōu)化.現(xiàn)代諸多編譯系統(tǒng)如GCC、Open64、LLVM都提供了對SSA的支持.DAG中包含程序的數(shù)據(jù)流信息和局部數(shù)據(jù)依賴間的關(guān)系；CFG是表示一個函數(shù)塊內(nèi)的執(zhí)行流圖，圖中的每一個節(jié)點是語句，邊表示執(zhí)行流信息.

本文基于LLVM的SSA圖，設(shè)計了一種更全面同時也更簡潔的IR的圖表示數(shù)據(jù)控制流圖的建模方法.LLVM首先會把基于SSA的IR表示為DAG，本文基于Eclipse環(huán)境下的Gecos[24]工具來生成對應(yīng)程序的DAG表示.數(shù)據(jù)控制流圖的基本設(shè)計思路是：1)首先將中間代碼改造成SSA形式的IR，并以此為基礎(chǔ)分別構(gòu)建基于SSA的DAG和控制流圖CFG.基于SSA的DAG和CFG用于捕獲程序的數(shù)據(jù)流和控制流.2)擴(kuò)展DAG和CFG，并將這兩種圖結(jié)構(gòu)組合在一起得到數(shù)據(jù)控制流圖CDFG，使得數(shù)據(jù)控制流圖在捕獲程序的數(shù)據(jù)流以及控制流的同時能夠更好地保證程序的語法及語義信息的完整性和正確性.因此，本文針對BWDSP平臺提出適應(yīng)性方案，最終導(dǎo)出以下6個數(shù)據(jù)控制流圖的設(shè)計規(guī)則：

Rule1.數(shù)據(jù)控制流圖能夠捕獲程序的數(shù)據(jù)流和控制流：捕獲兩種信息流能夠更完整的保存程序的信息.

Rule2.函數(shù)中的基本塊應(yīng)被表示成節(jié)點：便于捕獲控制流，同時便于進(jìn)行模式匹配.

Rule3.數(shù)據(jù)和控制操作應(yīng)被表示成節(jié)點：用于捕獲數(shù)據(jù)流和控制流.

Rule4.函數(shù)中所使用的實值應(yīng)被表示成節(jié)點：實值也是數(shù)據(jù).

Rule5.表示實值的節(jié)點只有一個入邊：保證每個實值只有一個定義.

Rule6.數(shù)據(jù)控制流圖應(yīng)基于SSA：SSA能夠保證精確地“使用-定義”關(guān)系.

函數(shù)的基本塊是IR中按順序執(zhí)行的指令容器，在基本塊中指令按照出現(xiàn)的先后順序來執(zhí)行.基于以上6個規(guī)則，本文分3步來構(gòu)建數(shù)據(jù)控制流圖：1)基于SSA構(gòu)建源程序的DAG；2)基于LLVM自帶的CFG生成工具構(gòu)建CFG；3)組合DAG和CFG得到CDFG.最后本文按照以上6個規(guī)則，將兩種圖結(jié)構(gòu)組合為CDFG.圖3為LLVM生成包含add和sub指令示例程序?qū)?yīng)的CFG.

圖3 LLVM生成包含add和sub指令程序?qū)?yīng)的CFGFig.3 CFG generated by LLVM containing add and sub instruction

2.1.1 捕獲數(shù)據(jù)流

為了捕獲數(shù)據(jù)流，本文基于SSA形式的IR構(gòu)建SSA圖.通常編譯器中可以提取出SSA圖，因為SSA圖基于SSA形式的IR，所以該圖符合R6以及R1中的部分規(guī)則.此外，本文對SSA圖定義了擴(kuò)展節(jié)點：

1)計算節(jié)點：該節(jié)點表示程序中的數(shù)據(jù)操作以及φ函數(shù).該類節(jié)點的定義滿足了R3的設(shè)計規(guī)則.

2)變量節(jié)點：該節(jié)點程序中的變量.該類節(jié)點的定義滿足了R3的設(shè)計規(guī)則.

3)實值節(jié)點：該節(jié)點用于表示被數(shù)據(jù)操作所使用或由數(shù)據(jù)操作所產(chǎn)生的實值.該類節(jié)點的定義滿足了R4的設(shè)計規(guī)則.

在計算節(jié)點中，φ函數(shù)用于解決SSA圖只賦值一次，因而無法確定同一變量在執(zhí)行先后順序上的取值問題.在變量節(jié)點中，程序中的變量表示的是在SSA圖中所使用的變量，包括函數(shù)外部的全局變量和函數(shù)內(nèi)部的局部變量.SSA圖和CFG共用一個返回節(jié)點，刪除SSA圖中的返回節(jié)點.基于上述設(shè)計的SSA圖不僅能夠捕獲數(shù)據(jù)流，同時能夠滿足R3、R4、R6以及R1的部分規(guī)則.

2.1.2 捕獲控制流

為了捕獲IR的控制流，本文基于SSA形式的IR構(gòu)建CFG，并在CFG中定義兩種節(jié)點：

1)塊節(jié)點：表示程序中的基本塊.該類節(jié)點的定義滿足了R2的設(shè)計規(guī)則；

2)控制節(jié)點：該節(jié)點表示控制流從一個塊跳轉(zhuǎn)到另一個塊的跳轉(zhuǎn).該類節(jié)點的定義滿足了R1的部分設(shè)計規(guī)則.

2.1.3 組合數(shù)據(jù)控制流圖

本文簡單地在SSA圖和CFG之間添加有向邊將這兩類圖組合成數(shù)據(jù)控制流圖：

1)值定義邊：每個實值節(jié)點與CFG的入口塊節(jié)點連接一條有向邊，表示實值節(jié)點的定義.

2)值引用邊：變量節(jié)點和使用該變量的控制節(jié)點之間連接一條有向邊，表示控制流對數(shù)據(jù)流的影響.

CFG中的邊表示程序中的控制流動，同時有一些邊需要為其加上標(biāo)簽，作為存儲CDFG圖信息的邊矩陣的元素值.例如從判斷語句的控制節(jié)點流出的邊需要為其標(biāo)識True和False，分別對應(yīng)的值為1和0.CFG中前后相鄰基本塊之間對于控制流的標(biāo)簽的依次累加.以此，為子圖集中的每個圖中的邊添加標(biāo)簽.

由于DAG中每個基本塊內(nèi)中指令按照先后順序執(zhí)行，所以在生成CDFG時基本塊中的控制流是定向流動的，因此塊內(nèi)可快速指定，方便簡化CDFG的生成過程.

2.2 構(gòu)建BWDSP指令集為指令圖集

在BWDSP處理器中總共有600多條指令，本文使用和建模源程序IR的CDFG相同的方法將指令表示成模式.與生成數(shù)據(jù)控制流圖不同的是，當(dāng)指令的輸出不依賴于控制流時，控制流圖為空，此時模式?jīng)]有入口塊.通常一條復(fù)雜指令能完成多條簡單指令組合才能完成的復(fù)雜操作，但是一條單獨的指令很難建模成圖.為了便于建模，本文為每條指令添加一條或多條語義規(guī)則.因為基于BWDSP處理器的所有程序都可以用這600多條指令表示，因此本文將這600多條指令全部建模并制作成子圖模式集以方便使用.

經(jīng)過以上步驟，已完成將目標(biāo)平臺的機(jī)器指令的語義描述由原先的.td文件轉(zhuǎn)換為與輸入數(shù)據(jù)集所包含的源程序結(jié)構(gòu)相同的圖結(jié)構(gòu)文件的內(nèi)容.輸入數(shù)據(jù)集與輸出結(jié)果采用相同的結(jié)構(gòu)作為統(tǒng)一的標(biāo)準(zhǔn)，為后期GNN模型的預(yù)測同步以實現(xiàn)節(jié)點從平臺無關(guān)到特定平臺的映射準(zhǔn)備.

表2是本文按照提出的規(guī)則對最大值指令的擴(kuò)展，增加了相應(yīng)的語義規(guī)則，是可表示圖結(jié)構(gòu)的模式.圖4對應(yīng)于表2的模式，其中虛線代表數(shù)據(jù)流，黑色表示控制流.此圖按照CDFG規(guī)則設(shè)計，符合指令對應(yīng)CDFG的前提條件.

表2 通過添加語義規(guī)則求最大值指令的模式Table 2 Pattern of maximum instruction by adding semantic rules

圖4 表2對應(yīng)的模式Fig.4 Corresponding pattern of Table2

2.3 基于圖集訓(xùn)練GNN指令選擇器模型

CDFG與SelectionDAG同為基于LLVM的IR圖表示，這使得模式匹配問題可以轉(zhuǎn)換成子圖匹配問題.而現(xiàn)階段，子圖匹配問題可以使用圖卷積神經(jīng)網(wǎng)絡(luò)的方法來解決.常見的GNN采用鄰域聚合方法，通過遞歸聚合和變換相鄰節(jié)點的嵌入表示來計算自身節(jié)點的嵌入表示，是一種非常有效的圖表示學(xué)習(xí)框架.目前許多基于GNN的變體也已經(jīng)被提出，因其令人信服的性能和較高的可解釋性而被應(yīng)用到節(jié)點分類[25]、圖分類[25]、鏈接預(yù)測[26]任務(wù)的領(lǐng)域中，且都取得了非常不錯的效果.圖5展示了圖節(jié)點嵌入的過程.

圖5 GNN中Embedding的示例Fig.5 An example of Embedding in GNN

本文所采用的GNN模型也是基于嵌入的GraphSage[27]和GIN[28]模型，針對本文特定的BWDSP的場景做了一些相應(yīng)的改進(jìn).GraphSAGE，即Graph SAmple and aggreGatE，是一種能夠利用頂點的屬性信息高效地產(chǎn)生未知頂點嵌入向量的一種歸納式學(xué)習(xí)的框架，核心思想是通過學(xué)習(xí)一個對鄰居頂點進(jìn)行聚合表示的函數(shù)來產(chǎn)生目標(biāo)頂點的嵌入向量表示，解決了GCN中歸納式學(xué)習(xí)的問題，能夠?qū)W習(xí)節(jié)點的表示方法，因此在現(xiàn)有的圖基礎(chǔ)上對所添加的新的節(jié)點能夠獲取其表示.GIN，即Graph Isomorphism Network，圖同構(gòu)網(wǎng)絡(luò)，該網(wǎng)絡(luò)模型對Weisfeiler-Lehman測試進(jìn)行了推廣，從而在GNNs中鑒別能力最強(qiáng).MLP可以近似擬合任意函數(shù)，因此GIN通過引入MLP，能夠?qū)W習(xí)到單射函數(shù)，從而彌補(bǔ)GraphSAGE模型中只使用單層感知機(jī)的不足.

甲維鹽全稱甲氨基阿維菌素苯甲酸鹽，可以增強(qiáng)神經(jīng)質(zhì)如谷氨酸和Y-氨基丁酸(GABA) 的作用，從而使大量氯離子進(jìn)入神經(jīng)細(xì)胞，使細(xì)胞功能喪失，擾亂神經(jīng)傳導(dǎo)，幼蟲在接觸后馬上停止進(jìn)食，發(fā)生不可逆轉(zhuǎn)的麻痹，在3～4天內(nèi)達(dá)到最高致死率．甲維鹽是一種新型高效半合成抗生素殺蟲劑，其具有超高效、低毒(制劑近無毒)、無殘留和無公害等生物農(nóng)藥的特點，對鱗翅目昆蟲的幼蟲和其它許多害蟲及螨類的活性極高，既有胃毒作用又兼觸殺作用，在非常低的劑量(0.084～2 g/hm2)下具有很好的效果，而且在防治害蟲的過程中對益蟲沒有傷害，有利于對害蟲的綜合防治[1-2]．

對于構(gòu)造出來的CDFG，由于GNN能夠理解圖中節(jié)點與節(jié)點之間的依賴關(guān)系，對于其中的CFG中的Basic Block，則可能在到達(dá)基本塊的結(jié)尾的時候預(yù)測出下一條指令為終止符指令，因此能夠增大GNN預(yù)測的準(zhǔn)確率.

本文首先將源程序和數(shù)據(jù)集的格式按照制定的標(biāo)準(zhǔn)統(tǒng)一，對原始數(shù)據(jù)集對應(yīng)的基于IR的CDFG進(jìn)行訓(xùn)練，以及構(gòu)建模式選擇器的過程，分為3個步驟描述.

1)源程序的控制流圖可以由順序結(jié)構(gòu)，選擇結(jié)構(gòu)以及循環(huán)結(jié)構(gòu)3種基本結(jié)構(gòu)表示，這里根據(jù)程序的執(zhí)行規(guī)則，所有結(jié)構(gòu)中的單獨指令都會在定長的指令周期內(nèi)完成，所以可假設(shè)單獨指令的執(zhí)行代價相同.BWDSP中對應(yīng)指令模式的數(shù)據(jù)流圖中也由同樣的規(guī)則，將所有指令對應(yīng)的模式代價視為與其控制流圖的執(zhí)行代價相同.其中所有的邊標(biāo)簽代表指令與指令之間的執(zhí)行代價，本文所涉及到的圖內(nèi)邊信息則基于控制流和數(shù)據(jù)流而表示為指令間依賴關(guān)系的強(qiáng)弱.

通過上述步驟之后本文所使用的CDFG存儲在其對應(yīng)的.dot文件，這樣指令對應(yīng)的.dot文件和源程序所對應(yīng)的.dot文件就構(gòu)成了GNN的輸入數(shù)據(jù)集.因此，依據(jù)此信息將.dot文件作為輸入，首先對圖中每個節(jié)點進(jìn)行按順序標(biāo)注，這樣就能得到IR的圖的拓?fù)浔硎?每一個節(jié)點都對應(yīng)一種指令，如二進(jìn)制位指令add、向量指令insertelement、內(nèi)存訪問alloca等，對這些指令添加和標(biāo)注標(biāo)簽.本文采用one-hot編碼格式為這些標(biāo)簽編碼，以連續(xù)化程序指令的特征，因而每一個指令對應(yīng)一個特有的標(biāo)簽向量.

因此，基于上述原理，本文可以按照統(tǒng)一的標(biāo)準(zhǔn)來制定源程序和BWDSP指令模式CDFG的節(jié)點標(biāo)簽和邊標(biāo)簽，圖6中黑色邊表示控制流，虛線邊表示數(shù)據(jù)流.

圖6 加入語義規(guī)則之后的Max指令其拓?fù)浣Y(jié)構(gòu)對應(yīng)的模式Fig.6 Topology of Max instruction after adding semantic rules

2)獲取CDFG的Laplacian矩陣.對應(yīng)一個圖G={V，E}，本文采用正則化的Laplacian矩陣，如式(2)所示：

Lsys=D-1/2LD-1/2

(2)

其中D為圖中頂點的度矩陣，L為組合的Laplacian矩陣.不同的CDFG的規(guī)模是不同的，且CDFG是有向圖，所以本文重定義了圖的鄰接關(guān)系，對轉(zhuǎn)換之后的Laplacian矩陣重新計算大小，將邊的信息添加至Laplacian矩陣當(dāng)中.設(shè)拓?fù)鋱D中節(jié)點的數(shù)量為M，則矩陣的規(guī)模為M×M.設(shè)圖的邊數(shù)為T，圖中節(jié)點最大的度為Dmax，則邊權(quán)值矩陣大小為T×Dmax.

本文所采用的模型的學(xué)習(xí)過程主要有以下4個步驟：

a)對節(jié)點的局部k跳鄰域進(jìn)行固定大小的隨機(jī)采樣.

b)通過聚合中心節(jié)點的鄰居特征信息來獲得中心節(jié)點的臨界狀態(tài).

c)將臨界狀態(tài)線性轉(zhuǎn)換為最終狀態(tài).

d)最后使用中心節(jié)點的最終狀態(tài)，進(jìn)行預(yù)測并反向傳播錯誤.

其中，對于第1步中節(jié)點的k跳鄰域，k的取值一般在{1，2}之間，本文中根據(jù)IR指令控制流動和數(shù)據(jù)流動的特征分析，聚合節(jié)點的一階和二階的鄰居信息即可滿足對于鄰居節(jié)點信息的要求.在第2步中的中心節(jié)點表示在當(dāng)前聚合過程中圖中的任一節(jié)點，從該節(jié)點出發(fā)聚合與其相鄰的一階和二階鄰居節(jié)點作為該節(jié)點的最終聚合信息.當(dāng)前中心節(jié)點完成聚合鄰居節(jié)點信息的操作后得到的嵌入向量表示即為當(dāng)前節(jié)點的臨界狀態(tài).將鄰居節(jié)點聚合的特征和經(jīng)過線性變換的當(dāng)前中心節(jié)點的特征進(jìn)行求和或級聯(lián)，通過非線性激活函數(shù)的轉(zhuǎn)換，得到更新后的特征即當(dāng)前節(jié)點聚合后的最終狀態(tài).

按照上述步驟完成模型的訓(xùn)練過程.對任何一個輸入指令的IR的CDFG可以輸出其對應(yīng)的匹配模式標(biāo)簽.根據(jù)之前對邊的標(biāo)簽和節(jié)點標(biāo)簽的處理特性，并結(jié)合GIN結(jié)構(gòu)的特點，本文使用sum聚合算子來學(xué)習(xí)全部的標(biāo)簽以及數(shù)量，以獲得精確的結(jié)構(gòu)信息.本文所使用的圖神經(jīng)網(wǎng)絡(luò)偽代碼如表3所示.

表3 圖神經(jīng)網(wǎng)絡(luò)偽代碼Table 3 Pseudocode of graph neural network

通過引入聚合函數(shù)的概念來定義圖的卷積.聚合函數(shù)實質(zhì)上是聚合節(jié)點的鄰域信息.它必須對節(jié)點順序的排列具有不變性，因此也保證了指令的執(zhí)行順序的不變性.其中sum聚合算子的定義如式(3)所示：

aggsum=σ(SUM{W·hj+b，?vj∈N(vi)})

(3)

其中W和b，是聚合操作中學(xué)習(xí)的參數(shù).Sum算子用于將鄰居聚合的特征與當(dāng)前節(jié)點特征合并，以更新當(dāng)前節(jié)點特征.圖7為節(jié)點和圖的更新過程.

圖7 節(jié)點和圖的更新過程Fig.7 Graph node and graph update process

訓(xùn)練的過程即實現(xiàn)指令選擇的過程，本文訓(xùn)練出來模型作為指令選擇器.本文所使用的指令選擇模型是基于GIN和GraphSAGE兩個神經(jīng)網(wǎng)絡(luò)模型，因此簡稱為GINSA.GINSA能夠預(yù)測出源程序?qū)?yīng)的CDFG中相應(yīng)節(jié)點的標(biāo)簽，將模型預(yù)測的指令標(biāo)簽整合成可使用BWDSP確定的指令超集，該超集是指令選擇中第2步模式匹配所選用指令的完備集，是對覆蓋指令集合的約束.通過元啟發(fā)式算法進(jìn)行模式匹配可選擇出有效的機(jī)器指令.

3 實驗及評估

3.1 時空復(fù)雜度分析

假設(shè)源程序的數(shù)目為m，LLVM虛擬指令數(shù)為n，BWDSP指令數(shù)目為l，每個源程序可產(chǎn)生若干條虛擬指令語句，設(shè)其數(shù)目為s，在加載源程序為其中間代碼編碼的過程的時間復(fù)雜度為O(m·s).另外，由于GINSA是基于GCN模型，前向傳播的重點在于聚合鄰居節(jié)點的信息，所以模型整體的主要時間復(fù)雜度和空間復(fù)雜度分別為式(4)和式(5)：

(4)

(5)

D為模型的層數(shù)，l為層數(shù)索引，M為需要聚合的鄰接節(jié)點的特征，對于單層卷積層來說M的維度如式(6)所示：

Ml=Nsrc×Nneighbor×Din

(6)

其中，Nsrc為源節(jié)點的數(shù)量，Nneighbor為鄰居節(jié)點的數(shù)量，Din為輸入的特征維度，K為卷積核的邊長，對于輸入為矩陣的神經(jīng)網(wǎng)絡(luò)模型，輸入輸出的通道數(shù)只有一層，故而簡化.

3.2 實 驗

3.2.1 實驗過程

本文所使用的實驗平臺是基于Ubuntu18.04上的BWDSP 1042模擬器，LLVM8.0 Release版本作為數(shù)據(jù)集構(gòu)建的環(huán)境架構(gòu)以及Nvidia GeForce RTX 2060顯卡用于模型的訓(xùn)練加速，實驗以準(zhǔn)確率為評判標(biāo)準(zhǔn).

3.2.2 GINSA基本測試實驗

本文首先在LLVM虛擬指令集上實驗，完成對每條平臺無關(guān)指令的編碼.基于MUTAG、PTC、CDFG這3個數(shù)據(jù)集，使用GCN、GIN、GraphSAGE作為基準(zhǔn)網(wǎng)絡(luò)模型，最后將GINSA模型同樣應(yīng)用于3個數(shù)據(jù)集，準(zhǔn)確率實驗結(jié)果如表4所示.

表4 對比實驗結(jié)果Table 4 Comparison of experimental results

MUTAG是關(guān)于化合物的數(shù)據(jù)集，原子代表結(jié)點，化學(xué)鍵代表邊，因此每個化合物可看為一張圖，其中包含兩類共188張圖，每個圖都對應(yīng)一個標(biāo)簽，代表類別.PTC也是關(guān)于化合物的數(shù)據(jù)集，包含4個類別共344張圖，同樣，每個圖都有一個標(biāo)簽表示類別.CDFG為本文收集的C源程序?qū)?yīng)的優(yōu)化后的IR數(shù)據(jù)集，語句代表節(jié)點，數(shù)據(jù)控制流表示邊，其中常用的LLVM虛擬指令集共包含108條指令，因而有108個類別共3000張圖.從表4中可知，在MUTAG和PTC兩個數(shù)據(jù)上使用GINSA模型得到的準(zhǔn)確率與基準(zhǔn)圖神經(jīng)網(wǎng)絡(luò)模型相差無幾，且在CDFG數(shù)據(jù)集能夠?qū)崿F(xiàn)識別出指令的功能，最高能達(dá)到79.8%的準(zhǔn)確率.一方面驗證了基于改進(jìn)的圖神經(jīng)網(wǎng)絡(luò)GINSA在一般性的圖數(shù)據(jù)集上的可行性和可靠性，另一方面也驗證了圖神經(jīng)網(wǎng)絡(luò)在處理指令選擇過程理論上的有效性.將模型對于源程序CDFG中節(jié)點的標(biāo)簽標(biāo)注收集起來作為指令選擇模式匹配任務(wù)中的超集.其對比結(jié)果如表5所示.

表5 指令選擇器指令超集和實際指令集對比Table 5 Instruction selector instruction superset versus actual instruction set

表5的結(jié)果是保證常見的指令至少出現(xiàn)一次的前提下，在同一個C源程序上得到由GINSA得出的指令和LLVM實際選用指令的類別內(nèi)數(shù)目的對比.可以看出，GINSA指令選擇器所選擇出來的指令超集和它實際所使用的指令之間的差距在所選用的指令類別上保持一致，其中僅僅在數(shù)據(jù)傳輸指令類別上有些許的不同，且實際選用的指令集是GINSA所選擇指令集的子集，說明指令選擇器具有完備性.另外，本文通過和LLVM后端中保存指令相關(guān)信息的.td文件對比得到的初步結(jié)論是：在編譯后端代碼生成的指令選擇過程中運用圖神經(jīng)網(wǎng)絡(luò)模型，在一定的情況下能夠識別和預(yù)測出正確的指令類別集合，并且能夠選擇出包含BWDSP指令集中特有復(fù)雜指令候選集合來完成多個單指令實現(xiàn)的目標(biāo).雖然模型的運算量較大，但后期進(jìn)行優(yōu)化之后可作為單獨可附加的模塊進(jìn)行移植.

3.2.3 GINSA在指令子數(shù)據(jù)集上的實驗

本文基于平臺無關(guān)的LLVM虛擬指令集，按照指令出現(xiàn)的頻率選擇最常見的虛擬指令作為指令子數(shù)據(jù)集，并以此整理數(shù)據(jù)集來評測GINSA的性能.

在大多數(shù)的簡單C程序中，從得到的中間代碼中可以觀察到，LLVM中的大多數(shù)復(fù)雜指令并沒有被用到.所以，在編碼的過程中為了降低程序所占內(nèi)存的大小和提高程序執(zhí)行速度，我們設(shè)計了這樣的實驗，對比在LLVM整體和局部指令集下GINSA的識別具體指令的準(zhǔn)確率.數(shù)據(jù)傳輸指令是數(shù)據(jù)存取的必要指令，幾乎每個程序都會涉及到其中幾種，如“store”“l(fā)oad”；在ALU指令中，常見的有“add”“sub”“and”“or”“xor”等；MUL指令中，有“mul”等.在該實驗中，本文摘取了其中的一部分作為數(shù)據(jù)集.圖8中虛線和實線分別表示訓(xùn)練的準(zhǔn)確率和測試的準(zhǔn)確率在使用數(shù)據(jù)集中的全部樣本對模型進(jìn)行的一次完整訓(xùn)練的變化過程，橫坐標(biāo)是完整訓(xùn)練次數(shù)增長的方向.可以看出，隨著訓(xùn)練次數(shù)的增加，每條曲線所代表的準(zhǔn)確率都在不斷上升，每條曲線所代表的準(zhǔn)確率都在不斷上升，最終能夠穩(wěn)定在96%上下，表明在該子指令集下GINSA能夠識別出有效的指令超集.本文檢取其中出現(xiàn)頻率最高的幾種指令，相比在LLVM整體虛擬指令集上的實驗，明顯提高了GINSA模型最終得到的準(zhǔn)確率，表明了GINSA模型的可靠性.

圖8 GINSA在LLVM子數(shù)據(jù)集上的性能Fig.8 Performance on LLVM subset by GINSA

4 總 結(jié)

本文基于改進(jìn)的GNN模型，設(shè)計實驗和驗證了改進(jìn)的指令選擇模型在編譯后端代碼生成的指令選擇步驟中的可行性、可靠性和有效性.本文首先驗證GNN在處理指令選擇場景上應(yīng)用的可行性，再提出構(gòu)造CDFG的規(guī)則，基于LLVM平臺和BWDSP1042模擬器，將指令集中的指令和程序建模成CDFG.然后在GraphSAGE和GIN兩種GNN模型上改進(jìn)，以訓(xùn)練出指令選擇器，最后基于GNN訓(xùn)練的結(jié)果為源代碼選擇出可靠的BWDSP復(fù)雜指令，完成了指令選擇的初始目的.

本文通過實驗驗證了GNN通用框架在處理圖類型的非結(jié)構(gòu)化數(shù)據(jù)上的高適用性.在BWDSP指令集和X86架構(gòu)上實驗，驗證了指令選擇模型所選擇出指令集合的可用性，并分析了GNN模型的優(yōu)勢和特性.在未來的工作中，可通過優(yōu)化GNN模型的結(jié)構(gòu)來提升指令選擇的正確性，也可通過將GNN模型簡化并封裝成BWDSP內(nèi)部可調(diào)用模塊的方式來實現(xiàn)其可集成性.