[MergedLoadStoreMotion] Conditional store elimination

[chill]

Summary

This patch implements replacement of certain conditional stores with
unconditional ones (subject to constraints).

A triangle shaped part of the CFG like:

header:
  ...
  br %cond, label %if.then, label %if.end
    
if.then:
  store %s.new, %addr
  br label %if.end
    
if.end:
   ...

would become

 header:
   ...
   br %cond, label %if.then, label %if.else
    
if.then:
   br %if.end
    
if.else:
  %s.old = load %addr
  br label %if.end
    
if.end:
  %s = phi [%s.new, if.then], [%s.old, if.else]
  store %s, %addr

This transformation is correct as long as the store:
a) is not volatile
b) does not introduce an invalid memory access in the new location
c) does not introduce a data race in the new location

For a) volatile stores are simply disqualified from the transformation.

To satisfy b) we can check that on all paths leading up to the end of the
header block

• the program already contains a write (or, for local objects only, a read) to precisely the same memory location, and
• for non-local objects only, following that write, there is no instruction that could possibly make subsequent writes invalid (local objects are considered always writable).

To satisfy c), for local objects only, we can check that the address of the
object does not escape the function.

For non-local objects or for escaping local objects we can check that on all
paths leading up to the end of the header block

• the program already contains a write to precisely the same memory location, and
• following that write, there is no instruction that could possibly be the tail edge of a "synchronizes-with" relation

If the candidate store is to a local variable, we first traverse the users of
the alloca instruction, noting whether the address escapes and whether a load
or a store to the same address dominates the candidate store (domination is a
stronger constraint than the above "on all paths" one).

Failing that, or for stores to non-local objects, we then traverse the MemorySSA
graph, starting from the MemoryDef that corresponds to the candidate
store. During that travesal:

• if we reach the initial liveOnEntry, nothing is guaranteed and we fail
• if we reach a call to an unknown function, a volatile memory access, or an atomic memory access we bail
• if we reach a simple store to the same memory location, we stop traversing upwards from this MemoryDef only
• otherwise we contionue the traverse to the incoming MemoryDef

If we didn't bail anywhere in the above traversal, the transformation is
considered correct.

[chill]

Oh, and I'm going to work on adding tests.

[lebedev.ri]

Warning: this pass clearly modifies CFG, and clearly does not update dominator tree,
which means you can not use dominator tree in this pass,
at least not until fixing the pass to preserve it when modifying CFG.

[chill]

llvm/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

491

Note to self: should be V == cast<StoreInst>(I)->getValueOperand())

[chill]

Updated with a very different implementation. Now handles non-local stores as well.
Updated the description with a justification why I think this transformation is correct.

[chill]

In D105545#2861643, @lebedev.ri wrote:

Warning: this pass clearly modifies CFG, and clearly does not update dominator tree,
which means you can not use dominator tree in this pass,
at least not until fixing the pass to preserve it when modifying CFG.

Thanks. I think all accesses to the dominator tree (and on the next variants to the MemorySSA graph) occur
before any changes to the CFG.

[chill]

In this updates:

• added tests
• update the Dom tree, preserve DomTreeAnalysis
• small fixes here and there

[jaykang10]

It looks like the patch does Partial Redundancy Elimination for store with triangle CFG... As far as I know, LLVM has passes to support the PRE.
If you have already checked the llvm passes, can you let me know why the passes do not handle the triangle CFG with store instruction please?

[chill]

In D105545#2879424, @jaykang10 wrote:

It looks like the patch does Partial Redundancy Elimination for store with triangle CFG... As far as I know, LLVM has passes to support the PRE.
If you have already checked the llvm passes, can you let me know why the passes do not handle the triangle CFG with store instruction please?

I'm not aware of a pass that does PRE on stores. GVN does a limited form of PRE
on diamonds, but it does not deal with void instructions (such is stores).
DSE only handles fully redundant stores, as far as I can tell.

Even if we have PRE on stores, we still need this pass (or a variant thereof) to
create the (partial) redundancy, to feed to or as a step of a (hypothetical?)
Partial-DSE pass, since we don't have actually a case for a PRE - no two stores,
one to be considered (partially) redundant.

In any case, I'm open to suggestions about better places for this
transformation.

[jaykang10]

