A compiler's reaching definitions analysis determines that variable x is assigned the constant value 5 on every path reaching a loop body, and x is not modified inside the loop. Which optimization applies, and what dataflow analysis enables it?
ADead code elimination, enabled by liveness analysis showing x is never used after the loop
BConstant propagation, enabled by reaching definitions analysis proving x always holds the value 5 at each use
CLoop-invariant code motion, enabled by dominator analysis showing the assignment dominates the loop header
DRegister allocation, enabled by an interference graph showing x has a short live range
Reaching definitions analysis tracks which variable definitions reach each program point. If only one definition of x — the assignment x = 5 — reaches every use inside the loop, the compiler can safely replace every use of x with the literal 5, eliminating the variable. This is constant propagation. Reaching definitions is exactly the dataflow analysis that proves the substitution is safe (no other value reaches those use sites). Loop-invariant code motion would apply to expressions computed inside the loop whose operands don't change; here x is already a known constant, so its uses are simply replaced.
Question 2 Multiple Choice
After optimization, a compiled program runs 15% faster but produces slightly different output on certain inputs compared to the unoptimized version. How should this be classified?
AA valid optimization — performance gain justifies small deviations in output
BA valid optimization for floating-point operations, which have inherent imprecision
CA compiler bug — preserving observable behavior is an absolute constraint on all optimizations
DAcceptable for machine-dependent optimizations but a bug in machine-independent ones
The fundamental invariant of code optimization is that observable behavior must be preserved — no exceptions. An optimization that changes program output is definitionally a compiler bug, not a performance-correctness tradeoff. Observable behavior includes outputs, side effects, and for concurrent programs, certain operation orderings. Options A, B, and D all treat correctness as negotiable — this is the key misconception to reject. The correctness constraint is what distinguishes a safe transformation from a program-corrupting bug.
Question 3 True / False
Machine-independent optimizations like constant propagation and dead code elimination are applied during target-specific code generation to the instruction sequences of the target architecture.
TTrue
FFalse
Answer: False
Machine-independent optimizations are applied to the intermediate representation (IR) — before any target-specific code generation. They operate on an abstract, architecture-neutral program representation and produce improvements that apply regardless of the target hardware. Machine-dependent optimizations (register allocation, instruction scheduling, peephole optimization) are what target specific hardware, applied during or after code generation. The distinction reflects the compiler pipeline: IR-level transformations first, then architecture-specific optimizations.
Question 4 True / False
Applying constant propagation to a program may create opportunities for dead code elimination that would not have been detectable before constant propagation ran.
TTrue
FFalse
Answer: True
Optimizations interact: the output of one creates conditions for another. Constant propagation replaces variables with their known constant values. If a branch condition becomes a known constant (effectively 'if (false)'), the unreachable branch is now detectable as dead code — but before constant propagation, the branch condition appeared to depend on a variable, making that branch appear live. Dead code elimination can then remove it. This chaining is why compilers run optimization passes in sequences and repeat them until no further improvements are found.
Question 5 Short Answer
Why must every compiler optimization be justified by a dataflow analysis that proves the transformation is safe to apply?
Think about your answer, then reveal below.
Model answer: Optimizations eliminate, reorder, or replace computations. Doing this incorrectly changes the program's observable behavior — making it a bug rather than an optimization. Dataflow analysis provides the formal proof that a transformation is safe: reaching definitions proves a constant substitution is valid (no other value reaches the use site); liveness analysis proves a computation is dead (its result is never subsequently used); available expressions analysis proves a reused value is still current (no intervening modification of its operands). Without this proof, an 'optimization' might eliminate a live computation, reuse a stale value, or hoist a non-invariant expression — corrupting the program.
Consider common subexpression elimination: replacing a second computation of (a + b) with the first result is only safe if neither a nor b has been modified between the two computations. Available expressions analysis tracks exactly this — an expression is 'available' at a point if it was computed on every reaching path and its operands were not subsequently modified. Without this analysis, CSE might reuse a stale result after a was reassigned, producing wrong output while appearing to be a legitimate optimization. The correctness constraint requires formal proof, and dataflow analysis provides that proof.