Reduce dependence on pointee types when deducing dereferenceability

[sanjoy]

Summary

Change some of the internal interfaces in Loads.cpp to keep track of the
number of bytes we're trying to prove dereferenceable using an explicit
Size parameter.

Before this, the Size parameter was implicitly inferred from the
pointee type of the pointer whose dereferenceability we were trying to
prove, causing us to be conservative around bitcasts. This was
unfortunate since bitcast instructions are no-ops and should never
break optimizations. With an explicit Size parameter, we're more
precise (as shown in the test cases), and the code is simpler.

We should eventually move towards a DerefQuery struct that groups
together a base pointer, an offset, a size and an alignment; but this
patch is a first step.

[apilipenko]

lib/Analysis/Loads.cpp

145–146

You change the behavior for opaque types here. Is it intentional? Previous version tried to give an answer for the cases where it could guarantee dereferenceability, e.g. load from an opaque typed global. I thought that we even have a test case for that.

If we don't want to support this case anymore, the code can be simplified further. Value::isPointerDereferenceable can be removed, instead we can rely on getPointerDereferenceable to return dereferenceable bytes for the cases now handled by isPointerDereferenceable.

If we do want to support both sized and opaque types it might make sense to separate handling into two functions, one for sized one for non-sized.

[sanjoy]

lib/Analysis/Loads.cpp

145–146

This wasn't intentional, but I also don't remember any upstream llvm-lit tests failing (which is why I thought the change was harmless). I'll take a closer look tomorrow.

[sanjoy]

lib/Analysis/Loads.cpp

145–146

Hi Artur,

I've "fixed" this issue by defining unsized loads and stores as illegal in http://reviews.llvm.org/rL271402

[apilipenko]

LGTM. As I mentioned, since we don't support opaque types here, we don't need isPointerDereferenceable. Corresponding logic should be moved to getPointerDereferenceableBytes.

lib/Analysis/Loads.cpp

 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/Statepoint.h"
 
 using namespace llvm;
 
-static bool isDereferenceableFromAttribute(const Value *BV, APInt Offset,
-                                           Type *Ty, const DataLayout &DL,
+static bool isDereferenceableFromAttribute(const Value *BV, APInt Size,
+                                           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");
-
   bool CheckForNonNull = false;
-  APInt DerefBytes(Offset.getBitWidth(),
+  APInt DerefBytes(Size.getBitWidth(),
                    BV->getPointerDereferenceableBytes(CheckForNonNull));
 
   if (DerefBytes.getBoolValue())
-    if (DerefBytes.uge(Offset + DL.getTypeStoreSize(Ty)))
+    if (DerefBytes.uge(Size))
       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,
                       const DataLayout &DL) {
   APInt BaseAlign(Offset.getBitWidth(), Base->getPointerAlignment(DL));
 
   if (!BaseAlign) {
     Type *Ty = Base->getType()->getPointerElementType();
     if (!Ty->isSized())
       return false;
static bool isAligned(const Value *Base, unsigned Align, const DataLayout &DL) {
   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 Value *V, unsigned Align, APInt Size, 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.
 
   bool CheckForNonNull;
   if (V->isPointerDereferenceable(CheckForNonNull)) {
+    Type *ETy = V->getType()->getPointerElementType();
+    if (ETy->isSized() && Size.ule(DL.getTypeStoreSize(ETy))) {
       if (CheckForNonNull && !isKnownNonNullAt(V, CtxI, DT, TLI))
         return false;
       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);
   }
 
-  if (isDereferenceableFromAttribute(V, DL, CtxI, DT, TLI))
+  // bitcast instructions are no-ops as far as dereferenceability is concerned.
+  if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V))
+    return isDereferenceableAndAlignedPointer(BC->getOperand(0), Align, Size,
+                                              DL, CtxI, DT, TLI, Visited);
+
+  if (isDereferenceableFromAttribute(V, Size, 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 *Ty = GEP->getResultElementType();
     const Value *Base = GEP->getPointerOperand();
 
-    // 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;
-
     APInt Offset(DL.getPointerTypeSizeInBits(GEP->getType()), 0);
-    if (!GEP->accumulateConstantOffset(DL, Offset))
+    if (!GEP->accumulateConstantOffset(DL, Offset) || Offset.isNegative() ||
+        !Offset.urem(APInt(Offset.getBitWidth(), Align)).isMinValue())
       return false;
 
-    // Check if the load is within the bounds of the underlying object
-    // and offset is aligned.
-    uint64_t LoadSize = DL.getTypeStoreSize(Ty);
-    Type *BaseType = GEP->getSourceElementType();
-    assert(isPowerOf2_32(Align) && "must be a power of 2!");
-    return (Offset + LoadSize).ule(DL.getTypeAllocSize(BaseType)) &&
-           !(Offset & APInt(Offset.getBitWidth(), Align-1));
+    // If the base pointer is dereferenceable for Offset+Size bytes, then the
+    // GEP (== Base + Offset) is dereferenceable for Size bytes.  If the base
+    // pointer is aligned to Align bytes, and the Offset is divisible by Align
+    // then the GEP (== Base + Offset == k_0 * Align + k_1 * Align) is also
+    // aligned to Align bytes.
+
+    return Visited.insert(Base).second &&
+           isDereferenceableAndAlignedPointer(Base, Align, Offset + Size, DL,
+                                              CtxI, DT, TLI, Visited);
   }
 
   // For gc.relocate, look through relocations
   if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V))
     return isDereferenceableAndAlignedPointer(
-        RelocateInst->getDerivedPtr(), Align, DL, CtxI, DT, TLI, Visited);
+        RelocateInst->getDerivedPtr(), Align, Size, DL, CtxI, DT, TLI, Visited);
 
   if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V))
