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
Test your understanding
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?
AStep 6
BStep 4
CStep 5
DStep 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?
AOUT(Block2) would include 'a+b' and 'c+d'
BOUT(Block2) would only include 'c+d'
COUT(Block2) would be empty
DOUT(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.