Skip to main content

Liveness analysis

Liveness analysis is a fundamental backward data flow analysis that determines which variables might be used in the future at each point in a program. A variable is "live" at a program point if its current value may be read before it's overwritten. This analysis is crucial for dead code elimination, register allocation, and understanding data dependencies.

In this guide, we will walk you through the core concepts of liveness analysis, show you how to implement and use it with OpenRewrite's APIs, and cover practical applications like dead code elimination and optimization. We will also explore common pitfalls, performance considerations, and how to combine liveness analysis with other program analyses for even more powerful results.

Understanding liveness​

Think of liveness like tracking which sticky notes on your desk are still needed. A sticky note with a phone number is "live" if you'll need to make that call later. Once you've made the call (used the value), or written a new number on top of it (reassigned the variable), the original note becomes "dead" - you could have thrown it away without any consequences.

A simple example​

Let's see how liveness analysis works with a basic example:

// Example 1: Understanding liveness analysis
int x = 5;      // Point A
int y = 10;     // Point B  
int z = x + y;  // Point C: uses x and y
return z;       // Point D: uses z

// To find what's "live" (still needed), we analyze BACKWARD from the end:
// * At D (return): nothing is live after this - it's the end
// * At C (z = x + y): z is live because it's used at D
// * At B (y = 10): both x and y are live because they're used at C  
// * At A (x = 5): only y is live. Why? Because x gets its value HERE,
//                  so any previous value of x would be overwritten anyway

The key insight: liveness analysis works backward - we start at the end and ask "what values do I need?" at each step going up.

Implementation in OpenRewrite​

Below is how we implemented the LivenessAnalysis class in OpenRewrite:

public class LivenessAnalysis extends BackwardDataFlowAnalysis<LiveVariable, LiveVariables> {
    
    public LivenessAnalysis(ControlFlowGraph cfg) {
        super(cfg);
    }
    
    @Override
    protected Set<LiveVariable> transfer(BasicBlock block, Set<LiveVariable> exitLive) {
        // Start with what's live at block exit
        Set<LiveVariable> result = new HashSet<>(exitLive);
        
        // Process statements in reverse order (backward analysis)
        List<Tree> statements = new ArrayList<>(block.getStatements());
        Collections.reverse(statements);
        
        for (Tree stmt : statements) {
            // KILL: Remove variables defined in this statement
            Set<String> defined = findDefinedVariables(stmt);
            result.removeIf(lv -> defined.contains(lv.getVariableName()));
            
            // GEN: Add variables used in this statement
            Set<LiveVariable> used = findUsedVariables(stmt);
            result.addAll(used);
        }
        
        return result;
    }
    
    @Override
    protected Set<LiveVariable> merge(Set<LiveVariable> facts1, Set<LiveVariable> facts2) {
        // Union for "may" analysis
        Set<LiveVariable> result = new HashSet<>(facts1);
        result.addAll(facts2);
        return result;
    }
}

Working with LiveVariables results​

Now that we've seen how liveness analysis is implemented, let's explore how to use it in practice. The LiveVariables result type provides rich querying capabilities that make it easy to answer questions about your code:

Basic queries​

LivenessAnalysis analysis = new LivenessAnalysis(cfg);
LiveVariables liveVars = analysis.analyze();

// Check if a variable is live at a specific point
boolean isLive = liveVars.isLive("counter", statement);

// Get all live variables at a statement
Set<String> liveAtStatement = liveVars.getLiveVariableNames(statement);

// Get live variables at block entry/exit
Set<String> liveAtEntry = liveVars.getLiveVariableNames(block);

Advanced queries​

// Find all dead assignments automatically
List<J.Assignment> deadAssignments = liveVars.findDeadAssignments();

// Find unused variable declarations
List<J.VariableDeclarations.NamedVariable> unusedVars = 
    liveVars.findDeadVariableDeclarations();

// Get variables live at method exit (potential return values)
Set<String> liveAtExit = liveVars.getLiveAtExit();

// Check if any variables are live
boolean hasLiveVars = liveVars.hasLiveVariables();

Common patterns and edge cases​

With these querying tools in hand, let's examine some common code patterns you'll encounter and the edge cases that can trip up liveness analysis:

Assignment chains​

int x = 5;      // Dead - immediately overwritten
x = 10;         // Live - used below
int y = x * 2;  // x is used here

Liveness analysis correctly identifies that the first assignment is dead.

Conditional assignments​

int result;
if (condition) {
    result = computeA();  // Live if condition is true
} else {
    result = computeB();  // Live if condition is false
}
return result;  // result used here

