BWDSP SIMD編譯的寄存器分配優(yōu)化技術(shù)研究※

王昊，王向前

（中國(guó)電子科技集團(tuán)公司第三十八研究所，合肥230088）

BWDSP SIMD編譯的寄存器分配優(yōu)化技術(shù)研究※

王昊，王向前

（中國(guó)電子科技集團(tuán)公司第三十八研究所，合肥230088）

BWDSP是一款自主設(shè)計(jì)的國(guó)產(chǎn)VLIW（超長(zhǎng)指令字）數(shù)字信號(hào)處理器，支持SIMD技術(shù)，其SIMD指令可以在4個(gè)宏上同時(shí)執(zhí)行4個(gè)32位計(jì)算，對(duì)寄存器使用有特殊規(guī)則，Open64編譯器的寄存器分配策略并不適用于這種規(guī)則。本文對(duì)BWDSP SIMD指令的寄存器分配優(yōu)化技術(shù)進(jìn)行了研究，并在BWDSP的編譯器OCC上得以實(shí)現(xiàn)。

DSP；SIMD；寄存器分配

引言

BWDSP［1］是一款32位靜態(tài)超標(biāo)量浮點(diǎn)數(shù)字處理器，采用超長(zhǎng)指令字（Very Long Instruction Word，VLIW）架構(gòu)，支持SIMD技術(shù)。BWDSP核內(nèi)包含4個(gè)基本執(zhí)行宏，代號(hào)是X、Y、Z、T，每個(gè)宏由算術(shù)邏輯單元（ALU）、乘法器（MUL）、移位器（SHF）、超算器（SPU）和一個(gè)通用寄存器組成。

BWDSP最多可以同時(shí)執(zhí)行16條指令，其SIMD指令有其特殊性，本質(zhì)上就是多條相同的指令并發(fā)執(zhí)行，下面將對(duì)其特性進(jìn)行分析，說(shuō)明BWDSP編譯器的寄存器分配需要特殊的優(yōu)化技術(shù)來(lái)滿(mǎn)足SIMD指令的要求。

1 BWDSP SIMD指令的特性分析

BWDSP計(jì)算指令的通用格式如下：

［Macro］Rm=Rnop Rs

Macro是執(zhí)行宏的代號(hào)，op是操作，符號(hào)“||”連接多個(gè)可并行指令，比如：xRm=Rn+Rs是Scalar指令，表示在X宏上執(zhí)行整數(shù)加法操作；xyztRm=Rn+Rs是SIMD指令，表示在X、Y、Z、T四個(gè)宏上同時(shí)執(zhí)行整數(shù)加法操作，等同于xRm=Rn+Rs||yRm=Rn+Rs||zRm=Rn+Rs||tRm=Rn+ Rs。圖1是BWDSP SIMD add指令的執(zhí)行示意圖。

圖1 BWDSP SIMD add指令執(zhí)行示意圖

Intel x86-64 CPU［2］也有SIMD加法指令：

paddd xmmi，xmmk

表示xmmk=xmmi+xmmk，形式很像BWDSP的Scalar加法指令。圖2是Intel x86-64的paddd指令執(zhí)行示意圖。

比較以上兩種類(lèi)型的SIMD加法指令，總結(jié)4點(diǎn)區(qū)別如下：

① x86-64的 paddd指令只需要一個(gè)核執(zhí)行；而B(niǎo)WDSP SIMD add指令需要多個(gè)宏同時(shí)執(zhí)行。

②x86-64的paddd指令只需要使用一個(gè)加法器；而B(niǎo)WDSP SIMD add指令使用4個(gè)加法器。

圖2 Intel x86-64 paddd指令執(zhí)行示意圖

③x86-64 CPU為支持128位SIMD數(shù)據(jù)操作，增加了128位全新的XMM寄存器，這些XMM寄存器屬于同一類(lèi)；而B(niǎo)WDSP只有32位通用寄存器，BWDSP SIMD add指令需要的寄存器在多個(gè)宏上，分屬不同寄存器類(lèi)。

