[GVN] Improve PRE on load instructions

[Carrot]

Summary

This patch implements the enhancement proposed by https://github.com/llvm/llvm-project/issues/59312.

Suppose we have following code

   v0 = load %addr
   br %LoadBB

LoadBB:
   v1 = load %addr
   ...

PredBB:
   ...
   br %cond, label %LoadBB, label %SuccBB

SuccBB:
   v2 = load %addr
   ...

Instruction v1 in LoadBB is partially redundant, edge (PredBB, LoadBB) is a critical edge. SuccBB is another successor of PredBB, it contains another load v2 which is identical to v1. Current GVN splits the critical edge (PredBB, LoadBB) and inserts a new load in it. A better method is move the load of v2 into PredBB, then v1 can be changed to a PHI instruction.

If there are two or more similar predecessors, like the test case in the bug entry, current GVN simply gives up because otherwise it needs to split multiple critical edges. But we can move all loads in successor blocks into predecessors.

Compared to last version, this patch contains a check for implicit control flow instruction in function findLoadToHoistIntoPred, so we can avoid moving load across unexpected control flow.

@reames and @hans please try to see if this patch works for your code.

[reames]

Please close this review and reopen the old review with the new diff so that review history is not lost.

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

private:
 
   /// Given a list of non-local dependencies, determine if a value is
   /// available for the load in each specified block.  If it is, add it to
   /// ValuesPerBlock.  If not, add it to UnavailableBlocks.
   void AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
                                AvailValInBlkVect &ValuesPerBlock,
                                UnavailBlkVect &UnavailableBlocks);
 
+  /// Given a critical edge from Pred to LoadBB, find a load instruction
+  /// which is identical to Load from another successor of Pred.
+  LoadInst *findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB,
+                                    LoadInst *Load);
+
   bool PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
                       UnavailBlkVect &UnavailableBlocks);
 
   /// Try to replace a load which executes on each loop iteraiton with Phi
   /// translation of load in preheader and load(s) in conditionally executed
   /// paths.
   bool performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
                           UnavailBlkVect &UnavailableBlocks);
 
   /// Eliminates partially redundant \p Load, replacing it with \p
   /// AvailableLoads (connected by Phis if needed).
   void eliminatePartiallyRedundantLoad(
       LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
-      MapVector<BasicBlock *, Value *> &AvailableLoads);
+      MapVector<BasicBlock *, Value *> &AvailableLoads,
+      MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad);
 
   // Other helper routines
   bool processInstruction(Instruction *I);
   bool processBlock(BasicBlock *BB);
   void dump(DenseMap<uint32_t, Value *> &d) const;
   bool iterateOnFunction(Function &F);
   bool performPRE(Function &F);
   bool performScalarPRE(Instruction *I);

llvm/lib/Transforms/Scalar/GVN.cpp

 STATISTIC(NumGVNInstr, "Number of instructions deleted");
 STATISTIC(NumGVNLoad, "Number of loads deleted");
 STATISTIC(NumGVNPRE, "Number of instructions PRE'd");
 STATISTIC(NumGVNBlocks, "Number of blocks merged");
 STATISTIC(NumGVNSimpl, "Number of instructions simplified");
 STATISTIC(NumGVNEqProp, "Number of equalities propagated");
 STATISTIC(NumPRELoad, "Number of loads PRE'd");
 STATISTIC(NumPRELoopLoad, "Number of loop loads PRE'd");
+STATISTIC(NumPRELoadMoved2CEPred,
+          "Number of loads moved to predecessor of a critical edge in PRE");
 
 STATISTIC(IsValueFullyAvailableInBlockNumSpeculationsMax,
           "Number of blocks speculated as available in "
           "IsValueFullyAvailableInBlock(), max");
 STATISTIC(MaxBBSpeculationCutoffReachedTimes,
           "Number of times we we reached gvn-max-block-speculations cut-off "
           "preventing further exploration");
 
cl::desc("Max number of blocks we're willing to speculate on (and recurse "
              "into) when deducing if a value is fully available or not in GVN "
              "(default = 600)"));
 
 static cl::opt<uint32_t> MaxNumVisitedInsts(
     "gvn-max-num-visited-insts", cl::Hidden, cl::init(100),
     cl::desc("Max number of visited instructions when trying to find "
              "dominating value of select dependency (default = 100)"));
 
+static cl::opt<uint32_t> MaxNumInsnsPerBlock(
+    "gvn-max-num-insns", cl::Hidden, cl::init(100),
+    cl::desc("Max number of instructions to scan in each basic block in GVN "
+             "(default = 100)"));
+
 struct llvm::GVNPass::Expression {
   uint32_t opcode;
   bool commutative = false;
   // The type is not necessarily the result type of the expression, it may be
   // any additional type needed to disambiguate the expression.
   Type *type = nullptr;
   SmallVector<uint32_t, 4> varargs;
 
#ifndef NDEBUG
 
   assert(NewSpeculativelyAvailableBBs.empty() &&
          "Must have fixed all the new speculatively available blocks.");
 #endif
 
   return !UnavailableBB;
 }
 
+/// If the specified (BB, OldValue) exists in ValuesPerBlock, replace its value
+/// with NewValue, otherwise we don't change it.
+static void replaceValuesPerBlockEntry(
+    SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock, BasicBlock *BB,
+    Value *OldValue, Value *NewValue) {
+  for (AvailableValueInBlock &V : ValuesPerBlock) {
+    if (V.BB == BB) {
+      if ((V.AV.isSimpleValue() && V.AV.getSimpleValue() == OldValue) ||
+         (V.AV.isCoercedLoadValue() && V.AV.getCoercedLoadValue() == OldValue))
+        V = AvailableValueInBlock::get(BB, NewValue);
+      return;
+    }
+  }
+}
+
 /// Given a set of loads specified by ValuesPerBlock,
 /// construct SSA form, allowing us to eliminate Load.  This returns the value
 /// that should be used at Load's definition site.
 static Value *
 ConstructSSAForLoadSet(LoadInst *Load,
                        SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock,
                        GVNPass &gvn) {
   // Check for the fully redundant, dominating load case.  In this case, we can
if (auto AV = AnalyzeLoadAvailability(Load, DepInfo, Dep.getAddress())) {
       UnavailableBlocks.push_back(DepBB);
     }
   }
 
   assert(Deps.size() == ValuesPerBlock.size() + UnavailableBlocks.size() &&
          "post condition violation");
 }
 
