[Compilers] Introduction and Common Optimizations

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…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.