基于改进图染色算法的ASIP寄存器分配器

摘要

针对传统的图染色算法很难为不规则结构的专用指令处理器(ASIP)生成优化代码的问题,提出一种能描述ASIP寄存器复杂约束关系的数学模型;改进了传统图染色算法,通过生命周期分析,将各种分配约束限制在一张有向数据相关图中,将寄存器分配问题转化为对有向数据相关图的简化问题;应用改进图染色算法构造了一个ASIP编译器.测试表明:和传统的图染色算法相比,改进图染色算法能充分地考虑寄存器之间的相互约束,降低了目标代码的空间尺寸,减少了寄存器的溢出.