1.一种融合寄存器对需求的寄存器选择方法,其特征在于,包括:
步骤S1:分析各寄存器分配候选者在符号寄存器对中出现的情况;
步骤S2:计算各寄存器分配候选者的奇偶号收益P;所述奇偶号收益P是指一个寄存器分配候选者在其涉及的那些符号寄存器对操作数中如果该候选者被指派奇数或偶数编号寄存器时将获得的收益;
步骤S3:为各寄存器分配候选者进行寄存器指派。
2.根据权利要求1所述的融合寄存器对需求的寄存器选择方法,其特征在于,所述步骤S2中,如果一个寄存器分配候选者未出现在任何符号寄存器对中,其奇偶号收益值为0,否则,奇偶号收益的计算方法为:SWa-SWb,其中,SWa为它在偶号或奇号寄存器侧的各次应用对应的权重值之和,SWb为它在奇号或偶号寄存器侧的各次应用对应的权重值之和。
3.根据权利要求2所述的融合寄存器对需求的寄存器选择方法,其特征在于,所述权重值取K的Ld次方,其中K为一个大于或等于1的数,Ld的值为对寄存器分配候选者的一次应用所在的指令对应的循环层次最大深度值。
4.根据权利要求1或2或3所述的融合寄存器对需求的寄存器选择方法,其特征在于,所述步骤S3中,在寄存器指派过程中,对于每个寄存器分配候选者Rs,获取相应的可用寄存器构成集合SA,然后按照以下过程从SA中选择一个寄存器Ra指派给Rs:步骤S301:如果已知Rs有首选寄存器Rp,且Rp在SA中,则将Rp作为Ra;
步骤S302:如果Rs还没有首选寄存器,且Rs未曾出现在任何符号寄存器对中,则按启发式一从SA中选择一个寄存器作为Ra;
步骤S303:如果Rs还没有首选寄存器,且Rs至少一次出现在任何符号寄存器对中,则先尝试根据Rs所在的、已经指派了一个寄存器的所有符号寄存器对的情况,按启发式二选择一个寄存器作为Ra;如果无法使用启发式二来成功获得寄存器,则根据奇偶号收益的值Ps按启发式三从SA中选择一个寄存器作为Ra。
在上述过程中,所述启发式一为:从SA中取编号最大或最小的那个寄存器,或者随机选择一个寄存器;在上述过程中,所述启发式二为:从Rs所在的符号寄存器对中找出各个已经指派了的寄存器所在的物理寄存器对中的另外一个寄存器,形成集合SB,然后在一定条件下从SB中找到一个符合Ps要求的寄存器;所述启发式三为:如果Ps等于0,则保持SA不变;如果Ps大于或小于0,则根据Ps对应的寄存器编号奇偶性需求从SA中删除编号为奇数或偶数的那些寄存器,如果此时SA为空则恢复删除前的状态,然后,从SA中按启发式一选择一个寄存器。
5.根据权利要求4所述的融合寄存器对需求的寄存器选择方法,其特征在于,在所述步骤S303完成之后,即对Rs的寄存器指派完毕之后,遍历Rs所在的各个符号寄存器对进行以下处理:若某对只有Rs指派了寄存器Ra,且Ra满足Rs的寄存器编号奇偶性要求,则设置此对涉及的另一个寄存器分配候选者Rst的首选寄存器为:Ra的配对寄存器Rb,只要Rb满足Rst的奇位率的需求。
6.根据权利要求1或2或3所述的融合寄存器对需求的寄存器选择方法,其特征在于,在上述过程中,指令的数据结构包括:
1)指令与w集合的映射关系:一条指令可能涉及多个w,这些w构成一个对应的集合;这条指令与对应的w集合构成一个映射对;所有这样的映射对构成一个映射集合,称为mI_sA;
2)w与符号寄存器对集合的映射关系:一个w可能出现在多个符号寄存器对中,这些符号寄存器对构成一个对应的集合;这个w与这个集合构成一个映射对;所有这样的映射对构成一个映射集合,称为mA_sAP;
3)奇偶号收益数组:对于每个至少一次处于符号寄存器对中的w,用一个奇偶号收益值作为为其指派寄存器的依据之一;所有w的这些收益值保存在数组aPW中;
4)两个不同的w构成的对wp以及多个wp构成的集合sWP;由两个在同一符号寄存器对中不同的w构成一对寄存器分配候选者wp,多个wp构成集合sWP;
5)w与其首选寄存器的映射关系:在寄存器指派过程中,可能会为尚未执行寄存器指派处理的寄存器分配候选者先确定一个首选寄存器Rp;各个w与其对应的Rp的映射对构成一个集合,称为mW_Rp;
6)w与其所获得的物理寄存器的映射关系:各个w与指派给它的物理寄存器映射对构成一个集合,称为mW_PR。
7.根据权利要求6所述的融合寄存器对需求的寄存器选择方法,其特征在于,在计算各寄存器分配候选者的奇偶号收益时,采用以下步骤:
1)清空aPW,然后令奇偶号收益值数组aPW的元素个数为寄存器分配候选者的数量;
2)遍历所有寄存器分配候选者;对于某个寄存器分配候选者w,执行下面的步骤的处理;
3)如果mA_sAP的键中不包含w,则令w的奇偶号收益值为0,否则,w的奇偶号收益的计算方法为:Ps=SWa-SWb,其中,SWa为它在偶号或奇号寄存器侧的各次应用对应的权重值之和,SWb为它在奇号寄存器侧的各次应用对应的权重值之和,若Swa是对应的奇号,则为偶号,w的一次应用对应的权重值取10Ld,其中Ld的值为该应用所在的指令对应的循环层次最大深度值;如果指令不在循环中,则Ld的值为0,循环层次尝试越大,Ld的值越大;计算Ps值的具体方法为:a)初始化令Ps=0;
b)使用一个二重循环,其外层循环遍历w的各个use和各个def对应的指令Ix,其内层循环遍历Ix的各个操作数;在内层循环中,对于访问了w的操作数,当w位于符号寄存器对的奇号侧,令Ps=Ps-10Ld,当w位于符号寄存器对的偶号侧,令Ps=Ps+10Ld。
8.根据权利要求7所述的融合寄存器对需求的寄存器选择方法,其特征在于,在融合寄存器对需求的物理寄存器选择时,包括以下步骤:从stk的顶部取出一个寄存器分配候选者w,按下面的步骤为w选择一个物理寄存器:
1)遍历w的邻接表,读取w的各相邻结点中已经获得的物理寄存器,保存在集合usedRegsByNeighbors中;根据可指派的物理寄存器集合,求usedRegsByNeighbors的补集candRegs;如果candRegs为空,结束指派过程;否则,执行下一步;
2)定义空集合SA,然后将candRegs的内容复制到SA中;
3)如果在mW_Rp中有w对应的首选寄存器Rp,且SA中也包含有Rp,则将Rp指派给w,转到第9)步;否则,进入下一步;
4)如果SA中只有唯一的一个元素Rx,则将Rx指派给w,转到第9)步;否则,进入下一步;
5)如果w不是mA_sAP的键,转到第7)步;否则,从aPW读取w的奇偶号收益值P;
6)基于已有指派结果进行寄存器选择,即尝试从w所在的、已经指派了一个寄存器的对中选择一个对应的、满足P的要求的候选寄存器Rx;如果能够获得Rx,则将Rx指派给w,转到第9)步;否则,进入下一步;
7)判断P是否为0;如果是,转到第9)步;否则,进入下一步;
8)按P值从SA中删除奇号或偶号寄存器;如果P大于0,则从SA中删除所有奇号寄存器,如果P小于0,则从SA中删除所有偶号寄存器;
9)判断SA是否为空;如果不为空,从SA中选择编号最大的寄存器Rx,将Rx指派给w,转到第9)步;如果为空,将candRegs的内容复制到SA中,转到第7)步;
10)分析剩余寄存器分配候选者的首选寄存器;结束对w的寄存器指派处理。
9.根据权利要求8所述的融合寄存器对需求的寄存器选择方法,其特征在于,在分析剩余寄存器分配候选者的首选寄存器时,即在为某个寄存器分配候选者w指派了一个物理寄存器Rp之后,为尚等待进行寄存器指派处理的其他相关的寄存器分配候选者分析它们的首选寄存器;包括以下步骤:
1)从mA_sAP中读取w对应的符号寄存器对集合sAP;如果sAP为空,结束处理;否则,进入下一步;
2)遍历sAP中的各个对wp,对每个wp进行如下处理:
a)读取wp中除w之外的另外一个寄存器分配候选者wx,如果该wx已经被指派了物理寄存器,或者已知其首选寄存器,切换到下一个wp后再执行本步骤;否则,进入下一步;
b)获取w在这个wp中的位置信息,如果Rp的编号的奇偶性与该位置信息不匹配,切换到下一个wp后重新执行上述步骤;否则,进入下一步;
c)获得Rp对应的成对寄存器Ro,从aPW读取wx对应的奇偶号收益Px;如果Ro的编号的奇偶性与Px值匹配,则将Ro作为wx的首选寄存器,将它们的映射关系添加到mW_Rp中。