Code-Optimization
Question 1 |
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 2 |
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 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 sub-expression 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 |
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 5 |
Loop unrolling | |
Dead code elimination | |
Strength reduction | |
Software pipelining |
This technique is similar to loop unrolling concept in code optimization.