[GVN] Refactor handling of pointer-select in GVN pass

[kachkov98]

Summary

This patch extends Def memory dependency with support of select instructions to consistently handle pointer-select conversion.

In general it would be great to support address translation through select inst (extend PHITransAddr?) to optimize different cases when array index depends from select like: https://godbolt.org/z/TsarK6xEs (I've reported this issue in https://github.com/llvm/llvm-project/issues/58569), now we only handle select-between-pointer; this patch is preparation for this work.

[nikic]

Could you please split out the AnalyzeLoadAvailability() refactoring to std::optional into a separate NFC patch (and base this one on top)?

[kachkov98]

Split AnalyzeLoadAvailability refactoring into separate patch: https://reviews.llvm.org/D141664

[nikic]

Thanks! Could you please also split off the change to findDominatingLoad()? For that change, we also need to introduce a limit on the number of instructions that get walked while finding the dominating value (100 would be consistent with MemDep), otherwise there may be issues with very large blocks. There should also be a test that shows we can now handle a case that we previously couldn't (with the dominating load being in a preceding basic block).

[kachkov98]

Split findDominatingLoad() rework into separate patch

[nikic]

LGTM

It's a bit odd to have a non-memory instruction as the dependency, but this does seem to work out nicely in practice.

llvm/lib/Transforms/Scalar/GVN.cpp

1105–1106

Outdated comment (End)

1105–1106

Outdated comment (End).

[nikic]

It looks like this breaks the build on 32-bit targets, because we don't have enough alignment bits.

[kachkov98]

Since extending MemDepResult looks not feasable (and replacing it to tag-pointer pair also looks bad because it frequently passed by value), I think we can treat select dependency as Def. It also fits naturally into existing GVN infra, and the meaning of Def dependency is already overloaded (it can be other load/store/alloca/memory intrinsic/etc.)

[kachkov98]

Treat select as Def dependency

[nikic]

LGTM

[nikic]

(Patch description needs an update though)

llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h

enum DepType {
     ///      this case, the load is loading an undef value or a store is the
     ///      first store to (that part of) the allocation.
     ///   3. Dependence queries on calls return Def only when they are readonly
     ///      calls or memory use intrinsics with identical callees and no
     ///      intervening clobbers.  No validation is done that the operands to
     ///      the calls are the same.
     Def,
 
+    /// This marker indicates that the query has dependency from select
+    /// instruction.
+    Select,
+
     /// This marker indicates that the query has no known dependency in the
     /// specified block.
     ///
     /// More detailed state info is encoded in the upper part of the pair (i.e.
     /// the Instruction*)
     Other
   };
 
enum OtherType {
     /// This marker indicates that the query dependency is unknown.
     Unknown
   };
 
   using ValueTy = PointerSumType<
       DepType, PointerSumTypeMember<Invalid, Instruction *>,
       PointerSumTypeMember<Clobber, Instruction *>,
       PointerSumTypeMember<Def, Instruction *>,
+      PointerSumTypeMember<Select, Instruction *>,
       PointerSumTypeMember<Other, PointerEmbeddedInt<OtherType, 3>>>;
   ValueTy Value;
 
   explicit MemDepResult(ValueTy V) : Value(V) {}
 
 public:
   MemDepResult() = default;
 
   /// get methods: These are static ctor methods for creating various
   /// MemDepResult kinds.
   static MemDepResult getDef(Instruction *Inst) {
     assert(Inst && "Def requires inst");
     return MemDepResult(ValueTy::create<Def>(Inst));
   }
   static MemDepResult getClobber(Instruction *Inst) {
     assert(Inst && "Clobber requires inst");
     return MemDepResult(ValueTy::create<Clobber>(Inst));
   }
+  static MemDepResult getSelect(Instruction *Inst) {
+    return MemDepResult(ValueTy::create<Select>(Inst));
+  }
   static MemDepResult getNonLocal() {
     return MemDepResult(ValueTy::create<Other>(NonLocal));
   }
   static MemDepResult getNonFuncLocal() {
     return MemDepResult(ValueTy::create<Other>(NonFuncLocal));
   }
   static MemDepResult getUnknown() {
     return MemDepResult(ValueTy::create<Other>(Unknown));
   }
 
   /// Tests if this MemDepResult represents a query that is an instruction
   /// clobber dependency.
   bool isClobber() const { return Value.is<Clobber>(); }
 
   /// Tests if this MemDepResult represents a query that is an instruction
   /// definition dependency.
   bool isDef() const { return Value.is<Def>(); }
 
