1 files changed, 77 insertions, 52 deletions

diff --git a/llvm/lib/Analysis/Loads.cpp b/llvm/lib/Analysis/Loads.cpp
index a7d07c0b6183..e5245225d905 100644
--- a/llvm/lib/Analysis/Loads.cpp
+++ b/llvm/lib/Analysis/Loads.cpp
@@ -27,24 +27,12 @@
 
 using namespace llvm;
 
-static MaybeAlign getBaseAlign(const Value *Base, const DataLayout &DL) {
-  if (const MaybeAlign PA = Base->getPointerAlignment(DL))
-    return *PA;
-  Type *const Ty = Base->getType()->getPointerElementType();
-  if (!Ty->isSized())
-    return None;
-  return Align(DL.getABITypeAlignment(Ty));
-}
-
 static bool isAligned(const Value *Base, const APInt &Offset, Align Alignment,
                       const DataLayout &DL) {
-  if (MaybeAlign BA = getBaseAlign(Base, DL)) {
-    const APInt APBaseAlign(Offset.getBitWidth(), BA->value());
-    const APInt APAlign(Offset.getBitWidth(), Alignment.value());
-    assert(APAlign.isPowerOf2() && "must be a power of 2!");
-    return APBaseAlign.uge(APAlign) && !(Offset & (APAlign - 1));
-  }
-  return false;
+  Align BA = Base->getPointerAlignment(DL);
+  const APInt APAlign(Offset.getBitWidth(), Alignment.value());
+  assert(APAlign.isPowerOf2() && "must be a power of 2!");
+  return BA >= Alignment && !(Offset & (APAlign - 1));
 }
 
 /// Test if V is always a pointer to allocated and suitably aligned memory for
@@ -52,7 +40,13 @@ static bool isAligned(const Value *Base, const APInt &Offset, Align Alignment,
 static bool isDereferenceableAndAlignedPointer(
     const Value *V, Align Alignment, const APInt &Size, const DataLayout &DL,
     const Instruction *CtxI, const DominatorTree *DT,
-    SmallPtrSetImpl<const Value *> &Visited) {
+    SmallPtrSetImpl<const Value *> &Visited, unsigned MaxDepth) {
+  assert(V->getType()->isPointerTy() && "Base must be pointer");
+
+  // Recursion limit.
+  if (MaxDepth-- == 0)
+    return false;
+
   // Already visited?  Bail out, we've likely hit unreachable code.
   if (!Visited.insert(V).second)
     return false;
@@ -61,9 +55,11 @@ static bool isDereferenceableAndAlignedPointer(
   // malloc may return null.
 
   // bitcast instructions are no-ops as far as dereferenceability is concerned.
-  if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V))
-    return isDereferenceableAndAlignedPointer(BC->getOperand(0), Alignment,
-                                              Size, DL, CtxI, DT, Visited);
+  if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V)) {
+    if (BC->getSrcTy()->isPointerTy())
+      return isDereferenceableAndAlignedPointer(
+          BC->getOperand(0), Alignment, Size, DL, CtxI, DT, Visited, MaxDepth);
+  }
 
   bool CheckForNonNull = false;
   APInt KnownDerefBytes(Size.getBitWidth(),
@@ -72,7 +68,7 @@ static bool isDereferenceableAndAlignedPointer(
     if (!CheckForNonNull || isKnownNonZero(V, DL, 0, nullptr, CtxI, DT)) {
       // As we recursed through GEPs to get here, we've incrementally checked
       // that each step advanced by a multiple of the alignment. If our base is
-      // properly aligned, then the original offset accessed must also be.  
+      // properly aligned, then the original offset accessed must also be.
       Type *Ty = V->getType();
       assert(Ty->isSized() && "must be sized");
       APInt Offset(DL.getTypeStoreSizeInBits(Ty), 0);
@@ -99,22 +95,22 @@ static bool isDereferenceableAndAlignedPointer(
     // addrspacecast, so we can't do arithmetic directly on the APInt values.
     return isDereferenceableAndAlignedPointer(
         Base, Alignment, Offset + Size.sextOrTrunc(Offset.getBitWidth()), DL,
-        CtxI, DT, Visited);
+        CtxI, DT, Visited, MaxDepth);
   }
 
   // For gc.relocate, look through relocations
   if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V))
     return isDereferenceableAndAlignedPointer(
-        RelocateInst->getDerivedPtr(), Alignment, Size, DL, CtxI, DT, Visited);
+      RelocateInst->getDerivedPtr(), Alignment, Size, DL, CtxI, DT, Visited, MaxDepth);
 
   if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V))
     return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Alignment,
