王昊，王向前

（中國電子科技集團公司第三十八研究所，合肥230088）

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

王昊，王向前

（中國電子科技集團公司第三十八研究所，合肥230088）

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

DSP；SIMD；寄存器分配

引言

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

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

1 BWDSP SIMD指令的特性分析

BWDSP計算指令的通用格式如下：

［Macro］Rm=Rnop Rs

Macro是執(zhí)行宏的代號，op是操作，符號“||”連接多個可并行指令，比如：xRm=Rn+Rs是Scalar指令，表示在X宏上執(zhí)行整數(shù)加法操作；xyztRm=Rn+Rs是SIMD指令，表示在X、Y、Z、T四個宏上同時執(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í)行示意圖。

比較以上兩種類型的SIMD加法指令，總結4點區(qū)別如下：

① x86-64的 paddd指令只需要一個核執(zhí)行；而BWDSP SIMD add指令需要多個宏同時執(zhí)行。

②x86-64的paddd指令只需要使用一個加法器；而BWDSP SIMD add指令使用4個加法器。

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

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

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

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

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

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

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

2.1 全局寄存器分配

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

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

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

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

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

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

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

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

②Simplify對沖突圖進行著色，能夠著色的結點會被分配寄存器；

③GRA_Note_Spill對不能著色的結點標記為溢出結點。

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

2.2 局部寄存器分配

OCC采用線性掃描局部寄存器分配策略，從程序的開始向后依次掃描各個基本塊，流程如圖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，釋放一個已分配但在bb中沒有引用的全局寄存器（在bb的Entry部分插入store指令，在bb的EXIT部分插入load指令），然后把該寄存器分配給spill_tn。

圖4 線性掃描局部寄存器分配流程

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

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

第2節(jié)詳細介紹了BWDSP Scalar指令的寄存器分配策略，但它無法滿足BWDSP SIMD指令的寄存器分配要求，主要是因為Scalar指令的寄存器分配策略有如下兩點不足：

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

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

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

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

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

3.2.1 GRA為SIMD指令預留寄存器

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

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

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

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

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

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

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

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

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

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

針對BWDSP SIMD指令的特點，程序原型采取的優(yōu)化方法解決了LRA的兩個關鍵問題：

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

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

結語

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

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

［1］王昊，黃光紅.基于BWDSP100的傳播分簇算法研究與實現(xiàn)［J］.中國集成電路，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編譯器設計。

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）