Research On Some Key Compiler Techniques For Embedded Processors

To meet various requirements like performance, power, and real-time response to external events, embedded systems need highly efficient machine code. Thereby assembly language is always widely used in embedded programming. However, time-consuming programming, vexing debugging, and poor code portability of assembly programming are not neglectable. With the extension of application area of embedded systems and the ever-growing of the size of embedded software, assembly language will be inevitably replaced by high level language in embedded software development. But compared to manually written assembly code, the code generated by high level language compilers is often much worse and cannot meet the requirements. So it is very important to study the compiler techniques for embedded systems.Traditional compiler techniques are usually not applicable to the embedded domain directly, which need to be extended. Moreover, some completely distinct algorithms are expected sometimes. The reason is that traditional compiler techniques are usually based on regular machine models, and apply simple heuristics to get results rapidly; however, embedded processors often have irregular architectural characteristics. Additionally, in the embedded domain, the importance of high quality code outweighs that of short compilation time.This thesis mainly focuses on three problems of compiler techniques for embedded systems: register allocation for embedded processors, code generation for multimedia instruction set extension, and code selection for dual instruction set processors.Traditional graph-coloring register allocation algorithms are based on over-simplified register files of machine models, which apply the rule of "degree < k" to test the local colorability of interference graphs and extend this rule by ad hoc skills to irregular register file characteristics. Significant progress has been made on this problem through years of efforts of compiler researchers. But when testing the local colorability of interference graphs, traditional graph-coloring register allocation algorithms cannot get the colors of its neighbor nodes, consequently, they make conservative estimations of them.Since traditional tree pattern matching and dynamic programming cannot exploit efficiently instruction-level parallelism, the extension based on traditional parallel compiler techniques mainly is limited in loop-level parallelism, which cannot exploit scalar instructions and SIMD vector instructions optimally.Traditional compiler techniques usually improve code quality for a single objective, such as performance or power. However, embedded systems usually need to be optimized for multiple objectives. It is necessary to research how a compiler transformation for one objective influences the other objectives and how to make trade-offs among different objectives.The complexity of embedded systems makes it necessary to apply new methods to research compiler techniques for them. The core idea of this thesis is improving compiler techniques with the help of meta-heuristics and the integration of compiler front-end and back-end.In the last twenty years, there has been extensive research on meta-heuristic algorithms. Meta-heuristics, inspired by nature, can overcome the limitations of classic optimization algorithms and can search the solution space systematically to solve many optimization problems by simulating natural phenomena such as physical processes and evolutions. There are a variety of optimization problems in the compiler domain, which are more complex in the embedded domain. They bring difficulties to the application of standard compiler techniques. Meta-heuristics open up a broad way to solve complex compiler optimization problems.Program analysis is the foundation of compiler optimizations. To meet the requirements of compiler techniques for embedded systems, the advantages of compiler front-end program analysis and the machine-specific information of compiler back-end can be combined.The main contributions of the thesis are as follows.1. For irregular architectural characteristics of embedded processors, a new graph-coloring register allocation algorithm HMA-GRA is proposed, which is based on a hybrid evolutionary method. The algorithm provides a new direction for implementing register allocators while breaking through the difficulties in computing local colorability of interference graphs, which cannot be solved by traditional graph coloring register allocation algorithms based on simple heuristics.HMA-GRA algorithm combines a genetic algorithm with a tabu search subroutine. It uses Chaitin algorithm to pre-process the interference graph, assigns colors to nodes of the remaining interference graph randomly according to their classes, computes the number of conflicts, and decreases this number gradually until the graph can be colored successfully. This method can not only compute the local colorability of interference graphs accurately, but also replace the ad hoc skills of traditional methods by a regular register allocation model. It can thus deal with complex irregular characteristics of embedded processor register files.2. For multimedia instruction set, a new algorithm ICG-ME for the generation of SIMD code is proposed. ICG-ME algorithm extends standard tree pattern matching and dynamic programming techniques, modifies the iburg code generator generator in such a way that its generated code generators allow to retain multiple matching rules for each target nonterminal of a node of data flow trees in order to identify parallel operations of SIMD instructions. The data flow analysis that is to identify whether memory references are aligned relative to vector registers is performed in the compiler front-end. Then the analysis results are transfered to the compiler back-end to assist in constructing SIMD and permutation instructions. Finally, assembly code of multimedia vector instructions and non-multimedia scalar instructions is generated. Through the integration of compiler front-end analysis and the machine-specific information of compiler back-end, ICG-ME algorithm can not only simplify the generation of SIMD code, but also use both SIMD and non-SIMD instructions to improve code quality.3. In order to meet multi-objective requirements of embedded systems, a new methodology is proposed to deal with multi-objective optimization problems in the compiler domain using meta-heuristics. And the problem of code selection for ARM/Thumb processors with dual instruction sets is used to exemplify this idea.This thesis formulates the problem of code selection for processors with dual instruction sets as a multi-objective optimization problem that needs trade-off between the code size and the code execution time, creates a mathematical model for it using program profiling technique, and solves it with a basic multi-objective ant colony optimization algorithm MOARM-ANT-SS together with subset selection method.4. Based on the SUIF/MachineSUIF compiler research framework, we have extended the experimental environment for code selection, register allocation, and program analysis.Several traditional graph-coloring register allocation algorithms and a meta-heuristic graph-coloring register allocation algorithm HMA-GRA have been implemented. A code generation algorithm ICG-ME for multimedia processors and several compiler passes for program analysis have been implemented as well. Furthermore, an ACO algorithm MOARM-ANT-SS for multi-objective code generation is implemented.It is necessary to extend traditional compiler techniques or to design new ones in the embedded domain. This thesis analyzes some key problems of traditional compiler techniques in the embedded domain. Based on meta-heuristics and the integration of the compiler front-end and back-end, it mainly focuses on three problems of embedded systems: register allocation for embedded processors, code generation for multimedia instruction set extension, and code selection for dual instruction set processors. Experimental results prove the efficiency of our methods. The research and implementation in this thesis on applying meta-heuristics to compiler techniques for embedded systems are still elementary. From a new direction, meta-heuristics open up a broad way to research compiler techniques in the embedded domain.