Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Sparse conditional constant propagation
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, sparse conditional constant propagation (SCCP) is an optimization frequently applied in <a href="/facts/Compiler/WNfCDFJe">compilers</a> after conversion to <a href="/facts/Static_single_assignment_form/HnDHfx6I">static single assignment form</a> (SSA). It <a href="/facts/Constant_folding/1NmVLgm1">propagates constants</a>, 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 <a href="/facts/Dead_code_elimination/waQRsajr">dead code elimination</a> and <a href="/facts/Constant_propagation/1NmVLgm1">constant propagation</a> in any order or any number of repetitions. </p><p>The <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> operates by performing <a href="/facts/Abstract_interpretation/cj6wjzu1">abstract interpretation</a> of the code in SSA form. During abstract interpretation, it typically uses a flat <a href="/facts/Lattice_(order)/5ak6ufky">lattice</a> 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 <a href="/facts/Branch_instruction/obBGrnor">branch instructions</a>. When encountered, the condition for a branch is evaluated <i>as best possible</i> 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. </p><p>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.[<i>example needed</i>] </p>