一种优化堆栈空间的寄存器分配方法

摘要

本发明提出一种优化堆栈空间的寄存器分配方法，所述的方法包含以下步骤：1.寄存器分配器对程序中间文件进行分析，得到数据流图；2.根据数据流图构造程序变量的干涉图；3.对干涉图进行优化，消除假干涉边；4.对干涉图试图着色；如果此步顺利，将没有变量溢出，寄存器分配结束；否则进行下一步；5.对干涉图进行删减，将优先级别低的变量溢出到堆栈中；6.给优先级最高的虚拟寄存器分配实际物理寄存器号；针对步骤5)中的溢出节点，插入相应溢出代码，查询步骤3)的精确干涉图得到为不干涉的溢出变量，分配相同的堆栈偏移；所述的消除假干涉边的方法：对于干涉的两个变量，进一步分析对于推断寄存器不相交的干涉变量，删除两个变量的连线，消除假干涉边。

主权项

一种优化的堆栈空间寄存器分配方法，该方法用于物理寄存器分配时有变量溢出的嵌入式系统中堆栈空间寄存器分配的优化方法，所述的方法包含以下步骤：1)寄存器分配器对程序的中间文件进行数据流分析，得到数据流图；2)根据数据流图构造程序变量的干涉图；3)对干涉图进行优化，消除假干涉边；4)对干涉图试图着色，着色数目为实际物理寄存器个数；如果此步骤顺利，将没有变量溢出，物理寄存器分配结束；否则进行下一步；5)对干涉图进行删减，将优先级别低的变量溢出到堆栈空间寄存器中；6)给优先级最高的虚拟寄存器分配实际物理寄存器；7)针对步骤5)中溢出的变量，为不干涉的溢出变量在堆栈空间寄存器中分配相同的堆栈偏移值；为干涉的溢出变量在堆栈空间寄存器中分配不同的堆栈偏移值；其中，溢出变量的干涉性通过查询步骤3)得到的消除假干涉边后的干涉图进行判断；8)重复步骤4)至步骤7)，直到所有的虚拟寄存器都被分到物理寄存器，且所有的溢出变量都得到合适的堆栈偏移值；所述的消除假干涉边的步骤，具体包含：针对干涉图中干涉的两个变量，进而分析它们的推断寄存器相交关系：如果推断寄存器不相交的两个干涉变量，删除干涉图中两个溢出变量之间的连线，两个溢出变量不干涉；如果推断寄存器相交的两个干涉变量，保留干涉图中两溢出变量之间的连线，两个溢出变量为干涉变量。