[GVN] Simple GVN hoist - loads and stores

[chill]

Summary

This is the second part of the Simple GVNHoist, which deals with load and store
instructions (first part is https://reviews.llvm.org/D110817).

This part makes use of MemorySSA to incorporate the incoming memory state into
the value numbers for the load and store instructions as well as to determine
memory dependencies.

If MemorySSA is not available, the value numbers for loads and stores are
unique, as before.

If MemorySSA is available, additional numbers are added to varargs of the
GVN::Expression.

If the incoming memory state is:

• LiveOnEntry, do nothing.

• a MemoryPhi, add <0, ID> where ID is the unique identifier of the MemoryPhi.

• a MemoryDef, add VN, where VN is the value number of the memory setting instruction.

Then the algorithm is essentially the same as for the scalars with a couple of
extra tweaks:

• when we pair instructions, we don't pair (therefore won't hoist/merge) volatile with non-volatile instructions or instructions with different atomic ordering.

• when hoisting, in addition of operands, for loads and store we try to hoist the memory dependencies too. Same principles as for operands apply - we only ever hoist pairs of instructions, starting from the memory dependencies of the then-instruction and just checking the memory dependencies of the else-instruction.

With both patches applied, the preliminary SPEC results look fairly decent (positive/higher is better, Neoverse N1, -O3 -flto):

500.perlbench_r	0.74%
502.gcc_r	0.26%
505.mcf_r	0.82%
520.omnetpp_r	-0.29%
523.xalancbmk_r	0.86%
525.x264_r	8.33%
531.deepsjeng_r	0.00%
541.leela_r	-0.71%
548.exchange2_r	0.00%
557.xz_r	0.75%

[mkazantsev]

I'll mark it "request changes" until the underlyingpatch has merged just to reduce my review list. Feel free to request review again when it lands.

[lebedev.ri]

Passing-by +1 to this approach.
I would like to remove load/store special-handling from simplifycfg's,
because that would allow to implement a more powerful phi-to-select bb merging fold.

[mkazantsev]

