What are common examiner traps in Data Flow Analyses?

Confusing variable definition (kill) with variable use (gen) along a path. Assuming a variable redefined within a loop or downstream block is still live past its redefinition point. Conflating compiler data-flow optimizations (register assignment via liveness) with runtime environment mechanisms (activation record/stack management) or peephole/local optimizations (constant folding, strength reduction). Using set union ( ) instead of intersection ( ) at CFG merge points, falsely marking expressions available along only one path as redundant. Failing to kill expressions when one of their constituent operand variables is reassigned (e.g., b = c + m kills b + i). Assuming an expression computed inside a target block is redundant even when it is not in the In set of that block. Failing to iterate until a fixed point is reached when loops/back-edges exist, resulting in missed propagated live variables. Applying forward analysis transfer functions instead of backward analysis (confusing IN/OUT flow directions). Incorrectly killing variables in def[B] before considering uses in the same block that precede the definition. Confusing OUT[B] (exit of block) with IN[B] (entry of block) when selecting options. Counting multiple variables assigned identical expressions as separate nodes instead of attaching multiple labels to a single operator node (e.g., treating d = b + c as a new node rather than labeling node a = b + c with d). Forgetting to count leaf nodes (variable identifiers and numerical literals like 1) in the total node count. Over-counting constants or literals that appear multiple times when they should map to a single shared leaf node. Confusing Constant Folding (evaluating compile-time constant arithmetic, e.g., 4 * 5 20) with Common Subexpression Elimination or Constant Propagation. Misattributing which data-flow analysis enables which optimization (e.g., confusing the roles of Liveness Analysis vs. Available Expressions).

Data Flow Analyses

8 Qs · since 2014 · 14 marks · 0.5 marks/paperStandard yield

Take topic test

Data flow analysis in GATE Compiler Design primarily evaluates an understanding of live variable analysis both conceptually and computationally on Control Flow Graphs (CFGs). Testi… Guide

Type

GATE CSE 2026 Set 1Q42MCQ2 marksMediumDiagramConsider 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.
GATE CSE 2026 Set 2Q45MCQ2 marksMediumDiagramConsider 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?
GATE CSE 2025 Set 1Q13MCQ1 markEasyWhich ONE of the following techniques used in compiler code optimization uses live variable analysis?
GATE CSE 2023Q37MCQ2 marksMediumDiagramConsider the control flow graph shown. Which one of the following choices correctly lists the set of $\textit{live}$ variables at the exit point of each basic block?
GATE CSE 2021 Set 1Q50NAT2 marksMediumConsider the following C code segment: a = b + c; e = a + 1; d = b + c; f = d + 1; g = e + f; In a compiler, this code segment is represented internally as a directed acyclic graph (DAG). The number of nodes in the DAG is ________.
GATE CSE 2021 Set 2Q38MCQ2 marksEasyFor a statement $S$ in a program, in the context of liveness analysis, the following sets are defined: $USE(S)$ : the set of variables used in $S$ $IN(S)$ : the set of variables that are live at the entry of $S$ $OUT(S)$ : the set of variables that are live at the exit of $S$ Consider a basic block…
GATE CSE 2015 Set 1Q50MCQ2 marksMediumDiagramA variable $x$ is said to be live at a statement $S_i$ in a program if the following three conditions hold simultaneously: i. There exists a statement $S_j$ that uses $x$ ii. There is a path from $S_i$ to $S_j$ in the flow graph corresponding to the program iii. The path has no intervening assignment to $x$ …
GATE CSE 2014 Set 1Q17MCQ1 markEasyWhich one of the following is FALSE?

Topic guide

What does GATE test in Data Flow Analyses?

Data flow analysis in GATE Compiler Design primarily evaluates an understanding of live variable analysis both conceptually and computationally on Control Flow Graphs (CFGs). Testing ranges from 1-mark recall questions on the compiler optimizations that rely on data-flow facts (like register allocation) to 2-mark CFG tracing questions tracking variable uses and definitions across program points.

Core concepts

