This is identical to what LLVM's load-store motion does for 
  loads, except for all expressions and not just loads.

It's actually not. It's what GVNHoist does, but not MLSM. MLSM only handles diamonds.

In any case, because the GCC implementation is written on top of a sane PRE infrastructure, it is like 50 lines of code to do this :)