④BWDSP SIMD add指令為相同位置的操作數(shù)分配的不同宏上的寄存器，其編號(hào)必須相同，如圖1中4個(gè)宏的結(jié)果寄存器的編號(hào)都是0，而x86-64沒(méi)有這種約束條件。

以上4點(diǎn)也是對(duì)BWDSP SIMD指令特性的分析，接下來(lái)本文將對(duì)OCC編譯器現(xiàn)有的寄存器分配策略進(jìn)行分析，說(shuō)明其還無(wú)法滿(mǎn)足BWDSP SIMD指令的這些特性，需要設(shè)計(jì)更有針對(duì)性的寄存器分配優(yōu)化技術(shù)。

2 BWDSP Scalar指令的寄存器分配策略

在機(jī)器硬件結(jié)構(gòu)中，寄存器的數(shù)量遠(yuǎn)小于內(nèi)存，但它們是存儲(chǔ)層次結(jié)構(gòu)中最快的介質(zhì)，也是關(guān)鍵資源之一。為提高程序運(yùn)行速度，源程序中用戶(hù)定義的變量應(yīng)該最大限度地映射到寄存器上。寄存器分配是編譯器后端的重要階段，在寄存器分配之前，中間代碼使用虛擬寄存器，數(shù)量不受限制，寄存器分配就是把這些虛擬寄存器映射到物理寄存器上的過(guò)程。

寄存器分配有一個(gè)重要的基本概念——生命期（Live Range，LR），是指一個(gè)值從定義到最后一次使用之間的活躍范圍，通常用活躍的基本塊的集合描述。寄存器分配就是為L(zhǎng)R分配寄存器。BWDSP的編譯器OCC是以O(shè)pen64［3］為基礎(chǔ)開(kāi)發(fā)的，Open64編譯器的寄存器分配分為兩類(lèi)：全局寄存器分配（Global Register Allocation，GRA）和局部寄存器分配（Local Register Allocation，LRA）。全局寄存器分配在一個(gè)函數(shù)范圍內(nèi)，為活躍范圍超出一個(gè)基本塊的LR分配寄存器；局部寄存器分配在一個(gè)基本塊范圍內(nèi)，為只活躍在基本塊內(nèi)部的LR分配寄存器。

2.1 全局寄存器分配

OCC采用Chaitin/Briggs的圖著色算法［5］實(shí)現(xiàn)全局寄存器分配，流程如圖3所示。

GRA_Create過(guò)程創(chuàng)建全局寄存器分配的沖突圖，分為3個(gè)子過(guò)程：

圖3 圖著色算法實(shí)現(xiàn)全局寄存器分配流程

①Create_LRANGEs創(chuàng)建生命期；

②Create_LiveBB_Sets為每個(gè)生命期創(chuàng)建活躍基本塊集合；

③ Create_Interference_Graph創(chuàng)建沖突圖。

GRA_Color過(guò)程執(zhí)行Chaitin/Briggs的圖著色算法為生命期分配寄存器，分為3個(gè)子過(guò)程：

①GRA_Grant_Some_Locals在全局寄存器分配之前為局部寄存器分配預(yù)留一些寄存器，這些寄存器不會(huì)參與全局寄存器分配；

②Simplify對(duì)沖突圖進(jìn)行著色，能夠著色的結(jié)點(diǎn)會(huì)被分配寄存器；

③GRA_Note_Spill對(duì)不能著色的結(jié)點(diǎn)標(biāo)記為溢出結(jié)點(diǎn)。

GRA_Spill過(guò)程對(duì)溢出的生命期在活躍范圍內(nèi)插入相應(yīng)的存取操作，在生命期的賦值操作后插入一條store指令，在該生命期的每個(gè)引用之前插入一條load指令。

2.2 局部寄存器分配

OCC采用線(xiàn)性?huà)呙杈植考拇嫫鞣峙洳呗裕瑥某绦虻拈_(kāi)始向后依次掃描各個(gè)基本塊，流程如圖4所示。

