GATE CS 2015 Set 2 Q14 — Local Optimization

To determine the correct statement, let us analyze each option based on the definitions of an Abstract Syntax Tree (AST) and a Control Flow Graph (CFG):

• Option A is FALSE: In a CFG, a back-edge in a loop can point from a node $N_1$ (at the end of the loop body) to a successor node $N_2$ (the loop header). In the source code, the code for the loop header $N_2$ appears before the code for $N_1$.
• Option B is FALSE: While an AST is a tree and therefore acyclic, a CFG represents the flow of control and will contain cycles for any program containing loops (such as while, for, or goto statements).
• Option C is TRUE:
  • In an AST, a node representing a function call can have as many children (successors) as there are arguments in the call, or a block node can have as many children as there are statements in that block. This directly depends on the input program.
  • In a CFG, a basic block containing a switch-case statement can have $k$ successors, where $k$ is the number of cases defined in the input program.
  Thus, the maximum number of successors of a node in both representations depends on the input program.
• Option D is FALSE: A node in a CFG represents a basic block, which is a sequence of consecutive statements. Therefore, a single CFG node can correspond to multiple statements in the input program.