CompilersOptimizationsEasy

Constant Folding

Master the fundamental concepts of optimizations through this focused micro-challenge.

~30 minutes Optimizations Ready to learn

Topic Overview

Fold Constants at Compile Time

Constant folding evaluates expressions with compile-time-known operands. Even -O0 Clang folds 2 + 3 to 5. JavaScript minifiers like Terser apply it on every production bundle. It enables further propagation and dead code removal.

What to Fold

Arithmetic, comparisons, and bitwise ops on literals. Boolean logic. Some sizeof and address-difference expressions in C. Stop before division by zero (may be runtime error) or side-effecting calls.

c
Loading…

Work on IR or AST after constant propagation
Re-run after other opts expose new constants
Float folding respects IEEE rounding mode flags
Conditional folds enable unreachable code elimination

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will implement constant folding on your IR. This exercise requires detecting instructions whose operands are all constants, replacing them with a single constant result, and enabling follow-on optimizations.

Implementation Task

Your Task

Implement constant folding together with constant propagation over straight-line code: evaluate every sub-expression whose operands are known constants at compile time, and substitute variables whose current value is a known constant.

Input

One assignment per line (blank lines ignored):

c
Loading…

EXPR uses integer literals, variable names, + - * / %, < <= > >= == !=, unary - and parentheses, with C precedence (comparisons lowest, then + -, then * / %, then unary -); binary operators are left-associative. Arithmetic is 64-bit signed; / and % truncate toward zero; comparisons give 1 or 0.

Rules

Propagation: a variable whose most recent assignment folded to a constant is replaced by that constant. After an assignment whose value is not a constant, the variable is unknown again. Variables never assigned are unknown.
Folding: bottom-up, an operator whose operands are all constants is replaced by its result. Nothing else is simplified: no algebraic identities (x * 1 stays) and no reassociation: x + 1 + 2 is (x + 1) + 2, which does not fold.
A / or % by a constant 0 is not folded (the program must still fault at run time); report it.

Output

Each assignment after optimisation, with the right-hand side printed as an S-expression: a constant or name as itself, (OP A B) for binary operators, (neg A) for unary minus. Append ; constant when the whole right-hand side folded to a constant. For a division by constant zero, print ; warning: division by zero instead.

Finish with folded=F propagated=P: F counts operator nodes replaced by constants, P counts variable uses replaced by constants.

Example

Input:

c
Loading…

Output:

c
Loading…

In d, a - 20 becomes 20 - 20 and folds to 0; b * c can't fold because c is unknown.

Requirements

Parse each right-hand side into a tree, then fold it with one recursive function that returns the (possibly new) node.
A table of known constant values, updated after every assignment.

Hidden tests cover comparisons, unary minus, negative results with / and %, a variable losing its constant value, and division by a constant zero.