[Attributor] Really use the executed-context

[jdoerfert]

Summary

Before we did not follow casts and geps when we looked at the users of a
pointer in the pointers must-be-executed-context. This caused us to fail
to determine if it was accessed for sure. With this change we follow
such users now.

The above extension exposed problems in getKnownNonNullAndDerefBytesForUse
which did not always check what the base pointer was. We also did not
handle negative offsets as conservative as we have to without explicit
loop handling. Finally, we should not derive a huge number if we access
a pointer that was traversed backwards first.

The problems exposed by this functional change are already tested in the
existing test cases as is the functional change.

[jdoerfert]

I'll reupload later with full context (sorry)

[jdoerfert]

Upload with full context and additional test

[jdoerfert]

llvm/test/Transforms/InferFunctionAttrs/dereferenceable.ll

-3

leftover, will be removed.

[lebedev.ri]

Thanks for looking into this!
I'm not really familiar with internals of Attributor so i'll leave the review to @uenoku / @sstefan1.

[uenoku]

LGTM

llvm/lib/Transforms/IPO/Attributor.cpp

1553–1558

It might be better to insert early returns to these blocks

llvm/lib/Transforms/IPO/Attributor.cpp

ChangeStatus updateImpl(Attributor &A) override {
     auto &S = this->getState();
     Instruction *CtxI = this->getIRPosition().getCtxI();
     if (!CtxI)
       return ChangeStatus::UNCHANGED;
 
     MustBeExecutedContextExplorer &Explorer =
         A.getInfoCache().getMustBeExecutedContextExplorer();
 
-    SetVector<const Use *> NextUses;
-
     auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI);
-    for (const Use *U : Uses) {
+    for (unsigned u = 0 ; u < Uses.size(); ++u) {
+      const Use *U = Uses[u];
       if (const Instruction *UserI = dyn_cast<Instruction>(U->getUser())) {
         bool Found = Explorer.findInContextOf(UserI, EIt, EEnd);
         if (Found && Base::followUse(A, U, UserI))
           for (const Use &Us : UserI->uses())
-            NextUses.insert(&Us);
+            Uses.insert(&Us);
       }
     }
-    for (const Use *U : NextUses)
-      Uses.insert(U);
 
     return BeforeState == S ? ChangeStatus::UNCHANGED : ChangeStatus::CHANGED;
   }
 
 private:
   /// Container for (transitive) uses of the associated value.
   SetVector<const Use *> Uses;
 };
if (ImmutableCallSite ICS = ImmutableCallSite(I)) {
 
     unsigned ArgNo = ICS.getArgumentNo(U);
     IRPosition IRP = IRPosition::callsite_argument(ICS, ArgNo);
     auto &DerefAA = A.getAAFor<AADereferenceable>(QueryingAA, IRP);
     IsNonNull |= DerefAA.isKnownNonNull();
     return DerefAA.getKnownDereferenceableBytes();
   }
 
