[Loads] Add optimized FindAvailableLoadedValue() overload (NFCI)

FindAvailableLoadedValue() accepts an iterator by reference. If no
available value is found, then the iterator will either be left
at a clobbering instruction or the beginning of the basic block.
This allows using FindAvailableLoadedValue() across multiple blocks.

If this functionality is not needed, as is the case in InstCombine,
then we can use a much more efficient implementation: First try
to find an available value, and only perform clobber checks if
we actually found one. As this function only looks at a very small
number of instructions (6 by default) and usually doesn't find an
available value, this saves many expensive alias analysis queries.

1 files changed, 45 insertions, 0 deletions

diff --git a/llvm/lib/Analysis/Loads.cpp b/llvm/lib/Analysis/Loads.cpp
index 42fe548..d82ed02 100644
--- a/llvm/lib/Analysis/Loads.cpp
+++ b/llvm/lib/Analysis/Loads.cpp
@@ -593,6 +593,51 @@ Value *llvm::FindAvailablePtrLoadStore(Value *Ptr, Type *AccessTy,
   return nullptr;
 }
 
+Value *llvm::FindAvailableLoadedValue(LoadInst *Load, AAResults &AA,
+                                      bool *IsLoadCSE,
+                                      unsigned MaxInstsToScan) {
+  const DataLayout &DL = Load->getModule()->getDataLayout();
+  Value *StrippedPtr = Load->getPointerOperand()->stripPointerCasts();
+  BasicBlock *ScanBB = Load->getParent();
+  Type *AccessTy = Load->getType();
+  bool AtLeastAtomic = Load->isAtomic();
+
+  if (!Load->isUnordered())
+    return nullptr;
+
+  // Try to find an available value first, and delay expensive alias analysis
+  // queries until later.
+  Value *Available = nullptr;;
+  SmallVector<Instruction *> MustNotAliasInsts;
+  for (Instruction &Inst : make_range(++Load->getReverseIterator(),
+                                      ScanBB->rend())) {
+    if (isa<DbgInfoIntrinsic>(&Inst))
+      continue;
+
+    if (MaxInstsToScan-- == 0)
+      return nullptr;
+
+    Available = getAvailableLoadStore(&Inst, StrippedPtr, AccessTy,
+                                      AtLeastAtomic, DL, IsLoadCSE);
+    if (Available)
+      break;
+
+    if (Inst.mayWriteToMemory())
+      MustNotAliasInsts.push_back(&Inst);
+  }
+
+  // If we found an available value, ensure that the instructions in between
+  // did not modify the memory location.
+  if (Available) {
+    auto AccessSize = LocationSize::precise(DL.getTypeStoreSize(AccessTy));
+    for (Instruction *Inst : MustNotAliasInsts)
+      if (isModSet(AA.getModRefInfo(Inst, StrippedPtr, AccessSize)))
+        return nullptr;
+  }
+
+  return Available;
+}
+
 bool llvm::canReplacePointersIfEqual(Value *A, Value *B, const DataLayout &DL,
                                      Instruction *CtxI) {
   Type *Ty = A->getType();