Introduction

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.

Try It: Watch Dead Branches Vanish

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

<!-- CFG visualization: entry block sets x and y as constants, branch checks z = x+y > 10 -->
<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">
  <!-- Control-flow graph: entry → branch → (big block | small block) -->
  <div class="node entry" id="node-entry">
    <div class="node-title">Entry block</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">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">true (z > 10)</div>
    </div>
    <div class="fork-right">
      <div class="arrow diag-right" id="arr-false"></div>
      <div class="arrow-label" id="lbl-false">false (z ≤ 10)</div>
    </div>
  </div>
  <div class="block-row">
    <div class="node block" id="node-big">
      <div class="node-title" id="title-big">Big block (z > 10)</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">Small block (z ≤ 10)</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">Propagate</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status"></div>

/* Styles for the SCCP constant propagation visualizer */
* { 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; }

// SCCP constant propagation demo: x and y are input constants, z = x+y is computed, then branch is resolved
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Lattice states for SCCP: UNKNOWN = unvisited (bottom), CONST = known value, OVER = overdefined (top)
// UNKNOWN = bottom of lattice, CONST = known value, OVER = overdefined (top)
const UNKNOWN = 'unknown';
const OVER = 'over';

let propagated = false;

function getX() { return parseInt(document.getElementById('xslider').value, 10); }
function getY() { return parseInt(document.getElementById('yslider').value, 10); }

function updateSliderLabels() {
  // Sync slider labels and entry-block display with current slider values
  document.getElementById('xval').textContent = getX();
  document.getElementById('yval').textContent = getY();
  document.getElementById('disp-x').textContent = getX();
  document.getElementById('disp-y').textContent = getY();
}

function resetView() {
  // Clear propagation state: remove live/dead styling, reset lattice badges, clear status
  propagated = false;
  ['node-big', 'node-small'].forEach(id => {
    const n = document.getElementById(id);
    n.classList.remove('dead', 'alive');
  });
  ['lat-x', 'lat-y', 'lat-z'].forEach(id => {
    const b = document.getElementById(id);
    b.textContent = '?';
    b.className = 'lat-badge';
  });
  document.getElementById('status').textContent = '';
  document.getElementById('status').className = 'status';
}

function setBadge(id, val) {
  // Update a lattice badge: unknown=?, overdefined=top symbol, constant=its value
  const b = document.getElementById(id);
  if (val === UNKNOWN) { b.textContent = '?'; b.className = 'lat-badge'; }
  else if (val === OVER) { b.textContent = '⊤'; b.className = 'lat-badge over'; }
  else { b.textContent = String(val); b.className = 'lat-badge const'; }
}

function propagate() {
  // Run one SCCP pass: fold x and y as constants, compute z, resolve the conditional branch
  const x = getX();
  const y = getY();
  const z = x + y;

  // Step 1: propagate x and y as constants, derive z
  setBadge('lat-x', x);
  setBadge('lat-y', y);
  setBadge('lat-z', z);

  // Step 2: the branch condition is now a constant — mark exactly one successor live
  const zGt10 = z > 10;
  const bigNode = document.getElementById('node-big');
  const smallNode = document.getElementById('node-small');

  if (zGt10) {
    // z > 10: true branch is live, false branch is dead
    bigNode.classList.remove('dead'); bigNode.classList.add('alive');
    smallNode.classList.remove('alive'); smallNode.classList.add('dead');
    document.getElementById('status').textContent = i18nFmt('z = %z% > 10 → true branch is live, small block is dead.', { z: z });
    document.getElementById('status').className = 'status ok';
  } else {
    // z <= 10: false branch is live, true branch is dead
    smallNode.classList.remove('dead'); smallNode.classList.add('alive');
    bigNode.classList.remove('alive'); bigNode.classList.add('dead');
    document.getElementById('status').textContent = i18nFmt('z = %z% ≤ 10 → false branch is live, big block is dead.', { z: z });
    document.getElementById('status').className = 'status info';
  }
  propagated = true;
}

document.getElementById('btn-propagate').addEventListener('click', propagate);
document.getElementById('btn-reset').addEventListener('click', () => { resetView(); updateSliderLabels(); });
document.getElementById('xslider').addEventListener('input', () => { updateSliderLabels(); if (propagated) propagate(); });
document.getElementById('yslider').addEventListener('input', () => { updateSliderLabels(); if (propagated) propagate(); });

// Initialize with default slider values
updateSliderLabels();
Result
Console

Notice what happens: as soon as the compiler pins down z=x+yz = 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 xx or yy so the sum crosses 10 and watch the opposite branch die instead.

The Real Complexity

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 kk, 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)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/constant-propagation/Content licensed under CC BY-NC 4.0.