Compiler Optimizations

Optimization is a bit of a misnomer here, a better word is “better”

Optimizations vs Dataflow Analysis

Optimizations

• Transform the program
• Informed by analyses
• Not much math Dataflow Analyses
• Do not change the program
• Provides information
• Lots of math Dataflow analyses inform our optimizations

In math, optimization is defined mathematically and compilers are an empirical engineering discipline.

ECE 351 optimization

Almost any question small enough to put on an exam can be done in your head, without any equations through intuition. This is good because we know what answer our equations should be producing. These optimizations are performed at compile time.

Stages of Progression for Dataflow Analysis

• By intuition
  • Just how I would try to make my code DRY when refactoring. Doing this also intuitively puts things into Three Address Code
• With equations (without loops or branches)
  • We solve these equations using substitution
• With equations (with loops and/or branches)
  • Substitution no longer works, we need to solve these using fixed-point iteration

I believe these are technically LLVM optimizations:
Optimization Step-By-Step:

• Convert the AST to Three Address Code
• Dataflow Analysis (different types)
• Actually transform the AST
  • Common Subexpression Elimination (enabled at LLVM level 1)
  • Copy Propagation
  • Dead Store Elimination

Related

• Dataflow Analysis

Performance in Rust

The idea here, is we want to get out of the compilers way so it can do its job. Add the following to the cargo.toml

[profile.release]
lto = true

Most of Rust’s optimization takes place in the backend LLVM compiler.

The -C opt-level sets inline limits and passes a requested optimization level to the backend:

• 0: no optimizations
• 1: basic optimizations
• 2: some optimizations
• 3: all optimizations
• “s”: optimize for binary size
• “z”: optimize for binary but turn off loop vectorization

LLVM Optimizations

Scalar Optimizations

Basically why do something later when you can do it now. If something can be computed at compile time, compute it so we don’t generate the runtime code (example: math on two constant numbers).

• Common Subexpression Elimination
• Copy Propagation
• Dead Store Elimination / redundant code optimizations

Loop Optimizations

These are profitable when loops execute often, which is common in programs. The trick is finding which loops are important. A loop induction variable is a variable that varies on each iteration of a loop. Induction variable elimination gets rid of extra induction variables.

Scalar Replacement

We learned this in ECE351 but I can’t find the note. Basically the idea is that is something like a[i] doesn’t change between reads, we can replace it with a single read to temp and references to temp.

Loop Unrolling

This lets the processor run more code without having to branch as often. Software pipelining is an optimization which allows multiple iterations of a loop to proceed in parallel. This is useful for SIMD. Intuitively, this does what we normally wouldn’t want to do, hard code the contents of a loop for all enumerations.

Loop Interchange

Changes the nesting of loops to coincide with the ordering of array elements in memory. Rust might be in “row-major” order language but this isn’t guaranteed?

Loop Fusion

If we iterate over the same condition or array etc in two different loops, we can merge these together and do it once. Sometimes the opposite “loop fission” will improve performance.

Loop Invariant Code Motion

See Loop Invariant Code Motion.

Low Level Optimizations

• Branch predictions
• You can mark a method as unlikely to be called (but not in Rust)
• You can usually make architecture specific optimizations as well