[GVN] Support chain of phi nodes in exit blocks.

[fhahn]

Summary

This patch extends to logic added in D118143 to allow chains of phis
from the lcssa phi to the using load instruction. The intermediate phis
must be in blocks only containing the phi and an unconditional branch.
The blocks must be connected directly. This ensures that the load
instruction executes if the loop exit executes.

Such chains of phi nodes are common for rotated loops and is required to
be able to handle cases such as (https://clang.godbolt.org/z/6czGzzqbs)

#include <vector>
#include <algorithm>

int foo(const std::vector<int> &V) {
   return *std::min_element(V.begin(), V.end());
}

Depends on D118143.

[fhahn]

add missing ;

[fhahn]

A major rewrite/update following @reames' suggestion in D118143 as extension to the available value analysis. This patch now tries to find an existing value-select that can be used instead of loading from a pointer-select. The first version is intentionally kept quite restrictive and can be extended through follow-ups.

Together with D118143, this enables vectorization for common code like std::min_element, yielding substantial speedups for code that uses it for non-tiny numbers of elements.

[reames]

Really not a fan here.

I think what we need to do is recognize the address clobber being from a select, and then perform both sides of the memory dependency "as if" we had two loads at the point of the select. Doing that would let this work generically.

I'd mentioned this scheme in the prior patch, but I was sorta okay with the special casing there. I'm really not on board with the extension made here.

Note that you don't need to go all the way to the fully general scheme. You could fork the analysis only once and handle only the case where there's a single select on the address. You do need to be consistent for both within block and cross block, but that's a different issue.

As an aside, I think this whole problem gets much easier if we can use the MSSA interfaces. I know there's someone trying to switch legacy GVN to MSSA. It might be worth trying to drive that through, and then revisiting.

[fhahn]

In D118144#3285181, @reames wrote:

Really not a fan here.

I think what we need to do is recognize the address clobber being from a select, and then perform both sides of the memory dependency "as if" we had two loads at the point of the select. Doing that would let this work generically.

That's a fair point, this patch is indeed very specific! Let me take a look at what some kind of 'fork-analysis' would take.

[lebedev.ri]

This review may be stuck/dead, consider abandoning if no longer relevant.
Removing myself as reviewer in attempt to clean dashboard.

llvm/lib/Transforms/Scalar/GVN.cpp

for (Value *U : Ptr->users()) {
       if (LI && LI->getParent() == Sel->getParent() && DT.dominates(LI, Sel))
         return LI;
     }
     return nullptr;
   };
 
   auto *L1 = FindDominatingLoad(Sel->getOperand(1));
   auto *L2 = FindDominatingLoad(Sel->getOperand(2));
+
+  // Try to find an existing value-select, which provides the same value as
+  // loading from the pointer-select Sel.
+  if (L1) {
+    SelectInst *ValueSel = nullptr;
+    for (User *U : L1->users()) {
+      ValueSel = dyn_cast<SelectInst>(U);
+      if (ValueSel && ValueSel->getOperand(0) == Sel->getOperand(0) &&
+          ValueSel->getOperand(1) == L1)
+        break;
+      ValueSel = nullptr;
+    }
+    if (ValueSel && DT.dominates(ValueSel, Sel)) {
+      auto *Phi0 = dyn_cast<PHINode>(ValueSel->getOperand(2));
+      auto *Phi1 = dyn_cast<PHINode>(Sel->getOperand(2));
+      if (Phi0 && Phi1 && Phi0->getParent() == Phi1->getParent() &&
+          all_of(Phi0->blocks(), [Phi0, Phi1, Sel, ValueSel](BasicBlock *BB) {
+            if (Phi0->getIncomingValueForBlock(BB) == ValueSel &&
+                Phi1->getIncomingValueForBlock(BB) == Sel)
+              return true;
+
+            auto *IncPtr = Phi1->getIncomingValueForBlock(BB);
+            auto *Load = dyn_cast<LoadInst>(Phi0->getIncomingValueForBlock(BB));
+            if (Load && Load->getPointerOperand() == IncPtr) {
+              return Load->getParent()->getSingleSuccessor() ==
+                         Sel->getParent() &&
+                     Load->getNextNode() == Load->getParent()->getTerminator();
+            }
+            return false;
+          })) {
+        return AvailableValueInBlock::get(Sel->getParent(), ValueSel);
+      }
+    }
+  }
   if (!L1 || !L2)
     return None;
