GATE CS & IT Engineering Compiler Design Syllabus

For a single statement $s:\ x = y + z$, give the live-variable transfer function $IN[s]$ in terms of $OUT[s]$.

$$IN[s] = (OUT[s] - \{x\}) \cup \{y, z\}$$ — $x$ is killed (defined), and $y, z$ are generated (used).

What is the relationship between liveness analysis and dead-code elimination?

If the variable defined by a statement is not live immediately after that statement (and the statement has no side effects), the assignment is dead and can be removed. Liveness identifies exactly such useless definitions.

How is liveness analysis used in register allocation?

Liveness defines live ranges of variables; two variables that are simultaneously live interfere. The interference graph is built from this, and graph coloring assigns registers so that interfering variables get different registers.

When do two variables 'interfere' in the interference graph used for register allocation?

Two variables interfere if their live ranges overlap — i.e., there is a point where both are simultaneously live — so they cannot share the same register.

Why does liveness analysis use the may (union) meet rather than must (intersection)?

A variable is live if it is used along some (any) future path, not all paths. Union over successors captures this 'may be used' (existential) property, making liveness a 'may' analysis.

What is the time complexity bound for the iterative liveness analysis, and why does it terminate?

It terminates because each iteration only adds variables to the monotone increasing IN/OUT sets, bounded by the finite variable set. With $n$ nodes and $v$ variables, a bit-vector iterative solver runs in roughly $O(n^2 v)$ worst case, often near-linear in practice.

In liveness analysis, after computing fixed point, $OUT[B] = \{a, b\}$ and $B$ contains only $c = a + 1$. What is $IN[B]$?

$def[B] = \{c\}$, $use[B] = \{a\}$. $IN[B] = use[B] \cup (OUT[B] - def[B]) = \{a\} \cup (\{a,b\} - \{c\}) = \{a, b\}$.

What distinguishes a 'live' variable from a 'reaching' definition conceptually?

Liveness is a backward analysis about future uses of a variable's value; reaching definitions is a forward analysis about which definitions of a variable may reach a point. They are dual in direction and ask different questions.

What is common subexpression elimination (CSE)?

CSE is an optimization that detects expressions computed more than once with the same operand values, and replaces redundant recomputations by reusing the previously computed result (stored in a temporary).

When is an expression $x\ op\ y$ called a common subexpression at a point?

It is a common subexpression if it was previously computed, and the values of $x$ and $y$ have not changed (no redefinition of $x$ or $y$) since that previous computation — so the earlier result is still valid.

What is an 'available expression', and how does it relate to CSE?

An expression $e$ is available at point $p$ if on every path from entry to $p$, $e$ has been computed and none of its operands redefined afterward. Available-expressions analysis identifies expressions safe to reuse, which is the basis for global CSE.

What are the direction and meet operator of available-expressions analysis?

Available expressions is a forward data-flow analysis with set intersection ($\cap$) as the meet operator (a 'must' analysis — available on all paths).

State the data-flow equations for available expressions.

$$OUT[B] = e\_gen[B] \cup (IN[B] - e\_kill[B])$$ $$IN[B] = \bigcap_{P \in pred(B)} OUT[P]$$ with $IN[\text{ENTRY}] = \varnothing$ and all other $OUT$ initialized to the universal set $U$.

In available-expressions analysis, what do $e\_gen[B]$ and $e\_kill[B]$ mean?

$e\_gen[B]$ is the set of expressions evaluated in $B$ and not subsequently killed in $B$ (their operands not redefined afterward in $B$); $e\_kill[B]$ is the set of expressions whose operands are redefined (killed) in $B$.

Why is the initialization for available expressions the universal set $U$ (not empty) for interior blocks?

Because it is a 'must' / intersection analysis: to find the maximum fixed point, interior $OUT$ sets start optimistically as the full universe $U$ and shrink via intersection. Starting empty would give the trivial all-empty (least) solution incorrectly.

Distinguish local CSE from global CSE.

