Dead Code Elimination (DCE)

Dead Code Elimination is a compiler optimization that identifies and removes code that does not affect the program's final output. This includes:

• Unreachable Code: Statements that can never be executed due to control flow (e.g., code after a return or in a conditional branch with a constant false condition).
• Dead Stores: Computations whose results are written to a variable but are never subsequently read before the variable is overwritten or goes out of scope.
• Unused Side Effects: Operations like function calls or memory stores that have no observable impact on the program's state or output.

The optimization operates on the compiler's Intermediate Representation (IR), using data-flow analysis to track the liveness of variables and the reachability of code blocks.

The aggressiveness of DCE depends on the compiler's analysis phase.

Static DCE is performed during compile-time analysis and can only eliminate code provably dead based on the source code structure. For example, it can remove code guarded by #ifdef flags that evaluate to false.

Aggressive DCE, often enabled by higher optimization levels (e.g., -O2, -O3), leverages more sophisticated analyses like interprocedural analysis and link-time optimization (LTO). This can eliminate entire functions that are never called, even across compilation unit boundaries, and remove code dependent on constant propagation from inlined functions.

DCE is rarely a standalone pass; it is deeply interwoven with other compiler transformations in a phase-ordering problem.

• Constant Propagation & Folding: Often creates new dead code by replacing variables with constants, revealing unreachable branches.
• Common Subexpression Elimination (CSE): Can make previously live computations redundant, turning them into candidates for DCE.
• Function Inlining: Exposes the internal logic of a called function, allowing the compiler to see if parts of it are unused in the specific calling context.
• Loop-Invariant Code Motion: Moves computations outside of loops, after which the original computation inside the loop may become dead if it was the only use.

The compiler typically runs multiple rounds of DCE after other major optimization passes to clean up newly created dead code.

On specialized hardware like Neural Processing Units (NPUs), DCE provides critical benefits beyond traditional CPU compilation:

• Reduced Kernel Size: Eliminating dead instructions shrinks the kernel binary, reducing instruction cache pressure and improving fetch efficiency.
• Lower Register Pressure: Removing computations frees up precious on-chip registers, potentially increasing kernel occupancy by allowing more thread blocks to reside concurrently on a streaming multiprocessor.
• Decreased Memory Traffic: Eliminating dead stores reduces unnecessary writes to global memory or shared memory, conserving bandwidth—a key bottleneck for many accelerators.
• Power Efficiency: Fewer executed instructions directly translates to lower dynamic power consumption, a crucial factor for edge and mobile NPUs.

Despite its utility, DCE has inherent limitations.

• Conservative Analysis: Compilers must be conservative. Code with potential side effects (e.g., I/O, volatile memory accesses) cannot be removed unless proven safe, even if the results are unused.
• Pointer Aliasing: If a variable's address is taken (&var), it becomes difficult to prove its value is never read, limiting dead store elimination.
• Separate Compilation: Without Link-Time Optimization (LTO), a function may appear unused in one compilation unit but be called from another, preventing its removal.
• Debugging & Instrumentation: DCE can interfere with debugging by removing code that sets variables a developer wishes to inspect. This is why optimizations are typically disabled for debug builds (-O0).

Consider a simple neural network layer in a computational graph: output = relu(conv2d(input, weights) + bias). An optimizing compiler for NPUs might perform operation fusion, creating a single fused kernel. During this process, DCE is critical.

1. The original, unfused graph has separate nodes for convolution, addition, and ReLU.
2. After fusion, the compiler generates a single kernel that performs all three operations.
3. Intermediate tensors that held the results of conv2d and the addition are no longer materialized in global memory; they become dead stores in the fused representation.
4. DCE removes the IR instructions that allocated and wrote to these now-ephemeral intermediate buffers.
5. The final kernel only contains instructions for the fused computation, writing directly to the final output tensor, minimizing memory traffic and kernel size.

