Reaching definitions analysis in Compiler Design - Step-by-Step Execution

Concept Flow - Reaching definitions analysis

Start: Entry block

↓

Initialize IN and OUT sets

↓

For each block

↓

Calculate GEN and KILL sets

↓

Iterate until IN and OUT stabilize

↓

Output reaching definitions for each block

The analysis starts by initializing sets, then repeatedly updates IN and OUT sets for each block until no changes occur, showing which definitions reach each point.

Execution Sample

Compiler Design

Block1: d1: x=1
Block2: d2: y=2
Block3: d3: x=3

Compute IN and OUT sets for each block.

This example shows how definitions d1, d2, d3 reach different blocks in a simple control flow.

Analysis Table

Step	Block	IN Set	GEN Set	KILL Set	OUT Set	Change?
1	Block1	{}	{d1}	{}	{d1}	Yes
2	Block2	{d1}	{d2}	{d3}	{d1,d2}	Yes
3	Block3	{d1,d2}	{d3}	{d1}	{d2,d3}	Yes
4	Block1	{}	{d1}	{}	{d1}	No
5	Block2	{d1}	{d2}	{d3}	{d1,d2}	No
6	Block3	{d1,d2}	{d3}	{d1}	{d2,d3}	No

💡 No changes in IN and OUT sets after step 6, analysis converged.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6
IN(Block1)	{}	{}	{}	{}	{}
OUT(Block1)	{}	{d1}	{d1}	{d1}	{d1}
IN(Block2)	{}	{d1}	{d1}	{d1}	{d1}
OUT(Block2)	{}	{}	{d1,d2}	{d1,d2}	{d1,d2}
IN(Block3)	{}	{}	{d1,d2}	{d1,d2}	{d1,d2}
OUT(Block3)	{}	{}	{d2,d3}	{d2,d3}	{d2,d3}

Key Insights - 3 Insights

Why do we keep updating IN and OUT sets multiple times?

Because definitions can flow through multiple blocks, we must iterate until no changes occur to ensure all reaching definitions are found, as shown by changes in steps 1-3 and no changes after step 6.

What does the KILL set represent in this analysis?

The KILL set contains definitions that are overwritten by new definitions in the block, so they no longer reach beyond this block, as seen in Block2 killing d3 and Block3 killing d1.

Why is the OUT set of a block different from its GEN set?

OUT includes GEN plus any reaching definitions from predecessors that are not killed, showing all definitions reaching after the block, e.g., Block2's OUT is {d1,d2} not just {d2}.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the OUT set of Block3?

A {d1,d2}

B {d2,d3}

C {d3}

D {d1,d3}

💡 Hint

Check the OUT Set column for Block3 at step 3 in the execution_table.

At which step does the analysis stop changing the IN and OUT sets?

A Step 3

B Step 4

C Step 6

D Step 2

💡 Hint

Look for the first step where Change? is 'No' for all blocks in the execution_table.

If Block2 did not kill d3, how would OUT(Block2) change at step 2?

A {d1,d2,d3}

B {d1,d2}

C {d2}

D {d3}

💡 Hint

Consider that without killing d3, it remains in the OUT set along with d1 and d2.

Concept Snapshot

Reaching Definitions Analysis:
- Tracks which variable assignments (definitions) reach each program point.
- Uses IN, OUT, GEN, KILL sets per block.
- Iterates until IN and OUT sets stabilize (no changes).
- Helps optimize by knowing where variables are defined and used.
- Key rule: OUT = GEN ∪ (IN - KILL).

Full Transcript

Reaching definitions analysis is a method used in compilers to find out which assignments to variables can reach a certain point in the program. It works by assigning sets of definitions to each block: GEN for definitions made in the block, KILL for definitions overwritten, IN for definitions reaching the block, and OUT for definitions leaving the block. The analysis starts with empty sets and repeatedly updates IN and OUT for each block until no changes occur. This process ensures all possible definitions reaching each point are found. For example, in a simple program with three blocks defining variables x and y, the analysis shows how definitions flow through blocks and which are killed or preserved. This information is useful for optimizations like removing unnecessary assignments or detecting variable usage. The key formula is OUT = GEN union (IN minus KILL). Iteration continues until IN and OUT sets stabilize, meaning no new information is found. Understanding this helps in compiler design and program analysis.