@mkazantsev I can see you have worked with PRE recently. If possible, can you recommend the point where this transformation is useful please?

[chill]

Ping.

[SjoerdMeijer]

Adding @efriedma to see if this is the right place for this.

Assuming it is, for now, I plan to look at this soon.

[SjoerdMeijer]

High-level question(s) first before I dive more into the details: I was wondering if the main benefit of this is simplification of control flow? Which then probably relies on the store that is being sunk the only instruction in the block? In other words, I was wondering if this is always a good thing to do. Or can we can regress things if it's not the only instruction, or it the other path (the one that does not have the store) now has to deal with the condition?

llvm/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

99

It's probably good to add some of the justification and legality considerations here, i.e. the things you added to the description of this ticket.

[efriedma]

At a high level, I think this needs some heuristic to drive it. I can see this being profitable under two circumstances, broadly speaking:

1. Sinking the store enables DSE to eliminate an earlier store.
2. Sinking the store enables vectorization.

Otherwise, you're just performing extra memory operations, which doesn't seem like an improvement.

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

144

We don't want an additional MemorySSA run, if we can avoid it.

If we're going to do this, maybe stick the code into Dead Store Elimination?

[chill]

Hello,

Thanks for the comments and the suggestions.
The main objective of this patch is to simplify the CFG, but, indeed, the patch itself does not
make the CFG simpler.
As it turns out, there's already a very similar transformation done in SimplifyCFG, so I have opted
to adding extra correctness checks (respectively, trigger in more cases) *there*.

I'm abandoning this patch in favour of https://reviews.llvm.org/D107281

llvm/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

 //===- MergedLoadStoreMotion.cpp - merge and sink stores ------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 //! \file
 //! This pass performs merges of stores on both sides of a
 //  diamond (hammock).
 //
 // The algorithm iteratively sinks two stores to the same address out of a
 // diamond (hammock) and merges them into a single store to the tail block
 // (footer). The algorithm iterates over the instructions of one side of the
 // diamond and attempts to find a matching store on the other side. New
-// tail/footer block may be insterted if the tail/footer block has more
+// tail/footer block may be inserted if the tail/footer block has more
 // predecessors (not only the two predecessors that are forming the diamond). It
 // sinks when it thinks it safe to do so.  This optimization helps with eg.
 // hiding load latencies, triggering if-conversion, and reducing static code
 // size.
 //
 //===----------------------------------------------------------------------===//
 //
 //

 //                        +                    +
 //            if.end ("footer"):
 //                     %s.sink = phi [%st, if.then], [%se, if.else]
 //                     <...>
 //                     store %s.sink, %addr_s
 //                     <...>
 //
 //
+// This pass also replaces conditional stores with unconditional ones (subject to
+// constraints).
+// Given a triangle shape before the transformation:
+//
+//            header:
+//                     br %cond, label %if.then, label %if.end
+//                        +                        +
+//                       +                         +
+//                      +                          +
+//            if.then:                             +
+//               store %s, %addr                   +
+//               br label %if.end                  +
+//                      +                          +
+//                       +                         +
+//                        +                        +
+//            if.end ("footer"):
+//                     <...>
+//
+// After the conditional store replacement, this becomes:
+//            header:
+//                     br %cond, label %if.then, label %if.else
+//                        +                    +
+//                       +                      +
+//                      +                        +
+//            if.then:                         if.else:
+//                br label %if.end                load  %s.old, %addr
+//                                                br label %if.end
+//                      +                        +
+//                       +                      +
+//                        +                    +
+//            if.end ("footer"):
+//                     %s.new = phi [%s, if.then], [%s.old, if.else]
+//                     <...>
+//                     store %s.new, %addr_s
+//                     <...>
+//
 //===----------------------- TODO -----------------------------------------===//
 //
 // 1) Generalize to regions other than diamonds
 // 2) Be more aggressive merging memory operations
