Compiler

Parser: Builds AST from string
Optimizer: Transform the program to make it better
CodeGen: Transforms from compiler representation to assembly or machine code

Optimizer

Compute information about a program + Use that information to perform program transformations

Representations

• Abstract Syntax Tree
• Control Flow Graph
• Dataflow Graph
• Static Single Assignment
• Control Dependence Graph
• Program Dependence Graph
• Call Graph

Analysis/Transformation Algorithms

• Dataflow Analysis
• Interprocedural Analysis
• Pointer Analysis

Applications

• Scalar Optimizations
• Loop Optimizations
• Object Oriented Optimizations
• Program Verification
• Bug Finding

…

Common Optimizations

Constant Propagation: Replacing uses of constant variables with the constant value itself
Constant Folding: Precomputing constant values with simple operators
Strength Reduction: Replacing MULT with SHL

Common Subexpression Elimination: Replace use of common expressions with LHS of first appearance of the expression –> need guarantee that values of LHS and RHS are not modified between the two identical expressions
Partial Redundancy Elimination: Sometimes redundant expression could be eliminated…
Copy Propagation: If LHS of a copy operation is used later, it can be replaced –> need guarantee that values of LHS and RHS are not modified

Dead Assignment Elimination: Unused assignment can be removed
Dead Code Elimination: Unreachable code can be eliminated

Branch Folding, Range Analysis, Pointer/Alias Analysis, Loop Invariant Code Motion, Inlining…