[DSE] Remove stores in the same loop iteration

[dmgreen]

Summary

DSE will currently only remove stores in the same block unless they can be guaranteed to be loop invariant. This expands that to any stores that are in the same Loop, at the same loop level. I believe this should still account for where AA/MSSA will not handle aliasing between loops, but allow the dead stores to be removed where they overlap in the same loop iteration. It requires adding loop info to DSE, but that looks fairly harmless.

The test case this helps is from code like this, which can come up in certain matrix operations:

  for(i=..)
    dst[i] = 0;
    for(j=..)
	  dst[i] += src[i*n+j];

After LICM, this becomes:

for(i=..)
  dst[i] = 0;
  sum = 0;
  for(j=..)
    sum += src[i*n+j];
  dst[i] = sum;

The first store is dead, but is not currently removed.

[fhahn]

Thanks for the patch! Given that this only shifts the invocation of LI, there shouldn't be any problems in terms of compile time.

I'm not sure how well the loop cases are covered in multiblock-loops.ll, but I think it might be worth to add a few more interesting cases that we can and can't optimize, especially with stores to different indices.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1324

Can LI just be part of DSEState?

2063

Should also preserve LoopAnalysis?

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1432–1434

I'm not sure this logic is correct. The problem I see is that LoopInfo only tracks natural loops. This means that even though Current and KillingDef might be in the same natural loop (say the nullptr loop), Current might still be part of a (non-natural) cycle, in which case KillingDef may not kill it.

I'm not particularly familiar with LoopInfo, but that's my understanding of how it works.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1432–1434

I'm not sure this logic is correct. The problem I see is that LoopInfo only tracks natural loops. This means that even though Current and KillingDef might be in the same natural loop (say the nullptr loop), Current might still be part of a (non-natural) cycle, in which case KillingDef may not kill it.

I'm not particularly familiar with LoopInfo, but that's my understanding of how it works.

Yes I think that's correct. There might be cycles that LoopInfo does not detect. So we should not rely on comparing the loops on its own.

If there is no loop for a given block, they still might be in a cycle that has not been detected by LoopInfo due to irreducible control flow; if there's a loop for a given block, it could be in a cycle that's completely contained in the loop we found. If LI finds a loop for a block, I think it is guaranteed that the loop is only entered through the header though.

I think this should allow us to treat the phis in the header as being in the same iteration or invariant in any undetected cycles in the loop.

[dmgreen]

Add a ContainsIrreducibleLoops flag, Move LoopInfo and add some irreducible tests.

[dmgreen]

Thanks for the patch! Given that this only shifts the invocation of LI, there shouldn't be any problems in terms of compile time.

It should iterate the same amount too, so I'm hoping it's OK. (But I have no evidence one way of the other).

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1432–1434

Ah, excellent point. I had not considered irreducible loops and they are not the kind of thing that naturally comes up in testing. (Unfortunately I feel like all the testing I could try would already have been run by Florian before DSE was committed, and it didn't show anything then just as it would not show any problems now. csmith didn't feel like much help). I was originally more worried about opening the door to any number of unrelated issues coming up from allowing DSE from different blocks where both LI's return nullptr.

For the moment, I have added a check using mayContainIrreducibleControl on the function and bailing if there are any. What do you think? Too much of a blunt hammer, or an OK way to handle this?

[nikic]

Could you please rebase this? The patch doesn't apply cleanly to main. (Insert rant here about Phabricator not providing 3way patches, making it impossible to resolve conflicts when applying.)

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1432–1434

I think that's a good way to handle it. Dealing with irreducible control flow in full generality is unlikely to be worthwhile.

Might want to extract this condition into a separate function, as it's getting a bit hard to read...

[dmgreen]

Rebase and move the condition logic into the start of IsGuaranteedLoopInvariant.

[nikic]

Compile-time: http://llvm-compile-time-tracker.com/compare.php?from=da627258742ae638b813d0341f069d5b4a6bd9ae&to=6c119f84a7fa3d6ea3b82e89d482c31836d5126f&stat=instructions

There is some impact, with the largest regression being sqlite3 with ThinLTO. I expect the reason isn't any of the added infrastructure, but rather the fact that we will now perform a longer walk in many cases.

[nikic]

I believe this is still not quite correct. Consider the following variation:

@x = global [10 x i16] zeroinitializer, align 1

define i16 @test(i1 %cond) {
entry: 
  br label %do.body

do.body:                             
  %i.0 = phi i16 [ 0, %entry ], [ %inc, %if.end2 ]
  %arrayidx2 = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 %i.0 
  store i16 2, i16* %arrayidx2, align 1 ;;; store is removed
  %exitcond = icmp eq i16 %i.0, 4
  br i1 %exitcond, label %exit, label %if.end

if.end:                   
  br i1 %cond, label %do.store, label %if.end2 
   
do.store:
  store i16 3, i16* %arrayidx2, align 1
  br label %if.end2 
   
if.end2:
  %inc = add nuw nsw i16 %i.0, 1
  br label %do.body 

exit:
  store i16 1, i16* %arrayidx2, align 1
  ret i16 0    
}

The current implementation will eliminate store store i16 2.

The reason is that DSE determines eliminable stores in two phases: First, a dominating access for the killing store is found. And second, all uses of the dominating access are checked. When store i16 1 is the killing access, we will bail out due to the loop invariance check. When store i16 3 is the killing store, we will not, because they are in the same loop. The store i16 1 will be examined as a use and skipped as a fully overwriting store.

[dmgreen]

Sigh. I should probably have found that problem. I hadn't considered multiple stores overriding happening like that.

[dmgreen]

Hello. OK. I'm back

This makes two changes. isOverwrite now checks IsGuaranteedLoopInvariant, returning OW_Unknown if they are not loop invariant. Otherwise we cannot trust the MustAlias that AA provides.
It also limits the IsGuaranteedLoopInvariant check from including global scope, only checking inside the same loop (or same block). This should hopefully limit the iterating on blocks that are very unlikely to be helpful.

Together these can mean we keep removing stores in loops, but does mean that certain partial alias overlaps that were removed before may no longer be. I don't believe those will come up very often though.

This removes some extra stores in the llvm test suite:

Metric: dse.NumRemainingStores
test-suite...nchmarkGame/spectral-norm.test     9.00     7.00   -22.2%
test-suite...abench/jpeg/jpeg-6a/cjpeg.test   6029.00  5709.00  -5.3%
test-suite...nsumer-jpeg/consumer-jpeg.test   6171.00  5851.00  -5.2%
test-suite...nchmarks/Misc/ReedSolomon.test   248.00   239.00   -3.6%
test-suite...s/ASC_Sequoia/AMGmk/AMGmk.test   220.00   216.00   -1.8%
test-suite...marks/Ptrdist/yacr2/yacr2.test   314.00   310.00   -1.3%
test-suite...nchmarks/McCat/18-imp/imp.test   143.00   142.00   -0.7%
test-suite...ocBench/espresso/espresso.test   1776.00  1772.00  -0.2%
test-suite...pplications/oggenc/oggenc.test   4174.00  4165.00  -0.2%
test-suite.../Benchmarks/nbench/nbench.test   1375.00  1373.00  -0.1%
test-suite...lications/ClamAV/clamscan.test   10107.00 10099.00 -0.1%
test-suite...arks/mafft/pairlocalalign.test   5967.00  5963.00  -0.1%
test-suite...nsumer-lame/consumer-lame.test   4615.00  4612.00  -0.1%
test-suite...lications/sqlite3/sqlite3.test   16485.00 16478.00 -0.0%
test-suite...marks/7zip/7zip-benchmark.test   32005.00 31993.00 -0.0%
test-suite...ications/JM/lencod/lencod.test   13650.00 13645.00 -0.0%
test-suite...ications/JM/ldecod/ldecod.test   6124.00  6122.00  -0.0%
test-suite...rks/tramp3d-v4/tramp3d-v4.test   49150.00 49144.00 -0.0%
test-suite...-typeset/consumer-typeset.test   22146.00 22144.00 -0.0%
test-suite.../Benchmarks/Bullet/bullet.test   26355.00 26354.00 -0.0%

