分簇结构向量寄存器分配策略研究*

王向前，王昊

(中国电子科技集团公司 第三十八研究所,合肥 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]，首先基于生命周期建立冲突图，为冲突的生命周期分配不同的寄存器。基于分簇结构上向量寄存器是由标量寄存器组合而成，提出了针对分簇结构的全局向量寄存器分配方法。

全局向量寄存器分配方法分为以下步骤：

① 在生成寄存器生命周期时，为组成向量寄存器的分布在各个簇上的标量寄存器分别建立生命周期，并维护一个指向所属向量寄存器的标量生命周期列表，称为向量生命周期；

② 向量生命周期按照其组合的若干标量生命周期建立冲突图，建立冲突图并不会区分向量生命周期与标量生命周期；

③ 在为标量生命周期寄存器分配之前，首先依次遍历向量生命周期，进行向量寄存器分配；

④ 根据冲突图分别得到组成向量生命周期的几个标量生命周期在每个簇上的允许可用寄存器集合；

⑤ 当前向量生命周期的允许可用寄存器集合分簇结构上分别与其簇上可用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)