-
   return AvailableValueInBlock::getSelect(Sel->getParent(),
                                           cast<SelectInst>(Address));
 }
 void GVNPass::AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
                                       AvailValInBlkVect &ValuesPerBlock,
                                       UnavailBlkVect &UnavailableBlocks) {
   // Filter out useless results (non-locals, etc).  Keep track of the blocks
   // where we have a value available in repl, also keep track of whether we see
bool GVNPass::processNonLocalLoad(LoadInst *Load) {
   // dependencies, this load isn't worth worrying about.  Optimizing
   // it will be too expensive.
   unsigned NumDeps = Deps.size();
   if (NumDeps > MaxNumDeps)
     return false;
 
   // If we had a phi translation failure, we'll have a single entry which is a
   // clobber in the current block.  Reject this early.
-  if (NumDeps == 1 &&
-      !Deps[0].getResult().isDef() && !Deps[0].getResult().isClobber()) {
+  if (NumDeps == 1 && !Deps[0].getResult().isDef() &&
+      !Deps[0].getResult().isClobber() &&
+      !tryToConvertLoadOfPtrSelect(Deps[0].getBB(), Deps[0].getAddress(),
+                                   getDominatorTree())) {
     LLVM_DEBUG(dbgs() << "GVN: non-local load "; Load->printAsOperand(dbgs());
                dbgs() << " has unknown dependencies\n";);
     return false;
   }
 
   bool Changed = false;
   // If this load follows a GEP, see if we can PRE the indices before analyzing.
   if (GetElementPtrInst *GEP =

llvm/test/Transforms/GVN/PRE/pre-loop-load-through-select.ll

 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV]], align 4
 ; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
 ; CHECK-NEXT:    [[TMP0]] = select i1 [[CMP_I_I_I]], i32 [[L_1]], i32 [[L_2]]
 ; CHECK-NEXT:    [[MIN_SELECT]] = select i1 [[CMP_I_I_I]], i32* [[PTR_IV]], i32* [[MIN_PTR]]
 ; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, i32* [[PTR_IV]], i64 1
 ; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = load i32, i32* [[MIN_SELECT]], align 4
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   %start.ptr = getelementptr inbounds i32, i32* %ptr, i64 1
   br label %loop
 
 loop:
   %ptr.iv = phi i32* [ %start.ptr, %entry ], [ %ptr.iv.next, %loop ]
   %min.ptr = phi i32* [ %ptr, %entry ], [ %min.select, %loop ]

 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV]], align 4
 ; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
 ; CHECK-NEXT:    [[TMP0]] = select i1 [[CMP_I_I_I]], i32 [[L_1]], i32 [[L_2]]
 ; CHECK-NEXT:    [[MIN_SELECT]] = select i1 [[CMP_I_I_I]], i32* [[PTR_IV]], i32* [[MIN_PTR]]
 ; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, i32* [[PTR_IV]], i64 1
 ; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = load i32, i32* [[MIN_SELECT]], align 4
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   %start.ptr = getelementptr inbounds i32, i32* %ptr, i64 1
   br label %loop
 
 loop:
   %ptr.iv = phi i32* [ %start.ptr, %entry ], [ %ptr.iv.next, %loop ]
   %min.ptr = phi i32* [ %ptr, %entry ], [ %min.select, %loop ]

 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV]], align 4
 ; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
 ; CHECK-NEXT:    [[TMP0]] = select i1 [[CMP_I_I_I]], i32 [[L_1]], i32 [[L_2]]
 ; CHECK-NEXT:    [[MIN_SELECT]] = select i1 [[CMP_I_I_I]], i32* [[PTR_IV]], i32* [[MIN_PTR]]
 ; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, i32* [[PTR_IV]], i64 1
 ; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = load i32, i32* [[MIN_SELECT]], align 4
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   br label %loop
 
 loop:
   %ptr.iv = phi i32* [ %A, %entry ], [ %ptr.iv.next, %loop ]
   %min.ptr = phi i32* [ %B, %entry ], [ %min.select, %loop ]
   %l.1 = load i32, i32* %ptr.iv, align 4

 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV]], align 4
 ; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
 ; CHECK-NEXT:    [[TMP0]] = select i1 [[CMP_I_I_I]], i32 [[L_1]], i32 [[L_2]]
 ; CHECK-NEXT:    [[MIN_SELECT]] = select i1 [[CMP_I_I_I]], i32* [[PTR_IV]], i32* [[MIN_PTR]]
 ; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, i32* [[PTR_IV]], i64 1
 ; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = load i32, i32* [[MIN_SELECT]], align 4
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   %start.ptr = getelementptr inbounds i32, i32* %ptr, i64 1
   br label %loop
 
 loop:
   %ptr.iv = phi i32* [ %start.ptr, %entry ], [ %ptr.iv.next, %loop ]
   %min.ptr = phi i32* [ %ptr, %entry ], [ %min.select, %loop ]

 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV]], align 4
 ; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
 ; CHECK-NEXT:    [[TMP0]] = select i1 [[CMP_I_I_I]], i32 [[L_1]], i32 [[L_2]]
 ; CHECK-NEXT:    [[MIN_SELECT]] = select i1 [[CMP_I_I_I]], i32* [[PTR_IV]], i32* [[MIN_PTR]]
 ; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, i32* [[PTR_IV]], i64 1
 ; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = load i32, i32* [[MIN_SELECT]], align 4
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   %start.ptr = getelementptr inbounds i32, i32* %ptr, i64 1
   br label %loop
 
 loop:
   %ptr.iv = phi i32* [ %start.ptr, %entry ], [ %ptr.iv.next, %loop ]
   %min.ptr = phi i32* [ %ptr, %entry ], [ %min.select, %loop ]