The number of defchecks and walks generally goes up a little on average, whilst the number of override checks goes down. But different cases can act very differently. sqlite is still doing more work.

WDYT? This is hopefully conservatively correct. Let me know if you think of ways it would not be.

[nikic]

Could you please pre-commit the move of isOverwrite? Hard to see what changed otherwise.

[dmgreen]

I've rebased over the movement of isOverwrite into DSEState (but not committed that yet, will do soon). I've also rebased over the tests, to show the ones the improve/get worse (and that most don't change).

[dmgreen]

Rebase onto main. Any thoughts or comments on this now?

[nikic]

Logic looks correct now, and new compile-time impact (https://llvm-compile-time-tracker.com/compare.php?from=e42636d3c1a41a9b7c5d8095ae5ef6682e26d4a2&to=502b1e5a2bd94706da3df367ddf558fdef7e2a2e&stat=instructions) also looks fine to me.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

931

While it ultimately shouldn't make a difference, I think this should be passing Earlier as the memory location.

1273–1287

Doc comment is outdated now -- and the function should probably also get renamed as well.

1275

const MemoryLocation &

[dmgreen]

Changed IsGuaranteedLoopInvariant to isGuaranteedLoopInvariant (if this wasn't what you meant, let me know, and do you have suggestions for a better name?)
Reworded comments.
Fixed Later->Earlier memref, which then needed a rejig of one of the test to move the initial memloc out of the entry block.

[nikic]

LGTM

In D100464#2780642, @dmgreen wrote:

Changed IsGuaranteedLoopInvariant to isGuaranteedLoopInvariant (if this wasn't what you meant, let me know, and do you have suggestions for a better name?)

That was not what I had in mind, but after your comment update, I think this framing works :)

[fhahn]

LGTM, thanks! I think it would be good to update some of the naming/comments slightly (as per the comments) before committing.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

929

nit: 'the same location' may be a bit confusing here. I guess it's meant as the same MemoryLocation value, but we can store to different concrete locations for locations that depend on a loop induction for example.

1281

Referring to candidates & elimination here seems a bit out-of-place given the name & doc-comment of the function. It would be good to update the function name (doesn't check for invariance any longer). It now more accurately tries to rule out cross-iteration dependencies?

[dmgreen]

I did some rewording, but I'm not sure it's really better than it was before. Feel free to update further if you see fit.

rG222aeb4d51a4

[clin1]

@dmgreen, we found that DSE is removing a non dead store in a loop with multiple backedges. File "dse-double-loop.ll" attached. The 2nd store postdominates the 1st one, but it doesn't run on every iteration, so the 1st one is still needed. We worked around it by checking numBackEdges > 1 in addition to the irreducibility check. Would you mind taking a look? I hope bugpoint did not over-reduce the test case; it's derived from "real" code in spec2000 186.crafty.

dse-double-loop.ll1 KBDownload

[dmgreen]

Oh so it does. Thanks for the report. I thought we had a test case for that...

I'll revert this for the time being.

[clin1]

Thank you for the quick response! Much appreciated.

[dmgreen]

Reopening with adjusted code (and more test cases). The issues were related to the checks for all paths leading to the exit collectively postdominating the earlier dead store. But:

• A store that walked back to itself was ignored, effectively killing itself. This was this issue that came up from the reproducer. It is only true if the access is loop invariant, so it now uses an extra isGuaranteedLoopInvariant() check.
• Stores in blocks with later PO numbers were again effectively ignored. With loops they need to be handled, in this case by returning None.

The number of stores remove in the llvm test suite was almost the same as with the previous version of this patch. The total remaining stores was 3 more than the last set of numbers.

[clin1]

spec2000/186 passes now -- thanks.

[dmgreen]

In D100464#2822499, @clin1 wrote:

spec2000/186 passes now -- thanks.

Thanks for checking! We didn't see any failures here in our running of SPEC, I don't believe, so it's good to see its fixed for you with the latest version. There must be something different about the way they get run, perhaps because of the differences in architecture.

[cfang]

We see a big performance regression caused by this patch due to register pressure increase.
We found that remove stores in the same iteration could increase
the register pressure dramatically. In the following piece of code, group 1 and group 2 stores
are eliminated and the register usage increased from 70 to 171. This is from our
critical application, I am not sure whether this DSE could estimate RP?

// group 1 stores
sw[0][j][i] = r0 * du0;
sw[1][j][i] = r0 * du1;
sw[2][j][i] = r0 * du2;

.....

#pragma unroll 8

for (int m = 0; m < 8; m++) {
  const double vs =sv[m][j];
  du0 += vs * sq[0][m][i];
  du1 += vs * sq[1][m][i];
  du2 += vs * sq[2][m][i];
}
// group 2 stores
sw[0][j][i] += r1 * du0;
sw[1][j][i] += r1 * du1;
sw[2][j][i] += r1 * du2;

......

#pragma unroll 8

for (int m = 0; m < 8; m++) {
  const double xt = st[m][k];
  dx0 += xt * ru[0][m];
  dx1 += xt * ru[1][m];
  dx2 += xt * ru[2][m];
}
// group 3 stores
sw[0][j][i] += r2 * dx0;
sw[1][j][i] += r2 * dx1;
sw[2][j][i] += r2 * dx2;

Any suggestions are welcome to resolve this issue. Thanks.

[lebedev.ri]

Was that code being vectorized before this patch?

[fhahn]

In D100464#3136624, @cfang wrote:

Any suggestions are welcome to resolve this issue. Thanks.

Which pass is actually causing the increase in register pressure? I don't think DSE would be directly responsible, but rather some other transformation will be enabled and may go crazy. Figuring out which one and why would be a good start.

[fhahn]

@dmgreen this review is still open, but the patch got recommitted again, right? Can it be closed?

[dmgreen]

Hello. Do you have a more full example where this is causing the regressions? Is it something like this https://godbolt.org/z/fW79sMhWP? Or is there more to it than that?

Like the others have said - it's likely a good thing to remove dead stores and other passes that should be handling the increase in register pressure more elegantly. Without a more complete example it's hard to say what or where though.

I guess there must be more to it than the example above - if all the loops are unrolled then all the instructions end up in the same block and DSE can remove all the stores. even before this patch.

[cfang]

Right. If we manually LICM'ed the load/stores in group 1 and group2 (with something like sum_i),
we will see the higher register pressure. Further, if we intentionally insert dead stores to store
the intermediate sum_is, the register pressure can be lowered. Some later passes should be responsible.

[dmgreen]

In D100464#3136949, @fhahn wrote:

@dmgreen this review is still open, but the patch got recommitted again, right? Can it be closed?

Yep, this went in a long time ago now.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
+#include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
if (LP != EP && !AA.isMustAlias(LP, EP))
     return OW_Unknown;
   // Masks.
   // TODO: check that Later's mask is a superset of the Earlier's mask.
   if (IIL->getArgOperand(3) != IIE->getArgOperand(3))
     return OW_Unknown;
   return OW_Complete;
 }
 
-/// Return 'OW_Complete' if a store to the 'Later' location (by \p LaterI
-/// instruction) completely overwrites a store to the 'Earlier' location.
-/// (by \p EarlierI instruction).
-/// Return OW_MaybePartial if \p Later does not completely overwrite
-/// \p Earlier, but they both write to the same underlying object. In that
-/// case, use isPartialOverwrite to check if \p Later partially overwrites
-/// \p Earlier. Returns 'OW_Unknown' if nothing can be determined.
-static OverwriteResult
-isOverwrite(const Instruction *LaterI, const Instruction *EarlierI,
-            const MemoryLocation &Later, const MemoryLocation &Earlier,
-            const DataLayout &DL, const TargetLibraryInfo &TLI,
-            int64_t &EarlierOff, int64_t &LaterOff, BatchAAResults &AA,
-            const Function *F) {
-  // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
-  // get imprecise values here, though (except for unknown sizes).
-  if (!Later.Size.isPrecise() || !Earlier.Size.isPrecise()) {
-    // In case no constant size is known, try to an IR values for the number
-    // of bytes written and check if they match.
-    const auto *LaterMemI = dyn_cast<MemIntrinsic>(LaterI);
-    const auto *EarlierMemI = dyn_cast<MemIntrinsic>(EarlierI);
-    if (LaterMemI && EarlierMemI) {
-      const Value *LaterV = LaterMemI->getLength();
-      const Value *EarlierV = EarlierMemI->getLength();
-      if (LaterV == EarlierV && AA.isMustAlias(Earlier, Later))
-        return OW_Complete;
-    }
-
-    // Masked stores have imprecise locations, but we can reason about them
-    // to some extent.
-    return isMaskedStoreOverwrite(LaterI, EarlierI, AA);
-  }
-
-  const uint64_t LaterSize = Later.Size.getValue();
-  const uint64_t EarlierSize = Earlier.Size.getValue();
-
-  // Query the alias information
-  AliasResult AAR = AA.alias(Later, Earlier);
-
-  // If the start pointers are the same, we just have to compare sizes to see if
-  // the later store was larger than the earlier store.
-  if (AAR == AliasResult::MustAlias) {
-    // Make sure that the Later size is >= the Earlier size.
-    if (LaterSize >= EarlierSize)
-      return OW_Complete;
-  }
-
-  // If we hit a partial alias we may have a full overwrite
-  if (AAR == AliasResult::PartialAlias && AAR.hasOffset()) {
-    int32_t Off = AAR.getOffset();
-    if (Off >= 0 && (uint64_t)Off + EarlierSize <= LaterSize)
-      return OW_Complete;
-  }
-
-  // Check to see if the later store is to the entire object (either a global,
-  // an alloca, or a byval/inalloca argument).  If so, then it clearly
-  // overwrites any other store to the same object.
-  const Value *P1 = Earlier.Ptr->stripPointerCasts();
-  const Value *P2 = Later.Ptr->stripPointerCasts();
-  const Value *UO1 = getUnderlyingObject(P1), *UO2 = getUnderlyingObject(P2);
-
-  // If we can't resolve the same pointers to the same object, then we can't
-  // analyze them at all.
-  if (UO1 != UO2)
-    return OW_Unknown;
-
-  // If the "Later" store is to a recognizable object, get its size.
-  uint64_t ObjectSize = getPointerSize(UO2, DL, TLI, F);
-  if (ObjectSize != MemoryLocation::UnknownSize)
-    if (ObjectSize == LaterSize && ObjectSize >= EarlierSize)
-      return OW_Complete;
-
-  // Okay, we have stores to two completely different pointers.  Try to
-  // decompose the pointer into a "base + constant_offset" form.  If the base
-  // pointers are equal, then we can reason about the two stores.
-  EarlierOff = 0;
-  LaterOff = 0;
-  const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, DL);
-  const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, DL);
-
-  // If the base pointers still differ, we have two completely different stores.
-  if (BP1 != BP2)
-    return OW_Unknown;
-
-  // The later access completely overlaps the earlier store if and only if
-  // both start and end of the earlier one is "inside" the later one:
-  //    |<->|--earlier--|<->|
-  //    |-------later-------|
-  // Accesses may overlap if and only if start of one of them is "inside"
-  // another one:
-  //    |<->|--earlier--|<----->|
-  //    |-------later-------|
-  //           OR
-  //    |----- earlier -----|
-  //    |<->|---later---|<----->|
-  //
-  // We have to be careful here as *Off is signed while *.Size is unsigned.
-
-  // Check if the earlier access starts "not before" the later one.
-  if (EarlierOff >= LaterOff) {
-    // If the earlier access ends "not after" the later access then the earlier
-    // one is completely overwritten by the later one.
-    if (uint64_t(EarlierOff - LaterOff) + EarlierSize <= LaterSize)
-      return OW_Complete;
-    // If start of the earlier access is "before" end of the later access then
-    // accesses overlap.
-    else if ((uint64_t)(EarlierOff - LaterOff) < LaterSize)
-      return OW_MaybePartial;
-  }
-  // If start of the later access is "before" end of the earlier access then
-  // accesses overlap.
-  else if ((uint64_t)(LaterOff - EarlierOff) < EarlierSize) {
-    return OW_MaybePartial;
-  }
-
-  // Can reach here only if accesses are known not to overlap. There is no
-  // dedicated code to indicate no overlap so signal "unknown".
-  return OW_Unknown;
-}
-
 /// Return 'OW_Complete' if a store to the 'Later' location completely
 /// overwrites a store to the 'Earlier' location, 'OW_End' if the end of the
 /// 'Earlier' location is completely overwritten by 'Later', 'OW_Begin' if the
 /// beginning of the 'Earlier' location is overwritten by 'Later'.
 /// 'OW_PartialEarlierWithFullLater' means that an earlier (big) store was
 /// overwritten by a latter (smaller) store which doesn't write outside the big
 /// store's memory locations. Returns 'OW_Unknown' if nothing can be determined.
 /// NOTE: This function must only be called if both \p Later and \p Earlier
struct DSEState {
   ///    value pointer.
   BatchAAResults BatchAA;
 
   MemorySSA &MSSA;
   DominatorTree &DT;
   PostDominatorTree &PDT;
   const TargetLibraryInfo &TLI;
   const DataLayout &DL;
+  const LoopInfo &LI;
+
+  // Whether the function contains any irreducible control flow, useful for
+  // being accurately able to detect loops.
+  bool ContainsIrreducibleLoops;
 
   // All MemoryDefs that potentially could kill other MemDefs.
   SmallVector<MemoryDef *, 64> MemDefs;
   // Any that should be skipped as they are already deleted
   SmallPtrSet<MemoryAccess *, 4> SkipStores;
   // Keep track of all of the objects that are invisible to the caller before
   // the function returns.
   // SmallPtrSet<const Value *, 16> InvisibleToCallerBeforeRet;
   DenseMap<const Value *, bool> InvisibleToCallerBeforeRet;
   // Keep track of all of the objects that are invisible to the caller after
   // the function returns.
   DenseMap<const Value *, bool> InvisibleToCallerAfterRet;
   // Keep track of blocks with throwing instructions not modeled in MemorySSA.
   SmallPtrSet<BasicBlock *, 16> ThrowingBlocks;
   // Post-order numbers for each basic block. Used to figure out if memory
   // accesses are executed before another access.
   DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
 
   /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
   /// basic block.
   DenseMap<BasicBlock *, InstOverlapIntervalsTy> IOLs;
 
   DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
-           PostDominatorTree &PDT, const TargetLibraryInfo &TLI)
+           PostDominatorTree &PDT, const TargetLibraryInfo &TLI,
+           const LoopInfo &LI)
       : F(F), AA(AA), BatchAA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI),
