Reaching definitions analysis in Compiler Design - Mini Project: Build & Apply

Reaching Definitions Analysis

📖 Scenario: You are working on a simple compiler optimization module. Your task is to analyze a small program's control flow graph (CFG) to find which variable definitions can reach each point in the program. This helps the compiler understand where variables get their values from.

🎯 Goal: Build a step-by-step reaching definitions analysis for a given control flow graph represented as a dictionary. You will create the initial data, set up configuration, apply the core reaching definitions logic, and finalize the analysis results.

📋 What You'll Learn

Create a dictionary called cfg representing the control flow graph with exact nodes and edges

Create a dictionary called definitions mapping each node to the set of variable definitions it generates

Implement the reaching definitions analysis using a fixed-point iteration approach

Produce a dictionary called in_sets showing the reaching definitions at the entry of each node

💡 Why This Matters

🌍 Real World

Reaching definitions analysis is used in compilers to optimize code by understanding where variables get their values and eliminating redundant computations.

💼 Career

Compiler engineers and software developers working on static analysis tools use reaching definitions to improve program performance and correctness.

1

Create the control flow graph

Create a dictionary called cfg representing the control flow graph with these exact nodes and edges: 1: [2], 2: [3, 4], 3: [5], 4: [5], 5: []

Compiler Design

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

Need a hint?

Use a Python dictionary where keys are node numbers and values are lists of successor nodes.

2

Define variable definitions per node

Create a dictionary called definitions mapping each node to a set of variable definitions it generates exactly as follows: 1: {"a=1"}, 2: {"b=2"}, 3: {"a=3"}, 4: {}, 5: {}

Compiler Design

cfg = {
    1: [2],
    2: [3, 4],
    3: [5],
    4: [5],
    5: []
}
# Create the definitions dictionary mapping nodes to sets of definitions
# Your code here

Need a hint?

Use sets to represent definitions generated at each node.

3

Implement reaching definitions analysis

Create a dictionary called in_sets with all nodes initialized to empty sets. Then use a while loop to update in_sets until no changes occur. For each node, set in_sets[node] to the union of in_sets of its predecessors plus their definitions. Use the exact variable names cfg, definitions, and in_sets.

Compiler Design

cfg = {
    1: [2],
    2: [3, 4],
    3: [5],
    4: [5],
    5: []
}
definitions = {
    1: {"a=1"},
    2: {"b=2"},
    3: {"a=3"},
    4: set(),
    5: set()
}
# Initialize in_sets and perform fixed-point iteration
# Your code here

Need a hint?

Use a loop that continues until no changes happen. For each node, find predecessors and combine their in_sets and definitions.

4

Finalize and output reaching definitions

Add a final line that creates a dictionary called out_sets where each node maps to the union of its in_sets[node] and definitions[node]. Use the exact variable names in_sets, definitions, and out_sets.

Compiler Design

cfg = {
    1: [2],
    2: [3, 4],
    3: [5],
    4: [5],
    5: []
}
definitions = {
    1: {"a=1"},
    2: {"b=2"},
    3: {"a=3"},
    4: set(),
    5: set()
}

in_sets = {node: set() for node in cfg}

changed = True
while changed:
    changed = False
    for node in cfg:
        preds = [p for p, succs in cfg.items() if node in succs]
        new_in = set()
        for p in preds:
            new_in |= in_sets[p] | definitions[p]
        if new_in != in_sets[node]:
            in_sets[node] = new_in
            changed = True

# Create out_sets dictionary mapping each node to in_sets[node] union definitions[node]
# Your code here

Need a hint?

Combine the in_sets and definitions for each node to get the final reaching definitions at the node's exit.