王向前，王昊

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

分簇結(jié)構(gòu)向量寄存器分配策略研究*

王向前，王昊

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

通過(guò)分簇結(jié)構(gòu)實(shí)現(xiàn)向量化執(zhí)行是一種高效而靈活的體系結(jié)構(gòu)選擇。在編譯中間表示里，向量指令與標(biāo)量指令交疊出現(xiàn)。分簇結(jié)構(gòu)向量化實(shí)現(xiàn)的特殊方式給傳統(tǒng)的寄存器分配框架帶來(lái)了挑戰(zhàn)。針對(duì)該問(wèn)題，本文從向量指令的表示形式、Callee/Caller寄存器劃分、向量寄存器分配等進(jìn)行研究，并給出全局與局部向量寄存器的分配方法。

分簇結(jié)構(gòu)；向量寄存器分配；Callee/Caller

引 言

分簇結(jié)構(gòu)[1-2]是一種可以有效增強(qiáng)體系結(jié)構(gòu)并行性而不會(huì)引起昂貴硬件代價(jià)的體系結(jié)構(gòu)。分簇結(jié)構(gòu)上向量化機(jī)制實(shí)現(xiàn)較為特殊，通過(guò)多個(gè)簇的組合實(shí)現(xiàn)高效而靈活的向量化執(zhí)行。

本文針對(duì)分簇結(jié)構(gòu)上向量化實(shí)現(xiàn)的特殊本質(zhì)，研究向量化的表示形式以及在傳統(tǒng)寄存器分配框架上實(shí)現(xiàn)分簇結(jié)構(gòu)向量寄存器分配的方法。

1 向量指令編譯后端表示

編譯器后端中間語(yǔ)言一般為一種基于目標(biāo)機(jī)指令的中間語(yǔ)言表示，在進(jìn)入代碼生成階段時(shí)由高級(jí)中間語(yǔ)言生成。指令注釋、寄存器分配、指令調(diào)度都運(yùn)行在該中間語(yǔ)言上。后端層次結(jié)構(gòu)通過(guò)控制流結(jié)構(gòu)表示；控制流結(jié)構(gòu)由若干基本塊組成；基本塊包括若干操作指令；操作指令主要由操作碼、源操作數(shù)、目的操作數(shù)組成。

分簇結(jié)構(gòu)上向量指令是通過(guò)多簇組合支持的，并不像傳統(tǒng)的向量指令，如表1所列，分簇結(jié)構(gòu)分為x、y、z、t四個(gè)簇，每個(gè)簇相同物理編號(hào)的寄存器組成向量寄存器。例如向量寄存器xyztR7表示128位向量寄存器，其中分別由x簇上的R7寄存器、y簇上R7寄存器、z簇上R7寄存器、t簇上R7寄存器組合而成；而表1中向量寄存器xyztR7:6則為256位向量寄存器，其中分別由x簇上的R7/R6寄存器、y簇上R7/R6寄存器、z簇上R7/R6寄存器、t簇上R7/R6寄存器組合而成。這種向量指令的源操作數(shù)和目的操作數(shù)實(shí)際上是通過(guò)x、y、z、t四個(gè)簇上的寄存器文件組合而成，和傳統(tǒng)的單個(gè)向量寄存器有本質(zhì)區(qū)別?；诖耍蛄恐噶畹暮蠖吮硎居袃蓚€(gè)思路：一是分布表示方法，二是整體表示法。如表2所列，表中分簇結(jié)構(gòu)也為x、y、z、t四個(gè)簇。

表1 分簇結(jié)構(gòu)上向量指令舉例

分布表示法是把向量指令的操作數(shù)一一羅列，通過(guò)若干虛擬寄存器表示向量寄存器結(jié)構(gòu)，每個(gè)虛擬寄存器就是一般化的標(biāo)量寄存器類型，為浮點(diǎn)類型或定點(diǎn)類型。它能夠表示和其它非向量化指令的定值-使用關(guān)系。優(yōu)點(diǎn)是利用了分簇結(jié)構(gòu)向量指令的本質(zhì)，保證了代碼生成階段數(shù)據(jù)流分析的精確性，能夠很好地支持傳統(tǒng)自動(dòng)向量化[3]技術(shù)。缺點(diǎn)是格式不夠簡(jiǎn)潔，過(guò)于冗雜。

