Sink store based on alias analysis

[ellab]

Summary

Similarly to patch D5991, I use alias analysis to define whether the given instruction is a barrier for store sinking.
For 2 identical stores, following instructions are checked in the both basic blocks, to determine whether they are sinking barriers.

[hfinkel]

include/llvm/Analysis/AliasAnalysis.h

8

I agree, this seems like a useful generalization. 'RefModify' seems odd to me, however. We use ModRef for most related things, how about:

canInstructionRangeModRef

lib/Transforms/IPO/ArgumentPromotion.cpp

2

Indentation seems off here.

lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

-2

We know that Inst is a store, so this should be cast, not dyn_cast.

-5–1

Why did you add the Inst->isUsedOutsideOfBlock check. We know that Inst is a store, and stores can't be 'used' anywhere.

4

I think we prefer the logical operator before the line break, not after. Can you move the first '&&' to the line above?

[ellab]

Applied hfinkel's comments

[Gerolf]

include/llvm/Analysis/AliasAnalysis.h

519

mode -> Mode

lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

148

Rename to SI

430

You could pass Loc as the third parameter and save one call to getLocation.

test/Transforms/InstMerge/st_sink_no_barrier_call.ll

46

Please remove

[ellab]

Applied Gerolf's comments

[ellab]

test/Transforms/InstMerge/st_sink_no_barrier_call.ll

46

If I remove the attribute, the call to foo will be a barrier (as in the test above - st_sink_barrier_call).

[reames]

include/llvm/Analysis/AliasAnalysis.h

509

It would be good to keep this interface consistent with the one you're changing. Leaving wrappers for the old interface names would be fine, or converting the BasicBlock versions to the ModRef form. I'd slightly prefer leaving convenience wrappers under the old names.

lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

421–432

Rather than stopping on the first readwrite call, this function will now rescan the end of the basic block for each store in the basic block. That seems mildly expensive: O(N^2) in the number of instructions in the BB. Have you considered the implications for compile time?

424

Use cast.

[delena]

lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

421–432

Hi Philip,

We already discussed about this when I implemented load hoisting. When you go through the first basic block, you don't know what to check. Because not every store/load is a barrier.

We are looking at pointer location while going through the second block. If the both strore instructions are indentical we start to look for a barrier - we do less checks in comparison to the previous implementation.
I do not expect the implications for compile time in this case.

• Elena

[ellab]

changed the cast syntax

[ellab]

include/llvm/Analysis/AliasAnalysis.h

509

I am not sure I understand.
I left the names of canBasicBlockModify as is.
However, I changed the name of the canInstructionRangeModRef convenience wrapper as it is no longer only modify (I now noticed the comment was not changed - will update now).
Do you think it should have been done somehow otherwise?

[ellab]

Fixed a comment

[Gerolf]

Other than nits it LGTM. Thanks for your nice work!

include/llvm/Analysis/AliasAnalysis.h

515

mode -> Mode (capital letter)

515

You could clean up the legacy common from "the value pointed to by Ptr" to "the Location" (or \param Location)

525

It should be Mode (capital M).

lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

424

There is similar legacy code you might want to clean up too, And you could use auto.

[ellab]

Applied Gerolf's comments

[delena]

This revision is committed. Turned to "Accept" in order to close.

include/llvm/Analysis/AliasAnalysis.h

 //===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the generic AliasAnalysis interface, which is used as the
 // common interface used by all clients of alias analysis information, and
 // implemented by all alias analysis implementations.  Mod/Ref information is
 // also captured by this interface.
 //
 // Implementations of this interface must implement the various virtual methods,
 // which automatically provides functionality for the entire suite of client
