Available expressions analysis in Compiler Design - Step-by-Step Execution

Concept Flow - Available expressions analysis

Start: Entry block

↓

Initialize: All expressions not available

↓

For each block

↓

Compute IN set: Intersection of predecessors' OUT sets

↓

Compute OUT set: GEN union (IN - KILL)

↓

Check if IN or OUT changed

↓

Repeat analysis

The analysis starts with no expressions available, then iteratively computes IN and OUT sets for each block until no changes occur, indicating all available expressions are found.

Execution Sample

Compiler Design

Block1:
  IN = {}
  OUT = GEN1
Block2:
  IN = OUT(Block1)
  OUT = GEN2 union (IN - KILL2)

Shows how IN and OUT sets are computed for two blocks using GEN and KILL sets.

Analysis Table

Step	Block	IN Set	OUT Set	Change Detected	Action
1	Entry	{}	{a+b}	Yes	Initialize OUT with GEN
2	Block1	{}	{a+b}	Yes	OUT = GEN1
3	Block2	{a+b}	{a+b, c+d}	Yes	IN = OUT(Block1), OUT = GEN2 union (IN - KILL2)
4	Block1	{a+b}	{a+b}	No	No change
5	Block2	{a+b}	{a+b, c+d}	No	No change
6	-	-	-	-	Fixed point reached, analysis complete

💡 No changes in IN or OUT sets detected, analysis converged

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
IN(Block1)	{}	{}	{}	{a+b}	{a+b}
OUT(Block1)	{}	{a+b}	{a+b}	{a+b}	{a+b}
IN(Block2)	{}	{}	{a+b}	{a+b}	{a+b}
OUT(Block2)	{}	{}	{}	{a+b, c+d}	{a+b, c+d}

Key Insights - 3 Insights

Why do we take the intersection of predecessors' OUT sets to compute IN?

Because an expression is only available at the start of a block if it is available at the end of all predecessor blocks, ensuring safety in reuse.

What causes the analysis to repeat steps multiple times?

If the IN or OUT sets change after computation, the analysis repeats to propagate these changes until no further changes occur, reaching a fixed point.

Why do we subtract KILL sets from IN when computing OUT?

Because expressions killed (overwritten or invalidated) in the block cannot be considered available after it, so they must be removed from the IN set before adding GEN.

Visual Quiz - 3 Questions

Look at the execution table at Step 3, what is the IN set for Block2?

A {c+d}

B {}

C {a+b}

D {a+b, c+d}

💡 Hint

Check the IN Set column for Block2 at Step 3 in the execution table

At which step does the analysis detect no changes and stop repeating?

A Step 6

B Step 4

C Step 5

D Step 3

💡 Hint

Look for the step where Change Detected is 'No' for all blocks and the exit note says analysis complete

If the KILL set for Block2 included 'a+b', how would OUT(Block2) change at Step 3?

A OUT(Block2) would include 'a+b' and 'c+d'

B OUT(Block2) would only include 'c+d'

C OUT(Block2) would be empty

D OUT(Block2) would be same as IN(Block2)

💡 Hint

Recall OUT = GEN union (IN - KILL); if 'a+b' is killed, it is removed from IN before union

Concept Snapshot

Available Expressions Analysis:
- Tracks expressions computed and not invalidated along all paths
- IN(block) = intersection of predecessors' OUT sets
- OUT(block) = GEN union (IN - KILL)
- Iterates until IN and OUT sets stabilize (fixed point)
- Helps optimize by reusing computed expressions safely

Full Transcript

Available expressions analysis is a compiler technique to find expressions that have been computed and not changed along all paths to a point. It starts with empty sets and iteratively computes IN and OUT sets for each block. IN is the intersection of all predecessor blocks' OUT sets, ensuring only expressions available on all paths are considered. OUT is computed by adding expressions generated in the block (GEN) and removing those killed (KILL) from IN. This process repeats until no changes occur, meaning the analysis has reached a fixed point. This information helps compilers optimize code by reusing previously computed expressions safely.

Practice

1. What is the main purpose of available expressions analysis in compiler design?

easy

A. To find expressions that have already been computed and not changed

B. To detect syntax errors in the source code

C. To allocate memory for variables

D. To generate machine code from source code

Solution

1. Step 1: Understand the goal of available expressions analysis

   This analysis identifies expressions that have been computed before and whose values have not changed since.

