Refactor ValueTracking isDereferenceableAndAlignedPointer

[apilipenko]

Summary

Current implementation of isDereferenceableAndAlignedPointer is messy. It tries to handle sized/non-sized types, looking through casts/relocations and inherent value dereferenceability properties in a single recursive function. Recent addition of alignment handling and context-sensitive non-null analysis made it even worse. This patch is an attempt to clean it up.

Inherent value dereferenceability properties are now handled in Value class:

• Value::isDereferenceablePointer
• Value::getDereferenceableBytes

The code which tracks dereferencability over a chain of values remains in ValueTracking. isDereferenceableAndAlignedPointer is no longer recursive. Instead it uses helper functions to strip all the casts/compute a base pointer and offset.

Overall structure of this code is as follows:

• Try to determine if a value is dereferenceable without dealing with type sizes. Strip type safe transformations only: address space casts, global aliases, GC relocations. If the resulting pointer is fully dereferenceable we are done. It will handle derferencability of opaque types.

• If the accessed type is sized try to decompose the value to a base pointer and an offset. Check if the accessed value lies within dereferenceable portion of the base pointer.

[apilipenko]

Rework stripForDereferenceable, stripAndAccumulateOffsetForDereferenceable to use standard Value::stripPointerCasts and GetPointerBaseWithConstantOffset functions. Now it's clear that the only reasons for these helpers is to look through gc relocations. I'm not sure that this is the right way to handle relocations though. But the current state is functional equivalent to what we had before the refactoring. May be we should update InstCombine to propagate dereferenceability through relocations instead of relying on looking through them (see D16143).

[apilipenko]

I'm going to split this change into a set of smaller ones.

include/llvm/Analysis/ValueTracking.h

void GetUnderlyingObjects(Value *V, SmallVectorImpl<Value *> &Objects,
                             const DataLayout &DL, LoopInfo *LI = nullptr,
                             unsigned MaxLookup = 6);
 
   /// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer
   /// are lifetime markers.
   bool onlyUsedByLifetimeMarkers(const Value *V);
 
   /// isDereferenceablePointer - Return true if this is always a dereferenceable
-  /// pointer. If the context instruction is specified perform context-sensitive
-  /// analysis and return true if the pointer is dereferenceable at the
-  /// specified instruction.
-  bool isDereferenceablePointer(const Value *V, const DataLayout &DL,
-                                const Instruction *CtxI = nullptr,
-                                const DominatorTree *DT = nullptr,
-                                const TargetLibraryInfo *TLI = nullptr);
+  /// pointer
+  bool isDereferenceablePointer(const Value *V, const DataLayout &DL);
 
   /// Returns true if V is always a dereferenceable pointer with alignment
   /// greater or equal than requested. If the context instruction is specified
   /// performs context-sensitive analysis and returns true if the pointer is
   /// dereferenceable at the specified instruction.
   bool isDereferenceableAndAlignedPointer(const Value *V, unsigned Align,
                                           const DataLayout &DL,
                                           const Instruction *CtxI = nullptr,

include/llvm/IR/Value.h

#include "llvm/IR/Value.def"
   ///
   /// Returns the original pointer value.  If this is called on a non-pointer
   /// value, it returns 'this'.
   Value *stripInBoundsOffsets();
   const Value *stripInBoundsOffsets() const {
     return const_cast<Value*>(this)->stripInBoundsOffsets();
   }
 
+  /// \brief Check if this is always a dereferenceable pointer
+  /// Sets CanBeNull if the pointer can be either dereferenceable or null
+  bool isDereferenceablePointer(bool &CanBeNull) const;
+
+  /// \brief Returns the number of bytes can be which safely dereferenced
+  /// via the pointer
+  /// Sets CanBeNull if the pointer can be either dereferenceable or null
+  uint64_t getDereferenceableBytes(const DataLayout &DL, bool &CanBeNull) const;
+
   /// \brief Translate PHI node to its predecessor from the given basic block.
   ///
   /// If this value is a PHI node with CurBB as its parent, return the value in
   /// the PHI node corresponding to PredBB.  If not, return ourself.  This is
   /// useful if you want to know the value something has in a predecessor
   /// block.
   Value *DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB);
 

