What do constant folding and constant propagation each do to a block of straight-line code?
answer
- two rewrites that feed each other
- compiler does the arithmetic itself
- known value moved to its uses
- sweep until nothing changes
- two literals merging lose the constant
basics
~20 sConstant folding evaluates an operation whose operands are all literals and replaces the expression with the result. Constant propagation replaces a use of a variable with the literal every reaching definition assigns it. Each creates work for the other, so pipelines iterate them.
solid answer
~40 sThey are a pair. **Folding** does arithmetic at compile time: `100 * 4` becomes `400`, and a comparison of two literals becomes a true or false literal. **Propagation** does no arithmetic at all; it is a data-flow analysis that asks, for each use of a variable, whether every definition reaching that use assigns the same literal, and if so rewrites the use to that literal. Folding needs literals in operand positions and propagation puts them there; propagation needs known values and folding produces new ones. So a pipeline runs them together and iterates to a fixed point — until a full sweep changes nothing. Where two branches assign different literals, the facts collapse to `not a constant` at the merge and nothing is substituted past it.
code
pseudocode · 17 lines// before
rate = 100
window = 4
scale = rate * window
threshold = scale / 8
for each row in batch:
if row.value > threshold:
emit(row)
// after propagation and folding have reached a fixed point
rate = 100 // now unused, left for elimination
window = 4 // now unused, left for elimination
scale = 400 // now unused, left for elimination
threshold = 50 // now unused, left for elimination
for each row in batch:
if row.value > 50:
emit(row)go deeper
Recall the split: folding computes, propagation substitutes. Being able to say which of the two turned 100 * 4 into 400 is the floor here.
Explain why the two are run as a loop rather than once each, and walk a short block to a fixed point out loud, naming what each step unlocked for the next.
Show where folding must decline — faulting operations and arithmetic the target defines differently — and what the pair sets up for elimination and for branch removal downstream.
Frame it as pipeline economics: these are the cheap normalising passes, so the interesting question is how often to re-run them after heavyweight transforms before the compile-time budget stops paying.
## What each rewrite does **Constant folding** is a local rewrite. When every operand of an operation is a literal the compiler already knows, the compiler performs the operation itself and replaces the whole expression with its result. `100 * 4` becomes `400`; `400 / 8` becomes `50`; a comparison between two literals becomes a true or false literal that a branch can then consume. **Constant propagation** is an analysis plus a rewrite. For each *use* of a variable it asks whether every definition that can reach that use assigns the same literal. If so, the use is replaced by that literal. Propagation computes nothing itself; it only carries a value already known to the place it is needed. Neither is worth much alone. Folding needs literals in the operand positions, and propagation is what puts them there; propagation needs known values, and folding is what manufactures new ones. Compilers therefore run the two together and iterate to a **fixed point** — repeating until a complete sweep changes nothing. ## A worked block Take a numeric kernel inside a batch report generator: ``` rate = 100 window = 4 scale = rate * window threshold = scale / 8 for each row in batch: if row.value > threshold: emit(row) ``` The sweep runs like this: 1. Propagation substitutes `rate` and `window`, giving `scale = 100 * 4`. 2. Folding evaluates that, giving `scale = 400`. 3. Propagation substitutes `scale`, giving `threshold = 400 / 8`. 4. Folding evaluates that, giving `threshold = 50`. 5. Propagation substitutes `threshold` into the comparison, giving `if row.value > 50`. Four of the five steps were only possible because the step before it fired. Notice also what is left behind: `scale` and `threshold` now have no remaining uses, and the assignments that produce them are debris. Removing them is a dead-code elimination pass's job, not this pair's, which is one reason the three are scheduled next to each other. ## The value lattice and the merge rule An analysis that tracks "what constant does this variable hold here" carries one of three facts per variable per program point: | fact | meaning | when it arises | |---|---|---| | **unknown so far** | no definition examined yet | the optimistic starting assumption | | **exactly c** | every definition examined assigns the literal `c` | a single literal assignment, or several that agree | | **not a constant** | the value is not fixed at compile time | two definitions disagree, or the value comes from input | Where control flow merges, the facts arriving on the incoming edges are combined. *Exactly 2* meeting *exactly 2* stays *exactly 2*. *Exactly 2* meeting *exactly 3* collapses to *not a constant* — which is why a variable assigned different literals in the two arms of a conditional is left alone after the join. The merge is order-independent: it does not matter which arm the analysis visited first. A refinement, usually called conditional constant propagation, interleaves the two passes more tightly: branch conditions are folded *during* the analysis, and an edge whose condition folded to false is treated as never executed, so the definitions on it never reach the merge at all. That can turn a value which looks non-constant into a constant. ## Where folding has to stop Folding is arithmetic the compiler performs on the target machine's behalf, so it is legal only where the compiler can reproduce the target's semantics exactly. - **Operations that can fault.** Folding a division by a literal zero would move a fault from run time — where a guard might mean it never executes — to compile time. Pipelines generally leave such an expression alone and wait for a later pass to prove the path unreachable. - **Arithmetic the target defines its own way.** Fixed-width wraparound, saturation, shift-count behaviour and floating-point rounding must be modelled as the *target* performs them, not as the machine running the compiler does. Toolchains differ in how much floating-point reassociation they will permit at all, and several allow it only under an explicit relaxation. - **Values that only look fixed.** A read of storage another thread or device can change is not a literal, however constant it appears in the source. ## Why the pair earns its place The visible saving — a couple of multiplications lifted out of a report kernel — is the smallest part of the payoff. What matters is what becomes *provable* afterwards: a folded loop bound turns into a known trip count, a folded condition makes one arm of a branch unreachable, and a constant argument carried into a body after inlining is frequently the entire reason inlining paid for itself. Folding and propagation are cheap, they normalise the intermediate form, and that is why a pipeline runs them repeatedly rather than once.
- What does folding a branch condition buy that folding an arithmetic expression does not?A folded condition makes one successor edge unreachable. That deletes a whole region of code rather than one operation, removes the merge that was collapsing other variables to `not a constant`, and can turn a loop with a folded bound into a known trip count. It is the cheapest way a pipeline turns one known value into a structural simplification.
- Why might an expression with two literal operands still be left unfolded?Because folding it would change observable behaviour or cannot be reproduced faithfully. A division by a literal zero would raise a fault at compile time that the running program might never have reached; fixed-width or floating-point arithmetic must be evaluated exactly as the target defines it, not as the compiling machine does. When the compiler cannot guarantee that, it declines.
- When does this pair stop being a single-block affair?Folding is local — it needs only the operands in front of it. Propagation needs to know which definitions reach a use, so beyond one straight-line block it needs a data-flow analysis over the control-flow graph, with a merge rule at every join. Carrying constants across function boundaries needs either a summary of the callee or inlining first.
saying these in an interview costs you the question
- Says constant propagation evaluates the expression; that is folding.
- Thinks one pass of each is enough, without iterating.
- Claims a variable assigned 2 on one branch and 3 on the other folds to a value.
- Folds a division by a literal zero at compile time.
- Assumes the compiler's own arithmetic matches the target machine's.