Dead Code Elimination (DCE) is a compiler optimization that identifies and removes code that does not affect the program's final output. This includes:

• Unreachable Code: Statements that can never be executed due to control flow (e.g., code after a return or in a conditional branch with a constant false condition).
• Dead Stores: Computations whose results are written to a variable but are never subsequently read.
• Unused Side-Effect-Free Expressions: Calculations that produce a value which is never consumed.

For NPU kernels, DCE is often performed on the Intermediate Representation (IR) after other optimizations like Constant Propagation and Common Subexpression Elimination (CSE) have exposed more dead code.

In NPU compilation, DCE directly enhances performance and efficiency by:

• Reducing Kernel Binary Size: Eliminating unused instructions shrinks the kernel, improving instruction cache hit rates.
• Minimizing Register Pressure: Removing dead computations frees up valuable on-chip registers, potentially increasing kernel occupancy.
• Eliminating Redundant Memory Traffic: Dead stores to global or shared memory are removed, conserving critical memory bandwidth.
• Enabling Further Optimizations: Cleaning the IR can expose new opportunities for Kernel Fusion or Loop Fission.

Without DCE, kernels waste precious NPU cycles and resources on computations that contribute nothing to the final result.

Compilers implement DCE at varying levels of aggressiveness:

• Static (Conservative) DCE: The default approach. It only removes code provably dead based on static analysis of the IR. It cannot eliminate code that depends on runtime values.
• Aggressive DCE: Often enabled via optimization flags (e.g., -O3). It makes more optimistic assumptions, such as treating inline functions without external linkage as having no side effects, allowing for more extensive removal.

A key limitation is code with side effects (e.g., I/O, volatile memory accesses). Conservative DCE will retain such code even if its output is unused, as the side effect itself is considered an observable behavior.

DCE is not a standalone pass; it works synergistically within an optimization pipeline:

1. Constant Propagation & Folding: Replaces variables with constants, often turning conditional branches into constants, creating new unreachable code for DCE to remove.
2. Common Subexpression Elimination (CSE): Creates temporary variables for repeated calculations. If the sole use of that temporary is later eliminated, DCE removes the CSE-introduced computation.
3. Inlining: Copies function bodies into call sites. This can expose function-local dead code to the broader optimization context.
4. Loop-Invariant Code Motion: Moves computations outside of loops. If the moved computation's result is unused, DCE will delete it entirely.

This creates a phase-ordering problem where the compiler may run DCE multiple times throughout the pass pipeline.

Machine learning frameworks perform DCE on computational graphs before lowering to NPU code:

• Graph-Level DCE: In frameworks like TensorFlow (with Grappler) and PyTorch (with TorchScript/torch.compile), the high-level dataflow graph is analyzed. Operations that do not contribute to a requested output tensor (like loss or predictions) are pruned.
• JIT Compilation: During Just-In-Time (JIT) Compilation, the runtime can perform aggressive DCE based on the concrete input shapes and requested outputs, removing entire branches of a conditional graph that aren't taken.
• Example: In a model with training and inference paths, the framework's graph compiler will eliminate the backward pass and optimizer update operations when only inference is requested.

While powerful, DCE has important boundaries and subtleties:

• Observable Side Effects: Code performing I/O, modifying volatile memory, or calling external functions with unknown side effects is always preserved.
• Debug Information: DCE typically operates independently of debug symbols. Code removed by DCE may still be referenced in debug data, leading to potential mismatches when stepping with a debugger.
• Link-Time Optimization (LTO): Truly global DCE often requires LTO, which allows the compiler to see the entire program. This can eliminate entire unused functions and global variables that are invisible during single-module compilation.
• Precision vs. Aggressiveness Trade-off: Overly aggressive DCE in the presence of complex pointer aliasing or indirect calls can incorrectly remove live code, leading to bugs. Sophisticated alias analysis is required for safety.