lib/Analysis/ValueTracking.cpp

for (const User *U : V->users()) {
 
     if (II->getIntrinsicID() != Intrinsic::lifetime_start &&
         II->getIntrinsicID() != Intrinsic::lifetime_end)
       return false;
   }
   return true;
 }
 
-static bool isDereferenceableFromAttribute(const Value *BV, APInt Offset,
-                                           Type *Ty, const DataLayout &DL,
-                                           const Instruction *CtxI,
-                                           const DominatorTree *DT,
-                                           const TargetLibraryInfo *TLI) {
-  assert(Offset.isNonNegative() && "offset can't be negative");
-  assert(Ty->isSized() && "must be sized");
-  
-  APInt DerefBytes(Offset.getBitWidth(), 0);
-  bool CheckForNonNull = false;
-  if (const Argument *A = dyn_cast<Argument>(BV)) {
-    DerefBytes = A->getDereferenceableBytes();
-    if (!DerefBytes.getBoolValue()) {
-      DerefBytes = A->getDereferenceableOrNullBytes();
-      CheckForNonNull = true;
-    }
-  } else if (auto CS = ImmutableCallSite(BV)) {
-    DerefBytes = CS.getDereferenceableBytes(0);
-    if (!DerefBytes.getBoolValue()) {
-      DerefBytes = CS.getDereferenceableOrNullBytes(0);
-      CheckForNonNull = true;
-    }
-  } else if (const LoadInst *LI = dyn_cast<LoadInst>(BV)) {
-    if (MDNode *MD = LI->getMetadata(LLVMContext::MD_dereferenceable)) {
-      ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
-      DerefBytes = CI->getLimitedValue();
-    }
-    if (!DerefBytes.getBoolValue()) {
-      if (MDNode *MD = 
-              LI->getMetadata(LLVMContext::MD_dereferenceable_or_null)) {
-        ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
-        DerefBytes = CI->getLimitedValue();
-      }
-      CheckForNonNull = true;
-    }
-  }
-  
-  if (DerefBytes.getBoolValue())
-    if (DerefBytes.uge(Offset + DL.getTypeStoreSize(Ty)))
-      if (!CheckForNonNull || isKnownNonNullAt(BV, CtxI, DT, TLI))
-        return true;
-
-  return false;
-}
-
-static bool isDereferenceableFromAttribute(const Value *V, const DataLayout &DL,
-                                           const Instruction *CtxI,
-                                           const DominatorTree *DT,
-                                           const TargetLibraryInfo *TLI) {
-  Type *VTy = V->getType();
-  Type *Ty = VTy->getPointerElementType();
-  if (!Ty->isSized())
-    return false;
-  
-  APInt Offset(DL.getTypeStoreSizeInBits(VTy), 0);
-  return isDereferenceableFromAttribute(V, Offset, Ty, DL, CtxI, DT, TLI);
-}
-
-static bool isAligned(const Value *Base, APInt Offset, unsigned Align,
+static bool isAligned(const Value *Base, uint64_t Offset, unsigned Align,
                       const DataLayout &DL) {
-  APInt BaseAlign(Offset.getBitWidth(), getAlignment(Base, DL));
+  unsigned BaseAlign = getAlignment(Base, DL);
 
-  if (!BaseAlign) {
+  if (BaseAlign == 0) {
     Type *Ty = Base->getType()->getPointerElementType();
     if (!Ty->isSized())
       return false;
     BaseAlign = DL.getABITypeAlignment(Ty);
   }
 
-  APInt Alignment(Offset.getBitWidth(), Align);
-
-  assert(Alignment.isPowerOf2() && "must be a power of 2!");
-  return BaseAlign.uge(Alignment) && !(Offset & (Alignment-1));
+  assert(isPowerOf2_32(Align) && "must be a power of 2!");
+  return BaseAlign >= Align && !(Offset & (Align-1));
 }
 
 static bool isAligned(const Value *Base, unsigned Align, const DataLayout &DL) {
-  Type *Ty = Base->getType();
-  assert(Ty->isSized() && "must be sized");
-  APInt Offset(DL.getTypeStoreSizeInBits(Ty), 0);
-  return isAligned(Base, Offset, Align, DL);
-}
-
-/// Test if V is always a pointer to allocated and suitably aligned memory for
-/// a simple load or store.
-static bool isDereferenceableAndAlignedPointer(
-    const Value *V, unsigned Align, const DataLayout &DL,
-    const Instruction *CtxI, const DominatorTree *DT,
-    const TargetLibraryInfo *TLI, SmallPtrSetImpl<const Value *> &Visited) {
-  // Note that it is not safe to speculate into a malloc'd region because
-  // malloc may return null.
-
-  // These are obviously ok if aligned.
-  if (isa<AllocaInst>(V))
-    return isAligned(V, Align, DL);
-
-  // It's not always safe to follow a bitcast, for example:
-  //   bitcast i8* (alloca i8) to i32*
-  // would result in a 4-byte load from a 1-byte alloca. However,
-  // if we're casting from a pointer from a type of larger size
-  // to a type of smaller size (or the same size), and the alignment
-  // is at least as large as for the resulting pointer type, then
-  // we can look through the bitcast.
-  if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V)) {
-    Type *STy = BC->getSrcTy()->getPointerElementType(),
-         *DTy = BC->getDestTy()->getPointerElementType();
-    if (STy->isSized() && DTy->isSized() &&
-        (DL.getTypeStoreSize(STy) >= DL.getTypeStoreSize(DTy)) &&
-        (DL.getABITypeAlignment(STy) >= DL.getABITypeAlignment(DTy)))
-      return isDereferenceableAndAlignedPointer(BC->getOperand(0), Align, DL,
-                                                CtxI, DT, TLI, Visited);
-  }
-
-  // Global variables which can't collapse to null are ok.
-  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
-    if (!GV->hasExternalWeakLinkage())
-      return isAligned(V, Align, DL);
-
-  // byval arguments are okay.
-  if (const Argument *A = dyn_cast<Argument>(V))
-    if (A->hasByValAttr())
-      return isAligned(V, Align, DL);
-
-  if (isDereferenceableFromAttribute(V, DL, CtxI, DT, TLI))
-    return isAligned(V, Align, DL);
-
-  // For GEPs, determine if the indexing lands within the allocated object.
-  if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
-    Type *VTy = GEP->getType();
-    Type *Ty = VTy->getPointerElementType();
-    const Value *Base = GEP->getPointerOperand();
+  return isAligned(Base, 0, Align, DL);
+}
 
