5. machine independent optimization

Question 1

optimization

Answer 1

—> programme transformation technique which tries to improve intermediate code by making it consume fewer resources (cpu, memory) so that faster running machine code will be resulted

Elimination of unnecessary instruction from object code
(or)
replacement of one sequence of instructions by faster sequence of instructions that does the same thing is called code optimization or code improvement
- compiler optimization process should meet the following objectives:
1. Optimization should not change the meaning of the programme
2. It should increase speed and performance of the program
3. Compilation time must be kept reasonable
4. It should not delay the overall compiling process
– Optimization also helps in:
1. Reduction in space and time(inc speed of compilation)
2. It analyses data sets with the help of softwares like tableau As manual data analysis involves lot of time and studious job
3. Often optimised code promotes reusability
– Types of Optimization:
1. Machine dependent optimization
2. machine independent optimization

Question 2

Where to apply optimization

Answer 2

1. Source prog
making changes to the algorithm or changing the loop structures.
2. intermediate code
Involves changing the address calculations and transforming the procedure calls
3. Target code
Done by the compiler
Usage of registers and select and move instructions are part of the optimization involved
4. Local Optimization
Transformations are applied on small basic blocks of code
Techniques are local value numbering and tree height balancing
5. Regional optimization
apply to extended basic blocks
superlocal value numbering and loop unrolling are the techniques
6. Global optimization
Apply to large programme segments that include functions procedures and loops
- Transformations are live variable analysis and global code replacement
7. Interprocedural optimization
Optimizations are applied to interprocedurally
- techniques are inline substitution and procedure placement

Question 3

Advantages and disadvantages of code optimization

Answer 3

adv
1. Improved performance
2. Reduction in Code size
3. increased portability
4. Reduced power consumption
5. improved maintainability

disadv
1. Increased compilation time
2. Increased complexity
3. Potential for introducing bugs
4. difficulty in accessing the effectivenessM’

Question 4

mach independent code optimization

Answer 4

1. Make the intermediate code more efficient by transforming a section of code that doesn’t involve in h/w components like cpu registers or any absolute memory location
2. it Eliminates redundancies(No longer useful code)
3. reduces the LOC
4. eliminates useless code
5. reduces the frequency of repeated code
6. Thus it can be used on any processor irrespective of machine specifications

achieved by two methods:
1. Function preserving
2. Loop Optimization

Question 5

Function preservation

Answer 5

Function preserving optimization:
– It attempts to reduce the computational time of code in a given function
1. common sub expression elimination
2. constant folding
3. Dead code elimination
4. copy propagation
5. Function cloning
6. function inlining

1) Common sub expression elimination
A common sub expression is the one which Is often repeated in the programme but the value doesnt change even after previous computation
- The compiler evaluates its value even if it doesnt change such evaluations result in wastage of resources and time so it is better to eliminate
eg:
t1=xz;
t2=a+b;
t3=p%t2;
t4=xz; (t4 and t1 is same expression)

// after Optimization
t1=x*z;
t2=a+b;
t3=p%t2;

2) Constant folding:
It is a technique where expression which is computed at the compile time is replaced by its value
– Generally such expressions are again evaluated at runtime but if we replace them with their values they need not to be Evaluated at the runtime helps in saving the time
-Folding can be applied on boolean, int, float
- Constant holding is often interleaved with constant propagation(def below)
eg:
//Code segment
int x= 5+7+c;

//Folding applied
int x=12+c;

Constant propagation
if any variable is assigned a constant value and used in further computations it is called as constant propagation
- Constant propagation suggests using constant value for further computation
eg:
// Code segment
int a = 5;
int c = b * 2;
int z = a;
//Applying constant propagation once
int c = 5 * 2;
int z = a;
//Applying constant propagation second time
int c = 10;
int z = a;
//Applying constant propagation last time
int z = a[10];

3) Dead Code Elimination
- Dead code is a block of code that is never executed or never reached in the programme
- It is a code that can be efficiently removed from the programme without affecting any other part of the programme
- In case if values obtain are never used in the future it is also regarded as Deadcode
eg:
//Code
int x= a+23;
//the variable x is never used in the program. Thus it is a dead code.
z=a+y;
printf(“%d,%d”.z,y);
//After Optimization
z=a+y;
printf(“%d,%d”.z,y);

4) copy propagation
It removes assignments and copy statements such as x=y
eg:
//Code segment
a=b;
z=a+x;
x=z-b;
//After Optimization
z=b+x;
x=z-b;
5) function inling
Here function call is replaced by the body of the function itself
-this saves lot of time in copying all the parameters storing the written addresses etc

6) function cloning
Here, specialized codes for a function are created for different calling parameters.
eg: Function Overloading

Question 6

loop optimization

Answer 6