+  // We need to follow common pointer manipulation uses to the accesses they
+  // feed into. We can try to be smart to avoid looking through things we do not
+  // like for now, e.g., non-inbounds GEPs.
+  if (isa<CastInst>(I)) {
+    TrackUse = true;
+    return 0;
+  }
+  if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
+    if (GEP->hasAllZeroIndices() ||
+        (GEP->isInBounds() && GEP->hasAllConstantIndices())) {
+      TrackUse = true;
+      return 0;
+    }
+
   int64_t Offset;
   if (const Value *Base = getBasePointerOfAccessPointerOperand(I, Offset, DL)) {
     if (Base == &AssociatedValue && getPointerOperand(I) == UseV) {
       int64_t DerefBytes =
-          Offset + (int64_t)DL.getTypeStoreSize(PtrTy->getPointerElementType());
+          (int64_t)DL.getTypeStoreSize(PtrTy->getPointerElementType()) + Offset;
 
       IsNonNull |= !NullPointerIsDefined;
-      return DerefBytes;
+      return std::max(int64_t(0), DerefBytes);
     }
   }
   if (const Value *Base =
           GetPointerBaseWithConstantOffset(UseV, Offset, DL,
                                            /*AllowNonInbounds*/ false)) {
+    if (Base == &AssociatedValue) {
       auto &DerefAA =
           A.getAAFor<AADereferenceable>(QueryingAA, IRPosition::value(*Base));
       IsNonNull |= (!NullPointerIsDefined && DerefAA.isKnownNonNull());
       IsNonNull |= (!NullPointerIsDefined && (Offset != 0));
       int64_t DerefBytes = DerefAA.getKnownDereferenceableBytes();
-    return std::max(int64_t(0), DerefBytes - Offset);
+      return std::max(int64_t(0), DerefBytes - std::max(int64_t(0), Offset));
+    }
   }
 
   return 0;
 }
 
 struct AANonNullImpl : AANonNull {
   AANonNullImpl(const IRPosition &IRP)
       : AANonNull(IRP),
         NullIsDefined(NullPointerIsDefined(
             getAnchorScope(),
             getAssociatedValue().getType()->getPointerAddressSpace())) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     if (!NullIsDefined &&
         hasAttr({Attribute::NonNull, Attribute::Dereferenceable}))
       indicateOptimisticFixpoint();
+    else if (isa<ConstantPointerNull>(getAssociatedValue()))
+      indicatePessimisticFixpoint();
     else
       AANonNull::initialize(A);
   }
 
   /// See AAFromMustBeExecutedContext
   bool followUse(Attributor &A, const Use *U, const Instruction *I) {
     bool IsNonNull = false;
     bool TrackUse = false;

llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll

 }
 
 ; TEST SCC with various calls, casts, and comparisons agains NULL
 ;
 ; CHECK: define dereferenceable_or_null(4) float* @scc_A(i32* readnone returned dereferenceable_or_null(4) "no-capture-maybe-returned" %a)
 ;
 ; CHECK: define dereferenceable_or_null(8) i64* @scc_B(double* readnone returned dereferenceable_or_null(8) "no-capture-maybe-returned" %a)
 ;
-; CHECK: define dereferenceable_or_null(2) i8* @scc_C(i16* readnone returned dereferenceable_or_null(2) "no-capture-maybe-returned" %a)
+; CHECK: define dereferenceable_or_null(4) i8* @scc_C(i16* readnone returned dereferenceable_or_null(4) "no-capture-maybe-returned" %a)
 ;
 ; float *scc_A(int *a) {
 ;   return (float*)(a ? (int*)scc_A((int*)scc_B((double*)scc_C((short*)a))) : a);
 ; }
 ;
 ; long *scc_B(double *a) {
 ;   return (long*)(a ? scc_C((short*)scc_B((double*)scc_A((int*)a))) : a);
 ; }

 ; TEST "captured" only through return
 ;
 ; long *not_captured_but_returned_1(long *a) {
 ;   *(a+1) = 1;
 ;   return a + 1;
 ; }
 ;
 ; There should *not* be a no-capture attribute on %a
-; CHECK: define nonnull i64* @not_captured_but_returned_1(i64* writeonly "no-capture-maybe-returned" %a)
+; CHECK: define nonnull dereferenceable(8) i64* @not_captured_but_returned_1(i64* nonnull writeonly dereferenceable(16) "no-capture-maybe-returned" %a)
 define i64* @not_captured_but_returned_1(i64* %a) #0 {
 entry:
   %add.ptr = getelementptr inbounds i64, i64* %a, i64 1
   store i64 1, i64* %add.ptr, align 8
   ret i64* %add.ptr
 }
 
 ; TEST calls to "captured" only through return functions

 
 ; TEST "captured" only through transitive return
 ;
 ; long* negative_test_not_captured_but_returned_call_1a(long *a) {
 ;   return not_captured_but_returned_1(a);
 ; }
 ;
 ; There should *not* be a no-capture attribute on %a
-; CHECK: define nonnull i64* @negative_test_not_captured_but_returned_call_1a(i64* writeonly "no-capture-maybe-returned" %a)
+; CHECK: define nonnull dereferenceable(8) i64* @negative_test_not_captured_but_returned_call_1a(i64* writeonly "no-capture-maybe-returned" %a)
 define i64* @negative_test_not_captured_but_returned_call_1a(i64* %a) #0 {
 entry:
   %call = call i64* @not_captured_but_returned_1(i64* %a)
   ret i64* %call
 }
 
 ; TEST captured through write
 ;

