[发明专利]一种基于组合并算法的偏移量分配优化方法

摘要

本发明公开了一种基于组合并算法的偏移量分配优化方法，特别涉及一种针对“受限制的索引寻址模式”的偏移量分配优化方法。本发明在对访问图进行划分的时候，采用组合并的方法，将权重较大的边优先划分到一个子图内，使得各个子图之内的顶点构成的子图之内边的权重之和最大，增强整体的分组效果。本发明可以对地址寄存器的设定操作，优化了代码，从而提高了编译优化性能。

主权项

1、一种基于组合并算法的偏移量分配优化方法，包括以下步骤：1)将存储器中的每个变量分别构成一个组；2)对所有组形成访问图，即每个组作为访问图的一个节点；3)将访问图中的边按照权重从大到小排序；对于权重相同的边，按照边上的两个节点与访问图中其他节点构成的边的权重之和从小到大排序；将排好序的边依次放入一个队列中；4)判断队列是否为空 若是，则执行步骤6)；若否，则执行下一步骤5)；5)选择队列中的第一条边，所选择的边上的两个节点分别对应两个组，判断这两个组中的变量个数之和是否小于或等于“受限制的索引寻址模式”中利用同一个基地址最多能访问变量的数目m 若是，则将对应的两个组合并成一个组，清空队列，执行步骤2)；若否，则在当前队列中删去这条边，则队列中原第二条边成为现在队列中的第一条边，然后执行步骤4)；6)选取一个组内变量数目小于m的组p，寻找一个组q，使得p与q中变量数目之和小于等于m，如果存在多个满足条件的组q，从中选择组内变量数目最大者，将组p与组q合并；7)重复执行步骤6)，直到所有组内变量数目小于m的组都被处理过；8)根据变量的分组情况决定变量在存储器中的分布，结束。