Local CSE eliminates redundant expressions within a single basic block (using a value/expression table during a single pass). Global CSE works across basic blocks using available-expressions data-flow analysis over the whole CFG.

How is a common subexpression eliminated once detected? Show the transformation.

Replace the first occurrence $t = b + c;\ x = t$ and a later redundant $y = b + c$ with $y = t$. A temporary $t$ holds the value: instead of recomputing $b+c$, reuse $t$ (provided $b, c$ unchanged).

What is the difference between common subexpression elimination and copy propagation?

CSE removes redundant computations of the same expression by reusing a stored result; copy propagation replaces uses of a variable $y$ with $x$ after a copy $y = x$. CSE often introduces temporaries/copies that copy propagation then cleans up.

Why can CSE sometimes increase register pressure or even degrade performance?

Storing a reused value in a temporary keeps it live across the gap between computations, lengthening live ranges and possibly forcing spills. If recomputation is cheaper than holding the value in a register, CSE can be counterproductive.

What role does a Directed Acyclic Graph (DAG) play in local common subexpression elimination?

A DAG representation of a basic block shares identical subexpressions as a single node; when building it, an existing node is reused instead of created, automatically detecting and eliminating local common subexpressions.

What is the difference between syntactic (lexical) and value-based (semantic) common subexpressions?

Syntactic CSE matches expressions textually (same operator and same operand names). Value-based CSE (e.g., value numbering / GVN) matches expressions that compute the same value even if written differently, catching more redundancies.

What is value numbering and how does it support CSE?

Value numbering assigns a unique number to each computed value; expressions that map to the same value number are equivalent. It detects common subexpressions (and constants/copies) by hash-lookup, forming a powerful basis for CSE.

Compare the meet operators and what they imply for available expressions vs. live variables.

Available expressions uses intersection ($\cap$, must/all-paths, forward); live variables uses union ($\cup$, may/some-path, backward). The meet reflects whether a property must hold on all paths or may hold on some path.

Fill the four-way classification: for (Reaching Definitions, Available Expressions, Live Variables, Busy/Anticipated Expressions), give direction and meet.

Reaching Definitions: forward, $\cup$. Available Expressions: forward, $\cap$. Live Variables: backward, $\cup$. Busy (Very Busy/Anticipated) Expressions: backward, $\cap$.

Is available-expressions analysis a 'may' or 'must' analysis, and what does that guarantee for CSE safety?

It is a 'must' analysis (intersection). This guarantees the expression's value is available on every path reaching the point, so reusing the precomputed result is always safe (sound).

In available expressions, block $B$ computes $t = b + c$ and does not redefine $b$ or $c$ afterward. What is $e\_gen[B]$ for this expression?

$e\_gen[B] = \{\,b + c\,\}$, since $b + c$ is evaluated in $B$ and its operands are not killed afterward within $B$.

If an expression $b + c$ is available at a point but $b$ is redefined just before, is $b + c$ still available? Explain.

No. Redefining $b$ kills $b + c$ (it is in $e\_kill$), so the previously computed value is stale. The expression must be recomputed; it is not safe for CSE at that point.

What is the key practical reason all three—constant propagation, liveness, and CSE—are framed as data-flow analyses?

They all compute facts that hold along control-flow paths by solving iterative fixed-point equations over a lattice. The unifying monotone data-flow framework (direction, meet, transfer functions) lets the same iterative algorithm solve each, differing only in lattice, direction, and meet.

Why does liveness analysis converge to a unique fixed point with the iterative algorithm?

Because the transfer functions are monotone over a finite lattice (bounded variable set) and sets only grow (for union/may analysis). Monotonicity plus finite height guarantees termination at the maximum fixed point, which is unique.

Give one example each where constant propagation, liveness, and CSE respectively reduce executed work.

Constant propagation: replaces $r = n \times 1$ with $r = n$ after folding, removing a multiply. Liveness: removes a dead assignment $t = a + b$ whose $t$ is never used. CSE: replaces a second $b + c$ with a stored temporary $t$, removing a redundant addition.