exit:
   %res = load i32, i32* %min.select, align 4
   ret i32 %res
 }
 
 define i32 @test_pointer_phi_select_same_object_split_edge(i32* %ptr, i32* %end, i1 %c)  {
 ; CHECK-LABEL: @test_pointer_phi_select_same_object_split_edge(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[START_PTR:%.*]] = getelementptr inbounds i32, i32* [[PTR:%.*]], i64 1
-; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP_PREHEADER:%.*]]
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[ENTRY_EXIT_CRIT_EDGE:%.*]], label [[LOOP_PREHEADER:%.*]]
+; CHECK:       entry.exit_crit_edge:
+; CHECK-NEXT:    [[RES_PRE:%.*]] = load i32, i32* [[END:%.*]], align 4
+; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
 ; CHECK-NEXT:    [[L_2_PRE:%.*]] = load i32, i32* [[PTR]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[L_2:%.*]] = phi i32 [ [[TMP0:%.*]], [[LOOP]] ], [ [[L_2_PRE]], [[LOOP_PREHEADER]] ]
 ; CHECK-NEXT:    [[PTR_IV:%.*]] = phi i32* [ [[PTR_IV_NEXT:%.*]], [[LOOP]] ], [ [[START_PTR]], [[LOOP_PREHEADER]] ]
 ; CHECK-NEXT:    [[MIN_PTR:%.*]] = phi i32* [ [[MIN_SELECT:%.*]], [[LOOP]] ], [ [[PTR]], [[LOOP_PREHEADER]] ]
 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV]], align 4
 ; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
 ; CHECK-NEXT:    [[TMP0]] = select i1 [[CMP_I_I_I]], i32 [[L_1]], i32 [[L_2]]
 ; CHECK-NEXT:    [[MIN_SELECT]] = select i1 [[CMP_I_I_I]], i32* [[PTR_IV]], i32* [[MIN_PTR]]
 ; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, i32* [[PTR_IV]], i64 1
-; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END:%.*]]
+; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END]]
 ; CHECK-NEXT:    br i1 [[EC]], label [[LOOP_EXIT:%.*]], label [[LOOP]]
 ; CHECK:       loop.exit:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[LCSSA_PHI_2:%.*]] = phi i32* [ [[END]], [[ENTRY:%.*]] ], [ [[MIN_SELECT]], [[LOOP_EXIT]] ]