llvm/test/Transforms/FunctionAttrs/dereferenceable.ll

 ; GEP inbounds
 define i32* @test3_1(i32* dereferenceable(8) %0) local_unnamed_addr {
 ; ATTRIBUTOR: define nonnull dereferenceable(4) i32* @test3_1(i32* nonnull readnone dereferenceable(8) "no-capture-maybe-returned" %0)
   %ret = getelementptr inbounds i32, i32* %0, i64 1
   ret i32* %ret
 }
 
 define i32* @test3_2(i32* dereferenceable_or_null(32) %0) local_unnamed_addr {
-; FIXME: Argument should be mark dereferenceable because of GEP `inbounds`.
-; ATTRIBUTOR: define nonnull dereferenceable(16) i32* @test3_2(i32* readnone dereferenceable_or_null(32) "no-capture-maybe-returned" %0)
+; FIXME: We should not have both deref(x) and deref_or_null(y) with x >= y.
+; ATTRIBUTOR: define nonnull dereferenceable(16) i32* @test3_2(i32* nonnull readnone dereferenceable(32) dereferenceable_or_null(32) "no-capture-maybe-returned" %0)
   %ret = getelementptr inbounds i32, i32* %0, i64 4
   ret i32* %ret
 }
 
 define i32* @test3_3(i32* dereferenceable(8) %0, i32* dereferenceable(16) %1, i1 %2) local_unnamed_addr {
 ; ATTRIBUTOR: define nonnull dereferenceable(4) i32* @test3_3(i32* nonnull readnone dereferenceable(8) "no-capture-maybe-returned" %0, i32* nonnull readnone dereferenceable(16) "no-capture-maybe-returned" %1, i1 %2) local_unnamed_addr
   %ret1 = getelementptr inbounds i32, i32* %0, i64 1
   %ret2 = getelementptr inbounds i32, i32* %1, i64 2

 define i32* @f7_3() {
 ; ATTRIBUTOR: define nonnull dereferenceable(4) i32* @f7_3()
   %ptr = tail call i32* @unkown_ptr()
   store i32 10, i32* %ptr, align 16
   ret i32* %ptr
 }
 
 define i32* @test_for_minus_index(i32* %p) {
-; FIXME: This should be define nonnull dereferenceable(8) i32* @test_for_minus_index(i32* nonnull %p)
-; ATTRIBUTOR: define nonnull dereferenceable(8) i32* @test_for_minus_index(i32* writeonly "no-capture-maybe-returned" %p)
+; FIXME: This should have a return dereferenceable(8) but we need to make sure it will work in loops as well.
+; ATTRIBUTOR: define nonnull i32* @test_for_minus_index(i32* nonnull writeonly "no-capture-maybe-returned" %p)
   %q = getelementptr inbounds i32, i32* %p, i32 -2
   store i32 1, i32* %q
   ret i32* %q
 }

llvm/test/Transforms/FunctionAttrs/nocapture.ll

 }
 
 ; EITHER: define i1 @captureICmpRev(i32* readnone %x)
 define i1 @captureICmpRev(i32* %x) {
   %1 = icmp eq i32* null, %x
   ret i1 %1
 }
 
-; EITHER: define i1 @nocaptureInboundsGEPICmp(i32* nocapture readnone %x)
+; FNATTR: define i1 @nocaptureInboundsGEPICmp(i32* nocapture readnone %x)
+; ATTRIBUTOR: define i1 @nocaptureInboundsGEPICmp(i32* nocapture nonnull readnone %x)
 define i1 @nocaptureInboundsGEPICmp(i32* %x) {
   %1 = getelementptr inbounds i32, i32* %x, i32 5
   %2 = bitcast i32* %1 to i8*
   %3 = icmp eq i8* %2, null
   ret i1 %3
 }
 
-; EITHER: define i1 @nocaptureInboundsGEPICmpRev(i32* nocapture readnone %x)
+; FNATTR: define i1 @nocaptureInboundsGEPICmpRev(i32* nocapture readnone %x)
+; ATTRIBUTOR: define i1 @nocaptureInboundsGEPICmpRev(i32* nocapture nonnull readnone %x)
 define i1 @nocaptureInboundsGEPICmpRev(i32* %x) {
   %1 = getelementptr inbounds i32, i32* %x, i32 5
   %2 = bitcast i32* %1 to i8*
   %3 = icmp eq i8* null, %2
   ret i1 %3
 }
 
 ; EITHER: define i1 @nocaptureDereferenceableOrNullICmp(i32* nocapture readnone dereferenceable_or_null(4) %x)

