The front end of a compiler is generally responsible for creating an intermediate representation of the source program whereas the back end of the compiler constructs the desired target program from the intermediate representation and the information in the symbol table. Before the intermediate code is passed to the back end of the compiler, it is necessary to improve the intermediate code so that better target code will result. The code optimization phase in a compiler attempts to improve the target code without changing its output or without side-effects.
Today, most of the compiler research is done in the optimization phase. There are many classical techniques (e.g.
Eliminating common sub-expressions, Dead-Code elimination, Constant Folding etc.) that have been used in code optimization. However, the increasing size and complexity of software products and the use of these products in embedded, web-based and mobile systems results in the demand for more optimized versions of the source code. This research paper discusses the challenges involved in code optimization for such systems and some recently developed techniques in code optimization.
Code Optimization is the process of transforming a piece of source code to produce more efficient target code. Efficiency is measured both in terms of time and space. Optimization is generally implemented using a set of optimizing transformations, i.e., algorithms which take a piece of source code and transform it to produce a semantically equivalent output code that uses fewer resources. Most of the optimization techniques attempt to improve the target code by eliminating unnecessary instructions in the object code, or by replacing one sequence of instructions by another faster sequence of instructions.
Optimization is one of the most important phases in a Compiler. Code optimization attempts to improve the source code so that better target code will result. Usually, a better target code is one that is better in terms of time and space. However, some other objectives may also be considered to measure the goodness of code, such as target code that consumes less power. In modern times, processor architectures are becoming more complex. With the introduction of multicore and embedded systems requiring a faster target code that consumes less space and power toexecute. The code optimization phase in a compiler attempts to resolve these issues and produces better target code without changing the desired output.
1.3 Presence of the Optimization phase in the Compiler Architecture
Code optimization may either be performed on the intermediate representation of the source code or on the un-optimized version of the target machine code. If applied on the intermediate representation, the code optimization phase will reduce the size of the Abstract Syntax Tree or the Three Address Code instructions. Otherwise, if it is applied as part of final code generation, the code optimization phase attempts to choose which instructions to emit, how to allocate registers and when to spill, and so on.
2. OPTIMIZATION TECHNIQUES
There are many classical optimization techniques that have been used in code optimization since the last decade. Some of these techniques are applied to the basic blocks in the source code and others are applied to the whole function. As the result of recent researches, many new optimization techniques have been introduced. In this research paper, the emphasize will be on the new techniques of code optimization; however, a brief overview of the classical techniques have also been introduced.
2.1 Classical Optimization Techniques
The classical techniques for code optimization can be categorized as:
1. Local Optimization
2. Global Optimization
3. Inter-Procedural Optimization
2.1.1 Local Optimization
The code optimization phase in a compiler begins with partitioning the sequences of three-address instructions into basic blocks. These basic blocks become the nodes of a flow graph. Local optimization is performed within each basic block. We can often obtain a substantial improvement in the running time of code by performing local optimization within each basic block by itself. Since basic blocks have no control flow, these optimizations need little analysis.
Local optimization can be performed using the following techniques-
(I) Eliminating local common subexpressions,
(ii) Dead code Elimination
(iii) The use of algebraic identities-
(a) The use of arithmetic identities
(b) Local reduction in strength, that is, replacing a more expensive operator by a cheaper one.
(c) Constant Folding
(iv) Reordering statements that do not depend on one another.
2.1.2 Global Optimization (Intra-Procedural Methods)
Global optimization techniques act on whole functions. In global optimization, improvement takes into account what happens across basic blocks.
Most global optimization techniques are based on data-flow analysis. The results of data-flow analysis all have the same form: for each instruction in the program, they specify some property that must hold every time that instruction is executed.