+/// Given the following code, v1 is partially available on some edges, but not
+/// available on the edge from PredBB. This function tries to find if there is
+/// another identical load in the other successor of PredBB.
+///
+///      v0 = load %addr
+///      br %LoadBB
+///
+///   LoadBB:
+///      v1 = load %addr
+///      ...
+///
+///   PredBB:
+///      ...
+///      br %cond, label %LoadBB, label %SuccBB
+///
+///   SuccBB:
+///      v2 = load %addr
+///      ...
+///
+LoadInst *GVNPass::findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB,
+                                           LoadInst *Load) {
+  // For simplicity we handle a Pred has 2 successors only.
+  auto *Term = Pred->getTerminator();
+  if (Term->getNumSuccessors() != 2 || Term->isExceptionalTerminator())
+    return nullptr;
+  auto *SuccBB = Term->getSuccessor(0);
+  if (SuccBB == LoadBB)
+    SuccBB = Term->getSuccessor(1);
+  if (!SuccBB->getSinglePredecessor())
+    return nullptr;
+
+  unsigned int NumInsts = MaxNumInsnsPerBlock;
+  for (Instruction &Inst : *SuccBB) {
+    if (Inst.isDebugOrPseudoInst())
+      continue;
+    if (--NumInsts == 0)
+      return nullptr;
+
+    if (!Inst.isIdenticalTo(Load))
+      continue;
+
+    MemDepResult Dep = MD->getDependency(&Inst);
+    // If an identical load doesn't depends on any local instructions, it can
+    // be safely moved to PredBB.
+    // Also check for the implicit control flow instructions. See the comments
+    // in PerformLoadPRE for details.
+    if (Dep.isNonLocal() && !ICF->isDominatedByICFIFromSameBlock(&Inst))
+      return cast<LoadInst>(&Inst);
+
+    // Otherwise there is something in the same BB clobbers the memory, we can't
+    // move this and later load to PredBB.
+    return nullptr;
+  }
+
+  return nullptr;
+}
+
 void GVNPass::eliminatePartiallyRedundantLoad(
     LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
-    MapVector<BasicBlock *, Value *> &AvailableLoads) {
+    MapVector<BasicBlock *, Value *> &AvailableLoads,
+    MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad) {
   for (const auto &AvailableLoad : AvailableLoads) {
     BasicBlock *UnavailableBlock = AvailableLoad.first;
     Value *LoadPtr = AvailableLoad.second;
 
     auto *NewLoad =
         new LoadInst(Load->getType(), LoadPtr, Load->getName() + ".pre",
                      Load->isVolatile(), Load->getAlign(), Load->getOrdering(),
                      Load->getSyncScopeID(), UnavailableBlock->getTerminator());
for (const auto &AvailableLoad : AvailableLoads) {
     // FIXME: How do we retain source locations without causing poor debugging
     // behavior?
 
     // Add the newly created load.
     ValuesPerBlock.push_back(
         AvailableValueInBlock::get(UnavailableBlock, NewLoad));
     MD->invalidateCachedPointerInfo(LoadPtr);
     LLVM_DEBUG(dbgs() << "GVN INSERTED " << *NewLoad << '\n');
+
+    // For PredBB in CriticalEdgePredAndLoad we need to replace the uses of old
+    // load instruction with the new created load instruction.
+    if (CriticalEdgePredAndLoad) {
+      auto I = CriticalEdgePredAndLoad->find(UnavailableBlock);
+      if (I != CriticalEdgePredAndLoad->end()) {
+        ++NumPRELoadMoved2CEPred;
+        ICF->insertInstructionTo(NewLoad, UnavailableBlock);
+        LoadInst *OldLoad = I->second;
+        OldLoad->replaceAllUsesWith(NewLoad);
+        replaceValuesPerBlockEntry(ValuesPerBlock, OldLoad->getParent(),
+                                   OldLoad, NewLoad);
+        if (uint32_t ValNo = VN.lookup(OldLoad, false))
+          removeFromLeaderTable(ValNo, OldLoad, OldLoad->getParent());
+        // To avoid deleting an instruction from different BB, we just leave
+        // the dead load here, it will be deleted in next iteration.
+      }
+    }
   }
 
   // Perform PHI construction.
   Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);
   Load->replaceAllUsesWith(V);
   if (isa<PHINode>(V))
     V->takeName(Load);
   if (Instruction *I = dyn_cast<Instruction>(V))
bool GVNPass::PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
   // available.
   MapVector<BasicBlock *, Value *> PredLoads;
   DenseMap<BasicBlock *, AvailabilityState> FullyAvailableBlocks;
   for (const AvailableValueInBlock &AV : ValuesPerBlock)
     FullyAvailableBlocks[AV.BB] = AvailabilityState::Available;
   for (BasicBlock *UnavailableBB : UnavailableBlocks)
     FullyAvailableBlocks[UnavailableBB] = AvailabilityState::Unavailable;
 
-  SmallVector<BasicBlock *, 4> CriticalEdgePred;
+  // The edge from Pred to LoadBB is a critical edge will be splitted.
+  SmallVector<BasicBlock *, 4> CriticalEdgePredSplit;
+  // The edge from Pred to LoadBB is a critical edge, another successor of Pred
+  // contains a load can be moved to Pred. This data structure maps the Pred to
+  // the movable load.
+  MapVector<BasicBlock *, LoadInst *> CriticalEdgePredAndLoad;
   for (BasicBlock *Pred : predecessors(LoadBB)) {
     // If any predecessor block is an EH pad that does not allow non-PHI
     // instructions before the terminator, we can't PRE the load.
     if (Pred->getTerminator()->isEHPad()) {
       LLVM_DEBUG(
           dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
                  << Pred->getName() << "': " << *Load << '\n');
       return false;
if (Pred->getTerminator()->getNumSuccessors() != 1) {
         if (DT->dominates(LoadBB, Pred)) {
           LLVM_DEBUG(
               dbgs()
               << "COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"
               << Pred->getName() << "': " << *Load << '\n');
           return false;
         }
 
-      CriticalEdgePred.push_back(Pred);
+      if (LoadInst *LI = findLoadToHoistIntoPred(Pred, LoadBB, Load))
+        CriticalEdgePredAndLoad[Pred] = LI;
+      else
+        CriticalEdgePredSplit.push_back(Pred);
     } else {
       // Only add the predecessors that will not be split for now.
       PredLoads[Pred] = nullptr;
     }
   }
 
   // Decide whether PRE is profitable for this load.
-  unsigned NumUnavailablePreds = PredLoads.size() + CriticalEdgePred.size();
+  unsigned NumInsertPreds = PredLoads.size() + CriticalEdgePredSplit.size();
+  unsigned NumUnavailablePreds = NumInsertPreds +
+      CriticalEdgePredAndLoad.size();
   assert(NumUnavailablePreds != 0 &&
          "Fully available value should already be eliminated!");
   (void)NumUnavailablePreds;
 
-  // If this load is unavailable in multiple predecessors, reject it.
+  // If we need to insert new load in multiple predecessors, reject it.
   // FIXME: If we could restructure the CFG, we could make a common pred with
   // all the preds that don't have an available Load and insert a new load into
   // that one block.
-  if (NumUnavailablePreds != 1)
+  if (NumInsertPreds > 1)
       return false;
 
   // Now we know where we will insert load. We must ensure that it is safe
   // to speculatively execute the load at that points.
   if (MustEnsureSafetyOfSpeculativeExecution) {
-    if (CriticalEdgePred.size())
+    if (CriticalEdgePredSplit.size())
       if (!isSafeToSpeculativelyExecute(Load, LoadBB->getFirstNonPHI(), AC, DT))
         return false;
     for (auto &PL : PredLoads)
       if (!isSafeToSpeculativelyExecute(Load, PL.first->getTerminator(), AC,
                                         DT))
         return false;
+    for (auto &CEP : CriticalEdgePredAndLoad)
+      if (!isSafeToSpeculativelyExecute(Load, CEP.first->getTerminator(), AC,
+                                        DT))
+        return false;
   }
 
   // Split critical edges, and update the unavailable predecessors accordingly.
-  for (BasicBlock *OrigPred : CriticalEdgePred) {
+  for (BasicBlock *OrigPred : CriticalEdgePredSplit) {
     BasicBlock *NewPred = splitCriticalEdges(OrigPred, LoadBB);
     assert(!PredLoads.count(OrigPred) && "Split edges shouldn't be in map!");
     PredLoads[NewPred] = nullptr;
     LLVM_DEBUG(dbgs() << "Split critical edge " << OrigPred->getName() << "->"
                       << LoadBB->getName() << '\n');
   }
 
+  for (auto &CEP : CriticalEdgePredAndLoad)
+    PredLoads[CEP.first] = nullptr;
+
   // Check if the load can safely be moved to all the unavailable predecessors.
   bool CanDoPRE = true;
   const DataLayout &DL = Load->getModule()->getDataLayout();
   SmallVector<Instruction*, 8> NewInsts;
   for (auto &PredLoad : PredLoads) {
     BasicBlock *UnavailablePred = PredLoad.first;
 
     // Do PHI translation to get its value in the predecessor if necessary.  The
while (!NewInsts.empty()) {
       // trying to number them. PHI translation might insert instructions
       // in basic blocks other than the current one, and we delete them
       // directly, as markInstructionForDeletion only allows removing from the
       // current basic block.
       NewInsts.pop_back_val()->eraseFromParent();
     }
     // HINT: Don't revert the edge-splitting as following transformation may
     // also need to split these critical edges.
-    return !CriticalEdgePred.empty();
+    return !CriticalEdgePredSplit.empty();
   }
 
   // Okay, we can eliminate this load by inserting a reload in the predecessor
   // and using PHI construction to get the value in the other predecessors, do
   // it.
   LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOAD: " << *Load << '\n');
   LLVM_DEBUG(if (!NewInsts.empty()) dbgs() << "INSERTED " << NewInsts.size()
                                            << " INSTS: " << *NewInsts.back()
                                            << '\n');
 
   // Assign value numbers to the new instructions.
   for (Instruction *I : NewInsts) {
     // Instructions that have been inserted in predecessor(s) to materialize
     // the load address do not retain their original debug locations. Doing
     // so could lead to confusing (but correct) source attributions.
     I->updateLocationAfterHoist();
 
     // FIXME: We really _ought_ to insert these value numbers into their
     // parent's availability map.  However, in doing so, we risk getting into
     // ordering issues.  If a block hasn't been processed yet, we would be
     // marking a value as AVAIL-IN, which isn't what we intend.
     VN.lookupOrAdd(I);
   }
 
-  eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, PredLoads);
+  eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, PredLoads,
+                                  &CriticalEdgePredAndLoad);
   ++NumPRELoad;
   return true;
 }
 
 bool GVNPass::performLoopLoadPRE(LoadInst *Load,
                                  AvailValInBlkVect &ValuesPerBlock,
                                  UnavailBlkVect &UnavailableBlocks) {
   if (!LI)
if (LoadPtr->canBeFreed())
     return false;
 
   // TODO: Support critical edge splitting if blocker has more than 1 successor.
   MapVector<BasicBlock *, Value *> AvailableLoads;
   AvailableLoads[LoopBlock] = LoadPtr;
   AvailableLoads[Preheader] = LoadPtr;
 
   LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOOP LOAD: " << *Load << '\n');
-  eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, AvailableLoads);
+  eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, AvailableLoads,
+                                  /*CriticalEdgePredAndLoad*/ nullptr);
   ++NumPRELoopLoad;
   return true;
 }
 
 static void reportLoadElim(LoadInst *Load, Value *AvailableValue,
                            OptimizationRemarkEmitter *ORE) {
   using namespace ore;
 

llvm/test/Transforms/GVN/PRE/2011-06-01-NonLocalMemdepMiscompile.ll

 
 ; CHECK-LABEL: bb6:
 ; CHECK:         br i1 undef, label %bb15split, label %bb10
 
 ; CHECK-LABEL: bb15split:                                        ; preds = %bb6
 ; CHECK-NEXT:    br label %bb15
 
 ; CHECK-LABEL: bb15:
-; CHECK:         %tmp17 = phi i8 [ %tmp8, %bb15split ], [ %tmp17.pre, %bb1.bb15_crit_edge ]
+; CHECK:         %tmp17 = phi i8 [ %tmp12.pre3, %bb15split ], [ %tmp17.pre, %bb1.bb15_crit_edge ]
 
 bb19:                                             ; preds = %bb15
   ret i1 %tmp18
 }
 
 declare void @isalnum() nounwind inlinehint ssp

