GATE CS & IT Engineering Compiler Design Syllabus

Compiler Design syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Compiler Design in GATE CS & IT Engineering, not a summary of it.

1. 1

   Lexical analysis

   overview

   Examined as a single unit within Compiler Design — no further topic split in the official outline.

2. 2

   Parsing

   overview

   Examined as a single unit within Compiler Design — no further topic split in the official outline.

3. 3

   Syntax-directed translation

   overview

   Examined as a single unit within Compiler Design — no further topic split in the official outline.

4. 4

   Runtime environments

   overview

   Examined as a single unit within Compiler Design — no further topic split in the official outline.

5. 5

   Intermediate code generation

   overview

   Examined as a single unit within Compiler Design — no further topic split in the official outline.

6. 6

   Local optimisation

   overview

   Examined as a single unit within Compiler Design — no further topic split in the official outline.

7. 7

   Data flow analyses

   3 topics

   • Constant propagation
   • Liveness analysis
   • Common sub expression elimination

Compiler Design flashcards for GATE CS & IT Engineering

25 of 50 cards from the Compiler Design deck — real questions with worked answers.

1. What is constant propagation in compiler optimization?

   Constant propagation is a data-flow optimization that replaces variables known to hold a constant value at a given program point with that constant, so the compiler can substitute the literal in place of the variable.

2. What is constant folding, and how does it relate to constant propagation?

   Constant folding evaluates constant expressions at compile time (e.g., $3 \times 4 \to 12$). It works hand-in-hand with constant propagation: propagation supplies constant operands, and folding then computes the result, often enabling further propagation.

3. In the data-flow framework, what kind of analysis is constant propagation (direction and meet)?

   Constant propagation is a forward data-flow analysis. Its lattice meet (confluence) operator combines values from predecessors, mapping conflicting constants to NAC (Not A Constant / $\bot$).

4. What are the three categories of values in the constant-propagation lattice for a single variable?

   $\top$ (UNDEF — not yet known / no information), a specific constant $c$, and $\bot$ (NAC — Not A Constant, meaning the variable may hold different values on different paths).

5. Why is the constant-propagation lattice considered to have infinite height (and a non-distributive framework)?

   Because there are infinitely many possible constants $c$, the per-variable lattice has the chain $\top > c > \bot$ but infinitely many incomparable constant elements. The framework is also non-distributive, so the MOP solution can be more precise than the MFP (iterative) solution.

6. Define the meet rules for combining two constant-propagation values $v_1 \sqcap v_2$.

   $\top \sqcap v = v$; $\bot \sqcap v = \bot$; $c \sqcap c = c$ (same constant); and $c_1 \sqcap c_2 = \bot$ when $c_1 \neq c_2$ (conflicting constants give NAC).

7. At a control-flow merge point, if variable $x$ is $5$ along one path and $7$ along another, what value does constant propagation assign to $x$?

   $\bot$ (NAC). Since the two incoming constants $5 \neq 7$ disagree, $x$ cannot be treated as a constant after the merge.

8. Why is constant propagation undecidable in the fully general (exact) case?

   Determining whether a variable always holds a particular constant at a point can depend on whether certain branches are ever taken, which reduces to undecidable problems (e.g., the halting problem). Compilers therefore compute a safe, conservative approximation.

9. What is the difference between the MOP and MFP solutions for constant propagation, and which is computed in practice?

   MOP (Meet Over all Paths) is the ideal solution meeting data-flow values over every path; MFP (Maximum Fixed Point) is what the iterative algorithm computes. Because constant propagation is non-distributive, $\text{MFP} \leq \text{MOP}$ (MFP is conservative/less precise). Compilers compute MFP.

10. Give the constant-propagation transfer function for an assignment $x = y + z$.

    If $y = c_1$ and $z = c_2$ are both constants, then $x = c_1 + c_2$ (folded). If either operand is $\bot$ (NAC), then $x = \bot$. If an operand is $\top$, $x$ remains $\top$ until that operand is resolved.

11. What is conditional constant propagation (sparse conditional constant propagation, SCCP)?

    SCCP combines constant propagation with dead-code/unreachable-branch detection: it propagates constants while simultaneously discovering which branches are unreachable (because the condition folds to a constant), making it strictly more powerful than doing the two optimizations separately.

12. In SSA form, why is constant propagation easier and more precise?

    In SSA each variable has exactly one definition, so the constant value of a variable is unambiguous; $\phi$-functions cleanly express merges. This enables efficient sparse algorithms like Wegman–Zadeck SCCP that work on def-use chains rather than re-iterating over all program points.

13. What optimization opportunities does constant propagation typically enable downstream?

    It enables constant folding, dead-code elimination (branches with constant conditions), strength reduction, algebraic simplification, and unreachable-code removal, often cascading to expose further constants.

14. After $a = 5$, the statement $b = a + 3$ is encountered. What does constant propagation (with folding) produce for $b$?

    It substitutes $a = 5$ to get $b = 5 + 3$, then folds to $b = 8$.

15. What is liveness analysis (live-variable analysis)?

    Liveness analysis is a data-flow analysis that determines, for each program point, the set of variables that are live — i.e., that hold a value which may be used along some path before being redefined.

16. Formally, when is a variable said to be live at a program point?

    A variable $x$ is live at point $p$ if there exists a path from $p$ to a use of $x$ that contains no redefinition of $x$ between $p$ and that use. Otherwise $x$ is dead at $p$.

17. What is the direction and meet operator of liveness analysis?

    Liveness is a backward data-flow analysis (information flows from uses back toward definitions), and its meet/confluence operator is set union ($\cup$).

18. State the data-flow equations for liveness analysis.

    $$IN[B] = use[B] \cup (OUT[B] - def[B])$$ $$OUT[B] = \bigcup_{S \in succ(B)} IN[S]$$ with the boundary condition $OUT[\text{EXIT}] = \varnothing$.

19. In liveness analysis, what do $use[B]$ and $def[B]$ (gen and kill) represent for a basic block $B$?

    $use[B]$ (gen) is the set of variables used in $B$ before any redefinition within $B$; $def[B]$ (kill) is the set of variables assigned (defined) in $B$ before any use of them in $B$.

20. What is the initialization and boundary condition for the iterative liveness algorithm?

    Initialize $IN[B] = OUT[B] = \varnothing$ for all blocks, and set the boundary $OUT[\text{EXIT}] = \varnothing$. Then iterate the backward equations until no set changes (fixed point).

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

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

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

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

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

See more Compiler Design flashcards →

Planning Compiler Design for GATE CS & IT Engineering

Compiler Design (GATE CS & IT Engineering) FAQ