Intermediate,Target Code Generation and Code Optimization
INTERMEDIATE CODE
Intermediate codes are machine independent codes,but they are close to machine instructions.
Syntax trees, postfix notation, 3-address codes , DAG can be used as intermediate langage.
Three-address code:
i) Quadruples ( 4 fields: Operator, Operand1, Operand2, Result)
ii) Triples (3 field: Operator, Operand1, Operand2)
iii) Indirect triples.
Need for Intermediate Code Generation
1. Suppose we have n-source language and m-target language:
i) Without Intermediate Code , we will change each source language into target language directly. So, for each source-target pair we will need a compiler.Hence , we need (n*m) compilers.
ii) With Intermediate Cod, we need n-compilers to convert each source language into intermediate code and m-compiler to convert intermediate code into m-target language.Thus, we need only (n+m) compiler.
2. Re-targeting is facilitated; a compiler for a different machine can be created by attaching a back-end (which generate target code) for the new machine to an existing front-end (which generate intermediate code).
3. A machine independent code-optimizer can be applied to the intermediate code.
4. Intermediate code is simple enough to be easily converted to any target code.
5. Complex enough to represent all the complex structure of high level language.
CODE GENERATION
A code generator has three primary tasks: instruction selection, register allocation and assignment, and instruction ordering.
1. The code generator is given the intermediate text in any one of its form.
2. But in specific algorithms, we deal with quadruples or in some case parse trees as the intermediate forms.
3. Necessary semantic checking is done.
4. The data areas and offsets have been determined for each name that information is available from the symbol table.
CODE OPTIMIZATION
Optimizations applied on target code (assembly code) is machine dependent optimization.
Optimization applied on 3-address code is machine independent optimization.
Basic Block: Sequence of consecutive statements in which context enters at beginning except at the end.
The optimization which is performed within the block is local optimization.
Machine Independent Optimizations
1. Loop Optimizations: Process of optimizing within the loop.
Characteristics of loop optimization:
i) Code motion/Loop invariant elimination/Frequency reduction:
- Reduce the evaluation frequency of expressions.
- Bring loop-invariant statements out of the loop
ii) Loop Unrolling:To execute less number of iterations.
iii) Loop Jamming/Loop Fusion/Loop Combining: Combine the bodies of two loops whenever they are sharing same index variable.
2. Constant Folding: Replacing the value of constant during compilations is called as folding.
3. Constant Propagation: Replacing the value of an expression during compile time is know as constant propagation.
4. Copy Propagation:
Example-
x = y
z = 1 + x ; z = 1 + y
5. Dead Code Elimination: Removes instruction without changing the behaviour (using DAG) .
6. Common Sub expression Elimination/Redundant Code Elimination:
7. Induction Variable and Strength Reduction:
An induction variable is used in loop for the following kind of assignment i = i + constant
strength reduction means replacing costly operator by simple (cheap/low strength) operator.
Example: y = 2*x ==> y = x + x
Directed A cyclic Graph (DAG)
DAG is used to eliminate the common subexpression
Procedure to construct DAG: Whenever we are going to create a node, first verify that whether node is already created or not. If it is already creates then make use of the existing one instead of going for new creation.
Intermediate codes are machine independent codes,but they are close to machine instructions.
Syntax trees, postfix notation, 3-address codes , DAG can be used as intermediate langage.
Three-address code:
i) Quadruples ( 4 fields: Operator, Operand1, Operand2, Result)
ii) Triples (3 field: Operator, Operand1, Operand2)
iii) Indirect triples.
Need for Intermediate Code Generation
1. Suppose we have n-source language and m-target language:
i) Without Intermediate Code , we will change each source language into target language directly. So, for each source-target pair we will need a compiler.Hence , we need (n*m) compilers.
ii) With Intermediate Cod, we need n-compilers to convert each source language into intermediate code and m-compiler to convert intermediate code into m-target language.Thus, we need only (n+m) compiler.
2. Re-targeting is facilitated; a compiler for a different machine can be created by attaching a back-end (which generate target code) for the new machine to an existing front-end (which generate intermediate code).
3. A machine independent code-optimizer can be applied to the intermediate code.
4. Intermediate code is simple enough to be easily converted to any target code.
5. Complex enough to represent all the complex structure of high level language.
CODE GENERATION
A code generator has three primary tasks: instruction selection, register allocation and assignment, and instruction ordering.
1. The code generator is given the intermediate text in any one of its form.
2. But in specific algorithms, we deal with quadruples or in some case parse trees as the intermediate forms.
3. Necessary semantic checking is done.
4. The data areas and offsets have been determined for each name that information is available from the symbol table.
CODE OPTIMIZATION
Optimizations applied on target code (assembly code) is machine dependent optimization.
Optimization applied on 3-address code is machine independent optimization.
Basic Block: Sequence of consecutive statements in which context enters at beginning except at the end.
The optimization which is performed within the block is local optimization.
Machine Independent Optimizations
1. Loop Optimizations: Process of optimizing within the loop.
Characteristics of loop optimization:
i) Code motion/Loop invariant elimination/Frequency reduction:
- Reduce the evaluation frequency of expressions.
- Bring loop-invariant statements out of the loop
ii) Loop Unrolling:To execute less number of iterations.
iii) Loop Jamming/Loop Fusion/Loop Combining: Combine the bodies of two loops whenever they are sharing same index variable.
2. Constant Folding: Replacing the value of constant during compilations is called as folding.
3. Constant Propagation: Replacing the value of an expression during compile time is know as constant propagation.
4. Copy Propagation:
Example-
x = y
z = 1 + x ; z = 1 + y
5. Dead Code Elimination: Removes instruction without changing the behaviour (using DAG) .
6. Common Sub expression Elimination/Redundant Code Elimination:
7. Induction Variable and Strength Reduction:
An induction variable is used in loop for the following kind of assignment i = i + constant
strength reduction means replacing costly operator by simple (cheap/low strength) operator.
Example: y = 2*x ==> y = x + x
Directed A cyclic Graph (DAG)
DAG is used to eliminate the common subexpression
Procedure to construct DAG: Whenever we are going to create a node, first verify that whether node is already created or not. If it is already creates then make use of the existing one instead of going for new creation.
No comments