馮競(jìng)舸 賀也平,2 陶秋銘 馬恒太

1 （基礎(chǔ)軟件國(guó)家工程研究中心（中國(guó)科學(xué)院軟件研究所） 北京 100190）

2 （計(jì)算機(jī)科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室（中國(guó)科學(xué)院軟件研究所） 北京 100190）（jingge@iscas.ac.cn）

自動(dòng)向量化[1]是利用處理器單指令多數(shù)據(jù)（single instruction multiple data，SIMD）擴(kuò)展部件實(shí)現(xiàn)程序數(shù)據(jù)級(jí)并行的編譯優(yōu)化方法，它與手工編寫SIMD 向量程序相比，不需要程序員深入理解SIMD 擴(kuò)展部件的功能特性，減少了程序員的負(fù)擔(dān).隨著SIMD 硬件擴(kuò)展指令集的不斷發(fā)展，向量指令應(yīng)用的領(lǐng)域和需求也越來(lái)越多，然而如何生成高效的向量指令至今依然是個(gè)挑戰(zhàn)[2-3].

目前自動(dòng)向量化主要有2 大類方法：基于循環(huán)的自動(dòng)向量化方法[4]和超字級(jí)并行（superword level parallelism，SLP）自動(dòng)向量化方法[5]，其分別旨在實(shí)現(xiàn)循環(huán)和基本塊的自動(dòng)向量化.SLP 一直是向量化領(lǐng)域關(guān)注的重要方法，本文重點(diǎn)對(duì)其展開研究.

SLP 方法通過(guò)尋找同構(gòu)指令序列[5]，將數(shù)據(jù)合并到同一向量寄存器中并行處理.由于同構(gòu)指令序列在實(shí)際程序中占比不是很高以及方法自身的原因[6]，SLP 的適用范圍受限.近年來(lái)，有研究者開始關(guān)注于通過(guò)等價(jià)變換將滿足特定條件的非同構(gòu)指令序列轉(zhuǎn)換為同構(gòu)指令序列，從而為實(shí)施SLP 創(chuàng)造條件.如PSLP 方法[7]采用基于程序差異特征的圖模式匹配，通過(guò)添加選擇（select）指令進(jìn)行擴(kuò)充，從而將非同構(gòu)指令序列轉(zhuǎn)換成同構(gòu)指令序列.LSLP 方法[8]利用交換律等價(jià)關(guān)系式對(duì)非同構(gòu)序列中的運(yùn)算操作和操作數(shù)進(jìn)行重排，從而獲得同構(gòu)指令序列.類似地，SNSLP 方法[9]和SLP-E 方法[10]分別采用減法/除法的等價(jià)關(guān)系式和擴(kuò)展等價(jià)關(guān)系式對(duì)非同構(gòu)序列中的運(yùn)算操作和操作數(shù)進(jìn)行變換，從而獲得同構(gòu)指令序列.

除了采用的同構(gòu)化轉(zhuǎn)換方法外，我們發(fā)現(xiàn)實(shí)際還存在其他方法可應(yīng)用于指令序列同構(gòu)化轉(zhuǎn)換中.例如利用二元表達(dá)式等價(jià)替換關(guān)系（如X× 4=X＜＜2）將非同構(gòu)指令序列轉(zhuǎn)換為同構(gòu)指令序列.

在對(duì)非同構(gòu)指令序列進(jìn)行SLP 向量化時(shí)，充分利用多種同構(gòu)化轉(zhuǎn)換方法比只考慮單一轉(zhuǎn)換方法更有優(yōu)勢(shì).例如在SPEC CPU 基準(zhǔn)測(cè)試程序中存在一些包含多條二元操作且存在常量操作數(shù)的語(yǔ)句，需要經(jīng)過(guò)多種方法的同構(gòu)化轉(zhuǎn)換后才可對(duì)其有效實(shí)施自動(dòng)向量化.然而，目前還無(wú)文獻(xiàn)專門針對(duì)同時(shí)利用多種同構(gòu)化轉(zhuǎn)換的向量化方法進(jìn)行研究.

與只考慮單一同構(gòu)化轉(zhuǎn)換不同，當(dāng)考慮多種同構(gòu)化轉(zhuǎn)換方法時(shí)，需解決同構(gòu)化轉(zhuǎn)換方法的選擇問(wèn)題.對(duì)于任一非同構(gòu)指令序列，首先需要分析確認(rèn)哪些同構(gòu)化轉(zhuǎn)換方法適用；其次，對(duì)于同一指令序列不同同構(gòu)化轉(zhuǎn)換方法產(chǎn)生的代價(jià)是不同的，需要選擇合適的同構(gòu)化轉(zhuǎn)換方法，提升程序的自動(dòng)向量化性能收益.因此指令序列同構(gòu)化轉(zhuǎn)換方法的選擇涉及2個(gè)問(wèn)題：?jiǎn)栴}1：一些指令序列存在不同的同構(gòu)化轉(zhuǎn)換方法，需進(jìn)行適用同構(gòu)化轉(zhuǎn)換方法的識(shí)別和搜索.問(wèn)題2：不同同構(gòu)化轉(zhuǎn)換方法產(chǎn)生的收益不同，需要針對(duì)各種同構(gòu)化轉(zhuǎn)換方法給出收益評(píng)估方法.

本文提出一種SLP 擴(kuò)展方法——SLP-M 向量化方法，將多種方法應(yīng)用于非同構(gòu)指令序列的同構(gòu)化轉(zhuǎn)換中，并評(píng)估每種同構(gòu)化轉(zhuǎn)換方法的性能收益，根據(jù)收益進(jìn)行同構(gòu)化轉(zhuǎn)換方法的選擇.為了解決同構(gòu)化轉(zhuǎn)換方法選擇的第1 個(gè)問(wèn)題，本文利用處理程序的特性和同構(gòu)化轉(zhuǎn)換方法的特點(diǎn)進(jìn)行分析，采用啟發(fā)式方法，優(yōu)先搜索那些需轉(zhuǎn)換指令數(shù)量較少以及引入自動(dòng)向量化的性能收益相對(duì)較高的同構(gòu)化轉(zhuǎn)換方法.為了解決同構(gòu)化轉(zhuǎn)換方法選擇的第2 個(gè)問(wèn)題，本文發(fā)現(xiàn)指令的操作類型相似程度越大，那么這些語(yǔ)句越容易被實(shí)施自動(dòng)向量化，越有機(jī)會(huì)帶來(lái)自動(dòng)向量化的性能收益，因此利用程序操作及操作數(shù)的類型相似程度并結(jié)合同構(gòu)化轉(zhuǎn)換方法的特征進(jìn)行收益評(píng)估.

SLP-M 方法與先前工作的主要區(qū)別在于：

1）SLP-M 綜合利用多種方法（包括二元表達(dá)式等價(jià)替換、擴(kuò)展變換、基于shuffle 指令的變換等）進(jìn)行同構(gòu)化轉(zhuǎn)換，而先前的PSLP 和LSLP 等方法都只采用了單一類型的同構(gòu)化轉(zhuǎn)換方法.SLP-M 與先前工作比較，提高了將非同構(gòu)指令序列轉(zhuǎn)換為同構(gòu)指令序列的能力.其中，基于二元表達(dá)式替換的指令序列同構(gòu)化轉(zhuǎn)換方法與PSLP 比較，對(duì)于特定類型程序，不需要生成引入額外運(yùn)行代價(jià)的指令就可進(jìn)行同構(gòu)化轉(zhuǎn)換.基于二元表達(dá)式的替換變換與LSLP 和SNSLP 進(jìn)行比較，能夠同構(gòu)化轉(zhuǎn)換一些先前方法不能同構(gòu)化轉(zhuǎn)換的指令序列.

2）由于SLP-M 綜合采用多種同構(gòu)化轉(zhuǎn)換方法，為了選擇合適的同構(gòu)化轉(zhuǎn)換方式，SLP-M 方法解決了采用多種方法進(jìn)行同構(gòu)化轉(zhuǎn)換過(guò)程中的一些特殊問(wèn)題，如多種同構(gòu)化轉(zhuǎn)換方法的識(shí)別、搜索和選擇等，這些是PSLP 和LSLP 等工作未涉及的.

本文基于LLVMv10.0 實(shí)現(xiàn)了SLP-M 方法，并基于SPEC CPU 2017 等測(cè)試集進(jìn)行了測(cè)試和評(píng)估.實(shí)驗(yàn)結(jié)果表明，本方法相比已有方法在核心函數(shù)測(cè)試中性能提升了21.8%，在基準(zhǔn)測(cè)試程序整體性能測(cè)試中性能提升了4.1%.

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

1）提出基于多種指令序列同構(gòu)化轉(zhuǎn)換方法的SLP-M 向量化方法，擴(kuò)展了對(duì)非同構(gòu)指令序列的自動(dòng)向量化適用范圍；

2）除了已有指令序列同構(gòu)化轉(zhuǎn)換方法，本文還引入和利用了基于二元表達(dá)式替換的方法，該方法不僅不會(huì)引入額外運(yùn)行代價(jià)，而且減少了指令的操作類型和數(shù)量；

3）提出指令序列同構(gòu)化轉(zhuǎn)換的選擇方法，發(fā)揮了多種同構(gòu)化轉(zhuǎn)換方法的優(yōu)勢(shì)，提升了對(duì)非同構(gòu)指令序列自動(dòng)向量化的性能收益.

1 背景與研究動(dòng)機(jī)

目前大部分關(guān)于自動(dòng)向量化的研究主要是針對(duì)某類特殊類型的程序向量化，將某個(gè)具體的程序變換方法與自動(dòng)向量化結(jié)合，或利用某個(gè)特殊SIMD 擴(kuò)展指令優(yōu)化自動(dòng)向量化等方法，這些研究往往對(duì)特定類型程序是有效的，但是利用單一自動(dòng)向量化方法變換后得到的結(jié)果并不總是有效.例如循環(huán)，既可包含循環(huán)內(nèi)的并行語(yǔ)句又可包含循環(huán)間的并行語(yǔ)句，如果單獨(dú)利用基于循環(huán)或基本塊內(nèi)的自動(dòng)向量化方法，得到的向量化方案不總是最優(yōu)的.

超字級(jí)并行[5]是對(duì)基本塊內(nèi)同構(gòu)指令序列進(jìn)行自動(dòng)向量化的方法，可有效提升程序的性能，得到許多研究者的關(guān)注和進(jìn)一步研究，相關(guān)成果集中于基于同構(gòu)指令序列構(gòu)建同構(gòu)鏈[7]的研究，具體包含2 方面內(nèi)容：1）擴(kuò)展SLP 向量化的適用范圍，如旨在對(duì)循環(huán)[11-15]和包含分支程序[16]的向量化，以及多級(jí)融合（跨循環(huán)和跨基本塊融合）[17]的向量化.2）提高向量化的性能收益，利用全局策略或局部貪心策略構(gòu)建同構(gòu)鏈，提高生成向量指令收益，減少重組指令的代價(jià).全局策略構(gòu)建同構(gòu)鏈方法是基于全局搜索的方式構(gòu)建同構(gòu)鏈[18-21].局部貪心策略構(gòu)建同構(gòu)鏈方法是基于局部貪心策略逐層構(gòu)建同構(gòu)鏈[22-24].此外，除了應(yīng)用于自動(dòng)向量化，SLP 方法也被擴(kuò)展應(yīng)用于動(dòng)態(tài)二進(jìn)制翻譯[25]、內(nèi)嵌匯編形式向量代碼優(yōu)化[26]和非SIMD向量指令優(yōu)化[27]等領(lǐng)域.

