julia
julia copied to clipboard
Add a Global Value Numbering Pass
This enables common subexpression elimination, fixes #50887. This is based on the NewGVN pass in LLVM.
A possible avenue for increasing the number of eliminations would be to implement code hoisting (eg. an expression that is also present in all predecessors to a block could be moved to the immediate dominator and then replaced; alternatively we could replace it with a phi node) or Partial Redundancy Elimination.
I'm not sure when it would be optimal for this pass to run, the effects of a function may allow a non inlined call to be eliminated completely whilst when inlined only parts may be deleted.
For small functions most of the time is spent on allocating two arrays (ssa_to_ssa
and the array backing val_to_ssa
). For larger functions the get!
dominates, #51091 speeds up get!
2x. I don't think there any easy optimizations left, one possible avenue would be computing use lists (a list of every instruction in which a SSAValue
is used) and using that to not have to iterate over every instruction.