GATE CSE 2026 | Set 1 | Question: 32

Question

Consider the control flow graph shown in the figure.
 

Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B$4$ and B$5$?

Note: All the variables are integers.

• A. B4: $\{b+i\}$               B5: $\{c+m\}$
• B. B4: $\{g * k\}$             B5: $\{c+m\}$
• C. B4: $\{g * k, b+i\}$      B5:$\{$ $\}$
• D. B4: $\{g * k\}$             B5:$\{$ $\}$

Comments

 

Source: link

---

$IN(B4)=\{g*k\},\ GEN(B4)=\{g*k,b+i\},\ KILL(B4)=\{E_x,E_y\}$, so $OUT(B4)=(IN(B4)\cup GEN(B4))-KILL(B4)=\{g*k,b+i\}$.

Since $IN(B5)=OUT(B4)$, => $IN(B5)=\{g*k,b+i\}$?

So shouldn't the answer for $B5$ be $\{g*k,b+i\}$?
@P0535_Yedidyah_Sagar

Answer 1

The question becomes really easy if you know the basics.

Consider a expression z = x + y
A expression is said to be redundant at a point only if both of the below conditions are satisfied:

1. The value of x and y are not modified in the path, because that would mean x+y has to be recomputed and we cant use the earlier computed value.
2. All paths to the point computes z = x + y.

Look at the options:

(b+i) --> The value of b is modified in B3 which is on the path to B4. Not Redundant
(c+m) --> The value of c and m are not modified but it is not computed in B2( which is a block in the path to B5), violates 2nd condition. Not Redundant
(g*k) --> The value of g and k is never modified and it is available on all paths(i.e via B2 and B3) to B4. Satisfies both conditions.  Redundant

Only (g*k) is redundant in block 4.

OPTION D is correct.

Answer 2

Ye question Available Expressions Analysis ka hai.

 

Bass yeh dekho ki, 

1. kisi basic block me jo expression calculate ho raha hai, kya woh har possible path par pehle se calculate hua tha?

2. aur uske operands beech me change nahi hue?

 

If yes then it is redundant (common subexpression)

 

They are asking B4 and B5  redundant expressions, so let's focus on them only.

B4 me g*k  analyze karte hai, 

Q1 - B4 ke pehle har path par calculate hua tha ?  

         Path 1 - B1 → B2 → B4  .........calculated in B2

         Path 2 - B1 → B3 → B4  .........calculated in B3 

Q2. - Kya g*k change/modify hue ?  Nahi 

Hence, g*k is redundant term.

 

B4 mai b+i bhi hai so use dekhte hai, 

Q1 - available/calculated in every path ? 

          Path 1 -  B1 → B2 → B4  ........available in B1 

          Path 2 - B1 → B3 → B4  .........different in B1 and B3  (B3 mai b ki value change ho gayi)

Hence, b+i not redundant.

 

Last, B5 mai c+m check karte hai, 

Q1 - available/calculated in every path ?

          Path 1 -  B1 → B2 → B4 → B5  ........not available in this path

Hence, c+m is not redundant.

 

Hence, Ans(D)  B4: {g∗k}   B5:{ }

Comments

Great Answer 👍

Answer 3

Answer : Option D

Sub expression : g*k is redundant in block B4. As, g*k is evaluated in both B2 and B3. Further, values of g and k have not been changed when they reached B4.

Regarding "b+i" in B1. The value of b is modified in B3. So, "b+i" is not redundant in B4.

"c+m" has not been evaluated via B2 path. So, "c+m" is not redundant in B5

Answer 4

Available Expression Analysis is used to find common subexpressio. 

---

Comments

nice

 

Answer 5

https://www.youtube.com/watch?v=IUAIytbb2mw&t=16236s

https://www.youtube.com/watch?v=oBAqib3LDi4&t=6756s

Answer 6

Shortcut trick