Live Variable Analysis
Control Flow Graphs (CFGs) and Basic Blocks
Register Allocation and Assignment via Live Ranges
Use-Definition (def-use) Chains and Variable Lifetimes
Distinction between data flow analysis and local/loop optimizations (Strength Reduction, Constant Folding)
Global Common Subexpression Elimination
Available Expressions Dataflow Analysis
Meet-over-all-paths confluence using set intersection ( )
Gen and Kill sets for arithmetic expressions
Variable redefinition and expression invalidation
Liveness analysis (backward, any-path / union data-flow analysis)
Use and Def sets for statements and basic blocks
Fixed-point iterative data-flow propagation on cyclic CFGs
Sequential composition and boundary conditions within basic blocks
DAG representation of basic blocks
Local common subexpression elimination
Leaf nodes vs. Interior operator nodes in a DAG
Variable label attachments to existing DAG nodes
Value numbering within basic blocks
Definition and structure of a Basic Block (single entry, single exit)
Available Expressions Analysis and its application in Common Subexpression Elimination (CSE)
Live Variable Analysis and its application in Dead Code Elimination
Constant Folding vs. Constant Propagation vs. Common Subexpression Elimination

Recurring question patterns

Liveness Analysis on Control Flow Graphs
common · MCQ · 2 marks · 2015
Given a CFG with basic blocks containing 3-address statements, determine which variables are live at specific program points or find the intersection/set of live variables across designated blocks.
Applications of Data Flow Frameworks
common · MCQ · 1 marks · 2025
Conceptual identification of which backend optimization or code generation task (e.g., register allocation/assignment, dead-code elimination) depends on specific data flow analyses (like liveness analysis).
Global Available Expression Analysis on CFGs
common · MCQ · 2 marks · 2026
Candidates are given a Control Flow Graph with several basic blocks (including branching and join nodes) and must determine which evaluated expressions are redundant (available from all incoming paths without being killed) within specific target basic blocks.
Sequential Data-Flow In/Out Relationships
occasional · MCQ · 2 marks · 2021
Evaluating theoretical relationships between IN, OUT, USE, and DEF sets across adjacent statements within a straight-line basic block.
CFG Liveness Fixed-Point Computation
common · MCQ · 2 marks · 2026, 2023
Given a CFG with 3 to 4 basic blocks containing branches and loops/back-edges, compute the precise set of live variables at the exit point (OUT set) or entry point (IN set) of every block.
DAG Node Counting for a Basic Block
occasional · NAT · 2 marks · 2021
Given a sequence of three-address assignments or C-style statements within a single basic block, construct its internal Directed Acyclic Graph (DAG) by reusing nodes for common subexpressions and identical operands, then find the total number of nodes (leaves plus interior operator nodes).
Conceptual / Definitional Truth Verification
rare · MCQ · 1 marks · 2014
A set of four statements testing core definitions of basic blocks, data-flow analysis applications (e.g., liveness analysis for dead code elimination, available expressions for CSE), and specific transformation examples to identify the TRUE/FALSE statement.

Formulas GATE uses

Live Variable Condition

\text{Live}(x, S_i) \iff \exists \text{ path } S_i \to S_j \text{ s.t. } x \in \text{use}(S_j) \land x \notin \text{def}(S_k) \; \forall S_k \in \text{path}(S_i, S_j)

Used when determining if variable $x$ holds a value at statement $S_i$ that is read downstream before any intervening reassignment.

Simultaneous Liveness across Program Points

\text{Live}(B_1) \cap \text{Live}(B_2)

Used when finding variables that are simultaneously live at two different basic block statements or program points.

Available Expressions Confluence (Meet) Operator

\text{In}[B] = \bigcap_{P \in \text{Pred}(B)} \text{Out}[P]

Used at CFG join points to compute the set of expressions available at the entry of basic block $B$ from all its predecessors.

Dataflow Transfer Function for Available Expressions

\text{Out}[B] = \text{Gen}[B] \cup (\text{In}[B] - \text{Kill}[B])

Used to compute expressions available at the exit of basic block $B$ after accounting for newly generated expressions and killed expressions.

Liveness Analysis Transfer Function

\text{IN}[B] = \text{use}[B] \cup (\text{OUT}[B] \setminus \text{def}[B])

Computing the live variables at the entry of basic block $B$ from its used/defined variables and exit live set.

