ACompressed recap
🧾
An IR separates front and back ends and is where machine-independent optimization happens. A DAG is a syntax tree that shares identical subexpressions; it is built bottom-up by value numbering (reuse an existing node with the same operator and children). For a block of assignments, variables are labels that move to the newest node. Count nodes as distinct leaves plus distinct operator applications; edges as 2 per binary operator.
BMerged rule card
4.1 Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG
- IR: between front end and back end; retargeting (m + n) and machine-independent optimization.
- DAG = syntax tree with identical subexpressions shared.
- Value numbering: reuse node (op, left, right) if it already exists.
- Block DAG: labels move to the newest node of each variable; initial values are leaves x₀.
- Nodes = distinct leaves + distinct operator applications; edges = 2 per binary node.
CInterleaved GATE-style questions
Q1NAT2 marksDAG nodes
How many nodes does the DAG of a + a * (b - c) + (b - c) * d have?
Numerical answer: ________
Q2NAT1 markTree nodes
How many nodes does the syntax tree of a + a * (b - c) + (b - c) * d have?
Numerical answer: ________
Q3NAT2 marksBlock DAG
How many nodes does the DAG of t1 = 4 * i; t2 = a[t1]; t3 = 4 * i; t4 = b[t3]; t5 = t2 * t4 have? (Treat x[y] as a binary node with children x and y.)
Numerical answer: ________
Q4MCQ1 markSharing
In the DAG of a * b + b * a without using commutativity, the products a * b and b * a are:
- (A) one shared node
- (B) two different nodes
- (C) leaves
- (D) removed
Q5MCQ1 markBlock
In the block a = b + c; b = a − d; c = b + c; d = a − d, which variables label the same node?
- (A) a and c
- (B) b and d
- (C) a and d
- (D) c and d
Q6MSQ1 markIR
Which are intermediate representations?
- (A) syntax tree
- (B) DAG
- (C) token list
- (D) one-operation-per-line code
Q7NAT1 markEdges
How many edges does the DAG of (a * b + c) * (a * b + c) - a * b have?
Numerical answer: ________
Q8MCQ2 marksConstruction
Building a DAG by value numbering, before creating a node (op, l, r) the compiler:
- (A) checks whether a node with the same op and children exists
- (B) always creates a new node
- (C) deletes the children
- (D) reorders operands
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 92 marks
4 leaves + 5 operators = 9.
Re-read: Lesson 4.1 — Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG
Q2 Answer: 131 mark
Every occurrence counts: 7 leaves + 6 operators = 13.
Re-read: Lesson 4.1 — Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG
Q3 Answer: 82 marks
Leaves 4, i, a, b; nodes 4*i (labels t1, t3), a[·], b[·], and the product: 8.
Re-read: Lesson 4.1 — Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG
Q4 Answer: (B)1 mark
Different operand order means a different key.
- (A) is wrong: Only with a commutativity rule.
- (C) is wrong: They are operator nodes.
- (D) is wrong: Nothing is removed.
Re-read: Lesson 4.1 — Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG
Q5 Answer: (B)1 mark
d = a − d₀ recomputes b’s value.
- (A) is wrong: c = b + c₀ uses the new b.
- (C) is wrong: Different operators.
- (D) is wrong: Different values.
Re-read: Lesson 4.1 — Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG
Q6 Answer: (A) (B) (D)1 mark
Tokens are the lexer’s output, before structure is known.
Re-read: Lesson 4.1 — Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG
Q7 Answer: 81 mark
4 binary operators × 2 = 8.
Re-read: Lesson 4.1 — Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG
Q8 Answer: (A)2 marks
That lookup is what shares subexpressions.
- (B) is wrong: That builds a tree.
- (C) is wrong: Children are kept.
- (D) is wrong: Order is part of the key.
Re-read: Lesson 4.1 — Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG