Research on Code Generation Algorithms for Retargetable Compilers for DSPs

在本项目中，我们对用于数字信号处理器的可重定向编译器的代码生成问题进行了研究。我们形式化地描述了一个代码生成问题，开发了解决该问题的算法，并在此基础上开发了一个原型编译器。代码生成任务包括三个阶段：1)指令选择、2)绑定和3)调度。对于1)，我们提出了一种基于规则的数据流图重写方法。对于2)，我们开发了一个启发式算法来最小化额外的数据传输操作的数量，同时最大化操作之间的并行度。对于3)，通过在基于列表的调度之前引入寄存器约束分析阶段，解决了寄存器容量约束的困难。实现了一个原型编译器，用C语言编写了一个G.723.1语音编解码程序，针对不同的数据路径配置、不同的MAC单元网数或不同的总线配置进行了测试。发现我们可以观察到硬件成本和执行周期数之间的权衡。

In this project, we conducted a research on code generation problem for retargetable compilers for DSPs (digital signal processors). We formalized a code generation problem, developed algorithms to solve this problem, and developed a prototype compiler based on the algorithms.The task of code generation consists of three phases : 1) instruction selection, 2) binding, and 3) scheduling. As for 1), we developed a rule based method of rewriting dataflow graphs. As for 2) we developed a heuristic algorithm to minimize the number of the additional data transfer operations and yet to maximize the parallelism among operations. As for 3), we solved the difficulty with respect to the register capacity constraints by introducing a register constraints analysis phase before list-based scheduling. We also proposed an analysis method of minimizing spill codes.We implemented a prototype compiler by which we compiled a G.723.1 speech codec program written in C language, targeting various datapath configuration with differenet numbers of MAC units or different bus configurations. It was found that we can observe the trade-off between the hardware costs and the number of execution cycles.