1. programme spends most of the time inside the loop
2. thus loop determine the time complexity of the programme so in order to get optimal and efficient code loop Optimization is required
3. In order to apply code optimization we need to first detect the loop using control flow analysis graphs With the help of programme flow graph
4. A cycle in a programme flow graph will indicate presence of loop
5. Once the loops are detected following loop optimization techniques can be applied:
   a. Frequency reduction
   b. Algebraic expression simplification
   c. Strength reduction
   d. Redudency elimination

a. Frequency reduction:
applies to the concept that Loop runs least possible lines of code.
This can be achieved by:
1) Code motion
2) Loop unrolling
3) loop jamming

Code motion
statements that remain unchanged for every iteration are included in the loop
– such statements are called loop invariants and only result the programme spending more Time inside the loop
– so code motion simply removes loop invariance from inside the code and places it’s outside the code
eg:
//Before code motion
p=100
for(i=0;i<p;i++)
{
a=b+40; //loop invariant code
if(p/a==0)
printf(“%d”,p);
}
// After code motion
p=100
a=b+40;
for(i=0;i<p;i++)
{
if(p/a==0)
printf(“%d”,p);
}
Loop unrolling
—Basically Decreasing iterations
If a loop runs doing the same operation for every iteration, we can perform that same operation inside the loop more than once.This is called as loop
-Such unrolled loop will perform the evaluation more than once in a single loop iteration.
Loop jamming
Combining the loop that carry out the same operations is called as loop jamming

algebraic expression simplication:
A programmatic contains some unuseful or trivial algebraic expressions do not result in any useful computation or change of values
-search lines of code can be eliminated so the compiler doesnt waste time evaluating it
eg:
A=A+0;
x=x*1; *

Strength reduction
It suggests replacing a costly operation like multiplication with a cheaper one
eg:
a x 4
after reduction
a&laquo_space;2

redudency elimination
It may happen that a specific expression is repeated in a code many times
-Redundancy elimination avoids evaluating the same expressions multiple times resulting in faster execution.
eg:
//Code:
int x=a+b;
int z=a+b+40;
return (a+b)5;
//After optimization
int x=a+b;
int z=x+40;
return x5

Question 7

principles sources of optimization

Answer 7

all the optimization techhniques

Question 8

Control flow graphs(cfg)
(SE concept)

Answer 8

-Graphical representation of control flow or computation during the execution of programmes or applications
-These are originally developed by Francis E. Allen

characteristics of cfg:
1. Process oriented
2. Shows all paths that can be traversed during programme execution
3. Directed graph
4. Edges portrait control flow paths and notes portray basic blocks of code

There are two designated blocks in control flow graphs:
1. Entry block
2. Exit block

Question 9

Data flow analysis

Answer 9

1. Analysis of flow of data in control flow graph
2. It determines the information regarding the definition and use of the data in the programme
3. Did the help of this analysis optimization can be done
4. It involves tracking the values of variables and expressions as they are computed and used throughout the programme
5. the main goal is to identifying opportunities for optimising and identifying potential errors

Thomas a common types of data flow analysis performed by compilers are:
1) Reaching definitions analysis
This analysis tracks the definitions of variables and expressions determines the points in the programme where the definition reaches a particular use of a variable or expression
-this information can be used to identify variables that can be safely optimised or eliminated
2) Live variable analysis
This analysis determines the points in the programme where variable or expression is live that means its value is still needed for some future computation
3) Available expressions analysis
This analysis determines the points in the programme with a particular expression is available meaning that the value has already been computed and can be reused
-This information is used to identify opportunities for common sub expression elimination in other optimization techniques
4) Constant propagation analysis:
This analysis tracks the values of constants and determines the points of the programme where the particular constant value is used
- This analysis is used to identify opportunities for constant folding and other optimization techniques
https://www.geeksforgeeks.org/data-flow-analysis-compiler/

Question 10

Advantages of Data flow analysis

Answer 10

1. Improved Code quality
2. better error detection
3. increased understanding of the programme behaviour

Question 11

Data Flow features –

Answer 11

1. Identifying Dependencies
2. Detecting dead code
3. optimizing code
4. Detecting errors
5. handling complex control flow
6. Procedural analysis
7. scalability

Question 12

foundations of data flow analysis

Answer 12

1. Control flow graph
2. Data flow equations
   Data flow analysis is often formulated using data flow equations. These equations describe how information (such as reaching definitions or available expressions) propagates through the CFG. They are typically represented using sets and lattice operations (e.g., union, intersection).
3. Fixed-Point Iteration:
   Solving data flow equations involves computing a fixed point, which is the point at which the solution no longer changes. Fixed-point iteration algorithms, such as the iterative algorithm or the worklist algorithm, are used to compute the fixed point efficiently.
4. Data Flow Framework:
   A data flow framework consists of a lattice, a set of transfer functions (one for each program point), and a direction (forward or backward). The lattice defines the set of possible states for the analysis, and the transfer functions describe how information flows between these states.
5. reaching definition