Code Optimazation Method Based on Computational Reordering for Programs Written in General Purpose Languages and its Application to DSP Compiler

现在，几乎所有的程序都是在通用计算机语言及其编译器的帮助下开发的。普通编译器通常严格按照源程序中编写的计算顺序生成程序代码。这些编译器可以为普通计算机和微处理器生成高效的代码，但对于最近的数字信号处理器(DSP)等处理器来说，由于这些处理器中存在多个算术运算单元或多级流水线，在相同的编译技术下生成的代码包含许多通过计算代码生成高效代码的开销。因此，本项目的目标是实现一个全新的通用语言编译系统，该系统能够生成高效的代码。用C语言编写的源程序可以用变量间具有优先关系的流程图来表示。在流程图中，在程序中引入了带有条件/非条件分支和循环的分叉和合取节点。通过这些节点，流图被划分为几个原语块。对于每个原始块，在优先关系下，通过调度算法得到具有较少开销代码的顺序。为了减少分支指令导致的代码开销，提出了一种在原语块之间移动代码的方法，并将所提算法应用于基于TM S320C30(TI)和MUPD77230(NEC)的C编译器。通过对几个带条件分支和循环的例子所生成的代码，证明了所提出的方法是有效的。另一方面，为了得到高效的DSP代码，不仅在计算顺序上进行了优化，而且在存储器访问方面也是非常重要的。在本项目中，还研究了DSP内存寻址的优化方法。

Almost all the programs are developed by help of general purpose computer languages and their compilers, now. The ordinary compilers usually generate program codes with strictly following the computational order written in the source programs. These compilers can generate efficient codes for ordinary computers and microprocessors, but, for the recent processors like digital signal processors (DSPs), codes generated under the same compiler techniques include many overhead generate highly efficient codes by computational codes, because of multiple arithmetic operation units or multi-stages pipeline in these processors. Therefore, the goal of this project is to realize a completely new compiler system for general purpose languages, which can generate highly efficient codes.C language is employed for a general purpose language in this project, because it is widely accepted. A given source program written in C can be represented by a flow graph with precedence relation between variables. In the flow graph, fork and conjunction nodes are introduced with conditional/non-conditional branches and loops in a program. By these nodes, the flow graph is partitioned into several primitive blocks. For each primitive block, an order with less overhead codes is derived by a scheduling algorithm under the precedence relation. In order to reduce overhead codes due to branch instructions, a method to moe codes between primitive blocks is proposed.The proposed alogorithms are applied to the C compiler for TMS320C30 (TI) and muPD77230 (NEC). By codes generated by this compiler for several examples with conditional branches and loops, the proposed methods are proved to be effective.On the otherhand, in order to derive a highly efficient DSP codes, not only optimization in computational ordering but also that in memory access is very important. In this project, optimization methods for DSP memory addressing are also investigated.