Dead Code Elimination (DCE) is a compiler optimization technique that removes code fragments which will never be executed during program runtime. By eliminating unreachable and useless operations, DCE improves both execution efficiency and resource utilization.

DCE in Traditional Compilers

The primary goal of DCE in traditional compilers is identifying and removing operations that either cannot be reached through any valid execution path or produce no externally visible effects. This optimization relies on Control Flow Graph (CFG) analysis to trace the program's execution paths.

Unreachable Operations

Unreachable operations fall into two categories:

Operations within unreachable basic blocks: In a CFG, a basic block $b_i$ is considered reachable if there exists at least one path from the entry block $b_0$ to $b_i$. Any operation contained in an unreachable basic block will never execute, making it a candidate for elimination.

Operations in discarded branches: When a conditional branch's condition can be evaluated at compile time, the compiler knows which branch will be taken. The other branch becomes unreachable, and all operations within it can be eliminated.

Consider a CFG where $b_9$ is unreachable because no path exists from $b_0$ to $b_9$. Similarly, if the condition at $b_3$ always evaluates to true and $b_4$ is the destination for the true branch, then $b_5$ becomes unreachable and its operations become dead code.

Example demonstrating unreachable operation removal:

def process_input(flag):
    if flag:
        log_message("Condition satisfied")
    else:
        log_message("Condition not satisfied")
    exit_function()
    debug_output("This never runs")

process_input(False)

Since process_input receives only False, the first log_message call will never execute. The compiler transforms this to:

def process_input(flag):
    log_message("Condition not satisfied")
    exit_function()
    debug_output("This never runs")

process_input(False)

After the exit_function() call, the debug_output statement is unreachable. Further optimization produces:

def process_input(flag):
    log_message("Condition not satisfied")
    exit_function()

process_input(False)

The elimination algorithm uses depth-first search to mark all reachable basic blocks starting from $b_0$. For conditional branches with known outcomes, the compiler marks the untaken path and removes corresponding edges, converting previously reachable blocks into unreachable ones.

Useless Operations

A useless operation produces a result with no externally observable effect. For instance, assigning a value to a variable that is never referenced afterward constitutes a useless operation.

Some operations are deemed inherently useful and are called critical operations. These include:

• Operations modifying reference parameters, globals, or ambiguous pointers
• Return statements
• Input/output operations
• Memory accesses affecting externally visible state

Example demonstrating useless operation elimination:

def compute_result(a, b, c):
    temp1 = a + b
    temp2 = temp1 + c
    return temp2

compute_result(1, 2, 3)

Here, both temp1 and temp2 contribute to the return value, making them useful. However, modifying the return statement:

def compute_result(a, b, c):
    temp1 = a + b
    temp2 = temp1 + c
    return a + b + c

compute_result(1, 2, 3)

In this case, neither temp1 nor temp2 affects the function's behavior—both are useless operations eligible for removal.

Post-Dominance and Control Dependence

To identify useless operations beyond critical operations, compilers employ post-dominance and control dependence analysis.

Post-dominance: In a CFG, node $b_j$ post-dominates $b_i$ if every non-empty path from $b_i$ to the exit block passes through $b_j$. The computation follows:

$$RDOM(n) = {n} \cup \left(\bigcap_{m\in succ(n)} RDOM(m)\right)$$

where $RDOM(n)$ represents the post-dominance set of basic block $b_n$, and $succ(n)$ denotes its successor nodes.

Control dependence: Basic block $b_j$ is control-dependent on $b_i$ if $b_j$'s execution depends on the outcome of a conditional branch at $b_i$. Specifically, there must exist both a path from $b_i$ to the exit that passes through $b_j$ and another path that avoids $b_j$.

The elimination process marks useful operations iteratively: starting from critical operations, mark their operands as useful, then mark the conditional branches controlling their basic blocks. After marking completes, useless conditional branches are converted to unconditional jumps taregting the first post-dominator containing useful operations.

DCE in AI Compilers

AI compilers perform DCE at the computation graph level, identifying and removing nodes that cannot be reached from inputs or contribute no effect to outputs.

Unreachable nodes: Nodes that cannot be reached from any input node through directed edges. In a computation graph containing operators A, B, and C, if no path exists from input nodes to B, then B is unreachable and eliminated along with its outgoing edges.

Useless nodes: Nodes whose results have no impact on output nodes. In a computation graph, if operator B produces an output with no successor nodes and does not affect program state, B qualifies as useless and gets removed.

During training, numerous subgraphs are generated that serve no purpose during inference. These training-only artifacts can be eliminated during inference deployments.

Implementation Case Study

The following outlines a DCE implementation approach:

1. Reachability analysis: Perform depth-first search from the entry block to mark all reachable basic blocks.

2. Remove outgoing edges from unreachable blocks: For any basic block $b_n$ not marked reachable, iterate through its successors and remove edges to reachable blocks.

3. Eliminate invalid edges from reachable blocks: For conditional branches with statically determined conditions, identify the untaken branch and remove edges to those destinations.

4. Mark and remove useless operations: Starting from critical operations, propagate usefulness backward through operands and control dependencies. Replace useless value references with nil values, then prune all basic blocks containing only nil values.

5. Remove empty blocks: Traverse the CFG and delete any basic blocks containing no operations.

This multi-pass approach systematically eliminates unreachable and useless code while preserving program correctness.