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

GATE CSE Data Flow Analyses PYQs

Standard yield10.4% of Compiler Design

Data flow analysis in GATE Compiler Design primarily evaluates an understanding of live variable analysis both conceptually and computationally on Control Flow… Read the guide

Take topic test

Questions: 8
Asked: since 2014
Total marks: 14
Marks / paper: 0.5

8 GATE CSE Data Flow Analyses PYQs with solutions, from Compiler Design. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Data Flow Analyses

Concepts, patterns, formulas and traps distilled from past papers.

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
CommonMCQ2 marks2015
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
CommonMCQ1 marks2025
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
CommonMCQ2 marks2026
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
OccasionalMCQ2 marks2021
Evaluating theoretical relationships between IN, OUT, USE, and DEF sets across adjacent statements within a straight-line basic block.
CFG Liveness Fixed-Point Computation
CommonMCQ2 marks2026, 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
OccasionalNAT2 marks2021
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
RareMCQ1 marks2014
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.