表2 向量指令表示方法

整體表示法是通過(guò)指令屬性指示該指令是向量指令。優(yōu)點(diǎn)是具有格式簡(jiǎn)潔的特點(diǎn)。缺點(diǎn)是不能保證代碼生成階段數(shù)據(jù)流分析的精確性，有可能有問(wèn)題；不能很好地支持超字級(jí)并行性向量化[4]技術(shù)。

綜合考慮兩種向量指令的表示方法，可以得出結(jié)論：分布表示法雖然不夠簡(jiǎn)潔，但作為向量指令的表示方法是比較合適的。

2 寄存器分配概述

為提高程序運(yùn)行的速度，源程序中用戶定義的變量應(yīng)該最大限度地映射到寄存器上。在寄存器分配之前，中間代碼使用虛擬寄存器，數(shù)量不受限制，寄存器分配的過(guò)程就是把這些虛擬寄存器映射到物理寄存器上的過(guò)程。

寄存器分配有個(gè)重要的基本概念：生命期(Live Range，簡(jiǎn)記為L(zhǎng)R)，是指一個(gè)值從定義到最后一次使用之間的活躍范圍，通常用活躍的基本塊的集合描述。寄存器分配就是為L(zhǎng)R分配寄存器。

寄存器分配分為兩部分：全局寄存器分配與局部寄存器分配。全局寄存器分配一般采用國(guó)際主流的圖著色方法[5]；局部寄存器分配則采取線性掃描分配[6]算法。與寄存器分配密切相關(guān)的一個(gè)內(nèi)容是寄存器Callee/Caller類別的劃分。

Callee寄存器又叫被調(diào)用保存寄存器，使用該類型的寄存器時(shí)，必須在使用前保存，使用后恢復(fù)。Caller寄存器又叫調(diào)用者保存寄存器，如果有函數(shù)調(diào)用，必須在函數(shù)調(diào)用前保存，調(diào)用后恢復(fù)。由于進(jìn)行寄存器分配時(shí)，可見(jiàn)范圍一般為一個(gè)函數(shù)，必須事先約定哪些寄存器屬于Callee寄存器，哪些寄存器屬于Caller寄存器?；谶^(guò)程間的寄存器分配可以精確地完成寄存器的保存與恢復(fù)，因?yàn)樵摷夹g(shù)可以掌握各個(gè)函數(shù)調(diào)用圖相關(guān)函數(shù)的寄存器使用情況，但是過(guò)程間寄存器技術(shù)代價(jià)過(guò)于昂貴，而且并非所有的場(chǎng)景下該技術(shù)都適合(例如動(dòng)態(tài)鏈接的函數(shù))。

Callee/Caller寄存器的劃分是有講究的。如果把所有寄存器都劃分為Caller寄存器，Caller函數(shù)有可能保存和恢復(fù)Callee函數(shù)從來(lái)沒(méi)使用的寄存器。而如果所有寄存器都設(shè)定為Callee寄存器，Callee函數(shù)則需要保存和恢復(fù)所有它使用的任何寄存器。根據(jù)經(jīng)驗(yàn)，可以把寄存器平均分為Caller/Callee寄存器，這樣寄存器分配的效果較好。

Callee寄存器又叫持久寄存器、全局寄存器；Caller寄存器又叫草稿寄存器、局部寄存器。這是由它們的特性決定的。為了減小保存和恢復(fù)寄存器的代價(jià)，跨Call傳遞的值應(yīng)該分配在Callee寄存器上，這些值具有函數(shù)層面全局的特性，屬于全局寄存器分配的任務(wù)；用于局部計(jì)算的值應(yīng)該分配在Caller寄存器上，這些計(jì)算具有基本塊內(nèi)局部的性質(zhì)，主要屬于局部寄存器分配的任務(wù)；未跨越函數(shù)調(diào)用的全局寄存器，本質(zhì)上屬于Caller寄存器，所以全局寄存器分配的任務(wù)也包括部分Caller寄存器的分配。