-        DL(F.getParent()->getDataLayout()) {}
+        DL(F.getParent()->getDataLayout()), LI(LI) {}
 
   static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
                       DominatorTree &DT, PostDominatorTree &PDT,
-                      const TargetLibraryInfo &TLI) {
-    DSEState State(F, AA, MSSA, DT, PDT, TLI);
+                      const TargetLibraryInfo &TLI, const LoopInfo &LI) {
+    DSEState State(F, AA, MSSA, DT, PDT, TLI, LI);
     // Collect blocks with throwing instructions not modeled in MemorySSA and
     // alloc-like objects.
     unsigned PO = 0;
     for (BasicBlock *BB : post_order(&F)) {
       State.PostOrderNumbers[BB] = PO++;
       for (Instruction &I : *BB) {
         MemoryAccess *MA = MSSA.getMemoryAccess(&I);
         if (I.mayThrow() && !MA)
static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
     for (Argument &AI : F.args())
       if (AI.hasPassPointeeByValueCopyAttr()) {
         // For byval, the caller doesn't know the address of the allocation.
         if (AI.hasByValAttr())
           State.InvisibleToCallerBeforeRet.insert({&AI, true});
         State.InvisibleToCallerAfterRet.insert({&AI, true});
       }
 
+    // Collect whether there is any irreducible control flow in the function.
+    State.ContainsIrreducibleLoops = mayContainIrreducibleControl(F, &LI);
+
     return State;
   }
 
+  /// Return 'OW_Complete' if a store to the 'Later' location (by \p LaterI
+  /// instruction) completely overwrites a store to the 'Earlier' location.
+  /// (by \p EarlierI instruction).
+  /// Return OW_MaybePartial if \p Later does not completely overwrite
+  /// \p Earlier, but they both write to the same underlying object. In that
+  /// case, use isPartialOverwrite to check if \p Later partially overwrites
+  /// \p Earlier. Returns 'OW_Unknown' if nothing can be determined.
+  OverwriteResult
+  isOverwrite(const Instruction *LaterI, const Instruction *EarlierI,
+              const MemoryLocation &Later, const MemoryLocation &Earlier,
+              int64_t &EarlierOff, int64_t &LaterOff) {
+    // AliasAnalysis does not account for loops. Limit overwrite checks to
+    // candidates for which we can guarantee they always store to the same
+    // memory location and not located in different loops.
+    if (!IsGuaranteedLoopInvariant(EarlierI, LaterI, Later))
+      return OW_Unknown;
+
+    // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
+    // get imprecise values here, though (except for unknown sizes).
+    if (!Later.Size.isPrecise() || !Earlier.Size.isPrecise()) {
+      // In case no constant size is known, try to an IR values for the number
+      // of bytes written and check if they match.
+      const auto *LaterMemI = dyn_cast<MemIntrinsic>(LaterI);
+      const auto *EarlierMemI = dyn_cast<MemIntrinsic>(EarlierI);
+      if (LaterMemI && EarlierMemI) {
+        const Value *LaterV = LaterMemI->getLength();
+        const Value *EarlierV = EarlierMemI->getLength();
+        if (LaterV == EarlierV && AA.isMustAlias(Earlier, Later))
+          return OW_Complete;
+      }
+
+      // Masked stores have imprecise locations, but we can reason about them
+      // to some extent.
+      return isMaskedStoreOverwrite(LaterI, EarlierI, BatchAA);
+    }
+
+    const uint64_t LaterSize = Later.Size.getValue();
+    const uint64_t EarlierSize = Earlier.Size.getValue();
+
+    // Query the alias information
+    AliasResult AAR = BatchAA.alias(Later, Earlier);
+
+    // If the start pointers are the same, we just have to compare sizes to see if
+    // the later store was larger than the earlier store.
+    if (AAR == AliasResult::MustAlias) {
+      // Make sure that the Later size is >= the Earlier size.
+      if (LaterSize >= EarlierSize)
+        return OW_Complete;
+    }
+
+    // If we hit a partial alias we may have a full overwrite
+    if (AAR == AliasResult::PartialAlias && AAR.hasOffset()) {
+      int32_t Off = AAR.getOffset();
+      if (Off >= 0 && (uint64_t)Off + EarlierSize <= LaterSize)
+        return OW_Complete;
+    }
+
+    // Check to see if the later store is to the entire object (either a global,
+    // an alloca, or a byval/inalloca argument).  If so, then it clearly
+    // overwrites any other store to the same object.
+    const Value *P1 = Earlier.Ptr->stripPointerCasts();
+    const Value *P2 = Later.Ptr->stripPointerCasts();
+    const Value *UO1 = getUnderlyingObject(P1), *UO2 = getUnderlyingObject(P2);
+
+    // If we can't resolve the same pointers to the same object, then we can't
+    // analyze them at all.
+    if (UO1 != UO2)
+      return OW_Unknown;
+
+    // If the "Later" store is to a recognizable object, get its size.
+    uint64_t ObjectSize = getPointerSize(UO2, DL, TLI, &F);
+    if (ObjectSize != MemoryLocation::UnknownSize)
+      if (ObjectSize == LaterSize && ObjectSize >= EarlierSize)
+        return OW_Complete;
+
+    // Okay, we have stores to two completely different pointers.  Try to
+    // decompose the pointer into a "base + constant_offset" form.  If the base
+    // pointers are equal, then we can reason about the two stores.
+    EarlierOff = 0;
+    LaterOff = 0;
+    const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, DL);
+    const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, DL);
+
+    // If the base pointers still differ, we have two completely different stores.
+    if (BP1 != BP2)
+      return OW_Unknown;
+
+    // The later access completely overlaps the earlier store if and only if
+    // both start and end of the earlier one is "inside" the later one:
+    //    |<->|--earlier--|<->|
+    //    |-------later-------|
+    // Accesses may overlap if and only if start of one of them is "inside"
+    // another one:
+    //    |<->|--earlier--|<----->|
+    //    |-------later-------|
+    //           OR
+    //    |----- earlier -----|
+    //    |<->|---later---|<----->|
+    //
+    // We have to be careful here as *Off is signed while *.Size is unsigned.
+
+    // Check if the earlier access starts "not before" the later one.
+    if (EarlierOff >= LaterOff) {
+      // If the earlier access ends "not after" the later access then the earlier
+      // one is completely overwritten by the later one.
+      if (uint64_t(EarlierOff - LaterOff) + EarlierSize <= LaterSize)
+        return OW_Complete;
+      // If start of the earlier access is "before" end of the later access then
+      // accesses overlap.
+      else if ((uint64_t)(EarlierOff - LaterOff) < LaterSize)
+        return OW_MaybePartial;
+    }
+    // If start of the later access is "before" end of the earlier access then
+    // accesses overlap.
+    else if ((uint64_t)(LaterOff - EarlierOff) < EarlierSize) {
+      return OW_MaybePartial;
+    }
+
+    // Can reach here only if accesses are known not to overlap. There is no
+    // dedicated code to indicate no overlap so signal "unknown".
+    return OW_Unknown;
+  }
+
   bool isInvisibleToCallerAfterRet(const Value *V) {
     if (isa<AllocaInst>(V))
       return true;
     auto I = InvisibleToCallerAfterRet.insert({V, false});
     if (I.second) {
       if (!isInvisibleToCallerBeforeRet(V)) {
         I.first->second = false;
       } else {
if (!UseInst->mayWriteToMemory())
       return false;
 
     if (auto *CB = dyn_cast<CallBase>(UseInst))
       if (CB->onlyAccessesInaccessibleMemory())
         return false;
 
     int64_t InstWriteOffset, DepWriteOffset;
     if (auto CC = getLocForWriteEx(UseInst))
-      return isOverwrite(UseInst, DefInst, *CC, DefLoc, DL, TLI, DepWriteOffset,
-                         InstWriteOffset, BatchAA, &F) == OW_Complete;
+      return isOverwrite(UseInst, DefInst, *CC, DefLoc, DepWriteOffset,
+                         InstWriteOffset) == OW_Complete;
     return false;
   }
 
   /// Returns true if \p Def is not read before returning from the function.
   bool isWriteAtEndOfFunction(MemoryDef *Def) {
     LLVM_DEBUG(dbgs() << "  Check if def " << *Def << " ("
                       << *Def->getMemoryInst()
                       << ") is at the end the function \n");
if (getUnderlyingObject(Loc.Ptr) !=
       return false;
 
     auto TermLoc = MaybeTermLoc->first;
     if (MaybeTermLoc->second) {
       const Value *LocUO = getUnderlyingObject(Loc.Ptr);
       return BatchAA.isMustAlias(TermLoc.Ptr, LocUO);
     }
     int64_t InstWriteOffset, DepWriteOffset;
-    return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, DL, TLI,
-                       DepWriteOffset, InstWriteOffset, BatchAA,
-                       &F) == OW_Complete;
+    return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, DepWriteOffset,
+                       InstWriteOffset) == OW_Complete;
   }
 
   // Returns true if \p Use may read from \p DefLoc.
   bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst) {
     if (isNoopIntrinsic(UseInst))
       return false;
 
     // Monotonic or weaker atomic stores can be re-ordered and do not need to be
bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst) {
     // be expensive compared to the benefits in practice. For now, avoid more
     // expensive analysis to limit compile-time.
     return isRefSet(BatchAA.getModRefInfo(UseInst, DefLoc));
   }
 
   /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
   /// loop. In particular, this guarantees that it only references a single
   /// MemoryLocation during execution of the containing function.