SLP 方法有賴于先找到程序中的同構(gòu)指令序列，這對(duì)SLP 方法的實(shí)際應(yīng)用造成一定局限.近年來(lái)，有學(xué)者[7]開始關(guān)注如何將SLP 方法擴(kuò)展應(yīng)用到非同構(gòu)指令序列如PSLP 和LSLP 等，PSLP 和LSLP 等方法將特定的非同構(gòu)指令序列轉(zhuǎn)換為同構(gòu)指令序列，然后再進(jìn)一步實(shí)施向量化.然而，PSLP 和LSLP 等方法都存在其特定的適用范圍，如果單一實(shí)施，向量化能力有限.

圖1 描繪了SPEC CPU 2017 625case 中的一段程序代碼采用幾種不同的自動(dòng)向量化方法進(jìn)行處理的過(guò)程.其中圖1（a）（b）分別為一段包含非同構(gòu)指令序列的輸入程序及其對(duì)應(yīng)的數(shù)據(jù)依賴圖.圖1（c）（e）（g）（i）是將多條標(biāo)量指令轉(zhuǎn)換為向量形式的分組圖，其中，陰影長(zhǎng)方形表示可自動(dòng)向量化的操作或操作數(shù)；虛線框的長(zhǎng)方形表示自動(dòng)向量化所需生成的存在額外運(yùn)行代價(jià)的指令.向量分組圖中的benefit表示自動(dòng)向量化的收益，即標(biāo)量指令代價(jià)與向量指令代價(jià)的差值，若benefit＞0，則自動(dòng)向量化有收益，編譯器實(shí)施自動(dòng)向量化；否則自動(dòng)向量化無(wú)收益，編譯器不進(jìn)行程序轉(zhuǎn)換.圖1（d）（f）（h）表示不同自動(dòng)向量化方法處理輸入程序的轉(zhuǎn)換過(guò)程.

Fig.1 Process of various auto-vectorization methods adopted by an example program圖1 一個(gè)示例程序采用不同自動(dòng)向量化方法進(jìn)行處理的過(guò)程

SLP 方法的向量分組如圖1（c）所示.SLP 方法先以A[0]，A[1]，A[2]，A[3]連續(xù)內(nèi)存訪問(wèn)為種子，并基于種子擴(kuò)展同構(gòu)指令序列，擴(kuò)展中發(fā)現(xiàn)訪存、移位、乘法操作，其類型不同，因而停止同構(gòu)指令序列的進(jìn)一步擴(kuò)展，編譯器評(píng)估自動(dòng)向量化無(wú)收益，因此不對(duì)輸入程序進(jìn)行轉(zhuǎn)換.

PSLP 方法對(duì)輸入程序的處理流程如圖1（d）（e）所示，代碼中4 條語(yǔ)句對(duì)應(yīng)數(shù)據(jù)依賴圖的差異較大，PSLP 方法在自動(dòng)向量化中生成較多額外運(yùn)行代價(jià)的選擇指令，編譯器評(píng)估自動(dòng)向量化無(wú)收益，因此不對(duì)輸入程序進(jìn)行程序轉(zhuǎn)換.

LSLP 方法只能對(duì)可交換運(yùn)算操作的操作數(shù)進(jìn)行重排序，由于處理中的訪存、移位、乘法操作不都是可交換運(yùn)算操作，因此無(wú)法實(shí)施同構(gòu)化轉(zhuǎn)換.SNSLP 方法與LSLP 方法類似，無(wú)法對(duì)輸入程序?qū)嵤┳詣?dòng)向量化.

對(duì)于圖1（a）中的原始輸入程序，其實(shí)存在的多種適用的同構(gòu)化轉(zhuǎn)換方法至少有2 種：

1）通過(guò)擴(kuò)展轉(zhuǎn)換關(guān)系將非同構(gòu)指令序列轉(zhuǎn)換為同構(gòu)指令序列.如圖1（f）（g）所示，先將第1 行語(yǔ)句的B[0]擴(kuò)展變換為B[0]＜＜0，然后將第3 行的B[2]×3擴(kuò)展變換為（B[2]×3）＜＜0，這樣程序轉(zhuǎn)為A[0]=B[0]＜＜0；A[1]=B[1]＜＜1；A[2]=（B[2]×3）＜＜0；A[3]=B[3]＜＜2，最后對(duì)第1，2，4 行語(yǔ)句擴(kuò)展乘法操作，將程序轉(zhuǎn)為同構(gòu)形式.從性能收益上考慮，由于將輸入程序中的2 個(gè)標(biāo)量移位和1 個(gè)標(biāo)量乘法替換為1 個(gè)向量移位和1個(gè)向量乘法，對(duì)于移位和乘法而言自動(dòng)向量化的收益為1，再加上將輸入程序的8 個(gè)標(biāo)量訪存轉(zhuǎn)換為2個(gè)向量訪存，自動(dòng)向量化總體收益是7，可有效實(shí)施自動(dòng)向量化.

2）同時(shí)采用擴(kuò)展轉(zhuǎn)換關(guān)系和二元表達(dá)式等價(jià)替換關(guān)系將非同構(gòu)指令序列轉(zhuǎn)換為同構(gòu)指令序列.如圖1（h）（i）所示，首先將第1 行語(yǔ)句的B[0]擴(kuò)展變換為B[0]×1，然 后 將 第2 行 語(yǔ) 句 的B[1]＜＜1 替 換 為B[1]×2，最后同理對(duì)第4 行語(yǔ)句進(jìn)行二元表達(dá)式替換，使非同構(gòu)指令序列轉(zhuǎn)換為同構(gòu)指令序列，與上文單獨(dú)采用擴(kuò)展變換比較，減少了向量移位操作，此時(shí)自動(dòng)向量化可帶來(lái)收益（benefit= 8），因此，進(jìn)一步提升了自動(dòng)向量化的性能收益.

從上面2 種轉(zhuǎn)換示例可以看出：1）當(dāng)引入多種同構(gòu)化轉(zhuǎn)換方法的時(shí)候，確實(shí)能夠獲得更多的向量化機(jī)會(huì)和性能收益；2）選擇不同同構(gòu)化轉(zhuǎn)換方法會(huì)影響向量化的性能收益.有鑒于此，本文希望研究和實(shí)現(xiàn)能夠有效利用多種指令序列同構(gòu)化轉(zhuǎn)換方式的向量化方法.

2 指令序列同構(gòu)化轉(zhuǎn)換方法

目前已有的指令序列同構(gòu)化轉(zhuǎn)換方法不是很多.PSLP 方法可以被認(rèn)為是第1 個(gè)對(duì)非同構(gòu)指令序列進(jìn)行轉(zhuǎn)換研究的工作，它利用硬件選擇指令來(lái)實(shí)施同構(gòu)化轉(zhuǎn)換.此后，有研究者注意到可以基于表達(dá)式等價(jià)關(guān)系實(shí)現(xiàn)同構(gòu)化轉(zhuǎn)換.例如LSLP 方法利用交換律進(jìn)行同構(gòu)化轉(zhuǎn)換，SN-SLP 方法利用減法以及除法等價(jià)關(guān)系式進(jìn)行同構(gòu)化轉(zhuǎn)換，SLP-M 利用等價(jià)擴(kuò)展變換進(jìn)行同構(gòu)化轉(zhuǎn)換.除了上述涉及操作符/操作數(shù)順序和個(gè)數(shù)變化的表達(dá)式等價(jià)變換外，我們發(fā)現(xiàn)實(shí)際還存在多種其他涉及操作符類型變化的等價(jià)轉(zhuǎn)換關(guān)系 可 應(yīng) 用 于 同 構(gòu) 化 轉(zhuǎn) 換 中，如X＜＜2=X×4，X×2=X+X等，也就是可將“形式不同但本質(zhì)功能相同”的操作符等價(jià)轉(zhuǎn)為類型相同的操作符.

結(jié)合目前已有方法以及我們自己的分析歸納，本文采用了4 種指令序列同構(gòu)化轉(zhuǎn)換方法：基于shuffle 指令的同構(gòu)化轉(zhuǎn)換、重排序變換、擴(kuò)展變換、二元表達(dá)式替換.下面逐一介紹.

2.1 基于shuffle 指令的同構(gòu)化轉(zhuǎn)換

shuffle 是將多個(gè)數(shù)據(jù)合并、重組和排序的指令，通常包含2 個(gè)輸入操作數(shù)和1 個(gè)輸出操作數(shù)，輸出操作數(shù)是輸入操作數(shù)重組后的數(shù)據(jù).絕大部分處理器都支持類似shuffle 功能的指令，如x86 和ARM 系列處理器等.

基于shuffle 指令的同構(gòu)化轉(zhuǎn)換方法是指利用shuffle 指令將不同的操作合并到同一向量寄存器，并基于它們相同位置的操作數(shù)，向“定義—使用”鏈和“使用—定義”鏈的方向繼續(xù)建立擴(kuò)展同構(gòu)指令序列的程序變換方式.基于shuffle 指令的同構(gòu)化轉(zhuǎn)換與PSLP 方法中采用選擇指令的轉(zhuǎn)換方法本質(zhì)相同，都是將不同類型的操作通過(guò)特殊指令合并到同一向量寄存器中.選擇指令的向量形式是基于shuffle 指令實(shí)現(xiàn)的.

具體示例如圖2 所示，其中圖2（a）（b）分別是輸入程序以及對(duì)應(yīng)的依賴圖，圖2（c）表示利用shuffle指令將減法和乘法操作合并到同一向量寄存器中.

Fig.2 An example of program transformation based on shuffle instruction圖2 基于shuffle 指令的程序轉(zhuǎn)換示例

2.2 重排序變換

重排序變換指基于交換律、減法性質(zhì)[9]或者除法性質(zhì)[9]的等價(jià)變換，通過(guò)重排序操作符或操作數(shù)獲得同構(gòu)指令序列，涉及操作符或操作數(shù)順序變化，不涉及其個(gè)數(shù)和類型的改變.

基于交換律的重排序等價(jià)變換式如：A?B= =B?A，其中?是可交換運(yùn)算，A和B是?的操作數(shù).滿足交換律的運(yùn)算普遍存在于實(shí)際程序中，包括加法、乘法、與運(yùn)算、或運(yùn)算等.重排序可交換運(yùn)算的操作數(shù)，如LSLP 方法，使得多個(gè)可交換運(yùn)算的操作數(shù)所對(duì)應(yīng)的指令組成同構(gòu)指令序列，如將c[0]=a[0]+b[0]和c[1]=b[1]+a[1]的第2 條語(yǔ)句變換為c[1]=a[1]+b[1].則這2 條語(yǔ)句加法的第1 個(gè)和第2 個(gè)操作數(shù)分別是a[0]，a[1]，b[0]，b[1]，它們是連續(xù)的內(nèi)存訪問(wèn)，可實(shí)施向量化.

SN-SLP 所采用的減法性質(zhì)是只由減法或加法所組成的表達(dá)式，交換其減法以及對(duì)應(yīng)操作數(shù)的順序，輸出值不變?nèi)鏰-b+c=a+c-b，所采用的除法性質(zhì)類似.SN-SLP 方法采用運(yùn)算符性質(zhì)的重排序變換，使得多個(gè)減法或者除法運(yùn)算的操作數(shù)組成同構(gòu)指令序列，如a[0]=b[0]-c[0]-d[0]和a[1]=b[1]-d[1]-c[1]可通過(guò)減法性質(zhì)將a[1]=b[1]-d[1]-c[1]變換為a[1]=b[1]-c[1]-d[1]，則這2 條語(yǔ)句減法對(duì)應(yīng)的操作數(shù)分別為a[0]，a[1]；b[0]，b[1]；c[0]，c[1]，它們是連續(xù)的內(nèi)存訪問(wèn)，可實(shí)施向量化.

