CD Notes
Complete guide to constant folding optimization covering compile-time evaluation, constant expressions, type handling, and interaction with other optimizations in the compilation pipeline.
What is Constant Folding?
Constant folding is a compiler optimization that evaluates constant expressions at compile time rather than runtime. When the compiler can determine that all operands of an expression are constants, it computes the result during compilation and replaces the expression with the computed value.
Basic Examples
| Before constant folding | After constant folding: |
| t1 = 3 + 5 | t1 = 8 |
| t2 = t1 * 2 | t2 = 16 (if t1 is known constant 8) |
| t3 = 2 ** 10 | t3 = 1024 |
Constant Folding Rules
Arithmetic
const1 OP const2 → result (evaluate at compile time)
x + 0 → x (identity)
x * 1 → x (identity)
x * 0 → 0 (annihilation)
x - x → 0 (self-subtraction)
x / x → 1 (self-division, x≠0)
0 / x → 0 (zero dividend)
Logical
true AND x → x
false AND x → false
true OR x → true
false OR x → x
NOT true → false
NOT false → true
Relational
5 < 10 → true
3 == 3 → true
7 > 10 → false
Bitwise
x AND 0 → 0
x OR 0 → x
x XOR 0 → x
x AND ~0 → x (all ones)
x XOR x → 0
x << 0 → x
0 << n → 0
Cascading Constant Folding
| c = a + b | c = 5 + 3 → c = 8 (fold) |
| d = c * 2 | d = 8 * 2 → d = 16 (fold) |
| e = d - 1 | e = 16 - 1 → e = 15 (fold) |
| if (e > 10) | if (15 > 10) → if (true) (fold) |
| f = e + a | f = 15 + 5 → f = 20 (fold) |
Floating-Point Constant Folding
Unsafe
Unbounded result, can include infinitely many tuples.
Safe
Finite result bounded by known relations.
Constant Folding in Control Flow
Compile-time branch evaluation
Before: After:
if (2 > 3) { // entire if-block eliminated
x = expensive_call(); // (dead code)
} else {
x = 42; x = 42;
}
Loop elimination
for (i = 0; i < 0; i++) { // loop never executes
process(i); // entirely eliminated
}
While loop
while (false) { // eliminated
do_something();
}
Switch folding
switch (3) { x = 30; // only matching case
case 1: x = 10; break;
case 2: x = 20; break;
case 3: x = 30; break; // this one
default: x = 0;
}
Implementation
| if I is of the form | x = const1 OP const2: |
| replace I with | x = result |
| else if I is of the form | x = OP const1 (unary): |
| replace I with | x = result |
| else if I is of the form | if const RELOP const goto L: |
| if result is true | replace with unconditional goto L |
| if result is false | delete the instruction |
| else if I is of the form | x = y OP z: |
| if y is marked constant | replace y with its value |
| if z is marked constant | replace z with its value |
| if both now constant | fold as above |
Interaction with Other Optimizations
| 1. Constant Propagation | enables → Constant Folding |
| a = 5; b = a + 3 | b = 5 + 3 → b = 8 |
| 2. Constant Folding | enables → Dead Code Elimination |
| if (true) x=1; else x=2; | x=1; (dead code removed) |
| 3. Constant Folding | enables → Branch Optimization |
| 4. Inlining | enables → Constant Folding |
| inline f(5) where f(x) = x*2 | body becomes 5*2 → 10 |
| 5. Loop Unrolling | enables → Constant Folding |
Compile-Time vs Runtime Constants
Compile-time constants (always foldable)
#define SIZE 100 // preprocessor constant
const int MAX = 50; // C const (if visible)
enum { RED=1, BLUE=2 }; // enum constants
sizeof(int) // known at compile time
alignof(struct S) // known at compile time
Runtime values (NOT foldable)
scanf("%d", &x); // user input
rand() // runtime function
time(NULL) // changes every call
volatile int v; // may change externally
Partially foldable
const int n = 10;
int a[n]; // n is compile-time in C++, not in C
constexpr int f() {...} // C++ constexpr: compile-time function
Interview Questions
- Q: Is constant folding always safe?
A: For integers, yes (overflow is defined or implementation-defined in most contexts). For floating point, it depends on rounding modes and exception behavior. For division by zero, the compiler must not fold (it would hide a runtime error). The compiler must match target semantics exactly.
- Q: How does constant folding differ from constant propagation?
A: Constant propagation replaces variable references with their constant values (a=5; b=a → b=5). Constant folding evaluates expressions with constant operands (b=5+3 → b=8). They work together: propagation feeds folding, and folding may enable more propagation.
- Q: Can constant folding occur at link time?
A: Yes! Link-Time Optimization (LTO) can fold constants that become known after inlining across compilation units. For example, if function f(x)=x*2 is in one file and the call f(5) is in another, LTO can inline and fold to get 10.
- Q: What is constexpr in C++ and how does it relate to constant folding?
A: constexpr guarantees that a function or variable CAN be evaluated at compile time. The compiler MUST constant-fold constexpr expressions in contexts requiring compile-time values (template arguments, array sizes). Regular constant folding is opportunistic; constexpr is mandatory.
- Q: How do modern compilers handle overflow during constant folding?
A: For unsigned integers, wrapping is defined behavior — fold with modular arithmetic. For signed integers in C/C++, overflow is undefined behavior, so the compiler may assume it doesn't happen (enabling optimizations) or may fold using two's complement. Java requires two's complement folding for all integers.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Constant Folding Optimization in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, code, optimization, constant, folding
Related Compiler Design Topics