Code Generation and Optimization

Question 1
Some code optimizations are carried out on the intermediate code because
Tick
they enhance the portability of the compiler to other target processors
Cross
program analysis is more accurate on intermediate code than on machine code
Cross
the information from dataflow analysis cannot otherwise be used for optimization
Cross
the information from the front end cannot otherwise be used for optimization


Question 1-Explanation: 
Option (B) is also true. But the main purpose of doing some code-optimization on intermediate code generation is to enhance the portability of the compiler to target processors. So Option A) is more suitable here. Intermediate code is machine/architecture independent code. So a compiler can optimize it without worrying about the architecture on which the code is going to execute (it may be the same or the other ). So that kind of compiler can be used by multiple different architectures. In contrast to that, suppose code optimization is done on target code, which is machine/architecture dependent, then the compiler has be specific about the optimizations on that kind of code. In this case the compiler can\'t be used by multiple different architectures, because the target code produced on different architectures would be different. Hence portability reduces here.
Question 2
In a simplified computer the instructions are: GATECS2007Q54 The computer has only two registers, and OP is either ADD or SUB. Consider the following basic block: GATECS2007Q541 Assume that all operands are initially in memory. The final value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block?
Cross
2
Tick
3
Cross
5
Cross
6


Question 2-Explanation: 
For Instructions of t2 and t3 1. MOV c, t2 2. OP d, t2(OP=ADD) 3. OP e, t2(OP=SUB) For Instructions of t1 and t4 4. MOV a, t1 5. OP b, t1(OP=ADD) 6. OP t1, t2(OP=SUB) 7. MOV t2, a(AS END Value has To be in the MEMORY) Step 6 should have been enough, if the question hadn\'t asked for final value in memory and rather be in register. The final step require another MOV, thus a total of 3.
Question 3
Which one of the following is FALSE?
Cross
A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end.
Cross
Available expression analysis can be used for common subexpression elimination.
Cross
Live variable analysis can be used for dead code elimination.
Tick
x = 4 ∗ 5 => x = 20 is an example of common subexpression elimination.


Question 3-Explanation: 
(A) A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end is TRUE. (B) Available expression analysis can be used for common subexpression elimination is TRUE. Available expressions is an analysis algorithm that determines for each point in the program the set of expressions that need not be recomputed. Available expression analysis is used to do global common subexpression elimination (CSE). If an expression is available at a point, there is no need to re-evaluate it. (C)Live variable analysis can be used for dead code elimination is TRUE. (D) x = 4 ∗ 5 => x = 20 is an example of common subexpression elimination is FALSE. Common subexpression elimination (CSE) refers to compiler optimization replaces identical expressions (i.e., they all evaluate to the same value) with a single variable holding the computed value when it is worthwhile to do so. Below is an example
In the following code:

a = b * c + g;
d = b * c * e;

it may be worth transforming the code to:

tmp = b * c;
a = tmp + g;
d = tmp * e;
Sources: https://en.wikipedia.org/wiki/Common_subexpression_elimination https://en.wikipedia.org/wiki/Available_expression
Question 4
One of the purposes of using intermediate code in compilers is to
Cross
make parsing and semantic analysis simpler.
Cross
improve error recovery and error reporting.
Tick
increase the chances of reusing the machine-independent code optimizer in other compilers.
Cross
improve the register allocation.


Question 4-Explanation: 
After semantic Analysis, the code is converted into intermediate code which is platform(OS + hardware) independent, the advantage of converting into intermediate code is to improve the performance of code generation and to increase the chances of reusing the machine-independent code optimizer in other compilers. So, option (C) is correct.
Question 5

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?

Cross

The code contains loop invariant computation

Cross

There is scope of common sub-expression elimination in this code

Cross

There is scope of strength reduction in this code

Tick

There is scope of dead code elimination in this code



Question 5-Explanation: 

Question asks about false statement

4*j is common subexpression elimination so B is true.

5*i can be moved out of inner loop so can be i%2. 
Means, A is true as we have loop invariant computation.

Next, 4*j as well as 5*i can be replaced with a = - 4;
before j loop then a = a + 4; where 4*j is computed,
likewise for 5*i. C is true as there is scope of strength 
reduction. 

