[deref-at-point] restrict inference of dereferenceability based on allocsize attribute

[reames]

Summary

(Patch description completely redone.)

Support deriving dereferenceability facts from allocation sites with known object sizes while correctly accounting for any possibly frees between allocation and use site. (At the moment, that's super conservative and only allowing it in functions where we know we can't free.)

This is part of the work on deref-at-point semantics. I'm making the change unconditional as the miscompile in this case is way too easy to trip by accident, and the optimization was only recently added (by me).

After this lands, the TLI wiring will be done separately in another review. That way a single review isn't both fixing a bug, and enabling further optimization.

[jdoerfert]

FWIW, the conceptual problem was known and D61652 was supposed to address this. We never merged it and we might not need it since we have free now.

[reames]

Rework of patch description, and candidate fix for issue exposed in first WIP.

[reames]

Really should have made sure the last build had fully finished running make check before posting patch...

[jdoerfert]

llvm/lib/Analysis/MemoryBuiltins.cpp

526 ↗

(On Diff #322529)

I think we need to address some of the TODOs to avoid regressions.

[reames]

llvm/lib/Analysis/MemoryBuiltins.cpp

526 ↗

(On Diff #322529)

As stated in the review description, the regression is intentional. As the author of the change being partially reverted, I think this is the right step forward.

[reames]

Rebase over the infrastructure added for deref-at-point semantics. This is effectively unconditionally using deref-at-point, but since if we don't, we have a miscompile actively happening, I'm not too worried about that.

[reames]

While trying to add the test case, ran across something weird. Not sure if the patch is wrong or my brain is just fried. Will take a fresh look tomorrow.

[reames]

Restrict scope further - only fix the existing latent issue w/allocsize.

(Good news, the weirdness from last night was human error.)

[reames]

llvm/test/Transforms/LoopVectorize/X86/load-deref-pred.ll

95

Please ignore these changes. This a result of autogen format change. I have landed a change which includes these, and the next rebase will wipe them out. I'd usually do that now, but build times are substantial given the Value.h change. :)

[reames]

ping

[jdoerfert]

LG, thanks for cleaning this up.

[nikic]

As we don't have any default-enabled nosync inference, doesn't this effectively disable this code entirely (for the default pipeline)?

[reames]

In D95815#2663147, @nikic wrote:

As we don't have any default-enabled nosync inference, doesn't this effectively disable this code entirely (for the default pipeline)?

Not really.

Remember, the currently hooked up code doesn't get the benefit of TLI. (Because doing so immediately broke badly.) As a result, it only handles things which are a) allocas and the like, or b) explicitly marked allocsize. We do take a hit on the allocsize cases - except that the single consumer I know of is a GCd frontend which is special cased in the canBeFreed stuff anyways. If anything, this should give us a net benefit because we can expose the malloc/new cases by adding TLI as a parameter (to be done and reviewed separately.)

llvm/include/llvm/IR/Value.h

public:
   const Value *stripInBoundsOffsets(function_ref<void(const Value *)> Func =
                                         [](const Value *) {}) const;
   inline Value *stripInBoundsOffsets(function_ref<void(const Value *)> Func =
                                   [](const Value *) {}) {
     return const_cast<Value *>(
         static_cast<const Value *>(this)->stripInBoundsOffsets(Func));
   }
 
+  /// Return true if the memory object referred to by V can by freed in the
+  /// scope for which the SSA value defining the allocation is statically
+  /// defined.  E.g.  deallocation after the static scope of a value does not
+  /// count, but a deallocation before that does.
+  bool canBeFreed() const;
+
   /// Returns the number of bytes known to be dereferenceable for the
   /// pointer value.
   ///
   /// If CanBeNull is set by this function the pointer can either be null or be
   /// dereferenceable up to the returned number of bytes.
   ///
   /// IF CanBeFreed is true, the pointer is known to be dereferenceable at
   /// point of definition only.  Caller must prove that allocation is not

llvm/lib/Analysis/Loads.cpp

if (const auto *Call = dyn_cast<CallBase>(V)) {
     // separate recursive walk.
     ObjectSizeOpts Opts;
     // TODO: It may be okay to round to align, but that would imply that
     // accessing slightly out of bounds was legal, and we're currently
     // inconsistent about that.  For the moment, be conservative.
     Opts.RoundToAlign = false;
     Opts.NullIsUnknownSize = true;
     uint64_t ObjSize;
-    // TODO: Plumb through TLI so that malloc routines and such working.
+    // TODO: Plumb through TLI so that malloc routines and such work.
     if (getObjectSize(V, ObjSize, DL, nullptr, Opts)) {
       APInt KnownDerefBytes(Size.getBitWidth(), ObjSize);
       if (KnownDerefBytes.getBoolValue() && KnownDerefBytes.uge(Size) &&
-          isKnownNonZero(V, DL, 0, nullptr, CtxI, DT) &&
-          // TODO: We're currently inconsistent about whether deref(N) is a
-          // global fact or a point in time fact.  Once D61652 eventually
-          // lands, this check will be restricted to the point in time
-          // variant. For that variant, we need to prove that object hasn't
-          // been conditionally freed before ontext instruction - if it has, we
-          // might be hoisting over the inverse conditional and creating a
-          // dynamic use after free. 
-          !PointerMayBeCapturedBefore(V, true, true, CtxI, DT, true)) {
+          isKnownNonZero(V, DL, 0, nullptr, CtxI, DT) && !V->canBeFreed()) {
         // 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. 
         Type *Ty = V->getType();
         assert(Ty->isSized() && "must be sized");
         APInt Offset(DL.getTypeStoreSizeInBits(Ty), 0);
         return isAligned(V, Offset, Alignment, DL);

llvm/lib/IR/Value.cpp

const Value *Value::stripAndAccumulateConstantOffsets(
   return V;
 }
 
 const Value *
 Value::stripInBoundsOffsets(function_ref<void(const Value *)> Func) const {
   return stripPointerCastsAndOffsets<PSK_InBounds>(this, Func);
 }
 
-// Return true if the memory object referred to by V can by freed in the scope
-// for which the SSA value defining the allocation is statically defined.  E.g.
-// deallocation after the static scope of a value does not count.
-static bool canBeFreed(const Value *V) {
-  assert(V->getType()->isPointerTy());
+bool Value::canBeFreed() const {
+  assert(getType()->isPointerTy());
 
   // Cases that can simply never be deallocated
   // *) Constants aren't allocated per se, thus not deallocated either.
-  if (isa<Constant>(V))
+  if (isa<Constant>(this))
     return false;
 
   // Handle byval/byref/sret/inalloca/preallocated arguments.  The storage
   // lifetime is guaranteed to be longer than the callee's lifetime.
-  if (auto *A = dyn_cast<Argument>(V))
+  if (auto *A = dyn_cast<Argument>(this))
     if (A->hasPointeeInMemoryValueAttr())
       return false;
 
   const Function *F = nullptr;
-  if (auto *I = dyn_cast<Instruction>(V))
+  if (auto *I = dyn_cast<Instruction>(this))
     F = I->getFunction();
-  if (auto *A = dyn_cast<Argument>(V))
+  if (auto *A = dyn_cast<Argument>(this))
     F = A->getParent();
 
   if (!F)
     return true;
 
   // A pointer to an object in a function which neither frees, nor can arrange
   // for another thread to free on its behalf, can not be freed in the scope
   // of the function.
bool Value::canBeFreed() const {
   if (!F->hasGC())
     return true;
   
   const auto &GCName = F->getGC();
   const StringRef StatepointExampleName("statepoint-example");
   if (GCName != StatepointExampleName)
     return true;
 
-  auto *PT = cast<PointerType>(V->getType());
+  auto *PT = cast<PointerType>(this->getType());
   if (PT->getAddressSpace() != 1)
     // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
     // GC managed heap.  This must match the same check in
     // RewriteStatepointsForGC (and probably needs better factored.)
     return true;
 
   // It is cheaper to scan for a declaration than to scan for a use in this
   // function.  Note that gc.statepoint is a type overloaded function so the
   // usual trick of requesting declaration of the intrinsic from the module
   // doesn't work.
   for (auto &Fn : *F->getParent())
     if (Fn.getIntrinsicID() == Intrinsic::experimental_gc_statepoint)
       return true;
   return false;
 }
 
-
 uint64_t Value::getPointerDereferenceableBytes(const DataLayout &DL,
                                                bool &CanBeNull,
                                                bool &CanBeFreed) const {
   assert(getType()->isPointerTy() && "must be pointer");
 
   uint64_t DerefBytes = 0;
   CanBeNull = false;
-  CanBeFreed = UseDerefAtPointSemantics && canBeFreed(this);
+  CanBeFreed = UseDerefAtPointSemantics && canBeFreed();
   if (const Argument *A = dyn_cast<Argument>(this)) {
     DerefBytes = A->getDereferenceableBytes();
     if (DerefBytes == 0) {
       // Handle byval/byref/inalloca/preallocated arguments
       if (Type *ArgMemTy = A->getPointeeInMemoryValueType()) {
         if (ArgMemTy->isSized()) {
           // FIXME: Why isn't this the type alloc size?
           DerefBytes = DL.getTypeStoreSize(ArgMemTy).getKnownMinSize();

llvm/test/Transforms/LICM/hoist-alloc.ll

 
 for.end:
   %phi = phi i8 [%res, %loop.latch], [0, %for.body]
   ret i8 %phi
 }
 
 declare noalias i8* @my_alloc(i64) allocsize(0)
 
-; FIXME: While the result shown here is correct for the test case as written,
-; it would require context sensitive reasoning about frees which we don't
-; currently have to reach this result.  So, this is effectively demonstrating
-; a miscompile which needs investigated further.
+; We would need context sensitive reasoning about frees (which we don't
+; don't currently have) to hoist the load in this example.
 define i8 @test_hoist_allocsize() {
 ; CHECK-LABEL: @test_hoist_allocsize(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_RAW:%.*]] = call nonnull i8* @my_alloc(i64 32)
 ; CHECK-NEXT:    call void @init(i8* [[A_RAW]])
 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i8, i8* [[A_RAW]], i32 31
-; CHECK-NEXT:    [[RES:%.*]] = load i8, i8* [[ADDR]], align 1
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    call void @unknown()
+; CHECK-NEXT:    [[RES:%.*]] = load i8, i8* [[ADDR]], align 1
 ; CHECK-NEXT:    call void @use(i8 [[RES]])
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], 200
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 ; CHECK:       for.end:
 ; CHECK-NEXT:    [[RES_LCSSA:%.*]] = phi i8 [ [[RES]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    call void @free(i8* [[A_RAW]])
 ; CHECK-NEXT:    ret i8 [[RES_LCSSA]]
for.body:
   %exitcond = icmp eq i64 %iv.next, 200
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:
   call void @free(i8* %a.raw)
   ret i8 %res
 }
 
-define i8 @test_hoist_allocsize_leak() {
+define i8 @test_hoist_allocsize_leak() nofree nosync {
 ; CHECK-LABEL: @test_hoist_allocsize_leak(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_RAW:%.*]] = call nonnull i8* @my_alloc(i64 32)
 ; CHECK-NEXT:    call void @init(i8* [[A_RAW]])
 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i8, i8* [[A_RAW]], i32 31
 ; CHECK-NEXT:    [[RES:%.*]] = load i8, i8* [[ADDR]], align 1
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:

llvm/test/Transforms/LoopVectorize/X86/load-deref-pred.ll

 ; CHECK-NEXT:    [[PREDPHI18:%.*]] = select <4 x i1> [[TMP19]], <4 x i32> [[WIDE_LOAD15]], <4 x i32> zeroinitializer
 ; CHECK-NEXT:    [[TMP36]] = add <4 x i32> [[VEC_PHI]], [[PREDPHI]]
 ; CHECK-NEXT:    [[TMP37]] = add <4 x i32> [[VEC_PHI4]], [[PREDPHI16]]
 ; CHECK-NEXT:    [[TMP38]] = add <4 x i32> [[VEC_PHI5]], [[PREDPHI17]]
 ; CHECK-NEXT:    [[TMP39]] = add <4 x i32> [[VEC_PHI6]], [[PREDPHI18]]
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 16
 ; CHECK-NEXT:    [[VEC_IND_NEXT]] = add <4 x i64> [[STEP_ADD2]], <i64 4, i64 4, i64 4, i64 4>
 ; CHECK-NEXT:    [[TMP40:%.*]] = icmp eq i64 [[INDEX_NEXT]], 4096
 ; CHECK-NEXT:    br i1 [[TMP40]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    [[BIN_RDX:%.*]] = add <4 x i32> [[TMP37]], [[TMP36]]
 ; CHECK-NEXT:    [[BIN_RDX19:%.*]] = add <4 x i32> [[TMP38]], [[BIN_RDX]]
 ; CHECK-NEXT:    [[BIN_RDX20:%.*]] = add <4 x i32> [[TMP39]], [[BIN_RDX19]]
 ; CHECK-NEXT:    [[TMP41:%.*]] = call i32 @llvm.vector.reduce.add.v4i32(<4 x i32> [[BIN_RDX20]])
 ; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 4096, 4096
 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[LOOP_EXIT:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
loop_exit:
   ret i32 %accum.next
 }
 
 
 ;; Model a custom allocate which allocates in chunks of 8 bytes
 declare align 8 dereferenceable_or_null(8) i8* @my_alloc(i32) allocsize(0)
 declare align 8 dereferenceable_or_null(8) i8* @my_array_alloc(i32, i32) allocsize(0, 1)
 
-define i32 @test_allocsize(i64 %len, i1* %test_base) {
+define i32 @test_allocsize(i64 %len, i1* %test_base) nofree nosync {
 ; CHECK-LABEL: @test_allocsize(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ALLOCATION:%.*]] = call nonnull i8* @my_alloc(i32 16384)
 ; CHECK-NEXT:    [[BASE:%.*]] = bitcast i8* [[ALLOCATION]] to i32*
 ; CHECK-NEXT:    call void @init(i32* [[BASE]])
 ; CHECK-NEXT:    br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
 ; CHECK:       vector.ph:
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
latch:
   %exit = icmp ugt i64 %iv, 4094
   br i1 %exit, label %loop_exit, label %loop
 
 loop_exit:
   ret i32 %accum.next
 }
 
 
-define i32 @test_allocsize_array(i64 %len, i1* %test_base) {
+define i32 @test_allocsize_array(i64 %len, i1* %test_base) nofree nosync {
 ; CHECK-LABEL: @test_allocsize_array(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ALLOCATION:%.*]] = call nonnull i8* @my_array_alloc(i32 4096, i32 4)
 ; CHECK-NEXT:    [[BASE:%.*]] = bitcast i8* [[ALLOCATION]] to i32*
 ; CHECK-NEXT:    call void @init(i32* [[BASE]])
 ; CHECK-NEXT:    br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
 ; CHECK:       vector.ph:
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]