GATE CS 2014 Set 1 Q.27 (CS Q.17): Intermediate Code Generation, Data Flow Analysis and Code Optimization

Which one of the following is FALSE?

A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end.

Available expression analysis can be used for common subexpression elimination.

Live variable analysis can be used for dead code elimination.

$x = 4 * 5 \implies x = 20$ is an example of common subexpression elimination.

Official answer and solution

Official answer: D
From: Official GATE 2014 answer key

Solution

Review definitions of basic compiler optimization techniques and data-flow analyses.

Let us check each statement:

(A) True: By definition, a basic block is a sequence of consecutive statements in which flow of control enters at the beginning and leaves at the end without halt or possibility of branching except at the end.
(B) True: Available expression analysis computes expressions whose values are guaranteed to be available at the current point, which directly enables common subexpression elimination.
(C) True: Live variable analysis determines whether a variable will be used along some path before being reassigned, which enables dead code elimination for assignments to dead variables.
(D) False: Replacing the expression $x = 4 * 5$ with $x = 20$ computes the value of constant operands at compile time, which is known as constant folding, not common subexpression elimination.

Therefore, statement D is FALSE.

Final answer

Common trap

Confusing constant folding (evaluating constant operations at compile time) with common subexpression elimination (reusing already computed expression values).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 1
Question: 27 of 65, printed as CS Q.17
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source