+  /// Tests if this MemDepResult represents a query that is an instruction
+  /// select dependency.
+  bool isSelect() const { return Value.is<Select>(); }
+
+  /// Tests if this MemDepResult represents a local query (Clobber/Def/Select).
+  bool isLocal() const { return isClobber() || isDef() || isSelect(); }
+
   /// Tests if this MemDepResult represents a query that is transparent to the
   /// start of the block, but where a non-local hasn't been done.
   bool isNonLocal() const {
     return Value.is<Other>() && Value.cast<Other>() == NonLocal;
   }
 
   /// Tests if this MemDepResult represents a query that is transparent to the
   /// start of the function.
public:
   Instruction *getInst() const {
     switch (Value.getTag()) {
     case Invalid:
       return Value.cast<Invalid>();
     case Clobber:
       return Value.cast<Clobber>();
     case Def:
       return Value.cast<Def>();
+    case Select:
+      return Value.cast<Select>();
     case Other:
       return nullptr;
     }
     llvm_unreachable("Unknown discriminant!");
   }
 
   bool operator==(const MemDepResult &M) const { return Value == M.Value; }
   bool operator!=(const MemDepResult &M) const { return Value != M.Value; }

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

private:
   SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
 
   // Helper functions of redundant load elimination
   bool processLoad(LoadInst *L);
   bool processNonLocalLoad(LoadInst *L);
   bool processAssumeIntrinsic(AssumeInst *II);
 
   /// Given a local dependency (Def or Clobber) determine if a value is
-  /// available for the load.  Returns true if an value is known to be
-  /// available and populates Res.  Returns false otherwise.
-  bool AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo,
-                               Value *Address, gvn::AvailableValue &Res);
+  /// available for the load.
+  std::optional<gvn::AvailableValue>
+  AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo, Value *Address);
 
   /// 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);
 

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

