A new GVN for IonMonkey



IonMonkey's new GVN

  • Full redundance only (same as before)
  • Pessimistic (old was optimistic, but didn't eliminate loop phis)
  • Structured to enable more cascading optimizations.
  • Usually single-pass
  • The SSA id() is the value number
  • Integrated unreachable code elimination (coming soon)

GVN algorithm overview

  • hash(opcode, operands, extra info)
  • Check dominance
  • Let reverse postorder be your guide
  • Fold and eliminate as you go

Reverse Postorder

Example RPO graph

Just re-run the whole pass

No need to remember how to rewind! Re-running is fairly uncommon The pass is fast, so running it twice isn't too bad

The code

Most of the code and complexity is for unreachable code removal. The actual GVN parts are very simple.