llvm/test/Transforms/GVN/PRE/2017-06-28-pre-load-dbgloc.ll

 ; This test checks if debug loc is propagated to load/store created by GVN/Instcombine.
-; RUN: opt < %s -passes=gvn -S | FileCheck %s --check-prefixes=ALL,GVN
-; RUN: opt < %s -passes=gvn,instcombine -S | FileCheck %s --check-prefixes=ALL,INSTCOMBINE
+; RUN: opt < %s -passes=gvn -S | FileCheck %s --check-prefixes=ALL
+; RUN: opt < %s -passes=gvn,instcombine -S | FileCheck %s --check-prefixes=ALL
 
 ; struct node {
 ;  int  *v;
 ; struct desc *descs;
 ; };
 
 ; struct desc {
 ;  struct node *node;

 
 %struct.desc = type { ptr }
 %struct.node = type { ptr, ptr }
 
 define i32 @test(ptr readonly %desc) local_unnamed_addr #0 !dbg !4 {
 entry:
   %tobool = icmp eq ptr %desc, null
   br i1 %tobool, label %cond.end, label %cond.false, !dbg !9
-; ALL: br i1 %tobool, label %entry.cond.end_crit_edge, label %cond.false, !dbg [[LOC_15_6:![0-9]+]]
-; ALL: entry.cond.end_crit_edge:
-; GVN: %.pre = load ptr, ptr null, align 8, !dbg [[LOC_16_13:![0-9]+]]
-; INSTCOMBINE:store ptr poison, ptr null, align 4294967296, !dbg [[LOC_16_13:![0-9]+]]
+; ALL: %.pre = load ptr, ptr %desc, align 8, !dbg [[LOC_16_13:![0-9]+]]
+; ALL: br i1 %tobool, label %cond.end, label %cond.false, !dbg [[LOC_15_6:![0-9]+]]
+; ALL: cond.false:
 
 cond.false:
   %0 = load ptr, ptr %desc, align 8, !dbg !11
   %1 = load ptr, ptr %0, align 8
   br label %cond.end, !dbg !9
 
 cond.end:
   %2 = phi ptr [ %1, %cond.false ], [ null, %entry ], !dbg !9

 !6 = !{!7}
 !7 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
 !8 = !{}
 !9 = !DILocation(line: 15, column: 6, scope: !4)
 !10 = !DILocation(line: 16, column: 13, scope: !4)
 !11 = !DILocation(line: 15, column: 34, scope: !4)
 
 ;ALL: [[SCOPE:![0-9]+]] = distinct  !DISubprogram(name: "test",{{.*}}
-;ALL: [[LOC_15_6]] = !DILocation(line: 15, column: 6, scope: [[SCOPE]])
 ;ALL: [[LOC_16_13]] = !DILocation(line: 16, column: 13, scope: [[SCOPE]])
+;ALL: [[LOC_15_6]] = !DILocation(line: 15, column: 6, scope: [[SCOPE]])

llvm/test/Transforms/GVN/PRE/2018-06-08-pre-load-dbgloc-no-null-opt.ll

 
 %struct.desc = type { ptr }
 %struct.node = type { ptr, ptr }
 
 define i32 @test_no_null_opt(ptr readonly %desc) local_unnamed_addr #0 !dbg !4 {
 entry:
   %tobool = icmp eq ptr %desc, null
   br i1 %tobool, label %cond.end, label %cond.false, !dbg !9
-; ALL: br i1 %tobool, label %entry.cond.end_crit_edge, label %cond.false, !dbg [[LOC_15_6:![0-9]+]]
-; ALL: entry.cond.end_crit_edge:
-; ALL: load ptr, ptr null, align {{[0-9]+}}, !dbg [[LOC_16_13:![0-9]+]]
+; ALL: %.pre = load ptr, ptr %desc, align 8, !dbg [[LOC_16_13:![0-9]+]]
+; ALL: br i1 %tobool, label %cond.end, label %cond.false, !dbg [[LOC_15_6:![0-9]+]]
+; ALL: cond.false:
 
 cond.false:
   %0 = load ptr, ptr %desc, align 8, !dbg !11
   %1 = load ptr, ptr %0, align 8
   br label %cond.end, !dbg !9
 
 cond.end:
-; ALL: phi ptr [ %0, %cond.false ], [ %.pre, %entry.cond.end_crit_edge ]
-; ALL: phi ptr [ %1, %cond.false ], [ null, %entry.cond.end_crit_edge ]
+; ALL: phi ptr [ %0, %cond.false ], [ null, %entry ]
 
   %2 = phi ptr [ %1, %cond.false ], [ null, %entry ], !dbg !9
   %3 = load ptr, ptr %desc, align 8, !dbg !10
   %descs = getelementptr inbounds %struct.node, ptr %3, i64 0, i32 1
   %4 = load ptr, ptr %descs, align 8
   %call = tail call i32 @bar(ptr %2, ptr %4)
   ret i32 %call
 }

 !6 = !{!7}
 !7 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
 !8 = !{}
 !9 = !DILocation(line: 15, column: 6, scope: !4)
 !10 = !DILocation(line: 16, column: 13, scope: !4)
 !11 = !DILocation(line: 15, column: 34, scope: !4)
 
 ;ALL: [[SCOPE:![0-9]+]] = distinct  !DISubprogram(name: "test_no_null_opt",{{.*}}
-;ALL: [[LOC_15_6]] = !DILocation(line: 15, column: 6, scope: [[SCOPE]])
 ;ALL: [[LOC_16_13]] = !DILocation(line: 16, column: 13, scope: [[SCOPE]])
+;ALL: [[LOC_15_6]] = !DILocation(line: 15, column: 6, scope: [[SCOPE]])

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

+; RUN: opt < %s -passes=gvn -gvn-max-num-insns=22 -S | FileCheck %s
+
+; Debug information should not impact gvn. The following two functions have same
+; code except debug information. They should generate same optimized
+; instructions.
+
+%struct.a = type { i16 }
+
+@f = local_unnamed_addr global i16 0, align 1
+@m = local_unnamed_addr global ptr null, align 1
+@h = global %struct.a zeroinitializer, align 1
+
+define void @withdbg() {
+; CHECK-LABEL: @withdbg
+; CHECK:         [[PRE_PRE1:%.*]] = load i16, ptr @f, align 1
+; CHECK-NEXT:    [[PRE_PRE2:%.*]] = load ptr, ptr @m, align 1
+; CHECK-NEXT:    br i1 true, label %[[BLOCK1:.*]], label %[[BLOCK2:.*]]
+; CHECK:       [[BLOCK1]]:
+; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[PRE_PRE1]] to i32
+; CHECK-NEXT:    store i32 [[CONV]], ptr [[PRE_PRE2]], align 1
+
+entry:
+  %agg.tmp.ensured.sroa.0.i = alloca i16, align 1
+  br i1 icmp ne (ptr  @withdbg, ptr  null), label %lor.end, label %lor.rhs
+
+lor.rhs:                                          ; preds = %entry
+  call void @llvm.dbg.declare(metadata ptr undef, metadata !46, metadata !DIExpression()), !dbg !40
+  call void @llvm.dbg.declare(metadata ptr undef, metadata !47, metadata !DIExpression()), !dbg !40
+  call void @llvm.dbg.declare(metadata ptr undef, metadata !48, metadata !DIExpression()), !dbg !40
+  call void @llvm.dbg.declare(metadata ptr undef, metadata !49, metadata !DIExpression()), !dbg !40
+  call void @llvm.dbg.declare(metadata ptr undef, metadata !50, metadata !DIExpression()), !dbg !40
+  %agg.tmp.ensured.sroa.0.0.copyload.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.1.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.1.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.2.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.2.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.3.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.3.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.4.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.4.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.5.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.5.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.6.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.6.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.7.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.7.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.8.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.8.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %fvalue = load i16, ptr @f, align 1
+  %mvalue = load ptr, ptr @m, align 1
+  br label %lor.end
+
+lor.end:                                          ; preds = %lor.rhs, %entry
+  %tmp11 = load i16, ptr @f, align 1
+  %conv.i.i6 = sext i16 %tmp11 to i32
+  %tmp12 = load ptr, ptr @m, align 1
+  store i32 %conv.i.i6, ptr %tmp12, align 1
+  ret void
+}
+
+define void @lessdbg() {
+; CHECK-LABEL: @lessdbg
+; CHECK:         [[PRE_PRE1:%.*]] = load i16, ptr @f, align 1
+; CHECK-NEXT:    [[PRE_PRE2:%.*]] = load ptr, ptr @m, align 1
+; CHECK-NEXT:    br i1 true, label %[[BLOCK1:.*]], label %[[BLOCK2:.*]]
+; CHECK:       [[BLOCK1]]:
+; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[PRE_PRE1]] to i32
+; CHECK-NEXT:    store i32 [[CONV]], ptr [[PRE_PRE2]], align 1
+
+entry:
+  %agg.tmp.ensured.sroa.0.i = alloca i16, align 1
+  br i1 icmp ne (ptr  @lessdbg, ptr  null), label %lor.end, label %lor.rhs
+
+lor.rhs:                                          ; preds = %entry
+  %agg.tmp.ensured.sroa.0.0.copyload.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.1.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.1.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.2.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.2.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.3.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.3.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.4.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.4.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.5.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.5.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.6.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.6.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.7.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.7.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %agg.tmp.ensured.sroa.0.0.copyload.8.i = load volatile i16, ptr @h, align 1
+  store i16 %agg.tmp.ensured.sroa.0.0.copyload.8.i, ptr %agg.tmp.ensured.sroa.0.i, align 1
+  %fvalue = load i16, ptr @f, align 1
+  %mvalue = load ptr, ptr @m, align 1
+  br label %lor.end
+
+lor.end:                                          ; preds = %lor.rhs, %entry
+  %tmp11 = load i16, ptr @f, align 1
+  %conv.i.i6 = sext i16 %tmp11 to i32
+  %tmp12 = load ptr, ptr @m, align 1
+  store i32 %conv.i.i6, ptr %tmp12, align 1
+  ret void
+}
+
+declare void @llvm.dbg.declare(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!35, !36}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C11, file: !1, producer: "clang version 17.0.0.prerel", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "bbi-78272.c", directory: "/tmp")
+!5 = !DIBasicType(name: "int", size: 16, encoding: DW_ATE_signed)
+
+!35 = !{i32 7, !"Dwarf Version", i32 4}
+!36 = !{i32 2, !"Debug Info Version", i32 3}
+!40 = !DILocation(line: 15, column: 7, scope: !41)
+!41 = distinct !DISubprogram(name: "x", scope: !1, file: !1, line: 14, type: !42, scopeLine: 14, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagLocalToUnit | DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !45)
+!42 = !DISubroutineType(types: !43)
+!43 = !{!5}
+!45 = !{!46, !47, !48, !49, !50}
+!46 = !DILocalVariable(name: "t", scope: !41, file: !1, line: 15, type: !5)
+!47 = !DILocalVariable(name: "c", scope: !41, file: !1, line: 15, type: !5)
+!48 = !DILocalVariable(name: "v", scope: !41, file: !1, line: 15, type: !5)
+!49 = !DILocalVariable(name: "d", scope: !41, file: !1, line: 15, type: !5)
+!50 = !DILocalVariable(name: "u", scope: !41, file: !1, line: 16, type: !5)

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

 ; Same as test13, but %x here is dereferenceable. A pointer that is
 ; dereferenceable can be loaded from speculatively without a risk of trapping.
 ; Since it is OK to speculate, PRE is allowed.
 
 define i32 @test15(ptr noalias nocapture readonly dereferenceable(8) align 4 %x, ptr noalias nocapture %r, i32 %a) nofree nosync {
 ; CHECK-LABEL: @test15(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[A:%.*]], 0
-; CHECK-NEXT:    br i1 [[TOBOOL]], label [[ENTRY_IF_END_CRIT_EDGE:%.*]], label [[IF_THEN:%.*]]
-; CHECK:       entry.if.end_crit_edge:
 ; CHECK-NEXT:    [[VV_PRE:%.*]] = load i32, ptr [[X:%.*]], align 4
-; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    [[UU:%.*]] = load i32, ptr [[X]], align 4
-; CHECK-NEXT:    store i32 [[UU]], ptr [[R:%.*]], align 4
+; CHECK-NEXT:    store i32 [[VV_PRE]], ptr [[R:%.*]], align 4
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[VV:%.*]] = phi i32 [ [[VV_PRE]], [[ENTRY_IF_END_CRIT_EDGE]] ], [ [[UU]], [[IF_THEN]] ]
 ; CHECK-NEXT:    call void @f()
