Constant Propagation

Every time you compile a program, your compiler quietly discards code that could never run. The trick that makes this possible is called constant propagation: the compiler tracks which variables are always the same value, rewrites every expression that depends on them, and then throws away any branch whose condition is already decided.

The idea is surprisingly old. You can trace it to simple constant folding — replacing 2 + 3 with 5 at compile time — but the powerful modern form is Sparse Conditional Constant Propagation (SCCP), introduced by Mark Wegman and Frank Kenneth Zadeck in 1991. SCCP walks the control-flow graph (CFG) of a function, marking each variable with one of three states on a lattice: unknown (not yet seen), constant (always the same value), or overdefined (different values reach this point). Whenever a value collapses to a constant, every expression and every branch that depends on it is immediately updated.

The payoff is dramatic: a whole if block can vanish because the compiler proved its condition is always false. The code that was compiled away never runs, never wastes memory, and never hides a bug.

The demo below shows a tiny control-flow graph with three variables ($x$, $y$, $z$) and two conditional branches. Set the values of $x$ and $y$ with the sliders, then click Propagate to run SCCP.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label>x = <span id="xval">3</span>
    <input type="range" id="xslider" min="0" max="15" value="3">
  </label>
  <label>y = <span id="yval">5</span>
    <input type="range" id="yslider" min="0" max="15" value="5">
  </label>
</div>
<div class="cfg" id="cfg">
  <!-- {{c_cfg_comment}} -->
  <div class="node entry" id="node-entry">
    <div class="node-title">{{lbl_entry}}</div>
    <div class="node-body">
      <div class="stmt" id="st-x">x = <span class="val" id="disp-x">3</span></div>
      <div class="stmt" id="st-y">y = <span class="val" id="disp-y">5</span></div>
      <div class="stmt" id="st-z">z = x + y</div>
    </div>
  </div>
  <div class="arrow-row">
    <div class="arrow down" id="arr-entry-branch"></div>
  </div>
  <div class="node branch" id="node-branch">
    <div class="node-title">{{lbl_branch}}</div>
    <div class="node-body">
      <div class="stmt">if z &gt; 10</div>
    </div>
  </div>
  <div class="arrow-row fork">
    <div class="fork-left">
      <div class="arrow diag-left" id="arr-true"></div>
      <div class="arrow-label" id="lbl-true">{{lbl_true}}</div>
    </div>
    <div class="fork-right">
      <div class="arrow diag-right" id="arr-false"></div>
      <div class="arrow-label" id="lbl-false">{{lbl_false}}</div>
    </div>
  </div>
  <div class="block-row">
    <div class="node block" id="node-big">
      <div class="node-title" id="title-big">{{lbl_big_block}}</div>
      <div class="node-body">
        <div class="stmt">result = z * 2</div>
      </div>
    </div>
    <div class="node block" id="node-small">
      <div class="node-title" id="title-small">{{lbl_small_block}}</div>
      <div class="node-body">
        <div class="stmt">result = z + 1</div>
      </div>
    </div>
  </div>
</div>
<div class="lattice-row" id="lattice-row">
  <div class="lat-cell">
    <span class="lat-var">x</span>
    <span class="lat-badge" id="lat-x">?</span>
  </div>
  <div class="lat-cell">
    <span class="lat-var">y</span>
    <span class="lat-badge" id="lat-y">?</span>
  </div>
  <div class="lat-cell">
    <span class="lat-var">z</span>
    <span class="lat-badge" id="lat-z">?</span>
  </div>
</div>
<div class="btns">
  <button id="btn-propagate" type="button">{{btn_propagate}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; gap: 1.2rem; flex-wrap: wrap; margin-bottom: .8rem; }
