Some kind of graph rewriting on the term is a promising idea, but I have no idea how that would look. I would like to hear more.
I have an example where sharing is a barrier to shortcut fusion.
In Stream fusion combinators like map, filter and so on are implemented as converting from list to streams, a stream transformer, then back to a list:
map f = unstream . map_s f . stream
Then the rewrite rule removes superfluous conversion:
{-# RULES stream . unstream = id #-}
So if you have map.map, this gets fused away:
map f . map g
= (inline map)
unstream . map_s f . stream . unstream . map_s g . stream
= (rewrite rule)
unstream . map_s f . map_s g . stream
However, this doesn't work once you introduce sharing:
let ys = map f xs in (map g ys, map h ys)
= (inline map)