All Exams Test series for 1 year @ ₹349 only
Question

Consider the following Three Address code sample for solving the questions:
100: t1 = y+2
101: initial = x/t1
102: limit = 10
103: if i > j goto 105
104: goto 111
105: if num > b goto 107
106: goto 111
107: num = limit-1
108: b = y+2
109: i = i - num
110: goto 103
111: j = i - num
112: k= j+b

What all blocks does Block 3 & Block 5 dominate in the Flow graph for the TAC given in the passage?

The correct answer is
Block 3:3 ; Block 5:5

To solve this problem, we need to determine which blocks are dominated by Block 3 and Block 5 in the flow graph derived from the given Three Address Code (TAC). Dominance in a control flow graph implies that a block B is said to dominate another block C if every path from the start block to block C goes through block B.

Let's first break down the given TAC to identify the basic blocks:

  1. Block 1: 100: \(t1 = y + 2\)
  2. Block 2: 101: \(initial = x/t1\)
  3. Block 3:
    • 102: \(limit = 10\)
    • 103: \(\text{if } i > j \text{ goto 105}\)
    • 104: \(\text{goto 111}\)
  4. Block 4:
    • 105: \(\text{if } num > b \text{ goto 107}\)
    • 106: \(\text{goto 111}\)
  5. Block 5:
    • 107: \(num = limit - 1\)
    • 108: \(b = y + 2\)
    • 109: \(i = i - num\)
    • 110: \(\text{goto 103}\)
  6. Block 6:
    • 111: \(j = i - num\)
    • 112: \(k = j + b\)

Now, examining the flow of the control graph:

Block 3 is a branching block due to the conditional jumps in instructions 103 and 104. Block 3's control transfers either to Block 5 (via instruction 103) or Block 6 (via instruction 104).

Block 5 receives control from both Block 4 and Block 3 via instruction 105, and it loops back to Block 3 at instruction 110.

Let's analyze the dominance:

  • Dominance of Block 3: Block 3 dominates itself (102-104), as a block always dominates itself. However, because of conditional branching, no other blocks are necessarily dominated by it as all possible branches do not mandatorily pass through Block 3.
  • Dominance of Block 5: Block 5 follows the execution of Block 4 and Block 3 but returns the control to Block 3, so it doesn't dominate any block other than itself.

Thus, the correct answer is:

  • Block 3: Dominates itself.
  • Block 5: Dominates itself.

Therefore, the correct answer from the given options is:

Block 3:3 ; Block 5:5

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 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.

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