while (ScanIt != BB->begin()) {
     // looking for a clobber in many cases; that's an alias property and is
     // handled by BasicAA.
     if (isa<AllocaInst>(Inst) || isNoAliasCall(Inst)) {
       const Value *AccessPtr = getUnderlyingObject(MemLoc.Ptr);
       if (AccessPtr == Inst || BatchAA.isMustAlias(Inst, AccessPtr))
         return MemDepResult::getDef(Inst);
     }
 
+    // If we found a select instruction for MemLoc pointer, return it as
+    // Select dependency.
+    if (isa<SelectInst>(Inst) && MemLoc.Ptr == Inst)
+      return MemDepResult::getSelect(Inst);
+
     if (isInvariantLoad)
       continue;
 
     // A release fence requires that all stores complete before it, but does
     // not prevent the reordering of following loads or stores 'before' the
     // fence.  As a result, we look past it when finding a dependency for
     // loads.  DSE uses this to find preceding stores to delete and thus we
     // can't bypass the fence if the query instruction is a store.
MemDepResult MemoryDependenceResults::getNonLocalInfoForBlock(
   if (ExistingResult)
     ExistingResult->setResult(Dep);
   else
     Cache->push_back(NonLocalDepEntry(BB, Dep));
 
   // If the block has a dependency (i.e. it isn't completely transparent to
   // the value), remember the reverse association because we just added it
   // to Cache!
-  if (!Dep.isDef() && !Dep.isClobber())
+  if (!Dep.isLocal())
     return Dep;
 
   // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
   // update MemDep when we remove instructions.
   Instruction *Inst = Dep.getInst();
   assert(Inst && "Didn't depend on anything?");
   ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
   ReverseNonLocalPtrDeps[Inst].insert(CacheKey);

llvm/lib/Transforms/Scalar/GVN.cpp

struct llvm::gvn::AvailableValue {
 
   /// Val - The value that is live out of the block.
   Value *Val;
   /// Kind of the live-out value.
   ValType Kind;
 
   /// Offset - The byte offset in Val that is interesting for the load query.
   unsigned Offset = 0;
+  /// V1, V2 - The dominating non-cloberred values of SelectVal.
+  Value *V1 = nullptr, *V2 = nullptr;
 
   static AvailableValue get(Value *V, unsigned Offset = 0) {
     AvailableValue Res;
     Res.Val = V;
     Res.Kind = ValType::SimpleVal;
     Res.Offset = Offset;
     return Res;
   }
struct llvm::gvn::AvailableValue {
   static AvailableValue getUndef() {
     AvailableValue Res;
     Res.Val = nullptr;
     Res.Kind = ValType::UndefVal;
     Res.Offset = 0;
     return Res;
   }
 
-  static AvailableValue getSelect(SelectInst *Sel) {
+  static AvailableValue getSelect(SelectInst *Sel, Value *V1, Value *V2) {
     AvailableValue Res;
     Res.Val = Sel;
     Res.Kind = ValType::SelectVal;
     Res.Offset = 0;
+    Res.V1 = V1;
+    Res.V2 = V2;
     return Res;
   }
 
   bool isSimpleValue() const { return Kind == ValType::SimpleVal; }
   bool isCoercedLoadValue() const { return Kind == ValType::LoadVal; }
   bool isMemIntrinValue() const { return Kind == ValType::MemIntrin; }
   bool isUndefValue() const { return Kind == ValType::UndefVal; }
   bool isSelectValue() const { return Kind == ValType::SelectVal; }
static AvailableValueInBlock get(BasicBlock *BB, Value *V,
                                    unsigned Offset = 0) {
     return get(BB, AvailableValue::get(V, Offset));
   }
 
   static AvailableValueInBlock getUndef(BasicBlock *BB) {
     return get(BB, AvailableValue::getUndef());
   }
 
-  static AvailableValueInBlock getSelect(BasicBlock *BB, SelectInst *Sel) {
-    return get(BB, AvailableValue::getSelect(Sel));
+  static AvailableValueInBlock getSelect(BasicBlock *BB, SelectInst *Sel,
+                                         Value *V1, Value *V2) {
+    return get(BB, AvailableValue::getSelect(Sel, V1, V2));
   }
 
   /// Emit code at the end of this block to adjust the value defined here to
   /// the specified type. This handles various coercion cases.
   Value *MaterializeAdjustedValue(LoadInst *Load, GVNPass &gvn) const {
     return AV.MaterializeAdjustedValue(Load, BB->getTerminator(), gvn);
   }
 };
for (const AvailableValueInBlock &AV : ValuesPerBlock) {
 
     SSAUpdate.AddAvailableValue(BB, AV.MaterializeAdjustedValue(Load, gvn));
   }
 
   // Perform PHI construction.
   return SSAUpdate.GetValueInMiddleOfBlock(Load->getParent());
 }
 
-static LoadInst *findDominatingLoad(Value *Ptr, Type *LoadTy, SelectInst *Sel,
-                                    DominatorTree &DT) {
-  for (Value *U : Ptr->users()) {
-    auto *LI = dyn_cast<LoadInst>(U);
-    if (LI && LI->getType() == LoadTy && LI->getParent() == Sel->getParent() &&
-        DT.dominates(LI, Sel))
-      return LI;
-  }
-  return nullptr;
-}
-
 Value *AvailableValue::MaterializeAdjustedValue(LoadInst *Load,
                                                 Instruction *InsertPt,
                                                 GVNPass &gvn) const {
   Value *Res;
   Type *LoadTy = Load->getType();
   const DataLayout &DL = Load->getModule()->getDataLayout();
   if (isSimpleValue()) {
     Res = getSimpleValue();
Res = getMemInstValueForLoad(getMemIntrinValue(), Offset, LoadTy,
                                  InsertPt, DL);
     LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset
                       << "  " << *getMemIntrinValue() << '\n'
                       << *Res << '\n'
                       << "\n\n\n");
   } else if (isSelectValue()) {
     // Introduce a new value select for a load from an eligible pointer select.
     SelectInst *Sel = getSelectValue();
-    LoadInst *L1 = findDominatingLoad(Sel->getOperand(1), LoadTy, Sel,
-                                      gvn.getDominatorTree());
-    LoadInst *L2 = findDominatingLoad(Sel->getOperand(2), LoadTy, Sel,
-                                      gvn.getDominatorTree());
-    assert(L1 && L2 &&
-           "must be able to obtain dominating loads for both value operands of "
-           "the select");
-    Res = SelectInst::Create(Sel->getCondition(), L1, L2, "", Sel);
+    assert(V1 && V2 && "both value operands of the select must be present");
+    Res = SelectInst::Create(Sel->getCondition(), V1, V2, "", Sel);
   } else {
     llvm_unreachable("Should not materialize value from dead block");
   }
   assert(Res && "failed to materialize?");
   return Res;
 }
 
 static bool isLifetimeStart(const Instruction *Inst) {
static void reportMayClobberedLoad(LoadInst *Load, MemDepResult DepInfo,
 
   if (OtherAccess)
     R << " in favor of " << NV("OtherAccess", OtherAccess);
 
   R << " because it is clobbered by " << NV("ClobberedBy", DepInfo.getInst());
 
   ORE->emit(R);
 }
 
-/// Check if a load from pointer-select \p Address in \p DepBB can be converted
-/// to a value select. The following conditions need to be satisfied:
-/// 1. The pointer select (\p Address) must be defined in \p DepBB.
-/// 2. Both value operands of the pointer select must be loaded in the same
-/// basic block, before the pointer select.
-/// 3. There must be no instructions between the found loads and \p End that may
-/// clobber the loads.
-static std::optional<AvailableValue>
-tryToConvertLoadOfPtrSelect(BasicBlock *DepBB, BasicBlock::iterator End,
-                            Value *Address, Type *LoadTy, DominatorTree &DT,
+// Find non-clobbered value for Loc memory location in extended basic block
+// (chain of basic blocks with single predecessors) starting From instruction.
+static Value *findDominatingValue(const MemoryLocation &Loc, Instruction *From,
                                   AAResults *AA) {
+  BasicBlock *FromBB = From->getParent();
+  for (BasicBlock *BB = FromBB; BB; BB = BB->getSinglePredecessor())
+    for (auto I = BB == FromBB ? From->getReverseIterator() : BB->rbegin(),
+              E = BB->rend();
+         I != E; ++I) {
+      Instruction *Inst = &*I;
+      if (isModSet(AA->getModRefInfo(Inst, Loc)))
+        return nullptr;
+      if (auto *LI = dyn_cast<LoadInst>(Inst))
+        if (MemoryLocation::get(LI) == Loc)
+          return LI;
+    }
+  return nullptr;
+}
 
-  auto *Sel = dyn_cast_or_null<SelectInst>(Address);
-  if (!Sel || DepBB != Sel->getParent())
-    return std::nullopt;
+std::optional<AvailableValue>
+GVNPass::AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo,
+                                 Value *Address) {
+  assert(Load->isUnordered() && "rules below are incorrect for ordered access");
+  assert(DepInfo.isLocal() && "expected a local dependence");
 
-  LoadInst *L1 = findDominatingLoad(Sel->getOperand(1), LoadTy, Sel, DT);
-  LoadInst *L2 = findDominatingLoad(Sel->getOperand(2), LoadTy, Sel, DT);
-  if (!L1 || !L2)
+  Instruction *DepInst = DepInfo.getInst();
+  if (DepInfo.isSelect()) {
+    // Check if load with Addr dependent from select can be converted to select
+    // between load values. There must be no instructions between the found
+    // loads and DepInst that may clobber the loads.
+    assert(isa<SelectInst>(DepInst) && "Dependency must be select instruction");
+    auto *Sel = cast<SelectInst>(DepInst);
+    assert(Sel->getType() == Load->getPointerOperandType());
+    auto Loc = MemoryLocation::get(Load);
+    Value *V1 = findDominatingValue(Loc.getWithNewPtr(Sel->getTrueValue()),
+                                    DepInst, getAliasAnalysis());
+    if (!V1)
       return std::nullopt;
-
-  // Ensure there are no accesses that may modify the locations referenced by
-  // either L1 or L2 between L1, L2 and the specified End iterator.
-  Instruction *EarlierLoad = L1->comesBefore(L2) ? L1 : L2;
-  MemoryLocation L1Loc = MemoryLocation::get(L1);
-  MemoryLocation L2Loc = MemoryLocation::get(L2);
-  if (any_of(make_range(EarlierLoad->getIterator(), End), [&](Instruction &I) {
-        return isModSet(AA->getModRefInfo(&I, L1Loc)) ||
-               isModSet(AA->getModRefInfo(&I, L2Loc));
-      }))
+    Value *V2 = findDominatingValue(Loc.getWithNewPtr(Sel->getFalseValue()),
+                                    DepInst, getAliasAnalysis());
+    if (!V2)
       return std::nullopt;
-
-  return AvailableValue::getSelect(Sel);
+    return AvailableValue::getSelect(Sel, V1, V2);
   }
 
-bool GVNPass::AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo,
-                                      Value *Address, AvailableValue &Res) {
-  if (!DepInfo.isDef() && !DepInfo.isClobber()) {
-    assert(isa<SelectInst>(Address));
-    if (auto R = tryToConvertLoadOfPtrSelect(
-            Load->getParent(), Load->getIterator(), Address, Load->getType(),
-            getDominatorTree(), getAliasAnalysis())) {
-      Res = *R;
-      return true;
-    }
-    return false;
-  }
-
-  assert((DepInfo.isDef() || DepInfo.isClobber()) &&
-         "expected a local dependence");
-  assert(Load->isUnordered() && "rules below are incorrect for ordered access");
-
   const DataLayout &DL = Load->getModule()->getDataLayout();
-
-  Instruction *DepInst = DepInfo.getInst();
   if (DepInfo.isClobber()) {
     // If the dependence is to a store that writes to a superset of the bits
     // read by the load, we can extract the bits we need for the load from the
     // stored value.
     if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) {
       // Can't forward from non-atomic to atomic without violating memory model.
       if (Address && Load->isAtomic() <= DepSI->isAtomic()) {
         int Offset =
             analyzeLoadFromClobberingStore(Load->getType(), Address, DepSI, DL);
-        if (Offset != -1) {
-          Res = AvailableValue::get(DepSI->getValueOperand(), Offset);
-          return true;
-        }
+        if (Offset != -1)
+          return AvailableValue::get(DepSI->getValueOperand(), Offset);
       }
     }
 
     // Check to see if we have something like this:
     //    load i32* P
     //    load i8* (P+1)
     // if we have this, replace the later with an extraction from the former.
     if (LoadInst *DepLoad = dyn_cast<LoadInst>(DepInst)) {
if (LoadInst *DepLoad = dyn_cast<LoadInst>(DepInst)) {
           // GVN has no deal with a negative offset.
           Offset = (ClobberOff == std::nullopt || *ClobberOff < 0)
                        ? -1
                        : *ClobberOff;
         }
         if (Offset == -1)
           Offset =
               analyzeLoadFromClobberingLoad(LoadType, Address, DepLoad, DL);
-        if (Offset != -1) {
-          Res = AvailableValue::getLoad(DepLoad, Offset);
-          return true;
-        }
+        if (Offset != -1)
+          return AvailableValue::getLoad(DepLoad, Offset);
       }
     }
 
     // If the clobbering value is a memset/memcpy/memmove, see if we can
     // forward a value on from it.
     if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
       if (Address && !Load->isAtomic()) {
         int Offset = analyzeLoadFromClobberingMemInst(Load->getType(), Address,
                                                       DepMI, DL);
-        if (Offset != -1) {
-          Res = AvailableValue::getMI(DepMI, Offset);
-          return true;
-        }
+        if (Offset != -1)
+          return AvailableValue::getMI(DepMI, Offset);
       }
     }
 
     // Nothing known about this clobber, have to be conservative
     LLVM_DEBUG(
         // fast print dep, using operator<< on instruction is too slow.
         dbgs() << "GVN: load "; Load->printAsOperand(dbgs());
         dbgs() << " is clobbered by " << *DepInst << '\n';);
     if (ORE->allowExtraAnalysis(DEBUG_TYPE))
       reportMayClobberedLoad(Load, DepInfo, DT, ORE);
 
-    return false;
+    return std::nullopt;
   }
   assert(DepInfo.isDef() && "follows from above");
 
   // Loading the alloca -> undef.
   // Loading immediately after lifetime begin -> undef.
-  if (isa<AllocaInst>(DepInst) || isLifetimeStart(DepInst)) {
-    Res = AvailableValue::get(UndefValue::get(Load->getType()));
-    return true;
-  }
+  if (isa<AllocaInst>(DepInst) || isLifetimeStart(DepInst))
+    return AvailableValue::get(UndefValue::get(Load->getType()));
 
   if (Constant *InitVal =
-          getInitialValueOfAllocation(DepInst, TLI, Load->getType())) {
-    Res = AvailableValue::get(InitVal);
-    return true;
-  }
+          getInitialValueOfAllocation(DepInst, TLI, Load->getType()))
+    return AvailableValue::get(InitVal);
 
   if (StoreInst *S = dyn_cast<StoreInst>(DepInst)) {
     // Reject loads and stores that are to the same address but are of
     // different types if we have to. If the stored value is convertable to
     // the loaded value, we can reuse it.
     if (!canCoerceMustAliasedValueToLoad(S->getValueOperand(), Load->getType(),
                                          DL))
-      return false;
+      return std::nullopt;
 
     // Can't forward from non-atomic to atomic without violating memory model.
     if (S->isAtomic() < Load->isAtomic())
-      return false;
+      return std::nullopt;
 
-    Res = AvailableValue::get(S->getValueOperand());
-    return true;
+    return AvailableValue::get(S->getValueOperand());
   }
 
   if (LoadInst *LD = dyn_cast<LoadInst>(DepInst)) {
     // If the types mismatch and we can't handle it, reject reuse of the load.
     // If the stored value is larger or equal to the loaded value, we can reuse
     // it.
     if (!canCoerceMustAliasedValueToLoad(LD, Load->getType(), DL))
-      return false;
+      return std::nullopt;
 
     // Can't forward from non-atomic to atomic without violating memory model.
     if (LD->isAtomic() < Load->isAtomic())
-      return false;
+      return std::nullopt;
 
-    Res = AvailableValue::getLoad(LD);
-    return true;
+    return AvailableValue::getLoad(LD);
   }
 
   // Unknown def - must be conservative
   LLVM_DEBUG(
       // fast print dep, using operator<< on instruction is too slow.
       dbgs() << "GVN: load "; Load->printAsOperand(dbgs());
       dbgs() << " has unknown def " << *DepInst << '\n';);
-  return false;
+  return std::nullopt;
 }
 
 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
   // dependencies that produce an unknown value for the load (such as a call
   // that could potentially clobber the load).
