[DSE] make sure memory is not modified before partial store merging (PR36129)

[spatel]

Summary

We missed a critical check in D30703. We must make sure that no intermediate store is sitting between the stores that we want to merge.

This should fix:
https://bugs.llvm.org/show_bug.cgi?id=36129

Thanks to Dave Green for the reduction and suggestion.

[dmgreen]

Looks good to me. Thanks for the speedy fix!

lib/Transforms/Scalar/DeadStoreElimination.cpp

while (InstDep.isDef() || InstDep.isClobber()) {
           bool IsOverwriteEnd = (OR == OW_End);
           MadeChange |= tryToShorten(DepWrite, DepWriteOffset, EarlierSize,
                                     InstWriteOffset, LaterSize, IsOverwriteEnd);
         } else if (EnablePartialStoreMerging &&
                    OR == OW_PartialEarlierWithFullLater) {
           auto *Earlier = dyn_cast<StoreInst>(DepWrite);
           auto *Later = dyn_cast<StoreInst>(Inst);
           if (Earlier && isa<ConstantInt>(Earlier->getValueOperand()) &&
-              Later && isa<ConstantInt>(Later->getValueOperand())) {
+              Later && isa<ConstantInt>(Later->getValueOperand()) &&
+              memoryIsNotModifiedBetween(Earlier, Later, AA)) {
             // If the store we find is:
             //   a) partially overwritten by the store to 'Loc'
             //   b) the later store is fully contained in the earlier one and
             //   c) they both have a constant value
             // Merge the two stores, replacing the earlier store's value with a
             // merge of both values.
             // TODO: Deal with other constant types (vectors, etc), and probably
             // some mem intrinsics (if needed)

test/Transforms/DeadStoreElimination/merge-stores.ll

 ;
   store i64 42, i64* %y          ; independent store
   %xbc = bitcast i32* %x to i8*
   store i32 0, i32* %x           ; big store of constant
   store i8 4, i8* %xbc           ; small store with mergeable constant
   ret void
 }
 
-; FIXME: We can't eliminate the last store because P and Q may alias.
+; We can't eliminate the last store because P and Q may alias.
 
 define void @PR36129(i32* %P, i32* %Q) {
 ; CHECK-LABEL: @PR36129(
-; CHECK-NEXT:    store i32 3, i32* [[P:%.*]]
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P]] to i8*
 ; CHECK-NEXT:    store i32 2, i32* [[Q:%.*]]
+; CHECK-NEXT:    store i8 3, i8* [[P2]]
 ; CHECK-NEXT:    ret void
 ;
   store i32 1, i32* %P
   %P2 = bitcast i32* %P to i8*
   store i32 2, i32* %Q
   store i8 3, i8* %P2
   ret void
 }