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

Step 1: Identify common sub-expressions.
The expressions \(x + 3\), \(y \rightarrow f1\), and \(y \rightarrow f2\) are loop-invariant and repeatedly used. With CSE applied, these expressions are computed only once and stored in temporary registers.
Let:
\[ t_1 = x + 3, t_2 = y \rightarrow f1, t_3 = y \rightarrow f2 \]

Step 2: Count dereference operations.
The dereferences \(y \rightarrow f1\) and \(y \rightarrow f2\) are each performed exactly once before the loop due to CSE.
\[ \text{Total dereference operations} = 2 \]

Step 3: Analyze addition operations.
• Computation of \(z = x + 3 + y \rightarrow f1 + y \rightarrow f2\): This requires 3 additions.
• The loop runs from \(i = 0\) to \(i < 200\) with step size 2, so the number of iterations is: \[ \frac{200}{2} = 100 \]
• In each iteration, exactly one addition is executed for updating either \(p\) or \(q\), depending on the branch taken, and another addition for updating the other variable. Hence, 3 additions per iteration occur (two inside the body and one for incrementing \(i\)).
Thus, total additions inside the loop: \[ 100 \times 3 = 300 \]

Step 4: Total addition count.
\[ 3 \text{ (initial)} + 300 \text{ (loop)} = 303 \]

Step 5: Final conclusion.
After common sub-expression elimination, the optimized code performs:
• \(303\) addition operations
• \(2\) dereference operations