-; CHECK-NEXT:    [[RES:%.*]] = load i32, i32* [[LCSSA_PHI_2]], align 4
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES_PRE]], [[ENTRY_EXIT_CRIT_EDGE]] ], [ [[TMP0]], [[LOOP_EXIT]] ]
+; CHECK-NEXT:    [[LCSSA_PHI_2:%.*]] = phi i32* [ [[END]], [[ENTRY_EXIT_CRIT_EDGE]] ], [ [[MIN_SELECT]], [[LOOP_EXIT]] ]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
 entry:
   %start.ptr = getelementptr inbounds i32, i32* %ptr, i64 1
   br i1 %c, label %exit, label %loop
 
 loop:
   %ptr.iv = phi i32* [ %start.ptr, %entry ], [ %ptr.iv.next, %loop ]

 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[PTR_IV:%.*]] = phi i32* [ [[A:%.*]], [[ENTRY:%.*]] ], [ [[PTR_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[MIN_PTR:%.*]] = phi i32* [ [[B:%.*]], [[ENTRY]] ], [ [[MIN_SELECT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    call void @may_throw()
 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV]], align 4
 ; CHECK-NEXT:    [[L_2:%.*]] = load i32, i32* [[MIN_PTR]], align 4
 ; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
+; CHECK-NEXT:    [[TMP0:%.*]] = select i1 [[CMP_I_I_I]], i32 [[L_1]], i32 [[L_2]]
 ; CHECK-NEXT:    [[MIN_SELECT]] = select i1 [[CMP_I_I_I]], i32* [[PTR_IV]], i32* [[MIN_PTR]]
 ; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, i32* [[PTR_IV]], i64 1
 ; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = load i32, i32* [[MIN_SELECT]], align 4
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   br label %loop
 
 loop:
   %ptr.iv = phi i32* [ %A, %entry ], [ %ptr.iv.next, %loop ]
   %min.ptr = phi i32* [ %B, %entry ], [ %min.select, %loop ]
   call void @may_throw()

 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[PTR_IV:%.*]] = phi i32* [ [[A:%.*]], [[ENTRY:%.*]] ], [ [[PTR_IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[MIN_PTR:%.*]] = phi i32* [ [[B:%.*]], [[ENTRY]] ], [ [[MIN_SELECT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV]], align 4
 ; CHECK-NEXT:    call void @may_throw()
 ; CHECK-NEXT:    [[L_2:%.*]] = load i32, i32* [[MIN_PTR]], align 4
 ; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
+; CHECK-NEXT:    [[TMP0:%.*]] = select i1 [[CMP_I_I_I]], i32 [[L_1]], i32 [[L_2]]
 ; CHECK-NEXT:    [[MIN_SELECT]] = select i1 [[CMP_I_I_I]], i32* [[PTR_IV]], i32* [[MIN_PTR]]
 ; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, i32* [[PTR_IV]], i64 1
 ; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = load i32, i32* [[MIN_SELECT]], align 4
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   br label %loop
 
 loop:
   %ptr.iv = phi i32* [ %A, %entry ], [ %ptr.iv.next, %loop ]
   %min.ptr = phi i32* [ %B, %entry ], [ %min.select, %loop ]
   %l.1 = load i32, i32* %ptr.iv, align 4

 
 define i32 @test_pointer_phi_used_by_others_in_loop_1(i32* %ptr, i32* %end)  {
 ; CHECK-LABEL: @test_pointer_phi_used_by_others_in_loop_1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[START_PTR:%.*]] = getelementptr inbounds i32, i32* [[PTR:%.*]], i64 1
 ; CHECK-NEXT:    [[L_2_PRE:%.*]] = load i32, i32* [[PTR]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[L_3:%.*]] = phi i32 [ [[L_2_PRE]], [[ENTRY:%.*]] ], [ [[L_3_PRE:%.*]], [[LOOP_LOOP_CRIT_EDGE:%.*]] ]
-; CHECK-NEXT:    [[L_2:%.*]] = phi i32 [ [[L_2_PRE]], [[ENTRY]] ], [ [[TMP0:%.*]], [[LOOP_LOOP_CRIT_EDGE]] ]
-; CHECK-NEXT:    [[PTR_IV:%.*]] = phi i32* [ [[START_PTR]], [[ENTRY]] ], [ [[PTR_IV_NEXT:%.*]], [[LOOP_LOOP_CRIT_EDGE]] ]
-; CHECK-NEXT:    [[MIN_PTR:%.*]] = phi i32* [ [[PTR]], [[ENTRY]] ], [ [[MIN_SELECT:%.*]], [[LOOP_LOOP_CRIT_EDGE]] ]
+; CHECK-NEXT:    [[L_3:%.*]] = phi i32 [ [[L_2_PRE]], [[ENTRY:%.*]] ], [ [[TMP0:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[PTR_IV:%.*]] = phi i32* [ [[START_PTR]], [[ENTRY]] ], [ [[PTR_IV_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[MIN_PTR:%.*]] = phi i32* [ [[PTR]], [[ENTRY]] ], [ [[MIN_SELECT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV]], align 4
-; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
-; CHECK-NEXT:    [[TMP0]] = select i1 [[CMP_I_I_I]], i32 [[L_1]], i32 [[L_2]]
+; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_3]]
+; CHECK-NEXT:    [[TMP0]] = select i1 [[CMP_I_I_I]], i32 [[L_1]], i32 [[L_3]]
 ; CHECK-NEXT:    [[MIN_SELECT]] = select i1 [[CMP_I_I_I]], i32* [[PTR_IV]], i32* [[MIN_PTR]]
 ; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, i32* [[PTR_IV]], i32 [[L_3]]
 ; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END:%.*]]
-; CHECK-NEXT:    br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP_LOOP_CRIT_EDGE]]
-; CHECK:       loop.loop_crit_edge:
-; CHECK-NEXT:    [[L_3_PRE]] = load i32, i32* [[MIN_SELECT]], align 4
-; CHECK-NEXT:    br label [[LOOP]]
+; CHECK-NEXT:    br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = load i32, i32* [[MIN_SELECT]], align 4
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   %start.ptr = getelementptr inbounds i32, i32* %ptr, i64 1
   br label %loop
 
 loop:
   %ptr.iv = phi i32* [ %start.ptr, %entry ], [ %ptr.iv.next, %loop ]
   %min.ptr = phi i32* [ %ptr, %entry ], [ %min.select, %loop ]

 ; CHECK-NEXT:    [[TMP0]] = select i1 [[CMP_I_I_I]], i32 [[L_1]], i32 [[L_2]]
 ; CHECK-NEXT:    [[MIN_SELECT]] = select i1 [[CMP_I_I_I]], i32* [[PTR_IV]], i32* [[MIN_PTR]]
 ; CHECK-NEXT:    [[GEP_MIN_PTR:%.*]] = getelementptr inbounds i32, i32* [[MIN_PTR]], i32 1
 ; CHECK-NEXT:    [[L_3:%.*]] = load i32, i32* [[GEP_MIN_PTR]], align 4
 ; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, i32* [[PTR_IV]], i32 [[L_3]]
 ; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = load i32, i32* [[MIN_SELECT]], align 4
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   %start.ptr = getelementptr inbounds i32, i32* %ptr, i64 1
   br label %loop
 
 loop:
   %ptr.iv = phi i32* [ %start.ptr, %entry ], [ %ptr.iv.next, %loop ]
   %min.ptr = phi i32* [ %ptr, %entry ], [ %min.select, %loop ]

llvm/test/Transforms/GVN/load-of-pointer-select-available.ll

 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, i32* [[PTR_IV]], align 4
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
 ; CHECK-NEXT:    [[MIN_VAL]] = select i1 [[CMP_1]], i32 [[L_1]], i32 [[L_2]]
 ; CHECK-NEXT:    [[MIN_SELECT]] = select i1 [[CMP_1]], i32* [[PTR_IV]], i32* [[MIN_PTR]]
 ; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, i32* [[PTR_IV]], i64 1
 ; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = load i32, i32* [[MIN_SELECT]], align 4
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 [[MIN_VAL]]
 ;
 entry:
   %start.ptr = getelementptr inbounds i32, i32* %ptr, i64 1
   %l.2.pre = load i32, i32* %ptr, align 4
   br label %loop
 
 loop:
   %l.2 = phi i32 [ %l.2.pre, %entry ], [ %min.val, %loop ]

 ; CHECK-NEXT:    call void @may_throw()
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
 ; CHECK-NEXT:    [[MIN_VAL]] = select i1 [[CMP_1]], i32 [[L_1]], i32 [[L_2]]
 ; CHECK-NEXT:    [[MIN_SELECT]] = select i1 [[CMP_1]], i32* [[PTR_IV]], i32* [[MIN_PTR]]
 ; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, i32* [[PTR_IV]], i64 1
 ; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[RES:%.*]] = load i32, i32* [[MIN_SELECT]], align 4
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 [[MIN_VAL]]
 ;
 entry:
   %start.ptr = getelementptr inbounds i32, i32* %ptr, i64 1
   %l.2.pre = load i32, i32* %ptr, align 4
   br label %loop
 
 loop:
   %l.2 = phi i32 [ %l.2.pre, %entry ], [ %min.val, %loop ]

 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
 ; CHECK-NEXT:    [[MIN_VAL]] = select i1 [[CMP_1]], i32 [[L_1]], i32 [[L_2]]
 ; CHECK-NEXT:    [[MIN_SELECT]] = select i1 [[CMP_1]], i32* [[PTR_IV]], i32* [[MIN_PTR]]
 ; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, i32* [[PTR_IV]], i64 1
 ; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32* [[PTR_IV_NEXT]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    call void @may_throw()
-; CHECK-NEXT:    [[RES:%.*]] = load i32, i32* [[MIN_SELECT]], align 4
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 [[MIN_VAL]]
 ;
 entry:
   %start.ptr = getelementptr inbounds i32, i32* %ptr, i64 1
   %l.2.pre = load i32, i32* %ptr, align 4
   br label %loop
 
 loop:
   %l.2 = phi i32 [ %l.2.pre, %entry ], [ %min.val, %loop ]