2. Step 2: Compare with other compiler tasks

   Unlike syntax checking or code generation, available expressions focus on optimization by reusing computed values.

3. Final Answer:

   To find expressions that have already been computed and not changed -> Option A

4. Quick Check:

   Available expressions = computed and unchanged expressions [OK]

Hint: Focus on expressions reused without recomputation [OK]

Common Mistakes:

• Confusing with syntax error detection
• Thinking it allocates memory
• Mixing with code generation tasks

2. Which of the following correctly represents the GEN set in available expressions analysis?

easy

A. All variables used in the program

B. Variables assigned new values in a block

C. Expressions computed in a block and not killed within it

D. Expressions that are never computed in the program

Solution

1. Step 1: Define the GEN set

   GEN set contains expressions that are computed in a block and remain valid (not overwritten) within that block.

2. Step 2: Eliminate incorrect options

   Variables assigned new values relate to KILL sets, not GEN. Expressions never computed or all variables are unrelated.

3. Final Answer:

   Expressions computed in a block and not killed within it -> Option C

4. Quick Check:

   GEN = computed and valid expressions [OK]

Hint: GEN = expressions generated and still valid in block [OK]

Common Mistakes:

• Mixing GEN with KILL sets
• Confusing variables with expressions
• Selecting unrelated program elements

3. Consider a basic block with the following statements:

a = b + c
d = a + e
b = 5

Which expressions are available at the end of this block?

medium

A. {a + e}

B. {} (empty set)

C. {b + c, a + e}

D. {b + c}

Solution

1. Step 1: Identify expressions computed

   The expressions computed are b + c and a + e.

2. Step 2: Check if expressions remain valid

   b + c is killed because b is assigned later (b = 5). a + e remains available since neither a nor e is reassigned after its computation.

3. Final Answer:

   {a + e} -> Option A

4. Quick Check:

   Expressions available if no operand reassigned after computation [OK]

Hint: Check operand reassignments after each computation [OK]

Common Mistakes:

• Ignoring variable reassignment kills expressions
• Assuming all computed expressions remain available
• Confusing direct operands with transitive dependencies

4. Identify the error in this available expressions analysis step:

GEN = {x + y}
KILL = {x = 3}
Available expressions at block end = GEN ∪ (IN - KILL)

What is wrong with this calculation?

medium

A. Using union (∪) instead of intersection (∩) for available expressions

B. Confusing KILL set with GEN set

C. Not updating IN set before calculation

D. Including variables instead of expressions in KILL

Solution

1. Step 1: Recall available expressions formula

   The formula Available_out = GEN ∪ (IN - KILL) is correct when GEN and KILL contain expressions.

2. Step 2: Identify the error in the sets

   KILL = {x = 3} includes an assignment instead of killed expressions (e.g., those with x as operand).

3. Final Answer:

   Including variables instead of expressions in KILL -> Option D

4. Quick Check:

   KILL = expressions killed by assignments [OK]

Hint: KILL contains killed expressions, not assignments [OK]

Common Mistakes:

• Misrepresenting KILL set contents
• Mixing variables and expressions in sets
• Ignoring proper IN set update

5. Given two basic blocks with:

Block 1: GEN = {a + b}, KILL = {a = 4}
Block 2: GEN = {a + b, c + d}, KILL = {b = 2}

If the IN set for Block 2 is {a + b}, what is the OUT set for Block 2 after available expressions analysis?

hard

A. {a + b, c + d}

B. {c + d}

C. {a + b}

D. {} (empty set)

Solution

1. Step 1: Calculate OUT set formula

   OUT = GEN ∪ (IN ∩ ¬KILL). Here, GEN = {a + b, c + d}, IN = {a + b}, KILL kills expressions involving b.

2. Step 2: Remove killed expressions from IN

   a + b is killed (involves b), so IN ∩ ¬KILL = {}.

3. Step 3: Compute OUT set

   OUT = GEN ∪ {} = {a + b, c + d}, but since a + b is killed by KILL, it should not be in OUT. Therefore, OUT = {c + d}.

4. Final Answer:

   {c + d} -> Option B

5. Quick Check:

   OUT = GEN ∪ (filtered IN) with killed expressions removed [OK]

Hint: Filter IN with ¬KILL, then union GEN [OK]

Common Mistakes:

• Applying KILL to GEN expressions
• Not intersecting IN with complement of KILL
• Assuming all GEN expressions remain available