+// 3) Add conditional store replacement for stores to non-local addresses
 // Note that both changes require register pressure control
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/MergedLoadStoreMotion.h"
+#include "llvm/ADT/ScopedHashTable.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "mldst-motion"
 
 namespace {
 //===----------------------------------------------------------------------===//
 //                         MergedLoadStoreMotion Pass
 //===----------------------------------------------------------------------===//
 class MergedLoadStoreMotion {
   AliasAnalysis *AA = nullptr;
 
+  // The set of stores considered safe to turn from conditional to
+  // unconditional.
+  DenseSet<Instruction *> SafeStores;
+
   // The mergeStores algorithms could have Size0 * Size1 complexity,
   // where Size0 and Size1 are the number 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 = 250;
 
   const bool SplitFooterBB;
 public:
   MergedLoadStoreMotion(bool SplitFooterBB) : SplitFooterBB(SplitFooterBB) {}
-  std::pair<bool, bool> run(Function &F, AliasAnalysis &AA);
+  std::pair<bool, bool> run(Function &F, AliasAnalysis &AA, DominatorTree &DT);
 
 private:
   bool isDiamondHead(BasicBlock *BB, BasicBlock *&Left, BasicBlock *&Right,
                      BasicBlock *&Tail);
+  bool isTriangleHead(BasicBlock *BB, BasicBlock *&Side, BasicBlock *&Tail);
   // Routines for sinking stores
   StoreInst *canSinkFromBlock(BasicBlock *BB, StoreInst *SI);
   PHINode *getPHIOperand(BasicBlock *BB, StoreInst *S0, StoreInst *S1);
   bool isStoreSinkBarrierInRange(const Instruction &Start,
                                  const Instruction &End, MemoryLocation Loc);
   bool canSinkStoresAndGEPs(StoreInst *S0, StoreInst *S1) const;
   void sinkStoresAndGEPs(BasicBlock *BB, StoreInst *SinkCand,
                          StoreInst *ElseInst);
   std::pair<bool, bool> mergeStores(BasicBlock *Head, BasicBlock *Left,
                                     BasicBlock *Right, BasicBlock *Tail);
+  bool isEscaping(const AllocaInst *AI);
+  bool sinkStores(BasicBlock *Head, BasicBlock *Side, BasicBlock *Tail);
+  void getSafeStores(DominatorTree &DT);
 };
 } // end anonymous namespace
 
 ///
 /// True when BB is the head of a diamond (hammock)
 ///
 bool MergedLoadStoreMotion::isDiamondHead(BasicBlock *BB, BasicBlock *&Left,
                                           BasicBlock *&Right,
bool MergedLoadStoreMotion::isDiamondHead(BasicBlock *BB, BasicBlock *&Left,
   if (!Right->getSinglePredecessor())
     return false;
 
   Tail = Left->getSingleSuccessor();
   return Tail && Tail == Right->getSingleSuccessor();
 }
 
 ///
+/// True when BB is the head of a triangle
+///
+bool MergedLoadStoreMotion::isTriangleHead(BasicBlock *BB, BasicBlock *&Side,
+                                           BasicBlock *&Tail) {
+  if (!BB)
+    return false;
+  auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
+  if (!BI || !BI->isConditional())
+    return false;
+
+  BasicBlock *Succ0 = BI->getSuccessor(0);
+  BasicBlock *Succ1 = BI->getSuccessor(1);
+
+  if (Succ0->hasNPredecessors(1)) {
+    Side = Succ0;
+    Tail = Succ1;
+    return Side->getSingleSuccessor() == Tail;
+  }
+
+  if (Succ1->hasNPredecessors(1)) {
+    Side = Succ1;
+    Tail = Succ0;
+    return Side->getSingleSuccessor() == Tail;
+  }
+
+  return false;
+}
+
+///
 /// 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,
while (Instruction *I = P->getPrevNonDebugInstruction()) {
     }
 
     MergedStores = true;
     sinkStoresAndGEPs(SinkBB, S0, S1);
   }
   return {MergedStores, SplitFooter};
 }
 
