Update basic deref API to account for possiblity of free [NFC]

[reames]

Summary

This patch is plumbing to support work towards the goal outlined in the recent llvm-dev post "[llvm-dev] RFC: Decomposing deref(N) into deref(N) + nofree".

The point of this change is purely to simplify iteration on other pieces on way to making the switch. Rebuilding with a change to Value.h is slow and painful, so I want to get the API change landed. Once that's done, I plan to more closely audit each caller, add the inference rules in their own patch, then post a patch with the langref changes and test diffs. The value of the command line flag is that we can exercise the inference logic in standalone patches without needing the whole switch ready to go just yet.

[nlopes]

Sounds good to me, as long as you commit to removing that cmd switch within a reasonable time frame. Otherwise we accumulate technical debt.

This patch just shows how terrible this LLVM thing of traversing things backwards can be. Just because a pointer can be freed, it doesn't mean it was. This patch is quite pessimistic; essentially it assumes all pointers are dead. What's the plan to avoid regressions?

[reames]

In D98908#2637360, @nlopes wrote:

Sounds good to me, as long as you commit to removing that cmd switch within a reasonable time frame. Otherwise we accumulate technical debt.

I do. Just to be clear, your SGTM is meant as an LGTM right?

This patch just shows how terrible this LLVM thing of traversing things backwards can be. Just because a pointer can be freed, it doesn't mean it was. This patch is quite pessimistic; essentially it assumes all pointers are dead. What's the plan to avoid regressions?

This patch is extraordinarily pessimistic. :)

First step is to add a predicate for when we know an object can't be freed in the queried scope. I have an initial version of that implemented, and it does cover a large number of existing cases. After that, I'm going to be looking closely at existing test cases to see what other inference looks profitable. (I've already spotted a couple of additional inference rules which look possible that way.) I want to get each "interesting" inference rule into it's own review for ease of discussion. (Or at least small batches of related inference rules.)

Once all of that is done, I'll post a final review which flips the flag with all the doc changes, and any remaining test changes. If we feel that the remaining delta in optimization potential is too large, we can explore one of the other attribute options mentioned in the RFC thread.

[nlopes]

It is LGTM, yes.
Thanks for the details on the plan. Sounds great, thanks!

llvm/include/llvm/Analysis/MemoryBuiltins.h

struct ObjectSizeOpts {
   /// point to a 0 byte region of memory.
   bool NullIsUnknownSize = false;
 };
 
 /// Compute the size of the object pointed by Ptr. Returns true and the
 /// object size in Size if successful, and false otherwise. In this context, by
 /// object we mean the region of memory starting at Ptr to the end of the
 /// underlying object pointed to by Ptr.
+///
+/// WARNING: The object size returned is the allocation size.  This does not
+/// imply dereferenceability at site of use since the object may be freeed in
+/// between.
 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
                    const TargetLibraryInfo *TLI, ObjectSizeOpts Opts = {});
 
 /// Try to turn a call to \@llvm.objectsize into an integer value of the given
 /// Type. Returns null on failure. If MustSucceed is true, this function will
 /// not return null, and may return conservative values governed by the second
 /// argument of the call to objectsize.
 Value *lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL,

llvm/include/llvm/IR/Value.h

return const_cast<Value *>(
         static_cast<const Value *>(this)->stripInBoundsOffsets(Func));
   }
 
   /// 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
+  /// deallocated between point of definition and use.
   uint64_t getPointerDereferenceableBytes(const DataLayout &DL,
-                                          bool &CanBeNull) const;
+                                          bool &CanBeNull,
+                                          bool &CanBeFreed) const;
 
   /// Returns an alignment of the pointer value.
   ///
   /// Returns an alignment which is either specified explicitly, e.g. via
   /// align attribute of a function argument, or guaranteed by DataLayout.
   Align getPointerAlignment(const DataLayout &DL) const;
 
   /// Translate PHI node to its predecessor from the given basic block.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 /// location size and the fact that null pointers cannot alias here.
 static uint64_t getMinimalExtentFrom(const Value &V,
                                      const LocationSize &LocSize,
                                      const DataLayout &DL,
                                      bool NullIsValidLoc) {
   // If we have dereferenceability information we know a lower bound for the
   // extent as accesses for a lower offset would be valid. We need to exclude
   // the "or null" part if null is a valid pointer.
-  bool CanBeNull;
-  uint64_t DerefBytes = V.getPointerDereferenceableBytes(DL, CanBeNull);
+  bool CanBeNull, CanBeFreed;
+  uint64_t DerefBytes =
+    V.getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
   DerefBytes = (CanBeNull && NullIsValidLoc) ? 0 : DerefBytes;
+  DerefBytes = CanBeFreed ? 0 : DerefBytes;
   // If queried with a precise location size, we assume that location size to be
   // accessed, thus valid.
   if (LocSize.isPrecise())
     DerefBytes = std::max(DerefBytes, LocSize.getValue());
   return DerefBytes;
 }
 
 /// Returns true if we can prove that the object specified by V has size Size.