在進(jìn)行兩種寄存器分配之前，要進(jìn)行活躍變量分析，確定每一個(gè)虛擬寄存器的屬性：全局還是局部。如果變量的活躍范圍跨越多個(gè)基本塊，確定為全局虛擬寄存器；反之，則確定為局部虛擬寄存器。

3 向量寄存器分配策略

向量寄存器分配分為兩個(gè)部分，全局向量寄存器分配和局部向量寄存器分配。全局寄存器分配基于經(jīng)典的圖著色分配[5]，首先基于生命周期建立沖突圖，為沖突的生命周期分配不同的寄存器?；诜执亟Y(jié)構(gòu)上向量寄存器是由標(biāo)量寄存器組合而成，提出了針對(duì)分簇結(jié)構(gòu)的全局向量寄存器分配方法。

全局向量寄存器分配方法分為以下步驟：

① 在生成寄存器生命周期時(shí)，為組成向量寄存器的分布在各個(gè)簇上的標(biāo)量寄存器分別建立生命周期，并維護(hù)一個(gè)指向所屬向量寄存器的標(biāo)量生命周期列表，稱為向量生命周期；

② 向量生命周期按照其組合的若干標(biāo)量生命周期建立沖突圖，建立沖突圖并不會(huì)區(qū)分向量生命周期與標(biāo)量生命周期；

③ 在為標(biāo)量生命周期寄存器分配之前，首先依次遍歷向量生命周期，進(jìn)行向量寄存器分配；

④ 根據(jù)沖突圖分別得到組成向量生命周期的幾個(gè)標(biāo)量生命周期在每個(gè)簇上的允許可用寄存器集合；

⑤ 當(dāng)前向量生命周期的允許可用寄存器集合分簇結(jié)構(gòu)上分別與其簇上可用Caller寄存器集合進(jìn)行與運(yùn)算，得到每個(gè)簇上新的寄存器可用集合；

⑥ 遍歷每個(gè)簇上寄存器可用集合，為組成向量生命周期的標(biāo)量生命周期分配符合規(guī)則的物理寄存器，即相同的物理寄存器，完成當(dāng)前向量生命周期的寄存器分配；

⑦ 如果分配失敗，則當(dāng)前向量生命周期的每個(gè)簇上允許可用寄存器集合分別與其簇上可用Callee寄存器集合進(jìn)行與運(yùn)算，得到每個(gè)簇上新的寄存器可用集合；

⑧ 遍歷每個(gè)簇上寄存器可用集合，為組成向量生命周期的標(biāo)量生命周期分配符合規(guī)則的物理寄存器，完成當(dāng)前向量生命周期的寄存器分配；

⑨ 如果失敗，進(jìn)行溢出操作，重新進(jìn)行向量寄存器分配。

局部寄存器分配，一般采用線性掃描分配策略[6]，依次從后向前遍歷基本塊的每一條指令，如果掃描到未進(jìn)行局部寄存器分配的虛擬寄存器的“使用”，則從空閑物理寄存器表格分配一個(gè)物理寄存器給該虛擬寄存器；如果掃描到虛擬寄存器的“定值”，該虛擬寄存器肯定已經(jīng)分配了物理寄存器，把相應(yīng)的物理寄存器歸還給空閑寄存器列表。