2.3 擴(kuò)展變換

擴(kuò)展變換是通過(guò)對(duì)表達(dá)式進(jìn)行等價(jià)的擴(kuò)展變換[10]，將程序中非同構(gòu)指令序列轉(zhuǎn)換為同構(gòu)指令序列，涉及操作符和操作數(shù)的個(gè)數(shù)改變.

首先介紹擴(kuò)展等價(jià)表達(dá)式.如果一個(gè)二元運(yùn)算?、常數(shù)C（C為0 或1），以及X（X可為變量、常量或者表達(dá)式）滿足X?C= =X或C?X= =X，那么本文把X?C或C?X稱為X的擴(kuò)展等價(jià)表達(dá)式.擴(kuò)展等價(jià)表達(dá)式存在多種類型，表1 給出了本文已實(shí)現(xiàn)的擴(kuò)展等價(jià)表達(dá)式.

Table 1 Equivalent Extended Expression of X表1 X 的擴(kuò)展等價(jià)表達(dá)式

擴(kuò)展變換就是將表達(dá)式X轉(zhuǎn)換為X的擴(kuò)展等價(jià)表達(dá)式，使其擴(kuò)展表達(dá)式的操作在特定條件可與其他的操作組成同構(gòu)指令序列.擴(kuò)展變換示例如圖3 所示，其中圖3（a）（b）分別是輸入程序以及對(duì)應(yīng)的依賴圖.圖3（c）表示通過(guò)擴(kuò)展變換方法將第1 行語(yǔ)句的B[0]擴(kuò)展為B[0]×1，擴(kuò)展變換后獲得同構(gòu)語(yǔ)句.

Fig.3 An example of extended transform圖3 擴(kuò)展變換示例

2.4 二元表達(dá)式替換

二元表達(dá)式替換是本文新引入的一種等價(jià)變換.在介紹該變換前，先引入二元替換等價(jià)表達(dá)式的概念.對(duì)于表達(dá)式1 ：X?Y，表達(dá)式2 ：Z?K，若同時(shí)滿足3 個(gè)條件則表達(dá)式2 被稱為表達(dá)式1 的二元替換等價(jià)表達(dá)式：

1）表達(dá)式1 和表達(dá)式2 中的?和?都是二元操作符，且操作符類型不同；

2）表達(dá)式1 和表達(dá)式2 至少存在1 個(gè)相同的操作數(shù)；

3）表達(dá)式1 中?可被直接替換為?（不涉及操作符個(gè)數(shù)的變化），且表達(dá)式1 和表達(dá)式2 輸出值相同.

二元表達(dá)式替換是指將程序中特定的二元表達(dá)式轉(zhuǎn)換為其二元替換等價(jià)表達(dá)式，進(jìn)而將程序中的非同構(gòu)指令序列轉(zhuǎn)換為同構(gòu)指令序列.二元替換等價(jià)表達(dá)式在程序中存在多種類型，本文已實(shí)現(xiàn)的表達(dá)式類型如表2 所示.二元表達(dá)式替換不同于重排序變換和擴(kuò)展變換，不涉及操作符順序和個(gè)數(shù)的改變，而涉及操作符類型的改變.

Table 2 List of Patterns of Replacement for Binary Expressions表2 二元表達(dá)式替換模式列表

二元表達(dá)式替換示例如圖4 所示，其中圖4（a）（b）分別是輸入程序以及對(duì)應(yīng)的依賴圖.圖4（c）表示通過(guò)二元表達(dá)式替換的方法將第1 行語(yǔ)句的移位操作替換為乘法操作，進(jìn)而將其轉(zhuǎn)換為同構(gòu)的形式.

Fig.4 An example of replacement of binary expression圖4 二元表達(dá)式替換示例

3 SLP-M 向量化方法

3.1 方法概述

SLP-M 是一種改進(jìn)的SLP 向量化方法.SLP 的基本處理過(guò)程是基于“種子”并根據(jù)“定義-使用（defuse）”鏈和“使用-定義（use-def）”鏈擴(kuò)展同構(gòu)圖，然后結(jié)合同構(gòu)圖分析向量及標(biāo)量形式代碼的代價(jià)，若向量代碼代價(jià)相對(duì)較低，則實(shí)施自動(dòng)向量化.SLP 方法不考慮對(duì)非同構(gòu)指令序列的向量化，而SLP-M 對(duì)SLP 的改進(jìn)就在于對(duì)非同構(gòu)指令序列的分析和處理，SLP-M 會(huì)嘗試對(duì)非同構(gòu)指令序列進(jìn)行同構(gòu)化轉(zhuǎn)換，并在條件滿足時(shí)對(duì)非同構(gòu)指令序列實(shí)施自動(dòng)向量化.

SLP-M 引入和運(yùn)用了多種同構(gòu)化轉(zhuǎn)換方法，包括基于shuffle 指令的轉(zhuǎn)換、重排序變換、擴(kuò)展變換、二元表達(dá)式替換.如引言所述，當(dāng)考慮多種同構(gòu)化轉(zhuǎn)換方法時(shí)候，對(duì)于同一指令序列有時(shí)存在多種適用的同構(gòu)化轉(zhuǎn)換方法，需解決同構(gòu)化轉(zhuǎn)換方法的選擇問(wèn)題.同時(shí)，對(duì)于同一指令序列不同的同構(gòu)化轉(zhuǎn)換方法產(chǎn)生的代價(jià)不同，需要選擇合適的同構(gòu)化轉(zhuǎn)換方法，提升程序的自動(dòng)向量化性能收益.該問(wèn)題主要涉及2 個(gè)問(wèn)題.

問(wèn)題1.同構(gòu)化轉(zhuǎn)換方法的識(shí)別和搜索.

有些指令序列存在大量適用的同構(gòu)化轉(zhuǎn)換方法，例如shuffle 指令理論上可把任意的操作存放到同一向量寄存器中，這就引入了很多轉(zhuǎn)換方法.若采用窮舉法遍歷每種適用的同構(gòu)化轉(zhuǎn)換方法，那么方法數(shù)量成指數(shù)級(jí)增長(zhǎng)，計(jì)算復(fù)雜度太高.因此需要尋找和設(shè)計(jì)高效的同構(gòu)化轉(zhuǎn)換方法的識(shí)別和搜索方法.

問(wèn)題2.針對(duì)特定同構(gòu)化轉(zhuǎn)換方法的收益評(píng)估.

不同同構(gòu)化轉(zhuǎn)換方法不僅影響目標(biāo)處理指令序列，而且影響其操作數(shù)，進(jìn)而影響自動(dòng)向量化的整體性能收益，需針對(duì)每種方法進(jìn)行整體性能收益評(píng)估.

對(duì)于問(wèn)題1，本文結(jié)合處理程序及同構(gòu)化轉(zhuǎn)換方法的特點(diǎn)，給出了一種啟發(fā)式方法用以識(shí)別和搜索更有機(jī)會(huì)帶來(lái)性能收益的轉(zhuǎn)換方式.同構(gòu)化轉(zhuǎn)換的目的是以選擇1 個(gè)指令作為基準(zhǔn)參照指令，通過(guò)等價(jià)轉(zhuǎn)換使指令序列中其他所有指令與其操作類型相同.原則上指令序列中的每個(gè)指令都可選作基準(zhǔn)參照指令.但如果啟發(fā)式將指令序列中的每個(gè)指令都嘗試作為基準(zhǔn)參照指令，遍歷所有適用的同構(gòu)化轉(zhuǎn)換方式，計(jì)算復(fù)雜度太大.其實(shí)，許多非同構(gòu)指令序列是可以被自動(dòng)向量化的，這些指令序列中大部分指令的操作類型是相似的.若將指令序列中的與其他指令相似程度最高的指令作為基準(zhǔn)參照指令（本文中被稱為基準(zhǔn)指令，參見3.2 節(jié)），那么以基準(zhǔn)指令作為參照的同構(gòu)化轉(zhuǎn)換的候選集合大概率會(huì)包含適用于這類指令序列的同構(gòu)化轉(zhuǎn)換方式.鑒于此，SLPM 以基準(zhǔn)指令作為參照，然后結(jié)合不同同構(gòu)化轉(zhuǎn)換方法的具體特點(diǎn)，如轉(zhuǎn)換方式對(duì)操作的處理以及引入自動(dòng)向量化的額外運(yùn)行代價(jià)等，啟發(fā)式識(shí)別和搜索更有機(jī)會(huì)帶來(lái)自動(dòng)向量化性能收益的具體變換方式.

對(duì)于問(wèn)題2，需要評(píng)估指令序列在不同方法同構(gòu)化轉(zhuǎn)換下自動(dòng)向量化的整體性能收益，SLP-M 利用程序?qū)?yīng)依賴圖中的操作類型相似信息評(píng)估自動(dòng)向量化的性能收益，從目標(biāo)處理指令對(duì)應(yīng)依賴圖中的節(jié)點(diǎn)開始，并遞歸沿著其子孫節(jié)點(diǎn)的方向，分析指令操作及其操作數(shù)的同構(gòu)化轉(zhuǎn)換方法，評(píng)估并統(tǒng)計(jì)整體的性能收益.

本文利用多種方法來(lái)進(jìn)行同構(gòu)化轉(zhuǎn)換，利用基準(zhǔn)指令的選擇方法來(lái)啟發(fā)式識(shí)別和選擇合理的同構(gòu)化轉(zhuǎn)換方法，降低選擇的代價(jià)，通過(guò)同構(gòu)化轉(zhuǎn)換方法的搜索并利用評(píng)估模型來(lái)評(píng)估適合的方法，由此得到自動(dòng)向量化性能收益較高的具體變換方式.而PSLP 和LSLP 等采用單一類型的同構(gòu)化轉(zhuǎn)換方法，不存在多種同構(gòu)化轉(zhuǎn)換方法的搜索和選擇問(wèn)題，因此未用到基準(zhǔn)指令的選擇和同構(gòu)化轉(zhuǎn)換的搜索方法.

SLP-M 的方法處理流程圖如圖5 所示，其中同構(gòu)化分析及轉(zhuǎn)換包括4 個(gè)具體步驟：1）基準(zhǔn)指令的選擇.根據(jù)程序?qū)?yīng)依賴圖中操作節(jié)點(diǎn)及子孫節(jié)點(diǎn)的信息選擇基準(zhǔn)指令.2）同構(gòu)化轉(zhuǎn)換方法的搜索.針對(duì)特定的指令序列搜索適用的同構(gòu)化轉(zhuǎn)換方法.3）同構(gòu)化轉(zhuǎn)換方法的選擇.評(píng)估收益并選擇其中評(píng)估性能收益最高的同構(gòu)化轉(zhuǎn)換方法.4）同構(gòu)化轉(zhuǎn)換.下面對(duì)這4 個(gè)步驟分別進(jìn)行介紹.

Fig.5 Process flow of SLP-M圖5 SLP-M 的處理流程

3.2 基準(zhǔn)指令的選擇

為了選擇基準(zhǔn)指令，SLP-M 遍歷指令序列中的每個(gè)指令，計(jì)算該指令與其他指令對(duì)應(yīng)依賴圖中的操作類型相同節(jié)點(diǎn)（下文稱為“匹配節(jié)點(diǎn)”）的個(gè)數(shù)，或者可通過(guò)二元表達(dá)式替換轉(zhuǎn)換為匹配節(jié)點(diǎn)的個(gè)數(shù).SLP-M 將與指令序列中其他指令的匹配節(jié)點(diǎn)個(gè)數(shù)最多的指令作為基準(zhǔn)指令.SLP-M 選擇基準(zhǔn)指令的步驟有2 個(gè).

