1 Assignment Objective

Implement a dead code detector for Java.

Dead code elimination is a common compiler optimization in which dead code is removed from a program, and its most challenging part is the detection of dead code. In this programming assignment, you will implement a dead code detector for Java by incorporating the analyses you wrote in the previous two assignments, i.e., live variable analysis and constant propagation.

2 What Is the Dead Code?

Dead code is part of the program which is unreachable (i.e., never be executed) or is executed but whose results are never used in any other computation.

In this assignment, we focus on two kinds of dead code, i.e., unreachable code and dead assignment.

2.1 Unreachable Code

Unreachable code in a program will never be executed. We consider two kinds of unreachable code, control-flow unreachable code and unreachable branch, as introduced below.

More-Details-Here

Control-flow Unreachable Code.

There is no control-flow path from the entry to the piece of code. For example:

int controlFlowUnreachable() {
    int x = 1;
    return x;
    int z = 42; // control-flow unreachable code
    foo(z); // control-flow unreachable code
}

Detection: Such code can be detected easily with CFG. We just need to traverse the CFG from the method entry and mark reachable statements. When the traversal finishes, the unmarked statements are control-flow unreachable.

Unreachable Branch: IF statement and SWITCH statement can form unreachable branches.

For an if-statement, if its condition value is a constant, then one of its two branches is certainly unreachable in any execution. For example:

int unreachableIfBranch() {
    int a = 1, b = 0, c;
    if (a > b)
        c = 2333;
    else
        c = 6666; // unreachable branch
    return c;
}

For a switch statement, if its condition value is a constant, then case branches whose values do not match that condition may be unreachable in any execution and become unreachable branches.

int unreachableSwitchBranch() {
    int x = 2, y;
    switch (x) {
        case 1: y = 100; break; // unreachable branch
        case 2: y = 200;
        case 3: y = 300; break; // fall through
        default: y = 666; // unreachable branch
    }
    return y;
}

Detection: to detect unreachable branches, we need to perform a constant propagation in advance, which tells us whether the condition values are constants, and then during CFG traversal, we do not enter the corresponding unreachable branches.

2.2 Dead Assignment

A local variable that is assigned a value but is not read by any subsequent instructions is referred to as a dead assignment, and the assigned variable is a dead variable (opposite to a live variable). Dead assignments do not affect program outputs and thus can be eliminated.

int deadAssign() {
    int a, b, c;
    a = 0; // dead assignment
    a = 1;
    b = a * 2; // dead assignment
    c = 3;
    return c;
}

Detection: to detect dead assignments, we need to perform a live variable analysis in advance. For an assignment, if its LHS variable is a dead variable (i.e., not live), then we could mark it as a dead assignment, except for one case as discussed below.

3 RTFC

💡

Talk is cheap, show me the code.

4 Solution

Control-flow Unreachable Statement:

💡

DFS Traverse

Dead Assignment Code:

💡

Leverage the result of live variables analysis

Static Program Analysis PA-3

Table of contents