In what cases is graph rewriting not enough to avoid duplicate work?
Consider this program:

f (m : Nat) x y = (x, if H(m,m) then x else y)

my_f = f my_number
my_f hard harder


where H(x,x) returns True if Turing machine number x halts on input x and False otherwise. Detecting duplicate work (always) would mean solving the halting problem, no matter whether you want to do the analysis statically or dynamically.

Hence, no method can be complete.