Intermediate Code Generation Notes & Formulas

1. Why ICG?

Provides a machine-independent representation. Allows portable optimizations.

• Connects the Front-End and Back-End.

2. Directed Acyclic Graphs (DAG)

• Similar to a tree, but shares identical sub-expressions.
• Used for identifying common sub-expressions and local optimization.

3. Three Address Code (TAC)

• General Form: $x = y op z$ (Max 3 addresses).
• Representations:
  1. Quadruples: (op, arg1, arg2, result). Uses temp names in result.
  2. Triples: (op, arg1, arg2). Refers to results by their position (index).
  3. Indirect Triples: Pointer to a triple table. Easier for code movement.

4. Postfix Notation

• Operator follows operands (e.g., $a b +$).
• Stack-based evaluation.

5. GATE formulas

• Number of nodes in a DAG for an expression: (Unique operands + Unique operators).
• Translation of control flow (if-else, while) into boolean TAC via backpatching.