Liveness Analysis

AI Summary

An AI-generated summary of this video lecture.

The lecture introduces liveness analysis in compiler design, beginning with the definitions of USE/GEN and DEF/KILL sets. The instructor uses a simple code example, x = a + b and y = x + c, to show that USE/GEN is {a, b, c} and DEF/KILL is {x, y}. The core dataflow equations are then presented: IN(n) = USE(n) ∪ (OUT(n) - DEF(n)) and OUT(n) = ⋃ IN(s) for s ∈ Successor(n). The term successor is defined as the node to which control can directly move. A four-block Control Flow Graph (CFG) is introduced as the main worked example: Block 1 contains p = q + r, s = p * q (or p + q), u = s / v; Block 2 contains v = u * r (or u + r); Block 3 contains q = s - u; and Block 4 contains q = v + r. The instructor builds a table with columns for Basic Block, USE, DEF, IN, and OUT, filling in the sets row by row. For example, Block 1 has USE {q, r, v} and DEF {p, s, u}. The lecture proceeds by applying the IN/OUT equations iteratively to compute live variables at entry and exit for each basic block, using the CFG edges including a back edge from Block 4 to Block 1. The final section continues filling the table with variable sets such as {p, q, r, v} and {s, u}, demonstrating the fixed-point computation of liveness.

Chapters

1. 0:00 – 2:00 00:00-02:00

   The lecture opens with a slide titled 'Liveness Analysis' and defines USE/GEN as variables used in a block before any assignment. The on-screen example shows 'x = a + b' and 'y = x + c', with USE/GEN = {a, b, c} highlighted. A DEF/KILL section is also shown. The view then switches to a Control Flow Graph with four boxes labeled Basic Block 1 through Basic Block 4, connected by arrows including a back edge from block 4 to block 1.

2. 2:00 – 5:00 02:00-05:00

   The instructor presents the CFG with four basic blocks and asks for IN (Entry) and OUT (Exit) live variables. The slide defines USE/GEN as variables used before assignment, with the example 'x = a + b' and 'y = x + c' yielding USE/GEN {a, b, c}. DEF/KILL is defined as variables assigned a value in the block. The IN(n) and OUT(n) formulas are introduced: IN(n) = USE(n) ∪ (OUT(n) - DEF(n)) and OUT(n) = ⋃ IN(s) over s ∈ Successor(n). The instructor points to Basic Block 1 in the CFG.

3. 5:00 – 10:00 05:00-10:00

   The instructor writes liveness formulas in magenta marker on the whiteboard: IN(m) = USE(m) ∪ (DEF(m) - OUT(m)) and later corrects to IN(m) = USE(m) ∪ (OUT(m) - DEF(m)), with OUT(m) = ⋃ IN(n), n ∈ Successor. A CFG is drawn with Basic Block 1 containing 'p = q + r', 's = p * q' (or 's = p + q'), 'u = s / v'; Block 2 with 'v = u * r' (or 'v = u + r'); Block 3 with 'q = s - u'; and Block 4 with 'q = v + r'. The on-screen prompt reads 'Q. Consider the following Control Flow Graph:' asking to determine IN and OUT live variables.

4. 10:00 – 15:00 10:00-15:00

   The instructor begins filling a table with columns 'Basic Block', 'USE', 'DEF'. Row 1 shows USE {q, r, v} and DEF {p, s, u}. The table then gains 'IN' and 'OUT' columns. The purple formulas at the top read IN(m) = USE(m) ∪ (OUT(m) - DEF(m)) and OUT(m) = ⋃ IN(n), n ∈ Successor. The CFG blocks contain statements such as 'q = p + r', 's = p + q', 'u = s / v' in Block 1, 'v = u * r' in Block 2, and 'q = s - u' in Block 3.

5. 15:00 – 20:00 15:00-20:00

   The instructor continues writing into the liveness table while the CFG is drawn on the left. The CFG shows Basic Block 1 with 'p = q + r', 's = p + q', 'u = s / v'; Block 2 with 'v = u * r' (or 'v = u + r'); Block 3 with 'q = s - u'; and Block 4 with 'q = v + r'. Top-right formulas read IN(m) = USE(m) ∪ (OUT(m) - DEF(m)) and OUT(m) = ⋃ IN(n), S ∈ Successor. The table headers are 'Basic Block', 'USE', 'DEF', 'IN', 'OUT'; row 1 lists USE {q, r, v} and DEF {p, s, u}.

6. 20:00 – 25:00 20:00-25:00

   The instructor continues filling the liveness table row by row with variable sets. The CFG lists Basic Block 1 (p = q + r, s = p + q, u = s / v), Block 2 (v = u + r), Block 3 (q = s - u), and Block 4 (q = v + r). Top-right formulas read IN(m) = USE(m) ∪ (OUT(m) − DEF(m)) and OUT(m) = ⋃ IN(n), S ∈ Successor. A table with columns Basic Block, USE, DEF, IN, OUT plus a second IN/OUT pair is filled with variable sets such as {p, q, r, v} and {s, u}.

7. 25:00 – 28:32 25:00-28:32

   The final section shows the completed or nearly completed liveness table with all four basic blocks. The graph lists Basic Block 1 (p = q + r, s = p + q, u = s / v), Block 2 (v = u + r), Block 3 (q = s - u), and Block 4 (q = v + r). Top-right formulas read IN(m) = USE(m) ∪ (OUT(m) − DEF(m)) and OUT(m) = ⋃ IN(n), S ∈ Successor. The table is filled row by row with variable sets, demonstrating the iterative fixed-point computation of live variables at entry and exit for each block.

The lecture systematically builds liveness analysis from definitions to a worked example. First, USE/GEN and DEF/KILL are defined using the simple code x = a + b; y = x + c, yielding USE/GEN {a, b, c} and DEF/KILL {x, y}. The dataflow equations IN(n) = USE(n) ∪ (OUT(n) - DEF(n)) and OUT(n) = ⋃ IN(s) for s ∈ Successor(n) are then introduced. The successor concept is defined as the node control can directly move to. A four-block CFG serves as the main example, with Block 1 containing three statements (p = q + r, s = p * q or p + q, u = s / v), Block 2 (v = u * r or u + r), Block 3 (q = s - u), and Block 4 (q = v + r). The instructor constructs a table with USE, DEF, IN, and OUT columns for each block. Block 1's USE is {q, r, v} and DEF is {p, s, u}. The IN/OUT equations are applied iteratively across the CFG edges, including a back edge from Block 4 to Block 1, to compute live variable sets at entry and exit. The table is filled row by row with sets such as {p, q, r, v} and {s, u}, illustrating the fixed-point iteration process central to liveness analysis.