Minor refactoring of GEP handling in isDereferenceablePointer

[apilipenko]

Summary

For GEP instructions isDereferenceablePointer checks that all indices are constant and within bounds. Replace this index calculation logic to a call to accumulateConstantOffset. Separated from the D9791.

[apilipenko]

Ping.

[reames]

Artur, I'm a bit confused on what this code is trying to accomplish. First, is this intended to be an NFC change? If not, where's the test case?

It appears like this is basically trying to infer the "inbounds" property on GEPs. I'm sure we have some code for this in InstCombine, have you looked there to see what it does? Having a function of the form isInboundsGEP(GetElementPointer *GEP) which is used from both places might be a good factoring.

[sanjoy]

I'm not sure that this is an NFC change -- I think the previous code will return false on the %1 below while the new code will return true.

%struct.A = type { [8 x i8], [5 x i8] }

define i8 @f(%struct.A* %a) {
  %1 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 0, i64 10
  %2 = load i8, i8* %1
  ret i8 %2
}

Please add a test case that shows this difference.

lib/Analysis/ValueTracking.cpp

2987 ↗

(On Diff #26134)

LLVM style is Type *.

2989 ↗

(On Diff #26134)

Can we simplify this to return (Offset + LoadSize).ule(DL.getTypeAllocSize(BaseType))?

[apilipenko]

Philip, the change was separated from D9791 by Sanjoy's suggestion. To take alignment into account I need to know GEP's offset. That was intended to be a NFC, but it turned out to be not.

Sanjoy, you are right, it will give another result for your code. I think it's OK as long as we stay within the underlying object size. Will add a test case.

[apilipenko]

Address review findings

[reames]

I'm deferring to Sanjoy because I don't understand the context of the patch. Sanjoy, can you comment?

[sanjoy]

test/Analysis/ValueTracking/memory-dereferenceable.ll

63 ↗

(On Diff #26776)

I'd call this %within_allocation or something like that, to prevent confusion with the inbounds attribute (which is not what we're testing here).

llvm/trunk/lib/Analysis/ValueTracking.cpp

if (const Argument *A = dyn_cast<Argument>(V))
     if (A->hasByValAttr())
       return true;
     
   if (isDereferenceableFromAttribute(V, DL, CtxI, DT, TLI))
     return true;
 
   // 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();
+
     // Conservatively require that the base pointer be fully dereferenceable.
-    if (!Visited.insert(GEP->getOperand(0)).second)
+    if (!Visited.insert(Base).second)
       return false;
-    if (!isDereferenceablePointer(GEP->getOperand(0), DL, CtxI,
+    if (!isDereferenceablePointer(Base, DL, CtxI,
                                   DT, TLI, Visited))
       return false;
-    // Check the indices.
-    gep_type_iterator GTI = gep_type_begin(GEP);
-    for (User::const_op_iterator I = GEP->op_begin()+1,
-         E = GEP->op_end(); I != E; ++I) {
-      Value *Index = *I;
-      Type *Ty = *GTI++;
-      // Struct indices can't be out of bounds.
-      if (isa<StructType>(Ty))
-        continue;
-      ConstantInt *CI = dyn_cast<ConstantInt>(Index);
-      if (!CI)
-        return false;
-      // Zero is always ok.
-      if (CI->isZero())
-        continue;
-      // Check to see that it's within the bounds of an array.
-      ArrayType *ATy = dyn_cast<ArrayType>(Ty);
-      if (!ATy)
-        return false;
-      if (CI->getValue().getActiveBits() > 64)
-        return false;
-      if (CI->getZExtValue() >= ATy->getNumElements())
-        return false;
-    }
-    // Indices check out; this is dereferenceable.
-    return true;
+    
+    APInt Offset(DL.getPointerTypeSizeInBits(VTy), 0);
+    if (!GEP->accumulateConstantOffset(DL, Offset))
+    
+    // Check if the load is within the bounds of the underlying object.
+    uint64_t LoadSize = DL.getTypeStoreSize(Ty);
+    Type *BaseType = Base->getType()->getPointerElementType();
+    return (Offset + LoadSize).ule(DL.getTypeAllocSize(BaseType));
   }
 
   // For gc.relocate, look through relocations
   if (const IntrinsicInst *I = dyn_cast<IntrinsicInst>(V))
     if (I->getIntrinsicID() == Intrinsic::experimental_gc_relocate) {
       GCRelocateOperands RelocateInst(I);
       return isDereferenceablePointer(RelocateInst.getDerivedPtr(), DL, CtxI,
                                       DT, TLI, Visited);

llvm/trunk/test/Analysis/ValueTracking/memory-dereferenceable.ll

 ; RUN: opt -print-memderefs -analyze -S <%s | FileCheck %s
 
 ; Uses the print-deref (+ analyze to print) pass to run
 ; isDereferenceablePointer() on many load instruction operands
 
 target datalayout = "e"
 
 declare zeroext i1 @return_i1()
 
 @globalstr = global [6 x i8] c"hello\00"
 @globali32ptr = external global i32*
 
+%struct.A = type { [8 x i8], [5 x i8] }
+@globalstruct = external global %struct.A
+
 define void @test(i32 addrspace(1)* dereferenceable(8) %dparam) gc "statepoint-example" {
 ; CHECK: The following are dereferenceable:
 ; CHECK: %globalptr
 ; CHECK: %alloca
 ; CHECK: %dparam
 ; CHECK: %relocate
 ; CHECK-NOT: %nparam
 ; CHECK-NOT: %nd_load
 ; CHECK: %d4_load
 ; CHECK-NOT: %d2_load
 ; CHECK-NOT: %d_or_null_load
 ; CHECK: %d_or_null_non_null_load
+; CHECK: %within_allocation
+; CHECK-NOT: %outside_allocation
 entry:
     %globalptr = getelementptr inbounds [6 x i8], [6 x i8]* @globalstr, i32 0, i32 0
     %load1 = load i8, i8* %globalptr
     %alloca = alloca i1
     %load2 = load i1, i1* %alloca
     %load3 = load i32, i32 addrspace(1)* %dparam
     %tok = tail call i32 (i64, i32, i1 ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_i1f(i64 0, i32 0, i1 ()* @return_i1, i32 0, i32 0, i32 0, i32 0, i32 addrspace(1)* %dparam)
     %relocate = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(i32 %tok, i32 7, i32 7)
entry:
     ; Load from a potentially null pointer with dereferenceable_or_null
     %d_or_null_load = load i32*, i32** @globali32ptr, !dereferenceable_or_null !0
     %load9 = load i32, i32* %d_or_null_load
 
     ; Load from a non-null pointer with dereferenceable_or_null
     %d_or_null_non_null_load = load i32*, i32** @globali32ptr, !nonnull !2, !dereferenceable_or_null !0
     %load10 = load i32, i32* %d_or_null_non_null_load
 
+    ; It's OK to overrun static array size as long as we stay within underlying object size
+    %within_allocation = getelementptr inbounds %struct.A, %struct.A* @globalstruct, i64 0, i32 0, i64 10
+    %load11 = load i8, i8* %within_allocation
+
+    ; GEP is outside the underlying object size
+    %outside_allocation = getelementptr inbounds %struct.A, %struct.A* @globalstruct, i64 0, i32 1, i64 10
+    %load12 = load i8, i8* %outside_allocation
+
     ret void
 }
 
 declare i32 @llvm.experimental.gc.statepoint.p0f_i1f(i64, i32, i1 ()*, i32, i32, ...)
 declare i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(i32, i32, i32)
 
 !0 = !{i64 4}
 !1 = !{i64 2}
 !2 = !{}