CD Notes
Complete guide to DAGs as intermediate representation covering DAG construction, common subexpression detection, code generation from DAGs, and optimization using DAG representation.
Introduction
A Directed Acyclic Graph (DAG) is a compact representation of expressions within a basic block. Unlike expression trees where common subexpressions result in duplicate subtrees, a DAG shares nodes for identical computations, naturally exposing optimization opportunities. DAGs serve both as an intermediate representation and as an optimization tool.
DAG vs Expression Tree
| Expression | a = b*c + b*c + d |
| Expression Tree (redundant) | DAG (shared): |
| DAG advantage | b*c node shared, revealing CSE automatically. |
DAG Construction Algorithm
| - YES | use existing node (common subexpression!) |
| - NO | create new internal node |
| - Node | (operator, left_child, right_child, attached_identifiers[]) |
| - Hash table: (op, left, right) | node [for CSE detection] |
| - Name table: variable_name | current_node |
| Example | Build DAG for: |
| Step 1 | t1 = a + b |
| Create: [a], [b], [+] | {t1} |
| Hash: (+, a_node, b_node) | plus_node |
| Step 2 | t2 = a + b |
| Look up: (+, a_node, b_node) | EXISTS (plus_node) |
| Attach t2 to same node: [+] | {t1, t2} |
| Step 3 | t3 = t1 * t2 |
| Look up: (*, plus_node, plus_node) | not found, create |
| New: [*] | {t3} with both children = plus_node |
| Step 4 | a = t3 |
| [*] | {t3, a} (a now refers to multiplication result) |
| Step 5 | t4 = a + b |
| Look up: (+, mul_node, b_node) | NOT found (a changed!) |
| Create new [+] | {t4} with children: mul_node and b_node |
| [+] | {t4} |
| [*] | {t3,a} [b₀] |
| [+] | {t1,t2} |
Generating Code from DAGs
| Algorithm | Topological sort of DAG nodes, then generate instruction for each. |
| 2. For shared nodes | compute once, reuse via variable name |
| DAG: [+] | {result} |
| [*] | {t1} [d] |
DAG for Optimization
Optimizations visible in DAG
1. Common Subexpression Elimination: shared nodes
2. Dead code: nodes with no live variable attached and no parent
3. Constant folding: node with constant children → evaluate
Example
a = b + c
d = b + c ← CSE (same node)
e = a + d ← simplifies to a + a = 2*a
f = 5 + 3 ← constant fold to 8
DAG after optimization
[+]→{a,d} [8]→{f} [+]→{e} or [*]→{e}
/ \ / \
[b] [c] [+]→{a,d} [+]→{a,d} → e = a + a
Dead node example
x = a + b ← if x not live at block exit and has no child: DEAD
y = c + d ← y IS live
DAG node for x can be removed if x not used later.
Algebraic Identities in DAG Construction
| Commutativity | a + b = b + a |
| Identity | x + 0 = x, x * 1 = x |
| Associativity | (a + b) + c = a + (b + c) |
DAG-Based Register Allocation Heuristic
| Leaf | label = 1 |
| Unary | label = child_label |
| Binary | if left_label == right_label: label = left_label + 1 |
| else | label = max(left_label, right_label) |
Interview Questions
- Q: How does a DAG differ from an expression tree?
A: An expression tree duplicates nodes for repeated subexpressions (each occurrence is a separate subtree). A DAG shares nodes — if b*c appears twice, only one node exists with multiple parent references. This sharing automatically identifies common subexpressions and reduces storage.
- Q: Why does redefining a variable complicate DAG construction?
A: When variable a is redefined (a = expr), the old leaf node for a no longer represents a's current value. References to the "new a" must point to the expr node, while earlier references used the original leaf. The algorithm detaches the name from the old node and attaches it to the new computation node.
- Q: Can DAGs represent control flow?
A: Standard DAGs represent only straight-line code (one basic block). For control flow, you need a control flow graph where each node is a basic block (possibly with its own DAG). Some extended representations (PDGs — Program Dependence Graphs) combine data and control dependencies.
- Q: How does the order of code generation from a DAG affect register usage?
A: Different topological orderings of the DAG nodes produce different instruction sequences requiring different numbers of registers. The optimal ordering problem is NP-hard for general DAGs but solvable in polynomial time for trees (Ershov labeling). Heuristics choose good orderings in practice.
- Q: What are the limitations of DAG-based optimization?
A: DAGs work within a single basic block only. They cannot capture optimizations across branches, loops, or function calls. Additionally, pointer aliasing and function calls with side effects may prevent node sharing even when expressions look identical syntactically.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Directed Acyclic Graphs (DAGs) in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, intermediate, code, generation, directed
Related Compiler Design Topics