-std::pair<bool, bool> MergedLoadStoreMotion::run(Function &F,
-                                                 AliasAnalysis &AA) {
+bool MergedLoadStoreMotion::sinkStores(BasicBlock *Head, BasicBlock *Side,
+                                       BasicBlock *Tail) {
+  // Bail out early if we can not merge into the footer BB.
+  if (!SplitFooterBB && Tail->hasNPredecessorsOrMore(3))
+    return false;
+
+  // Don't sink if there are more than two (terminator and store) instructions
+  // in the block.
+  // TODO: Should we try to hoist at least the pointer operand?
+  Instruction *I = Side->getTerminator()->getPrevNonDebugInstruction(true);
+  if (I == nullptr)
+    return false;
+  if (Instruction *P = I->getPrevNonDebugInstruction(true))
+    return false;
+
+  // Don't sink non-simple (atomic, volatile) stores.
+  if (!isa<StoreInst>(I))
+    return false;
+  auto *S = cast<StoreInst>(I);
+  if (!S->isSimple())
+    return false;
+
+  // Check it's legal to insert load along an alternative path and to move the
+  // store.
+  if (!SafeStores.contains(S))
+    return false;
+
+  BasicBlock *NewSide = nullptr;
+  BasicBlock *Sink = Tail;
+
+  // Create a load on the "other" side of the branch.
+  if (NewSide == nullptr)
+    NewSide = SplitBlockPredecessors(Tail, {Head}, ".alt");
+  Value *V = S->getValueOperand();
+  auto *L =
+      new LoadInst(V->getType(), S->getPointerOperand(), V->getName() + ".old",
+                   &*NewSide->getFirstInsertionPt());
+
+  // Sink the store to the tail block.
+  if (Sink != Tail && Tail->hasNPredecessorsOrMore(3))
+    Sink = SplitBlockPredecessors(Tail, {Head, Side}, ".sink");
+
+  LLVM_DEBUG(dbgs() << "Sink single store into";
+             Sink->printAsOperand(dbgs(), false); dbgs() << "Store: ";
+             S->dump(); dbgs() << "\n"; dbgs() << "Load:  "; L->dump();
+             dbgs() << "\n");
+  S->removeFromParent();
+  S->insertBefore(&*Sink->getFirstInsertionPt());
+
+  auto Phi =
+      PHINode::Create(V->getType(), 2, V->getName() + ".new", &Sink->front());
+  Phi->addIncoming(V, Side);
+  Phi->addIncoming(L, NewSide);
+  S->setOperand(0, Phi);
+
+  return true;
+}
+
+///
+/// Check whether the address of a local variable may escape from the function.
+///
+bool MergedLoadStoreMotion::isEscaping(const AllocaInst *AI) {
+  SmallPtrSet<const PHINode *, 4> Visited;
+  SmallVector<const Value *, 16> Worklist;
+
+  Worklist.push_back(AI);
+  while (!Worklist.empty()) {
+    const Value *V = Worklist.pop_back_val();
+    for (const User *U : V->users()) {
+      const Instruction *I = cast<Instruction>(U);
+      switch (I->getOpcode()) {
+      default:
+        // If not handled in one of the other cases, conservatively assume the
+        // value escapes.
+        return true;
+      case Instruction::Ret:
+      case Instruction::Load:
+      case Instruction::AtomicRMW:
+        // A pointer cannot escape via these instructions.
+        break;
+      case Instruction::Call: {
+        const auto *CI = cast<CallInst>(I);
+        if (CI->isDebugOrPseudoInst() || CI->isLifetimeStartOrEnd())
+          break;
+      }
+        LLVM_FALLTHROUGH;
+      case Instruction::Invoke:
+      case Instruction::CallBr:
+        if (any_of(cast<CallBase>(I)->data_ops(),
+                   [=](const Use &Arg) { return Arg.get() == V; }))
+          return true;
+        break;
+      case Instruction::Store:
+        if (AI == cast<StoreInst>(I)->getValueOperand())
+          return true;
+        break;
+      case Instruction::AtomicCmpXchg:
+        if (V == cast<AtomicCmpXchgInst>(I)->getNewValOperand())
+          return true;
+        break;
+      case Instruction::PHI:
+        if (!Visited.insert(cast<PHINode>(I)).second)
+          break;
+        LLVM_FALLTHROUGH;
+      case Instruction::GetElementPtr:
+      case Instruction::BitCast:
+      case Instruction::AddrSpaceCast:
+      case Instruction::Select:
+        Worklist.push_back(I);
+        break;
+      }
+    }
+  }
+
+  return false;
+}
+
+///
+///  Determine the set of "non-trapping" store instructions.
+///
+///  The criteria for "non-trapping" are:
+///   a) The store must be dominated by a store to or, additionally, for local
+///      objects only, by a load from the same memory location. The
+///      stack is considered always writable, therefore we allow a load to
+///      determine the access to the memory location cannot trap.
+///   b) For local objects, the address of the object may not escape from the
+///      function along any path in the CFG leading from the `alloca`
+///      instruction to the candidate store. For such objects, the conditional
+///      store replacement that we do will not create a data race.
+///   c) For non-local objects, there may not be function calls (except to
+///      `readnone`/`readonly`/`nofree` functions or certain library functions
+///      with known semantics) along any path in the CFG leading from the
+///      dominating store to the candidate store.
+///
+///   The function checks only for access to local objects (for the time being
+///   we don't do conditional replacement on stores to non-locals) and the
+///   escape check is conservatively global to the function.
+///   The function performs a depth-first traversal of the domination tree,
+///   maintaining in a stack-like fashion the set of all interesting potentially
+///   trapping memory accesses on the path in the DOM tree from the function
+///   entry to the current basic block. The stores in the current block are
+///   checked for a dominating access to the same memory location and then are
+///   added to the set.
+///
+void MergedLoadStoreMotion::getSafeStores(DominatorTree &DT) {
+  // Type used for maintaining conceptually a stack of hash tables.
+  using UnsafeLocationsTy = ScopedHashTable<MemoryLocation, bool>;
+
+  // Entry of the current path in the DOM tree.
+  struct PathEntry {
+    PathEntry(DomTreeNode *N, UnsafeLocationsTy &HT) : Node(N) {
+      Scope.reset(new UnsafeLocationsTy::ScopeTy(HT));
+    }
+    DomTreeNode *Node;
+    std::unique_ptr<UnsafeLocationsTy::ScopeTy> Scope;
+  };
+
+  UnsafeLocationsTy Unsafe;        // Set of potentially trapping locations.
+  SmallVector<PathEntry, 32> Path; // DOM tree path
+
+  LLVM_DEBUG(dbgs() << "Safe/unsafe access DOM traversal\n";);
+
+  SmallVector<DomTreeNode *, 32> Worklist;
+  Worklist.push_back(DT.getRootNode());
+  while (!Worklist.empty()) {
+    DomTreeNode *Curr = Worklist.back();
+
+    if (Path.size() && Curr == Path.back().Node) {
+      // If the next node in the workist is the same as the last node on the
+      // path it means we have finished traversing the node and all its
+      // children.
+      LLVM_DEBUG(auto *B = Curr->getBlock(); dbgs() << "finish ";
+                 B->printAsOperand(dbgs(), false); dbgs() << '\n';);
+      Worklist.pop_back();
+      Path.pop_back();
+      continue;
+    }
+
+    // Enter a new basic block and start a new scope in the hash table.
+    Path.emplace_back(Curr, Unsafe);
+    LLVM_DEBUG(auto *B = Curr->getBlock(); dbgs() << "enter ";
+               B->printAsOperand(dbgs(), false); dbgs() << '\n';);
+
+    // Scan the instructions in the block and examine the loads and the stores.
+    for (Instruction &I : *Curr->getBlock()) {
+      if (auto *S = dyn_cast<StoreInst>(&I)) {
+        const auto *AI =
+            dyn_cast<AllocaInst>(getUnderlyingObject(S->getPointerOperand()));
+        if (AI == nullptr || isEscaping(AI))
+          continue;
+        if (Unsafe.count(MemoryLocation::get(S))) {
+          LLVM_DEBUG(dbgs() << "Found safe store: "; I.dump(););
+          SafeStores.insert(&I);
+        } else {
+          LLVM_DEBUG(dbgs() << "Found unsafe store: "; I.dump(););
+          Unsafe.insert(MemoryLocation::get(S), true);
+        }
+      } else if (auto *L = dyn_cast<LoadInst>(&I)) {
+        const auto *AI =
+            dyn_cast<AllocaInst>(getUnderlyingObject(L->getPointerOperand()));
+        if (AI == nullptr || isEscaping(AI))
+          continue;
+        if (!Unsafe.count(MemoryLocation::get(L))) {
+          LLVM_DEBUG(dbgs() << "Found unsafe load: "; I.dump(););
+          Unsafe.insert(MemoryLocation::get(L), true);
+        }
+      }
+    }
+
+    // Traverse the children.
+    for (auto *C : Curr->children())
+      Worklist.push_back(C);
+  }
+}
+
+std::pair<bool, bool> MergedLoadStoreMotion::run(Function &F, AliasAnalysis &AA,
+                                                 DominatorTree &DT) {
   this->AA = &AA;
 
   bool Changed = false;
   bool CFGChanged = false;
 
   LLVM_DEBUG(dbgs() << "Instruction Merger\n");
+  getSafeStores(DT);
 
   // Merge unconditional branches, allowing PRE to catch more
   // optimization opportunities.
-  // This loop doesn't care about newly inserted/split blocks 
-  // since they never will be diamond heads.
+  // This loop doesn't care about newly inserted/split blocks
+  // since they will never be diamond or triangle heads.
   for (BasicBlock &BB : make_early_inc_range(F)) {
     BasicBlock *Left, *Right, *Tail;
     if (isDiamondHead(&BB, Left, Right, Tail)) {
       // Merge and sink store pairs outside diamonds when possible.
       bool Change, ChangeCFG;
       std::tie(Change, ChangeCFG) = mergeStores(&BB, Left, Right, Tail);
       Changed |= Change;
       CFGChanged |= ChangeCFG;
+    } else if (isTriangleHead(&BB, Left, Tail)) {
+      // Replace a conditional store.
+      if (sinkStores(&BB, Left, Tail))
+        Changed = CFGChanged = true;
     }
   }
+
+  SafeStores.clear();
   return {Changed, CFGChanged};
 }
 
 namespace {
 class MergedLoadStoreMotionLegacyPass : public FunctionPass {
   const bool SplitFooterBB;
 public:
   static char ID; // Pass identification, replacement for typeid
   MergedLoadStoreMotionLegacyPass(bool SplitFooterBB = false)
       : FunctionPass(ID), SplitFooterBB(SplitFooterBB) {
     initializeMergedLoadStoreMotionLegacyPassPass(
         *PassRegistry::getPassRegistry());
   }
 
   ///
   /// Run the transformation for each function
   ///
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
+
     MergedLoadStoreMotion Impl(SplitFooterBB);
     bool Change, _;
     std::tie(Change, _) =
-        Impl.run(F, getAnalysis<AAResultsWrapperPass>().getAAResults());
+        Impl.run(F, getAnalysis<AAResultsWrapperPass>().getAAResults(),
+                 getAnalysis<DominatorTreeWrapperPass>().getDomTree());
     return Change;
   }
 
 private:
   void getAnalysisUsage(AnalysisUsage &AU) const override {
-    if (!SplitFooterBB)
-      AU.setPreservesCFG();
+    AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 };
 
 char MergedLoadStoreMotionLegacyPass::ID = 0;
 } // anonymous namespace
 
 ///
 /// createMergedLoadStoreMotionPass - The public interface to this file.
 ///
 FunctionPass *llvm::createMergedLoadStoreMotionPass(bool SplitFooterBB) {
   return new MergedLoadStoreMotionLegacyPass(SplitFooterBB);
 }
 
 INITIALIZE_PASS_BEGIN(MergedLoadStoreMotionLegacyPass, "mldst-motion",
                       "MergedLoadStoreMotion", false, false)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_END(MergedLoadStoreMotionLegacyPass, "mldst-motion",
                     "MergedLoadStoreMotion", false, false)
 
 PreservedAnalyses
 MergedLoadStoreMotionPass::run(Function &F, FunctionAnalysisManager &AM) {
   MergedLoadStoreMotion Impl(Options.SplitFooterBB);
   auto &AA = AM.getResult<AAManager>(F);
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+
   bool Change, CFGChange;
-  std::tie(Change, CFGChange) = Impl.run(F, AA);
+  std::tie(Change, CFGChange) = Impl.run(F, AA, DT);
   if (!Change && !CFGChange)
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   if (!CFGChange)
     PA.preserveSet<CFGAnalyses>();
   return PA;
 }

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

 ; GCN-O2-NEXT:       Loop Pass Manager
 ; GCN-O2-NEXT:         Recognize loop idioms
 ; GCN-O2-NEXT:         Induction Variable Simplification
 ; GCN-O2-NEXT:         Delete dead loops
 ; GCN-O2-NEXT:         Unroll loops
 ; GCN-O2-NEXT:       SROA
 ; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       MergedLoadStoreMotion
+; GCN-O2-NEXT:       Dominator Tree Construction
+; GCN-O2-NEXT:       Natural Loop Information
 ; GCN-O2-NEXT:       Phi Values Analysis
+; GCN-O2-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       Memory Dependence Analysis
 ; GCN-O2-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O2-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O2-NEXT:       Optimization Remark Emitter
 ; GCN-O2-NEXT:       Global Value Numbering
 ; GCN-O2-NEXT:       Sparse Conditional Constant Propagation
 ; GCN-O2-NEXT:       Demanded bits analysis

 ; GCN-O3-NEXT:       Loop Pass Manager
 ; GCN-O3-NEXT:         Recognize loop idioms
 ; GCN-O3-NEXT:         Induction Variable Simplification
 ; GCN-O3-NEXT:         Delete dead loops
 ; GCN-O3-NEXT:         Unroll loops
 ; GCN-O3-NEXT:       SROA
 ; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       MergedLoadStoreMotion
+; GCN-O3-NEXT:       Dominator Tree Construction
+; GCN-O3-NEXT:       Natural Loop Information
 ; GCN-O3-NEXT:       Phi Values Analysis
+; GCN-O3-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       Memory Dependence Analysis
 ; GCN-O3-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O3-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O3-NEXT:       Optimization Remark Emitter
 ; GCN-O3-NEXT:       Global Value Numbering
 ; GCN-O3-NEXT:       Sparse Conditional Constant Propagation
 ; GCN-O3-NEXT:       Demanded bits analysis

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

 ; CHECK-NEXT:       Global Value Numbering
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       MemCpy Optimization
 ; CHECK-NEXT:       Post-Dominator Tree Construction
 ; CHECK-NEXT:       Dead Store Elimination
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       MergedLoadStoreMotion
+; CHECK-NEXT:       Dominator Tree Construction
+; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       LCSSA Verifier
 ; CHECK-NEXT:       Loop-Closed SSA Form Pass
+; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Loop Pass Manager
 ; CHECK-NEXT:         Induction Variable Simplification
 ; CHECK-NEXT:         Delete dead loops
 ; CHECK-NEXT:         Unroll loops
 ; CHECK-NEXT:       Loop Access Analysis
 ; CHECK-NEXT:       Lazy Branch Probability Analysis

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

 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Recognize loop idioms
 ; CHECK-NEXT:           Induction Variable Simplification
 ; CHECK-NEXT:           Delete dead loops
 ; CHECK-NEXT:           Unroll loops
 ; CHECK-NEXT:         SROA
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         MergedLoadStoreMotion
+; CHECK-NEXT:         Dominator Tree Construction
+; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Phi Values Analysis
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Global Value Numbering
 ; CHECK-NEXT:         Sparse Conditional Constant Propagation
 ; CHECK-NEXT:         Demanded bits analysis

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

 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Recognize loop idioms
 ; CHECK-NEXT:           Induction Variable Simplification
 ; CHECK-NEXT:           Delete dead loops
 ; CHECK-NEXT:           Unroll loops
 ; CHECK-NEXT:         SROA
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         MergedLoadStoreMotion
+; CHECK-NEXT:         Dominator Tree Construction
+; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Phi Values Analysis
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Global Value Numbering
 ; CHECK-NEXT:         Sparse Conditional Constant Propagation
 ; CHECK-NEXT:         Demanded bits analysis

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

 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Recognize loop idioms
 ; CHECK-NEXT:           Induction Variable Simplification
 ; CHECK-NEXT:           Delete dead loops
 ; CHECK-NEXT:           Unroll loops
 ; CHECK-NEXT:         SROA
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         MergedLoadStoreMotion
+; CHECK-NEXT:         Dominator Tree Construction
+; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Phi Values Analysis
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Global Value Numbering
 ; CHECK-NEXT:         Sparse Conditional Constant Propagation
 ; CHECK-NEXT:         Demanded bits analysis

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

 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Recognize loop idioms
 ; CHECK-NEXT:           Induction Variable Simplification
 ; CHECK-NEXT:           Delete dead loops
 ; CHECK-NEXT:           Unroll loops
 ; CHECK-NEXT:         SROA
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         MergedLoadStoreMotion
+; CHECK-NEXT:         Dominator Tree Construction
+; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Phi Values Analysis
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Global Value Numbering
 ; CHECK-NEXT:         Sparse Conditional Constant Propagation
 ; CHECK-NEXT:         Demanded bits analysis