-; CHECK-NEXT:    ret i32 [[VV]]
+; CHECK-NEXT:    ret i32 [[VV_PRE]]
 ;
 
 entry:
   %tobool = icmp eq i32 %a, 0
   br i1 %tobool, label %if.end, label %if.then
 
 
 if.then:

 ; Same as test14, but %x here is dereferenceable. A pointer that is
 ; dereferenceable can be loaded from speculatively without a risk of trapping.
 ; Since it is OK to speculate, PRE is allowed.
 
 define i32 @test16(ptr noalias nocapture readonly dereferenceable(8) align 4 %x, ptr noalias nocapture %r, i32 %a) nofree nosync {
 ; CHECK-LABEL: @test16(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[A:%.*]], 0
-; CHECK-NEXT:    br i1 [[TOBOOL]], label [[ENTRY_IF_END_CRIT_EDGE:%.*]], label [[IF_THEN:%.*]]
-; CHECK:       entry.if.end_crit_edge:
 ; CHECK-NEXT:    [[VV_PRE:%.*]] = load i32, ptr [[X:%.*]], align 4
-; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    [[UU:%.*]] = load i32, ptr [[X]], align 4
-; CHECK-NEXT:    store i32 [[UU]], ptr [[R:%.*]], align 4
+; CHECK-NEXT:    store i32 [[VV_PRE]], ptr [[R:%.*]], align 4
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[VV:%.*]] = phi i32 [ [[VV_PRE]], [[ENTRY_IF_END_CRIT_EDGE]] ], [ [[UU]], [[IF_THEN]] ]
 ; CHECK-NEXT:    call void @f()