Liveness Analysis Confluence / Meet Operator

\text{OUT}[B] = \bigcup_{S \in \text{succ}(B)} \text{IN}[S]

Gathering incoming backward data-flow information from all immediate successor blocks of block $B$ .

Sequential Statement Composition in Basic Block

\text{OUT}(S_1) = \text{IN}(S_2)

Relating boundary sets of two consecutive statements $S_1$ and $S_2$ within the same basic block.

Total DAG Nodes

|V_{\text{DAG}}| = |V_{\text{leaf}}| + |V_{\text{operator}}| = \text{distinct initial identifiers/constants} + \text{distinct non-redundant operations}

Used when computing the total number of nodes in a basic block DAG representation after applying common subexpression elimination.

Examiner traps in Data Flow Analyses

Confusing variable definition (kill) with variable use (gen) along a path.
Assuming a variable redefined within a loop or downstream block is still live past its redefinition point.
Conflating compiler data-flow optimizations (register assignment via liveness) with runtime environment mechanisms (activation record/stack management) or peephole/local optimizations (constant folding, strength reduction).
Using set union ( ) instead of intersection ( ) at CFG merge points, falsely marking expressions available along only one path as redundant.
Failing to kill expressions when one of their constituent operand variables is reassigned (e.g., b = c + m kills b + i).
Assuming an expression computed inside a target block is redundant even when it is not in the In set of that block.
Failing to iterate until a fixed point is reached when loops/back-edges exist, resulting in missed propagated live variables.
Applying forward analysis transfer functions instead of backward analysis (confusing IN/OUT flow directions).
Incorrectly killing variables in def[B] before considering uses in the same block that precede the definition.
Confusing OUT[B] (exit of block) with IN[B] (entry of block) when selecting options.
Counting multiple variables assigned identical expressions as separate nodes instead of attaching multiple labels to a single operator node (e.g., treating d = b + c as a new node rather than labeling node a = b + c with d).
Forgetting to count leaf nodes (variable identifiers and numerical literals like 1) in the total node count.
Over-counting constants or literals that appear multiple times when they should map to a single shared leaf node.
Confusing Constant Folding (evaluating compile-time constant arithmetic, e.g., 4 * 5 20) with Common Subexpression Elimination or Constant Propagation.
Misattributing which data-flow analysis enables which optimization (e.g., confusing the roles of Liveness Analysis vs. Available Expressions).

How questions are asked

Identify variables live at designated basic blocks in a CFG diagram
Match optimization techniques to their required data flow analyses
Identify redundant expressions in designated basic blocks of a given CFG diagram
Compute entry/exit available expression sets for specified nodes
Conceptual relation matching for statement boundary sets
CFG diagram analysis for multi-block OUT/IN set determination
Calculate the total number of nodes in the DAG for a given code snippet
Identify FALSE/TRUE statement among optimization and data-flow analysis definitions

Paper trends

Questions alternate between structural CFG path tracing with formal liveness conditions (2015) and direct conceptual mapping of analysis frameworks to optimization passes (2025).
2025, 2015
Emphasis is placed on global dataflow properties where confluence at join points requires intersection (all-paths availability) and careful tracking of operand redefinitions that kill previously computed expressions.
2026
Shift from purely theoretical statement-level transfer equation identities to full CFG-based iterative fixed-point computations involving cycles.
2026, 2023, 2021
Consistent presentation as 2-mark graphical/CFG-based MCQs requiring multi-pass iterative analysis until convergence.
2026, 2023
Questions on local optimization have moved toward exact NAT numerical queries asking for structural properties (e.g., node count) of DAG intermediate representations.
2021
Appeared as a 1-mark conceptual MCQ focusing on identifying standard definitions and matching optimization techniques to their underlying data-flow analyses.
2014

Difficulty notes

Easy: Direct theoretical classification identifying the purpose of a data-flow analysis (e.g., linking liveness analysis to register allocation). Medium: Tracing CFG paths with multiple branches/loops to compute exact live sets at one or more basic block entries/exits.

Data Flow Analyses

8 Qs · since 2014 · 14 marks · 0.5 marks/paperStandard yield

Take topic test

