[DSE] Fix bug in partial overwrite tracking

Summary:
Found cases where DSE incorrectly add partially-overwritten intervals.
Please see the test case for details.

Reviewers: mcrosier, eeckstein, hfinkel

Subscribers: mcrosier, llvm-commits

Differential Revision: http://reviews.llvm.org/D21859

llvm-svn: 274237

1 files changed, 14 insertions, 7 deletions

diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
index 595a556b505..6b648ee23cc 100644
--- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
@@ -385,18 +385,25 @@ static OverwriteResult isOverwrite(const MemoryLocation &Later,
     // Find any intervals ending at, or after, LaterIntStart which start
     // before LaterIntEnd.
     auto ILI = IM.lower_bound(LaterIntStart);
-    if (ILI != IM.end() && ILI->second < LaterIntEnd) {
-      // This existing interval ends in the middle of
-      // [LaterIntStart, LaterIntEnd), erase it adjusting our start.
+    if (ILI != IM.end() && ILI->second <= LaterIntEnd) {
+      // This existing interval is overlapped with the current store somewhere
+      // in [LaterIntStart, LaterIntEnd]. Merge them by erasing the existing
+      // intervals and adjusting our start and end.
       LaterIntStart = std::min(LaterIntStart, ILI->second);
       LaterIntEnd = std::max(LaterIntEnd, ILI->first);
       ILI = IM.erase(ILI);
 
-      while (ILI != IM.end() && ILI->first <= LaterIntEnd)
-        ILI = IM.erase(ILI);
-
-      if (ILI != IM.end() && ILI->second < LaterIntEnd)
+      // Continue erasing and adjusting our end in case other previous
+      // intervals are also overlapped with the current store.
+      //
+      // |--- ealier 1 ---|  |--- ealier 2 ---|
+      //     |------- later---------|
+      //
+      while (ILI != IM.end() && ILI->second <= LaterIntEnd) {
+        assert(ILI->second > LaterIntStart && "Unexpected interval");
         LaterIntEnd = std::max(LaterIntEnd, ILI->first);
+        ILI = IM.erase(ILI);
+      }
     }
 
     IM[LaterIntEnd] = LaterIntStart;