## Code-Optimization

 Question 1

Which one of the following is FALSE?

 A A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end. B Available expression analysis can be used for common subexpression elimination. C Live variable analysis can be used for dead code elimination. D x=4*5 ⇒ x=20 is an example of common subexpression elimination.
Compiler-Design       Code-Optimization       GATE 2014 [Set-1]
Question 1 Explanation:
x=4* 5 ⇒ x=20 is an example of common subexpression elimination is a false statement.
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
 A S1 is false and S2 is false B S1 is false and S2 is true C S1 is true and S2 is false D S1 is true and S2 is true
Compiler-Design       Code-Optimization       GATE 2006
Question 2 Explanation:
We cannot compare the program on the basis of runtime with respect to any inputs.
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?

 A The code contains loop invariant computation B There is scope of common sub-expression elimination in this code C There is scope of strength reduction in this code D There is scope of dead code elimination in this code
Compiler-Design       Code-Optimization       GATE 2006
Question 3 Explanation:
→ 4*j is a common sub-expression. So there is a scope of elimination. So B is correct.
→ 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
Consider the following ANSI C code segment:
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:
 A 303 and 2 B 303 and 102 C 403 and 102 D 203 and 2
Compiler-Design       Code-Optimization       GATE 2021 CS-Set-2       Video-Explanation
Question 4 Explanation:

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)

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;

So 303 and 2 are the answer.

 Question 5
Which of the following comment about peephole optimization is true?
 A It is applied to a small part of the code and applied repeatedly B It can be used to optimize intermediate code C It can be applied to a portion of the code that is not contiguous D It is applied in the symbol table to optimize the memory requirements.
Compiler-Design       Code-Optimization       ISRO-2018       Video-Explanation
Question 5 Explanation:
→ Peephole optimization is a kind of optimization performed over a very small set of instructions in a segment of generated code. The set is called a "peephole" or a "window". It works by recognizing sets of instructions that can be replaced by shorter or faster sets of instructions.

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.