1）遍歷處理指令序列insts中的每個(gè)指令（記為指令x_inst），計(jì)算指令x_inst與指令序列中其他指令（記為指令y_inst）的對(duì)應(yīng)依賴圖中的匹配節(jié)點(diǎn)或者可通過(guò)二元表達(dá)式替換轉(zhuǎn)換為匹配節(jié)點(diǎn)總數(shù).計(jì)算匹配節(jié)點(diǎn)個(gè)數(shù)的方法是：從指令x_inst和指令y_inst對(duì)應(yīng)依賴圖的節(jié)點(diǎn)開始自底向上統(tǒng)計(jì)匹配節(jié)點(diǎn)個(gè)數(shù).

①若指令x_inst和指令y_inst的操作類型相同，統(tǒng)計(jì)計(jì)數(shù)加1，繼續(xù)向它們的子節(jié)點(diǎn)方向統(tǒng)計(jì)計(jì)算；

②若指令x_inst和指令y_inst的操作類型不同，但可通過(guò)二元等價(jià)替換的方式將指令y_inst轉(zhuǎn)換為與指令x_inst相同類型的操作，實(shí)施二元等價(jià)替換，并統(tǒng)計(jì)計(jì)數(shù)加1，繼續(xù)向它們的子節(jié)點(diǎn)方向統(tǒng)計(jì)計(jì)算；

③若指令x_inst和指令y_inst的操作類型不同，且無(wú)法通過(guò)二元表達(dá)式替換轉(zhuǎn)換為與其相同的操作，或者遇到葉子節(jié)點(diǎn)，則停止向它們的子節(jié)點(diǎn)方向統(tǒng)計(jì)計(jì)算.

2）根據(jù)步驟1 計(jì)算的匹配節(jié)點(diǎn)個(gè)數(shù)，選擇指令序列insts中與其他指令對(duì)應(yīng)匹配個(gè)數(shù)最多的指令為基準(zhǔn)指令.當(dāng)多個(gè)指令與其他指令的匹配節(jié)點(diǎn)個(gè)數(shù)相同時(shí)，可啟發(fā)式選擇排在更前面的指令.

3.3 同構(gòu)化轉(zhuǎn)換方法的搜索

在求得基準(zhǔn)指令后，SLP-M 以基準(zhǔn)指令作為參照，搜索將指令序列中的指令轉(zhuǎn)換為與基準(zhǔn)指令類型相同操作的轉(zhuǎn)換方式.本文根據(jù)特定方法的轉(zhuǎn)換特征，如轉(zhuǎn)換方式對(duì)操作的處理以及引入自動(dòng)向量化的額外運(yùn)行代價(jià)，搜索每種同構(gòu)化轉(zhuǎn)換方法具體的轉(zhuǎn)換方式.

基于shuffle 指令的程序轉(zhuǎn)換會(huì)生成shuffle 指令，引入額外運(yùn)行代價(jià).SLP-M 排除引入較多額外運(yùn)行代價(jià)轉(zhuǎn)換的具體變換方式，僅考慮對(duì)于指令序列包含2 類二元操作的條件下將基于shuffle 指令的同構(gòu)化轉(zhuǎn)換納入候選同構(gòu)化的轉(zhuǎn)換方式.

重排序變換通過(guò)重排序指令的操作以及操作數(shù)使得在特定條件下增多自動(dòng)向量化語(yǔ)句的數(shù)量[8-9]不會(huì)引入額外代價(jià).因此，若在指令序列中存在與基準(zhǔn)指令操作類型相同的可交換運(yùn)算操作，SLP-M 會(huì)將對(duì)其的重排序變換納入候選同構(gòu)化轉(zhuǎn)換方式.

擴(kuò)展變換將指令轉(zhuǎn)換為其的擴(kuò)展等價(jià)表達(dá)式，使得擴(kuò)展后的指令與原始程序的指令組成同構(gòu)指令序列，盡管在程序擴(kuò)展轉(zhuǎn)換中增加了運(yùn)算指令，但是這些指令可與原程序中標(biāo)量代碼一同轉(zhuǎn)為向量形式，不會(huì)引入自動(dòng)向量化的額外運(yùn)行代價(jià).因此，若指令存在與基準(zhǔn)指令操作類型相同的等價(jià)擴(kuò)展式，SLPM 會(huì)將對(duì)其的擴(kuò)展變換納入候選同構(gòu)化轉(zhuǎn)換方式.

二元表達(dá)式替換變換是在特定的條件下將一個(gè)表達(dá)式替換為另一個(gè)表達(dá)式，使替換后指令與原始程序的指令組成同構(gòu)指令序列，盡管存在會(huì)將代價(jià)較低的標(biāo)量指令轉(zhuǎn)為代價(jià)較高的標(biāo)量指令的情形，但是轉(zhuǎn)換生成的指令可與原始程序一同轉(zhuǎn)為向量形式，因此向量化不會(huì)引入額外運(yùn)行代價(jià)，且由于替換變換減少了源程序標(biāo)量操作的種類，因此向量化后進(jìn)一步減少生成指令的種類和數(shù)量.若指令存在與基準(zhǔn)指令操作類型相同的二元表達(dá)式替換式，SLPM 會(huì)將對(duì)其的二元表達(dá)式替換變換納入候選同構(gòu)化轉(zhuǎn)換方式.

為了表示指令序列的同構(gòu)化轉(zhuǎn)換方式，本文沿用文獻(xiàn)[18]中指令對(duì)和轉(zhuǎn)換模式的術(shù)語(yǔ)，并結(jié)合本文要解決的同構(gòu)化轉(zhuǎn)換問(wèn)題進(jìn)一步明確其含義：1）指令對(duì).指由2 個(gè)指令組成的集合.2）轉(zhuǎn)換模式.指對(duì)于特定的指令對(duì)，描述其操作、操作數(shù)、具體的同構(gòu)化轉(zhuǎn)換方式的集合，包括操作指令集合v、同構(gòu)化轉(zhuǎn)換方式action和同構(gòu)化轉(zhuǎn)換后的操作集合v′這3 個(gè)部分，可表示為（v，action，v′）三元組形式，轉(zhuǎn)換模式示例如圖6 所示.1 個(gè)指令序列可由1 個(gè)或者多個(gè)指令對(duì)組成，其同構(gòu)轉(zhuǎn)換方式可描述為其中多個(gè)指令對(duì)的轉(zhuǎn)換模式集合.

Fig.6 An example of conversion pattern圖6 轉(zhuǎn)換模式示例

對(duì)于指令序列insts，SLP-M 首先搜索滿足2 個(gè)條件的指令對(duì)集合inst_pairs：1）指令對(duì)中的指令都屬于指令序列insts；2）指令對(duì)中必須包含insts的基準(zhǔn)指令.然后，針對(duì)inst_pairs中的每個(gè)指令對(duì)，在第2.1～2.3 節(jié)描述的同構(gòu)化轉(zhuǎn)換的可轉(zhuǎn)換條件所述滿足特定條件的候選同構(gòu)轉(zhuǎn)換方式中遍歷所有可將其中的非基準(zhǔn)指令轉(zhuǎn)換為與基準(zhǔn)指令相同類型操作的轉(zhuǎn)換方式，將其記錄于轉(zhuǎn)換模式集合patterns中.

3.4 同構(gòu)化轉(zhuǎn)換方法的選擇及實(shí)施

在搜索完所有具體適用的同構(gòu)化轉(zhuǎn)換方法后，需評(píng)估每種方法自動(dòng)向量化的性能收益，根據(jù)收益進(jìn)行同構(gòu)化轉(zhuǎn)換方法的選擇.考慮到評(píng)估方法的效率和準(zhǔn)確度，同構(gòu)化轉(zhuǎn)換方法的選擇以及實(shí)施向量化的評(píng)估分步處理，本文設(shè)計(jì)相對(duì)高效的基于操作符和操作數(shù)類型的相似信息評(píng)估模型進(jìn)行同構(gòu)化轉(zhuǎn)換方法的選擇，待確定具體的同構(gòu)化轉(zhuǎn)換方式后，利用準(zhǔn)確度相對(duì)較高的LLVM 自帶的評(píng)估模型判定是否實(shí)施向量化，若評(píng)估有收益則實(shí)施向量化，否則程序以原標(biāo)量形式執(zhí)行.為了評(píng)估自動(dòng)向量化的性能收益，本文介紹2 個(gè)基本概念.

1）單層指令對(duì)的自動(dòng)向量化收益.指對(duì)于1 個(gè)指令對(duì)，對(duì)其進(jìn)行自動(dòng)向量化獲得性能收益.這里給出單層指令對(duì)的自動(dòng)向量化收益評(píng)估方法，具體描述為：

①若指令對(duì)的2 條指令的操作類型相同，則單層指令對(duì)的收益計(jì)為1；

②若指令對(duì)的2 條指令經(jīng)過(guò)二元表達(dá)式替換或者重排序變換后，其操作的類型相同，則單層指令對(duì)的收益計(jì)為1；

③若指令對(duì)的2 條指令需經(jīng)過(guò)擴(kuò)展變換后，其操作的類型相同，則單層指令對(duì)的收益計(jì)為0；

④若指令對(duì)2 條指令的操作類型不同，且無(wú)法通過(guò)同構(gòu)化轉(zhuǎn)換方法將其轉(zhuǎn)為操作類型相同的形式，則單層指令對(duì)的收益計(jì)為0.

2）整體指令對(duì)的自動(dòng)向量化收益.指對(duì)于1 個(gè)指令對(duì)，若對(duì)其進(jìn)行自動(dòng)向量化，其本身指令對(duì)以及子操作數(shù)所依賴所有指令對(duì)自動(dòng)向量化性能收益的總和.這里給出評(píng)估整體指令對(duì)自動(dòng)向量化收益的方法，即整體指令對(duì)的自動(dòng)向量化收益是單層指令對(duì)的自動(dòng)向量化收益與其操作數(shù)所組成指令對(duì)的整體指令對(duì)自動(dòng)向量化收益之和.整體指令對(duì)的自動(dòng)向量化收益計(jì)算如式（1）所示，其中x和y都是指令，x.operands（k）和y.operands（k）分別是指令x和指令y的第k個(gè)操作數(shù)，scorewhole是整體指令對(duì)〈x，y〉的自動(dòng)向量化收益，scoresingle是單層指令對(duì)〈x，y〉的自動(dòng)向量化收益.

SLP-M 通過(guò)評(píng)估每個(gè)指令對(duì)在特定轉(zhuǎn)換模式下的整體指令，對(duì)自動(dòng)向量化收益選擇同構(gòu)化轉(zhuǎn)換方法，同構(gòu)化轉(zhuǎn)換選擇函數(shù)pattern_selection偽代碼如函數(shù)1 所示.

函數(shù)1.pattern_selection.

輸入：指令序列insts；

輸出：匹配分?jǐn)?shù)score，相對(duì)最優(yōu)的同構(gòu)化轉(zhuǎn)換方法pattern.

①base_inst = get_base_inst（insts）； /*求得基準(zhǔn)指令*/

/*遍歷指令序列中每條指令*/

② for（eachinstininsts）

③patterns=search_pattern（inst，base_inst）；/*遍歷搜索指令適用的轉(zhuǎn)換模式，

將其存儲(chǔ)到集合patterns中*/

④ if（patterns= NULL）then

⑤ return；

⑥ end if

⑦ if （inst=base_inst）then

⑧ continue；

⑨ end if

⑩best_score= 0； /*best_score用于記錄最優(yōu)轉(zhuǎn)換模式的分?jǐn)?shù)*/