-    return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Align, DL,
-                                              CtxI, DT, TLI, Visited);
+    return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Align, Size,
+                                              DL, CtxI, DT, TLI, Visited);
 
   // If we don't know, assume the worst.
   return false;
 }
 
 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;
-  }
+  if (!Ty->isSized())
+    return false;
 
   SmallPtrSet<const Value *, 32> Visited;
-  return ::isDereferenceableAndAlignedPointer(V, Align, DL, CtxI, DT, TLI,
-                                              Visited);
+  return ::isDereferenceableAndAlignedPointer(
+      V, Align, APInt(DL.getTypeSizeInBits(VTy), DL.getTypeStoreSize(Ty)), DL,
+      CtxI, DT, TLI, Visited);
 }
 
 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);
 }

test/Analysis/ValueTracking/deref-bitcast-of-gep.ll

+; RUN: opt -S -licm < %s | FileCheck %s
+
+; Note: the !invariant.load is there just solely to let us call @use()
+; to add a fake use, and still have the aliasing work out.  The call
+; to @use(0) is just to provide a may-unwind exit out of the loop, so
+; that LICM cannot hoist out the load simply because it is guaranteed
+; to execute.
+
+declare void @use(i32)
+
+define void @f_0(i8* align 4 dereferenceable(1024) %ptr) {
+; CHECK-LABEL: @f_0(
+; CHECK: entry:
+; CHECK:  %val = load i32, i32* %ptr.i32
+; CHECK:  br label %loop
+; CHECK: loop:
+; CHECK:  call void @use(i32 0)
+; CHECK-NEXT:  call void @use(i32 %val)
+
+
+entry:
+  %ptr.gep = getelementptr i8, i8* %ptr, i32 32
+  %ptr.i32 = bitcast i8* %ptr.gep to i32*
+  br label %loop
+
+loop:
+  call void @use(i32 0)
+  %val = load i32, i32* %ptr.i32, !invariant.load !{}
+  call void @use(i32 %val)
+  br label %loop
+}
+
+define void @f_1(i8* align 4 dereferenceable_or_null(1024) %ptr) {
+; CHECK-LABEL: @f_1(
+entry:
+  %ptr.gep = getelementptr i8, i8* %ptr, i32 32
+  %ptr.i32 = bitcast i8* %ptr.gep to i32*
+  %ptr_is_null = icmp eq i8* %ptr, null
+  br i1 %ptr_is_null, label %leave, label %loop
+
+; CHECK: loop.preheader:
+; CHECK:   %val = load i32, i32* %ptr.i32
+; CHECK:   br label %loop
+; CHECK: loop:
+; CHECK:  call void @use(i32 0)
+; CHECK-NEXT:  call void @use(i32 %val)
+
+loop:
+  call void @use(i32 0)
+  %val = load i32, i32* %ptr.i32, !invariant.load !{}
+  call void @use(i32 %val)
+  br label %loop
+
+leave:
+  ret void
+}
+
+define void @f_2(i8* align 4 dereferenceable_or_null(1024) %ptr) {
+; CHECK-LABEL: @f_2(
+; CHECK-NOT: load
+; CHECK:  call void @use(i32 0)
+; CHECK-NEXT:  %val = load i32, i32* %ptr.i32, !invariant.load !0
+; CHECK-NEXT:  call void @use(i32 %val)
+
+entry:
+  ;; Can't hoist, since the alignment does not work out -- (<4 byte
+  ;; aligned> + 30) is not necessarily 4 byte aligned.
+
+  %ptr.gep = getelementptr i8, i8* %ptr, i32 30
+  %ptr.i32 = bitcast i8* %ptr.gep to i32*
+  %ptr_is_null = icmp eq i8* %ptr, null
+  br i1 %ptr_is_null, label %leave, label %loop
+
+loop:
+  call void @use(i32 0)
+  %val = load i32, i32* %ptr.i32, !invariant.load !{}
+  call void @use(i32 %val)
+  br label %loop
+
+leave:
+  ret void
+}