Overview of Compilers

Goals

• Correctness: generated code must behave exactly as the source code specifies
• Performance: the code should run fast

Compiler Structure

• Front end: parses source code into an Intermediate Representation - IR
• Code Generator: turns IR into machine code
  • An optimizing compiler adds an optimizer in the middle that transforms the IT to be more efficient

Control Flow Graph

How Optimizations Improve Performance

$$ \text{Execution time = Number of Instruction Cycles * CPI * Time/Cycle} $$

• Fewer instructions: optimizations like constant folding or dead code elimination directly reduce the number of instructions executed
• Lower CPI: optimizations like instruction scheduling or improving cache behaviour (i.e., via loop transformations) ensure the CPU pipeline is kept busy and memory accesses are fast

Basic (Machine-Independent) Optimizations

• Constant propagation: Replacing a variable with its known constant value
• Constant folding: Calculating constant expressions at compile time (i.e., 5+3 turning into 8)
• Common subexpression elimination: Identifying and computing redundant calculations only once
• Copy propagation: Replacing the use of a variable with the variable it was copied from
• Dead code elimination: Removing code that can never be executed (i.e., code inside if(false) or after a return)