1. Field of the Invention
This invention relates to the field of software compilation and, and more particularly relates to post optimization of compiled code.
2. Description of the Related Art
Today's compilers include various schemes for code optimization. Generally, compilers produce relocatable object modules that can be linked together and loaded for execution by a link loader. The compilers can generate efficient instruction sets using target dependent or target independent machine codes. However, the code generated by a compiler may not be optimized for particular applications. Once an instruction set is generated by a compiler, the instruction set can further be optimized using various post-optimization techniques. Post-optimization of code involves re-visiting the generated code and finding an efficient way to execute the generated code. Some of the common techniques for post optimization include instruction scheduling and register allocation.
Instruction scheduling allows a compiler to identify code operations that are independent and can be executed out of sequence. For example, a routine for printing the status of idle peripheral devices can be executed ahead of a routine that is computing a complex mathematical algorithm as long as there are no data, resource or other related dependencies between the two routines.
In register allocation scheme, a compiler identifies and allocates available machine registers to store intermediate and final results of a computation. The number of actual hardware registers in a given machine is limited by the target machine architecture. A compiler's design may allow use of software virtual registers that are allocated memory locations, to be used for register operations. Initially, during code generation process, the compiler may assume an infinite number of available virtual registers and allocate virtual registers to various computations. However, each virtual register is eventually mapped to actual hardware registers for final code generation. Allowing a compiler to use unlimited number of virtual registers for code generation can produce an optimized instruction scheduling for a given code generation. Because each virtual register requires mapping with limited number of actual machine register, instruction scheduling can be limited.
The optimization of code generation can be improved by integrating instruction scheduling and register allocation. In integrated optimization, a balance between instruction scheduling and register allocation is achieved by accepting some inefficiency in instruction scheduling and some spillover register allocation of virtual registers. The current integrated optimization techniques include inefficient instruction scheduling and register allocation.