llvm/lib/Analysis/CaptureTracking.cpp

bool CaptureTracker::isDereferenceableOrNull(Value *O, const DataLayout &DL) {
   // the pointer escape using clever GEP hacking because doing so
   // would make the pointer point outside of the allocated object
   // and thus make the GEP result a poison value. Similarly, other
   // dereferenceable pointers cannot be manipulated without producing
   // poison.
   if (auto *GEP = dyn_cast<GetElementPtrInst>(O))
     if (GEP->isInBounds())
       return true;
-  bool CanBeNull;
-  return O->getPointerDereferenceableBytes(DL, CanBeNull);
+  bool CanBeNull, CanBeFreed;
+  return O->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
 }
 
 namespace {
   struct SimpleCaptureTracker : public CaptureTracker {
     explicit SimpleCaptureTracker(bool ReturnCaptures)
       : ReturnCaptures(ReturnCaptures), Captured(false) {}
 
     void tooManyUses() override { Captured = true; }

llvm/lib/Analysis/Loads.cpp

static bool isDereferenceableAndAlignedPointer(
   // bitcast instructions are no-ops as far as dereferenceability is concerned.
   if (const BitCastOperator *BC = dyn_cast<BitCastOperator>(V)) {
     if (BC->getSrcTy()->isPointerTy())
       return isDereferenceableAndAlignedPointer(
           BC->getOperand(0), Alignment, Size, DL, CtxI, DT, TLI,
           Visited, MaxDepth);
   }
 
-  bool CheckForNonNull = false;
+  bool CheckForNonNull, CheckForFreed;
   APInt KnownDerefBytes(Size.getBitWidth(),
-                        V->getPointerDereferenceableBytes(DL, CheckForNonNull));
-  if (KnownDerefBytes.getBoolValue() && KnownDerefBytes.uge(Size))
+                        V->getPointerDereferenceableBytes(DL, CheckForNonNull,
+                                                          CheckForFreed));
+  if (KnownDerefBytes.getBoolValue() && KnownDerefBytes.uge(Size) &&
+      !CheckForFreed)
     if (!CheckForNonNull || isKnownNonZero(V, DL, 0, nullptr, CtxI, DT)) {
       // 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

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 
 using namespace llvm;
 
+static cl::opt<unsigned> UseDerefAtPointSemantics(
+    "use-dereferenceable-at-point-semantics", cl::Hidden, cl::init(false),
+    cl::desc("Deref attributes and metadata infer facts at definition only"));
+
+
 static cl::opt<unsigned> NonGlobalValueMaxNameSize(
     "non-global-value-max-name-size", cl::Hidden, cl::init(1024),
     cl::desc("Maximum size for the name of non-global values."));
 
 //===----------------------------------------------------------------------===//
 //                                Value Class
 //===----------------------------------------------------------------------===//
 static inline Type *checkType(Type *Ty) {

 }
 
 const Value *
 Value::stripInBoundsOffsets(function_ref<void(const Value *)> Func) const {
   return stripPointerCastsAndOffsets<PSK_InBounds>(this, Func);
 }
 
 uint64_t Value::getPointerDereferenceableBytes(const DataLayout &DL,
-                                               bool &CanBeNull) const {
+                                               bool &CanBeNull,
+                                               bool &CanBeFreed) const {
   assert(getType()->isPointerTy() && "must be pointer");
 
   uint64_t DerefBytes = 0;
   CanBeNull = false;
+  CanBeFreed = UseDerefAtPointSemantics;
   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();
if (DerefBytes == 0) {
       }
       CanBeNull = true;
     }
   } else if (auto *AI = dyn_cast<AllocaInst>(this)) {
     if (!AI->isArrayAllocation()) {
       DerefBytes =
           DL.getTypeStoreSize(AI->getAllocatedType()).getKnownMinSize();
       CanBeNull = false;
+      CanBeFreed = false;
     }
   } else if (auto *GV = dyn_cast<GlobalVariable>(this)) {
     if (GV->getValueType()->isSized() && !GV->hasExternalWeakLinkage()) {
       // TODO: Don't outright reject hasExternalWeakLinkage but set the
       // CanBeNull flag.
       DerefBytes = DL.getTypeStoreSize(GV->getValueType()).getFixedSize();
       CanBeNull = false;
+      CanBeFreed = false;
     }
   }
   return DerefBytes;
 }
 
 Align Value::getPointerAlignment(const DataLayout &DL) const {
   assert(getType()->isPointerTy() && "must be pointer");
   if (auto *GO = dyn_cast<GlobalObject>(this)) {

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

void initialize(Attributor &A) override {
 
     if (isa<ConstantPointerNull>(V)) {
       indicatePessimisticFixpoint();
       return;
     }
 
     AANonNull::initialize(A);
 
-    bool CanBeNull = true;
-    if (V.getPointerDereferenceableBytes(A.getDataLayout(), CanBeNull)) {
+    bool CanBeNull, CanBeFreed;
+    if (V.getPointerDereferenceableBytes(A.getDataLayout(), CanBeNull,
+                                         CanBeFreed)) {
       if (!CanBeNull) {
         indicateOptimisticFixpoint();
         return;
       }
     }
 
     if (isa<GlobalValue>(&getAssociatedValue())) {
       indicatePessimisticFixpoint();
void initialize(Attributor &A) override {
     getAttrs({Attribute::Dereferenceable, Attribute::DereferenceableOrNull},
              Attrs, /* IgnoreSubsumingPositions */ false, &A);
     for (const Attribute &Attr : Attrs)
       takeKnownDerefBytesMaximum(Attr.getValueAsInt());
 
     const IRPosition &IRP = this->getIRPosition();
     NonNullAA = &A.getAAFor<AANonNull>(*this, IRP, DepClassTy::NONE);
 
-    bool CanBeNull;
+    bool CanBeNull, CanBeFreed;
     takeKnownDerefBytesMaximum(
         IRP.getAssociatedValue().getPointerDereferenceableBytes(
-            A.getDataLayout(), CanBeNull));
+            A.getDataLayout(), CanBeNull, CanBeFreed));
 
     bool IsFnInterface = IRP.isFnInterfaceKind();
     Function *FnScope = IRP.getAnchorScope();
     if (IsFnInterface && (!FnScope || !A.isFunctionIPOAmendable(*FnScope))) {
       indicatePessimisticFixpoint();
       return;
     }
 
auto VisitValueCB = [&](const Value &V, const Instruction *, DerefState &T,
           stripAndAccumulateMinimalOffsets(A, *this, &V, DL, Offset, false);
 
       const auto &AA = A.getAAFor<AADereferenceable>(
           *this, IRPosition::value(*Base), DepClassTy::REQUIRED);
       int64_t DerefBytes = 0;
       if (!Stripped && this == &AA) {
         // Use IR information if we did not strip anything.
         // TODO: track globally.
-        bool CanBeNull;
-        DerefBytes = Base->getPointerDereferenceableBytes(DL, CanBeNull);
+        bool CanBeNull, CanBeFreed;
+        DerefBytes =
+          Base->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
         T.GlobalState.indicatePessimisticFixpoint();
       } else {
         const DerefState &DS = AA.getState();
         DerefBytes = DS.DerefBytesState.getAssumed();
         T.GlobalState &= DS.GlobalState;
       }
 
       // For now we do not try to "increase" dereferenceability due to negative

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

if (isa<PointerType>(SrcTy) && isa<PointerType>(DestTy)) {
     // If we found a path from the src to dest, create the getelementptr now.
     if (SrcElTy == DstElTy) {
       SmallVector<Value *, 8> Idxs(NumZeros + 1, Builder.getInt32(0));
       GetElementPtrInst *GEP =
           GetElementPtrInst::Create(SrcPTy->getElementType(), Src, Idxs);
 
       // If the source pointer is dereferenceable, then assume it points to an
       // allocated object and apply "inbounds" to the GEP.
-      bool CanBeNull;
-      if (Src->getPointerDereferenceableBytes(DL, CanBeNull)) {
+      bool CanBeNull, CanBeFreed;
+      if (Src->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed)) {
         // In a non-default address space (not 0), a null pointer can not be
         // assumed inbounds, so ignore that case (dereferenceable_or_null).
         // The reason is that 'null' is not treated differently in these address
         // spaces, and we consequently ignore the 'gep inbounds' special case
         // for 'null' which allows 'inbounds' on 'null' if the indices are
         // zeros.
         if (SrcPTy->getAddressSpace() == 0 || !CanBeNull)
           GEP->setIsInBounds();