Sparse conditional constant propagation
Encyclopedia
In computer science
, sparse conditional constant propagation is an optimization frequently applied in compiler
s after conversion to static single assignment form
(SSA). It simultaneously removes some kinds of dead code
and propagates constants
throughout a program. However, it is strictly more powerful than applying dead code elimination
and constant propagation in any order or any number of repetitions.
The algorithm
operates by performing abstract interpretation
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 into 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 as 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.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, sparse conditional constant propagation is an optimization frequently applied in compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
s after conversion to static single assignment form
Static single assignment form
In compiler design, static single assignment form is a property of an intermediate representation , which says that each variable is assigned exactly once...
(SSA). It simultaneously removes some kinds of dead code
Dead code
Dead code is a computer programming term for code in the source code of a program which is executed but whose result is never used in any other computation...
and propagates constants
Constant folding
Constant folding and constant propagation are related compiler optimizations used by many modern compilers. An advanced form of constant propagation known as sparse conditional constant propagation can more accurately propagate constants and simultaneously remove dead code.- Constant folding...
throughout a program. However, it is strictly more powerful than applying dead code elimination
Dead code elimination
In compiler theory, dead code elimination is a compiler optimization to remove code which does not affect the program results. Removing such code has two benefits: it shrinks program size, an important...
and constant propagation in any order or any number of repetitions.
The algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
operates by performing abstract interpretation
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 program which gains information about its semantics In...
of the code in SSA form. During abstract interpretation, it typically uses a flat lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
of constants for values and a global environment mapping SSA variables to values into 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 as 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.