Question

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 heap) containing two fields \(f1\) and \(f2\), and the local variables \(x, y, z, p, q,\) and \(i\) are allotted registers. Common sub-expression elimination (CSE) optimization is applied on the code. The number of addition and dereference operations (of the form \(y \rightarrow f1\) or \(y \rightarrow f2\)) in the optimized code, respectively, are: 
 

• A. 403 and 102
• B. 203 and 2
• C. 303 and 102
• D. 303 and 2

Hint:

Common sub-expression elimination significantly reduces expensive operations like memory dereferencing by hoisting invariant expressions outside loops.

Answer 1

The Correct Option is D

To solve this problem, we need to apply common sub-expression elimination (CSE) optimization to the given ANSI C code and then determine the number of addition and dereference operations in the optimized code.

Step-by-Step Analysis and Optimization: 

1. Initial 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; 
                } 
            }

1. Common Sub-expression Identification:
   Identify common sub-expressions in the code that can be eliminated:
   • x + 3 is a common sub-expression used in the initialization of z and the assignment of p and q.
   • Dereferencing operations y->f1 and y->f2 are repeatedly accessed.
2. Applying CSE Optimization:
3. Counting Operations:
   • Addition Operations: In the optimized loop, each assignment inside the loop body uses one addition, and there are 4 unique addition operations:
     • Calculating temp1 = x + 3;
     • Calculating z = temp1 + temp2 + temp3;
     • In the if branch: p = p + temp1; and q = q + temp2;
     • In the else branch: p = p + temp3; and q = q + temp1;
   • Dereference Operations: Each field of the structure is dereferenced once for the calculation of temp2 and temp3. Thus, dereferencing operations are fixed:
     • Calculation of temp2 = y->f1;
     • Calculation of temp3 = y->f2;

Conclusion:

The number of addition operations in the optimized code is 303 and the number of dereference operations is 2. Thus, the correct answer is:

303 and 2