1.一种提升指令级并行性的寄存器选择优化方法,其特征在于:
相关的指令数据结构包括:
1)各个基本块中的指令子集列表:对于每个基本块中的指令序列,根据它们之间的依赖关系将它们分成多个指令子集;基本块中的这些指令子集共同构成指令子集列表instnGroupList;
2)指令与指令子集的映射关系:每条指令均在一个指令子集中,它们之间构成一个映射关系对;所有这样的映射关系对构成一个集合mI_igroup;
3)指令与w集合的映射关系:一条指令可能访问了多个w,这些w构成一个对应的集合,这条指令与对应的w集合构成一个映射对;所有这样的映射对构成一个集合,称为mI_sA;
4)w与其所获得的物理寄存器的映射关系:各个w与指派给它的寄存器映射对构成一个集合,称为mW_PR;
具体的执行过程包括:
步骤S1:改进寄存器分配的处理流程,在第一次用变量生命期名称替换函数中对应位置处的变量名之后,回到寄存器分配流程的起始位置重新进行寄存器分配处理;
步骤S2:增加一个处理环节,该环节用于获得函数各基本块内指令间的依赖关系,并根据依赖关系的传递顺序将每个基本块内的指令分成多个子集,将该环节作为寄存器分配的处理过程中的第一个环节;
步骤S3:在寄存器指派处理的初期,在为具体的变量生命期(也称之为寄存器分配候选者,或简称候选者)选择寄存器之前,构建指令与其所在的指令子集的映射关系;
步骤S4:分析与候选者所在指令相关的其他指令中已经使用的寄存器,如果除这些寄存器外还有未被分配的寄存器,则跳转步骤S6;否则,执行步骤S5;
步骤S5:找到同时包含分配候选者及其候选寄存器的指令子集,以单个候选寄存器为单位分别计算指令子集数量和包含候选寄存器的指令数量;
步骤S6:为各寄存器分配候选者选择对依赖关系影响最少的寄存器;上述步骤S3中,在求取指令与指令子集之间的映射关系过程时,采取以下步骤:对于每一个基本块的每一条指令ix,找到ix所依赖的那些指令对应的idn中的最大值idnMax,令ix的idn等于idnMax+1;然后,将相同的idn值的指令放入对应的集合igroup中,igroup即该指令对应的指令子集;最后,将ix与igroup的映射对添加到mI_igroup集合中;
上述步骤S4中,在分析与候选者所在指令相关的其他指令中已经使用的寄存器时,采取以下步骤:步骤S401:找出还没有被与W的相邻(即生命期有交集的)候选者使用的寄存器,构成候选寄存器集合SA;如果SA为空,则没有候选寄存器供w使用,结束指派过程;否则,执行下一步;
步骤S402:求取指令与其涉及的寄存器分配候选者之间的映射关系mI_sA;
步骤S403:根据映射关系mI_sA的内容,分析所有用到W的指令所在的指令子集中已经用到了哪些寄存器,将这些寄存器放到SX中;
步骤S404:计算C=SA-SX;如果C不为空,按一定的规则,如编号最大、最小或随机,从C中选择一个寄存器作为要指派的寄存器;否则执行步骤S5;
上述步骤S402中,在求取指令与其涉及的寄存器分配候选者之间的映射关系过程时,采取以下步骤:对于每一个候选者w,分别遍历每一个对w定值的指令和对w使用的指令,将w添加到这些指令对应的用于存放寄存器候选者的集合SA中;获得指令与候选者集合的映射关系mI_sA;
上述步骤S5中,在分别以单个候选寄存器为单位计算指令子集数量和包含候选寄存器的指令数量时,采取以下步骤:对于候选寄存器集合SA,使用下述启发式一和启发式二进一步处理SA,如果SA在处理后为空,则将SA恢复到其被处理前的状态;如果SA中寄存器的数量为1,则选择该寄存器指派给W;如果SA中剩下的寄存器的数量大于1,则按一定的规则,如编号最大、最小或随机,选择其中的一个寄存器指派给w;
在上述过程中,所述启发式一为从SA中选择对尽量少的指令子集有影响的寄存器,方法是对于SA中每个寄存器reg,分析同时含有W和该reg的指令子集的数量ng,然后,在SA中仅保留最小ng值对应的寄存器外,其他的寄存器全部从SA中移除;
在上述过程中,所述启发式二为从SA中选择对尽量少的指令有影响的寄存器,方法是对于SA中每个寄存器reg,分析同时含有W和该reg的指令子集中用到了该reg的指令数量ni,然后,在SA中仅保留最小ni值对应的寄存器外,其他的寄存器全部从SA中移除。