Research On Key Techniques For DSP Compiler

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.