All Exams Test series for 1 year @ ₹349 only
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 B4 and B5?
Note: All the variables are integers.

The correct answer is
B4: $\{g * k\}$
B5: $\{\}$

To determine the redundant expressions in the basic blocks \(B4\) and \(B5\), we need to analyze the control flow graph and identify any common subexpressions that have been previously computed and whose variables have not changed since their computation.

Let's examine each block:

  1. Basic Block B2:
    • Expressions: \(a = g \times k\)\(f = d - f\)\(a = c \times 4\)
    • \(g \times k\) is computed here.
  2. Basic Block B3:
    • Expressions: \(t = g \times k\)\(b = c + m\)
    • \(g \times k\) is recomputed, indicating a potential redundancy if \(g\) or \(k\) have not changed since the last computation.
  3. Basic Block B4:
    • Expressions: \(x = g \times k\)\(y = b + i\)
    • \(g \times k\) is a redundant expression because it was already computed in \(B2\) and neither \(g\) nor \(k\) have been altered.
    • \(b + i\) is computed again here, but there's no evidence that it was computed prior to \(B1\) suggesting it is not redundant.
  4. Basic Block B5:
    • Expression: \(z = c + m\)
    • \(c + m\) was calculated in \(B3\) but not carried forward to \(B5\) as these blocks do not share a direct relation without a merging point.

Based on this analysis, the redundant expressions in \(B4\) are \(\{g \times k\}\) and there are no redundant expressions in \(B5\).

Correct Answer: B4: \(\{g \times k\}\), B5: \(\{\}\)

Was this answer helpful?

Important Questions from Code Optimization

  1. Which of the following is the correct High level code for the given TAC in the passage
  2. What are the various LEADERS (leading statements) for the TAC given in the passage?
  3. Which of the followings is the correct Flow graph for the TAC given in the passage?
  4. Which of the following is the Optimized version for the given TAC in the passage
  5. Consider the control flow graph given below.



    Which one of the following options is the set of live variables at the exit point of each basic block?

Need Expert Advice?

Start Your Preparation with Prepp Mobile App

Download the app from Google Play & App Store
Download the app from Google Play & App Store
Prepp Mobile App