7.2 Syntax Trees, Directed Acyclic Graphs & Value Numbering

Back to DBMS Notes

📚Module 01Syntax Trees, Directed Acyclic Graphs & Value Numbering⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Shared Blueprint Deduplication Station

Imagine an architect drawing building plans for a 50-story commercial skyscraper:

• Parse Tree: A massive, legalistic municipal contract documenting every single grammatical rule used to describe the building (including commas, punctuation, and structural boilerplate).
• Abstract Syntax Tree (AST): A clean architectural blueprint showing only the actual physical walls, beams, and windows. However, if all 50 floors use identical bathroom plumbing, the AST draws 50 separate, duplicate copies of that plumbing schematic.
• Directed Acyclic Graph (DAG): The master engineer notices the redundancy and draws the bathroom plumbing schematic exactly once in a shared blueprint box. All 50 floors simply draw an arrow pointing to that single, shared plumbing box.
• Value Numbering: The inventory manager stamps that plumbing assembly with ID #42. Whenever any worker asks to construct that exact plumbing assembly, the manager says: "That is already component #42. Do not build it again; reuse the existing unit!"

💻 Bridging to Computer Science: Value Numbering & Common Subexpression Elimination

In intermediate code optimization, compilers convert expression trees into Directed Acyclic Graphs (DAGs):

• In an AST, every subexpression forms an independent tree node, causing identical subexpressions (e.g. $a + b$) to be duplicated in memory.
• In a DAG, nodes representing identical computations are deduplicated and shared: internal nodes can have multiple parent edges (in-degree $\ge 1$).
• Value Numbering is the linear-time algorithm that maintains a hash table of (op, left_child, right_child) tuples, mapping identical computations to a single canonical node ID.

📑Table of Contents

• 🏗️ Architectural Foundations: Parse Tree vs AST vs DAG
• 📐 Formal Foundations: DAG Construction & Node Invariants
  • 🏗️ The DAG Construction Algorithm (Hash Table Value Numbering)
• 🧱 DAG Construction for a Basic Block
  • 🎯 What a Basic Block DAG Reveals:
• 🏭 Real-World Production Context: How Industry Builds This
• 📐 Numerical Applications & Worked Examples
  • Example 1: Step-by-Step Basic Block DAG Construction
  • Example 2: Minimal DAG for a Compound Arithmetic Expression
• 🎯 Exam & Interview Pitfall Check

---

🏗️ Architectural Foundations: Parse Tree vs AST vs DAG

Parse Tree vs Syntax Tree (AST) vs Directed Acyclic Graph (DAG)

The progressive compression of syntactic representation into canonical computation graph

Syntax Tree (AST)

Abstract Syntax Tree (AST)

🌳

Dominant Architecture / DomainFrontend Parsing, Semantic Analysis

• •Interior nodes are operators; leaves are operands.
• •Stripped of grammatical non-terminals and syntactic punctuation.
• •Every subexpression appears as an independent, isolated subtree.
• •Duplicate computations like (a + b) appear multiple times.

"Faithfully mirrors expression syntax without memory deduplication."

DAG

Directed Acyclic Graph (DAG)

🕸️

Dominant Architecture / DomainIntermediate Code Optimization, ICG, GVN

• •Identical common subexpressions are shared with multiple parent edges.
• •Interior nodes have in-degree >= 1 (multiple parents).
• •Automatically exposes dead code and redundant memory loads.
• •Forms the theoretical foundation for local code generation.

"Canonical deduplication: identical computations merge into single nodes."

---

📐 Formal Foundations: DAG Construction & Node Invariants

A Directed Acyclic Graph (DAG) for an expression is a directed graph with no directed cycles such that:

1. Leaves: Represent unique variable names or literal constants.
2. Interior Nodes: Represent operator applications.
3. Sharing: A node $N$ has multiple parent edges if the subexpression rooted at $N$ is used as an operand in multiple operations.

🏗️ The DAG Construction Algorithm (Hash Table Value Numbering)

To construct a DAG in linear time $O(N)$, the compiler maintains a hash table of existing nodes:

Architecture Flow

The Value-Numbered DAG Construction Pipeline

Checking existing computation nodes before allocating new records

🔍Lookup

Query Node Hash Table

Hash signature: key = (op, left_child_id, right_child_id).

→

Exists?

⚖️Decision

Deduplication Branch

If found: return existing node ID. If absent: allocate new node record.

→

Insert

🏷️Attachment

Update Variable Association

Attach destination variable label to the resulting node ID.

Formal Algorithm: MakeNode(op, left, right)

1. Compute hash key $k = \text{hash}(op, left, right)$.
2. If an entry $(op, left, right)$ exists in the node table:
   • Return pointer to existing node $p$.
