GATE 2026 CS1 Q.42: solution and answer

Official answer: DSource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

1. An expression is redundant at a point if it is available there: it has been computed on every path from ENTRY, and none of its operands has been redefined since.

2. Available-expression equations: $\text{IN}(B)={\bigcap }_{P\in \text{pred}(B)}\text{OUT}(P)$ and $\text{OUT}(B)=\text{gen}(B)\cup (\text{IN}(B)-\text{kill}(B))$, with $\text{IN}(B1)=\{\}$.

3. B1 has a = b + i. It generates $b+i$. The variable $a$ is not an operand of any expression in play, so nothing is killed. $\text{OUT}(B1)=\{b+i\}$.

4. B2 has three statements. a = g * k generates $g\ast k$. f = d - f generates $d-f$ and then kills it, because $f$ is redefined by the same statement. a = c * 4 generates $c\ast 4$. No statement redefines $b$, $i$, $g$ or $k$, so $b+i$ survives. $\text{OUT}(B2)=\{b+i,g\ast k,c\ast 4\}$.

5. B3 has t = g * k, which generates $g\ast k$. Then b = c + m generates $c+m$ and kills $b+i$, because $b$ is redefined. $\text{OUT}(B3)=\{g\ast k,c+m\}$.

6. $\text{IN}(B4)=\text{OUT}(B2)\cap \text{OUT}(B3)=\{g\ast k\}$. So g * k in B4 is redundant. b + i in B4 is not redundant, because on the path through B3 it was killed.

7. B4 evaluates g * k (already available, nothing new generated) and b + i, which becomes available. Neither $x$ nor $y$ is an operand of any expression in play. $\text{OUT}(B4)=\{g\ast k,b+i\}$, so $\text{IN}(B5)=\{g\ast k,b+i\}$.

8. B5 computes c + m, which is not in $\text{IN}(B5)$. The path through B2 never computes $c+m$. So B5 has no redundant expression.

9. Result: B4: $\{g\ast k\}$ and B5: $\{\}$. This is option (D).