🚀 Code Optimisation & Data-Flow
Why it matters: Directly named in the syllabus: liveness, constant propagation and CSE via data-flow analysis.
Subtopics
Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 7 done.
1Local optimisations
2Common subexpression elimination
3Loop optimisations
4Live-variable analysis
5Reaching definitions
6Available expressions
7Data-flow framework at a glance
Formulas
Reaching definitions
OUT[B] = gen[B] ∪ (IN[B] − kill[B]); IN[B] = ∪ OUT[P]
Live variables
IN[B] = use[B] ∪ (OUT[B] − def[B]); OUT[B] = ∪ IN[S]
Available expressions
OUT[B] = gen[B] ∪ (IN[B] − kill[B]); IN[B] = ∩ OUT[P]; IN[entry] = ∅
Very busy expressions
backward, ∩ (used for code hoisting)
Iteration
repeat until no IN/OUT set changes; terminates since sets only move monotonically in a finite lattice
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Live variables at a point / number live
Compute IN/OUT for a small CFG and count variables live at a given point (register-pressure questions).
★★★
Reaching definitions / available expressions sets
IN/OUT sets for a block, or whether an expression is available, or which definitions reach a use.
★★★
Which optimisation applies / result of optimisation
Constant propagation + folding, CSE, dead code, strength reduction on a code fragment.
★★★
Direction / meet of an analysis
Match each analysis with forward/backward and may/must.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
3 real questions from the official GATE CSE papers (2014 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
3 questions · 0 correct of 0 attempted · marks 0 / 4
Year:
GATE 2025 CS1 · Q13MCQ1 mark
Which ONE of the following techniques used in compiler code optimization uses live variable analysis?
GATE 2023 · Q37MCQ2 marks
Consider the control flow graph:
ENTRY → B1 (i = m − 1; j = n; a = 10) → B2 (i = i + 1; j = j − 1) → B3 (a = 20) and B2 → B4 (i = a + 1) B3 → B4 B4 → B2 (back edge) and B4 → EXITWhich one of the following lists correctly the set of live variables at the exit point of each basic block?
GATE 2014 Set 1 · Q17MCQ1 mark
Which one of the following is FALSE?
Common traps
Liveness runs backward; start from the exit with OUT = ∅.
Available expressions initialises non-entry blocks with the universal set.
A definition kills all other definitions of the same variable.