⏱️
15 questions · 22 marks · 45 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT.
Q1NAT2 marksDAG
How many nodes does the DAG of (a * b + c) * (a * b + c) - a * b have?
Numerical answer: ________
Q2NAT1 markDAG
How many nodes does the DAG of (x + y) * (x + y) + (x + y) have?
Numerical answer: ________
Q3MCQ1 markBlock DAG
In the block a = b + c; b = a − d; c = b + c; d = a − d, the DAG has:
- (A) 4 nodes
- (B) 6 nodes
- (C) 8 nodes
- (D) 10 nodes
Q4MCQ1 markTriples
Which representation makes reordering instructions easiest?
- (A) triples
- (B) indirect triples
- (C) syntax trees
- (D) postfix
Q5NAT1 markTAC
How many temporaries (no sharing, last op directly into x) for x = (a + b) * (c − d) + e?
Numerical answer: ________
Q6NAT2 marksAddress
char C[0..9][0..15] (1 byte) row-major from 3000. Address of C[7][9]?
Numerical answer: ________
Q7NAT2 marksAddress
Same array column-major. Address of C[7][9]?
Numerical answer: ________
Q8MCQ1 markShort-circuit
With short-circuit evaluation of p && f(), f is called:
- (A) always
- (B) only if p is true
- (C) only if p is false
- (D) never
Q9NAT2 marksBackpatching
Backpatching a < b || c < d && e < f from 100: how many instructions are on the final truelist and falselist together?
Numerical answer: ________
Q10NAT2 marksSSA
How many distinct names in the SSA form of x = a + b; y = x * c; x = y − a; y = x + y; z = x * y?
Numerical answer: ________
Q11MCQ1 markφ
φ-functions appear in SSA at:
- (A) every assignment
- (B) join points of control flow
- (C) function calls
- (D) array accesses
Q12NAT1 markBlocks
How many basic blocks: 1 x = 0; 2 if x > 5 goto 5; 3 x = x + 1; 4 goto 2; 5 y = x?
Numerical answer: ________
Q13NAT2 marksEdges
For the same code, how many flow-graph edges?
Numerical answer: ________
Q14MSQ2 marksLeaders
Which are leaders by definition?
- (A) the first instruction
- (B) a jump target
- (C) the instruction after a conditional jump
- (D) the last instruction of the program
Q15MCQ1 markCFG
In “find which values are still needed later, on the CFG of each function”, CFG means:
- (A) context-free grammar
- (B) control flow graph
- (C) compiler front end
- (D) canonical form grammar
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 72 marks
3 leaves + 4 operators = 7.
Re-read: Lesson 4.1 — Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG
Q2 Answer: 51 mark
5.
Re-read: Lesson 4.1 — Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG
Q3 Answer: (B)1 mark
b₀, c₀, d₀, +, −, + (d shares the − node with b).
- (A) is wrong: Too few.
- (C) is wrong: d = a − d is shared.
- (D) is wrong: Too many.
Re-read: Lesson 4.1 — Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG
Q4 Answer: (B)1 mark
Only the pointer list changes.
- (A) is wrong: References break.
- (C) is wrong: Not a linear code.
- (D) is wrong: Not a code representation for optimization.
Re-read: Lesson 4.2.1 — Three-address code instruction forms; quadruples, triples, indirect triples
Q5 Answer: 31 mark
3.
Re-read: Lesson 4.2.1 — Three-address code instruction forms; quadruples, triples, indirect triples
Q6 Answer: 31212 marks
3000 + 7 × 16 + 9 = 3121.
Re-read: Lesson 4.2.2 — TAC for expressions and array accesses (address calculation)
Q7 Answer: 30972 marks
3000 + 9 × 10 + 7 = 3097.
Re-read: Lesson 4.2.2 — TAC for expressions and array accesses (address calculation)
Q8 Answer: (B)1 mark
If p is false, the && is already false.
- (A) is wrong: Not when p is false.
- (C) is wrong: Reversed.
- (D) is wrong: When p is true it is called.
Re-read: Lesson 4.2.3 — TAC for if/while and Boolean expressions (short-circuit; backpatching brief)
Q9 Answer: 42 marks
Truelist { 100, 104 }, falselist { 103, 105 } → 4.
Re-read: Lesson 4.2.3 — TAC for if/while and Boolean expressions (short-circuit; backpatching brief)
Q10 Answer: 82 marks
5 versions + a, b, c = 8.
Re-read: Lesson 4.3 — Static single assignment (SSA) form; counting variables and temporaries
Q11 Answer: (B)1 mark
They merge versions from different paths.
- (A) is wrong: No.
- (C) is wrong: No.
- (D) is wrong: No.
Re-read: Lesson 4.3 — Static single assignment (SSA) form; counting variables and temporaries
Q12 Answer: 41 mark
Leaders 1, 2, 3, 5 → 4.
Re-read: Lesson 4.4 — Basic blocks: leader rules and partitioning; control flow graphs (the second meaning of “CFG”); counting blocks and edges
Q13 Answer: 42 marks
B1→B2, B2→B3, B2→B4 (goto 5), B3→B2: 4.
Re-read: Lesson 4.4 — Basic blocks: leader rules and partitioning; control flow graphs (the second meaning of “CFG”); counting blocks and edges
Q14 Answer: (A) (B) (C)2 marks
The last instruction is a leader only if one of the rules applies.
Re-read: Lesson 4.4 — Basic blocks: leader rules and partitioning; control flow graphs (the second meaning of “CFG”); counting blocks and edges
Q15 Answer: (B)1 mark
Data about program points lives on the flow graph.
- (A) is wrong: Grammars do not have program points.
- (C) is wrong: No.
- (D) is wrong: No.
Re-read: Lesson 4.4 — Basic blocks: leader rules and partitioning; control flow graphs (the second meaning of “CFG”); counting blocks and edges
Wrong on Q → re-read
| Question | Topic | Re-read |
|---|---|---|
| Q1 | DAG | Lesson 4.1 |
| Q2 | DAG | Lesson 4.1 |
| Q3 | Block DAG | Lesson 4.1 |
| Q4 | Triples | Lesson 4.2.1 |
| Q5 | TAC | Lesson 4.2.1 |
| Q6 | Address | Lesson 4.2.2 |
| Q7 | Address | Lesson 4.2.2 |
| Q8 | Short-circuit | Lesson 4.2.3 |
| Q9 | Backpatching | Lesson 4.2.3 |
| Q10 | SSA | Lesson 4.3 |
| Q11 | φ | Lesson 4.3 |
| Q12 | Blocks | Lesson 4.4 |
| Q13 | Edges | Lesson 4.4 |
| Q14 | Leaders | Lesson 4.4 |
| Q15 | CFG | Lesson 4.4 |