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

现在，几乎所有的程序都是借助于通用计算机语言及其编译器来开发的。一般的编译程序通常严格按照源程序的计算顺序生成程序代码。这些编译器可以为普通计算机和微处理器生成高效的代码，但是，对于最近的处理器，如数字信号处理器（DSP），由于这些处理器中的多个算术运算单元或多级流水线，在相同的编译技术下生成的代码包括许多开销，通过计算代码生成高效代码。因此，本项目的目标是实现一个全新的通用语言编译系统，它可以生成高效的代码。C语言被广泛接受，因此在本项目中被用作通用语言。用C语言编写的源程序可以用变量间具有优先关系的流图表示。在流图中，分叉和合取节点被引入程序中的条件/非条件分支和循环。通过这些节点，流图被划分成若干个基元块。对于每个基元块，通过优先关系下的调度算法得到开销代码较少的顺序。为了减少由分支指令引起的代码开销，提出了一种基元块间莫伊代码迁移的方法，并在TI公司的TMS 320 C30和NEC公司的muPD 77230的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.