?best_pattern= NULL； /*best_pattern用于記錄最優(yōu)的轉(zhuǎn)換模式*/

/*遍歷所有的轉(zhuǎn)換模式*/

? for eachpatterninpatterns

?out_inst=patterns.out_inst（）； /*out_inst用于存儲(chǔ)特定轉(zhuǎn)換模式轉(zhuǎn)換后輸出的指令*/

?score=init_score（patterns）； /*初始化特定轉(zhuǎn)換模式的分?jǐn)?shù)*/

?score=score+cal_match_score（base_inst，inst）； /*計(jì)算特定轉(zhuǎn)換模式的分?jǐn)?shù)*/

? if（score＞best_score）then

?best_score=score；

?best_pattern=pattern；

? end if

? end for

?insts_score+=best_score；

?insts_pattern[inst] =best_pattern； /*insts_pattern用于存儲(chǔ)指令序列的最優(yōu)轉(zhuǎn)換模式*/

? end for

? return（insts_score，insts_pattern）.

為了計(jì)算整體指令對(duì)自動(dòng)向量化的收益，需要計(jì)算指令對(duì)的單層自動(dòng)向量化收益以及其子操作數(shù)所組成指令對(duì)的整體指令對(duì)的自動(dòng)向量化收益.SLPM 的目標(biāo)是找到使得整體指令對(duì)自動(dòng)向量化收益相對(duì)最大的同構(gòu)化轉(zhuǎn)換方式.SLP-M 利用每種方法轉(zhuǎn)換后的指令序列的依賴圖，沿著對(duì)應(yīng)的節(jié)點(diǎn)自底向上遞歸統(tǒng)計(jì)和評(píng)估，先評(píng)估子操作數(shù)對(duì)應(yīng)指令對(duì)在每種轉(zhuǎn)換方法下的整體收益，并選擇收益最大的同構(gòu)化轉(zhuǎn)換方式，再進(jìn)行指令對(duì)的整體自動(dòng)向量化的收益評(píng)估和同構(gòu)化轉(zhuǎn)換方法的選擇.具體整體指令對(duì)自動(dòng)向量化收益評(píng)估函數(shù)的偽代碼詳見函數(shù)2 和函數(shù)3.

函數(shù)2.cal_match_score.

輸入：指令base_inst，指令inst；

輸出：匹配分?jǐn)?shù)match_score.

①best_score= 0；

/*若可進(jìn)行擴(kuò)展變換，則進(jìn)行分?jǐn)?shù)評(píng)估*/

② if（can_extend_trans（get_opcode（base_inst），get_opcode（inst）））then

③new_inst=get_extended_expression（base_inst，inst）； /*嘗試進(jìn)行擴(kuò)展變換分析*/

④extend_score=cal_match_score_1（base_inst，new_inst）； /*遞歸計(jì)算指令的操作數(shù)分?jǐn)?shù)*/

⑤ if（extended_score＞best_score）then

⑥best_score=extended_score；

⑦ end if

⑧ end if

/*若可進(jìn)行二元表達(dá)式替換或重排序變換，則進(jìn)行分?jǐn)?shù)評(píng)估*/

⑨ if（can_binary_trans（get_opcode（base_inst），get_opcode（inst）））then

⑩new_inst=get_bin_trans_expression（base_inst，inst）； /*嘗試進(jìn)行二元表達(dá)式替換或重排序變換分析*/

?bin_trans_score= 1 +cal_match_score_1（base_inst，new_inst）； /*遞歸計(jì)算指令的操作數(shù)分?jǐn)?shù)*/

? if（bin_trans_score＞best_score）then

?best_score=bin_trans_score；

? end if

? end if

/*若原始指令可進(jìn)行向量化*/

? if（can_vectorize（base_inst，inst））then

?original_score= 1 +cal_match_score_1（base_inst，inst）；

? if（original_score＞best_score）then

?best_score=original_score；

? end if

? end if

? returnbest_score.

函數(shù)3.cal_match_score_1.

輸入：指令base_inst，指令inst；

輸出：匹配分?jǐn)?shù)score.

①score= 0；

② for eachoperand_idxofbase_inst

③base_operand=get_operand（base_inst，operand_idx）； /*求得基準(zhǔn)指令的操作數(shù)*/

④new_operand=get_operand（new_inst，operand_idx）；/*求得轉(zhuǎn)換得到新指令的操作數(shù)*/

/*調(diào)用函數(shù)cal_match_score求得最優(yōu)轉(zhuǎn)換模式和分?jǐn)?shù)*/

⑤operand_score=cal_match_score（base_operand，new_operand）；

⑥score+=operand_score；

⑦ end for

⑧ returnscore.

值得注意的是，由于基于shuffle 指令的變換方式會(huì)引入額外運(yùn)行代價(jià)，SLP-M 評(píng)估其收益需特殊考慮，在上述類似評(píng)估方法的基礎(chǔ)上減去生成shuffle 指令的代價(jià).SLP-M 在評(píng)估完基于shuffle 指令的收益后，將其與其他同構(gòu)化轉(zhuǎn)換方法的收益比較，選擇收益較高的同構(gòu)化轉(zhuǎn)換方法.待完成處理程序的整體同構(gòu)化轉(zhuǎn)換方式的選擇后，SLP-M 利用LLVM中SLP 實(shí)現(xiàn)的評(píng)估模型判定該程序是否實(shí)施向量化，若評(píng)估有收益則實(shí)施向量化.

處理程序?qū)?yīng)依賴圖的高度對(duì)SLP-M 的性能收益和編譯時(shí)間存在較大的影響.SLP-M 利用操作符和操作數(shù)的類型信息進(jìn)行同構(gòu)化轉(zhuǎn)換方法的選擇，分析程序?qū)?yīng)依賴圖高度越高，采用的類型相似信息越多，越有助于同構(gòu)化轉(zhuǎn)換方法的選擇.然而，采用優(yōu)化程序?qū)?yīng)依賴圖高度過(guò)高并不總能有效提升程序的性能收益，并且由于需要分析更多的同構(gòu)化轉(zhuǎn)換選擇方式和評(píng)估計(jì)算，增加了較多的編譯優(yōu)化時(shí)間.其實(shí)，為了有效提升程序的性能，考慮整體優(yōu)化程序?qū)?yīng)依賴圖不是必要的.由于SLP-M 方法與SLP 都是類似自底向上構(gòu)建同構(gòu)圖，與根節(jié)點(diǎn)距離較近的節(jié)點(diǎn)對(duì)于向量化的收益評(píng)估更重要[7]，而節(jié)點(diǎn)的高度越高，其對(duì)應(yīng)向量化的收益評(píng)估的重要性越低.由于依賴圖高度較高的節(jié)點(diǎn)依賴于高度較低節(jié)點(diǎn)，因同構(gòu)化轉(zhuǎn)換需要生成更多數(shù)量的額外代價(jià)指令的概率增高，因此高度較高的節(jié)點(diǎn)可向量化的難度更大.我們?cè)趯?shí)驗(yàn)中發(fā)現(xiàn)絕大部分可有效向量化的層數(shù)不超過(guò)20.

同構(gòu)化轉(zhuǎn)換方法選擇的具體實(shí)施過(guò)程示例如圖7 所示.圖7（a）（b）分別為一段包含4 條語(yǔ)句的輸入程序及其對(duì)應(yīng)的數(shù)據(jù)依賴圖.假設(shè)SLP-M 正在處理由指令x0，x1，x2，x3 組成的指令序列〈x0，x1，x2，x3〉，其操作分別為訪存、移位、乘法、移位.為了選擇基準(zhǔn)指令，SLP-M 遍歷指令序列中的每條指令，計(jì)算與其他指令在對(duì)應(yīng)依賴圖中匹配的節(jié)點(diǎn)個(gè)數(shù)或者可通過(guò)二元表達(dá)式替換可轉(zhuǎn)換為匹配的節(jié)點(diǎn)個(gè)數(shù)，將其作為基準(zhǔn)指令的評(píng)估分?jǐn)?shù).

Fig.7 An example of isomorphism transform selection method圖7 同構(gòu)化轉(zhuǎn)換選擇方法示例

首先，評(píng)估x0 作為基準(zhǔn)指令的分?jǐn)?shù)，其他指令及其二元表達(dá)式替換后的指令與x0 都沒有操作類型相同的形式，因此指令x0 作為基準(zhǔn)指令的評(píng)估分?jǐn)?shù)是0.

其次，評(píng)估x1 作為基準(zhǔn)指令的分?jǐn)?shù)，x0 和x2 及其二元表達(dá)式替換后的指令與x1 都沒有操作類型相同的形式，因此x1 分別與x0 和x2 的匹配分?jǐn)?shù)均是0，x3 與x1 的操作類型相同，繼續(xù)沿著對(duì)應(yīng)依賴圖，向其子孫節(jié)點(diǎn)遞歸計(jì)算匹配分?jǐn)?shù)，共計(jì)包含3 個(gè)匹配節(jié)點(diǎn)，分別是移位操作、內(nèi)存訪問(wèn)操作、常量操作.因此x1 與x3 的匹配分?jǐn)?shù)是3.綜上，x1 作為基準(zhǔn)指令的評(píng)估分?jǐn)?shù)是與上述其他指令匹配分?jǐn)?shù)的總和，即score_sum（x1）=0+0+3=3.

然后，評(píng)估x2 作為基準(zhǔn)指令的分?jǐn)?shù)，x0 與x2 沒有操作類型相同的形式，因此x2 與x0 的匹配分?jǐn)?shù)是0，x1 和x3 都可通過(guò)二元表達(dá)式替換轉(zhuǎn)換為與x2 操作類型相同的形式，繼續(xù)沿著對(duì)應(yīng)依賴圖，向其子孫節(jié)點(diǎn)遞歸計(jì)算匹配分?jǐn)?shù)得到x2 分別與x1 和x3 的匹配分?jǐn)?shù)都是3.綜上，x2 作為基準(zhǔn)指令的評(píng)估分?jǐn)?shù)score_sum（x2）= 0+3+3=6.

最后，評(píng)估x3 作為基準(zhǔn)指令的分?jǐn)?shù)，與計(jì)算x1作為基準(zhǔn)指令的評(píng)估過(guò)程類似，計(jì)算得到x3 作為基準(zhǔn)指令的評(píng)估分?jǐn)?shù)是3.根據(jù)上文計(jì)算得到的匹配分?jǐn)?shù)，指令x2 的分?jǐn)?shù)最多，因此SLP-M 將其作為基準(zhǔn)指令.

SLP-M 在確定基準(zhǔn)指令后，搜索在指令序列〈x0，x1，x2，x3〉中包含基準(zhǔn)指令x2 的所有指令對(duì)，如指令對(duì)〈x2，x0〉，〈x2，x1〉，〈x2，x3〉，然后針對(duì)每個(gè)指令對(duì)，搜索所有適用的轉(zhuǎn)換模式pattern0，pattern1，pattern2等.接下來(lái)計(jì)算每個(gè)同構(gòu)化轉(zhuǎn)換模式下的指令對(duì)的整體自動(dòng)向量化的收益.

指令對(duì)〈x2，x0〉包含同構(gòu)化轉(zhuǎn)換模式pattern0.pattern0 將x0 擴(kuò)展變換為x0′，根據(jù)3.4 節(jié)所示的單層指令對(duì)收益評(píng)估方法，x2 與x0′的單層指令對(duì)的收益為0，繼續(xù)沿著對(duì)應(yīng)依賴圖，向其子孫節(jié)點(diǎn)遞歸計(jì)算單層指令對(duì)的收益，x2 和x0′的第1 個(gè)操作數(shù)節(jié)點(diǎn)對(duì)應(yīng)的指令分別是B[2]和B[0]，其操作類型相同，因此B[2]和B[0]的單層指令對(duì)的收益為1，同理x2 和x0′的第2 個(gè)操作數(shù)都是常量操作，它們對(duì)應(yīng)的單層指令對(duì)的收益為1，進(jìn)而得出指令對(duì)〈x2，x0〉在轉(zhuǎn)換模式pattern0 下的整體指令對(duì)的自動(dòng)向量化收益為score（pattern0）=0+1+1=2.