3. Else:
   • Create a new node $N$ with operator $op$, left pointer $left$, and right pointer $right$.
   • Insert $N$ into the hash table under key $k$.
   • Return $N$.

---

🧱 DAG Construction for a Basic Block

In a basic block, variables can be assigned multiple times. When variable $x$ is updated ($x = y + z$):

1. The compiler evaluates the right-hand side using current node pointers for $y$ and $z$.
2. It obtains node $p = \text{MakeNode}(+, \text{node}(y), \text{node}(z))$.
3. It attaches label $x$ to node $p$.
4. Crucial Rule: The label $x$ is removed from any previous node it was attached to, because that old value is now killed!

Basic Block DAG Construction Trace: Handling Variable Reassignment

Tracing node creation, operator evaluation, and label killing when variable 'a' is reassigned

Input Leaves

Node Allocator

Value Table

Variable Map

1

Input Leaves→Node Allocator

Initial Leaf Registration

2

Node Allocator→Value Table

Statement 1: a = b + c

3

Value Table→Variable Map

Statement 2: a = a * d (Kills Old 'a')

4

Variable Map→Value Table

Label Migration & Historical Preservation

🎯 What a Basic Block DAG Reveals:

1. Common Subexpressions: Any internal node with in-degree $> 1$ represents a subexpression computed once and reused multiple times.
2. Dead Code Elimination: Any internal node that has no parents and whose attached variable labels are not live at the exit of the basic block can be safely eliminated.
3. Variables Used Before Definition: Any leaf node labeled with an initial variable name represents an input variable whose value originated outside the basic block.

---

🏭 Real-World Production Context: How Industry Builds This

In industrial production compilers (such as LLVM and GCC):

Production compilers expand basic block DAG construction into function-wide optimization:

• Global Value Numbering (GVN) operates directly over SSA form and dominator trees.
• Because each SSA variable is assigned exactly once, value numbers are globally valid across all basic blocks dominated by the definition.
• LLVM's GVNPass detects common subexpressions across control branches, eliminates redundant heap loads, and hoists loop-invariant expressions.

Compilers for functional languages (OCaml, Haskell) use hash-consing to guarantee that structurally identical syntax subtrees share the exact same physical heap address, slashing compiler memory footprints from gigabytes to megabytes.

---

📐 Numerical Applications & Worked Examples

Example 1: Step-by-Step Basic Block DAG Construction

Construct the minimal DAG for the following sequence of three-address statements in a basic block:

$$\begin{aligned} (1) \quad t_1 &= a + b \\ (2) \quad t_2 &= a - b \\ (3) \quad t_3 &= t_1 \times t_2 \\ (4) \quad t_4 &= a + b \\ (5) \quad t_5 &= t_3 + t_4 \\ (6) \quad a &= t_5 \\ (7) \quad t_6 &= a + b \end{aligned}$$

Determine:

1. Total number of nodes (leaves + internal operators) in the final DAG.
2. Total number of directed edges.
3. The optimized three-address code reconstructed from the DAG.

Step-by-Step Construction:

• Statement 1: $t_1 = a + b$
  • Allocate leaf nodes: $n_1 = a_0$, $n_2 = b$.
  • Internal operator: $n_3 = (+, n_1, n_2)$. Attach label: $\{t_1\}$.
• Statement 2: $t_2 = a - b$
  • Internal operator: $n_4 = (-, n_1, n_2)$. Attach label: $\{t_2\}$.
• Statement 3: $t_3 = t_1 \times t_2$
  • Internal operator: $n_5 = (\times, n_3, n_4)$. Attach label: $\{t_3\}$.
• Statement 4: $t_4 = a + b$
  • Query table for $(+, n_1, n_2)$. Found existing node $n_3$!
  • Attach label: $\{t_1, t_4\}$ to node $n_3$. (Common Subexpression eliminated!)
• Statement 5: $t_5 = t_3 + t_4$
  • Operands: $n_5$ ($t_3$) and $n_3$ ($t_4$).
  • Internal operator: $n_6 = (+, n_5, n_3)$. Attach label: $\{t_5\}$.
• Statement 6: $a = t_5$
  • Attach label $a$ to node $n_6$.
  • ⚠️ Killed Variable: Variable $a$ now points to node $n_6$. Leaf $n_1$ remains as $a_0$ (initial value of $a$).
• Statement 7: $t_6 = a + b$
  • Operands: Current node for $a$ is $n_6$. Current node for $b$ is $n_2$.
  • Signature: $(+, n_6, n_2)$.
  • This is a new distinct operation ($n_6$ is not the old $a_0$).
  • Allocate internal operator: $n_7 = (+, n_6, n_2)$. Attach label: $\{t_6\}$.

