An optimization is a justified change in representation, not merely an algebraic-looking rewrite.
By the end: Explain constant folding, propagation, dead work, aliasing constraints, and why fewer IR instructions need not mean faster code.
Start with a transformation you can audit
Constant folding evaluates a subtree whose operands are known constants. In x * (2 + 3), the addition can become five, while x remains unknown until execution. Our folder handles only numeric constant subtrees and uses the same 32-bit arithmetic as the evaluator and VM.
The lab checks binding and types before optimization. It must not erase an invalid program by replacing flag * 0 with zero. In the accepted pure integer subset, more algebraic rewrites could be valid, but the implemented pass is deliberately narrower so its behavior is easy to inspect.
Prove a local replacement from the leaves upward
A folding rule needs both a pattern and a reason the replacement means the same thing. For a binary node with two integer literal children, SmallExpr can compute their wrapped result and replace the entire node with one integer literal. The replacement preserves the value returned to the parent. A name does not match that pattern, even when the editor displays its current binding. This distinction separates constant folding over syntax from specialization to a particular environment, which would require a different contract.
Follow x * (2 + 3) from its leaves. The traversal returns the name x unchanged. It visits the addition's children, finds the integer literals two and three, and computes five. The multiplication now has children x and five. Because one child is a name, the traversal keeps the multiplication. The resulting tree is x * 5. At execution, LOAD x supplies four, PUSH supplies five, and MUL returns twenty. Only the addition moved from execution into translation; reading x did not disappear.
Only the literal child disappears
Original syntax trees, drawn schematically. Lines mean parent-child relationships; positions are not timing or memory addresses. The name x survives folding, so its value is still loaded during execution.
The same rule can expose another opportunity at a parent. For (2 + 3) * (4 - 1), the two child operations become five and three. After those recursive replacements, the root also has two integer literals, so multiplication becomes fifteen. The traversal must inspect the rebuilt children rather than only the original root's immediate children. One bottom-up traversal therefore folds several nested operations. It does not need a separate global search for every newly exposed arithmetic node in this expression tree.
Here is a local correctness argument that extends through the tree. A literal or name retains its value. Assume each transformed child returns the same value as its original child. If the parent remains an operation, applying the same operation to equal child values preserves the parent's value. If the parent becomes a literal, the folder uses exactly the operation the evaluator would have applied. This argument depends on agreement about integer wrapping and operand types. It is a structural argument, not a claim based on one successful run.
Typing comes before this transformation in the working pipeline. Consider flag * 0. Its tree has an arithmetic node, but flag resolves to a boolean, so checking rejects it. Replacing the whole expression with integer zero would hide a required error. Even a proposed arithmetic identity must state the domain on which it applies. SmallExpr accepts a boolean as a complete expression, but that does not permit arithmetic on booleans. The numeric folder also leaves boolean literal nodes alone rather than silently treating them as zero or one.
Compare the two successful examples in the editor before drawing a general conclusion. Select the child-folding preset, then the fully constant preset. Identify which parent receives a replacement child and which root disappears. Predict the bytecode counts before reading them. The first changes five instructions to three; the second changes seven to one. Count each leaf load or push and each arithmetic instruction. These counts verify what this emitter removed. They do not establish elapsed time, and the proof of value preservation comes from the operation rules rather than the count reduction.
What permits a literal replacement?
Candidate
Required evidence
Decision in this pass
2 + 3
Both children are integer literals; wrapped sum is 5.
Replace with integer literal 5.
x * 5
One child is a name, not a literal.
Retain LOAD x and multiplication.
flag * 0
Arithmetic requires integers; flag is bool.
Typing rejects before optimization.
(2 + 3) * (4 - 1)
Children fold to 5 and 3; their wrapped product is 15.
Replace the root after folding children.
These are syntax and typing obligations for SmallExpr. Knowing the editor currently binds x to four does not make x a literal.
A proof depends on the language
Reassociating floating-point addition can change rounding. Removing a call multiplied by zero can remove output, an exception, or nontermination. Reading through two pointers may reach the same storage, so a write through one can invalidate a cached read through the other. These are semantic questions, not failures of arithmetic notation.
Undefined behavior in some languages also changes the permitted reasoning. It is not a guarantee of a particular crash. Do not apply rules from a language with undefined signed overflow to our wrapping integer language, or assume that every compiler option preserves the same floating-point contract.
Identify the semantics that a rewrite would change
Integer constant folding must use the language's arithmetic, not the compiler author's preferred arithmetic. SmallExpr stores the signed representative of a result modulo two to the thirty-second power after every operation. Begin with 999 * 999 * 999 * 999, which fits the paired view's four-leaf limit. Left association first produces 998001, then 997002999. Both fit the signed range. Multiplying once more produces the mathematical integer 996005996001. Its signed wrapped result is negative, so replacing the tree with that negative value is correct here.
Check the final conversion explicitly. The positive mathematical product has remainder 3868550625 modulo 4294967296. That remainder exceeds the greatest signed value, 2147483647. Subtracting 4294967296 gives negative 426416671. The folder stores that integer in a literal node, and the emitter can push it directly. The input grammar's limit on decimal literal magnitudes does not restrict internal results to 999. A folded tree is an internal representation, so its negative constant need not be re-enterable as one decimal token in the source editor.
Fold using signed 32-bit wrapping
Left-associated stage
Mathematical result
Stored integer
999 * 999
998001
998001
998001 * 999
997002999
997002999
997002999 * 999
996005996001
-426416671
Final unsigned remainder
3868550625 modulo 4294967296
Subtract 4294967296 to obtain the signed value.
All numbers are dimensionless integers, not timings. The final fold can produce an internal negative literal even though input decimal tokens are bounded to 0 through 999.
A different arithmetic contract can invalidate a familiar rewrite. In floating-point arithmetic with rounding after each operation, grouping additions differently can change a result. As an illustrative decimal machine, retain three significant digits and round to nearest after each addition. Adding 1000 and negative 1000 first gives zero, then adding one gives one. Adding negative 1000 and one first rounds negative 999 exactly, then adding 1000 also gives one, so that particular example does not distinguish the groupings. Choosing a larger magnitude is necessary to expose the rounding loss.
Use 10000, negative 10000, and one instead on that same decimal machine. The left grouping cancels the large terms and returns one. The right grouping first forms negative 9999, which rounds to negative 10000 at three significant digits. The final addition then returns zero. This example states a rounding model rather than borrowing SmallExpr's integer rules. It explains why an optimizer needs permission or a stronger proof before reassociating floating-point operations. The arithmetic symbols alone do not determine which transformations preserve a language's results.
Effects require a different comparison. In separate pseudocode, a call that prints a line and returns seven, followed by multiplication by zero, returns zero and prints the line. Replacing everything with zero preserves only the numeric result. Keeping the call and replacing its arithmetic use with zero can preserve the message, provided the call still executes with the required ordering and behavior. If the call can throw or fail to terminate, those outcomes also matter. SmallExpr has no calls; this counterexample explains a restriction for a richer language.
Two distinct ways to lose equivalence
Contract
Original computation
Changed computation
Three-significant-digit decimal rounding
(10000 + -10000) + 1 returns 1.
10000 + (-10000 + 1) returns 0 after rounding the inner sum.
Call prints a line and returns 7
Call, then multiply by 0: returns 0 and prints a line.
Replace everything with 0: returns 0 without the line.
Keep the effect, simplify its numeric use
Call, then multiply by 0.
Execute the call with its required behavior, then use 0.
The decimal rounding machine and effectful call are separate illustrative models. Neither adds floating point or calls to SmallExpr.
To test your own proposed rewrite, name the observations that must remain equal before comparing instruction streams. For SmallExpr's accepted expressions, compare the returned typed value under valid bindings and the specified wrapping operations. For the effectful pseudocode, compare the output and whether execution returns as well. For the decimal example, calculate both intermediate rounded results. These are different proof obligations. A failed rewrite in one domain does not refute a valid rewrite in another, and a successful numeric test does not discharge an obligation about output or termination.
Work through the mechanism
Compare before and after folding
Presets replace the whole source. Editing replaces the current calculation and resets any execution trace. Names: x = 4, y = 7, flag = true. Use ASCII - for subtraction and negation. Arithmetic is signed 32-bit wrapping; booleans are not numbers. See lesson 1 for the full grammar and editor bounds. The paired optimization view accepts at most four leaves so both trees stay readable.
Type: int. Direct evaluation: 20. VM result: 20. Original instructions: 5; after folding: 3.
Original bytecode
LOAD x
PUSH2PUSH3ADDMUL
After folding
LOAD x
PUSH5MUL
Folded VM result: 20. Counts measure these abstract instructions, not elapsed time or native CPU instructions.
The output is recalculated immediately. This bounded compiler implements expressions only, not the later pseudocode examples. The entered source is never passed to JavaScript eval or Function.
Expression
Folded form
What remains dynamic
x * (2 + 3)
x * 5
Read x and multiply
(2 + 3) * (4 - 1)
15
Nothing in this pure expression
x * 0 + y
x * 0 + y
This pass does not apply algebraic identities
The last row is intentionally unchanged by this specific constant-folder pass.
Explore the boundary between folding and propagation
Use the paired experiment to distinguish a missing optimization from an incorrect optimization. Enter x * 0 + y. Every arithmetic node has a name somewhere among its children, so the implemented folder leaves the tree unchanged. With the fixed bindings, multiplication returns zero and addition returns seven. You may know an algebraic simplification to y for this pure integer language. The unchanged tree means that the pass lacks that rule, not that the simplification would necessarily violate the language. Correctness does not require discovering every valid simplification.
Now change only the source to x * (2 + 3), then to x * (y + 3). In the first tree, the addition folds because both children are integer literals. In the second, the addition keeps a name and remains dynamic. With the fixed bindings, the results are twenty and forty. Predict the instruction sequences too. The first emits five original instructions and three folded instructions; the second retains all five. The presence of parentheses is not the folding criterion.
Predict a changed tree before checking its counts
Source
Folded form
VM instructions before / after
Fixed-environment result
x * (2 + 3)
x * 5
5 / 3
20
x * (y + 3)
Unchanged
5 / 5
40
x * 0 + y
Unchanged
5 / 5
7
(2 + 3) * (4 - 1)
15
7 / 1
15
Count a PUSH or LOAD for each leaf and one instruction for each arithmetic node. The environment is x = 4 and y = 7; these are instruction counts, not speed ratios.
Do not try to change the environment through the expression input. That input has no assignment syntax, and the view fixes x, y, and flag. To reason about portability of the first replacement, use a separate paper calculation with a hypothetical integer x equal to seven. Both x * (2 + 3) and x * 5 then return thirty-five, while a proposed replacement with constant twenty fails. This counterexample distinguishes a reusable local fold from a specialization whose validity would depend on a stable environment assumption.
Constant propagation requires facts about definitions rather than merely literal children. In separate straight-line pseudocode, let a receive two, let b receive a plus three, and return b times four. A propagation analysis can associate a with two, replace its use, and expose a literal addition. Folding then produces five, which propagation can carry to b's use. The final multiplication can become twenty. This is a possible sequence of analyses and transformations, not a feature implemented by the expression editor. It requires a representation with definitions and uses.
A join changes the proof. Suppose one branch defines a as two and the other defines a as nine. A compiler cannot propagate two to a use after the join just because a chosen test run took the first branch. If both branches define a as two, the common fact can survive the join. If analysis proves one branch unreachable, that proof can also change the result. Static facts summarize possible executions under assumptions; an execution trace records one path. The source of a claimed constant determines which replacement is justified.
A constant must hold on every relevant incoming path
Separate branch pseudocode
Facts reaching the join
May replace a with 2?
Left defines a = 2; right defines a = 9.
Either 2 or 9, depending on the edge.
No, if both edges remain possible.
Left defines a = 2; right defines a = 2.
2 on both incoming edges.
Yes, under these definitions.
Left defines a = 2; right defines a = 9; right is proved unreachable.
Only the left definition can arrive.
Yes, if the reachability proof is valid.
A single run took the left edge.
Observed value 2 in that run only.
Not established for other runs.
This table compares static proof obligations with a dynamic observation. Branches and propagation are separate paper models, not implemented SmallExpr passes.
Complete the exploration by entering flag * 0 and then returning to x * 0 + y. The former produces a typing error before a valid optimization comparison; the latter remains accepted but unchanged. Explain that contrast without calling both cases optimizer failures. Then choose the fully constant preset and account for every removed instruction. The experiment provides exact trees, values, and instruction counts. The propagation and join examples are paper exercises for understanding additional analyses, not controls hidden elsewhere in this working model.
Analyses enable transformations but have costs
Constant propagation tracks known values through data flow. Dead-code elimination removes computations that cannot affect required behavior, subject to effects and termination rules. Common-subexpression elimination reuses results only when the computation and relevant state remain equivalent. Loop transformations need dependence analysis and other conditions.
A transformation can reduce one instruction count while increasing code size, register pressure, or cache misses. Pass order can expose or hide opportunities. The lab counts abstract bytecode instructions before and after folding; it makes no speed claim about a CPU, VM implementation, or real workload.
Separate a legal change from a profitable change
Common-subexpression elimination needs more than matching printed expressions. In separate memory pseudocode, read a cell through p, write nine through q, and read through p again. If p and q refer to the same cell, the second read observes nine, not the earlier value. Reusing the first read would be wrong. If analysis proves the references cannot alias, and no other relevant operation changes that cell, reuse may become legal. Aliasing means two references can designate the same storage; different names do not prove different storage.
Work the alias case with the initial cell containing four. The first read returns four. The write changes that very cell to nine. The second read returns nine, so adding the two read results gives thirteen. Replacing the second read by the first gives eight instead. For a nonaliasing comparison, let p designate a cell containing four and q a separate cell initially containing six. The write changes only q's cell. Both reads through p return four, and their sum is eight. The required distinction concerns object identity, not spelling.
A write can invalidate an earlier read
Operation
p and q designate the same cell
p and q designate separate cells
Initial memory
One shared cell contains 4.
p-cell contains 4; q-cell contains 6.
first = read(p)
first = 4
first = 4
write(q, 9)
Shared cell now contains 9.
q-cell becomes 9; p-cell remains 4.
second = read(p)
second = 9
second = 4
first + second
13
8
Replace second with first
8, which is wrong.
8, which agrees for this trace.
Exact sequential pseudocode trace with no other memory writes. Agreement in the separate-cell case illustrates a necessary memory fact; real reuse also requires excluding other relevant changes.
Legality still does not determine profitability. Reusing an earlier result extends the period during which that value must remain available. On a target with few usable registers, the compiler may need a spill and reload, or may prevent another value from remaining in a register. Recomputing a cheap expression can sometimes require less storage traffic. The next lesson makes simultaneous live values visible. For now, distinguish the semantic question, whether reuse preserves behavior, from the target-dependent question, whether keeping that result is worth its storage cost.
Even a large reduction in this lab's instruction count has a narrow interpretation. Changing seven abstract instructions to one removes six executed teaching-VM instructions for that expression. It is not a measured sevenfold speedup. A real interpreter has dispatch overhead and instruction-dependent costs; native code may use different instructions altogether. Measurement also includes work outside the expression, such as parsing or repeated invocation. Define the workload and timing boundary before claiming a performance improvement.
Pass order can alter which opportunities a compiler sees. Propagating known definitions can expose literal operands for folding. Folding a condition in a richer IR can expose an unreachable edge, which can simplify a join and reveal more constants. Eliminating dead work can shorten live ranges, while sharing results can lengthen them. These interactions explain repeated analyses without implying that any fixed sequence always wins. Each transformation must maintain its IR's validity, and any cached facts that it invalidates must be updated or recomputed before later passes rely on them.
Audit a proposed optimization with two separate records. First write its preconditions and the observable behavior it preserves. For the memory example, record whether aliasing is excluded and what can modify the cell between reads. Then write its expected resource changes, including retained values and code size, before seeking measurements. For SmallExpr folding, the first record can use a local structural proof and the second can list exact VM instructions. This division makes an unsupported speed claim easier to detect without confusing it with evidence that the transformation itself is wrong.
Keep the correctness argument separate from the cost argument
Change
Semantic obligation
Resource question
Fold literal arithmetic
Use the same typed wrapping operations.
How many emitted VM instructions disappear?
Reuse a memory read
Prove no relevant write changes its value.
Does keeping the result create spills?
Reuse a pure arithmetic result
Inputs and operation must retain their meaning.
Is retention cheaper than recomputation on this target?
Move a computation
Preserve dependencies, effects, and required failures.
Does the new schedule improve the measured workload?
A legal transformation can have an unfavorable cost. The SmallExpr comparison supplies exact abstract instruction counts, not native timing evidence.
Exercises
Fold, do not guess a variable
Fold x * (2 + 3) with the implemented pass. Why is the result not simply twenty even though the lab environment has x = 4?
Hint
This pass folds numeric literal subtrees, not environment-dependent names.
Worked answer
Only the literal addition is folded. Both trees retain a read of x.
Form
With x = 4
With x = 7
x * (2 + 3)
20
35
x * 5
20
35
Constant 20
20
20, wrong for x = 7
The tree comparison shows which subtree is actually folded.
It produces x * 5. The folder does not specialize to the current environment or replace x by four. Both original and folded forms produce twenty with x = 4, but they also agree for other valid integer x values. Treating a fixed UI example as a universal constant would make a different optimization.
A zero result can still have effects
In a language where logAndReturn() prints a message and returns an integer, may an optimizer always replace logAndReturn() * 0 with 0?
Hint
The returned number is only one observable part of the execution.
Worked answer
Version
Numeric result
Output
Call then multiply
0
Message remains
Replace whole expression
0
Message disappears
This is an effectful-language counterexample, not a SmallExpr function call.
No. The replacement removes the call and therefore its message. Other calls may throw or fail to terminate. A compiler might simplify the arithmetic while retaining required effects, but deleting the whole computation needs a proof that those effects do not matter under the language contract.
Sources and further reading
The explanations, examples, and worked answers are complete without these optional links. The sources describe specific implementations and language contracts, not one universal compiler pipeline. SmallExpr and the later pseudocode models are constructed teaching examples. Source notes identify the selected material reviewed; this is not an exhaustive compiler survey, production conformance test, or independent specialist review.
Selected material on IR structure, SSA, phi semantics, integer operations, and semantic constraints. A production IR reference, not a specification of SmallExpr or a claim that every compiler uses LLVM.
Selected overview and register-allocation material describing instruction selection, target constraints, liveness, and native-code generation. The storage lab is not an implementation of LLVM’s allocator. The reviewed register-allocation example has inconsistent def/use prose; the lesson follows explicit assignment direction instead.