Data flow analysis in GATE Compiler Design primarily evaluates an understanding of live variable analysis both conceptually and computationally on Control Flow Graphs (CFGs). Testi… Guide

Type

Topic guide

What does GATE test in Data Flow Analyses?

Core concepts

Live Variable Analysis
Control Flow Graphs (CFGs) and Basic Blocks
Register Allocation and Assignment via Live Ranges
Use-Definition (def-use) Chains and Variable Lifetimes
Distinction between data flow analysis and local/loop optimizations (Strength Reduction, Constant Folding)
Global Common Subexpression Elimination
Available Expressions Dataflow Analysis
Meet-over-all-paths confluence using set intersection ( )
Gen and Kill sets for arithmetic expressions
Variable redefinition and expression invalidation
Liveness analysis (backward, any-path / union data-flow analysis)
Use and Def sets for statements and basic blocks
Fixed-point iterative data-flow propagation on cyclic CFGs
Sequential composition and boundary conditions within basic blocks
DAG representation of basic blocks
Local common subexpression elimination
Leaf nodes vs. Interior operator nodes in a DAG
Variable label attachments to existing DAG nodes
Value numbering within basic blocks
Definition and structure of a Basic Block (single entry, single exit)
Available Expressions Analysis and its application in Common Subexpression Elimination (CSE)
Live Variable Analysis and its application in Dead Code Elimination
Constant Folding vs. Constant Propagation vs. Common Subexpression Elimination

Recurring question patterns

Liveness Analysis on Control Flow Graphs
common · MCQ · 2 marks · 2015
Given a CFG with basic blocks containing 3-address statements, determine which variables are live at specific program points or find the intersection/set of live variables across designated blocks.
Applications of Data Flow Frameworks
common · MCQ · 1 marks · 2025
Conceptual identification of which backend optimization or code generation task (e.g., register allocation/assignment, dead-code elimination) depends on specific data flow analyses (like liveness analysis).
Global Available Expression Analysis on CFGs
common · MCQ · 2 marks · 2026
Candidates are given a Control Flow Graph with several basic blocks (including branching and join nodes) and must determine which evaluated expressions are redundant (available from all incoming paths without being killed) within specific target basic blocks.
Sequential Data-Flow In/Out Relationships
occasional · MCQ · 2 marks · 2021
Evaluating theoretical relationships between IN, OUT, USE, and DEF sets across adjacent statements within a straight-line basic block.
CFG Liveness Fixed-Point Computation
common · MCQ · 2 marks · 2026, 2023
Given a CFG with 3 to 4 basic blocks containing branches and loops/back-edges, compute the precise set of live variables at the exit point (OUT set) or entry point (IN set) of every block.
DAG Node Counting for a Basic Block
occasional · NAT · 2 marks · 2021
Given a sequence of three-address assignments or C-style statements within a single basic block, construct its internal Directed Acyclic Graph (DAG) by reusing nodes for common subexpressions and identical operands, then find the total number of nodes (leaves plus interior operator nodes).
Conceptual / Definitional Truth Verification
rare · MCQ · 1 marks · 2014
A set of four statements testing core definitions of basic blocks, data-flow analysis applications (e.g., liveness analysis for dead code elimination, available expressions for CSE), and specific transformation examples to identify the TRUE/FALSE statement.

Formulas GATE uses

Live Variable Condition

\text{Live}(x, S_i) \iff \exists \text{ path } S_i \to S_j \text{ s.t. } x \in \text{use}(S_j) \land x \notin \text{def}(S_k) \; \forall S_k \in \text{path}(S_i, S_j)

Used when determining if variable $x$ holds a value at statement $S_i$ that is read downstream before any intervening reassignment.

Simultaneous Liveness across Program Points

\text{Live}(B_1) \cap \text{Live}(B_2)

Used when finding variables that are simultaneously live at two different basic block statements or program points.

Available Expressions Confluence (Meet) Operator

\text{In}[B] = \bigcap_{P \in \text{Pred}(B)} \text{Out}[P]

Used at CFG join points to compute the set of expressions available at the entry of basic block $B$ from all its predecessors.

Dataflow Transfer Function for Available Expressions

