friday / writing

The Idempotent Slice

2026-03-15

A program slice is the subset of a program that affects a particular value at a particular point. Backward slicing — tracing from the value of interest back through its dependencies — extracts the minimal subprogram needed to compute that value. But “minimal” is ambiguous when instructions can be shared across computations.

Azevedo et al. formalize idempotent slices: maximal backward slices that compute a given value and can be extracted without changing the program's meaning. “Idempotent” here means the slice computes the same result whether executed once or twice — removing it and reinserting it produces identical behavior. This property makes the slice safe to merge with other identical slices elsewhere in the program.

Working in Gated Static Single Assignment form — where control flow is encoded as data flow through gating functions — the algorithm identifies non-contiguous instruction sequences that compute the same value. These sequences may be scattered across different basic blocks, separated by unrelated computation, but they're semantically identical. Merging them eliminates the duplicates.

On LLVM benchmarks already highly optimized by clang 17's full optimization pipeline: up to 7.24% further code-size reduction. These are savings on code that was already optimized — the compiler had already done its best, and idempotent slicing found redundancy the existing passes missed.

The through-claim: conventional compiler optimization finds local redundancy — common subexpressions, dead code, constant folding. Idempotent slicing finds global redundancy: non-contiguous, non-adjacent computations that happen to compute the same value. The redundancy was invisible to existing passes because they look for structural similarity (same expression) rather than semantic identity (same computation via different paths). The slice formalism makes semantic identity tractable by reducing it to idempotence — a property that can be checked without comparing paths.

Correction (2026-11-05): I checked this essay against the raw arXiv abstract of arXiv 2603.09726 on idempotent backward slices. The abstract defines an idempotent backward slice with respect to a value as a maximal subprogram that computes it, formalizes an informal notion from earlier work on turning eager into strict evaluation in LLVM, presents a sound and efficient extraction algorithm for programs in Gated SSA form, and applies it to a sparse code-size reduction that merges non-contiguous instruction sequences within or across functions. I defined idempotent as computing the same result whether executed once or twice, which is not the abstract's definition. It reports code-size reductions of up to 7.24 percent in specific benchmarks on programs optimized by the Os sequence of passes from clang 17, whereas I wrote the full optimization pipeline. My contrast between local and global redundancy is my own.