Dead Code Elimination (DCE)

Dead Code Elimination is a compiler optimization pass that identifies and removes code that does not affect the program's final output. It operates by performing liveness analysis and reachability analysis on the program's Intermediate Representation (IR) or computational graph.

• Liveness Analysis: Determines if the result of an operation (a variable or tensor) is ever read by a subsequent, live operation before the program terminates.
• Reachability Analysis: Traverses the graph from the output nodes backward, marking all operations that contribute to an output. Unmarked nodes are unreachable and thus dead.

For example, in a neural network graph, a tensor produced by an intermediate layer that is never consumed by the loss function or any downstream output node is identified as dead code and can be pruned.

DCE can be applied at different stages of the compilation pipeline, with varying levels of precision and required analysis.

• Static DCE: Performed at compile time (Ahead-Of-Time Compilation) by analyzing the static structure of the computational graph. It relies on Static Shape Inference and constant propagation to identify code provably dead for all possible executions. This is the most common form in NPU compilers.
• Dynamic DCE: Hypothetically, code could be eliminated at runtime (Just-In-Time Compilation) based on profile data or specific input values. However, pure dynamic DCE is rare; more commonly, Profile-Guided Optimization (PGO) informs more aggressive static DCE decisions for future compilations.

The effectiveness of static DCE is limited by the compiler's ability to analyze control flow and data dependencies statically.

DCE is most powerful when applied to code in Static Single Assignment (SSA) Form. SSA simplifies dataflow analysis because each variable is defined once, making it trivial to trace uses of a value.

DCE also has a symbiotic relationship with other compiler passes:

• Constant Folding & Propagation: Turns variables into constants, potentially rendering the code that uses them dead.
• Common Subexpression Elimination (CSE): Creates new, single-use variables for previously redundant computations, which DCE can then eliminate if those uses become dead.
• Inlining: Can expose new dead code opportunities within the inlined function body.

These passes often run in a loop within the compiler's optimization pipeline, repeatedly creating new optimization opportunities for each other.

In the context of Neural Processing Unit Acceleration, DCE is a critical early-stage graph optimization. It cleans the computational graph before hardware-specific passes, leading to significant efficiency gains.

• Memory Planning: By removing dead tensors and their associated operations, DCE reduces the peak memory usage calculated by the Memory Planning pass, allowing larger models or batch sizes to fit in limited NPU memory.
• Kernel Fusion & Scheduling: A simpler graph with fewer nodes reduces the search space for Graph Fusion and Operator Clustering passes, and simplifies scheduling decisions.
• Binary Size Reduction: Eliminating unused operations directly reduces the size of the compiled kernel binary deployed to the NPU, important for edge devices with constrained storage.

DCE is often applied after graph lowering and canonicalization but before aggressive fusion and layout transformations.

The application and impact of DCE differ markedly between training and inference compilation scenarios.

• Inference Graphs: The graph is typically a forward pass only. DCE aggressively prunes any branch or operation not on the path from input to the specified output node(s). This includes unused alternative branches in conditional logic and debugging or logging operations.
• Training Graphs: The graph includes the forward pass, loss calculation, and the backward pass (Automatic Differentiation). DCE must preserve all operations necessary to compute gradients for trainable parameters. However, it can eliminate:
  • Activations not needed for the backward pass (addressed more comprehensively by Activation Recomputation).
  • Gradients for non-trainable parameters or frozen layers.
  • Operations in the forward pass that do not contribute to the final loss or to gradients of trainable parameters.

This makes DCE for training more complex but still highly beneficial.

A compiler must guarantee that DCE is safe, meaning it does not alter the program's semantics. Key challenges and limitations include:

• Side Effects: The primary constraint. Operations with side effects (e.g., writing to a file, printing to console, updating a global state) must never be eliminated, even if their output is unused. In ML graphs, most pure mathematical operations are side-effect-free.
• Precision of Analysis: Conservative analysis may leave some dead code (e.g., code behind a complex condition the compiler cannot statically resolve). Overly aggressive analysis risks removing live code.
• Debug Symbols & Instrumentation: Code inserted for profiling or debugging (e.g., operations that write to a telemetry buffer) may be intentionally side-effecting and must be preserved if instrumentation is enabled.
• Dynamic Control Flow: Graphs with data-dependent control flow (e.g., dynamic tf.cond or torch.jit.script conditions) limit static DCE's ability to prune branches.

Modern compilers use well-defined semantics for side effects to perform DCE safely and effectively.

Static Single Assignment (SSA) is a critical intermediate representation property where each variable is assigned exactly once. This form drastically simplifies dataflow analysis, which is a prerequisite for many optimizations. By ensuring each variable has a single definition point, the compiler can unambiguously trace the flow of values, making it far easier to identify dead code (variables that are defined but never used) and perform constant propagation. Most modern ML compilers, including those for NPUs, convert graphs to SSA form early in the optimization pipeline to enable powerful transformations like DCE.

Common Subexpression Elimination (CSE) is a compiler optimization that identifies and eliminates redundant computations. It analyzes the computational graph to find expressions that are calculated multiple times with the same inputs. The compiler then computes the expression once, stores the result, and reuses it. While DCE removes code that produces unused results, CCE removes code that performs duplicate calculations of used results. Both are redundancy elimination techniques, but they target different types of waste: unused outputs versus repeated computations.

Constant folding evaluates expressions consisting entirely of compile-time constants, replacing them with their computed result. Constant propagation then pushes these known constant values through the graph, substituting variables with their constant values. This process often creates new opportunities for DCE. For example, propagating a constant may turn a conditional branch into a known path, making the other branch dead code. Similarly, folding a computation may render its output unused, allowing DCE to remove it. These passes form a synergistic optimization loop.

Peephole optimization is a low-level, local optimization that examines short sequences of instructions (a 'peephole') and replaces them with more efficient sequences. It operates on a much finer granularity than graph-level DCE. Examples include removing redundant moves (x = x) or replacing a multiply by a power of two with a shift. While DCE removes entire nodes or blocks, peephole optimization cleans up inefficiencies within the code that remains after high-level passes. It is often one of the final optimization steps before code generation.

Graph canonicalization is a compiler transformation that rewrites a computational graph into a standard, simplified form. It eliminates syntactic variations that do not affect semantics, such as collapsing identity operations or normalizing operator attributes. This process is a crucial precursor to DCE and other analyses. By putting the graph into a predictable canonical form, the compiler ensures that optimizations behave consistently and can reliably identify equivalent patterns—like recognizing that an operation whose output feeds only into an identity node is a candidate for elimination.