【作者】 任坤；

【导师】 严晓浪； 孙玲玲；

【作者基本信息】 浙江大学 ， 电路与系统， 2007， 博士

【摘要】 为了提高特定应用环境下的运行速度，DSP增加了许多特殊的指令和功能单元，体系结构越来越不规则。传统的代码生成算法是一种分治算法，没有考虑指令和寄存器之间的约束关系，难以应用在DSP编译器中。必须为DSP编译器发展出新的代码生成算法，以适应新的需求和挑战。本文主要研究了DSP编译器的若干关键技术，DSP编译器的目标机器平台是浙江大学自主研发的媒体DSP——SPOCK。编译器前端包括词法分析器、语法分析器和中间代码生成器等。针对DSP的体系结构特点，重新改造了LCC编译器中记号、符号表、数据类型支持等数据结构，并使LCC前端能够正确的处理计算溢出和数据类型转换等。DSP的体系结构复杂多变，拥有高级语言难以表述的诸多特性，代码生成技术是编译器最难、最复杂的技术之一，它从根本上决定了一个编译器的效率和性能。代码生成技术共分三个子问题：指令选择、寄存器分配以及指令调度，传统的分步优化算法生成的目标代码往往是次优代码。本文研究了包括时间约束、资源约束和DSP体系约束等特性，指出必须发展出同时考虑指令选择、寄存器分配和指令调度的新算法，才有可能为DSP生成优化的目标代码。根据最优化原理，提出调度DAG的概念，给出了同时考虑指令选择和寄存器分配的代码综合生成算法。该代码生成算法在指令生成过程中，充分考虑的指令和寄存器之间的约束，将代码优化生成的问题转化为在调度DAG中寻找一条优化路径的问题。在传统的图染色算法中，仅仅用物理寄存器个数——n表示寄存器堆的模型，这种简单的方式不足以描述DSP寄存器的约束关系。提出了一个能够描述这些约束关系的DSP寄存器模型，该模型将DSP的寄存器分成若干类，并定义了它们之间的相互约束量和优先级别。传统图染色算法只能有效地为通用处理器分配寄存器，改进了图染色算法，将算法的应用范围延伸到DSP领域。提出了有向冲突图的概念，有向边的权值代表寄存器类之间的约束值，寄存器分配的过程就是对有向图进行简化、归约的过程。给出判断有向冲突图节点染色性的精确判据，当冲突图中所有节点都不可染色，算法就选择一个优化的节点溢出到存储器中。中间语言反映源语言的结构，又和目标体系相关，具有目标语言的特性。中间语言对编译器的结构和功能影响很大，其形式是多方面考虑的折中。本文基于XML语言，扩展了IBURG的树文法。这种中间语言的好处就是简单明确，描述能力强，能方便地描述DSP体系结构的特征。为DSP编译器的重定位提供了一个良好的机制，简化了DSP编译器充定位的难度。LCC是一个重定位的通用处理器编译器系统。采用LCC的前端，应用综合代码生成算法和改进图染色寄存器分配算法，重写了编译器后端，构成了一个DSP编译器。试验证明，该DSP编译器能较好的利用DSP特性，提高了代码生成质量，降低了寄存器溢出的概率。更多还原

【Abstract】 This dissertation is involved with key compile techniques and implementation of DSP (digital signal processor). The machine platform is a DSP named SPOCK, which is developed by the VLSI, Zhejiang University. To accelerate some applications, many special instructions and functional units are added to DSP. So ISAs of DSPs are more complicated, structures of DSPs more irregular. The traditional code generation algorithms ignore the relation of code selection and register allocation, which results in sub-optimal code generation. It is essential to develop new code generation algorithms for DSP. In this dissertation, the research fields include code selection, register allocation, code schedule of DSP code generation, and the implementation of DSP compiler, and etc.Compiler, assembler, linker and simulator constitute a whole compiler system. Compiler techniques are focused on in this dissertation. The compiler front-end includes lexical analysis, syntax analysis and semantic analysis. The symbol data structure, symbol table and the support structure to data type are designed newly to adapt to the architecture of DSP. The intermediate language has not only characteristics of high level language but also characteristics of assembly language. It affects the performance and function of compiler strongly, and it is designed as a tradeoff of many capabilities and requirements. In this DSP compiler, an intermediate language owning 36 operators is adopted, which can clearly and briefly describe abstract syntax tree.The architecture of DSP is more irregular than general purpose processor (GPP) and owns many special instructions. The time constraint, resource constraint and architecture constraint are researched in the dissertation, which makes code generation for DSP more difficult. Code selection, register allocation and instruction schedule are sub-phases of code generation, which are coupled with each other. These coupling relations result in traditional methods producing sub-optimality of generated code. To satisfy register restriction of DSP and real-time requirement of applications, a new code-generation algorithm based on dynamic programming is presented, which copes with code selection and register allocation simultaneously. A new concept—schedule directed acyclic graph (DAG) is introduced. The optimal code generation is translated into finding an optimal path in schedule DAG.In traditional graph-coloring algorithms, processor register file is described by the number of registers—N. But this simple model can not accurately describe DSP register file. A new model, which divides DSP register file into several register classes and precedence levels, defines the value of constraint, is presented. Traditional graph-coloring register allocation cannot produce optimal code for irregular structure DSP. The traditional graph-coloring algorithm is improved to be adapted to DSP according to DSP register file model. In the new algorithm, a directed interference graph is built by analyzing variables’ live range and register constraints. The register allocation is translated into how to simplify this graph.The intermediate language, which affects functions of compiler importantly, has the characters of both high level language and the target language. The format of intermediate language of compiler is a tradeoff of many factors. In the dissertation, the grammar of IBURG is extended to describe the irregular architecture of DSP.This grammar based on XML affords a good retargetable mechanism for DSP compiler.LCC is a retargetable compiler. Using the front end of the LCC compiler, applying the methods dealing with code selection and register allocation simultaneously, a new backend is developed. Experimental results show it has better performance of code-generation and less register spilling than traditional code-generation algorithm.更多还原