(Please don't mind -1 for me as it was just for sorting out review list purposes)

The general question I have - we are planning to transit from GVN to NewGVN, or at least so I heard. Is NewGVN already able to handle that? Is there a further plan to port these changes there?

[aeubanks]

In D110822#3099586, @mkazantsev wrote:

(Please don't mind -1 for me as it was just for sorting out review list purposes)

The general question I have - we are planning to transit from GVN to NewGVN, or at least so I heard. Is NewGVN already able to handle that? Is there a further plan to port these changes there?

I believe transitioning to NewGVN is still not definitive, there are a lot of things it doesn't support yet and it has bugs.

[asbirlea]

The request changes is for the use of getID() in MemorySSA(). Other optimizations should never rely on the value of the IDs assigned by MemorySSA.

I think the idea of implementing GVN Hoist is good, but there are other broader issues that concern me.
So, stepping back, I'd like to raise the question of how this change is going to be used if implemented. In the current default pipeline MemorySSA is not available where GVN is added. This is forcing the computation of MemorySSA before GVN.

Having MemorySSA computed before GVN may be good in the LTO pipeline (GVN already preserves the analysis), as the following passes require it (MemCpyOpt and DSE), but in the function simplification pipeline we'd end up with GVN computing, using and preserving two analysis (MemorySSA and MemDepAnalysis) with overlapping goals.

The status for switching to NewGVN is uncertain at this point, but porting GVN to switch over from MemDepAnalysis to MemorySSA may be an option, at least in the interim. This will lift the issue of having two analysis and also provide the availability of MemorySSA here. Is this something you'd be interested in exploring?

[chill]

In D110822#3116785, @asbirlea wrote:

The request changes is for the use of getID() in MemorySSA(). Other optimizations should never rely on the value of the IDs assigned by MemorySSA.

The getID() was already a public method in derived classes and the ID is used according to its description "Guaranteed unique among MemoryAccesses".

How about value numbering the BasicBlock that corresponds to a MemoryPhi ? It's a little bit of overhead and not strictly necessary if we have an ID readily available, but, fair enough, I don't mind doing it this way.

The status for switching to NewGVN is uncertain at this point, but porting GVN to switch over from MemDepAnalysis to MemorySSA may be an option, at least in the interim. This will lift the issue of having two analysis and also provide the availability of MemorySSA here. Is this something you'd be interested in exploring?

It's certainly something we need to discuss first.

[asbirlea]

In D110822#3116954, @chill wrote:

In D110822#3116785, @asbirlea wrote:

The request changes is for the use of getID() in MemorySSA(). Other optimizations should never rely on the value of the IDs assigned by MemorySSA.

The getID() was already a public method in derived classes and the ID is used according to its description "Guaranteed unique among MemoryAccesses".

How about value numbering the BasicBlock that corresponds to a MemoryPhi ? It's a little bit of overhead and not strictly necessary if we have an ID readily available, but, fair enough, I don't mind doing it this way.

The problem I have in mind is that the ID (and MemoryPhi ptr) may no longer exist during the transformation. The hoistPair is recursive, and it calls both the lookup (which adds the ID) and the moveToPlace in the MSSAUpdater; the moveToPlace can cleanup redundant MemoryPhis after a move and also add new phis; it's possible for a block to be revisited in GVN, and no longer have a MemoryPho; it's also possible it still has a MemoryPhi but with a different ID, if a move cleaned it up but then needed to readd it.
Relying on the BB ptr for example makes sense, that won't move from under your feet.

The status for switching to NewGVN is uncertain at this point, but porting GVN to switch over from MemDepAnalysis to MemorySSA may be an option, at least in the interim. This will lift the issue of having two analysis and also provide the availability of MemorySSA here. Is this something you'd be interested in exploring?

It's certainly something we need to discuss first.

Agreed, this is a big topic.

[chill]

In D110822#3117021, @asbirlea wrote:

Relying on the BB ptr for example makes sense, that won't move from under your feet.

All right, I used the basic block in the draft https://reviews.llvm.org/D115160 . In time, I'm going to rebase all these patches on top of the MemorySSA-for-GVN conversion.

llvm/include/llvm/Analysis/MemorySSA.h

public:
   }
   DefsOnlyType::reverse_self_iterator getReverseDefsIterator() {
     return this->DefsOnlyType::getReverseIterator();
   }
   DefsOnlyType::const_reverse_self_iterator getReverseDefsIterator() const {
     return this->DefsOnlyType::getReverseIterator();
   }
 
+  /// Used for debugging and tracking things about MemoryAccesses.
+  /// Guaranteed unique among MemoryAccesses, no guarantees otherwise.
+  inline unsigned getID() const;
+
 protected:
   friend class MemoryDef;
   friend class MemoryPhi;
   friend class MemorySSA;
   friend class MemoryUse;
   friend class MemoryUseOrDef;
 
   /// Used by MemorySSA to change the block of a MemoryAccess when it is
   /// moved.
   void setBlock(BasicBlock *BB) { Block = BB; }
 
-  /// Used for debugging and tracking things about MemoryAccesses.
-  /// Guaranteed unique among MemoryAccesses, no guarantees otherwise.
-  inline unsigned getID() const;
-
   MemoryAccess(LLVMContext &C, unsigned Vty, DeleteValueTy DeleteValue,
                BasicBlock *BB, unsigned NumOperands)
       : DerivedUser(Type::getVoidTy(C), Vty, nullptr, NumOperands, DeleteValue),
         Block(BB) {}
 
   // Use deleteValue() to delete a generic MemoryAccess.
   ~MemoryAccess() = default;
 

llvm/include/llvm/Transforms/Scalar/GVN.h

class ValueTable {
 
     // Cache for phi-translate in scalarpre.
     using PhiTranslateMap =
         DenseMap<std::pair<uint32_t, const BasicBlock *>, uint32_t>;
     PhiTranslateMap PhiTranslateTable;
 
     AAResults *AA = nullptr;
     MemoryDependenceResults *MD = nullptr;
+    MemorySSA *MSSA = nullptr;
     DominatorTree *DT = nullptr;
 
     uint32_t nextValueNumber = 1;
 
     Expression createExpr(Instruction *I);
     Expression createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
                              Value *LHS, Value *RHS);
     Expression createExtractvalueExpr(ExtractValueInst *EI);
     uint32_t lookupOrAddCall(CallInst *C);
+    uint32_t lookupOrAddLoadStore(Instruction *I);
     uint32_t phiTranslateImpl(const BasicBlock *BB, const BasicBlock *PhiBlock,
                               uint32_t Num, GVN &Gvn);
     bool areCallValsEqual(uint32_t Num, uint32_t NewNum, const BasicBlock *Pred,
                           const BasicBlock *PhiBlock, GVN &Gvn);
     std::pair<uint32_t, bool> assignExpNewValueNum(Expression &exp);
     bool areAllValsInBB(uint32_t num, const BasicBlock *BB, GVN &Gvn);
 
   public:
public:
     void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock);
     bool exists(Value *V) const;
     void add(Value *V, uint32_t num);
     void clear();
     void erase(Value *v);
     void setAliasAnalysis(AAResults *A) { AA = A; }
     AAResults *getAliasAnalysis() const { return AA; }
     void setMemDep(MemoryDependenceResults *M) { MD = M; }
+    void setMemorySSA(MemorySSA *M) { MSSA = M; }
     void setDomTree(DominatorTree *D) { DT = D; }
     uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
     void verifyRemoved(const Value *) const;
   };
 
 private:
   friend class gvn::GVNLegacyPass;
   friend struct DenseMapInfo<Expression>;

llvm/lib/Transforms/Scalar/GVN.cpp

if (AA->doesNotAccessMemory(C)) {
     valueNumbering[C] = v;
     return v;
   } else {
     valueNumbering[C] = nextValueNumber;
     return nextValueNumber++;
   }
 }
 
+// If MemorySSA is available, the incoming memory state is included in the hash
+// for loads and stores. If the incoming memory state is:
+// * LiveOnEntry, do nothing.
+// * a MemoryPhi, add <0, ID> where ID is the MemoryPhi ID.
+// * a MemoryDef, add VN, where VN is the value number of the memory setting
+//   instruction.
+uint32_t GVN::ValueTable::lookupOrAddLoadStore(Instruction *I) {
+  if (MSSA == nullptr) {
+    valueNumbering[I] = nextValueNumber;
+    return nextValueNumber++;
+  }
+
+  Expression e;
+  e.type = I->getType();
+  e.opcode = I->getOpcode();
+  for (Use &Op : I->operands())
+    e.varargs.push_back(lookupOrAdd(Op));
+
+  MemoryAccess *MA = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(I);
+  if (isa<MemoryPhi>(MA)) {
+    e.varargs.push_back(0);
+    e.varargs.push_back(MA->getID());
+  } else if (!MSSA->isLiveOnEntryDef(MA))
+    e.varargs.push_back(lookupOrAdd(cast<MemoryDef>(MA)->getMemoryInst()));
+
+  uint32_t N = assignExpNewValueNum(e).first;
+  valueNumbering[I] = N;
+  return N;
+}
+
 /// Returns true if a value number exists for the specified value.
 bool GVN::ValueTable::exists(Value *V) const { return valueNumbering.count(V) != 0; }
 
 /// lookup_or_add - Returns the value number for the specified value, assigning
 /// it a new number if it did not have one before.
 uint32_t GVN::ValueTable::lookupOrAdd(Value *V) {
   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
   if (VI != valueNumbering.end())
case Instruction::GetElementPtr:
       break;
     case Instruction::ExtractValue:
       exp = createExtractvalueExpr(cast<ExtractValueInst>(I));
       break;
     case Instruction::PHI:
       valueNumbering[V] = nextValueNumber;
       NumberingPhi[nextValueNumber] = cast<PHINode>(V);
       return nextValueNumber++;
+    case Instruction::Load:
+    case Instruction::Store:
+      return lookupOrAddLoadStore(I);
     default:
       valueNumbering[V] = nextValueNumber;
       return nextValueNumber++;
   }
 
   uint32_t e = assignExpNewValueNum(exp).first;
   valueNumbering[V] = e;
   return e;