By choice elimination, we have D.
Question 6

Consider the grammar rule E → E1 - E2 for arith­metic expressions. The code generated is targeted to a CPU having a single user register. The sub­traction operation requires the first operand to be in the register. If E1 and E2 do not have any com­mon sub expression, in order to get the shortest possible code

Cross

E1 should be evaluated first

Tick

E2 should be evaluated first

Cross

Evaluation of E1 and E2 should necessarily be interleaved

Cross

Order of evaluation of E1 and E2 is of no consequence



Question 6-Explanation: 

  E -> E1 - E2 Given that E1 and E2 don\'t share any sub expression, most optimized usage of single user register for evaluation of this production rule would come only when E2 is evaluated before E1. This is because when we will have E1  evaluated in the register, E2 would have been already computed and stored at some memory location. Hence we could just use subtraction operation to take the user register as first operand, i.e. E1 and E2 value from its   memory location referenced using some index register or some other form according to the instruction. Hence correct answer should be (B) E2 should be evaluated first. 

Question 7
Consider the intermediate code given below:
1. i = 1
2. j = 1
3. t1 = 5 * i
4. t2 = t1 + j
5. t3 = 4 * t2
6. t4 = t3
7. a[t4] = –1
8. j = j + 1
9. if j <= 5 goto(3)
10. i = i + 1
11. if i < 5 goto(2) 
The number of nodes and edges in the control-flow-graph constructed for the above code, respectively, are
Cross
5 and 7
Tick
6 and 7
Cross
5 and 5
Cross
7 and 8


Question 7-Explanation: 
Below is control flow graph of above code. \"cfg\"
Question 8
Consider the following code segment.
x = u - t;
y = x * v;
x = y + w;
y = t - z;
y = x * y; 
The minimum number of total variables required to convert the above code segment to static single assignment form is   Note : This question was asked as Numerical Answer Type.
Cross
6
Cross
8
Cross
9
Tick
10


Question 8-Explanation: 
Static Single Assignment is used for intermediate code in compiler design. In Static Single Assignment form(SSA) each assignment to a variable should be specified with distinct names. We use subscripts to distinguish each definition of variables. In the given code segment, there are two assignments of the variable x
x = u - t;
x = y + w;
and three assignments of the variable y.
y = x * v;
y = t - z;
y = x * y 
So we use two variables x1, x2 for specifying distinct assignments of x and y1, y2 and y3 each assignment of y. So, total number of variables is 10 (x1, x2, y1, y2, y3, t, u, v, w, z). Static Single Assignment form(SSA) of the given code segment is:
x1 = u - t;
y1 = x1 * v;
x2 = y1 + w;
y2 = t - z;
y3 = x2 * y2;
Please refer below link for details https://www.cs.cmu.edu/~fp/courses/15411-f08/lectures/09-ssa.pdf
Question 9
A grammar that is both left and right recursive for a non-terminal is
Cross
Ambiguous
Cross
Unambiguous
Tick
Information is not sufficient to decide whether it is ambiguous or Unambiguous.
Cross
None of the above


Question 9-Explanation: 
Suppose we have grammar like this :
S → n
B → BbB 
Here we see that grammar is left as well as right recursive but still it is unambiguous grammar because A is useless production but it is still part of grammar. So we can say that a grammar having both left as well as right recursion may or may not be ambiguous . Lets understand with another example as we have grammar like this A→AA using this grammar we can not produce any string in finite steps as language of this grammar is empty set {}. Hence, we finally get conclusion as if grammar is having both left as well as right recursion, then grammar may or may not be ambiguous. Option (C) is correct.
Question 10

The least number of temporary variables required to create a three-address code in static single assignment form for the expression a=b * d - c + b * e - c is ______

Cross

3

Tick

4

Cross

5

Cross

6



Question 10-Explanation: 
a=b * d - c + b * e - c
t1 = b * d
t2 = b * e
t3 = t1 + t2
t4 = t3 -c
a= t4 -c  

Total temp variables = 4

So, option (B) is correct.

Refer - Static Single Assignment

There are 38 questions to complete.

  • Last Updated : 21 Jan, 2014

Share your thoughts in the comments
Similar Reads