This patch is the (rewritten) mechanical part of D21007 to avoid problems with iterator invalidation.
The test committed with http://reviews.llvm.org/rL273141 is removed because this patch no longer performs any type of back tracking, which is what was causing the codegen differences with and without debug information.
No correctness issues across SPEC2000, SPEC2006, and llvm-test-suite. In fact, there were no codegen changes across this suite of benchmarks. However, codegen changes are possible because we no longer backtrack when the current instruction is deleted.
FWIW, I'm in the process of trying to port DSE to use MemorySSA and I thought pushing this change sooner rather than later would simplify my life. Sorry to hijack your change, Eli.