ACompressed recap
🧾
An expression is available at a point if every path computes it and none of its operands changes afterwards. The analysis is forward with intersection; e_gen holds expressions computed and not killed later in the block, e_kill expressions whose operands the block assigns; non-entry blocks start with all expressions. Available expressions drive global common-subexpression elimination through temporaries.
BMerged rule card
6.5 Global common-subexpression elimination via available expressions
- x op y available at p: computed on every path to p, operands unchanged since.
- e_gen: computed in B, operands not redefined later in B. e_kill: expressions using a variable B defines.
- Forward, ∩: IN = ∩ OUT[preds]; OUT = e_gen ∪ (IN − e_kill); IN[entry] = ∅; other OUT start = U.
- Global CSE: save earlier results in a temporary; replace the later computation by a copy.
CInterleaved GATE-style questions
Q1NAT1 markAvailable
In the B1–B4 example of Lesson 6.5 (a = b + c; d = a − e …), how many expressions are available at the start of B3?
Numerical answer: ________
Q2MCQ1 markDirection
Available expressions analysis is:
- (A) forward, must
- (B) backward, may
- (C) forward, may
- (D) backward, must
Q3MCQ1 markInitialisation
Why are non-entry OUT sets initialised to the universal set?
- (A) to allow the intersection to shrink to the largest correct solution
- (B) to make every expression available forever
- (C) because the meet is union
- (D) to speed up liveness
Q4MCQ2 marksgen
For the block a = b + c; b = a − d; e = b + c, e_gen contains:
- (A) b + c and a − d
- (B) a − d only
- (C) b + c only
- (D) nothing
Q5MSQ2 marksElimination
In the GATE example (B3 sets c = 7), which statements in B4 can reuse earlier results?
- (A) t = a * b
- (B) w = a + c
- (C) both
- (D) neither
Q6MCQ1 markLocal vs global
Common subexpressions inside a single block are usually found with:
- (A) the block DAG
- (B) available expressions only
- (C) liveness
- (D) constant propagation
Q7NAT1 markAvailable
In the self-loop example (B1: t = x * y; B2: u = x * y, x = 1; B3: v = x * y), how many expressions are available at the start of B3?
Numerical answer: ________
Q8MCQ1 markTemporary
Global CSE of z = x + y (available from earlier computations) is implemented by:
- (A) deleting z
- (B) storing earlier results in a temporary t and setting z = t
- (C) moving z to the entry
- (D) recomputing x + y
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 21 mark
IN[B3] = { a - e, b + c } → 2.
Re-read: Lesson 6.5 — Global common-subexpression elimination via available expressions
Q2 Answer: (A)1 mark
Forward with intersection.
- (B) is wrong: That is liveness.
- (C) is wrong: That is reaching definitions.
- (D) is wrong: No.
Re-read: Lesson 6.5 — Global common-subexpression elimination via available expressions
Q3 Answer: (A)1 mark
Starting with ∅ would lose expressions around loops.
- (B) is wrong: They shrink as kills are found.
- (C) is wrong: The meet is intersection.
- (D) is wrong: Unrelated.
Re-read: Lesson 6.5 — Global common-subexpression elimination via available expressions
Q4 Answer: (A)2 marks
The first b + c is killed by b = a − d, but the final b + c is computed after that and survives; a − d survives because a and d are not assigned after it. Computed: { a - d, b + c }.
- (B) is wrong: b + c is recomputed at the end.
- (C) is wrong: a − d is not killed: a and d do not change after it.
- (D) is wrong: Both survive.
Re-read: Lesson 6.5 — Global common-subexpression elimination via available expressions
Q5 Answer: (A)2 marks
Only a * b is available.
Re-read: Lesson 6.5 — Global common-subexpression elimination via available expressions
Q6 Answer: (A)1 mark
Value numbering on the block DAG.
- (B) is wrong: That is the global method.
- (C) is wrong: No.
- (D) is wrong: No.
Re-read: Lesson 6.5 — Global common-subexpression elimination via available expressions
Q7 Answer: 01 mark
x is redefined in B2: 0.
Re-read: Lesson 6.5 — Global common-subexpression elimination via available expressions
Q8 Answer: (B)1 mark
The value must be carried to the later use.
- (A) is wrong: z is still needed.
- (C) is wrong: No.
- (D) is wrong: That is what CSE avoids.
Re-read: Lesson 6.5 — Global common-subexpression elimination via available expressions