Implement Code Optimisation Stage, Part 1 - Local Optimisation

[aalhour]

Code Optimization

Three main types in Compiler Research:

1. Local Optimization: Basic Blocks level.
2. Regional Optimization - won't be implemented.
3. Global Optimization.
4. Inter-Procedural Optimization - won't be supported.

Local Optimisation:

• Algebraic Expressions Simplification:

   x = x + 0    =>   x = x
   x = x * 1    =>   x = x
   x = x * 0    =>   x = 0
   x = x + 8    =>   x = x << 3
   x = x ** x   =>   x = x * x
  

• Constant Folding:

    a = 2 * 3   =>   a = 6
    b = 1 + 2   =>   b = 3
  

• Dead Code Elimination. Dead code is code that does't contribute to the program's result.

• Peephole Optimisations.

• SSA-based Optimisations:

  • Ensure registers (or variables in IR) are assigned once, in all computations.
  • Common Subexpression Elimination:

   a = x * x
   ...
   d = x * x    =>   d = a
  

  • Copy Propagation:

    b = x       =>    gets eliminated and all references changed to "x"
    c = b * 2   =>    c = x * 2
    

  • Constant Propagation:

    a = 2       =>   *eliminated*
    b = a + 2   =>   b = 2 + 2   =>    b = 4
    c = b * 3   =>   c = 4 * 3   =>    c = 12