Discussion
Consider the control flow graph shown in the figure.
| Block | Statements | Control flows to |
|---|---|---|
| B1 (from ENTRY) | a = b + i | B2 and B3 |
| B2 | a = g * k f = d - f a = c * 4 | B4 |
| B3 | t = g * k b = c + m | B4 |
| B4 | x = g * k y = b + i | B5 |
| B5 | z = c + m | EXIT |
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.
Answer: D
The redundant expressions are B4: { g * k } and B5: { }.
An expression is redundant in a block if it is available there: computed on every path into the block, with none of its operands changed afterwards.
- g * k is computed in both B2 and B3, the only predecessors of B4, and neither block changes g or k afterwards, so it is available in B4.
- b + i is computed in B1, but B3 then assigns b = c + m, so on the path through B3 the value is stale. It is not available in B4.
- c + m is computed only in B3. On the path B1, B2, B4, B5 it is never computed, so it is not available in B5.
The options listing b + i or c + m each ignore one of these paths.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development