julia icon indicating copy to clipboard operation
julia copied to clipboard

Add a Global Value Numbering Pass

Open Zentrik opened this issue 10 months ago • 7 comments

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.

Zentrik avatar Aug 30 '23 19:08 Zentrik