llvm/test/Transforms/FunctionAttrs/nosync.ll

 ; TEST 1
 ; non-convergent and readnone implies nosync
 %struct.RT = type { i8, [10 x [20 x i32]], i8 }
 %struct.ST = type { i32, double, %struct.RT }
 
 ; FNATTR: Function Attrs: norecurse nounwind optsize readnone ssp uwtable
 ; FNATTR-NEXT: define nonnull i32* @foo(%struct.ST* readnone %s)
 ; ATTRIBUTOR: Function Attrs: nofree nosync nounwind optsize readnone ssp uwtable
-; ATTRIBUTOR-NEXT: define nonnull i32* @foo(%struct.ST* readnone "no-capture-maybe-returned" %s)
+; ATTRIBUTOR-NEXT: define nonnull i32* @foo(%struct.ST* nonnull readnone "no-capture-maybe-returned" %s)
 define i32* @foo(%struct.ST* %s) nounwind uwtable readnone optsize ssp {
 entry:
   %arrayidx = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 1, i32 2, i32 1, i64 5, i64 13
   ret i32* %arrayidx
 }
 
 ; TEST 2
 ; atomic load with monotonic ordering

 ; }
 
 %"struct.std::atomic" = type { %"struct.std::__atomic_base" }
 %"struct.std::__atomic_base" = type { i8 }
 
 ; FNATTR: Function Attrs: nofree norecurse nounwind
 ; FNATTR-NEXT: define void @foo1(i32* nocapture %0, %"struct.std::atomic"* nocapture %1)
 ; ATTRIBUTOR-NOT: nosync
-; ATTRIBUTOR: define void @foo1(i32* nocapture nonnull writeonly dereferenceable(4) %0, %"struct.std::atomic"* nocapture writeonly %1)
+; ATTRIBUTOR: define void @foo1(i32* nocapture nonnull writeonly dereferenceable(4) %0, %"struct.std::atomic"* nocapture nonnull writeonly dereferenceable(1) %1)
 
 define void @foo1(i32* %0, %"struct.std::atomic"* %1) {
   store i32 100, i32* %0, align 4
   fence release
   %3 = getelementptr inbounds %"struct.std::atomic", %"struct.std::atomic"* %1, i64 0, i32 0, i32 0
   store atomic i8 1, i8* %3 monotonic, align 1
   ret void
 }
 
 ; FNATTR: Function Attrs: nofree norecurse nounwind
 ; FNATTR-NEXT: define void @bar(i32* nocapture readnone %0, %"struct.std::atomic"* nocapture readonly %1)
 ; ATTRIBUTOR-NOT: nosync
-; ATTRIBUTOR: define void @bar(i32* nocapture readnone %0, %"struct.std::atomic"* nocapture readonly %1)
+; ATTRIBUTOR: define void @bar(i32* nocapture readnone %0, %"struct.std::atomic"* nocapture nonnull readonly dereferenceable(1) %1)
 define void @bar(i32* %0, %"struct.std::atomic"* %1) {
   %3 = getelementptr inbounds %"struct.std::atomic", %"struct.std::atomic"* %1, i64 0, i32 0, i32 0
   br label %4
 
 4:                                                ; preds = %4, %2
   %5 = load atomic i8, i8* %3  monotonic, align 1
   %6 = and i8 %5, 1
   %7 = icmp eq i8 %6, 0
   br i1 %7, label %4, label %8
 
 8:                                                ; preds = %4
   fence acquire
   ret void
 }
 
 ; TEST 13 - Fence syncscope("singlethread") seq_cst
 ; FNATTR: Function Attrs: nofree norecurse nounwind
 ; FNATTR-NEXT: define void @foo1_singlethread(i32* nocapture %0, %"struct.std::atomic"* nocapture %1)
 ; ATTRIBUTOR: Function Attrs: nofree nosync nounwind willreturn
-; ATTRIBUTOR: define void @foo1_singlethread(i32* nocapture nonnull writeonly dereferenceable(4) %0, %"struct.std::atomic"* nocapture writeonly %1)
+; ATTRIBUTOR: define void @foo1_singlethread(i32* nocapture nonnull writeonly dereferenceable(4) %0, %"struct.std::atomic"* nocapture nonnull writeonly dereferenceable(1) %1)
 
 define void @foo1_singlethread(i32* %0, %"struct.std::atomic"* %1) {
   store i32 100, i32* %0, align 4
   fence syncscope("singlethread") release
   %3 = getelementptr inbounds %"struct.std::atomic", %"struct.std::atomic"* %1, i64 0, i32 0, i32 0
   store atomic i8 1, i8* %3 monotonic, align 1
   ret void
 }
 
 ; FNATTR: Function Attrs: nofree norecurse nounwind
 ; FNATTR-NEXT: define void @bar_singlethread(i32* nocapture readnone %0, %"struct.std::atomic"* nocapture readonly %1)
 ; ATTRIBUTOR: Function Attrs: nofree nosync nounwind
