GATE CS 2006 Q60 — Local Optimization

To determine which statement is false, let's analyze each optimization technique with respect to the given code segment:

1. Loop Invariant Computation (Option A is True): An expression is loop-invariant if its value does not change during the execution of the loop.
   • In the inner loop (with loop variable $j$), the expression 5*i and the condition i%2 depend only on $i$.
   • Since $i$ is constant relative to the inner loop, these computations can be hoisted outside the inner loop.
2. Common Sub-expression Elimination (Option B is True): An occurrence of an expression is a common sub-expression if it was previously computed and the values of its operands have not changed since.
   • The expression 4*j is computed twice within the same iteration: once in x += (4*j + 5*i) and again in y += (7 + 4*j).
   • We can compute temp = 4*j once and reuse it.
3. Strength Reduction (Option C is True): Strength reduction replaces expensive operations (like multiplication) with cheaper ones (like addition) using induction variables.
   • The multiplication 4*j can be replaced by initializing a temporary variable to 0 and adding 4 in each iteration of the $j$-loop.
4. Dead Code Elimination (Option D is False): Dead code is code that is either unreachable or computes a value that is never used.
   • All statements inside the loops are reachable and actively update the variables x and y. There is no dead code present in this segment.

Therefore, statement D is false.