.controls label { font: 600 14px system-ui; display: flex; align-items: center; gap: .4rem; }
.controls input[type=range] { width: 90px; }
.cfg { display: flex; flex-direction: column; align-items: center; gap: 0; }
.node { border: 2px solid #1d3557; border-radius: 10px; min-width: 160px; background: #eef2f6; transition: opacity .4s, border-color .4s; }
.node-title { background: #1d3557; color: #fff; font: 700 12px system-ui; padding: .2rem .6rem; border-radius: 7px 7px 0 0; text-align: center; }
.node-body { padding: .35rem .65rem; }
.stmt { font: 500 13px ui-monospace, monospace; line-height: 1.6; }
.val { font-weight: 700; color: #0a7d33; }
.arrow-row { display: flex; justify-content: center; align-items: flex-start; min-height: 22px; }
.arrow.down { width: 2px; height: 22px; background: #1d3557; }
.arrow-row.fork { justify-content: space-around; width: 260px; margin-top: 0; }
.fork-left, .fork-right { display: flex; flex-direction: column; align-items: center; gap: 2px; }
.arrow.diag-left, .arrow.diag-right { width: 2px; height: 28px; background: #1d3557; transform: rotate(-20deg); }
.arrow.diag-right { transform: rotate(20deg); }
.arrow-label { font: 600 11px system-ui; color: #1d3557; }
.block-row { display: flex; gap: 1rem; justify-content: center; }
.node.dead { opacity: .28; border-color: #aaa; }
.node.dead .node-title { background: #aaa; }
.node.alive { border-color: #0a7d33; }
.node.alive .node-title { background: #0a7d33; }
.lattice-row { display: flex; gap: 1rem; justify-content: center; margin: .7rem 0 .5rem; }
.lat-cell { display: flex; align-items: center; gap: .3rem; }
.lat-var { font: 700 14px ui-monospace, monospace; }
.lat-badge { font: 700 13px ui-monospace, monospace; background: #dde4ec; color: #1d3557; padding: .1rem .45rem; border-radius: 5px; min-width: 32px; text-align: center; transition: background .3s, color .3s; }
.lat-badge.const { background: #0a7d33; color: #fff; }
.lat-badge.over { background: #c92f3c; color: #fff; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font: 600 14px system-ui; min-height: 1.4em; margin-top: .5rem; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }

// Code not found

Notice what happens: as soon as the compiler pins down $z = x + y$ as a constant, it can evaluate if z > 10 without executing the program. The branch whose condition is false is marked dead and its block is grayed out — that code will never appear in the compiled output. Change $x$ or $y$ so the sum crosses 10 and watch the opposite branch die instead.

Constant propagation sounds like it should be expensive — tracking every variable through every path of a program — but the SCCP algorithm is remarkably efficient.

• The lattice has only three levels. Every variable starts as unknown ($\bot$), may settle to a single constant value $k$, and if two different constants could reach the same variable it becomes overdefined ($\top$). Because the lattice only goes down (unknown → constant → overdefined), each variable can change state at most twice during the whole analysis.
• Sparse representation. The "sparse" in SCCP means the algorithm only revisits a node when something it depends on actually changed. Work is proportional to the number of edges in the CFG times the lattice height, which gives $O(E)$ time — near-linear in the size of the program.
• Conditional branches are tracked separately. A naive analysis might assume both branches of an if are executable. SCCP keeps a second worklist for branches: a branch is only marked executable once its predecessor is executable. Dead branches are never explored, so the analysis is not fooled by code that can never run.
• It is strictly more powerful than simple constant folding. Simple folding evaluates expressions but does not prune branches. SCCP can discover a constant inside a branch that simple folding would miss because it assumed the branch might be taken.

The result: a solved, polynomial-time problem that delivers outsized wins. SCCP is now a standard pass in production compilers such as GCC, LLVM, and the Java HotSpot JIT. Learn how it works and you've seen program analysis at its most elegant.

Constant propagation is not an academic curiosity — it is one of the workhorses of every production compiler:

• Dead-code elimination: once SCCP marks a branch dead, the compiler can legally remove it. The final binary is smaller, caches are happier, and there is simply less code for a bug to hide in.
• Constant folding and strength reduction: knowing x is always 4 lets the compiler replace x * x with 16 and x * 8 with a shift — cheaper instructions, no runtime math.
• Inlining and devirtualization: in object-oriented languages, if a call's receiver type is proven constant, the compiler can inline the right method and skip the virtual dispatch.
• JIT compilers: JavaScript engines like V8 and SpiderMonkey use type-specializing variants of constant propagation to generate fast machine code for dynamic languages; when the engine learns a variable is always an integer, the slow generic path disappears.
• Static analysis and verification: constant propagation underlies tools that detect dead conditions, always-true assertions, and unreachable error paths — real bugs that show up as unreachable code.

Master constant propagation and you have a window into program synthesis and the broader world of program equivalence — the deep question of whether two pieces of code always compute the same thing.

Constant propagation is the compiler's version of thinking ahead. Instead of generating code for every possible runtime value, the compiler asks: do I already know what this variable is? When the answer is yes, an entire branch of the program — sometimes a large one — can be quietly deleted before the program ever runs.

SCCP achieves this in near-linear time by exploiting the simple three-level lattice and by refusing to explore branches that are provably dead. The result is smaller binaries, faster execution, and programs that carry only the code that can ever be reached.

The next time your debugger tells you a line is unreachable, a constant propagation pass already knew that — and quietly cleaned it up. That is program analysis doing its job invisibly, millions of times a day.