-    // Conservatively require that the base pointer be fully dereferenceable
-    // and aligned.
-    if (!Visited.insert(Base).second)
-      return false;
-    if (!isDereferenceableAndAlignedPointer(Base, Align, DL, CtxI, DT, TLI,
-                                            Visited))
-      return false;
+static const Value *stripForDereferenceable(const Value *V) {
+  // Even though we don't look through PHI nodes, we could be called on an
+  // instruction in an unreachable block, which may be on a cycle.
+  SmallPtrSet<const Value *, 4> Visited;
+  Visited.insert(V);
+  do {
+    V = V->stripPointerCasts();
 
-    APInt Offset(DL.getPointerTypeSizeInBits(VTy), 0);
-    if (!GEP->accumulateConstantOffset(DL, Offset))
-      return false;
+    if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V)) {
+      V = RelocateInst->getDerivedPtr();
+    } else {
+      return V;
+    }
+    assert(V->getType()->isPointerTy() && "Unexpected operand type!");
+  } while (Visited.insert(V).second);
 
-    // Check if the load is within the bounds of the underlying object
-    // and offset is aligned.
-    uint64_t LoadSize = DL.getTypeStoreSize(Ty);
-    Type *BaseType = Base->getType()->getPointerElementType();
-    assert(isPowerOf2_32(Align) && "must be a power of 2!");
-    return (Offset + LoadSize).ule(DL.getTypeAllocSize(BaseType)) && 
-           !(Offset & APInt(Offset.getBitWidth(), Align-1));
-  }
+  return V;
 
