Compilation Methods lecture notes.

00_CompilationMethods.md

Lecture

01_Optimization.md

Optimization

Reduce run-time and/or code size of the program, without changing its observable effects.

• Transformations

  • Algebraic simplification x^2 = xx x+0 = x x2 = x << 1
  • Constant Propagation x = 2 ... y = x+5
  • Common subexpressions a = 5y+3 b = 5y+4
  • Dead variables a = b+c a = 5
  • Copy propagation x = y z = x => z = y
  • Dead code b = true if b: x=5 else: y=7
  • Code motion if c: x = (a+b)*2 else: x = (a+b)/2
  • Function inlining int sqr(x): xx; a = sqr(5) => a = 55;
  • Loop invariant while (...): ... x = 5 ...
  • Induction variables in loops i = 1 while (...): k = i*3 f(k) i = i+1

• Static Analysis

• Context Analysis

• Methods

  • Control-flow graph

    • Basic Block: Maximum sequence of instructions that can be entered and exited only at one point.
    • Properties
      • Dominator relation
        • immediate dominator tree)
        • every block has a single immediate dominator
      • Loop recognition
      • Hierarchical reduction
    • Transformations
      • Dead code elimination
      • Code motion
      • Loop optimization
        • Pre-header for invariants

  • data-flow information

  • use-def relations

  • data dependecy graph

  • dominator-tree loops

  • call graph

• Data-Flow-Analysis Problems

  • Forward
    • along the control flow
  • Backward
    • against the control flow
  • Union
    • there is a path
  • Intersect
    • for all paths
  • Optimization information

02_CodeGeneration.md

Code Generation

Storage Mapping

• Array Implementation

  • Pointer Tree

  • Contiguous Storage

    Index map: start + (...((i1-l1)*st2 + (i2-l2))*st3 ...)*stn + (in-ln))*elsz

• Run Time Stack

  • Activation Record

      Result
      Parameters
      Static Link
      Return Address
      Dynamic Link
      Local Variables
      Register Save Area
    

    • Static Link
    • Dynamic Link
    • Closure: has to be on the runtime stack when the function is called

  • Not Most Recent Property

Code Selection

• Code Sequences
• Value Descriptor
• Pattern Matching
  • Bottom-Up Rewrite System

Register Allocation

03_RegisterAllocation.md

Register Allocation

04_Parallelization.md

Parallelization

Instruction Scheduling

• Data Dependence Graph
• List Scheduling
• Pipelining

Loop Transformation

• Loop carried dependencies u-->v
  • Flow u wrties before v uses
  • Anti u uses before v overwrites
  • Output u writes before v overwrites
• Loop unrolling
• Software Pipelining
• Itteration Spaces
• Dependency Vector