-; ATTRIBUTOR: define void @bar_singlethread(i32* nocapture readnone %0, %"struct.std::atomic"* nocapture readonly %1)
+; ATTRIBUTOR: define void @bar_singlethread(i32* nocapture readnone %0, %"struct.std::atomic"* nocapture nonnull readonly dereferenceable(1) %1)
 define void @bar_singlethread(i32* %0, %"struct.std::atomic"* %1) {
   %3 = getelementptr inbounds %"struct.std::atomic", %"struct.std::atomic"* %1, i64 0, i32 0, i32 0
   br label %4
 
 4:                                                ; preds = %4, %2
   %5 = load atomic i8, i8* %3  monotonic, align 1
   %6 = and i8 %5, 1
   %7 = icmp eq i8 %6, 0

llvm/test/Transforms/InferFunctionAttrs/dereferenceable.ll

 ; RUN: opt < %s -inferattrs -S | FileCheck %s
 ; RUN: opt < %s -attributor --attributor-disable=false -S | FileCheck %s --check-prefix=ATTRIBUTOR
 
 
 
 ; Determine dereference-ability before unused loads get deleted:
 ; https://bugs.llvm.org/show_bug.cgi?id=21780
 
 define <4 x double> @PR21780(double* %ptr) {
 ; CHECK-LABEL: @PR21780(double* %ptr)
-; FIXME: this should be @PR21780(double* nonnull dereferenceable(32) %ptr) 
-;        trakcing use of GEP in Attributor would fix this problem.
-; ATTRIBUTOR-LABEL: @PR21780(double* nocapture nonnull readonly dereferenceable(8) %ptr)
+; ATTRIBUTOR-LABEL: @PR21780(double* nocapture nonnull readonly dereferenceable(32) %ptr)
 
   ; GEP of index 0 is simplified away.
   %arrayidx1 = getelementptr inbounds double, double* %ptr, i64 1
   %arrayidx2 = getelementptr inbounds double, double* %ptr, i64 2
   %arrayidx3 = getelementptr inbounds double, double* %ptr, i64 3
 
   %t0 = load double, double* %ptr, align 8
   %t1 = load double, double* %arrayidx1, align 8
   %t2 = load double, double* %arrayidx2, align 8
   %t3 = load double, double* %arrayidx3, align 8
 
   %vecinit0 = insertelement <4 x double> undef, double %t0, i32 0
   %vecinit1 = insertelement <4 x double> %vecinit0, double %t1, i32 1
   %vecinit2 = insertelement <4 x double> %vecinit1, double %t2, i32 2
   %vecinit3 = insertelement <4 x double> %vecinit2, double %t3, i32 3
   %shuffle = shufflevector <4 x double> %vecinit3, <4 x double> %vecinit3, <4 x i32> <i32 0, i32 0, i32 2, i32 2>
   ret <4 x double> %shuffle
 }
 
 
 define double @PR21780_only_access3_with_inbounds(double* %ptr) {
 ; CHECK-LABEL: @PR21780_only_access3_with_inbounds(double* %ptr)
-; FIXME: this should be @PR21780_only_access3_with_inbounds(double* nonnull dereferenceable(32) %ptr)
-;        trakcing use of GEP in Attributor would fix this problem.
-; ATTRIBUTOR-LABEL: @PR21780_only_access3_with_inbounds(double* nocapture readonly %ptr) 
+; ATTRIBUTOR-LABEL: @PR21780_only_access3_with_inbounds(double* nocapture nonnull readonly dereferenceable(32) %ptr)
 
   %arrayidx3 = getelementptr inbounds double, double* %ptr, i64 3
   %t3 = load double, double* %arrayidx3, align 8
   ret double %t3
 }
 
 define double @PR21780_only_access3_without_inbounds(double* %ptr) {
 ; CHECK-LABEL: @PR21780_only_access3_without_inbounds(double* %ptr)