-  unsigned NumDeps = Deps.size();
-  for (unsigned i = 0, e = NumDeps; i != e; ++i) {
-    BasicBlock *DepBB = Deps[i].getBB();
-    MemDepResult DepInfo = Deps[i].getResult();
+  for (const auto &Dep : Deps) {
+    BasicBlock *DepBB = Dep.getBB();
+    MemDepResult DepInfo = Dep.getResult();
 
     if (DeadBlocks.count(DepBB)) {
       // Dead dependent mem-op disguise as a load evaluating the same value
       // as the load in question.
       ValuesPerBlock.push_back(AvailableValueInBlock::getUndef(DepBB));
       continue;
     }
 
-    // The address being loaded in this non-local block may not be the same as
-    // the pointer operand of the load if PHI translation occurs.  Make sure
-    // to consider the right address.
-    Value *Address = Deps[i].getAddress();
-
-    if (!DepInfo.isDef() && !DepInfo.isClobber()) {
-      if (auto R = tryToConvertLoadOfPtrSelect(
-              DepBB, DepBB->end(), Address, Load->getType(), getDominatorTree(),
-              getAliasAnalysis())) {
-        ValuesPerBlock.push_back(
-            AvailableValueInBlock::get(DepBB, std::move(*R)));
-        continue;
-      }
+    if (!DepInfo.isLocal()) {
       UnavailableBlocks.push_back(DepBB);
       continue;
     }
 
-    AvailableValue AV;
-    if (AnalyzeLoadAvailability(Load, DepInfo, Address, AV)) {
+    // The address being loaded in this non-local block may not be the same as
+    // the pointer operand of the load if PHI translation occurs.  Make sure
+    // to consider the right address.
+    if (auto AV = AnalyzeLoadAvailability(Load, DepInfo, Dep.getAddress())) {
       // subtlety: because we know this was a non-local dependency, we know
       // it's safe to materialize anywhere between the instruction within
       // DepInfo and the end of it's block.
-      ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB,
-                                                          std::move(AV)));
+      ValuesPerBlock.push_back(
+          AvailableValueInBlock::get(DepBB, std::move(*AV)));
     } else {
       UnavailableBlocks.push_back(DepBB);
     }
   }
 
-  assert(NumDeps == ValuesPerBlock.size() + UnavailableBlocks.size() &&
+  assert(Deps.size() == ValuesPerBlock.size() + UnavailableBlocks.size() &&
          "post condition violation");
 }
 
 void GVNPass::eliminatePartiallyRedundantLoad(
     LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
     MapVector<BasicBlock *, Value *> &AvailableLoads) {
   for (const auto &AvailableLoad : AvailableLoads) {
     BasicBlock *UnavailableBlock = AvailableLoad.first;
bool GVNPass::processLoad(LoadInst *L) {
 
   // ... to a pointer that has been loaded from before...
   MemDepResult Dep = MD->getDependency(L);
 
   // If it is defined in another block, try harder.
   if (Dep.isNonLocal())
     return processNonLocalLoad(L);
 
-  Value *Address = L->getPointerOperand();
   // Only handle the local case below
-  if (!Dep.isDef() && !Dep.isClobber() && !isa<SelectInst>(Address)) {
+  if (!Dep.isLocal()) {
     // This might be a NonFuncLocal or an Unknown
     LLVM_DEBUG(
         // fast print dep, using operator<< on instruction is too slow.
         dbgs() << "GVN: load "; L->printAsOperand(dbgs());
         dbgs() << " has unknown dependence\n";);
     return false;
   }
 
-  AvailableValue AV;
-  if (AnalyzeLoadAvailability(L, Dep, Address, AV)) {
-    Value *AvailableValue = AV.MaterializeAdjustedValue(L, L, *this);
+  auto AV = AnalyzeLoadAvailability(L, Dep, L->getPointerOperand());
+  if (!AV)
+    return false;
 
-    // Replace the load!
-    patchAndReplaceAllUsesWith(L, AvailableValue);
-    markInstructionForDeletion(L);
-    if (MSSAU)
-      MSSAU->removeMemoryAccess(L);
-    ++NumGVNLoad;
-    reportLoadElim(L, AvailableValue, ORE);
-    // Tell MDA to reexamine the reused pointer since we might have more
-    // information after forwarding it.
-    if (MD && AvailableValue->getType()->isPtrOrPtrVectorTy())
-      MD->invalidateCachedPointerInfo(AvailableValue);
-    return true;
-  }
+  Value *AvailableValue = AV->MaterializeAdjustedValue(L, L, *this);
 
-  return false;
-}
-
 /// Return a pair the first field showing the value number of \p Exp and the
 /// second field showing whether it is a value number newly created.
 std::pair<uint32_t, bool>
 GVNPass::ValueTable::assignExpNewValueNum(Expression &Exp) {
   uint32_t &e = expressionNumbering[Exp];
   bool CreateNewValNum = !e;
   if (CreateNewValNum) {
     Expressions.push_back(Exp);

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

 ; CHECK-LABEL: @test_pointer_phi_select_simp_store_clobber_3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    store i32 99, ptr [[C:%.*]], align 4
 ; CHECK-NEXT:    [[L_1:%.*]] = load i32, ptr [[A:%.*]], align 4
 ; CHECK-NEXT:    [[L_2:%.*]] = load i32, ptr [[B:%.*]], align 4
 ; CHECK-NEXT:    [[CMP_I_I_I:%.*]] = icmp ult i32 [[L_1]], [[L_2]]
+; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP_I_I_I]], i32 [[L_1]], i32 [[L_2]]
 ; CHECK-NEXT:    [[MIN_SELECT:%.*]] = select i1 [[CMP_I_I_I]], ptr [[A]], ptr [[B]]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       else:
+; CHECK-NEXT:    [[RES_2_PRE:%.*]] = load i32, ptr [[A]], align 4
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
+; CHECK-NEXT:    [[RES_2:%.*]] = phi i32 [ [[SELECT]], [[THEN]] ], [ [[RES_2_PRE]], [[ELSE]] ]
 ; CHECK-NEXT:    [[P:%.*]] = phi ptr [ [[MIN_SELECT]], [[THEN]] ], [ [[A]], [[ELSE]] ]
-; CHECK-NEXT:    [[RES_2:%.*]] = load i32, ptr [[P]], align 4
 ; CHECK-NEXT:    ret i32 [[RES_2]]
 ;
 entry:
   br i1 %cond, label %then, label %else
 
 then:
   store i32 99, ptr %c
   %l.1 = load i32, ptr %a, align 4