-                                              Size, DL, CtxI, DT, Visited);
+                                              Size, DL, CtxI, DT, Visited, MaxDepth);
 
   if (const auto *Call = dyn_cast<CallBase>(V))
     if (auto *RP = getArgumentAliasingToReturnedPointer(Call, true))
       return isDereferenceableAndAlignedPointer(RP, Alignment, Size, DL, CtxI,
-                                                DT, Visited);
+                                                DT, Visited, MaxDepth);
 
   // If we don't know, assume the worst.
   return false;
@@ -128,11 +124,11 @@ bool llvm::isDereferenceableAndAlignedPointer(const Value *V, Align Alignment,
   // Note: At the moment, Size can be zero.  This ends up being interpreted as
   // a query of whether [Base, V] is dereferenceable and V is aligned (since
   // that's what the implementation happened to do).  It's unclear if this is
-  // the desired semantic, but at least SelectionDAG does exercise this case.  
-  
+  // the desired semantic, but at least SelectionDAG does exercise this case.
+
   SmallPtrSet<const Value *, 32> Visited;
   return ::isDereferenceableAndAlignedPointer(V, Alignment, Size, DL, CtxI, DT,
-                                              Visited);
+                                              Visited, 16);
 }
 
 bool llvm::isDereferenceableAndAlignedPointer(const Value *V, Type *Ty,
@@ -140,9 +136,11 @@ bool llvm::isDereferenceableAndAlignedPointer(const Value *V, Type *Ty,
                                               const DataLayout &DL,
                                               const Instruction *CtxI,
                                               const DominatorTree *DT) {
-  if (!Ty->isSized())
+  // For unsized types or scalable vectors we don't know exactly how many bytes
+  // are dereferenced, so bail out.
+  if (!Ty->isSized() || isa<ScalableVectorType>(Ty))
     return false;
-  
+
   // When dereferenceability information is provided by a dereferenceable
   // attribute, we know exactly how many bytes are dereferenceable. If we can
   // determine the exact offset to the attributed variable, we can use that
@@ -160,7 +158,7 @@ bool llvm::isDereferenceablePointer(const Value *V, Type *Ty,
                                     const DataLayout &DL,
                                     const Instruction *CtxI,
                                     const DominatorTree *DT) {
-  return isDereferenceableAndAlignedPointer(V, Ty, Align::None(), DL, CtxI, DT);
+  return isDereferenceableAndAlignedPointer(V, Ty, Align(1), DL, CtxI, DT);
 }
 
 /// Test if A and B will obviously have the same value.
@@ -202,8 +200,7 @@ bool llvm::isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L,
 
   APInt EltSize(DL.getIndexTypeSizeInBits(Ptr->getType()),
                 DL.getTypeStoreSize(LI->getType()));
-  const Align Alignment = DL.getValueOrABITypeAlignment(
-      MaybeAlign(LI->getAlignment()), LI->getType());
+  const Align Alignment = LI->getAlign();
 
   Instruction *HeaderFirstNonPHI = L->getHeader()->getFirstNonPHI();
 
@@ -259,14 +256,10 @@ bool llvm::isDereferenceableAndAlignedInLoop(LoadInst *LI, Loop *L,
 ///
 /// This uses the pointee type to determine how many bytes need to be safe to
 /// load from the pointer.
-bool llvm::isSafeToLoadUnconditionally(Value *V, MaybeAlign MA, APInt &Size,
+bool llvm::isSafeToLoadUnconditionally(Value *V, Align Alignment, APInt &Size,
                                        const DataLayout &DL,
                                        Instruction *ScanFrom,
                                        const DominatorTree *DT) {
-  // Zero alignment means that the load has the ABI alignment for the target
-  const Align Alignment =
-      DL.getValueOrABITypeAlignment(MA, V->getType()->getPointerElementType());
-
   // If DT is not specified we can't make context-sensitive query
   const Instruction* CtxI = DT ? ScanFrom : nullptr;
   if (isDereferenceableAndAlignedPointer(V, Alignment, Size, DL, CtxI, DT))
@@ -301,7 +294,8 @@ bool llvm::isSafeToLoadUnconditionally(Value *V, MaybeAlign MA, APInt &Size,
       return false;
 
     Value *AccessedPtr;
-    MaybeAlign MaybeAccessedAlign;
+    Type *AccessedTy;
+    Align AccessedAlign;
     if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
       // Ignore volatile loads. The execution of a volatile load cannot
       // be used to prove an address is backed by regular memory; it can,
@@ -309,20 +303,18 @@ bool llvm::isSafeToLoadUnconditionally(Value *V, MaybeAlign MA, APInt &Size,
       if (LI->isVolatile())
         continue;
       AccessedPtr = LI->getPointerOperand();
-      MaybeAccessedAlign = MaybeAlign(LI->getAlignment());
+      AccessedTy = LI->getType();
+      AccessedAlign = LI->getAlign();
     } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
       // Ignore volatile stores (see comment for loads).
       if (SI->isVolatile())
         continue;
       AccessedPtr = SI->getPointerOperand();
-      MaybeAccessedAlign = MaybeAlign(SI->getAlignment());
+      AccessedTy = SI->getValueOperand()->getType();
+      AccessedAlign = SI->getAlign();
     } else
       continue;
 
-    Type *AccessedTy = AccessedPtr->getType()->getPointerElementType();
-
-    const Align AccessedAlign =
-        DL.getValueOrABITypeAlignment(MaybeAccessedAlign, AccessedTy);
     if (AccessedAlign < Alignment)
       continue;
 
@@ -338,7 +330,7 @@ bool llvm::isSafeToLoadUnconditionally(Value *V, MaybeAlign MA, APInt &Size,
   return false;
 }
 
-bool llvm::isSafeToLoadUnconditionally(Value *V, Type *Ty, MaybeAlign Alignment,
+bool llvm::isSafeToLoadUnconditionally(Value *V, Type *Ty, Align Alignment,
                                        const DataLayout &DL,
                                        Instruction *ScanFrom,
                                        const DominatorTree *DT) {
@@ -362,7 +354,7 @@ Value *llvm::FindAvailableLoadedValue(LoadInst *Load,
                                       BasicBlock *ScanBB,
                                       BasicBlock::iterator &ScanFrom,
                                       unsigned MaxInstsToScan,
-                                      AliasAnalysis *AA, bool *IsLoad,
+                                      AAResults *AA, bool *IsLoad,
                                       unsigned *NumScanedInst) {
   // Don't CSE load that is volatile or anything stronger than unordered.
   if (!Load->isUnordered())
@@ -373,11 +365,33 @@ Value *llvm::FindAvailableLoadedValue(LoadInst *Load,
       ScanFrom, MaxInstsToScan, AA, IsLoad, NumScanedInst);
 }
 
+// Check if the load and the store have the same base, constant offsets and
+// non-overlapping access ranges.
+static bool AreNonOverlapSameBaseLoadAndStore(
+    Value *LoadPtr, Type *LoadTy, Value *StorePtr, Type *StoreTy,
+    const DataLayout &DL) {
+  APInt LoadOffset(DL.getTypeSizeInBits(LoadPtr->getType()), 0);
+  APInt StoreOffset(DL.getTypeSizeInBits(StorePtr->getType()), 0);
+  Value *LoadBase = LoadPtr->stripAndAccumulateConstantOffsets(
+      DL, LoadOffset, /* AllowNonInbounds */ false);
+  Value *StoreBase = StorePtr->stripAndAccumulateConstantOffsets(
+      DL, StoreOffset, /* AllowNonInbounds */ false);
+  if (LoadBase != StoreBase)
+    return false;
+  auto LoadAccessSize = LocationSize::precise(DL.getTypeStoreSize(LoadTy));
+  auto StoreAccessSize = LocationSize::precise(DL.getTypeStoreSize(StoreTy));
+  ConstantRange LoadRange(LoadOffset,
+                          LoadOffset + LoadAccessSize.toRaw());
+  ConstantRange StoreRange(StoreOffset,
+                           StoreOffset + StoreAccessSize.toRaw());
+  return LoadRange.intersectWith(StoreRange).isEmptySet();
+}
+
 Value *llvm::FindAvailablePtrLoadStore(Value *Ptr, Type *AccessTy,
                                        bool AtLeastAtomic, BasicBlock *ScanBB,
                                        BasicBlock::iterator &ScanFrom,
                                        unsigned MaxInstsToScan,
-                                       AliasAnalysis *AA, bool *IsLoadCSE,
+                                       AAResults *AA, bool *IsLoadCSE,
                                        unsigned *NumScanedInst) {
   if (MaxInstsToScan == 0)
     MaxInstsToScan = ~0U;
@@ -451,10 +465,21 @@ Value *llvm::FindAvailablePtrLoadStore(Value *Ptr, Type *AccessTy,
           StrippedPtr != StorePtr)
         continue;
 
-      // If we have alias analysis and it says the store won't modify the loaded
-      // value, ignore the store.
-      if (AA && !isModSet(AA->getModRefInfo(SI, StrippedPtr, AccessSize)))
-        continue;
+      if (!AA) {
+        // When AA isn't available, but if the load and the store have the same
+        // base, constant offsets and non-overlapping access ranges, ignore the
+        // store. This is a simple form of alias analysis that is used by the
+        // inliner. FIXME: use BasicAA if possible.
+        if (AreNonOverlapSameBaseLoadAndStore(
+                Ptr, AccessTy, SI->getPointerOperand(),
+                SI->getValueOperand()->getType(), DL))
+          continue;
+      } else {
+        // If we have alias analysis and it says the store won't modify the
+        // loaded value, ignore the store.
+        if (!isModSet(AA->getModRefInfo(SI, StrippedPtr, AccessSize)))
+          continue;
+      }
 
       // Otherwise the store that may or may not alias the pointer, bail out.
       ++ScanFrom;