-  bool IsGuaranteedLoopInvariant(Value *Ptr) {
-    auto IsGuaranteedLoopInvariantBase = [this](Value *Ptr) {
+  bool IsGuaranteedLoopInvariant(const Instruction *Current,
+                                 const Instruction *KillingDef,
+                                 MemoryLocation CurrentLoc) {
+    // Limit elimination to candidates for which we can guarantee they always
+    // store to the same memory location and not located in different loops. But
+    // also be careful with irreducible control flow, which can create cycles
+    // without appearing as loops.
+    if (Current->getParent() == KillingDef->getParent())
+      return true;
+    const Loop *CurrentLI = LI.getLoopFor(Current->getParent());
+    if (!ContainsIrreducibleLoops && CurrentLI &&
+        CurrentLI == LI.getLoopFor(KillingDef->getParent()))
+      return true;
+
+    auto IsGuaranteedLoopInvariantBase = [this](const Value *Ptr) {
       Ptr = Ptr->stripPointerCasts();
       if (auto *I = dyn_cast<Instruction>(Ptr)) {
         if (isa<AllocaInst>(Ptr))
           return true;
 
         if (isAllocLikeFn(I, &TLI))
           return true;
 
         return false;
       }
       return true;
     };
 
-    Ptr = Ptr->stripPointerCasts();
+    const Value *Ptr = CurrentLoc.Ptr->stripPointerCasts();
     if (auto *I = dyn_cast<Instruction>(Ptr)) {
       if (I->getParent() == &I->getFunction()->getEntryBlock()) {
         return true;
       }
     }
     if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
       return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&
              GEP->hasAllConstantIndices();
     }
     return IsGuaranteedLoopInvariantBase(Ptr);
   }
 
   // Find a MemoryDef writing to \p DefLoc and dominating \p StartAccess, with
   // no read access between them or on any other path to a function exit block
   // if \p DefLoc is not accessible after the function returns. If there is no
   // such MemoryDef, return None. The returned value may not (completely)
   // overwrite \p DefLoc. Currently we bail out when we encounter an aliasing
   // MemoryUse (read).
   Optional<MemoryAccess *>
   getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *StartAccess,
                   const MemoryLocation &DefLoc, const Value *DefUO,
                   unsigned &ScanLimit, unsigned &WalkerStepLimit,
                   bool IsMemTerm, unsigned &PartialLimit) {
     if (ScanLimit == 0 || WalkerStepLimit == 0) {
       LLVM_DEBUG(dbgs() << "\n    ...  hit scan limit\n");
       return None;
     }
 
     MemoryAccess *Current = StartAccess;
     Instruction *KillingI = KillingDef->getMemoryInst();
     bool StepAgain;
do {
       if (!CurrentLoc) {
         StepAgain = true;
         Current = CurrentDef->getDefiningAccess();
         continue;
       }
 
       // AliasAnalysis does not account for loops. Limit elimination to
       // candidates for which we can guarantee they always store to the same
-      // memory location and not multiple locations in a loop.
-      if (Current->getBlock() != KillingDef->getBlock() &&
-          !IsGuaranteedLoopInvariant(const_cast<Value *>(CurrentLoc->Ptr))) {
+      // memory location and not located in different loops.
+      if (!IsGuaranteedLoopInvariant(CurrentI, KillingI, *CurrentLoc)) {
+        LLVM_DEBUG(dbgs() << "  ... not guaranteed loop invariant\n");
         StepAgain = true;
         Current = CurrentDef->getDefiningAccess();
         WalkerStepLimit -= 1;
         continue;
       }
 
       if (IsMemTerm) {
         // If the killing def is a memory terminator (e.g. lifetime.end), check
         // the next candidate if the current Current does not write the same
         // underlying object as the terminator.
         if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI)) {
           StepAgain = true;
           Current = CurrentDef->getDefiningAccess();
         }
         continue;
       } else {
         int64_t InstWriteOffset, DepWriteOffset;
-        auto OR = isOverwrite(KillingI, CurrentI, DefLoc, *CurrentLoc, DL, TLI,
-                              DepWriteOffset, InstWriteOffset, BatchAA, &F);
+        auto OR = isOverwrite(KillingI, CurrentI, DefLoc, *CurrentLoc,
+                              DepWriteOffset, InstWriteOffset);
         // If Current does not write to the same object as KillingDef, check
         // the next candidate.
         if (OR == OW_Unknown) {
           StepAgain = true;
           Current = CurrentDef->getDefiningAccess();
         } else if (OR == OW_MaybePartial) {
           // If KillingDef only partially overwrites Current, check the next
           // candidate if the partial step limit is exceeded. This aggressively
if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
         return true;
       }
     }
 
     return false;
   }
 };
 
-bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
+static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
                                 DominatorTree &DT, PostDominatorTree &PDT,
-                         const TargetLibraryInfo &TLI) {
+                                const TargetLibraryInfo &TLI,
+                                const LoopInfo &LI) {
   bool MadeChange = false;
 
-  DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI);
+  DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI, LI);
   // For each store:
   for (unsigned I = 0; I < State.MemDefs.size(); I++) {
     MemoryDef *KillingDef = State.MemDefs[I];
     if (State.SkipStores.count(KillingDef))
       continue;
     Instruction *SI = KillingDef->getMemoryInst();
 
     Optional<MemoryLocation> MaybeSILoc;
for (unsigned I = 0; I < ToCheck.size(); I++) {
         LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *NI
                           << "\n  KILLER: " << *SI << '\n');
         State.deleteDeadInstruction(NI);
         ++NumFastStores;
         MadeChange = true;
       } else {
         // Check if NI overwrites SI.
         int64_t InstWriteOffset, DepWriteOffset;
-        OverwriteResult OR =
-            isOverwrite(SI, NI, SILoc, NILoc, State.DL, TLI, DepWriteOffset,
-                        InstWriteOffset, State.BatchAA, &F);
+        OverwriteResult OR = State.isOverwrite(SI, NI, SILoc, NILoc,
+                                               DepWriteOffset, InstWriteOffset);
         if (OR == OW_MaybePartial) {
           auto Iter = State.IOLs.insert(
               std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
                   NI->getParent(), InstOverlapIntervalsTy()));
           auto &IOL = Iter.first->second;
           OR = isPartialOverwrite(SILoc, NILoc, DepWriteOffset, InstWriteOffset,
                                   NI, IOL);
         }

 // DSE Pass
 //===----------------------------------------------------------------------===//
 PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
   AliasAnalysis &AA = AM.getResult<AAManager>(F);
   const TargetLibraryInfo &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
   MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
   PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
