Integrating Code Optimization and Instruction Scheduling

In the compilers to exploit instruction level parallelism, code optimization applied separately with instruction scheduling will not lead to an ideal result or even generate negative effect. In this paper, the idea of integrating the code optimization and instruction scheduling is put forward in this paper. Based on the idea, we first introduce a framework that is suitable for the integration of code optimization and instruction scheduling. In the framework, instruction scheduling and register allocation are cooperative, which is good for optimizer to know the usage of functional resources and registers, and the computation of ready operations is changed to a data flow problem, which makes the instruction scheduling easy to be integrated with code optimization which is also a data flow problem. Then, to integrate all proper code optimizations into instruction scheduling properly, we analyze all kinds of traditional code optimizations carefully. As a result, we picked out the optimization types, which are suitable to be integrated, by considering the aspects of efficiency, reversibility and opportunity of optimizations. They are copy propagation, common sub expression elimination and DAG transformation. Finally, the detailed methods to integrate the selected optimizations are given. In those methods, we mainly focus on two aspects: the profitability checking and the selection of optimization candidates. In detail, we apply a kind of optimization only when it will not heaven the pressure of functional resources and registers, which avoids the negative effect of optimizations, and we combine the selection of the optimization candidates with the computation of ready operations, which shortens the time cost by compiler. All methods in this paper have been implemented in an instruction level parallel compiler. According to the result of experiments, this method can improve the performance of code optimization obviously. For the result of 24 livermore kernels, most of them can get speedup of 1.5—2.4 over the instruction scheduling without being combined with code optimization.