Init_Avail_Regs初始化可用寄存器，Setup_Live_Ranges bb為基本塊bb中的局部TN創(chuàng)建生命期，Assign_Registers （bb，&spill_tn）遍歷bb中的所有操作，為其中的局部TN分配寄存器，成功則返回TRUE，失敗則返回FALSE，spill_tn是寄存器分配失敗的局部TN。如果失敗，調(diào)用Fix_LRA_ Blues，釋放一個(gè)已分配但在bb中沒(méi)有引用的全局寄存器（在bb的Entry部分插入store指令，在bb的EXIT部分插入load指令），然后把該寄存器分配給spill_tn。

圖4 線(xiàn)性?huà)呙杈植考拇嫫鞣峙淞鞒?/p>

3 BWDSP SIMD寄存器分配優(yōu)化技術(shù)

3.1 Scalar指令寄存器分配策略的不足

第2節(jié)詳細(xì)介紹了BWDSP Scalar指令的寄存器分配策略，但它無(wú)法滿(mǎn)足BWDSP SIMD指令的寄存器分配要求，主要是因?yàn)镾calar指令的寄存器分配策略有如下兩點(diǎn)不足：

①無(wú)法同時(shí)在BWDSP四個(gè)宏上分配寄存器。根據(jù)第1節(jié)對(duì)BWDSP SIMD指令的特性分析可知，一個(gè)Scalar指令的某個(gè)操作數(shù)位置需要映射到對(duì)應(yīng)宏（由分簇階段確定）上的一個(gè)寄存器，而一個(gè)SIMD指令的某個(gè)操作數(shù)位置需要映射到4個(gè)宏上的4個(gè)寄存器，并且要求編號(hào)相同。因此Scalar指令的寄存器分配策略目前無(wú)法滿(mǎn)足SIMD指令對(duì)寄存器分配的要求。

②SIMD指令的寄存器分配引入的寄存器溢出操作開(kāi)銷(xiāo)太大。SIMD指令都是在for循環(huán)內(nèi)部，操作數(shù)只活躍在一個(gè)基本塊內(nèi)部，其寄存器分配是由局部寄存器分配完成的。由2.2節(jié)可知，當(dāng)Assign_Registers（bb，&spill_tn）失敗時(shí)，需要溢出一個(gè)全局寄存器，如果Assign_Registers失敗多次，就需要溢出多個(gè)全局寄存器，而這些溢出操作都要插入到for循環(huán)體內(nèi)部。一方面，SIMD指令對(duì)寄存器的需求量大（一個(gè)運(yùn)算類(lèi)SIMD指令最多需要12個(gè)通用寄存器），寄存器分配失敗可能會(huì)引入大量的溢出操作；另一方面，循環(huán)次數(shù)越多，溢出操作帶來(lái)的額外開(kāi)銷(xiāo)就越大。由此帶來(lái)的副作用可能會(huì)抵消SIMD指令對(duì)程序的加速作用，因此應(yīng)該想辦法彌補(bǔ)這個(gè)不足。

3.2 SIMD指令寄存器分配優(yōu)化策略

BWDSP SIMD指令的寄存器分配優(yōu)化策略是在Scalar指令寄存器分配策略基礎(chǔ)上有所創(chuàng)新，是對(duì)前者的補(bǔ)充，兩者綜合在一起滿(mǎn)足為兩類(lèi)指令分配寄存器的需求。SIMD指令寄存器分配優(yōu)化策略需要彌補(bǔ)Scalar指令寄存器分配策略的不足，一方面必須能同時(shí)在BWDSP四個(gè)宏上分配寄存器，另一方面要消除與SIMD指令相關(guān)的寄存器溢出操作。

OCC后端的SIMD指令產(chǎn)生過(guò)程如圖5所示，SIMD指令寄存器分配優(yōu)化策略涉及其中3個(gè)階段，分別是SIMD指令WHIRL中間表示產(chǎn)生、全局寄存器分配和局部寄存器分配，下面將逐一對(duì)各階段的優(yōu)化技術(shù)進(jìn)行詳細(xì)介紹。

