论文部分内容阅读
在计算机软硬件开发设计过程之中，编译器是软件和硬件之间的重要桥梁。如何提高编译器的性能，编译出更高性能的执行代码，是当前热点研究课题。寄存器分配是编译器后端一个十分重要的阶段。在存储层次中，寄存器访问速度最快但数量有限，生成代码对寄存器的有效使用取决于寄存器分配方法。
本文对经典的基于图染色的寄存器分配算法进行了介绍，并分析其时空复杂性，随后提出了基于生存期扫描的寄存器分配算法，此算法并不是基于图染色方法。在详细阐述了算法设计细节之后，给出正确性证明，并分析其时空复杂性。根据理论分析的结果，其空间复杂度为O(n)，预处理阶段时间复杂度为O(nlogn)，分配过程的时间复杂性为O(n)。
借助UNITY编译器的帮助，对新算法、基于图染色的寄存器分配算法与UNITY编译器中的寄存器分配算法进行了评测。新算法得到了相当的分配结果，由于其时空复杂性上的优势，使其更适用于编译时间和代码质量都被关注的环境，比如just-in-time编译器。