PreservedAnalyses GVN::run(Function &F, FunctionAnalysisManager &AM) {
   // behavior, but until then don't change the order here.
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
   auto *MemDep =
       isMemDepEnabled() ? &AM.getResult<MemoryDependenceAnalysis>(F) : nullptr;
   auto *LI = AM.getCachedResult<LoopAnalysis>(F);
-  auto *MSSA = AM.getCachedResult<MemorySSAAnalysis>(F);
+  auto *MSSA = &AM.getResult<MemorySSAAnalysis>(F);
   auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
   bool Changed = runImpl(F, AC, DT, TLI, AA, MemDep, LI, &ORE,
                          MSSA ? &MSSA->getMSSA() : nullptr);
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<TargetLibraryAnalysis>();
bool GVN::ValueTable::areCallValsEqual(uint32_t Num, uint32_t NewNum,
   // Check to see if the Call has no function local clobber.
   for (const NonLocalDepEntry &D : deps) {
     if (D.getResult().isNonFuncLocal())
       return true;
   }
   return false;
 }
 
+// For certain opcodes, some varargs are not value numbers. Those numbers should
+// not be translated.
+static bool shouldNotPhiTranslate(const GVN::Expression &Exp, int Idx) {
+  return (Idx > 1 && Exp.opcode == Instruction::InsertValue) ||
+         (Idx > 0 && Exp.opcode == Instruction::ExtractValue) ||
+         (Idx > 1 && Exp.opcode == Instruction::ShuffleVector) ||
+         (Idx > 0 && Exp.opcode == Instruction::Load) ||
+         (Idx > 1 && Exp.opcode == Instruction::Store);
+}
+
 /// Translate value number \p Num using phis, so that it has the values of
 /// the phis in BB.
 uint32_t GVN::ValueTable::phiTranslateImpl(const BasicBlock *Pred,
                                            const BasicBlock *PhiBlock,
                                            uint32_t Num, GVN &Gvn) {
   if (PHINode *PN = NumberingPhi[Num]) {
     for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
       if (PN->getParent() == PhiBlock && PN->getIncomingBlock(i) == Pred)
uint32_t GVN::ValueTable::phiTranslateImpl(const BasicBlock *Pred,
   if (!areAllValsInBB(Num, PhiBlock, Gvn))
     return Num;
 
   if (Num >= ExprIdx.size() || ExprIdx[Num] == 0)
     return Num;
   Expression Exp = Expressions[ExprIdx[Num]];
 
   for (unsigned i = 0; i < Exp.varargs.size(); i++) {
-    // For InsertValue and ExtractValue, some varargs are index numbers
-    // instead of value numbers. Those index numbers should not be
-    // translated.
-    if ((i > 1 && Exp.opcode == Instruction::InsertValue) ||
-        (i > 0 && Exp.opcode == Instruction::ExtractValue) ||
-        (i > 1 && Exp.opcode == Instruction::ShuffleVector))
+    if (shouldNotPhiTranslate(Exp, i))
       continue;
     Exp.varargs[i] = phiTranslate(Pred, PhiBlock, Exp.varargs[i], Gvn);
   }
 
   if (Exp.commutative) {
     assert(Exp.varargs.size() >= 2 && "Unsupported commutative instruction!");
     if (Exp.varargs[0] > Exp.varargs[1]) {
       std::swap(Exp.varargs[0], Exp.varargs[1]);
bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
   VN.setDomTree(DT);
   TLI = &RunTLI;
   VN.setAliasAnalysis(&RunAA);
   MD = RunMD;
   ImplicitControlFlowTracking ImplicitCFT;
   ICF = &ImplicitCFT;
   this->LI = LI;
   VN.setMemDep(MD);
+  VN.setMemorySSA(MSSA);
   ORE = RunORE;
   InvalidBlockRPONumbers = true;
   MemorySSAUpdater Updater(MSSA);
   MSSAU = MSSA ? &Updater : nullptr;
 
   bool Changed = false;
   bool ShouldContinue = true;
 
void GVN::assignValNumForDeadCode() {
   }
 }
 
 // Won't reorder above these instructions.
 static bool isHoistBarrier(const Instruction &I) {
   return !isGuaranteedToTransferExecutionToSuccessor(&I);
 }
 
+// Return true iff the two instructions have the same volatile-ty and the same
+// atomic ordering.
+static bool canMergeInstructions(const Instruction &A, const Instruction &B) {
+  if (const auto *LA = dyn_cast<LoadInst>(&A)) {
+    const auto *LB = cast<LoadInst>(&B);
+    return LA->isVolatile() == LB->isVolatile() &&
+           LA->getOrdering() == LB->getOrdering();
+  }
+
+  if (const auto *SA = dyn_cast<StoreInst>(&A)) {
+    const auto *SB = cast<StoreInst>(&B);
+    return SA->isVolatile() == SB->isVolatile() &&
+           SA->getOrdering() == SB->getOrdering();
+  }
+
+  return true;
+}
+
 void GVN::collectHoistCandidates(BasicBlock *BB) {
   bool HasHoistBarrier = false;
   for (Instruction &I : *BB) {
     if (I.isTerminator())
       break;
     if (isa<PHINode>(I))
       continue;
 
for (Instruction &I : *BB) {
     if (I.isTerminator())
       break;
     if (isa<PHINode>(I))
       continue;
 
     if (!HasHoistBarrier || isSafeToSpeculativelyExecute(&I)) {
       uint32_t N = VN.lookupOrAdd(&I);
       auto It = HoistPairs.find(N);
-      if (It != HoistPairs.end())
+      if (It != HoistPairs.end()) {
+        // Only pair instructions with the same volatile-ty and atomic ordering.
+        if (canMergeInstructions(*It->second.first, I))
           It->second.second = &I;
       }
+    }
 
     if ((HasHoistBarrier |= isHoistBarrier(I)))
       LLVM_DEBUG(dbgs() << "Simple GVNHoist: reached hoist barrier" << I
                         << '\n';);
   }
 }
 
 void GVN::replaceInstruction(Instruction *I, Instruction *Repl) {
   LLVM_DEBUG(dbgs() << "Simple GVNHoist: replacing" << *I << " by" << *Repl
                     << '\n';);
+  assert(llvm::none_of(InstrsToErase,
+                       [=](const Instruction *X) { return I == X; }) &&
+         "Deleting an instruction twice");
   patchReplacementInstruction(I, Repl);
+  if (auto *LI = dyn_cast<LoadInst>(Repl))
+    LI->setAlignment(std::min(LI->getAlign(), cast<LoadInst>(I)->getAlign()));
+  else if (auto *SI = dyn_cast<StoreInst>(Repl))
+    SI->setAlignment(std::min(SI->getAlign(), cast<StoreInst>(I)->getAlign()));
   ICF->removeUsersOf(I);
   I->replaceAllUsesWith(Repl);
   salvageKnowledge(I, AC);
   salvageDebugInfo(*I);
   if (MD)
     MD->removeInstruction(I);
   if (MSSAU)
     MSSAU->removeMemoryAccess(I);
   VN.erase(I);
   ICF->removeInstruction(I);
   LLVM_DEBUG(verifyRemoved(I));
   I->eraseFromParent();
 }
 
+// Returns `true` if the instruction `Def` may write to the same memory that
+// `Use` reads.
+static bool defClobbersUse(AAResults *AA, Instruction *Def, Instruction *Use) {
+  Optional<MemoryLocation> DefLoc = MemoryLocation::getOrNone(Def);
+  Optional<MemoryLocation> UseLoc = MemoryLocation::getOrNone(Use);
+  return DefLoc && UseLoc ? !AA->isNoAlias(*DefLoc, *UseLoc) : true;
+}
+
 // Only hoist instructions from the "then" block.
 // Each hoisted instructions must be paired with an instruction from the "else"
 // block.
 std::pair<bool, bool> GVN::hoistPair(BasicBlock *DestBB, BasicBlock *ThenBB,
                                      BasicBlock *ElseBB, Instruction *ThenI,
                                      Instruction *ElseI) {
   // If the instruction is moved out of the "then" block there's nothing to do.
   if (ThenI->getParent() != ThenBB)
     return {false, false};
 
   // Instruction must have already been selected for hoisting and matched with
   // another instruction.
   auto It = HoistPairs.find(VN.lookupOrAdd(ThenI));
   if (It == HoistPairs.end())
     return {false, true};
 
   assert((ElseI == nullptr || ElseI == It->second.second) &&
          "Attempt to hoist two not paired instructions.");
 
   if (LLVM_LIKELY(ElseI == nullptr) && (ElseI = It->second.second) == nullptr)
     return {false, true};
   It->second.second = nullptr;
 
   assert(ElseI->getParent() == ElseBB && "Instruction already removed");
-  assert(!ThenI->mayReadOrWriteMemory() && !ElseI->mayReadOrWriteMemory() &&
-         "Memory read/write instructions must not be hoisted.");
   bool Change = false;
 
   // Hoist operands. Begin by hoisting all of the operands of the "then"
   // instruction, then check all of the operands of the "else" instruction
   // dominate its block.
   for (unsigned I = 0, N = ThenI->getNumOperands(); I < N; ++I) {
     auto *Op = dyn_cast<Instruction>(ThenI->getOperand(I));
     if (Op == nullptr)
std::pair<bool, bool> GVN::hoistPair(BasicBlock *DestBB, BasicBlock *ThenBB,
   for (unsigned I = 0, N = ElseI->getNumOperands(); I < N; ++I) {
     auto *Op = dyn_cast<Instruction>(ElseI->getOperand(I));
     if (Op == nullptr)
       continue;
     if (Op->getParent() == ElseBB)
       return {Change, true};
   }
 
+  // Do the same for memory dependencies.
+  if (ThenI->mayReadOrWriteMemory()) {
+    // Hoist preceding aliased MemoryDefs.
+    auto *MSSA = MSSAU->getMemorySSA();
+    auto *Walker = MSSA->getSkipSelfWalker();
+    MemoryAccess *ThenMA = Walker->getClobberingMemoryAccess(ThenI);
+    while (!MSSA->isLiveOnEntryDef(ThenMA) && ThenMA->getBlock() == ThenBB) {
+      bool DepChange, CantHoist;
+      std::tie(DepChange, CantHoist) =
+          hoistPair(DestBB, ThenBB, ElseBB,
+                    cast<MemoryDef>(ThenMA)->getMemoryInst(), nullptr);
+      Change |= DepChange;
+      if (CantHoist)
+        return {Change, true};
+      ThenMA = Walker->getClobberingMemoryAccess(ThenI);
+    }
+
+    MemoryAccess *ElseMA = Walker->getClobberingMemoryAccess(ElseI);
+    if (!MSSA->isLiveOnEntryDef(ElseMA) && ElseMA->getBlock() == ElseBB)
+      return {Change, true};
+
+    // For instructions that modify memory, try to hoist preceding aliased
+    // MemoryUses.
+    if (const auto *Def = dyn_cast<MemoryDef>(MSSA->getMemoryAccess(ThenI))) {
+      // Collect the uses ...
+      SmallVector<Instruction *, 4> MemoryUses;
+      for (const MemoryAccess &MA : *MSSA->getBlockAccesses(ThenBB)) {
+        if (const auto *Use = dyn_cast<MemoryUse>(&MA)) {
+          if (!MSSA->locallyDominates(Use, Def))
+            continue;
+          Instruction *U = Use->getMemoryInst();
+          if (!defClobbersUse(getAliasAnalysis(), ThenI, U))
+            continue;
+          MemoryUses.push_back(U);
+        }
+      }
+
+      // ... then try to hoist them.
+      for (Instruction *I : MemoryUses) {
+        bool DepChange, CantHoist;
+        std::tie(DepChange, CantHoist) =
+            hoistPair(DestBB, ThenBB, ElseBB, I, nullptr);
+        Change |= DepChange;
+        if (CantHoist)
+          return {Change, true};
+      }
+
+      // None should have remained in the "else" block.
+      Def = cast<MemoryDef>(MSSA->getMemoryAccess(ElseI));
+      for (const MemoryAccess &MA : *MSSA->getBlockAccesses(ElseBB)) {
+        if (const auto *Use = dyn_cast<MemoryUse>(&MA)) {
+          if (!MSSA->locallyDominates(Use, Def))
+            continue;
+          Instruction *U = Use->getMemoryInst();
+          if (defClobbersUse(getAliasAnalysis(), ElseI, U))
+            return {Change, true};
+        }
+      }
+    }
+  }
+
+  // Remove the instruction from the memory dependence cache, as the cache might
+  // keep a reference to the old block.
+  MD->removeInstruction(ThenI);
   // Hoist one of the instructions and replace all uses of the other with it.
   ICF->removeInstruction(ThenI);
   ICF->insertInstructionTo(ThenI, DestBB);
   ThenI->moveBefore(DestBB->getTerminator());
+  if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(ThenI))
+    MSSAU->moveToPlace(MA, DestBB, MemorySSA::InsertionPlace::BeforeTerminator);
   replaceInstruction(ElseI, ThenI);
 
   return {true, false};
 }
 
 // Perform trivial hoisting of values from two blocks to their common
 // predecessor.
 bool GVN::performHoist(Function &F) {

llvm/test/Analysis/ValueTracking/gep-negative-issue.ll

entry:
   %y3 = load double addrspace(100)*, double addrspace(100)* addrspace(100)* %y2
   %y4 = getelementptr inbounds double, double addrspace(100)* %y3, i64 -1
   store double 0.000000e+00, double addrspace(100)* %y4
   ret void
 ; CHECK-LABEL: define void @test
 ; CHECK: getelementptr inbounds double, double addrspace(100)* {{%.*}}, i64 -1
 ; CHECK-NEXT: store double 0.000000e+00, double addrspace(100)* [[DST:%.*]]
 ; CHECK-NEXT: store double 0.000000e+00, double addrspace(100)* [[DST]]
-; CHECK: load
-; CHECK: getelementptr inbounds %ArrayImpl, %ArrayImpl addrspace(100)*
-; CHECK: load
+; CHECK: load double addrspace(100)*
 ; CHECK: getelementptr inbounds double, double addrspace(100)* {{%.*}}, i64 -1
 ; CHECK: store double 0.000000e+00, double addrspace(100)*
 ; CHECK: ret
 }

llvm/test/Transforms/GVN/PRE/load-pre-align.ll

-; RUN: opt < %s -gvn -S | FileCheck %s
-; RUN: opt < %s -passes="gvn<load-pre>" -S | FileCheck %s
+; RUN: opt < %s -gvn                    --enable-simple-gvn-hoist=false -S | FileCheck %s
+; RUN: opt < %s -passes="gvn<load-pre>" --enable-simple-gvn-hoist=false -S | FileCheck %s
 
 target datalayout = "e-p:32:32:32-i1:8:32-i8:8:32-i16:16:32-i32:32:32-i64:32:32-f32:32:32-f64:32:32-v64:64:64-v128:128:128-a0:0:32-n32"
 
 @p = external global i32
 
 define i32 @test(i32 %n) nounwind {
 ; CHECK-LABEL: @test(
 entry:

llvm/test/Transforms/GVN/PRE/pre-single-pred.ll

-; RUN: opt < %s -gvn -enable-load-pre -S | FileCheck %s
-; RUN: opt < %s -passes="gvn<load-pre>" -enable-load-pre=false -S | FileCheck %s
+; RUN: opt < %s -gvn -enable-load-pre -enable-simple-gvn-hoist=false -S | FileCheck %s
+; RUN: opt < %s -passes="gvn<load-pre>" -enable-simple-gvn-hoist=false -enable-load-pre=false -S | FileCheck %s
 ; This testcase assumed we'll PRE the load into %for.cond, but we don't actually
 ; verify that doing so is safe.  If there didn't _happen_ to be a load in
 ; %for.end, we would actually be lengthening the execution on some paths, and
 ; we were never actually checking that case.  Now we actually do perform some
 ; conservative checking to make sure we don't make paths longer, but we don't
 ; currently get this case, which we got lucky on previously.
 ;
 ; Now that that faulty assumption is corrected, test that we DON'T incorrectly

llvm/test/Transforms/GVN/PRE/volatile.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; Tests that check our handling of volatile instructions encountered
 ; when scanning for dependencies
-; RUN: opt -basic-aa -gvn -S < %s | FileCheck %s
+; RUN: opt -basic-aa -gvn -enable-simple-gvn-hoist=false -S < %s | FileCheck %s
 
 ; Check that we can bypass a volatile load when searching
 ; for dependencies of a non-volatile load
 define i32 @test1(i32* nocapture %p, i32* nocapture %q) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load volatile i32, i32* [[Q:%.*]], align 4
 ; CHECK-NEXT:    ret i32 0

llvm/test/Transforms/GVN/condprop.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -basic-aa -gvn -S | FileCheck %s
+; RUN: opt < %s -basic-aa -gvn -enable-simple-gvn-hoist=false -S | FileCheck %s
 
 @a = external global i32    ; <i32*> [#uses=7]
 
 define i32 @test1() nounwind {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* @a, align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 4

llvm/test/Transforms/GVN/simple-gvnhoist-loadstore.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S --aa-pipeline=tbaa,basic-aa --passes=gvn %s | FileCheck %s
 
 define dso_local i32 @basic_load_hoisting(i1 %cc, i32* %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @basic_load_hoisting(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
-; CHECK:       if.then:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[TMP0]], [[B:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = sdiv i32 [[C:%.*]], [[TMP1]]
+; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[A]], align 4
-; CHECK-NEXT:    [[TMP4:%.*]] = add nsw i32 [[TMP3]], [[B]]
-; CHECK-NEXT:    [[TMP5:%.*]] = sdiv i32 [[C]], [[TMP4]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP2]], [[IF_THEN]] ], [ [[TMP5]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP2]], [[IF_THEN]] ], [ [[TMP2]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   %0 = load i32, i32* %a
   %1 = add nsw i32 %0, %b

 if.end:
   %r = phi i32 [%2, %if.then], [%5, %if.else]
   ret i32 %r
 }
 
 define dso_local i32 @hoist_volatile(i1 %cc, i32* %a) {
 ; CHECK-LABEL: @hoist_volatile(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load volatile i32, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    [[TMP0:%.*]] = load volatile i32, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    [[TMP1:%.*]] = load volatile i32, i32* [[A]], align 4
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[IF_THEN]] ], [ [[TMP1]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[IF_THEN]] ], [ [[TMP0]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   %0 = load volatile i32, i32* %a
   br label %if.end

 if.end:
   %r = phi i32 [%0, %if.then], [%1, %if.else]
   ret i32 %r
 }
 
 define dso_local i32 @hoist_atomic(i1 %cc, i32* %a) {
 ; CHECK-LABEL: @hoist_atomic(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load atomic i32, i32* [[A:%.*]] acquire, align 4
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    [[TMP0:%.*]] = load atomic i32, i32* [[A:%.*]] acquire, align 4
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    [[TMP1:%.*]] = load atomic i32, i32* [[A]] acquire, align 4
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[IF_THEN]] ], [ [[TMP1]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[IF_THEN]] ], [ [[TMP0]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   %0 = load atomic i32, i32* %a acquire, align 4
   br label %if.end

 if.end:
   %r = phi i32 [%0, %if.then], [%1, %if.else]
   ret i32 %r
 }
 
 define dso_local i32 @no_reorder_load_over_aliasing_store1(i1 %cc, i32* %a, i32* %b, i32* %c, i32 %d, i32 %e) {
 ; CHECK-LABEL: @no_reorder_load_over_aliasing_store1(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i32 0, i32* [[B:%.*]], align 4, !tbaa [[TBAA0:![0-9]+]]
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    store i32 0, i32* [[C:%.*]], align 4, !tbaa [[TBAA0:![0-9]+]]
-; CHECK-NEXT:    store i32 0, i32* [[B:%.*]], align 4, !tbaa [[TBAA4:![0-9]+]]
+; CHECK-NEXT:    store i32 0, i32* [[C:%.*]], align 4, !tbaa [[TBAA4:![0-9]+]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[A:%.*]], align 4, !tbaa [[TBAA6:![0-9]+]]
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    store i32 0, i32* [[B]], align 4, !tbaa [[TBAA4]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[A]], align 4, !tbaa [[TBAA6]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[TMP1]], [[D:%.*]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], [[E:%.*]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[IF_THEN]] ], [ [[TMP3]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;

 if.end:
   %r = phi i32 [%0, %if.then], [%3, %if.else]
   ret i32 %r
 }
 
 define dso_local i32 @reorder_non_volatile(i1 %cc, i32* %a, i32* %b, i32 %c) {
 ; CHECK-LABEL: @reorder_non_volatile(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[B:%.*]], align 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i32 [[TMP0]], [[TMP1]]
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
 ; CHECK-NEXT:    [[TMP3:%.*]] = load volatile i32, i32* [[B]], align 4
-; CHECK-NEXT:    [[TMP4:%.*]] = load i32, i32* [[A]], align 4
-; CHECK-NEXT:    [[TMP5:%.*]] = add nsw i32 [[TMP3]], [[TMP4]]
+; CHECK-NEXT:    [[TMP4:%.*]] = add nsw i32 [[TMP3]], [[TMP0]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP2]], [[IF_THEN]] ], [ [[TMP5]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP2]], [[IF_THEN]] ], [ [[TMP4]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   %0 = load i32, i32* %a
   %1 = load i32, i32* %b

 if.end:
   %r = phi i32 [%2, %if.then], [%5, %if.else]
   ret i32 %r
 }
 
 define dso_local i32 @no_reorder_atomic1(i1 %cc, i32* %a, i32* %b, i32 %c) {
 ; CHECK-LABEL: @no_reorder_atomic1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
-; CHECK:       if.then:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load atomic i32, i32* [[A:%.*]] acquire, align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = load atomic i32, i32* [[B:%.*]] acquire, align 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i32 [[TMP0]], [[TMP1]]
+; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    [[TMP3:%.*]] = load atomic i32, i32* [[A]] acquire, align 4
-; CHECK-NEXT:    [[TMP4:%.*]] = load atomic i32, i32* [[B]] acquire, align 4
-; CHECK-NEXT:    [[TMP5:%.*]] = add nsw i32 [[TMP3]], [[TMP4]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP2]], [[IF_THEN]] ], [ [[TMP5]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP2]], [[IF_THEN]] ], [ [[TMP2]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   %0 = load atomic i32, i32* %a acquire, align 4
   %1 = load atomic i32, i32* %b acquire, align 4

 if.end:
   %r = phi i32 [%2, %if.then], [%5, %if.else]
   ret i32 %r
 }
 
 define dso_local i32 @reorder_load_over_non_aliasing_store(i1 %cc, i32* %a, i32 %b, i32 %c, i32* %p) {
 ; CHECK-LABEL: @reorder_load_over_non_aliasing_store(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[A:%.*]], align 4, !tbaa [[TBAA4]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[TMP0]], [[B:%.*]]
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4, !tbaa [[TBAA4]]
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[A:%.*]], align 4, !tbaa [[TBAA0]]
-; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[TMP0]], [[B:%.*]]
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4, !tbaa [[TBAA0]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = sdiv i32 [[C:%.*]], [[TMP0]]
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[A]], align 4, !tbaa [[TBAA0]]
-; CHECK-NEXT:    [[TMP4:%.*]] = add nsw i32 [[TMP3]], [[B]]
-; CHECK-NEXT:    [[TMP5:%.*]] = sdiv i32 [[C]], [[TMP4]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sdiv i32 [[C]], [[TMP1]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP2]], [[IF_THEN]] ], [ [[TMP5]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP2]], [[IF_THEN]] ], [ [[TMP3]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   store i32 0, i32* %p, !tbaa !5
   %0 = load i32, i32* %a, !tbaa !6

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[CC0:%.*]], label [[IF_THEN0:%.*]], label [[IF_ELSE0:%.*]]
 ; CHECK:       if.then0:
 ; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br label [[BB:%.*]]
 ; CHECK:       if.else0:
 ; CHECK-NEXT:    br label [[BB]]
 ; CHECK:       bb:
-; CHECK-NEXT:    br i1 [[CC1:%.*]], label [[IF_THEN1:%.*]], label [[IF_ELSE1:%.*]]
-; CHECK:       if.then1:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[TMP0]], [[B:%.*]]
+; CHECK-NEXT:    br i1 [[CC1:%.*]], label [[IF_THEN1:%.*]], label [[IF_ELSE1:%.*]]
+; CHECK:       if.then1:
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else1:
-; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[A]], align 4
-; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i32 [[TMP2]], [[B]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP1]], [[IF_THEN1]] ], [ [[TMP3]], [[IF_ELSE1]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP1]], [[IF_THEN1]] ], [ [[TMP1]], [[IF_ELSE1]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc0, label %if.then0, label %if.else0
 
 if.then0:
   store i32 0, i32* %p
   br label %bb

 if.end:
   %r = phi i32 [%1, %if.then1], [%3, %if.else1]
   ret i32 %r
 }
 
 define dso_local i32 @host_store0(i1 %cc, i32* %a, i32 %b, i32* %p) {
 ; CHECK-LABEL: @host_store0(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[B:%.*]], 1
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i32 [[B]], [[TMP1]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[IF_THEN]] ], [ [[TMP2]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:

 if.end:
   %r = phi i32 [%0, %if.then], [%2, %if.else]
   ret i32 %r
 }
 
 define dso_local i32 @host_store1(i1 %cc, i32* %a, i32 %b, i32* %p) {
 ; CHECK-LABEL: @host_store1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
-; CHECK:       if.then:
 ; CHECK-NEXT:    store i32 1, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[B:%.*]], 1
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    store i32 1, i32* [[A]], align 4
-; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[A]], align 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i32 [[B]], [[TMP1]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[IF_THEN]] ], [ [[TMP2]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:

 if.end:
   %r = phi i32 [%0, %if.then], [%2, %if.else]
   ret i32 %r
 }
 
 define dso_local i32 @no_store_reorder_across_aliasing_load1(i1 %cc, i32* %a, i32* %b, i32* %p) {
 ; CHECK-LABEL: @no_store_reorder_across_aliasing_load1(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[TMP0]], 1
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[A]], align 4
-; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[B:%.*]], align 4
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[B:%.*]], align 4
 ; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
-; CHECK-NEXT:    [[TMP4:%.*]] = add nsw i32 [[TMP2]], [[TMP3]]
+; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i32 [[TMP0]], [[TMP2]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP1]], [[IF_THEN]] ], [ [[TMP4]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP1]], [[IF_THEN]] ], [ [[TMP3]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   %0 = load i32, i32* %a
   store i32 0, i32* %p

 if.end:
   %r = phi i32 [%1, %if.then], [%4, %if.else]
   ret i32 %r
 }
 
 define dso_local void @store_reorder_across_nonaliasing_store(i1 %cc, i32* %b, i32* %c) {
 ; CHECK-LABEL: @store_reorder_across_nonaliasing_store(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i32 1, i32* [[C:%.*]], align 4, !tbaa [[TBAA4]]
+; CHECK-NEXT:    store i32 0, i32* [[B:%.*]], align 4, !tbaa [[TBAA0]]
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    store i32 0, i32* [[B:%.*]], align 4, !tbaa [[TBAA4]]
-; CHECK-NEXT:    store i32 1, i32* [[C:%.*]], align 4, !tbaa [[TBAA0]]
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    store i32 1, i32* [[C]], align 4, !tbaa [[TBAA0]]
-; CHECK-NEXT:    store i32 0, i32* [[B]], align 4, !tbaa [[TBAA4]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   store i32 0, i32* %b, !tbaa !5
   store i32 1, i32* %c, !tbaa !6
   br label %if.end
 
 if.else:
   store i32 1, i32* %c, !tbaa !6
   store i32 0, i32* %b, !tbaa !5
   br label %if.end
 
 if.end:
   ret void
 }
 
 define dso_local i32 @store_reorder_across_nonaliasing_load(i1 %cc, i32* %b, i32* %c) {
 ; CHECK-LABEL: @store_reorder_across_nonaliasing_load(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i32 1, i32* [[C:%.*]], align 4, !tbaa [[TBAA4]]
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[B:%.*]], align 4, !tbaa [[TBAA4]]
-; CHECK-NEXT:    store i32 1, i32* [[C:%.*]], align 4, !tbaa [[TBAA0]]
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[B:%.*]], align 4, !tbaa [[TBAA0]]
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    store i32 1, i32* [[C]], align 4, !tbaa [[TBAA0]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[B]], align 4
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[IF_THEN]] ], [ [[TMP1]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else

llvm/test/Transforms/GVN/simple-gvnhoist-scalars.ll

if.else:
   %3 = sdiv i32 %c, %2
   br label %if.end
 
 if.end:
   %r = phi i32 [%1, %if.then], [%3, %if.else]
   ret i32 %r
 }
 
-; speculation barrier
+; speculation barrier (it could have hoisted the `sdiv`s, but the search stops
+; at the `store` before the `store` itself is hoisted).
 define dso_local i32 @spec_barrier1(i1 %cc, i32 %a, i32 %b, i32 %c, i32* %p) {
 ; CHECK-LABEL: @spec_barrier1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    store volatile i32 0, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    store volatile i32 0, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = sdiv i32 [[C:%.*]], [[TMP0]]
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    store volatile i32 0, i32* [[P]], align 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = sdiv i32 [[C]], [[TMP0]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP1]], [[IF_THEN]] ], [ [[TMP2]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else

 ; CHECK-NEXT:    [[TMP0:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[C:%.*]], [[TMP0]]
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    [[TMP2:%.*]] = load atomic volatile i32, i32* [[P:%.*]] acquire, align 4
 ; CHECK-NEXT:    [[TMP3:%.*]] = mul nsw i32 [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    [[TMP4:%.*]] = load atomic volatile i32, i32* [[P]] acquire, align 4
+; CHECK-NEXT:    [[TMP4:%.*]] = load atomic volatile i32, i32* [[P]] monotonic, align 4
 ; CHECK-NEXT:    [[TMP5:%.*]] = mul nsw i32 [[TMP4]], [[TMP1]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP3]], [[IF_THEN]] ], [ [[TMP5]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   %0 = load atomic volatile i32, i32* %p acquire, align 4
   %1 = sdiv i32 %a, %b
   %2 = add nsw i32 %c, %1
   %3 = mul nsw i32 %0, %2
   br label %if.end
 
 if.else:
-  %4 = load atomic volatile i32, i32* %p acquire, align 4
+  %4 = load atomic volatile i32, i32* %p monotonic, align 4
   %5 = sdiv i32 %a, %b
   %6 = add nsw i32 %c, %5
   %7 = mul nsw i32 %4, %6
   br label %if.end
 
 if.end:
   %r = phi i32 [%3, %if.then], [%7, %if.else]
   ret i32 %r

llvm/test/Transforms/GVNHoist/hoist-inline.ll

 ; RUN: opt -S -O2 -enable-gvn-hoist < %s | FileCheck %s
 
 ; Check that the inlined loads are hoisted.
 ; CHECK-LABEL: define i32 @fun(
 ; CHECK-LABEL: entry:
+; CHECK-NOT: if.then
 ; CHECK: load i32, i32* @A
-; CHECK: if.then:
 
 @A = external global i32
 @B = external global i32
 @C = external global i32
 
 define i32 @loadA() {
    %a = load i32, i32* @A
    ret i32 %a

llvm/test/Transforms/InstMerge/st_sink_bugfix_22613.ll

 ; ModuleID = 'bug.c'
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
-; RUN: opt -O2 -S < %s | FileCheck %s
+; RUN: opt -O2 -S  --enable-simple-gvn-hoist=false < %s | FileCheck %s
 
 ; CHECK-LABEL: main
 ; CHECK: if.end
 ; CHECK: store
 ; CHECK: memset
 ; CHECK: if.then
 ; CHECK: store
 ; CHECK: memset