public:
   /// Higher level methods for querying mod/ref information.
   ///
 
   /// canBasicBlockModify - Return true if it is possible for execution of the
   /// specified basic block to modify the value pointed to by Ptr.
   bool canBasicBlockModify(const BasicBlock &BB, const Location &Loc);
 
   /// canBasicBlockModify - A convenience wrapper.
   bool canBasicBlockModify(const BasicBlock &BB, const Value *P, uint64_t Size){
     return canBasicBlockModify(BB, Location(P, Size));
   }
 
-  /// canInstructionRangeModify - Return true if it is possible for the
-  /// execution of the specified instructions to modify the value pointed to by
-  /// Ptr.  The instructions to consider are all of the instructions in the
-  /// range of [I1,I2] INCLUSIVE.  I1 and I2 must be in the same basic block.
-  bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2,
-                                 const Location &Loc);
-
-  /// canInstructionRangeModify - A convenience wrapper.
-  bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2,
-                                 const Value *Ptr, uint64_t Size) {
-    return canInstructionRangeModify(I1, I2, Location(Ptr, Size));
+  /// canInstructionRangeModRef - Return true if it is possible for the
+  /// execution of the specified instructions to mod\ref (according to the
+  /// mode) the value pointed to by Ptr. The instructions to consider are all
+  /// of the instructions in the range of [I1,I2] INCLUSIVE.
+  /// I1 and I2 must be in the same basic block.
+  bool canInstructionRangeModRef(const Instruction &I1,
+                                const Instruction &I2, const Location &Loc,
+                                const ModRefResult mode);
+
+  /// canInstructionRangeModRef - A convenience wrapper.
+  bool canInstructionRangeModRef(const Instruction &I1,
+                                 const Instruction &I2, const Value *Ptr,
+                                 uint64_t Size, const ModRefResult mode) {
+    return canInstructionRangeModRef(I1, I2, Location(Ptr, Size), mode);
   }
 
   //===--------------------------------------------------------------------===//
   /// Methods that clients should call when they transform the program to allow
   /// alias analyses to update their internal data structures.  Note that these
   /// methods may be called on any instruction, regardless of whether or not
   /// they have pointer-analysis implications.
   ///

lib/Analysis/AliasAnalysis.cpp

uint64_t AliasAnalysis::getTypeStoreSize(Type *Ty) {
   return DL ? DL->getTypeStoreSize(Ty) : UnknownSize;
 }
 
 /// canBasicBlockModify - Return true if it is possible for execution of the
 /// specified basic block to modify the value pointed to by Ptr.
 ///
 bool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB,
                                         const Location &Loc) {
-  return canInstructionRangeModify(BB.front(), BB.back(), Loc);
+  return canInstructionRangeModRef(BB.front(), BB.back(), Loc, Mod);
 }
 