3.2.1 GRA為SIMD指令預(yù)留寄存器

SIMD指令的寄存器由LRA階段分配，只能分配caller-save寄存器（調(diào)用函數(shù)負(fù)責(zé)保存的寄存器），GRA先于LRA執(zhí)行，因此GRA階段需要為L(zhǎng)RA預(yù)留適量的callersave寄存器，保證 Scalar指令和SIMD指令有足夠的寄存器可供分配。但GRA又不能把所有callersave寄存器都預(yù)留給LRA，需要保障自身有充足的可分配寄存器。根據(jù)BWDSP的寄存器使用規(guī)則，每個(gè)宏上可供分配的caller-save寄存器有30個(gè)，根據(jù)經(jīng)驗(yàn)選取其中12個(gè)編號(hào)連續(xù)的寄存器預(yù)留給LRA使用，4個(gè)宏上一共有48個(gè)寄存器。

3.2.2 優(yōu)化SIMD指令WHIRL中間表示產(chǎn)生模塊

圖5 編譯器后端SIMD指令產(chǎn)生過(guò)程

理論上，一個(gè)for循環(huán)體內(nèi)的SIMD指令數(shù)量是沒(méi)有限制的，但由2.2節(jié)可知，當(dāng)LRA失敗時(shí)會(huì)產(chǎn)生溢出操作，而且額外開(kāi)銷(xiāo)很大，應(yīng)當(dāng)避免?？疾霣WDSP的指令集可知一個(gè)SIMD運(yùn)算指令在一個(gè)宏上最多使用3個(gè)寄存器（4個(gè)宏上共使用12個(gè)寄存器）。為了不產(chǎn)生溢出操作，根據(jù)GRA預(yù)留的寄存器數(shù)量，每個(gè)for循環(huán)體內(nèi)最多可以有4條SIMD運(yùn)算指令。

當(dāng)一個(gè)for循環(huán)體內(nèi)的SIMD運(yùn)算指令多于4個(gè)時(shí)，需要把該循環(huán)拆分成多個(gè)小循環(huán)，保證每個(gè)小循環(huán)體內(nèi)最多只有4條 SIMD運(yùn)算指令。這個(gè)判斷拆分過(guò)程要在SIMD指令的WHIRL中間表示產(chǎn)生模塊中進(jìn)行，因此要對(duì)原有的產(chǎn)生模塊進(jìn)行優(yōu)化，圖6顯示了原有的 SIMD WHIRL中間表示產(chǎn)生過(guò)程，圖7顯示了為配合SIMD指令寄存器分配而做的優(yōu)化過(guò)程。

圖6 原有的SIMD WHIRL中間表示產(chǎn)生過(guò)程

圖7 優(yōu)化后的SIMD WHIRL中間表示產(chǎn)生過(guò)程

在優(yōu)化過(guò)程中，如果一個(gè)Loop經(jīng)過(guò)分析可以做SIMD優(yōu)化，還要判斷其內(nèi)部的Store操作（每個(gè)SIMD WN的頂層OPC都是Store）數(shù)量是否大于4。如果不大于4，直接執(zhí)行SIMD（Loop），產(chǎn)生Loop的SIMD WHIRL中間表示；如果大于4，就要把Loop拆分成多個(gè)小循環(huán)，并對(duì)每個(gè)小循環(huán)分別執(zhí)行SIMD處理過(guò)程，產(chǎn)生各自的SIMD WHIRL中間表示。以上的優(yōu)化過(guò)程限制了小循環(huán)的體積，保證了SIMD指令在LRA階段不會(huì)產(chǎn)生額外的寄存器溢出操作。

3.2.3 優(yōu)先為SIMD指令分配寄存器

經(jīng)過(guò)上面兩個(gè)優(yōu)化過(guò)程，保證在LRA階段有足夠的寄存器可以分配給SIMD指令，不會(huì)產(chǎn)生寄存器溢出操作，接下來(lái)就要解決LRA無(wú)法同時(shí)在BWDSP四個(gè)宏上分配寄存器問(wèn)題。LRA階段為SIMD指令分配寄存器的優(yōu)化方法的程序原型略——編者注。

