A Framework of Modulo Scheduling Based on Finite State Automation

该项目将研究整数编程在寄存器分配中的使用，以及与寄存器分配交互的重要编译器优化。该项目将建立在前面工作的基础上，该工作表明，整数规划可以在合理的时间内产生最佳或接近最佳的寄存器分配，大大减少了寄存器分配的开销。该项目的第一个目标是通过发现和实现更有效的整数编程公式，在基于整数编程的寄存器分配中实现数量级的加速。该项目的第二个目标是扩展整数编程公式的范围，以包括其他直接与寄存器分配交互的编译器优化，例如公共子表达式消除和循环不变代码移动。扩展的公式将允许寄存器分配和这些交互优化同时完成，消除了传统的相位排序问题。预计扩展整数规划公式将提供显著的代码质量改进，并且新的优化可以在合理的时间内完成。

This project will study the use of integer programming for register allocation and for important compiler optimizations that interact with register allocation. The project will build on the preceding work which shows that integer programming can produce optimal or near-optimal register allocations in reasonable time, providing significant reductions in register allocation overhead. The project's first objective is to achieve order of magnitude speedup in integer-programming-based register allocation by discovering and implementing more efficient integer-programming formulations. The project's second objective is to extend the scope of the integer programming formulation to include other compiler optimizations that directly interact with register allocation, such as common subexpression elimination and loop-invariant code motion. The extended formulation will allow register allocation and these interacting optimizations to be done simultaneously, eliminating the traditional phase ordering problem. It is expected that the extended integer programming formulation will provide significant code quality improvements, and that the new optimization can be done in reasonable time.