Available expressions analysis in Compiler Design - Mini Project: Build & Apply

Available Expressions Analysis

📖 Scenario: You are working on a simple compiler optimization task. You want to find expressions in a program that have already been computed and whose values are still available at certain points in the program. This helps avoid repeating calculations and speeds up the program.

🎯 Goal: Build a step-by-step analysis to identify available expressions at each point in a simple control flow graph (CFG) of a program.

📋 What You'll Learn

Create a control flow graph with basic blocks and their expressions

Define the set of all expressions in the program

Compute the available expressions at the entry and exit of each block

Complete the analysis by applying the data flow equations

💡 Why This Matters

🌍 Real World

Available expressions analysis is used in compilers to optimize code by reusing previously computed expressions, reducing redundant calculations and improving performance.

💼 Career

Understanding data flow analysis techniques like available expressions is essential for compiler developers, performance engineers, and software developers working on code optimization.

1

Create the control flow graph data structure

Create a dictionary called cfg representing the control flow graph with these exact entries: 'B1': ['a + b', 'c * d'], 'B2': ['a + b', 'e - f'], and 'B3': ['c * d', 'g + h'].

Compiler Design

# Create the control flow graph dictionary called cfg
# Your code here

Hint

Use a Python dictionary with block names as keys and lists of expressions as values.

2

Define the universal set of expressions

Create a set called all_expr that contains all unique expressions from all blocks in cfg.

Compiler Design

cfg = {
    'B1': ['a + b', 'c * d'],
    'B2': ['a + b', 'e - f'],
    'B3': ['c * d', 'g + h']
}

# Create the set all_expr with all unique expressions
# Your code here

Hint

Use a loop over cfg keys and update a set with expressions from each block.

3

Initialize available expressions at entry and exit

Create two dictionaries called avail_in and avail_out with keys as block names from cfg. Initialize avail_in for all blocks to the empty set, and avail_out for all blocks to the set of expressions in that block.

Compiler Design

cfg = {
    'B1': ['a + b', 'c * d'],
    'B2': ['a + b', 'e - f'],
    'B3': ['c * d', 'g + h']
}

all_expr = set()
for block in cfg:
    all_expr.update(cfg[block])

# Initialize avail_in and avail_out dictionaries
# Your code here

Hint

Use dictionary comprehensions to create avail_in and avail_out.

4

Apply data flow equations to update available expressions

Given the control flow graph edges edges = {'B1': ['B2', 'B3'], 'B2': ['B3'], 'B3': []}, update avail_in and avail_out by applying the available expressions data flow equations once: for each block, set avail_in[block] to the intersection of avail_out of its predecessors, and set avail_out[block] to the union of cfg[block] and avail_in[block]. Assume avail_in of entry block 'B1' is empty set.

Compiler Design

cfg = {
    'B1': ['a + b', 'c * d'],
    'B2': ['a + b', 'e - f'],
    'B3': ['c * d', 'g + h']
}

all_expr = set()
for block in cfg:
    all_expr.update(cfg[block])

avail_in = {block: set() for block in cfg}
avail_out = {block: set(cfg[block]) for block in cfg}

edges = {'B1': ['B2', 'B3'], 'B2': ['B3'], 'B3': []}

# Update avail_in and avail_out using data flow equations
# Your code here

Hint

First find predecessors of each block, then update avail_in as intersection of avail_out of predecessors, and avail_out as union of block expressions and avail_in.

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