針對(duì)BWDSP SIMD指令的特點(diǎn)，程序原型采取的優(yōu)化方法解決了LRA的兩個(gè)關(guān)鍵問(wèn)題：

①保證SIMD指令有足夠可分配的寄存器。函數(shù)Assign_Registers為基本塊bb中的操作（OP）分配寄存器，其中的函數(shù)Init_Insts_Vector為 bb生成 OP序列 Insts_ Vector，在Insts_Vector中，SIMD操作排在Scalar操作之前。接下來(lái)，函數(shù)Assign_Registers_For_OP按照Insts_Vector內(nèi)的順序依次為各個(gè)OPs分配寄存器，因此SIMD指令會(huì)被優(yōu)先分配寄存器，這就保證了SIMD指令有足夠可供分配的寄存器。

②保證SIMD指令的操作數(shù)能夠同時(shí)獲得4個(gè)宏上相同編號(hào)的寄存器。函數(shù)Allocate_Register為虛擬寄存器tn指派物理寄存器，其中的函數(shù)Get_Avail_Reg獲得一個(gè)可用的物理寄存器（reg是寄存器編號(hào)）。如果tn是SIMD指令的操作數(shù)，調(diào)用函數(shù)Delete_Avail_Reg把X、Y、Z、T四個(gè)宏上同為編號(hào)reg的寄存器都標(biāo)記為已使用，這樣該tn所代表的SIMD指令的操作數(shù)就同時(shí)獲得了4個(gè)宏上相同編號(hào)的寄存器。

結(jié)語(yǔ)

本文詳細(xì)介紹了如何在編譯器 OCC上實(shí)現(xiàn)為BWDSP SIMD指令分配寄存器的優(yōu)化技術(shù)，該技術(shù)緊密結(jié)合BWDSP SIMD指令的特殊規(guī)則，可以與已有的Scalar指令寄存器分配策略有機(jī)整合在一起，相輔相成，共同滿(mǎn)足為BWDSP的兩類(lèi)指令分配寄存器的需求。

編者注：本文為期刊縮略版，全文見(jiàn)本刊網(wǎng)站www. mesnet.com.cn。

［1］王昊，黃光紅.基于BWDSP100的傳播分簇算法研究與實(shí)現(xiàn)［J］.中國(guó)集成電路，2014（8）：24-28.

［2］Vernon Turner.White Paper Intel Announces Xeon Processor with 64-Bit Extensions［EB/OL］.［2014-12］.http：//developer.intel.com/technology/64bitextensions/IDC_Intel_Xeon_ Whitepaper.pdf.

［3］University of Houston.Overview of the open64 Compiler Infrastructure［EB/OL］.［2014-12］.http：//www2.cs.uh.edu/～dragon/Documents/open64-doc.pdf.

［4］SGI Inc.Whirl intermediate language specification［EB/OL］. ［2014-12］.http：//open64.sourceforge.net.

［5］Briggs P，Cooper K，Torczon L.Improvements to Graph Coloring Register Allocation［J］.ACM Transactions on Programming Languages and Systems，1994，16（3）：428-455.

王昊（工程師），主要研究方向是DSP編譯器設(shè)計(jì)。

Register Allocation Optimization Technology Based on BWDSP SIMD Compilation※

Wang Hao，Wang Xiangqian
（No.38th Research Institute，China Electronic Technology Group Corporation，Hefei 230088，China）

BWDSP is a self-designed home made VLIW（Very Long Instruction Word）digital signal processor，which supports SIMD technology.BWDSP SIMD instructions can execute four 32-bit computing in four macros simultaneously.BWDSP SIMD instructions have special rules of register usage，but Open64 register allocation strategy is not fit for these rules.This paper carries out research on register allocation optimization of BWDSP SIMD instructions，and the actual process has been implemented on the BWDSP OCC compiler.

DSP；SIMD；register allocation

TP314

A

薛士然

2014-12-01）