-  // For gc.relocate, look through relocations
-  if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V))
-    return isDereferenceableAndAlignedPointer(
-        RelocateInst->getDerivedPtr(), Align, DL, CtxI, DT, TLI, Visited);
+static const Value *
+stripAndAccumulateOffsetForDereferenceable(const Value *V,
+                                           const DataLayout &DL,
+                                           uint64_t &Offset) {
+  // Even though we don't look through PHI nodes, we could be called on an
+  // instruction in an unreachable block, which may be on a cycle.
+  SmallPtrSet<const Value *, 4> Visited;
+  Visited.insert(V);
+  do {
+    int64_t CurrentOffset = 0;
+    V = GetPointerBaseWithConstantOffset(V, CurrentOffset, DL);
+    Offset += CurrentOffset;
 
-  if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V))
-    return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Align, DL,
-                                              CtxI, DT, TLI, Visited);
+    if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V)) {
+      V = RelocateInst->getDerivedPtr();
+    } else {
+      return V;
+    }
+    assert(V->getType()->isPointerTy() && "Unexpected operand type!");
+  } while (Visited.insert(V).second);
 
-  // If we don't know, assume the worst.
-  return false;
+  return V;
 }
 
 bool llvm::isDereferenceableAndAlignedPointer(const Value *V, unsigned Align,
                                               const DataLayout &DL,
                                               const Instruction *CtxI,
                                               const DominatorTree *DT,
                                               const TargetLibraryInfo *TLI) {
-  // 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
-  // information here.
   Type *VTy = V->getType();
   Type *Ty = VTy->getPointerElementType();
 
   // Require ABI alignment for loads without alignment specification
   if (Align == 0)
     Align = DL.getABITypeAlignment(Ty);
 
-  if (Ty->isSized()) {
-    APInt Offset(DL.getTypeStoreSizeInBits(VTy), 0);
-    const Value *BV = V->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
-
-    if (Offset.isNonNegative())
-      if (isDereferenceableFromAttribute(BV, Offset, Ty, DL, CtxI, DT, TLI) &&
-          isAligned(BV, Offset, Align, DL))
-        return true;
+  bool CanBeNull = false;
+
+  // (1) Check if we can say if V is dereferenceable without dealing with type
+  // sizes. Strip casts, GC relocations. If the resulting pointer is fully
+  // dereferenceable we are done.
+  const Value *BV = stripForDereferenceable(V);
+  if (BV->getType() == V->getType())
+    if (BV->isDereferenceablePointer(CanBeNull)) {
+      if (CanBeNull && !isKnownNonNullAt(BV, CtxI, DT, TLI))
+        return false;
+      return Align == 1 || isAligned(BV, Align, DL);
     }
 
-  SmallPtrSet<const Value *, 32> Visited;
-  return ::isDereferenceableAndAlignedPointer(V, Align, DL, CtxI, DT, TLI,
-                                              Visited);
+  // If accessed type is not sized, there is nothing we can do
+  if (!Ty->isSized())
+    return false;
+
+  // (2) Strip casts, relocations, GEPs and accumulate V offset along the way.
+  // Check if the access is within dereferenceable portion of the base pointer.
+  uint64_t Offset = 0;
+  BV = stripAndAccumulateOffsetForDereferenceable(V, DL, Offset);
+
+  uint64_t DerefBytes = BV->getDereferenceableBytes(DL, CanBeNull);
+  if (DerefBytes >= Offset + DL.getTypeStoreSize(Ty)) {
+    if (CanBeNull && !isKnownNonNullAt(BV, CtxI, DT, TLI))
+      return false;
+    return Align == 1 || isAligned(BV, Offset, Align, DL);
   }
 
-bool llvm::isDereferenceablePointer(const Value *V, const DataLayout &DL,
-                                    const Instruction *CtxI,
-                                    const DominatorTree *DT,
-                                    const TargetLibraryInfo *TLI) {
-  return isDereferenceableAndAlignedPointer(V, 1, DL, CtxI, DT, TLI);
+  return false;
+}
+
+bool llvm::isDereferenceablePointer(const Value *V, const DataLayout &DL) {
+  return isDereferenceableAndAlignedPointer(V, 1, DL);
 }
 
 bool llvm::isSafeToSpeculativelyExecute(const Value *V,
                                         const Instruction *CtxI,
                                         const DominatorTree *DT,
                                         const TargetLibraryInfo *TLI) {
   const Operator *Inst = dyn_cast<Operator>(V);
   if (!Inst)

lib/IR/Value.cpp

Value *Value::stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
 
   return V;
 }
 
 Value *Value::stripInBoundsOffsets() {
   return stripPointerCastsAndOffsets<PSK_InBounds>(this);
 }
 
+bool Value::isDereferenceablePointer(bool &CanBeNull) const {
+  CanBeNull = false;
+
+  if (isa<AllocaInst>(this))
+    return true;
+
+  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(this)) {
+    // TODO: set CanBeNull and return true instead
+    return !GV->hasExternalWeakLinkage();
+  }
+
+  if (const Argument *A = dyn_cast<Argument>(this))
+    if (A->hasByValAttr())
+      return true;
+
+  return false;
+}
+
+uint64_t Value::getDereferenceableBytes(const DataLayout &DL,
+                                        bool &CanBeNull) const {
+  CanBeNull = false;
+
+  Type *Ty = getType()->getPointerElementType();
+  uint64_t TyStoreSize = Ty->isSized() ? DL.getTypeStoreSize(Ty) : 0;
+
+  if (isa<AllocaInst>(this)) {
+    return TyStoreSize;
+  }
+
+  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(this)) {
+    // TODO: set CanBeNull and return true instead
+    if (GV->hasExternalWeakLinkage())
+      return 0;
+    return TyStoreSize;
+  }
+
+  uint64_t DerefBytes = 0;
+  if (const Argument *A = dyn_cast<Argument>(this)) {
+    if (A->hasByValAttr()) {
+      DerefBytes = TyStoreSize;
+    } else {
+      DerefBytes = A->getDereferenceableBytes();
+      if (DerefBytes == 0) {
+        DerefBytes = A->getDereferenceableOrNullBytes();
+        CanBeNull = true;
+      }
+    }
+    return DerefBytes;
+  }
+
+  if (auto CS = ImmutableCallSite(this)) {
+    DerefBytes = CS.getDereferenceableBytes(0);
+    if (DerefBytes == 0) {
+      DerefBytes = CS.getDereferenceableOrNullBytes(0);
+      CanBeNull = true;
+    }
+    return DerefBytes;
+  }
+
+  if (const LoadInst *LI = dyn_cast<LoadInst>(this)) {
+    if (MDNode *MD = LI->getMetadata(LLVMContext::MD_dereferenceable)) {
+      ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
+      DerefBytes = CI->getLimitedValue();
+    }
+    if (DerefBytes == 0) {
+      if (MDNode *MD =
+              LI->getMetadata(LLVMContext::MD_dereferenceable_or_null)) {
+        ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
+        DerefBytes = CI->getLimitedValue();
+      }
+      CanBeNull = true;
+    }
+    return DerefBytes;
+  }
+
+  return 0;
+}
+
 Value *Value::DoPHITranslation(const BasicBlock *CurBB,
                                const BasicBlock *PredBB) {
   PHINode *PN = dyn_cast<PHINode>(this);
   if (PN && PN->getParent() == CurBB)
     return PN->getIncomingValueForBlock(PredBB);
   return this;
 }