進(jìn)行局部向量寄存器分配時(shí)，采用的方法與全局向量寄存器分配方法類似，主要步驟也是在對(duì)基本塊從后向前線性掃描每一條指令時(shí)，如果掃描到向量寄存器的“使用”，一次性為組合成向量寄存器的每個(gè)簇上標(biāo)量寄存器從每個(gè)簇上的Caller空閑寄存器中遍歷選擇出相同編號(hào)的物理寄存器，完成局部向量寄存器分配；如果分配失敗，則進(jìn)行寄存器溢出操作；如果掃描到向量寄存器的“定值”，則歸還該分配給該向量寄存器的物理寄存器到空閑寄存器列表。可見(jiàn)，局部向量寄存器分配時(shí)只涉及到Caller空間寄存器。

結(jié) 語(yǔ)

[1] Terechko A S.Clustered VLIW architectures:a quantitativeapproach[D].Eindhoven：Technical University Eindhoven，2007.

[2] Lapinskii V S,Jacome M F,De Veciana G A.Cluster assignment for high-performance embedded VLIW processors[J].ACM Transactions on Design Automation of Electronic Systems (TODAES),2002,7(3):430-454.

[3] Hohenauer M,Engel F,Leupers R,et al.A SIMD optimization framework for retargetablecompilers[J].Acm Transactions on Architecture&Code Optimization,2009,6(1):118-125.

[4] Chame J,Hall M,Shin J.Superword-level parallelism in the presence of control flow[J].International Symposium on Code Generation and Optimization,2005:165-175.

[5] Torczon P B K D C L.Improvements To Graph Coloring Register Allocation[J].Acm Transactions on Programming Languages & Systems,1994,16(3):428-455.

[6] Wimmer C,Franz M.Linear scan register allocation on SSA form[J].Proceedings of the International Symposium on Code Generation&Optimization,2010:170-179.

王向前(工程師)，主要研究方向?yàn)镈SP編譯優(yōu)化與應(yīng)用算法開(kāi)發(fā)。

結(jié) 語(yǔ)

參考文獻(xiàn)

[1] 洪一,方體蓮,趙斌,等.“魂芯一號(hào)”數(shù)字信號(hào)處理器及其應(yīng)用[J].中國(guó)科學(xué):信息科學(xué),2015,45(4):574-586.

[2] 朱艷,林廣棟,黃光紅.Eclipse開(kāi)源代碼的多核DSP調(diào)試系統(tǒng)集成[J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用,2015,15(9):11-13.

[3] 權(quán)彥清.基于BWDSP104X系統(tǒng)的嵌入式操作系統(tǒng)內(nèi)存管理和上下文切換的實(shí)時(shí)性研究[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué),2015.

[4] 孫魯毅.四種流行的嵌入式實(shí)時(shí)操作系統(tǒng)的比較研究-VxWorks,QNX,ucLinux,RTEMS[J].計(jì)算機(jī)應(yīng)用與軟件,2007,24(8):196-197.

[5] Introduction to Programming with DSF[EB/OL].[2017-04].http://help.eclipse.org/indigo/topic/org.eclipse.cdt.doc.

朱艷，研究方向?yàn)镈SP集成開(kāi)發(fā)環(huán)境。

(責(zé)任編輯：薛士然 收稿日期：2017-04-24)

Research on Vector Register Allocation Method for Clustering

Wang Xiangqian,Wang Hao

(No.38 Research Institude,China Electronics Technology Group Corporation,Hefei 230088, China)

It is an efficient and flexible architecture choice to realize SIMD execution through clustering structure.And then the vector instructions probably come out together with the scalar instructions in the intermediate representation of compiler.The special way for SIMD impementation on clustering structure brings challenges to the traditional register allocation framework.To solve the problem,in the paper,the representation style of the vector instructions,the partition of Callee/Caller register,the vector register allocation are studied,and the global and local vector register allocation methods are proposed.

clusting structure;vector register allocation;Callee/Caller

國(guó)家“核心電子器件、高端通用芯片及基礎(chǔ)軟件產(chǎn)品”重大專項(xiàng)“面向先進(jìn)雷達(dá)的高性能DSP”(No.2012ZX01034001-001)資助。

TP314

A

?士然

2017-03-21)