In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, sparse conditional constant propagation (SCCP) is an optimization frequently applied in
compiler
In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primaril ...
s after conversion to
static single assignment form (SSA). It
propagates constants, which is the calculation of static values which can be calculated at compile time. Moreover, it can find more constant values, and thus more opportunities for improvement, than separately applying
dead code elimination
In compiler theory, dead-code elimination (DCE, dead-code removal, dead-code stripping, or dead-code strip) is a compiler optimization to remove dead code (code that does not affect the program results). Removing such code has several benefits: i ...
and
constant propagation in any order or any number of repetitions.
[Click, Clifford and Cooper, Keith.]
Combining Analyses, Combining Optimizations
, ''ACM Transactions on Programming Languages and Systems'', 17(2), March 1995, pages 181-196
The
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
operates by performing
abstract interpretation
In computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. It can be viewed as a partial execution of a computer pro ...
of the code in SSA form. During abstract interpretation, it typically uses a flat
lattice of constants for values and a global environment mapping SSA variables to values in this lattice. The crux of the algorithm comes in how it handles the interpretation of
branch instructions. When encountered, the condition for a branch is evaluated ''as best possible'' given the precision of the abstract values bound to variables in the condition. It may be the case that the values are perfectly precise (neither top nor bottom) and hence, abstract execution can decide in which direction to branch. If the values are not constant, or a variable in the condition is undefined, then both branch directions must be taken to remain conservative.
Upon completion of the abstract interpretation, instructions which were never reached are marked as dead code. SSA variables found to have constant values may then be inlined at (propagated to) their point of use.
Notes
References
* Cooper, Keith D. and Torczon, Linda. ''Engineering a Compiler''. Morgan Kaufmann. 2005.
{{Compiler optimizations
Compiler optimizations