Global common-subexpression elimination via available expressions

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• Is liveness a forward or a backward problem, and what is its meet? from Lesson 6.4
• What are gen[B] and kill[B] for reaching definitions? from Lesson 6.2
• How does the block DAG find a local common subexpression? from Lesson 4.1

1 · The Story

📖

Already worked out?

Inside one chapter, Ishaan already reuses repeated phrases. Across chapters it is harder. Chapter 3 says “sales plus tax”. Was that total already worked out earlier on every route into chapter 3, with sales and tax unchanged since? If yes, chapter 3 can reuse it. If even one route reaches chapter 3 without computing it, or after changing sales, it must be worked out again.

So this time, where routes join, a total counts only if it is known on all of them.

2 · Predict First

🤔

B1 computes b + c and a − e and branches to B2 and B3. B2 computes b + c again and then changes b; B3 does nothing to b, c, a, e. Both go to B4, which computes b + c. Is b + c available at B4? Write your guess down. The answer is in the vault.

3 · Core Concept

Available expressions

An expression x op y is available at point p if every path from the entry to p evaluates x op y, and after the last such evaluation on each path, neither x nor y is redefined. If x op y is available at a use, that use can reuse the earlier result instead of recomputing it.

gen and kill

• e_gen[B]: expressions computed in B whose operands are not redefined later in B.
• e_kill[B]: all expressions in the program that use a variable defined in B (and are not regenerated after that definition in B).

Example: in the block e = b + c; b = d * 2, the expression b + c is computed, but b is then redefined, so b + c is killed, not generated.

Equations (forward, intersection)

OUT[B] = e_gen[B] ∪ (IN[B] − e_kill[B])
IN[B]  = ∩ over predecessors P of OUT[P]
IN[ENTRY block] = ∅; all other OUT start as the universal set U of expressions

Intersection, because the expression must have been computed on all paths. Starting with U lets the intersection shrink to the largest correct answer.

Eliminating global common subexpressions

For a statement z = x op y in B where x op y is available at that point: find the evaluations of x op y that reach it (going backwards along all paths), store their result in a new temporary t (t = x op y; w = t), and replace the statement by z = t. Copy propagation can then clean up.

Local vs global

Local CSE (block DAG, Lesson 6.1) handles repeats inside one block; available expressions extend it across blocks, including around loops.

Story → compiler term

4 · Visual

Available expressions, computed. At B3 both b + c and a − e are available; at B4 nothing is, because the path through B2 kills both.

5 · Worked Examples

Example 1 Easy

Compute e_gen and e_kill for each block above.

Solution

B1 (a = b + c; d = a − e): gen = { b + c, a − e } (a is redefined by the first statement before a − e is computed, so a − e survives). B2 (e = b + c; b = d * 2): gen = { d * 2 }; it defines e and b, so it kills a − e and b + c. B3 (f = b + c; g = a − e): gen = { b + c, a − e }, kills nothing. B4: gen = { b + c }.

Example 2 Medium

Which expressions are available at the start of B3 and B4, and what can be eliminated?

Solution

IN[B3] = OUT[B1] = { a - e, b + c }: both f = b + c and g = a − e in B3 can reuse B1’s results (store them in temporaries in B1: t1 = b + c; a = t1; t2 = a − e; d = t2; then f = t1; g = t2). IN[B4] = OUT[B2] ∩ OUT[B3] = ∅: h = b + c must be recomputed.

Example 3 GATE

B1: p = a * b, q = a + c; B2: r = a * b; B3: c = 7, s = a * b; B2 and B3 both go to B4: t = a * b, w = a + c. Which of B4’s expressions can be eliminated?

Solution

a * b: computed on both paths with a, b unchanged → available at B4: IN[B4] = { a * b }, so t = a * b reuses it. a + c: killed in B3 (c = 7), so w = a + c must be recomputed.

6 · Shortcuts

⚡

Available at B ⇔ computed on every incoming path and not killed afterwards. Check each path separately, then intersect. Valid when: small flow graphs in exam questions.

⚡

Kill = assignment to any operand after (or without) the computation in the block. Valid when: computing e_kill quickly.

7 · GATE Traps

⚠️

• Meet is intersection: one path without the expression makes it unavailable.
• Non-entry blocks start with OUT = U, not ∅ (otherwise loops lose everything).
• An expression computed and then having an operand redefined in the same block is killed, not generated.
• Available expressions look backward in time but the analysis runs forward.
• Global CSE needs a temporary to carry the value to the later use.

8 · Memory Hook

🧠

Available = computed on all roads, untouched since. Forward, intersect.

9 · Connect the Dots

The last lesson of the phase looks at loops, where a program spends most of its time: moving work that does not change out of the loop, and simplifying variables that step by a fixed amount.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markMeet

Available-expressions analysis uses which meet?

• (A) union
• (B) intersection
• (C) difference
• (D) none

Q2MCQ1 markKill

In the block x = y + z; y = 4, the expression y + z is:

• (A) generated
• (B) killed
• (C) both generated and available at the end
• (D) unaffected

Q3MCQ2 marksAvailability

B1: t = x * y → B2 (self-loop): u = x * y, x = 1 → B3: v = x * y (edges B1→B2, B2→B2, B2→B3). Is x * y available at the start of B2?

• (A) yes
• (B) no, because the back edge brings OUT[B2], where x * y is killed
• (C) only on the first iteration
• (D) yes, because B1 computes it

Q4NAT1 markCount

In the B1–B4 graph of the GATE example (p = a * b, q = a + c; …; c = 7 in B3), how many expressions are available at the start of B4?

Numerical answer: ________

Q5MSQ1 markFacts

Which are true?

• (A) Available expressions is a forward problem.
• (B) Non-entry OUT sets start as the universal set.
• (C) It enables global common-subexpression elimination.
• (D) It is a backward may problem.

11 · Rule Card

• 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.

12 · Concept Ledger

available expressione_gen / e_killuniversal set Uglobal common-subexpression elimination

13 · Answer Vault