computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

, sparse conditional constant propagation (SCCP) is an optimization frequently applied in

compiler In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...

s after conversion to

static single assignment form In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR) that requires each variable to be assigned exactly once and defined before it is used. Existing var ...

(SSA). It simultaneously removes some kinds of

dead code The term dead code has multiple definitions. Some use the term to refer to code (i.e. instructions in memory) which can never be executed at run-time. In some areas of computer programming, dead code is a section in the source code of a program whic ...

and propagates constants throughout a program. 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 (also known as DCE, dead-code removal, dead-code stripping, or dead-code strip) is a compiler optimization to remove code which does not affect the program results. Removing such code has several benefits: ...

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 rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

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 prog ...

of the code in SSA form. During abstract interpretation, it typically uses a flat

lattice Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an ornam ...

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 instruction A branch is an instruction in a computer program that can cause a computer to begin executing a different instruction sequence and thus deviate from its default behavior of executing instructions in order. ''Branch'' (or ''branching'', ''branc ...

s. 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