+  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
 
-  bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI);
+  bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI);
 
 #ifdef LLVM_ENABLE_STATS
   if (AreStatisticsEnabled())
     for (auto &I : instructions(F))
       NumRemainingStores += isa<StoreInst>(&I);
 #endif
 
   if (!Changed)
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   PA.preserve<GlobalsAA>();
   PA.preserve<MemorySSAAnalysis>();
+  PA.preserve<LoopAnalysis>();
   return PA;
 }
 
 namespace {
 
 /// A legacy pass for the legacy pass manager that wraps \c DSEPass.
 class DSELegacyPass : public FunctionPass {
 public:
bool runOnFunction(Function &F) override {
 
     AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     const TargetLibraryInfo &TLI =
         getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
     MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
     PostDominatorTree &PDT =
         getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
+    LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 
-    bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI);
+    bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI);
 
 #ifdef LLVM_ENABLE_STATS
     if (AreStatisticsEnabled())
       for (auto &I : instructions(F))
         NumRemainingStores += isa<StoreInst>(&I);
 #endif
 
     return Changed;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addRequired<PostDominatorTreeWrapperPass>();
     AU.addRequired<MemorySSAWrapperPass>();
     AU.addPreserved<PostDominatorTreeWrapperPass>();
     AU.addPreserved<MemorySSAWrapperPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
+    AU.addPreserved<LoopInfoWrapperPass>();
   }
 };
 
 } // end anonymous namespace
 
 char DSELegacyPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_END(DSELegacyPass, "dse", "Dead Store Elimination", false,
                     false)
 
 FunctionPass *llvm::createDeadStoreEliminationPass() {
   return new DSELegacyPass();
 }

llvm/test/CodeGen/AMDGPU/opt-pipeline.ll

 ; GCN-O2-NEXT:       Jump Threading
 ; GCN-O2-NEXT:       Value Propagation
 ; GCN-O2-NEXT:       Post-Dominator Tree Construction
 ; GCN-O2-NEXT:       Aggressive Dead Code Elimination
 ; GCN-O2-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       Memory SSA
 ; GCN-O2-NEXT:       MemCpy Optimization
-; GCN-O2-NEXT:       Dead Store Elimination
 ; GCN-O2-NEXT:       Natural Loop Information
+; GCN-O2-NEXT:       Dead Store Elimination
 ; GCN-O2-NEXT:       Canonicalize natural loops
 ; GCN-O2-NEXT:       LCSSA Verifier
 ; GCN-O2-NEXT:       Loop-Closed SSA Form Pass
 ; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       Scalar Evolution Analysis
 ; GCN-O2-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O2-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O2-NEXT:       Loop Pass Manager

 ; GCN-O3-NEXT:       Jump Threading
 ; GCN-O3-NEXT:       Value Propagation
 ; GCN-O3-NEXT:       Post-Dominator Tree Construction
 ; GCN-O3-NEXT:       Aggressive Dead Code Elimination
 ; GCN-O3-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       Memory SSA
 ; GCN-O3-NEXT:       MemCpy Optimization
-; GCN-O3-NEXT:       Dead Store Elimination
 ; GCN-O3-NEXT:       Natural Loop Information
+; GCN-O3-NEXT:       Dead Store Elimination
 ; GCN-O3-NEXT:       Canonicalize natural loops
 ; GCN-O3-NEXT:       LCSSA Verifier
 ; GCN-O3-NEXT:       Loop-Closed SSA Form Pass
 ; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       Scalar Evolution Analysis
 ; GCN-O3-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O3-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O3-NEXT:       Loop Pass Manager

llvm/test/Other/opt-O2-pipeline.ll

 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Post-Dominator Tree Construction
 ; CHECK-NEXT:         Aggressive Dead Code Elimination
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         MemCpy Optimization
-; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Natural Loop Information
+; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager

llvm/test/Other/opt-O3-pipeline-enable-matrix.ll

 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Post-Dominator Tree Construction
 ; CHECK-NEXT:         Aggressive Dead Code Elimination
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         MemCpy Optimization
-; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Natural Loop Information
+; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager

llvm/test/Other/opt-O3-pipeline.ll

 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Post-Dominator Tree Construction
 ; CHECK-NEXT:         Aggressive Dead Code Elimination
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         MemCpy Optimization
-; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Natural Loop Information
+; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager

llvm/test/Other/opt-Os-pipeline.ll

 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Post-Dominator Tree Construction
 ; CHECK-NEXT:         Aggressive Dead Code Elimination
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         MemCpy Optimization
-; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Natural Loop Information
+; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager

llvm/test/Transforms/DeadStoreElimination/multiblock-loops.ll

 ; CHECK-NEXT:    br i1 [[CMP27]], label [[FOR_BODY4_LR_PH_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
 ; CHECK:       for.body4.lr.ph.preheader:
 ; CHECK-NEXT:    br label [[FOR_BODY4_LR_PH:%.*]]
 ; CHECK:       for.cond.cleanup:
 ; CHECK-NEXT:    ret void
 ; CHECK:       for.body4.lr.ph:
 ; CHECK-NEXT:    [[I_028:%.*]] = phi i32 [ [[INC11:%.*]], [[FOR_COND_CLEANUP3:%.*]] ], [ 0, [[FOR_BODY4_LR_PH_PREHEADER]] ]
 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i32 [[I_028]]
-; CHECK-NEXT:    store i32 0, i32* [[ARRAYIDX]], align 4
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[I_028]], [[N]]
 ; CHECK-NEXT:    br label [[FOR_BODY4:%.*]]
 ; CHECK:       for.body4:
 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ 0, [[FOR_BODY4_LR_PH]] ], [ [[ADD9:%.*]], [[FOR_BODY4]] ]
 ; CHECK-NEXT:    [[J_026:%.*]] = phi i32 [ 0, [[FOR_BODY4_LR_PH]] ], [ [[INC:%.*]], [[FOR_BODY4]] ]
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[J_026]], [[MUL]]
 ; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i32 [[ADD]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[ARRAYIDX5]], align 4

 if.end:                                           ; preds = %do.body
   %inc = add nuw nsw i16 %i.0, 1
   br label %do.body
 
 if.end10:                                         ; preds = %do.body
   store i16 1, i16* %arrayidx2, align 1
   ret i16 0
 }