指令對(duì)〈x2，x1〉包含同構(gòu)化轉(zhuǎn)換模式pattern1 和pattern2.pattern1 將x1 擴(kuò)展變換為x1′，根據(jù)3.4 節(jié)所示的單層指令對(duì)收益評(píng)估方法，x2 與x1′的單層指令對(duì)收益為0，繼續(xù)沿著對(duì)應(yīng)依賴圖，向其子孫節(jié)點(diǎn)遞歸計(jì)算單層指令對(duì)的收益，x2 和x1′的第1 個(gè)操作數(shù)節(jié)點(diǎn)對(duì)應(yīng)的指令分別是B[2]和移位操作，其操作類型不同，并且沒有適用的同構(gòu)化方法可將移位操作轉(zhuǎn)為與B[2]操作類型相同的形式，因此B[2]和移位操作的單層指令對(duì)的收益為0.x2 和x1′的第2 個(gè)操作數(shù)都是常量操作，它們對(duì)應(yīng)的單層指令對(duì)的收益為1.進(jìn)而得出指令對(duì)〈x2，x1〉在轉(zhuǎn)換模式pattern1 下的整體指令對(duì)的自動(dòng)向量化收益為score（pattern1）=1.pattern2 是將B[1]＜＜C等價(jià)替換為B[1]×C′，其中x1′是由x1 二元表達(dá)式替換生成的，x2 與x1′的單層指令對(duì)的收益為1，繼續(xù)沿著對(duì)應(yīng)依賴圖，向其子孫節(jié)點(diǎn)遞歸計(jì)算單層指令對(duì)的收益，x2 和x1′的第1 個(gè)操作數(shù)節(jié)點(diǎn)對(duì)應(yīng)的指令分別是B[2]和B[1]，其操作類型相同，B[2]和B[1]的單層指令對(duì)的收益為1.同理x2和x1′的第2 個(gè)操作數(shù)都是常量操作，它們對(duì)應(yīng)的單層指令對(duì)的收益為1，進(jìn)而得出指令對(duì)〈x2，x1〉在轉(zhuǎn)換模式pattern2 下的整體指令對(duì)的自動(dòng)向量化收益為score（pattern2）=1+1+1=3.

指令對(duì)〈x2，x3〉包含同構(gòu)化轉(zhuǎn)換模式pattern3 和pattern4，其計(jì)算過(guò)程與pattern1 和pattern2 的計(jì)算過(guò)程類似，它們整體指令對(duì)的自動(dòng)向量化收益分別為3 和1.

在計(jì)算完所有轉(zhuǎn)換模式下的整體指令對(duì)的自動(dòng)向量化收益，根據(jù)收益選擇每個(gè)指令對(duì)的同構(gòu)化轉(zhuǎn)換方式.指令對(duì)〈x2，x0〉只包含一種同構(gòu)化轉(zhuǎn)換模式pattern0，將其作為指令對(duì)〈x2，x0〉同構(gòu)化轉(zhuǎn)換方式.指令對(duì)〈x2，x1〉包含2 種同構(gòu)化轉(zhuǎn)換方式pattern1 和pattern2，由于pattern2 下的整體指令對(duì)的自動(dòng)向量化收益相對(duì)較高，因此pattern2 作為指令對(duì)〈x2，x1〉的同構(gòu)化轉(zhuǎn)換方式，同理，pattern3 作為指令對(duì)〈x2，x3〉的同構(gòu)化轉(zhuǎn)換方式.

在分析完成指令對(duì)〈x2，x0〉，〈x2，x1〉，〈x2，x3〉的同構(gòu)化轉(zhuǎn)換方式后，SLP-M 也就確定了指令序列〈x0，x1，x2，x3〉中每條指令的同構(gòu)化轉(zhuǎn)換方式，如圖7（g）（h）所示.

在選出同構(gòu)化轉(zhuǎn)換方法后，SLP-M 方法實(shí)施相應(yīng)轉(zhuǎn)換，并繼續(xù)向其子節(jié)點(diǎn)方向擴(kuò)展同構(gòu)鏈，直到遇到葉子節(jié)點(diǎn)或者無(wú)適用的同構(gòu)化轉(zhuǎn)換為止.

對(duì)于可同時(shí)處理的指令數(shù)量，SLP-M 方法與已有方法如PSLP 和LSLP 等類似，根據(jù)實(shí)際處理器所支持的SIMD 擴(kuò)展部件的寄存器長(zhǎng)度和程序特征選擇向量化因子[14].若處理指令存在差異如指令類型或排布等，本文將嘗試?yán)脭U(kuò)展變換和二元表達(dá)式替換等同構(gòu)化轉(zhuǎn)換方法并進(jìn)行選擇.若可利用上述方式進(jìn)行同構(gòu)化轉(zhuǎn)換且有收益則進(jìn)行向量化，否則采用與PSLP 和LSLP 類似的方法，將向量化因子減半，繼續(xù)進(jìn)行同構(gòu)化分析及轉(zhuǎn)換，直到存在有收益的向量化轉(zhuǎn)換方式或者向量化因子等于1 時(shí)為止.

4 實(shí)驗(yàn)與結(jié)果分析

本文基于LLVMv10.0 實(shí)現(xiàn)了SLP-M 方法，從構(gòu)造函數(shù)、基于SPEC CPU 2017/2006/2000 和MediaBench[28]測(cè)試集提取的核心函數(shù)、整體測(cè)試3 個(gè)方面對(duì)SLPM 方法進(jìn)行測(cè)試，并與SLP 方法和PSLP 方法進(jìn)行對(duì)比.目前LLVM 中實(shí)現(xiàn)的SLP 方法如LLVM-SLP 已經(jīng)集成了LSLP 和SN-SLP 方法，本文不再另外單獨(dú)將LSLP 和SN-SLP 與SLP-M 比較.實(shí)驗(yàn)所用計(jì)算機(jī)的處理器型號(hào)為Intel i7-4 790，其主頻為 3.2 GHz，支持AVX2，AVX1，SSE 向量指令集，其中AVX2 的向量寄存器長(zhǎng)度為256 b，它能同時(shí)處理4 個(gè)double 數(shù)據(jù)或者8 個(gè)float 數(shù)據(jù).AVX1 和SSE 的向量寄存器長(zhǎng)度為128 b，它能同時(shí)處理2 個(gè)double 數(shù)據(jù)或者4 個(gè)float 數(shù)據(jù).測(cè)試處理器包含4 個(gè)物理核，每個(gè)物理核可 支持2 個(gè) 邏 輯 核，L1 緩 存 大 小 為32 KB（8way，64B/line），L2 為256 KB（8way，64B/line），L3 為8 MB（共享內(nèi)存），內(nèi)存為20 GB，操作系統(tǒng)為Ubuntu20.04.實(shí)數(shù)域的運(yùn)算性質(zhì)在計(jì)算機(jī)的浮點(diǎn)實(shí)現(xiàn)存在偏差[29-30]，為了保證基于等價(jià)表達(dá)式的程序變換，維持原始程序語(yǔ)義不變，本文采用原始LLVM 編譯器中相關(guān)變換對(duì)操作及操作數(shù)類型的限制規(guī)則，具體詳見LLVM 的常量折疊以及強(qiáng)度削弱優(yōu)化的具體實(shí)現(xiàn)[31].如3.4 節(jié)所述隨著彼此依賴指令數(shù)量的增多，本文方法所需的編譯運(yùn)行時(shí)間逐步增多，絕大部分可有效向量化程序?qū)?yīng)依賴圖高度較低，為了確保SLP-M編譯優(yōu)化在合理時(shí)間范圍內(nèi)，本文實(shí)驗(yàn)限定優(yōu)化程序?qū)?yīng)依賴圖的高度不超過(guò)20.后續(xù)程序員可綜合考慮程序特征和優(yōu)化時(shí)間設(shè)定該數(shù)值.

4.1 構(gòu)造函數(shù)測(cè)試

為了考察各種SLP 向量化方法的分析處理能力，本文構(gòu)造了多種非同構(gòu)指令序列的程序，覆蓋了各種典型的語(yǔ)句間差異，包括操作類型不同、操作個(gè)數(shù)不同、數(shù)據(jù)類型不同及語(yǔ)句數(shù)量不同.具體如表3所示.

本文測(cè)試了多種自動(dòng)向量化方法在構(gòu)造測(cè)試程序上運(yùn)行時(shí)間，計(jì)算了各種自動(dòng)向量化方法相對(duì)于在關(guān)閉SLP 向量化優(yōu)化條件下的O3 優(yōu)化加速比，也就是LLVM 編譯器關(guān)閉SLP 向量化功能的優(yōu)化，并打開其他所有LLVM O3 編譯優(yōu)化功能，包括開啟循環(huán)自動(dòng)向量化和循環(huán)展開優(yōu)化等，其編譯選項(xiàng)為-O3-march=haswell -mtune=haswell -fno-slp-vectorize，后續(xù)為描述方便，本文利用O3 表示上述的編譯優(yōu)化.其他多種自動(dòng)向量化方法都是在O3 優(yōu)化條件的基礎(chǔ)上打開特定的向量化優(yōu)化方法.除了測(cè)試SLPM 外，本文還測(cè)試了在SLP-M 優(yōu)化基礎(chǔ)上關(guān)閉二元表達(dá)式替換功能優(yōu)化的性能，用于評(píng)估二元表達(dá)式替換優(yōu)化對(duì)性能的影響，為了描述方便，用SLP-MRelaceOff 表示.性能結(jié)果如圖8 所示，其中，橫軸表示測(cè)試程序，縱軸表示不同方法在測(cè)試程序上相對(duì)于O3 的 性 能 加 速 比.LLVM-SLP、 PSLP、 SLP-MRelaceOff、SLP-M 的 平 均 加 速 比 分 別 為1.08，1.29，1.34，3.17.對(duì)于大部分程序，SLP-M 顯著提升了程序的性能，而LLVM-SLP 和PSLP 對(duì)程序的性能提升幅度相對(duì)較小.

Fig.8 Speedup ratios of various methods on constructing kernel functions圖8 不同方法在構(gòu)造核心函數(shù)上的加速比

下面分析多種優(yōu)化方法對(duì)構(gòu)造函數(shù)編譯優(yōu)化的測(cè)試結(jié)果，分別從操作個(gè)數(shù)不同、操作類型不同、操作個(gè)數(shù)及操作類型都不同的3 類構(gòu)造函數(shù)進(jìn)行分析.

1）操作個(gè)數(shù)不同的程序包括測(cè)試程序s1，s4，s8 等.LLVM-SLP 對(duì)其中大部分程序，如s1 和s4，未實(shí)施自動(dòng)向量化，也未有效提升該類程序的性能.PSLP，SLP-M-RelaceOff，SLP-M 對(duì)其中所有程序?qū)嵤┝俗詣?dòng)向量化，進(jìn)一步提升了程序的性能.

