We can break down optimizations into a series of rewrite patterns which make code into semantically equivalent and ideally faster code, a small example is constant folding where computing 1 + 1 is equivalent to 2 and thus any occurrences can be replaced with this simpler form. Let's walk through some more simple passes:
As we've already discussed this is how constant expressions are converted into constant values.
print((1 << 32) - 1)
// optimizer:
// 1 << 32 = 4294967296
//
// 4294967296 - 1 = 4294967295
//
// therefore:
// print(4294967295)
CSE is when two identical instructions take in identical inputs and produce identical outputs so we only compute the result once and use it multiple times.
return (x * x) + (y * y) + (x * x)
// optimizer:
// (x * x) is used twice, merge them
//
// therefore:
// xx = x * x
// return xx + (y * y) + xx
Some passes (such as constant folding, CSE or DCE) work to simplify code and avoid noise in bigger passes like inlining or loop unrolling which means there's a benefit to running simple passes after any complex pass. This would come at a time complexity cost since all of these passes would be O(n) (since they at least check all instructions). We could simplify this if each complex pass tracked its changes and thus we only need to run simple passes on changed IR and now the time complexity of the entire set of function passes is the O(m) where m is all the changed instructions.
convert into IR
// do set of function level passes
changed_ir = { literally all instructions }
cfg_dirty = true
doms = {}
i = 0
repeat
// if there's any cfg changes, we
// update the doms, canonicalizing
// doesn't affect the cfg.
if cfg_dirty
doms = get_doms(function)
cfg_dirty = false
// CSE, fold, DCE, ld/st ops
// only try canonicalization on
// changed instructions
for i in changed_ir
canonical(function, doms, i)
// run actual pass
changed_ir, cfg_dirty = passes[i](function);
i = i + 1
until is_empty(changed_ir)
return function