Final DAG Node & Edge Counts:

• Leaf Nodes (2):
  1. $n_1 = a_0$ (initial value of $a$)
  2. $n_2 = b$
• Internal Operator Nodes (5): 3. $n_3 = (+, n_1, n_2)$ with labels $\{t_1, t_4\}$ 4. $n_4 = (-, n_1, n_2)$ with label $\{t_2\}$ 5. $n_5 = (\times, n_3, n_4)$ with label $\{t_3\}$ 6. $n_6 = (+, n_5, n_3)$ with labels $\{t_5, a\}$ 7. $n_7 = (+, n_6, n_2)$ with label $\{t_6\}$
• Total Nodes: $2 \text{ leaves} + 5 \text{ operators} = 7 \text{ nodes}$.
• Directed Edges (10):
  • $n_3 \to n_1, n_2$ (2 edges)
  • $n_4 \to n_1, n_2$ (2 edges)
  • $n_5 \to n_3, n_4$ (2 edges)
  • $n_6 \to n_5, n_3$ (2 edges)
  • $n_7 \to n_6, n_2$ (2 edges)
  • Total = $2 + 2 + 2 + 2 + 2 = 10 \text{ edges}$.

Reconstructed Optimized Three-Address Code:

$$\begin{aligned} t_1 &= a + b && (\text{Evaluates both } t_1 \text{ and } t_4) \\ t_2 &= a - b \\ t_3 &= t_1 \times t_2 \\ a &= t_3 + t_1 \\ t_6 &= a + b \end{aligned}$$

Original instructions: 7. Optimized instructions: 5. Redundant instructions eradicated: 2.

---

Example 2: Minimal DAG for a Compound Arithmetic Expression

Find the minimum number of nodes and edges in the DAG for the arithmetic expression:

$$E = (a + b \times c) \times (a + b \times c) + (b \times c)$$

Step-by-Step Analytical Derivation:

1. Identify Subexpressions:
   • $S_1 = b \times c$
   • $S_2 = a + S_1 = a + b \times c$
   • $S_3 = S_2 \times S_2 = (a + b \times c) \times (a + b \times c)$
   • $S_4 = S_3 + S_1 = S_3 + (b \times c)$
2. Graph Construction:
   • Leaf nodes: $a, b, c$ (3 leaf nodes).
   • Node 4: $(\times, b, c)$ [Computes $S_1$]
   • Node 5: $(+, a, \text{Node 4})$ [Computes $S_2$]
   • Node 6: $(\times, \text{Node 5}, \text{Node 5})$ [Computes $S_3$, both children point to Node 5!]
   • Node 7: $(+, \text{Node 6}, \text{Node 4})$ [Computes $S_4$, reuses Node 4!]
3. Counts:
   • Total Nodes: $3 \text{ leaves} + 4 \text{ operators} = 7 \text{ nodes}$.
   • Total Edges:
     • Node 4: 2 edges (to $b, c$)
     • Node 5: 2 edges (to $a$, Node 4)
     • Node 6: 2 edges (both to Node 5)
     • Node 7: 2 edges (to Node 6, Node 4)
     • Total edges = $2 + 2 + 2 + 2 = 8 \text{ edges}$.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "How does a compiler know if an expression in a DAG is a common subexpression?"
Key Focus Points:

• An internal node in a DAG represents a common subexpression if and only if its in-degree is greater than 1 (it has two or more incoming parent edges).
• This indicates that the value computed by this node is consumed as an input by multiple downstream operations.

Question 2: "What happens when a variable on the left-hand side of an assignment is reassigned in the same basic block?"
Key Focus Points:

• Its variable label is migrated to the new computation node.
• It is removed from the previous node. Any subsequent operations referencing that variable will link to the new node, while existing parent edges continue to point to the historical node.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Assuming commutative operations match automatically in a value numbering table.
Answer: Implementation pitfall. In a naive hash table, key $(+, a, b)$ does not equal key $(+, b, a)$. Production compilers canonicalize commutative operator operands (e.g. enforcing $\text{ID}(left) \le \text{ID}(right)$) before querying the value table.

Trap 2: Ignoring memory aliasing when optimizing array loads in a DAG.
Answer: Silent corruption danger. If an array store $a[j] = x$ occurs between two loads $t_1 = a[i]$ and $t_2 = a[i]$, the compiler CANNOT eliminate the second load unless alias analysis proves $i \neq j$. If $i == j$, the store mutates the value, invalidating the previous load node.

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic7.1 Intermediate Representations, Three-Address Code, Quadruples & TriplesNext Topic →7.3 Control Flow Translation, Boolean Expressions & Backpatching