Common Subexpression Elimination is a compiler optimization that identifies and eliminates redundant computations of identical expressions. It analyzes the program to find expressions that are computed more than once with the same operands. The compiler then computes the expression once, stores the result in a temporary variable, and reuses that value, thereby reducing computational overhead.

• Example: In the code a = x * y + 5; b = x * y + 10;, the subexpression x * y is computed twice. CSE would compute temp = x * y; once, then rewrite the statements as a = temp + 5; b = temp + 10;.
• Interaction with DCE: CSE creates temporary variables that may become dead if all their uses are later eliminated by other optimizations, making them candidates for subsequent Dead Code Elimination.

Constant Propagation is an optimization that replaces variables known to have constant values with those literal values. Constant Folding is the subsequent evaluation of expressions consisting entirely of constants at compile time, replacing them with their single computed result.

• Mechanism: The compiler performs data-flow analysis to track variables assigned literal values. It then propagates these constants through the code, enabling folding (e.g., converting x = 3 * 5; into x = 15;).
• Creates Dead Code: This process often renders variables and calculations obsolete. For instance, after propagating and folding, an entire branch of code guarded by if (false) becomes unreachable, and variables used only within that branch become dead. This creates new opportunities for Dead Code Elimination to remove the now-redundant statements.

Loop-Invariant Code Motion is an optimization that identifies expressions within a loop whose values do not change across iterations and moves them outside the loop body to a preheader block. This avoids recomputing the same value repeatedly.

• Analysis: The compiler must prove the expression is invariant—its operands are constant or defined outside the loop—and that moving it does not change the program's semantics or cause exceptions.
• Synergy with DCE: After moving invariant code, the original computation inside the loop is replaced with a use of the precomputed variable. If that variable is only used within the now-optimized loop and nowhere else, it may become a candidate for Dead Code Elimination in a broader scope, especially if the loop itself is later removed or simplified.

Function Inlining is an optimization that replaces a function call site with the actual body of the called function. This eliminates the overhead of the call instruction, setup, and teardown, and exposes the function's internal logic to optimizations within the caller's context.

• Trade-off: It increases code size but often improves performance by enabling context-specific optimizations. Aggressive inlining is common in high-performance computing and kernel compilation.
• Generates Dead Code: Once inlined, local variables and logic within the function body become visible to the caller's optimizer. This often reveals dead code, such as parameters or calculations that are irrelevant in the specific caller's context. The subsequent Dead Code Elimination pass can then strip this now-redundant inlined code, mitigating the code size increase.

Unreachable Code Elimination is a specific, critical subset of Dead Code Elimination that removes code which can never be executed under any possible control flow. This is code that follows an unconditional branch (like a return, break, or goto) or is guarded by a condition that is statically proven to be always false.

• Control Flow Analysis: The compiler builds a control flow graph (CFG) of the program. Any basic block that has no incoming edges from a potentially executable predecessor is marked as unreachable and removed.
• Foundation for DCE: This is often the first and most straightforward step in a DCE pass. By pruning unreachable blocks, the compiler simplifies the CFG, which in turn may cause variables defined only in those blocks to become dead, enabling further elimination of their definitions elsewhere. It is essential for cleaning up code after optimizations like constant propagation.

Liveness Analysis is a fundamental data-flow analysis that determines for each variable and program point whether the variable's value will be used in the future before being overwritten. A variable is live at a point if there exists a path from that point to a use of the variable without an intervening redefinition.

• Core of DCE: Dead Code Elimination relies directly on the results of liveness analysis. A variable definition (e.g., x = 10;) is dead if the variable is not live immediately after the definition. The statement can be safely removed.
• Interaction with Register Allocation: The register allocator uses liveness information to determine when registers can be reused. Aggressive Dead Code Elimination performed before register allocation reduces the number of live variables, decreasing register pressure and minimizing costly register spilling to memory, which is critical for NPU performance.