\text{Out}[B] = \text{Gen}[B] \cup (\text{In}[B] - \text{Kill}[B])

Used to compute expressions available at the exit of basic block $B$ after accounting for newly generated expressions and killed expressions.

Liveness Analysis Transfer Function

\text{IN}[B] = \text{use}[B] \cup (\text{OUT}[B] \setminus \text{def}[B])

Computing the live variables at the entry of basic block $B$ from its used/defined variables and exit live set.

Liveness Analysis Confluence / Meet Operator

\text{OUT}[B] = \bigcup_{S \in \text{succ}(B)} \text{IN}[S]

Gathering incoming backward data-flow information from all immediate successor blocks of block $B$ .

Sequential Statement Composition in Basic Block

\text{OUT}(S_1) = \text{IN}(S_2)

Relating boundary sets of two consecutive statements $S_1$ and $S_2$ within the same basic block.

Total DAG Nodes

|V_{\text{DAG}}| = |V_{\text{leaf}}| + |V_{\text{operator}}| = \text{distinct initial identifiers/constants} + \text{distinct non-redundant operations}

Used when computing the total number of nodes in a basic block DAG representation after applying common subexpression elimination.

Examiner traps in Data Flow Analyses

Confusing variable definition (kill) with variable use (gen) along a path.
Assuming a variable redefined within a loop or downstream block is still live past its redefinition point.
Conflating compiler data-flow optimizations (register assignment via liveness) with runtime environment mechanisms (activation record/stack management) or peephole/local optimizations (constant folding, strength reduction).
Using set union ( ) instead of intersection ( ) at CFG merge points, falsely marking expressions available along only one path as redundant.
Failing to kill expressions when one of their constituent operand variables is reassigned (e.g., b = c + m kills b + i).
Assuming an expression computed inside a target block is redundant even when it is not in the In set of that block.
Failing to iterate until a fixed point is reached when loops/back-edges exist, resulting in missed propagated live variables.
Applying forward analysis transfer functions instead of backward analysis (confusing IN/OUT flow directions).
Incorrectly killing variables in def[B] before considering uses in the same block that precede the definition.
Confusing OUT[B] (exit of block) with IN[B] (entry of block) when selecting options.
Counting multiple variables assigned identical expressions as separate nodes instead of attaching multiple labels to a single operator node (e.g., treating d = b + c as a new node rather than labeling node a = b + c with d).
Forgetting to count leaf nodes (variable identifiers and numerical literals like 1) in the total node count.
Over-counting constants or literals that appear multiple times when they should map to a single shared leaf node.
Confusing Constant Folding (evaluating compile-time constant arithmetic, e.g., 4 * 5 20) with Common Subexpression Elimination or Constant Propagation.
Misattributing which data-flow analysis enables which optimization (e.g., confusing the roles of Liveness Analysis vs. Available Expressions).

How questions are asked

Identify variables live at designated basic blocks in a CFG diagram
Match optimization techniques to their required data flow analyses
Identify redundant expressions in designated basic blocks of a given CFG diagram
Compute entry/exit available expression sets for specified nodes
Conceptual relation matching for statement boundary sets
CFG diagram analysis for multi-block OUT/IN set determination
Calculate the total number of nodes in the DAG for a given code snippet
Identify FALSE/TRUE statement among optimization and data-flow analysis definitions

Paper trends

Questions alternate between structural CFG path tracing with formal liveness conditions (2015) and direct conceptual mapping of analysis frameworks to optimization passes (2025).
2025, 2015
Emphasis is placed on global dataflow properties where confluence at join points requires intersection (all-paths availability) and careful tracking of operand redefinitions that kill previously computed expressions.
2026
Shift from purely theoretical statement-level transfer equation identities to full CFG-based iterative fixed-point computations involving cycles.
2026, 2023, 2021
Consistent presentation as 2-mark graphical/CFG-based MCQs requiring multi-pass iterative analysis until convergence.
2026, 2023
Questions on local optimization have moved toward exact NAT numerical queries asking for structural properties (e.g., node count) of DAG intermediate representations.
2021
Appeared as a 1-mark conceptual MCQ focusing on identifying standard definitions and matching optimization techniques to their underlying data-flow analyses.
2014