CodeOptimization
Question 1 
Which one of the following is FALSE?
A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end.  
Available expression analysis can be used for common subexpression elimination.  
Live variable analysis can be used for dead code elimination.  
x=4*5 ⇒ x=20 is an example of common subexpression elimination. 
Common subexpression elimination (CSE) is a compiler optimization that searches for instances of identical expressions (i.e., they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value.
For ex: Consider the following code:
m=y+z * p
n= y+z *k
The common subexpression is “y+z” we can be calculate it one time and replace in both expression
temp = y+z
m = temp*p
n = temp*k
Question 2 
Consider these two functions and two statements S1 and S2 about them
int work1(int *a, int i, int j) int work2(int *a, int i, int j) { { int x = a[i+2]; int t1 = i+2; a[j] = x+1; int t2 = a[t1]; return a[i+2] – 3; a[j] = t2+1; } return t2 – 3; }
 S1: The transformation form work1 to work2 is valid, i.e., for any program state and input arguments, work2 will compute the same output and have the same effect on program state as work1
S2: All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1
S1 is false and S2 is false
 
S1 is false and S2 is true  
S1 is true and S2 is false  
S1 is true and S2 is true 
So, given statement is wrong.
S1: Let us assume an array = {1,2,3,4,5} and i=0.
Let j = i+2 = 0+2 = 2
For the respective example work1 and work2 results 1 and 0, so S1 statement is False.
Question 3 
Consider the following C code segment.
for (i = 0, i < n; i++) { for (j = 0; j < n; j++) { if (i%2) { x += (4*j + 5*i); y += (7 + 4*j); } } }
Which one of the following is false?
The code contains loop invariant computation  
There is scope of common subexpression elimination in this code  
There is scope of strength reduction in this code  
There is scope of dead code elimination in this code

→ 5*i can be moved out of inner loop. So can be i%2, here loop invariant computation can be done, so option A is correct.
→ 4*i, 5*j can also be replaced so there is a scope of strength reduction. So C is true.
→ But there is no dead code to eliminate, we can replace the variable representation only.
Question 4 
z = x + 3 + y > f1 + y > f2;
for (i = 0; i < 200; i = i+2) {
if (z > i) {
p = p + x + 3;
q = q + y > f1;
} else {
p = p + y > f2;
q = q + x + 3;
}
}
Assume that the variable y points to a struct (allocated on the head) containing two fields f1 and f2, and the local variables x, y, z, p, q, and i are allotted registers. Common subexpression elimination (CSE) optimization is applied on the code. The number of addition and dereference operations (of the form y>f1 or y>f2) in the optimized code, respectively, are:
303 and 2  
303 and 102  
403 and 102  
203 and 2 
In compiler theory, common subexpression elimination is a compiler optimization that searches for instances for identical expressions (i.e, they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value.
For example: Consider the following block of code
a=x+y+z;
r=p+q;
b=x+y+r;
The code after common subexpression elimination.
t=x+y;
a=t+z;
r=p+q;
b=t+r;
In the given code
z = x + 3 + y > f1 + y > f2;
for (i = 0; i < 200; i = i+2) {
if (z > i) {
p = p + x + 3;
q = q + y > f1;
} else {
p = p + y > f2;
q = q + x + 3;
}
}
X+3 is common subexpression, also y > f1 & y > f2 is found in first line itself so they are also like common subexpression.
Hence the code after common subexpression
t1=x+3; t2=y > f1 ; t3= y > f2;
z = t1 + t2 + t3;
for (i = 0; i < 200; i = i+2) {
if (z > i) {
p = p + t1;
q = q + t2;
} else {
p = p + t3;
q = q + t1;
}
}
Hence two dereference operations (of the form y>f1 or y>f2) in the optimized code.
The number of addition in the optimized code are:
Loop will execute for 100 times and in loop one addition (i+2)
So 100 additions.
Inside loop we have two additions (either in if block or in else block) so 200 additions inside loop
Hence 300 additions in loop (loop body as well as inside)
First 2 lines contains 3 additions
t1=x+3;
z = t1 + t2 + t3;
Hence total 303 additions.
So 303 and 2 are the answer.
Question 5 
It is applied to a small part of the code and applied repeatedly  
It can be used to optimize intermediate code  
It can be applied to a portion of the code that is not contiguous  
It is applied in the symbol table to optimize the memory requirements. 
Replacement Rules:
1. Null sequences – Delete useless operations.
2. Combine operations – Replace several operations with one equivalent.
3. Algebraic laws – Use algebraic laws to simplify or reorder instructions.
4. Special case instructions – Use instructions designed for special operand cases.
5. Address mode operations – Use address modes to simplify code.