分簇結構向量寄存器分配策略研究*

王向前，王昊

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

分簇結構向量寄存器分配策略研究*

王向前，王昊

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

通過分簇結構實現向量化執行是一種高效而靈活的體系結構選擇。在編譯中間表示里，向量指令與標量指令交疊出現。分簇結構向量化實現的特殊方式給傳統的寄存器分配框架帶來了挑戰。針對該問題，本文從向量指令的表示形式、Callee/Caller寄存器劃分、向量寄存器分配等進行研究，并給出全局與局部向量寄存器的分配方法。

分簇結構；向量寄存器分配；Callee/Caller

引 言

分簇結構[1-2]是一種可以有效增強體系結構并行性而不會引起昂貴硬件代價的體系結構。分簇結構上向量化機制實現較為特殊，通過多個簇的組合實現高效而靈活的向量化執行。

本文針對分簇結構上向量化實現的特殊本質，研究向量化的表示形式以及在傳統寄存器分配框架上實現分簇結構向量寄存器分配的方法。

1 向量指令編譯后端表示

編譯器后端中間語言一般為一種基于目標機指令的中間語言表示，在進入代碼生成階段時由高級中間語言生成。指令注釋、寄存器分配、指令調度都運行在該中間語言上。后端層次結構通過控制流結構表示；控制流結構由若干基本塊組成；基本塊包括若干操作指令；操作指令主要由操作碼、源操作數、目的操作數組成。

分簇結構上向量指令是通過多簇組合支持的，并不像傳統的向量指令，如表1所列，分簇結構分為x、y、z、t四個簇，每個簇相同物理編號的寄存器組成向量寄存器。例如向量寄存器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寄存器組合而成。這種向量指令的源操作數和目的操作數實際上是通過x、y、z、t四個簇上的寄存器文件組合而成，和傳統的單個向量寄存器有本質區別?；诖?，向量指令的后端表示有兩個思路：一是分布表示方法，二是整體表示法。如表2所列，表中分簇結構也為x、y、z、t四個簇。

表1 分簇結構上向量指令舉例

分布表示法是把向量指令的操作數一一羅列，通過若干虛擬寄存器表示向量寄存器結構，每個虛擬寄存器就是一般化的標量寄存器類型，為浮點類型或定點類型。它能夠表示和其它非向量化指令的定值-使用關系。優點是利用了分簇結構向量指令的本質，保證了代碼生成階段數據流分析的精確性，能夠很好地支持傳統自動向量化[3]技術。缺點是格式不夠簡潔，過于冗雜。

表2 向量指令表示方法

整體表示法是通過指令屬性指示該指令是向量指令。優點是具有格式簡潔的特點。缺點是不能保證代碼生成階段數據流分析的精確性，有可能有問題；不能很好地支持超字級并行性向量化[4]技術。

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

2 寄存器分配概述

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

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

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

Callee寄存器又叫被調用保存寄存器，使用該類型的寄存器時，必須在使用前保存，使用后恢復。Caller寄存器又叫調用者保存寄存器，如果有函數調用，必須在函數調用前保存，調用后恢復。由于進行寄存器分配時，可見范圍一般為一個函數，必須事先約定哪些寄存器屬于Callee寄存器，哪些寄存器屬于Caller寄存器?；谶^程間的寄存器分配可以精確地完成寄存器的保存與恢復，因為該技術可以掌握各個函數調用圖相關函數的寄存器使用情況，但是過程間寄存器技術代價過于昂貴，而且并非所有的場景下該技術都適合(例如動態鏈接的函數)。

Callee/Caller寄存器的劃分是有講究的。如果把所有寄存器都劃分為Caller寄存器，Caller函數有可能保存和恢復Callee函數從來沒使用的寄存器。而如果所有寄存器都設定為Callee寄存器，Callee函數則需要保存和恢復所有它使用的任何寄存器。根據經驗，可以把寄存器平均分為Caller/Callee寄存器，這樣寄存器分配的效果較好。

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

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

3 向量寄存器分配策略

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

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

① 在生成寄存器生命周期時，為組成向量寄存器的分布在各個簇上的標量寄存器分別建立生命周期，并維護一個指向所屬向量寄存器的標量生命周期列表，稱為向量生命周期；

② 向量生命周期按照其組合的若干標量生命周期建立沖突圖，建立沖突圖并不會區分向量生命周期與標量生命周期；

③ 在為標量生命周期寄存器分配之前，首先依次遍歷向量生命周期，進行向量寄存器分配；

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

⑤ 當前向量生命周期的允許可用寄存器集合分簇結構上分別與其簇上可用Caller寄存器集合進行與運算，得到每個簇上新的寄存器可用集合；

⑥ 遍歷每個簇上寄存器可用集合，為組成向量生命周期的標量生命周期分配符合規則的物理寄存器，即相同的物理寄存器，完成當前向量生命周期的寄存器分配；

⑦ 如果分配失敗，則當前向量生命周期的每個簇上允許可用寄存器集合分別與其簇上可用Callee寄存器集合進行與運算，得到每個簇上新的寄存器可用集合；

⑧ 遍歷每個簇上寄存器可用集合，為組成向量生命周期的標量生命周期分配符合規則的物理寄存器，完成當前向量生命周期的寄存器分配；

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

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

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

結 語

[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.

王向前(工程師)，主要研究方向為DSP編譯優化與應用算法開發。

結 語

參考文獻

[1] 洪一,方體蓮,趙斌,等.“魂芯一號”數字信號處理器及其應用[J].中國科學:信息科學,2015,45(4):574-586.

[2] 朱艷,林廣棟,黃光紅.Eclipse開源代碼的多核DSP調試系統集成[J].單片機與嵌入式系統應用,2015,15(9):11-13.

[3] 權彥清.基于BWDSP104X系統的嵌入式操作系統內存管理和上下文切換的實時性研究[D].合肥:中國科學技術大學,2015.

[4] 孫魯毅.四種流行的嵌入式實時操作系統的比較研究-VxWorks,QNX,ucLinux,RTEMS[J].計算機應用與軟件,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.

朱艷，研究方向為DSP集成開發環境。

(責任編輯：薛士然 收稿日期：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

國家“核心電子器件、高端通用芯片及基礎軟件產品”重大專項“面向先進雷達的高性能DSP”(No.2012ZX01034001-001)資助。

TP314

A

?士然

2017-03-21)