-; CHECK-NEXT:    ret i32 [[VV]]
+; CHECK-NEXT:    ret i32 [[VV_PRE]]
 ;
 
 entry:
   %tobool = icmp eq i32 %a, 0
   br i1 %tobool, label %if.end, label %if.then
 
 
 if.then:

 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[COND2:%.*]] = icmp sgt i64 [[V1]], 100
 ; CHECK-NEXT:    br i1 [[COND2]], label [[BB100:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[V2:%.*]] = add nsw i64 [[V1]], 1
 ; CHECK-NEXT:    store i64 [[V2]], ptr [[P1]], align 8
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    [[V3:%.*]] = load i64, ptr [[P1]], align 8
+; CHECK-NEXT:    [[V3:%.*]] = phi i64 [ [[V3_PRE:%.*]], [[BB200]] ], [ [[V3_PRE1:%.*]], [[BB100]] ], [ [[V2]], [[BB2]] ]
 ; CHECK-NEXT:    store i64 [[V3]], ptr [[P2:%.*]], align 8
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb100:
 ; CHECK-NEXT:    [[COND3:%.*]] = call i1 @foo()
+; CHECK-NEXT:    [[V3_PRE1]] = load i64, ptr [[P1]], align 8
 ; CHECK-NEXT:    br i1 [[COND3]], label [[BB3]], label [[BB101:%.*]]
 ; CHECK:       bb101:
-; CHECK-NEXT:    [[V4:%.*]] = load i64, ptr [[P1]], align 8
-; CHECK-NEXT:    store i64 [[V4]], ptr [[P3:%.*]], align 8
+; CHECK-NEXT:    store i64 [[V3_PRE1]], ptr [[P3:%.*]], align 8
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb200:
 ; CHECK-NEXT:    [[COND4:%.*]] = call i1 @bar()
+; CHECK-NEXT:    [[V3_PRE]] = load i64, ptr [[P1]], align 8
 ; CHECK-NEXT:    br i1 [[COND4]], label [[BB3]], label [[BB201:%.*]]
 ; CHECK:       bb201:
-; CHECK-NEXT:    [[V5:%.*]] = load i64, ptr [[P1]], align 8
-; CHECK-NEXT:    store i64 [[V5]], ptr [[P4:%.*]], align 8
+; CHECK-NEXT:    store i64 [[V3_PRE]], ptr [[P4:%.*]], align 8
 ; CHECK-NEXT:    ret void
 ;
 {
 entry:
   %v1 = load i64, ptr %p1, align 8
   %cond1 = icmp sgt i64 %v1, 200
   br i1 %cond1, label %bb200, label %bb1
 
bb200:
   %cond4 = call i1 @bar()
   br i1 %cond4, label %bb3, label %bb201
 
 bb201:
   %v5 = load i64, ptr %p1, align 8
   store i64 %v5, ptr %p4, align 8
   ret void
 }
+
+; The output value from %if.then block is %dec, not loaded %v1.
+; So ValuesPerBlock[%if.then] should not be replaced when the load instruction
+; is moved to %entry.
+define void @test18(i1 %cond, ptr %p1, ptr %p2) {
+; CHECK-LABEL: @test18(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[V2_PRE:%.*]] = load i16, ptr [[P1:%.*]], align 2
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[DEC:%.*]] = add i16 [[V2_PRE]], -1
+; CHECK-NEXT:    store i16 [[DEC]], ptr [[P1]], align 2
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[V2:%.*]] = phi i16 [ [[DEC]], [[IF_THEN]] ], [ [[V2_PRE]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    store i16 [[V2]], ptr [[P2:%.*]], align 2
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %cond, label %if.end, label %if.then
+
+if.then:
+  %v1 = load i16, ptr %p1
+  %dec = add i16 %v1, -1
+  store i16 %dec, ptr %p1
+  br label %if.end
+
+if.end:
+  %v2 = load i16, ptr %p1
+  store i16 %v2, ptr %p2
+  ret void
+}
+
+; PRE of load instructions should not cross exception handling instructions.
+define void @test19(i1 %cond, ptr %p1, ptr %p2)
+; CHECK-LABEL: @test19(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[V2:%.*]] = load i64, ptr [[P2:%.*]], align 8
+; CHECK-NEXT:    [[ADD:%.*]] = add i64 [[V2]], 1
+; CHECK-NEXT:    store i64 [[ADD]], ptr [[P1:%.*]], align 8
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       else:
+; CHECK-NEXT:    invoke void @f()
+; CHECK-NEXT:    to label [[ELSE_END_CRIT_EDGE:%.*]] unwind label [[LPAD:%.*]]
+; CHECK:       else.end_crit_edge:
+; CHECK-NEXT:    [[V1_PRE:%.*]] = load i64, ptr [[P1]], align 8
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[V1:%.*]] = phi i64 [ [[V1_PRE]], [[ELSE_END_CRIT_EDGE]] ], [ [[ADD]], [[THEN]] ]
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V1]], 100
+; CHECK-NEXT:    store i64 [[AND]], ptr [[P2]], align 8
+; CHECK-NEXT:    ret void
+; CHECK:       lpad:
+; CHECK-NEXT:    [[LP:%.*]] = landingpad { ptr, i32 }
+; CHECK-NEXT:    cleanup
+; CHECK-NEXT:    [[V3:%.*]] = load i64, ptr [[P1]], align 8
+; CHECK-NEXT:    [[OR:%.*]] = or i64 [[V3]], 200
+; CHECK-NEXT:    store i64 [[OR]], ptr [[P1]], align 8
+; CHECK-NEXT:    resume { ptr, i32 } [[LP]]
+;
+  personality ptr @__CxxFrameHandler3 {
+entry:
+  br i1 %cond, label %then, label %else
+
+then:
+  %v2 = load i64, ptr %p2
+  %add = add i64 %v2, 1
+  store i64 %add, ptr %p1
+  br label %end
+
+else:
+  invoke void @f()
+  to label %end unwind label %lpad
+
+end:
+  %v1 = load i64, ptr %p1
+  %and = and i64 %v1, 100
+  store i64 %and, ptr %p2
+  ret void
+
+lpad:
+  %lp = landingpad { ptr, i32 }
+  cleanup
+  %v3 = load i64, ptr %p1
+  %or = or i64 %v3, 200
+  store i64 %or, ptr %p1
+  resume { ptr, i32 } %lp
+}
+
+; A predecessor BB has both successors to the same BB, for simplicity we don't
+; handle it, nothing should be changed.
+define void @test20(i1 %cond, i1 %cond2, ptr %p1, ptr %p2) {
+; CHECK-LABEL: @test20(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[V1:%.*]] = load i16, ptr [[P1:%.*]], align 2
+; CHECK-NEXT:    [[DEC:%.*]] = add i16 [[V1]], -1
+; CHECK-NEXT:    store i16 [[DEC]], ptr [[P1]], align 2
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[IF_END]], label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[V2:%.*]] = load i16, ptr [[P1]], align 2
+; CHECK-NEXT:    store i16 [[V2]], ptr [[P2:%.*]], align 2
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %cond, label %if.then, label %if.else
+
+if.then:
+  %v1 = load i16, ptr %p1
+  %dec = add i16 %v1, -1
+  store i16 %dec, ptr %p1
+  br label %if.end
+
+if.else:
+  br i1 %cond2, label %if.end, label %if.end
+
+if.end:
+  %v2 = load i16, ptr %p1
+  store i16 %v2, ptr %p2
+  ret void
+}
+
+; More edges from the same BB to LoadBB. Don't change anything.
+define void @test21(i1 %cond, i32 %code, ptr %p1, ptr %p2) {
+; CHECK-LABEL: @test21(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[V1:%.*]] = load i16, ptr [[P1:%.*]], align 2
+; CHECK-NEXT:    [[DEC:%.*]] = add i16 [[V1]], -1
+; CHECK-NEXT:    store i16 [[DEC]], ptr [[P1]], align 2
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    switch i32 [[CODE:%.*]], label [[IF_END]] [
+; CHECK-NEXT:    i32 1, label [[IF_END]]
+; CHECK-NEXT:    i32 2, label [[IF_END]]
+; CHECK-NEXT:    i32 3, label [[IF_END]]
+; CHECK-NEXT:    ]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[V2:%.*]] = load i16, ptr [[P1]], align 2
+; CHECK-NEXT:    store i16 [[V2]], ptr [[P2:%.*]], align 2
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %cond, label %if.then, label %if.else
+
+if.then:
+  %v1 = load i16, ptr %p1
+  %dec = add i16 %v1, -1
+  store i16 %dec, ptr %p1
+  br label %if.end
+
+if.else:
+  switch i32 %code, label %if.end [
+  i32 1, label %if.end
+  i32 2, label %if.end
+  i32 3, label %if.end
+  ]
+
+if.end:
+  %v2 = load i16, ptr %p1
+  store i16 %v2, ptr %p2
+  ret void
+}
+
+; Call to function @maybethrow may cause exception, so the load of %v3 can't
+; be hoisted to block %if.else.
+define void @test22(i1 %cond, ptr %p1, ptr %p2) {
+; CHECK-LABEL: @test22(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[V1:%.*]] = load i64, ptr [[P1:%.*]], align 8
+; CHECK-NEXT:    [[DEC:%.*]] = add i64 [[V1]], -1
+; CHECK-NEXT:    store i64 [[DEC]], ptr [[P1]], align 8
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[V2:%.*]] = phi i64 [ [[V2_PRE:%.*]], [[IF_ELSE_IF_END_CRIT_EDGE:%.*]] ], [ [[DEC]], [[IF_THEN]] ]
+; CHECK-NEXT:    store i64 [[V2]], ptr [[P2:%.*]], align 8
+; CHECK-NEXT:    ret void
+; CHECK:       if.else:
+; CHECK-NEXT:    [[COND2:%.*]] = call i1 @foo()
+; CHECK-NEXT:    br i1 [[COND2]], label [[IF_ELSE_IF_END_CRIT_EDGE]], label [[EXIT:%.*]]
+; CHECK:       if.else.if.end_crit_edge:
+; CHECK-NEXT:    [[V2_PRE]] = load i64, ptr [[P1]], align 8
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[_:%.*]] = call i1 @maybethrow()
+; CHECK-NEXT:    [[V3:%.*]] = load i64, ptr [[P1]], align 8
+; CHECK-NEXT:    store i64 [[V3]], ptr [[P2]], align 8
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %cond, label %if.then, label %if.else
+
+if.then:
+  %v1 = load i64, ptr %p1
+  %dec = add i64 %v1, -1
+  store i64 %dec, ptr %p1
+  br label %if.end
+
+if.end:
+  %v2 = load i64, ptr %p1
+  store i64 %v2, ptr %p2
+  ret void
+
+if.else:
+  %cond2 = call i1 @foo()
+  br i1 %cond2, label %if.end, label %exit
+
+exit:
+  %_ = call i1 @maybethrow()
+  %v3 = load i64, ptr %p1
+  store i64 %v3, ptr %p2
+  ret void
+}
+
+declare void @maybethrow() readnone

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

 exit:
   ret i32 %add
 }
 
 ; Does cross block PRE work with volatiles?
 define i32 @test7(i1 %c, ptr noalias nocapture %p, ptr noalias nocapture %q) {
 ; CHECK-LABEL: @test7(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 [[C:%.*]], label [[ENTRY_HEADER_CRIT_EDGE:%.*]], label [[SKIP:%.*]]
-; CHECK:       entry.header_crit_edge:
 ; CHECK-NEXT:    [[Y_PRE:%.*]] = load i32, ptr [[P:%.*]], align 4
-; CHECK-NEXT:    br label [[HEADER:%.*]]
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[HEADER:%.*]], label [[SKIP:%.*]]
 ; CHECK:       skip:
-; CHECK-NEXT:    [[Y1:%.*]] = load i32, ptr [[P]], align 4
-; CHECK-NEXT:    call void @use(i32 [[Y1]])
+; CHECK-NEXT:    call void @use(i32 [[Y_PRE]])
 ; CHECK-NEXT:    br label [[HEADER]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[Y:%.*]] = phi i32 [ [[Y_PRE]], [[ENTRY_HEADER_CRIT_EDGE]] ], [ [[Y]], [[HEADER]] ], [ [[Y1]], [[SKIP]] ]
 ; CHECK-NEXT:    [[X:%.*]] = load volatile i32, ptr [[Q:%.*]], align 4
-; CHECK-NEXT:    [[ADD:%.*]] = sub i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = sub i32 [[Y_PRE]], [[X]]
 ; CHECK-NEXT:    [[CND:%.*]] = icmp eq i32 [[ADD]], 0
 ; CHECK-NEXT:    br i1 [[CND]], label [[EXIT:%.*]], label [[HEADER]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   br i1 %c, label %header, label %skip
 skip:

llvm/test/Transforms/GVN/condprop.ll

 ; that gep2 does not alias ptr1 on that path (as it would require that
 ; ptr2==ptr2+2), so we can perform PRE of the load.
 define i32 @test13(ptr %ptr1, ptr %ptr2) {
 ; CHECK-LABEL: @test13(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr i32, ptr [[PTR2:%.*]], i32 1
 ; CHECK-NEXT:    [[GEP2:%.*]] = getelementptr i32, ptr [[PTR2]], i32 2
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq ptr [[PTR1:%.*]], [[PTR2]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[ENTRY_END_CRIT_EDGE:%.*]]
-; CHECK:       entry.end_crit_edge:
 ; CHECK-NEXT:    [[VAL2_PRE:%.*]] = load i32, ptr [[GEP2]], align 4
-; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
 ; CHECK:       if:
-; CHECK-NEXT:    [[VAL1:%.*]] = load i32, ptr [[GEP2]], align 4
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[VAL2:%.*]] = phi i32 [ [[VAL1]], [[IF]] ], [ [[VAL2_PRE]], [[ENTRY_END_CRIT_EDGE]] ]
-; CHECK-NEXT:    [[PHI1:%.*]] = phi ptr [ [[PTR2]], [[IF]] ], [ [[GEP1]], [[ENTRY_END_CRIT_EDGE]] ]
-; CHECK-NEXT:    [[PHI2:%.*]] = phi i32 [ [[VAL1]], [[IF]] ], [ 0, [[ENTRY_END_CRIT_EDGE]] ]
+; CHECK-NEXT:    [[PHI1:%.*]] = phi ptr [ [[PTR2]], [[IF]] ], [ [[GEP1]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[PHI2:%.*]] = phi i32 [ [[VAL2_PRE]], [[IF]] ], [ 0, [[ENTRY]] ]
 ; CHECK-NEXT:    store i32 0, ptr [[PHI1]], align 4
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[PHI2]], [[VAL2]]
+; CHECK-NEXT:    [[RET:%.*]] = add i32 [[PHI2]], [[VAL2_PRE]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
 entry:
   %gep1 = getelementptr i32, ptr %ptr2, i32 1
   %gep2 = getelementptr i32, ptr %ptr2, i32 2
   %cmp = icmp eq ptr %ptr1, %ptr2
   br i1 %cmp, label %if, label %end