2）操作類型不同的程序包括測(cè)試程序s2，s5 和s9 等.LLVM-SLP，PSLP，SLP-M-RelaceOff 通 過(guò) 生 成shuffle 指令，對(duì)其中少數(shù)程序?qū)嵤┝俗詣?dòng)向量化（如s2 和s5），提升了該類程序的性能.SLP-M 對(duì)該類程序都實(shí)施了自動(dòng)向量化，且通過(guò)二元表達(dá)式替換和減少了其中的操作種類數(shù)量，進(jìn)一步提升了該類程序的 性 能.例 如LLVM-SLP，PSLP，SLP-M-RelaceOff，SLP-M 都對(duì)s9 實(shí)施了自動(dòng)向量化，LLVM-SLP，PSLP，SLP-M-RelaceOff 都利用了向量乘法、向量除法、shuffle 指令組合實(shí)施了自動(dòng)向量化.我們發(fā)現(xiàn)盡管LLVM-SLP 方法采用了向量的代碼形式，而與O3 采用標(biāo)量的代碼形式比較，并未帶來(lái)實(shí)際性能提升.SLPM 將s9 中的除法轉(zhuǎn)為乘法，并實(shí)施了自動(dòng)向量化，由于乘法操作相比于除法操作在Intel 機(jī)器上實(shí)際執(zhí)行快數(shù)倍，因此顯著提升了程序的性能，s2 也類似.

3）操作數(shù)量及類型都不同的程序包括測(cè)試程序s6，s10，s15 等，LLVM-SLP，PSLP，SLP-M-RelaceOff 對(duì)于其中大部分程序要么未實(shí)施向量化，要么只對(duì)其中部分語(yǔ)句實(shí)施向量化，對(duì)該類程序的程序的性能提升幅度較少.SLP-M 對(duì)該類程序都實(shí)施了自動(dòng)向量化，顯著地提升了該類程序的性能.例如s6 包含訪存、乘法、移位操作.LLVM-SLP 未對(duì)該類程序?qū)嵤┳詣?dòng)向量化，PSLP 方法和SLP-M-RelaceOff 方法盡管可將該類程序轉(zhuǎn)換為同構(gòu)的形式，但是向量化無(wú)收益，因此未實(shí)施向量化.SLP-M 方法采用了多種同構(gòu)化轉(zhuǎn)換方法，將s6 第1 條語(yǔ)句的b[0]轉(zhuǎn)換為b[0]×1，將第3條語(yǔ)句中的移位操作轉(zhuǎn)為乘法操作，進(jìn)而實(shí)施了向量化，有效提升了程序的性能.對(duì)于s15，SLP-M 可顯著提升其性能的原因與s9 類似，都是減少了向量除法操作以及重組指令操作帶來(lái)的性能提升.

除了測(cè)試和計(jì)算了性能加速比外，本文還通過(guò)LLVM 自帶的性能評(píng)估模型，評(píng)估了各種向量化方法對(duì)于構(gòu)造核心函數(shù)的性能收益.圖9 是LLVM 統(tǒng)計(jì)多種優(yōu)化方法對(duì)測(cè)試程序相對(duì)于O3 編譯優(yōu)化減少指令代價(jià)的統(tǒng)計(jì)圖，其中橫軸表示核心函數(shù)，縱軸表示程序經(jīng)過(guò)自動(dòng)向量化方法的優(yōu)化后，利用LLVM評(píng)估模型得出的減少的指令代價(jià).總體而言，SLP-M方法自動(dòng)向量化減少的指令代價(jià)多于其他方法，這反映出SLP-M 方法較強(qiáng)的自動(dòng)向量化優(yōu)化能力，能夠有效提升向量化的性能收益.

Fig.9 Reduced instruction costs of auto-vectorization methods on constructing kernel functions圖9 構(gòu)造核心函數(shù)自動(dòng)向量化方法減少的指令代價(jià)

4.2 實(shí)際應(yīng)用核心函數(shù)測(cè)試

本文從實(shí)際應(yīng)用如SPEC CPU 2017/2006/2000 和MediaBench2 基準(zhǔn)測(cè)試集中提取代表性的核心函數(shù)代碼片段，如表4 所示.提取的核心函數(shù)代碼片段主要來(lái)自在科學(xué)計(jì)算領(lǐng)域和多媒體領(lǐng)域計(jì)算密集型的代碼（如生物系統(tǒng)模擬和影像關(guān)系追蹤等），其熱點(diǎn)包含較多的非同構(gòu)指令序列，代碼覆蓋了程序中語(yǔ)句間的典型差異，包括操作類型不同、操作個(gè)數(shù)不同，同時(shí)包含類型及個(gè)數(shù)上的差異.本文通過(guò)在循環(huán)中多次執(zhí)行同一個(gè)核心函數(shù)，使得總體運(yùn)行時(shí)間超過(guò)20 min，以減小環(huán)境因素影響.

Table 4 Description of the Kernel Functions表4 核心函數(shù)描述

本文測(cè)試了多種自動(dòng)向量化方法在核心函數(shù)上的運(yùn)行時(shí)間，計(jì)算了各種自動(dòng)向量化方法相對(duì)于O3的加速比，結(jié)果如圖10 所示，其中，橫軸表示測(cè)試程序，縱軸表示不同方法在測(cè)試程序上相對(duì)于O3 的性能加速比，LLVM-SLP，PSLP，SLP-M-RelaceOff，SLPM 的平均加速比分別為1.0，1.25，1.1，1.6.SLP-M 相對(duì)于LLVM-SLP（包含LSLP 和SN-SLP）的平均性能提升了40.4%，相對(duì)于PSLP 的平均性能提升了21.8%.

Fig.10 Speedup ratios of various methods on kernel functions圖10 不同方法在核心函數(shù)上的加速比

下面分析多種優(yōu)化方法對(duì)實(shí)際應(yīng)用核心函數(shù)編譯優(yōu)化的測(cè)試結(jié)果，也是分別對(duì)不同操作個(gè)數(shù)、不同操作類型、不同操作個(gè)數(shù)及操作類型的3 類程序進(jìn)行分析.

對(duì)于第1 類操作個(gè)數(shù)不同的程序，SLP 未能有效提升該類程序的性能，PSLP，SLP-M-RelaceOff，SLPM 可顯著提升其中部分程序的性能.對(duì)于函數(shù)gl_render_vb，其核心代碼片段如圖11（a）所示，盡管4 條語(yǔ)句都是同構(gòu)的，但是第4 條語(yǔ)句在自動(dòng)向量化前編譯器將其中的i- 0 變換為i，使得轉(zhuǎn)換后的語(yǔ)句不是同構(gòu)的，LLVM-SLP 未對(duì)該程序?qū)嵤┳詣?dòng)向量化，PSLP，SLP-M-RelaceOff，SLP-M 對(duì)其實(shí)施了自動(dòng)向量化，具體的不同自動(dòng)向量化生成的匯編代碼如圖12所示.對(duì)于函數(shù)u2s，其核心代碼片段如圖11（b）所示，LLVM-SLP 和PSLP 同構(gòu)化轉(zhuǎn)換能力較弱，無(wú)法對(duì)其進(jìn)行同構(gòu)化轉(zhuǎn)換，因此未對(duì)其實(shí)施自動(dòng)向量化，實(shí)際以標(biāo)量形式執(zhí)行.而SLP-M-RelaceOff 和SLP-M 盡管可對(duì)其實(shí)施自動(dòng)向量化，但是性能反而不如標(biāo)量程序的性能，通過(guò)查看匯編程序發(fā)現(xiàn)，SLP-M 將32 b 轉(zhuǎn)換為8 b 類型數(shù)據(jù)中生成了代價(jià)較高的非對(duì)齊訪存以及重組指令，在這種情況下自動(dòng)向量化不能帶來(lái)性能收益，然而在實(shí)施向量化評(píng)估中本文采用了LLVM 的評(píng)估代價(jià)模型，其分析是有收益的，因此對(duì)該程序?qū)嵤┝讼蛄炕?，其性能不如?biāo)量程序.函數(shù)calc_pair_energy與函數(shù)gl_render_vb類似，如圖11（c），SLP 未對(duì)其實(shí)施自動(dòng)向量化，PSLP，SLP-M-RelaceOff，SLP-M 對(duì)其實(shí)施了自動(dòng)向量化.

Fig.11 Code fragments of the kernel function with different numbers with opcodes圖11 不同操作數(shù)量的核心函數(shù)代碼片段

Fig.12 Assembly instructions generated by the code fragments of the function gl_render_vb圖12 函數(shù)gl_render_vb 代碼片斷生成的匯編指令

對(duì)于第2 類操作類型不同的程序，SLP-M 與LLVM-SLP，PSLP，SLP-M-RelaceOff 比較，對(duì)該類程序性能的提升幅度更大.對(duì)于函數(shù)start_pass_fdctmgr，其核心代碼片段如圖13（a）所示，LLVM-SLP，PSLP，SLP-M-RelaceOff，SLP-M 都對(duì)其實(shí)施了向量化.函數(shù)box_UVCoord多處包含如圖13（b）所示的代碼片段，編譯器在自動(dòng)向量化前將其中的第1 個(gè)除法轉(zhuǎn)為乘法，使得2 條語(yǔ)句轉(zhuǎn)換為非同構(gòu)的形式.LLVM-SLP未對(duì)圖13（b）中程序?qū)嵤┝俗詣?dòng)向量化，PSLP 和SLPM-RelaceOff 通過(guò)生成向量除法指令，對(duì)圖13（b）中的程序?qū)嵤┝俗詣?dòng)向量化.SLP-M 方法將除法指令轉(zhuǎn)為乘法指令，并利用向量乘法指令對(duì)其實(shí)施向量化，與PSLP 比較，未生成延時(shí)較大的向量除法，由于乘法操作相比于除法操作在Intel 機(jī)器上實(shí)際執(zhí)行將近數(shù)倍，因此顯著提升了程序的性能，具體不同自動(dòng)向量化生成的匯編代碼如圖14所示.函數(shù)ssim_end1 核心代碼以及優(yōu)化方法生成的匯編代碼如圖13（c）和圖14所示，LLVM-SLP，PSLP，SLP-M-RelaceOff，SLP-M 都未對(duì)其實(shí)施自動(dòng)向量化，它們優(yōu)化后程序的性能差異不大.

Fig.13 Code fragments of the kernel function of different types of opcodes圖13 不同操作類型的核心函數(shù)代碼片段

Fig.14 Assembly instructions for the code fragments of the function box_UVCoord generated by various auto-vectorization methods圖14 多種自動(dòng)向量化方法對(duì)于函數(shù)box_UVCoord 代碼片斷生成的匯編指令

對(duì)于第3 類操作數(shù)量及類型都不同的程序，這類程序需利用多種同構(gòu)化轉(zhuǎn)換方法并進(jìn)行合理選擇，才能對(duì)其實(shí)施自動(dòng)向量化，目前在被測(cè)試的優(yōu)化方法中只有SLP-M 顯著提升了該類程序的性能.如函數(shù)intra16x16_plane_pred_mbaff，其單層循環(huán)的核心代碼片段如圖15（a）所示，其中i是歸納變量，編譯器在自動(dòng)向量化優(yōu)化前，對(duì)于不同的i值將代碼轉(zhuǎn)為不同的形式如i= 8，那么第1 行語(yǔ)句，（i-7）×ib會(huì)被轉(zhuǎn)換為ib，第4 行 語(yǔ) 句 的（i-4）×ib轉(zhuǎn) 為ib＜＜2.LLVM-SLP 未對(duì)原始程序?qū)嵤┳詣?dòng)向量化，PSLP 將函數(shù)實(shí)施了同構(gòu)化轉(zhuǎn)換，但是需添加較多數(shù)量的重組指令，使得向量化無(wú)性能收益，因而未實(shí)施向量化.SLP-M 同時(shí)選擇運(yùn)用了擴(kuò)展變換和二元表達(dá)式替換變換，將函數(shù)轉(zhuǎn)為同構(gòu)的形式，有效實(shí)施了自動(dòng)向量化，提升了性能，具體不同方法生成的匯編代碼如圖15（b）（c）（d）所示.

