The Idempotent Slice

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.