[DSE] Merge stores when the later store only writes to memory locations the early store also wrote to.

[spatel]

Summary

This fixes PR31777.

If both stores' values are ConstantInt, we merge the two stores
(shifting the smaller store appropriately) and replace the earlier (and
larger) store with an updated constant.

In the future we should also support vectors of integers. And maybe
float/double if we can.

[filcab]

Added a test where we need to merge the same byte several times.

[junbuml]

test/Transforms/DeadStoreElimination/merge-stores.ll

6

I think the current code should handle this.

[filcab]

test/Transforms/DeadStoreElimination/merge-stores.ll

6

This specific test is about making sure we still do the current optimization (remove a store that's later shadowed by other stores). The code I added doesn't fire on this one (and it shouldn't). I can probably move it to the combine-partial-overwrites.ll test to make it consistent, though.

Some of the tests there got changed due to this patch.

[filcab]

Removed unneeded tests and disabled the new optimization in the old tests.

[RKSimon]

lib/Transforms/Scalar/DeadStoreElimination.cpp

301

As a NFC pre-commit please can you update these to match the style guide (OW_Begin ..... OW_Unknown)

test/Transforms/DeadStoreElimination/merge-stores.ll

6

Commit test with current codegen? Is it feasible to use update_test_checks.py here?

[filcab]

Added a big endian version of the test
Did the OW_... change in trunk, rebases
Used update_test_checks.py for the tests. A new run won't change the output.

[davide]

Filipe, did you take a look at the work @bryant is doing? (cc: @dberlin) He's implementing a full-fledged PDSE which I expect should cover also this case (partial stores).
Now, well, I'm not sure how far away is that from being ready (and probably this is something we want anyway in the meanwhile), but I think it's something you may want to look at independently.

[filcab]

In D30703#714535, @davide wrote:

Filipe, did you take a look at the work @bryant is doing? (cc: @dberlin) He's implementing a full-fledged PDSE which I expect should cover also this case (partial stores).
Now, well, I'm not sure how far away is that from being ready (and probably this is something we want anyway in the meanwhile), but I think it's something you may want to look at independently.

Thanks! I've looked at D29866 and it seems like it *might* deal with partial store merging/elimination in the future. But it's in a TODO, for now. So I think we could go ahead with this and, when PDSE grows that functionality, then remove it from here (or even just replace DSE with PDSE and we're done :-) ).
Thank you,
Filipe

[• dberlin]

In D30703#716674, @filcab wrote:

In D30703#714535, @davide wrote:

Filipe, did you take a look at the work @bryant is doing? (cc: @dberlin) He's implementing a full-fledged PDSE which I expect should cover also this case (partial stores).
Now, well, I'm not sure how far away is that from being ready (and probably this is something we want anyway in the meanwhile), but I think it's something you may want to look at independently.

Thanks! I've looked at D29866 and it seems like it *might* deal with partial store merging/elimination in the future. But it's in a TODO, for now. So I think we could go ahead with this and, when PDSE grows that functionality, then remove it from here (or even just replace DSE with PDSE and we're done :-) ).
Thank you,
Filipe

Just FYI, i expect we're going to add it prior to first commit.
It's not that hard.

(i don't have an opinion on this patch)

[filcab]

Ping!

[sanjoy]

lib/Transforms/Scalar/DeadStoreElimination.cpp

1192

You also need to copy over the atomicity of the previous store (which can only be unordered).

[filcab]

Address Sanjoy's comment and add Synchscope and atomic settings from the original store.

[RKSimon]

What is happening with this patch? Is PDSE likely to land anytime soon (e.g. for the 5.000 release?) and support this case?

[filcab]

@sanjoy: Are you ok with the changes I made?

Thank you,
Filipe

[sanjoy]

Some comments inline.

lib/Transforms/Scalar/DeadStoreElimination.cpp

304–305

Update doc.

446

Can LaterOff - EarlierOff sign overflow (in artificial but legal cases)?

452

Shouldn't this be FullEarlierWithPartialLater?

In a second change, I'd suggest changing the naming scheme to:

OW_Begin - OW_Prefix
OW_Complete - OW_Complete
OW_End - OW_Suffix
OW_PartialEarlierWithFullLater - OW_Partial
OW_Unknown - OW_Unknown

1178

I'd call this LShiftAmount.

1196

I'm not sure if copyMetadata is correct here. Someone could be using metadata to track "the value I'm storing here is positive" which may no longer be true after the rewrite. I think you should copy whitelisted metadata types (like !tbaa).

1200

Why is this needed? store instructions should not have users (and a WeakTrackingVH on a store is most likely doing the wrong thing).

[filcab]

Address Sanjoy's review comments

[filcab]

Hi @sanjoy. Can you take a look at the revised changes?

Thank you,
Filipe

lib/Transforms/Scalar/DeadStoreElimination.cpp

446

Probably yes. Redoing the math.

1 - Make sure LaterOff is between EarlierOff and EarlierOff + Earlier.Size. We know that addition won't overflow (if it does, the bug is in GetPointerBaseWithConstantOffset), so we'll know we can subtract EarlierOff from LaterOff later without problems, since they're ordered that way and the difference will be smaller than Earlier.Size.

452

Partial earlier store gets overwritten by a latter store (and the latter store doesn't write outside the "full" earlier store).

It's a weird way to phrase it, but I don't think changing it to your suggestion makes much sense (but I think I know what you mean).
I do think your renaming proposal for the whole enum makes sense, so I'll do that one.

1200

Removed.

[RKSimon]

ping?

[filcab]

Update for newer SynchScope API.
@sanjoy: Any thoughts?

Thank you,
Filipe

[sanjoy]

LGTM

lib/Transforms/Scalar/DeadStoreElimination.cpp

443

latter is correct, but I'd s/latter/later/ since that's what the source says.

1210

s|////|//|

[rnk]

We're seeing null derefs on some code in Chromium after this patch:

ninja -v -d keeprsp -C out\clang_tot obj/third_party/angle/libANGLE/Caps.obj
ninja.exe -v -d keeprsp -C out\clang_tot obj/third_party/angle/libANGLE/Caps.obj -j 46 -l 48
ninja: Entering directory `out\clang_tot'
[1 processes, 1/1 @ 0.2/s : 4.732s ] ../../third_party/llvm-build/Release+Asserts/bin/clang-cl.exe /nologo /showIncludes  @obj/third_party/angle/libANGLE/Caps.obj.rsp /c ../../third_party/angle/src/libANGLE/Caps.cpp /Foobj/third_party/angle/libANGLE/Caps.obj /Fd"obj/third_party/angle/libANGLE_cc.pdb"
FAILED: obj/third_party/angle/libANGLE/Caps.obj
../../third_party/llvm-build/Release+Asserts/bin/clang-cl.exe /nologo /showIncludes  @obj/third_party/angle/libANGLE/Caps.obj.rsp /c ../../third_party/angle/src/libANGLE/Caps.cpp /Foobj/third_party/angle/libANGLE/Caps.obj /Fd"obj/third_party/angle/libANGLE_cc.pdb"
Assertion failed: Val && "isa<> used on a null pointer", file C:\src\chromium3\src\third_party\llvm\include\llvm/Support/Casting.h, line 106
Wrote crash dump file "c:\src\Temp\clang-cl.exe-d4113f.dmp"
#0 0x00007ff6f6338775 HandleAbort c:\src\chromium3\src\third_party\llvm\lib\support\windows\signals.inc:411:0
#1 0x00007ff6f7b99769 raise minkernel\crts\ucrt\src\appcrt\misc\signal.cpp:516:0
#2 0x00007ff6f7b86df8 abort minkernel\crts\ucrt\src\appcrt\startup\abort.cpp:71:0
#3 0x00007ff6f7b86532 common_assert_to_stderr<wchar_t> minkernel\crts\ucrt\src\appcrt\startup\assert.cpp:149:0
#4 0x00007ff6f7b865ce _wassert minkernel\crts\ucrt\src\appcrt\startup\assert.cpp:404:0
#5 0x00007ff6f5ed6de3 llvm::GEPOperator::hasAllZeroIndices(void)const  c:\src\chromium3\src\third_party\llvm\include\llvm\ir\operator.h:456:0
#6 0x00007ff6f5ed32fe `anonymous namespace'::stripPointerCastsAndOffsets<1> c:\src\chromium3\src\third_party\llvm\lib\ir\value.cpp:483:0
#7 0x00007ff6f61bd100 isOverwrite c:\src\chromium3\src\third_party\llvm\lib\transforms\scalar\deadstoreelimination.cpp:326:0
#8 0x00007ff6f61b9bd6 eliminateDeadStores c:\src\chromium3\src\third_party\llvm\lib\transforms\scalar\deadstoreelimination.cpp:1131:0
#9 0x00007ff6f61ba7d7 eliminateDeadStores c:\src\chromium3\src\third_party\llvm\lib\transforms\scalar\deadstoreelimination.cpp:1265:0
#10 0x00007ff6f61bf55c `anonymous namespace'::DSELegacyPass::runOnFunction c:\src\chromium3\src\third_party\llvm\lib\transforms\scalar\deadstoreelimination.cpp:1308:0
#11 0x00007ff6f5ee35fd llvm::FPPassManager::runOnFunction(class llvm::Function &) c:\src\chromium3\src\third_party\llvm\lib\ir\legacypassmanager.cpp:1514:0
#12 0x00007ff6f5bdae07 `anonymous namespace'::CGPassManager::RunPassOnSCC c:\src\chromium3\src\third_party\llvm\lib\analysis\callgraphsccpass.cpp:149:0
#13 0x00007ff6f5bdab93 `anonymous namespace'::CGPassManager::RunAllPassesOnSCC c:\src\chromium3\src\third_party\llvm\lib\analysis\callgraphsccpass.cpp:418:0
#14 0x00007ff6f5bdba59 `anonymous namespace'::CGPassManager::runOnModule c:\src\chromium3\src\third_party\llvm\lib\analysis\callgraphsccpass.cpp:474:0
#15 0x00007ff6f5ee3a3e `anonymous namespace'::MPPassManager::runOnModule c:\src\chromium3\src\third_party\llvm\lib\ir\legacypassmanager.cpp:1591:0
#16 0x00007ff6f5ee2ef1 llvm::legacy::PassManagerImpl::run(class llvm::Module &) c:\src\chromium3\src\third_party\llvm\lib\ir\legacypassmanager.cpp:1695:0
#17 0x00007ff6f653810c `anonymous namespace'::EmitAssemblyHelper::EmitAssembly c:\src\chromium3\src\third_party\llvm\tools\clang\lib\codegen\backendutil.cpp:788:0
#18 0x00007ff6f653a140 clang::EmitBackendOutput(class clang::DiagnosticsEngine &,class clang::HeaderSearchOptions const &,class clang::CodeGenOptions const &,class clang::TargetOptions const &,class clang::LangOptions const &,class llvm::DataLayout const &,class llvm::Module *,enum clang::BackendAction,class std::unique_ptr<class llvm::raw_pwrite_stream,struct std::default_delete<class llvm::raw_pwrite_stream> >) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\codegen\backendutil.cpp:1148:0
#19 0x00007ff6f7cc3a31 clang::BackendConsumer::HandleTranslationUnit(class clang::ASTContext &) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\codegen\codegenaction.cpp:265:0
#20 0x00007ff6f68c6cbc clang::MultiplexConsumer::HandleTranslationUnit(class clang::ASTContext &) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\frontend\multiplexconsumer.cpp:305:0
#21 0x00007ff6f6f224d6 clang::ParseAST(class clang::Sema &,bool,bool) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\parse\parseast.cpp:162:0
#22 0x00007ff6f688654d clang::ASTFrontendAction::ExecuteAction(void) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\frontend\frontendaction.cpp:1005:0
#23 0x00007ff6f7cc30fb clang::CodeGenAction::ExecuteAction(void) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\codegen\codegenaction.cpp:992:0
#24 0x00007ff6f68863db clang::FrontendAction::Execute(void) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\frontend\frontendaction.cpp:906:0
#25 0x00007ff6f6873b65 clang::CompilerInstance::ExecuteAction(class clang::FrontendAction &) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\frontend\compilerinstance.cpp:981:0
#26 0x00007ff6f68f7bfd clang::ExecuteCompilerInvocation(class clang::CompilerInstance *) c:\src\chromium3\src\third_party\llvm\tools\clang\lib\frontendtool\executecompilerinvocation.cpp:252:0
#27 0x00007ff6f4fc5ff4 cc1_main(class llvm::ArrayRef<char const *>,char const *,void *) c:\src\chromium3\src\third_party\llvm\tools\clang\tools\driver\cc1_main.cpp:221:0
#28 0x00007ff6f4fc1d40 ExecuteCC1Tool c:\src\chromium3\src\third_party\llvm\tools\clang\tools\driver\driver.cpp:313:0
#29 0x00007ff6f4fc3b3a main c:\src\chromium3\src\third_party\llvm\tools\clang\tools\driver\driver.cpp:387:0
#30 0x00007ff6f7b6349d __scrt_common_main_seh f:\dd\vctools\crt\vcstartup\src\startup\exe_common.inl:283:0
#31 0x00007ff855298364 (C:\WINDOWS\System32\KERNEL32.DLL+0x8364)
#32 0x00007ff855e870d1 (C:\WINDOWS\SYSTEM32\ntdll.dll+0x670d1)
clang-cl.exe: error: clang frontend command failed due to signal (use -v to see invocation

I'll try to get a repro, but heads up.

[RKSimon]

Reopening as it was reverted at rL310123 due to PR34074

[RKSimon]

PR34074

[spatel]

llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp

1219–1221 ↗

(On Diff #109719)

I think @filcab is unable to get back to this patch currently and D29866 is not progressing.

I don't have a full understanding of DSE, but I'll propose a one-word fix to this patch (and an additional test case). It should avoid the bug that caused the patch to be reverted ( https://bugs.llvm.org/show_bug.cgi?id=34074 ).

This 'continue' should be a 'break'. We killed 'Inst' above, so 'InstDep' is no longer valid. Therefore, we can't carry on in the inner loop; we need to break back out to the outer loop and really 'start over' as the comment already says. :)

[spatel]

Commandeering so I can post the updated patch here.

[spatel]

Patch updated:

1. Break from the inner loop after we successfully merge (kill) the earlier and later stores.
2. Add test reduced from PR34074 that was crashing.

[filcab]

In D30703#880203, @spatel wrote:

Patch updated:

1. Break from the inner loop after we successfully merge (kill) the earlier and later stores.
2. Add test reduced from PR34074 that was crashing.

Thanks for comandeering and fixing it, Sanjay!
Your fix looks good on my end.

[RKSimon]

LGTM - cheers

lib/Transforms/Scalar/DeadStoreElimination.cpp

 using namespace llvm;
 
 #define DEBUG_TYPE "dse"
 
 STATISTIC(NumRedundantStores, "Number of redundant stores deleted");
 STATISTIC(NumFastStores, "Number of stores deleted");
 STATISTIC(NumFastOther , "Number of other instrs removed");
 STATISTIC(NumCompletePartials, "Number of stores dead by later partials");
+STATISTIC(NumModifiedStores, "Number of stores modified");
 
 static cl::opt<bool>
 EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking",
   cl::init(true), cl::Hidden,
   cl::desc("Enable partial-overwrite tracking in DSE"));
 
+static cl::opt<bool>
+EnablePartialStoreMerging("enable-dse-partial-store-merging",
+  cl::init(true), cl::Hidden,
+  cl::desc("Enable partial store merging in DSE"));
+
 
 //===----------------------------------------------------------------------===//
 // Helper functions
 //===----------------------------------------------------------------------===//
 typedef std::map<int64_t, int64_t> OverlapIntervalsTy;
 typedef DenseMap<Instruction *, OverlapIntervalsTy> InstOverlapIntervalsTy;
 
 /// Delete this instruction.  Before we do, go through and zero out all the
static uint64_t getPointerSize(const Value *V, const DataLayout &DL,
   return MemoryLocation::UnknownSize;
 }
 
 namespace {
 enum OverwriteResult {
   OverwriteBegin,
   OverwriteComplete,
   OverwriteEnd,
+  OverwritePartialEarlierWithFullLater,
   OverwriteUnknown
 };
 }
 
 /// Return 'OverwriteComplete' if a store to the 'Later' location completely
 /// overwrites a store to the 'Earlier' location, 'OverwriteEnd' if the end of
 /// the 'Earlier' location is completely overwritten by 'Later',
 /// 'OverwriteBegin' if the beginning of the 'Earlier' location is overwritten
 /// by 'Later', or 'OverwriteUnknown' if nothing can be determined.
 static OverwriteResult isOverwrite(const MemoryLocation &Later,
                                    const MemoryLocation &Earlier,
                                    const DataLayout &DL,
                                    const TargetLibraryInfo &TLI,
if (ILI->second <= EarlierOff &&
                       int64_t(EarlierOff + Earlier.Size) <<
                       ") Composite Later [" <<
                       ILI->second << ", " << ILI->first << ")\n");
       ++NumCompletePartials;
       return OverwriteComplete;
     }
   }
 
+  // Check for an earlier store which writes to all the memory locations that
+  // the latter store writes to.
+  if (EnablePartialStoreMerging && LaterOff >= EarlierOff &&
+      Earlier.Size >= Later.Size &&
+      uint64_t(LaterOff - EarlierOff) + Later.Size <= Earlier.Size) {
+    DEBUG(dbgs() << "DSE: Partial overwrite an earlier load [" << EarlierOff
+                 << ", " << int64_t(EarlierOff + Earlier.Size)
+                 << ") by a later store [" << LaterOff << ", "
+                 << int64_t(LaterOff + Later.Size) << ")\n");
+    // TODO: Maybe come up with a better name?
+    return OverwritePartialEarlierWithFullLater;
+  }
+
   // Another interesting case is if the later store overwrites the end of the
   // earlier store.
   //
   //      |--earlier--|
   //                |--   later   --|
   //
   // In this case we may want to trim the size of earlier to avoid generating
   // writes to addresses which will definitely be overwritten later
while (InstDep.isDef() || InstDep.isClobber()) {
         }
         if (!IsStoreDeadOnUnwind)
           break;
       }
 
       // If we find a write that is a) removable (i.e., non-volatile), b) is
       // completely obliterated by the store to 'Loc', and c) which we know that
       // 'Inst' doesn't load from, then we can remove it.
+      // Also try to merge two stores if a latter one only touches memory
+      // written to by the earlier one.
       if (isRemovable(DepWrite) &&
           !isPossibleSelfRead(Inst, Loc, DepWrite, *TLI, *AA)) {
         int64_t InstWriteOffset, DepWriteOffset;
         OverwriteResult OR =
             isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset, InstWriteOffset,
                         DepWrite, IOL);
         if (OR == OverwriteComplete) {
           DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: "
while (InstDep.isDef() || InstDep.isClobber()) {
           assert(!EnablePartialOverwriteTracking && "Do not expect to perform "
                                                     "when partial-overwrite "
                                                     "tracking is enabled");
           int64_t EarlierSize = DepLoc.Size;
           int64_t LaterSize = Loc.Size;
           bool IsOverwriteEnd = (OR == OverwriteEnd);
           MadeChange |= tryToShorten(DepWrite, DepWriteOffset, EarlierSize,
                                     InstWriteOffset, LaterSize, IsOverwriteEnd);
+        } else if (EnablePartialStoreMerging &&
+                   OR == OverwritePartialEarlierWithFullLater) {
+          auto *Earlier = dyn_cast<StoreInst>(DepWrite);
+          auto *Later = dyn_cast<StoreInst>(Inst);
+          if (Earlier && isa<ConstantInt>(Earlier->getValueOperand()) &&
+              Later && isa<ConstantInt>(Later->getValueOperand())) {
+            // If the store we find is:
+            //   a) partially overwritten by the store to 'Loc'
+            //   b) the latter store is fully contained in the earlier one and
+            //   c) They both have a contant 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)
+
+            APInt EarlierValue =
+                cast<ConstantInt>(Earlier->getValueOperand())->getValue();
+            APInt LaterValue =
+                cast<ConstantInt>(Later->getValueOperand())->getValue();
+            unsigned LaterBits = LaterValue.getBitWidth();
+            assert(EarlierValue.getBitWidth() > LaterValue.getBitWidth());
+            LaterValue = LaterValue.zext(EarlierValue.getBitWidth());
+
+            // Offset of the smaller store inside the larger store
+            unsigned BitOffsetDiff = (InstWriteOffset - DepWriteOffset) * 8;
+            unsigned ShiftAmount =
+                DL.isBigEndian()
+                    ? EarlierValue.getBitWidth() - BitOffsetDiff - LaterBits
+                    : BitOffsetDiff;
+            APInt Mask =
+                APInt::getBitsSet(EarlierValue.getBitWidth(), ShiftAmount,
+                                  ShiftAmount + LaterBits);
+            // Clear the bits we'll be replacing, then OR with the smaller
+            // store, shifted appropriately.
+            APInt Merged = (EarlierValue & ~Mask) | (LaterValue << ShiftAmount);
+            DEBUG(dbgs() << "DSE: Merge Stores:\n  Earlier: " << *DepWrite
+                         << "\n  Later: " << *Inst
+                         << "\n  Merged Value: " << Merged << '\n');
+
+            auto *SI = new StoreInst(
+                ConstantInt::get(Earlier->getValueOperand()->getType(), Merged),
+                Earlier->getPointerOperand(), false, Earlier->getAlignment(),
+                DepWrite);
+            SI->copyMetadata(*DepWrite);
+            ++NumModifiedStores;
+
+            // Replace earlier, wider, store
+            DepWrite->replaceAllUsesWith(SI);
+            size_t Idx = InstrOrdering.lookup(DepWrite);
+            InstrOrdering.erase(DepWrite);
+            InstrOrdering.insert(std::make_pair(SI, Idx));
+
+            //// Delete the old stores and now-dead instructions that feed them.
+            deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL, &InstrOrdering);
+            deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
+                                  &InstrOrdering);
+            MadeChange = true;
+
+            //// We erased DepWrite; start over.
+            InstDep = MD->getDependency(SI);
+            continue;
+          }
         }
       }
 
       // If this is a may-aliased store that is clobbering the store value, we
       // can keep searching past it for another must-aliased pointer that stores
       // to the same location.  For example, in:
       //   store -> P
       //   store -> Q

test/Transforms/DeadStoreElimination/PartialStore.ll

 ; RUN: opt < %s -basicaa -dse -S | FileCheck %s
 target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
 
 ; Ensure that the dead store is deleted in this case.  It is wholely
 ; overwritten by the second store.
 define void @test1(i32 *%V) {
         %V2 = bitcast i32* %V to i8*            ; <i8*> [#uses=1]
         store i8 0, i8* %V2
         store i32 1234567, i32* %V
         ret void
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT: store i32 1234567
 }
 
-; Note that we could do better by merging the two stores into one.
+; Check that we merge these two stores
 define void @test2(i32* %P) {
 ; CHECK-LABEL: @test2(
   store i32 0, i32* %P
-; CHECK: store i32
   %Q = bitcast i32* %P to i16*
   store i16 1, i16* %Q
-; CHECK: store i16
+; CHECK-NOT: store
+; Big endian store, so we get 1<<16 as the merged value
+; CHECK: store i32 65536, i32* %P
+; CHECK-NOT: store
   ret void
 }
 
 
 define i32 @test3(double %__x) {
 ; CHECK-LABEL: @test3(
 ; CHECK: store double
   %__u = alloca { [3 x i32] }

test/Transforms/DeadStoreElimination/combined-partial-overwrites.ll

  store i8 25, i8* %bptr2
  %bptr3 = getelementptr inbounds i8, i8* %bptr, i64 3
  store i8 47, i8* %bptr3
  %bptr1 = getelementptr inbounds i8, i8* %bptr, i64 1
  %wptrp = bitcast i8* %bptr1 to i16*
  store i16 2020, i16* %wptrp, align 1
  ret void
 
-; CHECK-NOT: store i32 5, i32* %ptr
-; CHECK-NOT: store i8 7, i8* %bptr
-; CHECK: store i16 -30062, i16* %wptr
-; CHECK-NOT: store i8 25, i8* %bptr2
-; CHECK: store i8 47, i8* %bptr3
-; CHECK: store i16 2020, i16* %wptrp, align 1
-
+; CHECK-NOT: store
+; CHECK: store i32 -1979194321, i32* %ptr
+; CHECK-NOT: store
 ; CHECK: ret void
 }
 
 define void @test2(i32 *%ptr) {
 entry:
 ; CHECK-LABEL: @test2
 
   store i32 5, i32* %ptr
; CHECK-LABEL: @test2
   %wptr3 = bitcast i8* %bptr3 to i16*
 
   store i16 1456, i16* %wptrm1, align 1
   store i16 1346, i16* %wptr, align 1
   store i16 1756, i16* %wptr1, align 1
   store i16 1126, i16* %wptr2, align 1
   store i16 5656, i16* %wptr3, align 1
 
-; CHECK-NOT: store i32 5, i32* %ptr
-
+; CHECK-NEXT: entry:
+; CHECK-NEXT: store i32 84280422, i32* %ptr
+; All the intermediate stored bytes that are fully contained in the i32 memory
+; region get merged to the i32 store.
+; CHECK-NOT: store
 ; CHECK: store i16 1456, i16* %wptrm1, align 1
-; CHECK: store i16 1346, i16* %wptr, align 1
-; CHECK: store i16 1756, i16* %wptr1, align 1
-; CHECK: store i16 1126, i16* %wptr2, align 1
-; CHECK: store i16 5656, i16* %wptr3, align 1
+; CHECK-NEXT: store i16 5656, i16* %wptr3, align 1
+; CHECK-NOT: store
 
   ret void
 
 ; CHECK: ret void
 }
 
 define signext i8 @test3(i32 *%ptr) {
 entry:
; CHECK-LABEL: @test3
 
   %v = load i8, i8* %bptr, align 1
   store i16 1456, i16* %wptrm1, align 1
   store i16 1346, i16* %wptr, align 1
   store i16 1756, i16* %wptr1, align 1
   store i16 1126, i16* %wptr2, align 1
   store i16 5656, i16* %wptr3, align 1
 
-; CHECK: store i32 5, i32* %ptr
+; CHECK-NEXT: entry:
+; Top (first) byte is 0x00 because we load from it in between the two stores.
+; CHECK-NEXT:  store i32 394342, i32* %ptr
+; CHECK-NOT: store
+; CHECK:  store i16 1456, i16* %wptrm1, align 1
+; CHECK-NEXT: store i16 1346, i16* %wptr, align 1
+; CHECK-NEXT:  store i16 5656, i16* %wptr3, align 1
+; CHECK-NOT: store
 
   ret i8 %v
 
 ; CHECK: ret i8 %v
 }
 
 %struct.foostruct = type {
 i32 (i8*, i8**, i32, i8, i8*)*,

test/Transforms/DeadStoreElimination/merge-stores.ll

+; RUN: opt -dse -enable-dse-partial-store-merging -S < %s | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-f128:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK-LABEL: @combine_overlapping_stores
+define void @combine_overlapping_stores(i32 *%ptr) {
+entry:
+  ;; This store should disappear, it should not be merged since we can't remove
+  ;; the latter ones (they're not fully contained in this one) and the latter
+  ;; ones overwrite the whole memory region written to by this store.
+  store i32 305419896, i32* %ptr  ; 0x12345678
+  %wptr = bitcast i32* %ptr to i16*
+  %wptrm1 = getelementptr inbounds i16, i16* %wptr, i64 -1  ; Lower 2B
+  %wptrp1 = getelementptr inbounds i16, i16* %wptr, i64 1   ; Upper 2B
+  %ptrL2B = bitcast i16* %wptrm1 to i32*
+  %ptrU2B = bitcast i16* %wptrp1 to i32*
+
+  store i32 1126266452, i32* %ptrL2B  ; 0x43217654
+  store i32 1985229328, i32* %ptrU2B  ; 0x76543210
+
+; CHECK-NEXT: entry:
+; CHECK-NOT: store
+; CHECK: store i32 1126266452, i32* %ptrL2B
+; CHECK-NEXT: store i32 1985229328, i32* %ptrU2B
+; CHECK-NOT: store
+; CHECK-NEXT: ret void
+  ret void
+}
+
+; CHECK-LABEL: @byte_by_byte_replacement
+define void @byte_by_byte_replacement(i32 *%ptr) {
+entry:
+  ;; This store's value should be modified as it should be better to use larger
+  ;; stores than smaller ones.
+  store i32 305419896, i32* %ptr  ; 0x12345678
+  %bptr = bitcast i32* %ptr to i8*
+  %bptr1 = getelementptr inbounds i8, i8* %bptr, i64 1
+  %bptr2 = getelementptr inbounds i8, i8* %bptr, i64 2
+  %bptr3 = getelementptr inbounds i8, i8* %bptr, i64 3
+
+  store i8 9, i8* %bptr
+  store i8 10, i8* %bptr1
+  store i8 11, i8* %bptr2
+  store i8 12, i8* %bptr3
+
+; CHECK-NEXT: entry:
+; CHECK-NOT: store
+; CHECK: store i32 202050057, i32* %ptr
+; CHECK-NOT: store
+; CHECK-NEXT: ret void
+  ret void
+}
+
+; CHECK-LABEL: @word_replacement
+define void @word_replacement(i64 *%ptr) {
+entry:
+  store i64 72623859790382856, i64* %ptr  ; 0x0102030405060708
+
+  %wptr = bitcast i64* %ptr to i16*
+  %wptr1 = getelementptr inbounds i16, i16* %wptr, i64 1
+  %wptr2 = getelementptr inbounds i16, i16* %wptr, i64 2
+  %wptr3 = getelementptr inbounds i16, i16* %wptr, i64 3
+
+  ;; We should be able to merge these two stores with the i64 one above
+  store i16  4128, i16* %wptr1  ; 0x1020
+  store i16 28800, i16* %wptr3  ; 0x7080
+
+; CHECK-NEXT: entry:
+; CHECK-NOT: store
+;                 0x0807201004038070
+; CHECK: store i64 8106482645252179720, i64* %ptr
+; CHECK-NOT: store
+; CHECK-NEXT: ret void
+  ret void
+}
+
+
+; CHECK-LABEL: @differently_sized_replacements
+define void @differently_sized_replacements(i64 *%ptr) {
+entry:
+  store i64 579005069656919567, i64* %ptr  ; 0x08090a0b0c0d0e0f
+
+  %bptr = bitcast i64* %ptr to i8*
+  %bptr6 = getelementptr inbounds i8, i8* %bptr, i64 6
+  %wptr = bitcast i64* %ptr to i16*
+  %wptr2 = getelementptr inbounds i16, i16* %wptr, i64 2
+  %dptr = bitcast i64* %ptr to i32*
+
+  ;; We should be able to merge all these stores with the i64 one above
+  ; value (not bytes) stored before  ; 08090a0b0c0d0e0f
+  store i8         7, i8*  %bptr6    ;   07
+  store i16     1541, i16* %wptr2    ;     0605
+  store i32 67305985, i32* %dptr     ;         04030201
+
+; CHECK-NEXT: entry:
+; CHECK-NOT: store
+;                 0x0807060504030201
+; CHECK: store i64 578437695752307201, i64* %ptr
+; CHECK-NOT: store
+; CHECK-NEXT: ret void
+  ret void
+}
+
+
+; CHECK-LABEL: @multiple_replacements_to_same_byte
+define void @multiple_replacements_to_same_byte(i64 *%ptr) {
+entry:
+  store i64 579005069656919567, i64* %ptr  ; 0x08090a0b0c0d0e0f
+
+  %bptr = bitcast i64* %ptr to i8*
+  %bptr3 = getelementptr inbounds i8, i8* %bptr, i64 3
+  %wptr = bitcast i64* %ptr to i16*
+  %wptr1 = getelementptr inbounds i16, i16* %wptr, i64 1
+  %dptr = bitcast i64* %ptr to i32*
+
+  ;; We should be able to merge all these stores with the i64 one above
+  ; value (not bytes) stored before  ; 08090a0b0c0d0e0f
+  store i8         7, i8*  %bptr3    ;         07
+  store i16     1541, i16* %wptr1    ;         0605
+  store i32 67305985, i32* %dptr     ;         04030201
+
+; CHECK-NEXT: entry:
+; CHECK-NOT: store
+;                 0x08090a0b04030201
+; CHECK: store i64 579005069522043393, i64* %ptr
+; CHECK-NOT: store
+; CHECK-NEXT: ret void
+  ret void
+}
+
+; CHECK-LABEL: @merged_merges
+define void @merged_merges(i64 *%ptr) {
+entry:
+  store i64 579005069656919567, i64* %ptr  ; 0x08090a0b0c0d0e0f
+
+  %bptr = bitcast i64* %ptr to i8*
+  %bptr3 = getelementptr inbounds i8, i8* %bptr, i64 3
+  %wptr = bitcast i64* %ptr to i16*
+  %wptr1 = getelementptr inbounds i16, i16* %wptr, i64 1
+  %dptr = bitcast i64* %ptr to i32*
+
+  ;; We should be able to merge all these stores with the i64 one above
+  ; value (not bytes) stored before  ; 08090a0b0c0d0e0f
+  store i32 67305985, i32* %dptr     ;         04030201
+  store i16     1541, i16* %wptr1    ;         0605
+  store i8         7, i8*  %bptr3    ;         07
+
+; CHECK-NEXT: entry:
+; CHECK-NOT: store
+;                 0x08090a0b07050201
+; CHECK: store i64 579005069572506113, i64* %ptr
+; CHECK-NOT: store
+; CHECK-NEXT: ret void
+  ret void
+}
+
+;; Test case from PR31777
+%union.U = type { i64 }
+
+; CHECK-LABEL: @foo
+define void @foo(%union.U* nocapture %u) {
+entry:
+; CHECK-NOT: store
+; CHECK: store i64 42, i64* %i, align 8
+; CHECK-NEXT: ret void
+  %i = getelementptr inbounds %union.U, %union.U* %u, i64 0, i32 0
+  store i64 0, i64* %i, align 8
+  %s = bitcast %union.U* %u to i16*
+  store i16 42, i16* %s, align 8
+  ret void
+}