Optimisation formulas

Local optimisation and data-flow analysis. 3 formulas for GATE CS Compiler Design, each with when to use it. Each is explained in the topic notes.

All 3 Optimisation formulas

LIVE VARIABLES (BACKWARD, UNION)

IN [B] = use [B] \cup (OUT [B] - def [B]), OUT [B] = S \in succ (B) ⋃ IN [S]

A variable is live at a point if its current value may be read later before being overwritten. Initialise IN[B] = ∅ for all B; OUT of an exit block is ∅ unless the question names live-out variables.

REACHING DEFINITIONS (FORWARD, UNION)

OUT [B] = gen [B] \cup (IN [B] - kill [B]), IN [B] = P \in pred (B) ⋃ OUT [P]

A definition reaches a point if some path from it to that point does not redefine the variable. Initialise OUT[B] = ∅; IN[entry] = ∅.

AVAILABLE EXPRESSIONS (FORWARD, INTERSECTION)

OUT [B] = e_gen [B] \cup (IN [B] - e_kill [B]), IN [B] = P \in pred (B) ⋂ OUT [P]

An expression is available at a point if on every path to it the expression has been computed and its operands not changed since. IN[entry] = ∅; initialise OUT[B] to the set U of all expressions for every other block.

Where this was asked: 2023 (1), 2024 (1), 2025 (2), 2026 (2). See the 6 previous-year questions on Optimisation. This shows what was asked, not what will be asked.

KEEP GOING

Optimisation: the notes and 6 solved previous-year questions