+
+; Similar to above, but with an irreducible loop. The stores should not be removed.
+define i16 @irreducible(i1 %c) {
+; CHECK-LABEL: @irreducible(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i16 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[B]] ]
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 [[I_0]]
+; CHECK-NEXT:    br label [[B]]
+; CHECK:       B:
+; CHECK-NEXT:    [[J_0:%.*]] = phi i16 [ 0, [[ENTRY]] ], [ [[I_0]], [[A]] ]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 [[J_0]]
+; CHECK-NEXT:    store i16 2, i16* [[ARRAYIDX]], align 1
+; CHECK-NEXT:    [[INC]] = add nuw nsw i16 [[J_0]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i16 [[J_0]], 4
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[A]]
+; CHECK:       exit:
+; CHECK-NEXT:    store i16 1, i16* [[ARRAYIDX]], align 1
+; CHECK-NEXT:    ret i16 0
+;
+entry:
+  br i1 %c, label %A, label %B
+
+A:
+  %i.0 = phi i16 [ 0, %entry ], [ %inc, %B ]
+  %arrayidx2 = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 %i.0
+  br label %B
+
+B:
+  %j.0 = phi i16 [ 0, %entry ], [ %i.0, %A ]
+  %arrayidx = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 %j.0
+  store i16 2, i16* %arrayidx, align 1
+  %inc = add nuw nsw i16 %j.0, 1
+  %exitcond = icmp eq i16 %j.0, 4
+  br i1 %exitcond, label %exit, label %A
+
+exit:
+  store i16 1, i16* %arrayidx, align 1
+  ret i16 0
+}
+
+; An irreducible loop inside another loop.
+define i16 @irreducible_nested() {
+; CHECK-LABEL: @irreducible_nested(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[OUTER:%.*]]
+; CHECK:       outer:
+; CHECK-NEXT:    [[X:%.*]] = phi i16 [ 0, [[ENTRY:%.*]] ], [ [[INCX:%.*]], [[OUTERL:%.*]] ]
+; CHECK-NEXT:    [[C:%.*]] = icmp sgt i16 [[X]], 2
+; CHECK-NEXT:    br i1 [[C]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i16 [ 0, [[OUTER]] ], [ [[INC:%.*]], [[B]] ]
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 [[I_0]]
+; CHECK-NEXT:    br label [[B]]
+; CHECK:       B:
+; CHECK-NEXT:    [[J_0:%.*]] = phi i16 [ 0, [[OUTER]] ], [ [[I_0]], [[A]] ]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 [[J_0]]
+; CHECK-NEXT:    store i16 2, i16* [[ARRAYIDX]], align 1
+; CHECK-NEXT:    [[INC]] = add nuw nsw i16 [[J_0]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i16 [[J_0]], 4
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[OUTERL]], label [[A]]
+; CHECK:       outerl:
+; CHECK-NEXT:    store i16 1, i16* [[ARRAYIDX]], align 1
+; CHECK-NEXT:    [[INCX]] = add nuw nsw i16 [[X]], 1
+; CHECK-NEXT:    [[EXITCONDX:%.*]] = icmp eq i16 [[X]], 4
+; CHECK-NEXT:    br i1 [[EXITCONDX]], label [[END:%.*]], label [[OUTER]]
+; CHECK:       end:
+; CHECK-NEXT:    ret i16 0
+;
+entry:
+  br label %outer
+
+outer:
+  %x = phi i16 [ 0, %entry ], [ %incx, %outerl ]
+  %c = icmp sgt i16 %x, 2
+  br i1 %c, label %A, label %B
+
+A:
+  %i.0 = phi i16 [ 0, %outer ], [ %inc, %B ]
+  %arrayidx2 = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 %i.0
+  br label %B
+
+B:
+  %j.0 = phi i16 [ 0, %outer ], [ %i.0, %A ]
+  %arrayidx = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 %j.0
+  store i16 2, i16* %arrayidx, align 1
+  %inc = add nuw nsw i16 %j.0, 1
+  %exitcond = icmp eq i16 %j.0, 4
+  br i1 %exitcond, label %outerl, label %A
+
+outerl:
+  store i16 1, i16* %arrayidx, align 1
+  %incx = add nuw nsw i16 %x, 1
+  %exitcondx = icmp eq i16 %x, 4
+  br i1 %exitcondx, label %end, label %outer
+
+end:
+  ret i16 0
+}
+
+define i16 @multi_overwrite(i1 %cond) {
+; CHECK-LABEL: @multi_overwrite(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[DO_BODY:%.*]]
+; CHECK:       do.body:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i16 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[IF_END2:%.*]] ]
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 [[I_0]]
+; CHECK-NEXT:    store i16 2, i16* [[ARRAYIDX2]], align 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i16 [[I_0]], 4
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[DO_STORE:%.*]], label [[IF_END2]]
+; CHECK:       do.store:
+; CHECK-NEXT:    store i16 3, i16* [[ARRAYIDX2]], align 1
+; CHECK-NEXT:    br label [[IF_END2]]
+; CHECK:       if.end2:
+; CHECK-NEXT:    [[INC]] = add nuw nsw i16 [[I_0]], 1
+; CHECK-NEXT:    br label [[DO_BODY]]
+; CHECK:       exit:
+; CHECK-NEXT:    store i16 1, i16* [[ARRAYIDX2]], align 1
+; CHECK-NEXT:    ret i16 0
+;
+entry:
+  br label %do.body
+
+do.body:
+  %i.0 = phi i16 [ 0, %entry ], [ %inc, %if.end2 ]
+  %arrayidx2 = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 %i.0
+  store i16 2, i16* %arrayidx2, align 1
+  %exitcond = icmp eq i16 %i.0, 4
+  br i1 %exitcond, label %exit, label %if.end
+
+if.end:
+  br i1 %cond, label %do.store, label %if.end2
+
+do.store:
+  store i16 3, i16* %arrayidx2, align 1
+  br label %if.end2
+
+if.end2:
+  %inc = add nuw nsw i16 %i.0, 1
+  br label %do.body
+
+exit:
+  store i16 1, i16* %arrayidx2, align 1
+  ret i16 0
+}
+
+define void @test(i8* noalias %data1, i8* %data2, i16* %data3, i32 %i1)
+; CHECK-LABEL: @test(
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[I1:%.*]], 0
+; CHECK-NEXT:    br label [[PH0:%.*]]
+; CHECK:       ph0:
+; CHECK-NEXT:    br label [[HEADER0:%.*]]
+; CHECK:       header0:
+; CHECK-NEXT:    [[P1:%.*]] = phi i32 [ 0, [[PH0]] ], [ [[PN1:%.*]], [[END1:%.*]] ]
+; CHECK-NEXT:    [[PN1]] = add i32 [[P1]], 1
+; CHECK-NEXT:    [[PC1:%.*]] = icmp slt i32 [[PN1]], 5
+; CHECK-NEXT:    [[V2:%.*]] = getelementptr [10 x i16], [10 x i16]* @x, i32 0, i32 [[P1]]
+; CHECK-NEXT:    store i16 1, i16* [[V2]], align 2
+; CHECK-NEXT:    br i1 [[C]], label [[THEN1:%.*]], label [[ELSE1:%.*]]
+; CHECK:       then1:
+; CHECK-NEXT:    store i16 2, i16* [[V2]], align 2
+; CHECK-NEXT:    br label [[END1]]
+; CHECK:       else1:
+; CHECK-NEXT:    br label [[END1]]
+; CHECK:       end1:
+; CHECK-NEXT:    br i1 [[PC1]], label [[HEADER0]], label [[END0:%.*]]
+; CHECK:       end0:
+; CHECK-NEXT:    br label [[HEADER2:%.*]]
+; CHECK:       header2:
+; CHECK-NEXT:    [[P3:%.*]] = phi i32 [ 0, [[END0]] ], [ [[PN3:%.*]], [[HEADER2]] ]
+; CHECK-NEXT:    [[PN3]] = add i32 [[P3]], 1
+; CHECK-NEXT:    [[PC3:%.*]] = icmp slt i32 [[PN3]], 5
+; CHECK-NEXT:    store i16 4, i16* [[V2]], align 2
+; CHECK-NEXT:    br i1 [[PC3]], label [[HEADER2]], label [[END2:%.*]]
+; CHECK:       end2:
+; CHECK-NEXT:    ret void
+;
+{
+  %c = icmp eq i32 %i1, 0
+  br label %ph0
+ph0:
+  br label %header0
+header0:
+  %p1 = phi i32 [0, %ph0], [%pn1, %end1]
+  %pn1 = add i32 %p1, 1
+  %pc1 = icmp slt i32 %pn1, 5
+  %v2 = getelementptr [10 x i16], [10 x i16]* @x, i32 0, i32 %p1
+  store i16 1, i16* %v2
+  br i1 %c, label %then1, label %else1
+then1:
+  store i16 2, i16* %v2
+  br label %end1
+else1:
+  br label %end1
+end1:
+  br i1 %pc1, label %header0, label %end0
+end0:
+  br label %header2
+header2:
+  %p3 = phi i32 [0, %end0], [%pn3, %header2]
+  %pn3 = add i32 %p3, 1
+  %pc3 = icmp slt i32 %pn3, 5
+  store i16 4, i16* %v2
+  br i1 %pc3, label %header2, label %end2
+end2:
+  ret void
+}
+
+; Similar to above, but with multiple partial overlaps
+define i16 @partial_override_fromloop(i1 %c, i32 %i) {
+; CHECK-LABEL: @partial_override_fromloop(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[DO_BODY:%.*]]
+; CHECK:       do.body:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i16 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[IF_END2:%.*]] ]
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 [[I_0]]
+; CHECK-NEXT:    store i16 2, i16* [[ARRAYIDX2]], align 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i16 [[I_0]], 4
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[DO_STORE:%.*]], label [[IF_END2]]
+; CHECK:       do.store:
+; CHECK-NEXT:    store i16 3, i16* [[ARRAYIDX2]], align 1
+; CHECK-NEXT:    br label [[IF_END2]]
+; CHECK:       if.end2:
+; CHECK-NEXT:    [[INC]] = add nuw nsw i16 [[I_0]], 1
+; CHECK-NEXT:    br label [[DO_BODY]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[BC:%.*]] = bitcast i16* [[ARRAYIDX2]] to i8*
+; CHECK-NEXT:    [[BC2:%.*]] = getelementptr inbounds i8, i8* [[BC]], i32 1
+; CHECK-NEXT:    store i8 10, i8* [[BC]], align 1
+; CHECK-NEXT:    store i8 11, i8* [[BC2]], align 1
+; CHECK-NEXT:    ret i16 0
+;
+entry:
+  br label %do.body
+
+do.body:
+  %i.0 = phi i16 [ 0, %entry ], [ %inc, %if.end2 ]
+  %arrayidx2 = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 %i.0
+  store i16 2, i16* %arrayidx2, align 1
+  %exitcond = icmp eq i16 %i.0, 4
+  br i1 %exitcond, label %exit, label %if.end
+
+if.end:
+  br i1 %c, label %do.store, label %if.end2
+
+do.store:
+  store i16 3, i16* %arrayidx2, align 1
+  br label %if.end2
+
+if.end2:
+  %inc = add nuw nsw i16 %i.0, 1
+  br label %do.body
+
+exit:
+  %bc = bitcast i16* %arrayidx2 to i8*
+  %bc2 = getelementptr inbounds i8, i8* %bc, i32 1
+  store i8 10, i8* %bc, align 1
+  store i8 11, i8* %bc2, align 1
+  ret i16 0
+}
+
+
+define i16 @partial_override_overloop(i1 %c, i32 %i) {
+; CHECK-LABEL: @partial_override_overloop(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i32 [[I:%.*]]
+; CHECK-NEXT:    store i16 1, i16* [[ARRAYIDX]], align 1
+; CHECK-NEXT:    br label [[DO_BODY:%.*]]
+; CHECK:       do.body:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i16 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[DO_BODY]] ]
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 [[I_0]]
+; CHECK-NEXT:    store i16 2, i16* [[ARRAYIDX2]], align 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i16 [[I_0]], 4
+; CHECK-NEXT:    [[INC]] = add nuw nsw i16 [[I_0]], 1
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[DO_BODY]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[BC:%.*]] = bitcast i16* [[ARRAYIDX]] to i8*
+; CHECK-NEXT:    [[BC2:%.*]] = getelementptr inbounds i8, i8* [[BC]], i32 1
+; CHECK-NEXT:    store i8 10, i8* [[BC]], align 1
+; CHECK-NEXT:    store i8 11, i8* [[BC2]], align 1
+; CHECK-NEXT:    ret i16 0
+;
+entry:
+  %arrayidx = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i32 %i
+  store i16 1, i16* %arrayidx, align 1
+  br label %do.body
+
+do.body:
+  %i.0 = phi i16 [ 0, %entry ], [ %inc, %do.body ]
+  %arrayidx2 = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 %i.0
+  store i16 2, i16* %arrayidx2, align 1
+  %exitcond = icmp eq i16 %i.0, 4
+  %inc = add nuw nsw i16 %i.0, 1
+  br i1 %exitcond, label %exit, label %do.body
+
+exit:
+  %bc = bitcast i16* %arrayidx to i8*
+  %bc2 = getelementptr inbounds i8, i8* %bc, i32 1
+  store i8 10, i8* %bc, align 1
+  store i8 11, i8* %bc2, align 1
+  ret i16 0
+}
+
+define i16 @partial_override_multi(i1 %c, i32 %i) {
+; CHECK-LABEL: @partial_override_multi(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[DO_BODY:%.*]]
+; CHECK:       do.body:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i16 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[DO_BODY]] ]
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 [[I_0]]
+; CHECK-NEXT:    store i16 10, i16* [[ARRAYIDX2]], align 1
+; CHECK-NEXT:    [[BC:%.*]] = bitcast i16* [[ARRAYIDX2]] to i8*
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i16 [[I_0]], 4
+; CHECK-NEXT:    [[INC]] = add nuw nsw i16 [[I_0]], 1
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[DO_BODY]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[BC2:%.*]] = getelementptr inbounds i8, i8* [[BC]], i32 1
+; CHECK-NEXT:    store i8 11, i8* [[BC2]], align 1
+; CHECK-NEXT:    ret i16 0
+;
+entry:
+  br label %do.body
+
+do.body:
+  %i.0 = phi i16 [ 0, %entry ], [ %inc, %do.body ]
+  %arrayidx2 = getelementptr inbounds [10 x i16], [10 x i16]* @x, i16 0, i16 %i.0
+  store i16 2, i16* %arrayidx2, align 1
+  %bc = bitcast i16* %arrayidx2 to i8*
+  store i8 10, i8* %bc, align 1
+  %exitcond = icmp eq i16 %i.0, 4
+  %inc = add nuw nsw i16 %i.0, 1
+  br i1 %exitcond, label %exit, label %do.body
+
+exit:
+  %bc2 = getelementptr inbounds i8, i8* %bc, i32 1
+  store i8 11, i8* %bc2, align 1
+  ret i16 0
+}
+