-/// canInstructionRangeModify - Return true if it is possible for the execution
-/// of the specified instructions to modify the value pointed to by Ptr.  The
-/// instructions to consider are all of the instructions in the range of [I1,I2]
-/// INCLUSIVE.  I1 and I2 must be in the same basic block.
-///
-bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1,
+/// canInstructionRangeModRef - Return true if it is possible for the
+/// execution of the specified instructions to mod\ref (according to the
+/// mode) the value pointed to by Ptr. The instructions to consider are all
+/// of the instructions in the range of [I1,I2] INCLUSIVE.
+/// I1 and I2 must be in the same basic block.  
+bool AliasAnalysis::canInstructionRangeModRef(const Instruction &I1,
                                               const Instruction &I2,
-                                              const Location &Loc) {
+                                              const Location &Loc,
+                                              const ModRefResult mode) {
   assert(I1.getParent() == I2.getParent() &&
          "Instructions not in same basic block!");
   BasicBlock::const_iterator I = &I1;
   BasicBlock::const_iterator E = &I2;
   ++E;  // Convert from inclusive to exclusive range.
 
   for (; I != E; ++I) // Check every instruction in range
-    if (getModRefInfo(I, Loc) & Mod)
+    if (getModRefInfo(I, Loc) & mode)
       return true;
   return false;
 }
 
 /// isNoAliasCall - Return true if this pointer is returned by a noalias
 /// function.
 bool llvm::isNoAliasCall(const Value *V) {
   if (isa<CallInst>(V) || isa<InvokeInst>(V))

lib/Transforms/IPO/ArgumentPromotion.cpp

 //===-- ArgumentPromotion.cpp - Promote by-reference arguments ------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass promotes "by reference" arguments to be "by value" arguments.  In
bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg,
 
   for (unsigned i = 0, e = Loads.size(); i != e; ++i) {
     // Check to see if the load is invalidated from the start of the block to
     // the load itself.
     LoadInst *Load = Loads[i];
     BasicBlock *BB = Load->getParent();
 
     AliasAnalysis::Location Loc = AA.getLocation(Load);
-    if (AA.canInstructionRangeModify(BB->front(), *Load, Loc))
+    if (AA.canInstructionRangeModRef(BB->front(), *Load, Loc,
+        AliasAnalysis::Mod))
       return false;  // Pointer is invalidated!
 
     // Now check every path from the entry block to the load for transparency.
     // To do this, we perform a depth first search on the inverse CFG from the
     // loading block.
     for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
       BasicBlock *P = *PI;
       for (BasicBlock *TranspBB : inverse_depth_first_ext(P, TranspBlocks))

lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

 //===- MergedLoadStoreMotion.cpp - merge and hoist/sink load/stores -------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //! \file
 //! \brief This pass performs merges of loads and stores on both sides of a
 //  diamond (hammock). It hoists the loads and sinks the stores.
private:
   void hoistInstruction(BasicBlock *BB, Instruction *HoistCand,
                         Instruction *ElseInst);
   bool isSafeToHoist(Instruction *I) const;
   bool hoistLoad(BasicBlock *BB, LoadInst *HoistCand, LoadInst *ElseInst);
   bool mergeLoads(BasicBlock *BB);
   // Routines for sinking stores
   StoreInst *canSinkFromBlock(BasicBlock *BB, StoreInst *SI);
   PHINode *getPHIOperand(BasicBlock *BB, StoreInst *S0, StoreInst *S1);
-  bool isStoreSinkBarrier(Instruction *Inst);
+  bool isStoreSinkBarrierInRange(const Instruction& Start,
+                                 const Instruction& End,
+                                 AliasAnalysis::Location Loc);
   bool sinkStore(BasicBlock *BB, StoreInst *SinkCand, StoreInst *ElseInst);
   bool mergeStores(BasicBlock *BB);
   // The mergeLoad/Store algorithms could have Size0 * Size1 complexity,
   // where Size0 and Size1 are the #instructions on the two sides of
   // the diamond. The constant chosen here is arbitrary. Compiler Time
   // Control is enforced by the check Size0 * Size1 < MagicCompileTimeControl.
   const int MagicCompileTimeControl;
 };

 /// being loaded or protect against the load from happening
 /// it is considered a hoist barrier.
 ///
 
 bool MergedLoadStoreMotion::isLoadHoistBarrierInRange(const Instruction& Start, 
                                                       const Instruction& End,
                                                       LoadInst* LI) {
   AliasAnalysis::Location Loc = AA->getLocation(LI);
-  return AA->canInstructionRangeModify(Start, End, Loc);
+  return AA->canInstructionRangeModRef(Start, End, Loc, AliasAnalysis::Mod);
 }
 
 ///
 /// \brief Decide if a load can be hoisted
 ///
 /// When there is a load in \p BB to the same address as \p LI
 /// and it can be hoisted from \p BB, return that load.
 /// Otherwise return Null.
if (LoadInst *L1 = canHoistFromBlock(Succ1, L0)) {
       if (!Res)
         break;
     }
   }
   return MergedLoads;
 }
 
 ///
