3.3.1 IR Normalization & Cleanup Passes

[Mathnerd314]

Desired function
Maintain IR invariants expected by downstream algorithms and tools.

Futamura role
Normalizes (i)’s internal representation so specialization and compilation see a reasonably canonical IR.

Inputs

• IR graphs that may violate local invariants after transformations.

Processing

• Dead code elimination, unreachable block removal.
• Recursion-to-loop conversion when beneficial.
• Strength reduction for expensive operations.
• Defunctionalization where desired to separate control and data.
• Canonicalization of patterns, elimination of dangling edges, enforcing SSA/sea-of-nodes invariants.
• Code motion and other standard local optimizations
  • removal of unused parameters
  • replacement of parameters passed by reference by parameters passed by value.
  • replace standard functions with faster alternatives when possible
  • inlining
  • deduplication of constants, functions, code sequences (tail merging / cross jumping)
  • common subexpression elimination (CSE)
  • dead code/store eliminate (DCE/DSE)
  • conditional dead code elimination (DCE) for calls to built-in functions that may set errno but are otherwise free of side effects
  • global constant and copy propagation
  • constant propagation - which values/bits of values passed to functions are constants, function cloning
  • value range propagation - like constant propagation but value ranges
  • sparse conditional constant propagation (CCP), including bit-level
  • elimination of always true/false conditions
  • move loads/stores outside loops
  • loop unrolling/peeling
  • loop exit test
  • cross-jumping transformation
  • constant folding
  • specializing call dispatch (possible targets, likely targets, test/branch)
  • Code hoisting - evaluate guaranteed-evaluated expressions as early as possible
  • copy propagation - eliminate unnecessary copy operations
  • Discover which variables escape
  • partial/full redundancy elimination (PRE/FRE)
  • modified/referenced memory analysis, points-to analysis, aliasing
  • strips sign operations if the sign of a value never matters
  • convert initialization in switch to initialization from a scalar array
  • termination checking
  • loop nest optimizer based on the Pluto optimization algorithms. It calculates a loop structure optimized for data-locality and parallelism.
  • graphite - loop distribution, loop interchange, unroll, jam, peel, split, unswitch, parallelize, copy variables, inline to use first iteration values, predictive commoning, prefetch
  • final value replacement - loop to calculation using initial value and number of loop iterations
  • explode structures to scalars in registers
  • vectorization - loop vectorization, basic block vectorization, cost free (for debugging), likely faster, or code size
  • reorder blocks, duplicate blocks, partition into hot/cold to improve paging and cache locality
  • specialization of division operations using knowledge of the denominator

Outputs

• Canonical IR suitable for specialization, verification, and codegen.