Both assignments are live because result is used after the if-statement.

Loop variables​

for (int i = 0; i < n; i++) {
    sum += i;  // i is used
    // At loop end: i is live (used in increment and condition)
}
// After loop: i is dead (out of scope)

Loop variables have special liveness patterns due to back edges.

Field access​

Field access requires careful handling.

class Container {
    int value;
    
    void process() {
        this.value = 10;    // Is this dead?
        other.value = 20;   // Different object's field
        // Need field-sensitive analysis
    }
}

OpenRewrite's implementation tracks fields separately when possible.

Practical applications​

Understanding these patterns is important, but the real value of liveness analysis comes from applying it to solve real problems. Here are the most common applications:

Dead code elimination​

The most direct application.

public void optimizeMethod() {
    LiveVariables liveVars = new LivenessAnalysis(cfg).analyze();
    
    // Remove dead assignments
    for (J.Assignment dead : liveVars.findDeadAssignments()) {
        removeStatement(dead);
    }
    
    // Remove unused variables
    for (var unused : liveVars.findDeadVariableDeclarations()) {
        removeDeclaration(unused);
    }
}

Register allocation​

Compilers use liveness for efficient register allocation.

// Variables with non-overlapping live ranges can share registers
int x = compute1();  // Live: lines 1-3
use(x);
// x dead after here
int y = compute2();  // Live: lines 4-6
use(y);
// x and y can use the same register!

Advanced topics​

Once you've mastered the basics, you'll encounter situations that require more sophisticated approaches. Let's explore some advanced topics in liveness analysis:

Liveness with aliasing​

When variables can alias, liveness becomes more complex.

int[] arr1 = new int[10];
int[] arr2 = arr1;  // arr2 aliases arr1
arr2[0] = 5;        // Also affects arr1
// Both arr1 and arr2 are live if either is used

Inter-procedural liveness​

Tracking liveness across method calls.

public int compute(int x) {
    int y = transform(x);  // Is x live after this?
    // Depends on whether transform modifies x
    // or if x is used after the call
    return y;
}

Liveness in concurrent programs​

Thread interactions affect liveness.

volatile int shared;

void thread1() {
    shared = 10;  // Can't be dead - other threads might read
}

Performance optimization​

As your analyses scale to larger codebases, performance becomes critical. Here are key strategies for making liveness analysis efficient:

Sparse representations​

For large methods, use sparse representations.

// Instead of tracking all variables at all points
Map<ProgramPoint, Set<Variable>> allLiveness;  // Dense

// Track only where changes occur
Map<ProgramPoint, LivenessChange> changes;     // Sparse

Incremental updates​

When code changes, update liveness incrementally.

public void updateLiveness(Statement changed) {
    BasicBlock block = findContainingBlock(changed);
    
    // Only recompute from this block
    invalidateBlock(block);
    propagateChanges(block);
}

Common pitfalls​

Even with all these techniques, there are still traps that can catch you. Here are the most common pitfalls and how to avoid them:

Side effects in expressions​

Not all "dead" assignments can be removed.

int x = sideEffect();  // Can't remove even if x is dead!
// The method call might have important effects

Exception paths​

Variables might be live only on exception paths.

String error = "Starting";
try {
    error = "Processing";
    riskyOperation();
    error = "Success";  // Might seem dead but...
} catch (Exception e) {
    log.error(error);   // Used on exception path!
}

Implicit uses​

Some uses aren't obvious in the AST.

public String toString() {
    return name;  // Implicit use of 'this.name'
}

Testing liveness analysis​

With all these edge cases and pitfalls, thorough testing becomes essential.

@Test
void testConditionalLiveness() {
    rewriteRun(
        java("""
            class Test {
                int method(boolean flag) {
                    int x = 1;
                    if (flag) {
                        x = 2;
                    }
                    return x;  // x is live through all paths
                }
            }
            """)
    );
    
    // Verify both assignments are marked as live
}

Integration with other analyses​

While liveness analysis is powerful on its own, it becomes even more valuable when combined with other program analyses. Here are some powerful combinations:

With reaching definitions​

// Find uninitialized variable uses
if (liveVars.isLive(var, point) && !reachingDefs.hasDefinition(var, point)) {
    reportError("Uninitialized variable: " + var);
}

With constant propagation​

// Only propagate constants to live variables
if (liveVars.isLive(var, point) && constants.isConstant(var)) {
    replaceWithConstant(var, constants.getValue(var));
}

Next steps​