-/// \brief True when instruction is sink barrier for a store
-/// 
-bool MergedLoadStoreMotion::isStoreSinkBarrier(Instruction *Inst) {
-  // FIXME: Conservatively let a load instruction block the store.
-  // Use alias analysis instead.
-  if (isa<LoadInst>(Inst))
-    return true;
-  if (isa<CallInst>(Inst))
-    return true;
-  if (isa<TerminatorInst>(Inst) && !isa<BranchInst>(Inst))
-    return true;
-  // Note: mayHaveSideEffects covers all instructions that could
-  // trigger a change to state. Eg. in-flight stores have to be executed
-  // before ordered loads or fences, calls could invoke functions that store
-  // data to memory etc.
-  if (!isa<StoreInst>(Inst) && Inst->mayHaveSideEffects()) {
-    return true;
-  }
-  DEBUG(dbgs() << "No Sink Barrier\n");
-  return false;
+/// \brief True when instruction is a sink barrier for a store
+/// located in Loc
+///
+/// Whenever an instruction could possibly read or modify the
+/// value being stored or protect against the store from
+/// happening it is considered a sink barrier.
+///
+
+bool MergedLoadStoreMotion::isStoreSinkBarrierInRange(const Instruction& Start,
+                                                      const Instruction& End,
+                                                      AliasAnalysis::Location
+                                                      Loc) {
+  return AA->canInstructionRangeModRef(Start, End, Loc, AliasAnalysis::Ref);
 }
 
 ///
 /// \brief Check if \p BB contains a store to the same address as \p SI
 ///
 /// \return The store in \p  when it is safe to sink. Otherwise return Null.
 ///
-StoreInst *MergedLoadStoreMotion::canSinkFromBlock(BasicBlock *BB,
-                                                   StoreInst *SI) {
-  StoreInst *I = 0;
-  DEBUG(dbgs() << "can Sink? : "; SI->dump(); dbgs() << "\n");
-  for (BasicBlock::reverse_iterator RBI = BB->rbegin(), RBE = BB->rend();
+StoreInst *MergedLoadStoreMotion::canSinkFromBlock(BasicBlock *BB1,
+                                                   StoreInst *Store0) {
+  DEBUG(dbgs() << "can Sink? : "; Store0->dump(); dbgs() << "\n");
+  for (BasicBlock::reverse_iterator RBI = BB1->rbegin(), RBE = BB1->rend();
        RBI != RBE; ++RBI) {
     Instruction *Inst = &*RBI;
 
-    // Only move loads if they are used in the block.
-    if (isStoreSinkBarrier(Inst))
-      break;
-    if (isa<StoreInst>(Inst)) {
-      AliasAnalysis::Location LocSI = AA->getLocation(SI);
-      AliasAnalysis::Location LocInst = AA->getLocation((StoreInst *)Inst);
-      if (AA->isMustAlias(LocSI, LocInst)) {
-        I = (StoreInst *)Inst;
-        break;
-      }
+    if (!isa<StoreInst>(Inst))
+       continue;
+
+    StoreInst *Store1 = cast<StoreInst>(Inst);
+    BasicBlock *BB0 = Store0->getParent();
+
+    AliasAnalysis::Location Loc0 = AA->getLocation(Store0);
+    AliasAnalysis::Location Loc1 = AA->getLocation(Store1);
+    if (AA->isMustAlias(Loc0, Loc1) && Store0->isSameOperationAs(Store1) &&
+      !isStoreSinkBarrierInRange(*Store1, BB1->back(), Loc1) &&
+      !isStoreSinkBarrierInRange(*Store0, BB0->back(), Loc0)) {
+      return Store1;
     }
   }
-  return I;
+  return nullptr;
 }
 
 ///
 /// \brief Create a PHI node in BB for the operands of S0 and S1
 ///
 PHINode *MergedLoadStoreMotion::getPHIOperand(BasicBlock *BB, StoreInst *S0,
                                               StoreInst *S1) {
   // Create a phi if the values mismatch.
bool MergedLoadStoreMotion::mergeStores(BasicBlock *T) {
   int Size1 = Pred1->size();
   int NStores = 0;
 
   for (BasicBlock::reverse_iterator RBI = Pred0->rbegin(), RBE = Pred0->rend();
        RBI != RBE;) {
 
     Instruction *I = &*RBI;
     ++RBI;
-    if (isStoreSinkBarrier(I))
-      break;
+
     // Sink move non-simple (atomic, volatile) stores
     if (!isa<StoreInst>(I))
       continue;
     StoreInst *S0 = (StoreInst *)I;
     if (!S0->isSimple())
       continue;
 
     ++NStores;

test/Transforms/InstMerge/st_sink_barrier_call.ll

+; Test to make sure that a function call that needs to be a barrier to sinking stores is indeed a barrier.
+; Stores sunks into the footer.
+; RUN: opt -basicaa -memdep -mldst-motion -S < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+%struct.node = type { i32, %struct.node*, %struct.node*, %struct.node*, i32, i32, i32, i32 }
+
+declare i32 @foo(i32 %x)
+
+; Function Attrs: nounwind uwtable
+define void @sink_store(%struct.node* nocapture %r, i32 %index) {
+entry:
+  %node.0.in16 = getelementptr inbounds %struct.node* %r, i64 0, i32 2
+  %node.017 = load %struct.node** %node.0.in16, align 8
+  %index.addr = alloca i32, align 4
+  store i32 %index, i32* %index.addr, align 4
+  %0 = load i32* %index.addr, align 4
+  %cmp = icmp slt i32 %0, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+; CHECK: if.then
+if.then:                                          ; preds = %entry
+  %1 = load i32* %index.addr, align 4
+  %p1 = getelementptr inbounds %struct.node* %node.017, i32 0, i32 6
+  ; CHECK: store i32
+  store i32 %1, i32* %p1, align 4
+  br label %if.end
+  
+; CHECK: if.else
+if.else:                                          ; preds = %entry
+  %2 = load i32* %index.addr, align 4
+  %add = add nsw i32 %2, 1
+  %p3 = getelementptr inbounds %struct.node* %node.017, i32 0, i32 6
+  ; CHECK: store i32
+  store i32 %add, i32* %p3, align 4
+  call i32 @foo(i32 5)          ;barrier
+  br label %if.end
+
+; CHECK: if.end
+if.end:                                           ; preds = %if.else, %if.then
+; CHECK-NOT: store
+  ret void
+}

test/Transforms/InstMerge/st_sink_no_barrier_call.ll

+; Test to make sure that stores in a diamond get merged with a non barrier function call after the store instruction
+; Stores sunks into the footer.
+; RUN: opt -basicaa -memdep -mldst-motion -S < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+%struct.node = type { i32, %struct.node*, %struct.node*, %struct.node*, i32, i32, i32, i32 }
+
+declare i32 @foo(i32 %x) #0
+
+; Function Attrs: nounwind uwtable
+define void @sink_store(%struct.node* nocapture %r, i32 %index) {
+entry:
+  %node.0.in16 = getelementptr inbounds %struct.node* %r, i64 0, i32 2
+  %node.017 = load %struct.node** %node.0.in16, align 8
+  %index.addr = alloca i32, align 4
+  store i32 %index, i32* %index.addr, align 4
+  %0 = load i32* %index.addr, align 4
+  %cmp = icmp slt i32 %0, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+; CHECK: if.then
+if.then:                                          ; preds = %entry
+  %1 = load i32* %index.addr, align 4
+  %p1 = getelementptr inbounds %struct.node* %node.017, i32 0, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %1, i32* %p1, align 4
+  br label %if.end
+  
+; CHECK: if.else
+if.else:                                          ; preds = %entry
+  %2 = load i32* %index.addr, align 4
+  %add = add nsw i32 %2, 1
+  %p3 = getelementptr inbounds %struct.node* %node.017, i32 0, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %add, i32* %p3, align 4
+  call i32 @foo(i32 5)          ;not a barrier
+  br label %if.end
+
+; CHECK: if.end
+if.end:                                           ; preds = %if.else, %if.then
+; CHECK: store
+  ret void
+}
+
+attributes #0 = { readnone } 

test/Transforms/InstMerge/st_sink_no_barrier_load.ll

+; Test to make sure that stores in a diamond get merged with a non barrier load after the store instruction
+; Stores sunks into the footer.
+; RUN: opt -basicaa -memdep -mldst-motion -S < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+%struct.node = type { i32, %struct.node*, %struct.node*, %struct.node*, i32, i32, i32, i32 }
+
+; Function Attrs: nounwind uwtable
+define void @sink_store(%struct.node* nocapture %r, i32 %index) {
+entry:
+  %node.0.in16 = getelementptr inbounds %struct.node* %r, i64 0, i32 2
+  %node.017 = load %struct.node** %node.0.in16, align 8
+  %index.addr = alloca i32, align 4
+  store i32 %index, i32* %index.addr, align 4
+  %0 = load i32* %index.addr, align 4
+  %cmp = icmp slt i32 %0, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+; CHECK: if.then
+if.then:                                          ; preds = %entry
+  %1 = load i32* %index.addr, align 4
+  %p1 = getelementptr inbounds %struct.node* %node.017, i32 0, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %1, i32* %p1, align 4
+  %p2 = getelementptr inbounds %struct.node* %node.017, i32 5, i32 6
+  ; CHECK: load i32*
+  %not_barrier = load i32 * %p2, align 4
+  br label %if.end
+
+; CHECK: if.else
+if.else:                                          ; preds = %entry
+  %2 = load i32* %index.addr, align 4
+  %add = add nsw i32 %2, 1
+  %p3 = getelementptr inbounds %struct.node* %node.017, i32 0, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %add, i32* %p3, align 4
+  br label %if.end
+
+; CHECK: if.end
+if.end:                                           ; preds = %if.else, %if.then
+; CHECK: store
+  ret void
+}

test/Transforms/InstMerge/st_sink_no_barrier_store.ll

+; Test to make sure that stores in a diamond get merged with a non barrier store after the store instruction to be sunk
+; Stores sunks into the footer.
+; RUN: opt -basicaa -memdep -mldst-motion -S < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+%struct.node = type { i32, %struct.node*, %struct.node*, %struct.node*, i32, i32, i32, i32 }
+
+; Function Attrs: nounwind uwtable
+define void @sink_store(%struct.node* nocapture %r, i32 %index) {
+entry:
+  %node.0.in16 = getelementptr inbounds %struct.node* %r, i64 0, i32 2
+  %node.017 = load %struct.node** %node.0.in16, align 8
+  %index.addr = alloca i32, align 4
+  store i32 %index, i32* %index.addr, align 4
+  %0 = load i32* %index.addr, align 4
+  %cmp = icmp slt i32 %0, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+; CHECK: if.then
+if.then:                                          ; preds = %entry
+  %1 = load i32* %index.addr, align 4
+  %p1 = getelementptr inbounds %struct.node* %node.017, i32 0, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %1, i32* %p1, align 4
+  br label %if.end
+
+; CHECK: if.else
+if.else:                                          ; preds = %entry
+  %2 = load i32* %index.addr, align 4
+  %add = add nsw i32 %2, 1
+  %p2 = getelementptr inbounds %struct.node* %node.017, i32 0, i32 6
+  store i32 %add, i32* %p2, align 4
+  %p3 = getelementptr inbounds %struct.node* %node.017, i32 5, i32 6
+  ; CHECK: store i32
+  store i32 %add, i32* %p3, align 4          ; This is not a barrier
+  br label %if.end
+
+; CHECK: if.end
+if.end:                                           ; preds = %if.else, %if.then
+; CHECK: store
+  ret void
+}

test/Transforms/InstMerge/st_sink_two_stores.ll

+; Test to make sure that stores in a diamond get merged
+; Stores sunks into the footer.
+; RUN: opt -basicaa -memdep -mldst-motion -S < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+%struct.node = type { i32, %struct.node*, %struct.node*, %struct.node*, i32, i32, i32, i32 }
+
+; Function Attrs: nounwind uwtable
+define void @sink_store(%struct.node* nocapture %r, i32 %index) {
+entry:
+  %node.0.in16 = getelementptr inbounds %struct.node* %r, i64 0, i32 2
+  %node.017 = load %struct.node** %node.0.in16, align 8
+  %index.addr = alloca i32, align 4
+  store i32 %index, i32* %index.addr, align 4
+  %0 = load i32* %index.addr, align 4
+  %cmp = icmp slt i32 %0, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+; CHECK: if.then
+if.then:                                          ; preds = %entry
+  %1 = load i32* %index.addr, align 4
+  %p1 = getelementptr inbounds %struct.node* %node.017, i32 0, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %1, i32* %p1, align 4
+  %p2 = getelementptr inbounds %struct.node* %node.017, i32 4, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %1, i32* %p2, align 4
+  br label %if.end
+
+; CHECK: if.else
+if.else:                                          ; preds = %entry
+  %2 = load i32* %index.addr, align 4
+  %add = add nsw i32 %2, 1
+  %p3 = getelementptr inbounds %struct.node* %node.017, i32 0, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %add, i32* %p3, align 4
+  %p4 = getelementptr inbounds %struct.node* %node.017, i32 4, i32 6
+  ; CHECK-NOT: store i32
+  store i32 %2, i32* %p4, align 4  
+  br label %if.end
+
+; CHECK: if.end
+if.end:                                           ; preds = %if.else, %if.then
+; CHECK: store
+; CHECK: store
+  ret void
+}

test/Transforms/InstMerge/st_sink_with_barrier.ll

+; Test to make sure that load from the same address as a store and appears after the store prevents the store from being sunk
+; RUN: opt -basicaa -memdep -mldst-motion -S < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+%struct.node = type { i32, %struct.node*, %struct.node*, %struct.node*, i32, i32, i32, i32 }
+
+; Function Attrs: nounwind uwtable
+define void @sink_store(%struct.node* nocapture %r, i32 %index) {
+entry:
+  %node.0.in16 = getelementptr inbounds %struct.node* %r, i64 0, i32 2
+  %node.017 = load %struct.node** %node.0.in16, align 8
+  %index.addr = alloca i32, align 4
+  store i32 %index, i32* %index.addr, align 4
+  %0 = load i32* %index.addr, align 4
+  %cmp = icmp slt i32 %0, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+; CHECK: if.then
+if.then:                                          ; preds = %entry
+  %1 = load i32* %index.addr, align 4
+  %p1 = getelementptr inbounds %struct.node* %node.017, i32 0, i32 6
+  ; CHECK: store i32
+  store i32 %1, i32* %p1, align 4
+  %p2 = getelementptr inbounds %struct.node* %node.017, i32 0, i32 6
+  ; CHECK: load i32*
+  %barrier = load i32 * %p2, align 4
+  br label %if.end
+
+; CHECK: if.else
+if.else:                                          ; preds = %entry
+  %2 = load i32* %index.addr, align 4
+  %add = add nsw i32 %2, 1
+  %p3 = getelementptr inbounds %struct.node* %node.017, i32 0, i32 6
+  ; CHECK: store i32
+  store i32 %add, i32* %p3, align 4
+  br label %if.end
+
+; CHECK: if.end
+if.end:                                           ; preds = %if.else, %if.then
+; CHECK-NOT: store
+  ret void
+}