Fig.15 Code fragments of the function intra16x16_plane_pred_mbaff圖15 函數(shù)intra16x16_plane_pred_mbaff 代碼片段

函數(shù)intra16x16_plane_pred核心代碼片段如圖16所示，與函數(shù)intra16x16_plane_pred_mbaff類似，只有SLP-M 方法能夠?qū)ζ鋵?shí)施自動(dòng)向量化.

Fig.16 Code fragments of the function intra16x16_plane_pred圖16 函數(shù)intra16x16_plane_pred 代碼片段

函數(shù)start_pass核心代碼片段如圖17 所示，盡管原始代碼是同構(gòu)的，但是編譯器在自動(dòng)向量化前通過(guò)常量折疊優(yōu)化將語(yǔ)句1 中（（b[0]×16 384）+1 024）＞＞11 轉(zhuǎn)為b[0]＜＜3，變換后的語(yǔ)句并不是同構(gòu)的，LLVMSLP，PSLP，SLP-M-RelaceOff 都未對(duì)其實(shí)施自動(dòng)向量化，SLP-M 利用多種同構(gòu)化轉(zhuǎn)換方法，對(duì)左移和右移操作時(shí)通過(guò)添加shuffle 指令進(jìn)行擴(kuò)展，然后通過(guò)2步擴(kuò)展變換將b[0]轉(zhuǎn)換為b[0]×1+0 的形式，進(jìn)而將原始程序轉(zhuǎn)為同構(gòu)的形式，并實(shí)施了自動(dòng)向量化，有效提升了程序的性能，具體匯編代碼如圖17 所示.

Fig.17 Assembly instructions for the code fragments of the function start_pass generated by various auto-vectorization methods圖17 多種自動(dòng)向量化方法對(duì)于函數(shù)start_pass 代碼片斷生成的匯編指令

通過(guò)上述核心函數(shù)測(cè)試結(jié)果可以看出，對(duì)于第1類程序，除了u2s外，SLP-M 與目前業(yè)界測(cè)試最優(yōu)方法的向量化優(yōu)化能力持平，對(duì)于第2，3 類程序，SLPM 優(yōu)于其他方法.尤其對(duì)于第3 類程序，其他測(cè)試方法無(wú)法對(duì)該類程序進(jìn)行有效向量化，而SLP-M 可顯著提升了該類程序的性能.從上述測(cè)試看出，對(duì)于操作個(gè)數(shù)或操作類型不同的程序，采用單一的同構(gòu)化轉(zhuǎn)換方法帶來(lái)的自動(dòng)向量化性能收益并不總是最優(yōu)的，SLP-M 利用了多種同構(gòu)化轉(zhuǎn)換方法，并對(duì)其進(jìn)行選擇，可有效提升這類程序的性能.

與4.1 節(jié)類似，本文也通過(guò)LLVM 自帶的性能評(píng)估模型評(píng)估了各種自動(dòng)向量化方法對(duì)于實(shí)際應(yīng)用核心函數(shù)的性能收益.具體結(jié)果如圖18 所示.總體而言，SLP-M 自動(dòng)化向量化減少的指令代價(jià)多于LLVM-SLP和PSLP，這反映出SLP-M 具備較強(qiáng)的向量化優(yōu)化能力，能夠有效提升向量化的性能收益.

Fig.18 Reduced instruction costs of auto-vectorization methods on kernel functions圖18 核心函數(shù)自動(dòng)向量化方法減少的指令代價(jià)

4.3 整體測(cè)試

本文利用SPEC CPU 2017/2006/2000 和MediaBench2基準(zhǔn)測(cè)試集測(cè)試SLP-M 的整體加速比，排除了實(shí)驗(yàn)的自動(dòng)向量化方法都未有效觸發(fā)實(shí)施轉(zhuǎn)換的程序，執(zhí)行基準(zhǔn)測(cè)試集12 次，分別剔除性能最優(yōu)以及最差的測(cè)試數(shù)據(jù)，然后對(duì)剩余的測(cè)試數(shù)據(jù)取幾何平均值.整體加速比如圖19 所示，其中橫軸表示測(cè)試程序，縱軸表示不同方法在測(cè)試程序上相對(duì)于O3 的性能加速比.LLVM-SLP，PSLP，SLP-M-RelaceOff，SLP-M的平均加速比分別為1.06，1.07，1.09，1.11.SLP-M 方法對(duì)于整體性能的提升優(yōu)于實(shí)驗(yàn)的其他自動(dòng)向量化方法.

Fig.19 Speedup ratios of various auto-vectorization methods on whole benchmarks圖19 不同自動(dòng)向量化方法在整體基準(zhǔn)測(cè)試程序集上的加速比

SLP-M 相比于其他向量化方法對(duì)不同類型程序性能提升幅度不同，分別對(duì)3 類情況進(jìn)行論述：1）SLP-M 與已有方法相比程序的性能進(jìn)一步提升；2）SLP-M 與已有方法相比程序的性能下降；3）SLP-M與已有方法相比程序性能提升幅度趨同.

對(duì)于第1 種類型如453.povray，623.xalancbmk_s，625.x264_s測(cè)試程序，SLP-M 與已有方法比較進(jìn)一步提升了程序的性能.由于SLP-M 應(yīng)用了多種同構(gòu)化轉(zhuǎn)換方法并進(jìn)行選擇，提升了同構(gòu)化轉(zhuǎn)換能力，進(jìn)而增加了向量化的機(jī)會(huì).453.povray，623.xalancbmk_s，625.x264_s包含較多加法、減法、乘法組合運(yùn)算操作，SLP-M 對(duì)這些程序利用二元表達(dá)式等價(jià)替換及其他同構(gòu)化轉(zhuǎn)換方法對(duì)該類程序轉(zhuǎn)換同構(gòu)指令序列，并實(shí)施了自動(dòng)向量化，有效提升了這些程序的性能.

對(duì)于第2 種類型如416.gamess，SLP-M 相比于PSLP 使得416.gamess性能下降.我們查看程序編譯后生成的匯編代碼，分析LLVM 的評(píng)估模型，發(fā)現(xiàn)程序性能下降并不是SLP-M 程序變換引起的，而是由于LLVM 的評(píng)估模型不準(zhǔn)確造成的.LLVM 未充分考慮超標(biāo)量處理器中標(biāo)量指令級(jí)并行和訪存因素，對(duì)于本質(zhì)上無(wú)收益的程序變換，卻認(rèn)為有收益，進(jìn)而實(shí)施無(wú)效的程序變換，導(dǎo)致程序性能下降.

對(duì) 于第3 種 類 型 如cjpeg，433.milc，447.dealII測(cè)試程序，SLP-M 與PSLP 對(duì)于上述程序性能提升幅度趨同，這是由于利用這2 種方法后實(shí)施相同優(yōu)化轉(zhuǎn)換方式程序的占比較高，對(duì)于這些程序SLP-M 應(yīng)用了與PSLP 類似的同構(gòu)化轉(zhuǎn)換方法（基于shuffle 指令的變換方式）進(jìn)行向量化，如433.milc和447.dealII熱點(diǎn)區(qū)域，或都不對(duì)其向量化.

SLP-M 對(duì)整體的性能提升沒有像對(duì)核心函數(shù)那樣提升顯著，主要有3 方面的原因：1）SLP-M 能夠有效觸發(fā)的程序并不是都是應(yīng)用程序的熱點(diǎn)區(qū)域；2）SLP-M 進(jìn)行同構(gòu)化轉(zhuǎn)換方法的選擇屬于啟發(fā)式方法，對(duì)有些程序的同構(gòu)化方法的選擇并不是最優(yōu)的，這就使得程序優(yōu)化引入的性能提升是有限的；3）LLVM 的自動(dòng)向量化代價(jià)模型準(zhǔn)確性能有待提高，本文采用LLVM 自帶的自動(dòng)向量化評(píng)估模型，發(fā)現(xiàn)有些程序經(jīng)過(guò)SLP-M 的同構(gòu)化分析評(píng)估是有收益的，可實(shí)施自動(dòng)向量化，然而，實(shí)際上對(duì)于有些程序并未帶來(lái)性能提升，甚至使其性能略有下降.

SLP-M 與現(xiàn)有方法比較可有效提升程序的性能.由于SPEC CPU Benchmark 是編譯優(yōu)化領(lǐng)域標(biāo)桿式的測(cè)試集，許多研究者針對(duì)該測(cè)試集進(jìn)行研究及優(yōu)化[20]，且SLP 本身是自動(dòng)向量化領(lǐng)域重要的優(yōu)化方法，也可用于其他多個(gè)領(lǐng)域如二進(jìn)制翻譯等，SLP-M 對(duì)于SPEC CPU Benchmark 的性能提升依然是難能可貴的.

5 總 結(jié)

基本的SLP 方法在處理非同構(gòu)指令序列時(shí)存在局限性.本文提出了一種SLP 擴(kuò)展方法——SLP-M，它與現(xiàn)有方法相比，將多種方法應(yīng)用于非同構(gòu)指令序列的同構(gòu)化轉(zhuǎn)換中，發(fā)揮了多種同構(gòu)化轉(zhuǎn)換方法的優(yōu)勢(shì)，進(jìn)一步擴(kuò)大了“同構(gòu)化轉(zhuǎn)換”處理的對(duì)象范圍，整體提升了自動(dòng)向量化的性能收益.該方法并不局限于本文提到的幾種同構(gòu)化轉(zhuǎn)換方法，還可在此基礎(chǔ)上擴(kuò)展應(yīng)用更多的同構(gòu)化轉(zhuǎn)換方法，如三角函數(shù)等價(jià)變換、指數(shù)等價(jià)變換等.隨著更多方法的應(yīng)用，有助于進(jìn)一步發(fā)揮多種方法的優(yōu)勢(shì)，提升SLP 向量化的適用范圍和收益.

本文基于LLVM 編譯器實(shí)現(xiàn)了SLP-M 方法，并基于SPEC CPU 2017 等測(cè)試集進(jìn)行了測(cè)試實(shí)驗(yàn).實(shí)驗(yàn)表明，對(duì)于核心函數(shù)代碼片段，SLP-M 方法相對(duì)于LLVM-SLP 方法（包含LSLP 和SN-SLP 方法）的平均性能提升了40.4%，相對(duì)于PSLP 方法的平均性能提升了21.8%.對(duì)于整體性能測(cè)試，SLP-M 方法相對(duì)于LLVM-SLP 方法（包含LSLP 和SN-SLP 方法）的平均性能提升了5%，相對(duì)于PSLP 方法的平均性能提升了4.1%.

指令序列同構(gòu)化轉(zhuǎn)換方法的選擇直接影響SLPM 方法的適用范圍及性能收益，本文采用的單層指令對(duì)和整體指令的向量化收益結(jié)合性能評(píng)估和選擇方法有效提升了程序的性能收益，然而該方法屬于啟發(fā)式方法，實(shí)驗(yàn)發(fā)現(xiàn)對(duì)于少數(shù)程序未帶來(lái)性能提升.下一步深入分析各種同構(gòu)化轉(zhuǎn)換方法的特點(diǎn)，從適用范圍、性能收益和程序特征等角度考慮，研究更好的選擇策略和方法如機(jī)器學(xué)習(xí)方法[32].

作者貢獻(xiàn)聲明：馮競(jìng)舸提出了方法思路和實(shí)驗(yàn)方案，完成實(shí)驗(yàn)并撰寫論文；賀也平、陶秋銘、馬恒太提出指導(dǎo)性意見.