[Attributor] Deduce "dereferenceable" attribute

[uenoku]

Summary

Deduce dereferenceable attribute in Attributor.

These will be added in a later patch.

• dereferenceable(_or_null)_globally (D61652)
• Deduction based on load instruction (similar to D64258)

[uenoku]

Fix typo.

[uenoku]

Refactor initialize.

[uenoku]

Fix patch.

[jdoerfert]

Initial comments.

llvm/lib/Transforms/IPO/Attributor.cpp

378

-1 instead

1116

Do we make sure dereferenceable(0) is invalid IR? If not, we should. (The logic you use above relies on it and other places might be as well.)

1139

This can be commited separately with the other nonnull changes above. Please change the order in this conditional to first check the attributes and then call isKnownNonZero, or better, remove the attribute checks and make sure isKnownNonZero performs them.

1217

comments describing the members missing

1220

While it practically doesn't make a difference (I think) I would have suspected both states to be asked here.

1370

Add a TODO here wrt. tacking the globally flag as well, or just do it.

1373

Here and below it might make sense to move the declaration into the conditional:

if (auto *DerefAA = ... )

1388

If Offset is not 0, Base cannot be null (due to the inbounds properties). I thought about relying on the attribute to know this but that is actually not always possible. Instead, I think you can here say something like:
Offset != 0 || BaseDerefAA->isAssumedNonNull()

Furthermore, we could strip non-inbounds offsets as well, I think. Thought, we then have to be more careful with the difference calculation, e.g., only non-negative Offset values would then be allowed.

What do you think?

1401

true should be !NullPointerIsDefined(&getAnchorScope(), V.getType()->getPointerAddressSpace()) to allow nullptr as valid pointer.

Shouldn't one of the two checks above subsume the other?

1458

Why not call computeAssumedDerefenceableBytes on the CS.getArgOperand(ArgNo) value?

1821

Whitelist check missing here and above (and in existing code).

[uenoku]

Address comments.

I'll split a patch for nonnull initialization and fix whitelist in a few days.

llvm/lib/Transforms/IPO/Attributor.cpp

1139

or better, remove the attribute checks and make sure isKnownNonZero performs them.

I think isKnownNonZero would not check parameter attribute in call site so it is not correct.

1220

Even though NonNullGlobalState was not valid, we can deduce dereferenceable_or_null so I think this is appropriate.

1388

Furthermore, we could strip non-inbounds offsets as well, I think. Thought, we then have to be more careful with the difference calculation, e.g., only non-negative Offset values would then be allowed.

I'll try it later.

1458

It is already called below.

[jdoerfert]

Can you make sure this passes the llvm test suite when the Attributor is turned on?

llvm/lib/Transforms/IPO/Attributor.cpp

1368

make it static

1377

and the nonnull flag. Maybe add a parameter bool &IsNonNull and bool &IsGlobal.

[uenoku]

Address comments.

[jdoerfert]

This LGTM assuming you tried it on the test suite. Clang format the patch please and see the two comments below.

llvm/lib/Transforms/IPO/Attributor.cpp

1220

Change the name to something meaningful or remove it, should not be necessary anyway.

1386

if you do not track them, set them to false. I think tracking nonnull should be easy, you compute it below almost in all cases anyway.

[uenoku]

Address comments and add stats. test-suite passed. However as far as I see it, no new dereferenceable was deduced.

[jdoerfert]

In D64876#1595032, @uenoku wrote:

Address comments and add stats. test-suite passed. However as far as I see it, no new dereferenceable was deduced.

if (!Attr.isEnumAttribute())
  return;

Will block the attribute to reach stats. Could you re-run (with --cmake-define=TEST_SUITE_COLLECT_STATS=ON)?

[uenoku]

Will block the attribute to reach stats. Could you re-run (with --cmake-define=TEST_SUITE_COLLECT_STATS=ON)?

Oh, I see. All test passed and here is a summary:

attributor.NumCSArgumentDereferenceable 79604.0
attributor.NumFnArgumentDereferenceable 1105.0
attributor.NumFnReturnedDereferenceable 123.0

[uenoku]

Rebase.

[uenoku]

Minor update.

llvm/include/llvm/Transforms/IPO/Attributor.h

struct IntegerState : public AbstractState {
 
   /// Keep only "assumed bits" also set in \p BitsEncoding but all known ones.
   IntegerState &intersectAssumedBits(base_t BitsEncoding) {
     // Make sure we never loose any "known bits".
     Assumed = (Assumed & BitsEncoding) | Known;
     return *this;
   }
 
+  /// Take minimum of assumed and \p Value.
+  IntegerState &takeAssumedMinimum(base_t Value) {
+    // Make sure we never loose "known value".
+    Assumed = std::max(std::min(Assumed, Value), Known);
+    return *this;
+  }
+
+  /// Take maximum of known and \p Value.
+  IntegerState &takeKnownMaximum(base_t Value) {
+    // Make sure we never loose "known value".
+    Assumed = std::max(Value, Assumed);
+    Known = std::max(Value, Known);
+    return *this;
+  }
+
+  /// Equality for IntegerState.
+  bool operator==(const IntegerState &R) const {
+    return this->getAssumed() == R.getAssumed() &&
+           this->getKnown() == R.getKnown();
+  }
+
 private:
   /// The known state encoding in an integer of type base_t.
   base_t Known = getWorstState();
 
   /// The assumed state encoding in an integer of type base_t.
   base_t Assumed;
 };
 
struct AANonNull : public AbstractAttribute {
   virtual bool isKnownNonNull() const = 0;
 
   /// See AbastractState::getAttrKind().
   Attribute::AttrKind getAttrKind() const override { return ID; }
 
   /// The identifier used by the Attributor for this class of attributes.
   static constexpr Attribute::AttrKind ID = Attribute::NonNull;
 };
+
+/// An abstract interface for all dereferenceable attribute.
+struct AADereferenceable : public AbstractAttribute {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AADereferenceable(Value &V, InformationCache &InfoCache)
+      : AbstractAttribute(V, InfoCache) {}
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AADereferenceable(Value *AssociatedVal, Value &AnchoredValue,
+                    InformationCache &InfoCache)
+      : AbstractAttribute(AssociatedVal, AnchoredValue, InfoCache) {}
+
+  /// Return true if we assume that the underlying value is nonnull.
+  virtual bool isAssumedNonNull() const = 0;
+
+  /// Return true if we know that underlying value is nonnull.
+  virtual bool isKnownNonNull() const = 0;
+
+  /// Return true if we assume that underlying value is
+  /// dereferenceable(_or_null) globally.
+  virtual bool isAssumedGlobal() const = 0;
+
+  /// Return true if we know that underlying value is
+  /// dereferenceable(_or_null) globally.
+  virtual bool isKnownGlobal() const = 0;
+
+  /// Return assumed dereferenceable bytes.
+  virtual uint32_t getAssumedDereferenceableBytes() const = 0;
+
+  /// Return known dereferenceable bytes.
+  virtual uint32_t getKnownDereferenceableBytes() const = 0;
+
+  /// See AbastractState::getAttrKind().
+  Attribute::AttrKind getAttrKind() const override { return ID; }
+
+  /// The identifier used by the Attributor for this class of attributes.
+  static constexpr Attribute::AttrKind ID = Attribute::Dereferenceable;
+};
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H

llvm/lib/Transforms/IPO/Attributor.cpp

 
 #include "llvm/Transforms/IPO/Attributor.h"
 
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr,
   if (Attr.isStringAttribute()) {
     StringRef Kind = Attr.getKindAsString();
     if (Attrs.hasAttribute(AttrIdx, Kind))
       if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
         return false;
     Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
     return true;
   }
+  if (Attr.isIntAttribute()) {
+    Attribute::AttrKind Kind = Attr.getKindAsEnum();
+    if (Attrs.hasAttribute(AttrIdx, Kind))
+      if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
+        return false;
+    Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
+    return true;
+  }
 
   llvm_unreachable("Expected enum or string attribute!");
 }
 
 ChangeStatus AbstractAttribute::update(Attributor &A) {
   ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
   if (getState().isAtFixpoint())
     return HasChanged;
Function &AbstractAttribute::getAnchorScope() {
   llvm_unreachable("No scope for anchored value found!");
 }
 
 const Function &AbstractAttribute::getAnchorScope() const {
   return const_cast<AbstractAttribute *>(this)->getAnchorScope();
 }
 
 /// -----------------------NoUnwind Function Attribute--------------------------
 
 struct AANoUnwindFunction : AANoUnwind, BooleanState {
 
   AANoUnwindFunction(Function &F, InformationCache &InfoCache)
       : AANoUnwind(F, InfoCache) {}
 
   /// See AbstractAttribute::getState()
   /// {
   AbstractState &getState() override { return *this; }
struct AANonNullReturned : AANonNullImpl {
   ManifestPosition getManifestPosition() const override { return MP_RETURNED; }
 
   /// See AbstractAttriubute::initialize(...).
   void initialize(Attributor &A) override {
     Function &F = getAnchorScope();
 
     // Already nonnull.
     if (F.getAttributes().hasAttribute(AttributeList::ReturnIndex,
-                                       Attribute::NonNull))
+                                       Attribute::NonNull) ||
+        F.getAttributes().hasAttribute(AttributeList::ReturnIndex,
+                                       Attribute::Dereferenceable))
       indicateOptimisticFixpoint();
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override;
 };
 
 ChangeStatus AANonNullReturned::updateImpl(Attributor &A) {
AANonNullArgument(Argument &A, InformationCache &InfoCache)
       : AANonNullImpl(A, InfoCache) {}
 
   /// See AbstractAttribute::getManifestPosition().
   ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
 
   /// See AbstractAttriubute::initialize(...).
   void initialize(Attributor &A) override {
     Argument *Arg = cast<Argument>(getAssociatedValue());
-    if (Arg->hasNonNullAttr())
+    if (Arg->hasNonNullAttr() || Arg->hasAttribute(Attribute::Dereferenceable))
       indicateOptimisticFixpoint();
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override;
 };
 
 /// NonNull attribute for a call site argument.
 struct AANonNullCallSiteArgument : AANonNullImpl {
 
   /// See AANonNullImpl::AANonNullImpl(...).
   AANonNullCallSiteArgument(CallSite CS, unsigned ArgNo,
                             InformationCache &InfoCache)
       : AANonNullImpl(CS.getArgOperand(ArgNo), *CS.getInstruction(), InfoCache),
         ArgNo(ArgNo) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     CallSite CS(&getAnchoredValue());
     if (isKnownNonZero(getAssociatedValue(),
                        getAnchorScope().getParent()->getDataLayout()) ||
+        CS.paramHasAttr(ArgNo, Attribute::Dereferenceable) ||
         CS.paramHasAttr(ArgNo, getAttrKind()))
       indicateOptimisticFixpoint();
   }
 
   /// See AbstractAttribute::updateImpl(Attributor &A).
   ChangeStatus updateImpl(Attributor &A) override;
 
   /// See AbstractAttribute::getManifestPosition().
   ManifestPosition getManifestPosition() const override {
ChangeStatus AANonNullCallSiteArgument::updateImpl(Attributor &A) {
   if (!NonNullAA || !NonNullAA->isAssumedNonNull()) {
     indicatePessimisticFixpoint();
     return ChangeStatus::CHANGED;
   }
 
   return ChangeStatus::UNCHANGED;
 }
 
+/// -------------------- Dereferenceable Argument Attribute --------------------
+
+struct DerefState : AbstractState {
+  IntegerState DerefBytesState;
+  IntegerState NonNullGlobalState;
+  enum Deref {
+    DEREF_NONNULL = 1 << 0,
+    DEREF_GLOBAL = 1 << 1,
+  };
+
+  /// See AbstractState::isValidState()
+  bool isValidState() const override { return DerefBytesState.isValidState(); }
+
+  // See AbstractState::isAtFixpoint()
+  bool isAtFixpoint() const override {
+    return DerefBytesState.isAtFixpoint() && NonNullGlobalState.isAtFixpoint();
+  }
+
+  /// See AbstractState::indicateOptimisticFixpoint(...)
+  void indicateOptimisticFixpoint() override {
+    DerefBytesState.indicateOptimisticFixpoint();
+    NonNullGlobalState.indicateOptimisticFixpoint();
+  }
+
+  /// See AbstractState::indicatePessimisticFixpoint(...)
+  void indicatePessimisticFixpoint() override {
+    DerefBytesState.indicatePessimisticFixpoint();
+    NonNullGlobalState.indicatePessimisticFixpoint();
+  }
+
+  /// Update known dereferenceable bytes.
+  void takeKnownDerefBytesMaximum(uint64_t Bytes) {
+    DerefBytesState.takeKnownMaximum(Bytes);
+  }
+
+  /// Update assumed dereferenceable bytes.
+  void takeAssumedDerefBytesMinimum(uint64_t Bytes) {
+    DerefBytesState.takeAssumedMinimum(Bytes);
+  }
+
+  /// Equality for DerefState.
+  bool operator==(const DerefState &R) {
+    return this->DerefBytesState == R.DerefBytesState &&
+           this->NonNullGlobalState == R.NonNullGlobalState;
+  }
+};
+struct AADereferenceableImpl : AADereferenceable, DerefState {
+
+  AADereferenceableImpl(Value &V, InformationCache &InfoCache)
+      : AADereferenceable(V, InfoCache) {}
+
+  AADereferenceableImpl(Value *AssociatedVal, Value &AnchoredValue,
+                        InformationCache &InfoCache)
+      : AADereferenceable(AssociatedVal, AnchoredValue, InfoCache) {}
+
+  /// See AbstractAttribute::getState()
+  /// {
+  AbstractState &getState() override { return *this; }
+  const AbstractState &getState() const override { return *this; }
+  /// }
+
+  /// See AADereferenceable::getAssumedDereferenceableBytes().
+  uint32_t getAssumedDereferenceableBytes() const override {
+    return DerefBytesState.getAssumed();
+  }
+
+  /// See AADereferenceable::getKnownDereferenceableBytes().
+  uint32_t getKnownDereferenceableBytes() const override {
+    return DerefBytesState.getKnown();
+  }
+
+  // Helper function for syncing nonnull state.
+  void syncNonNull(const AANonNull *NonNullAA) {
+    if (!NonNullAA) {
+      NonNullGlobalState.removeAssumedBits(DEREF_NONNULL);
+      return;
+    }
+
+    if (NonNullAA->isKnownNonNull())
+      NonNullGlobalState.addKnownBits(DEREF_NONNULL);
+
+    if (!NonNullAA->isAssumedNonNull())
+      NonNullGlobalState.removeAssumedBits(DEREF_NONNULL);
+  }
+
+  /// See AADereferenceable::isAssumedGlobal().
+  bool isAssumedGlobal() const override {
+    return NonNullGlobalState.isAssumed(DEREF_GLOBAL);
+  }
+
+  /// See AADereferenceable::isKnownGlobal().
+  bool isKnownGlobal() const override {
+    return NonNullGlobalState.isKnown(DEREF_GLOBAL);
+  }
+
+  /// See AADereferenceable::isAssumedNonNull().
+  bool isAssumedNonNull() const override {
+    return NonNullGlobalState.isAssumed(DEREF_NONNULL);
+  }
+
+  /// See AADereferenceable::isKnownNonNull().
+  bool isKnownNonNull() const override {
+    return NonNullGlobalState.isKnown(DEREF_NONNULL);
+  }
+
+  void getDeducedAttributes(SmallVectorImpl<Attribute> &Attrs) const override {
+    LLVMContext &Ctx = AnchoredVal.getContext();
+
+    // TODO: Add *_globally support
+    if (isAssumedNonNull())
+      Attrs.emplace_back(Attribute::getWithDereferenceableBytes(
+          Ctx, getAssumedDereferenceableBytes()));
+    else
+      Attrs.emplace_back(Attribute::getWithDereferenceableOrNullBytes(
+          Ctx, getAssumedDereferenceableBytes()));
+  }
+  uint64_t computeAssumedDerefenceableBytes(Attributor &A, Value &V);
+
+  /// See AbstractAttribute::getAsStr().
+  const std::string getAsStr() const override {
+    if (!getAssumedDereferenceableBytes())
+      return "unknown-dereferenceable";
+    return std::string("dereferenceable") +
+           (isAssumedNonNull() ? "" : "_or_null") +
+           (isAssumedGlobal() ? "_globally" : "") + "<" +
+           std::to_string(getKnownDereferenceableBytes()) + "-" +
+           std::to_string(getAssumedDereferenceableBytes()) + ">";
+  }
+};
+
+struct AADereferenceableReturned : AADereferenceableImpl {
+  AADereferenceableReturned(Function &F, InformationCache &InfoCache)
+      : AADereferenceableImpl(F, InfoCache) {}
+
+  /// See AbstractAttribute::getManifestPosition().
+  ManifestPosition getManifestPosition() const override { return MP_RETURNED; }
+
+  /// See AbstractAttriubute::initialize(...).
+  void initialize(Attributor &A) override {
+    Function &F = getAnchorScope();
+
+    if (F.getAttributes().hasAttribute(AttributeList::ReturnIndex,
+                                       Attribute::Dereferenceable)) {
+      takeKnownDerefBytesMaximum(
+          F.getDereferenceableBytes(AttributeList::ReturnIndex));
+      F.removeAttribute(AttributeList::ReturnIndex, Attribute::Dereferenceable);
+    }
+
+    if (F.getAttributes().hasAttribute(AttributeList::ReturnIndex,
+                                       Attribute::DereferenceableOrNull)) {
+      takeKnownDerefBytesMaximum(
+          F.getDereferenceableOrNullBytes(AttributeList::ReturnIndex));
+      F.removeAttribute(AttributeList::ReturnIndex,
+                        Attribute::DereferenceableOrNull);
+    }
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override;
+};
+
+// Helper function that returns dereferenceable bytes.
+uint64_t calcDifferenceIfBaseIsNonNull(int64_t DerefBytes, int64_t Offset,
+                                       bool IsNonNull) {
+  if (!IsNonNull)
+    return 0;
+  return std::max((int64_t)0, DerefBytes - Offset);
+}
+
+uint64_t AADereferenceableImpl::computeAssumedDerefenceableBytes(Attributor &A,
+                                                                 Value &V) {
+  // First, we try to get information about V from Attributor.
+  auto *DerefAA = A.getAAFor<AADereferenceable>(*this, V);
+  if (DerefAA)
+    return DerefAA->getAssumedDereferenceableBytes();
+
+  // Otherwise, we try to compute assumed bytes from base pointer.
+  const DataLayout &DL = getAnchorScope().getParent()->getDataLayout();
+  unsigned IdxWidth =
+      DL.getIndexSizeInBits(V.getType()->getPointerAddressSpace());
+  APInt Offset(IdxWidth, 0);
+  Value *Base = V.stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
+
+  auto *BaseDerefAA = A.getAAFor<AADereferenceable>(*this, *Base);
+
+  if (BaseDerefAA)
+    return calcDifferenceIfBaseIsNonNull(
+        BaseDerefAA->getAssumedDereferenceableBytes(), Offset.getSExtValue(),
+        BaseDerefAA->isAssumedNonNull());
+
+  // Then, use IR information.
+
+  bool BaseKnownCanBeNull = false;
+  if (uint64_t BaseKnownDerefBytes =
+          Base->getPointerDereferenceableBytes(DL, BaseKnownCanBeNull))
+    return calcDifferenceIfBaseIsNonNull(
+        BaseKnownDerefBytes, Offset.getSExtValue(), !BaseKnownCanBeNull);
+
+  if (isDereferenceablePointer(Base, Base->getType(), DL))
+    return calcDifferenceIfBaseIsNonNull(
+        DL.getTypeStoreSize(Base->getType()->getPointerElementType()),
+        Offset.getSExtValue(), true);
+
+  return 0;
+}
+ChangeStatus AADereferenceableReturned::updateImpl(Attributor &A) {
+  Function &F = getAnchorScope();
+  auto BeforeState = static_cast<DerefState>(*this);
+
+  syncNonNull(A.getAAFor<AANonNull>(*this, F));
+
+  auto *AARetVal = A.getAAFor<AAReturnedValues>(*this, F);
+  if (!AARetVal) {
+    indicatePessimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
+
+  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
+    takeAssumedDerefBytesMinimum(computeAssumedDerefenceableBytes(A, RV));
+    return isValidState();
+  };
+
+  if (AARetVal->checkForallReturnedValues(Pred))
+    return BeforeState == static_cast<DerefState>(*this)
+               ? ChangeStatus::UNCHANGED
+               : ChangeStatus::CHANGED;
+
+  indicatePessimisticFixpoint();
+  return ChangeStatus::CHANGED;
+}
+
+struct AADereferenceableArgument : AADereferenceableImpl {
+  AADereferenceableArgument(Argument &A, InformationCache &InfoCache)
+      : AADereferenceableImpl(A, InfoCache) {}
+
+  /// See AbstractAttribute::getManifestPosition().
+  ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
+
+  /// See AbstractAttriubute::initialize(...).
+  void initialize(Attributor &A) override {
+    Argument *Arg = cast<Argument>(getAssociatedValue());
+    if (Arg->hasAttribute(Attribute::Dereferenceable)) {
+      takeKnownDerefBytesMaximum(Arg->getDereferenceableBytes());
+      Arg->removeAttr(Attribute::Dereferenceable);
+    }
+    if (Arg->hasAttribute(Attribute::DereferenceableOrNull)) {
+      takeKnownDerefBytesMaximum(Arg->getDereferenceableOrNullBytes());
+      Arg->removeAttr(Attribute::DereferenceableOrNull);
+    }
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override;
+};
+
+ChangeStatus AADereferenceableArgument::updateImpl(Attributor &A) {
+  Function &F = getAnchorScope();
+  Argument &Arg = cast<Argument>(getAnchoredValue());
+
+  auto BeforeState = static_cast<DerefState>(*this);
+
+  unsigned ArgNo = Arg.getArgNo();
+
+  syncNonNull(A.getAAFor<AANonNull>(*this, F, ArgNo));
+
+  // Callback function
+  std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) -> bool {
+    assert(CS && "Sanity check: Call site was not initialized properly!");
+
+    auto *DereferenceableAA =
+        A.getAAFor<AADereferenceable>(*this, *CS.getInstruction(), ArgNo);
+
+    // Check that DereferenceableAA is AADereferenceableCallSiteArgument.
+    if (DereferenceableAA) {
+      ImmutableCallSite ICS(&DereferenceableAA->getAnchoredValue());
+      if (ICS && CS.getInstruction() == ICS.getInstruction()) {
+        takeAssumedDerefBytesMinimum(
+            DereferenceableAA->getAssumedDereferenceableBytes());
+        return isValidState();
+      }
+    }
+
+    takeAssumedDerefBytesMinimum(
+        computeAssumedDerefenceableBytes(A, *CS.getArgOperand(ArgNo)));
+
+    return isValidState();
+  };
+
+  if (!A.checkForAllCallSites(F, CallSiteCheck, true)) {
+    indicatePessimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
+  return BeforeState == static_cast<DerefState>(*this) ? ChangeStatus::UNCHANGED
+                                                       : ChangeStatus::CHANGED;
+}
+
+/// Dereferenceable attribute for a call site argument.
+struct AADereferenceableCallSiteArgument : AADereferenceableImpl {
+
+  /// See AADereferenceableImpl::AADereferenceableImpl(...).
+  AADereferenceableCallSiteArgument(CallSite CS, unsigned ArgNo,
+                                    InformationCache &InfoCache)
+      : AADereferenceableImpl(CS.getArgOperand(ArgNo), *CS.getInstruction(),
+                              InfoCache),
+        ArgNo(ArgNo) {}
+
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {
+    CallSite CS(&getAnchoredValue());
+    if (CS.paramHasAttr(ArgNo, Attribute::Dereferenceable)) {
+      takeKnownDerefBytesMaximum(CS.getDereferenceableBytes(ArgNo));
+      CS.removeParamAttr(ArgNo, Attribute::Dereferenceable);
+    }
+
+    if (CS.paramHasAttr(ArgNo, Attribute::DereferenceableOrNull)) {
+      takeKnownDerefBytesMaximum(CS.getDereferenceableOrNullBytes(ArgNo));
+      CS.removeParamAttr(ArgNo, Attribute::DereferenceableOrNull);
+    }
+  }
+
+  /// See AbstractAttribute::updateImpl(Attributor &A).
+  ChangeStatus updateImpl(Attributor &A) override;
+
+  /// See AbstractAttribute::getManifestPosition().
+  ManifestPosition getManifestPosition() const override {
+    return MP_CALL_SITE_ARGUMENT;
+  };
+
+  // Return argument index of associated value.
+  int getArgNo() const { return ArgNo; }
+
+private:
+  unsigned ArgNo;
+};
+
+ChangeStatus AADereferenceableCallSiteArgument::updateImpl(Attributor &A) {
+  // NOTE: Never look at the argument of the callee in this method.
+  //       If we do this, "dereferenceable" is always deduced because of the
+  //       assumption.
+
+  Value &V = *getAssociatedValue();
+
+  auto BeforeState = static_cast<DerefState>(*this);
+
+  syncNonNull(A.getAAFor<AANonNull>(*this, getAnchoredValue(), ArgNo));
+  takeAssumedDerefBytesMinimum(computeAssumedDerefenceableBytes(A, V));
+
+  return BeforeState == static_cast<DerefState>(*this) ? ChangeStatus::UNCHANGED
+                                                       : ChangeStatus::CHANGED;
+}
+
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 bool Attributor::checkForAllCallSites(Function &F,
                                       std::function<bool(CallSite)> &Pred,
                                       bool RequireAllCallSites) {
   // We can try to determine information from
   // the call sites. However, this is only possible all call sites are known,
   // hence the function has internal linkage.
   if (RequireAllCallSites && !F.hasInternalLinkage()) {
     LLVM_DEBUG(
         dbgs()
         << "Attributor: Function " << F.getName()
         << " has no internal linkage, hence not all call sites are known\n");
     return false;
   }
 
   for (const Use &U : F.uses()) {
 
     CallSite CS(U.getUser());
-    dbgs() << *CS.getInstruction() << "\n";
     if (!CS || !CS.isCallee(&U) || !CS.getCaller()->hasExactDefinition()) {
       if (!RequireAllCallSites)
         continue;
 
       LLVM_DEBUG(dbgs() << "Attributor: User " << *U.getUser()
                         << " is an invalid use of " << F.getName() << "\n");
       return false;
     }
if (!ReturnType->isVoidTy()) {
     // though it is an argument attribute.
     if (!Whitelist || Whitelist->count(AAReturnedValues::ID))
       registerAA(*new AAReturnedValuesImpl(F, InfoCache));
 
     // Every function with pointer return type might be marked nonnull.
     if (ReturnType->isPointerTy() &&
         (!Whitelist || Whitelist->count(AANonNullReturned::ID)))
       registerAA(*new AANonNullReturned(F, InfoCache));
+
+    // Every function with pointer return type might be marked dereferenceable.
+    if (ReturnType->isPointerTy() &&
+        (!Whitelist || Whitelist->count(AADereferenceableReturned::ID)))
+      registerAA(*new AADereferenceableReturned(F, InfoCache));
   }
 
-  // Every argument with pointer type might be marked nonnull.
   for (Argument &Arg : F.args()) {
-    if (Arg.getType()->isPointerTy())
+    if (Arg.getType()->isPointerTy()) {
+      // Every argument with pointer type might be marked nonnull.
       registerAA(*new AANonNullArgument(Arg, InfoCache));
+
+      // Every argument with pointer type might be marked dereferenceable.
+      registerAA(*new AADereferenceableArgument(Arg, InfoCache));
+    }
   }
 
   // Walk all instructions to find more attribute opportunities and also
   // interesting instructions that might be queried by abstract attributes
   // during their initialization or update.
   auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
   auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
 
for (Instruction &I : instructions(&F)) {
     CallSite CS(&I);
     if (CS && CS.getCalledFunction()) {
       for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) {
         if (!CS.getArgument(i)->getType()->isPointerTy())
           continue;
 
         // Call site argument attribute "non-null".
         registerAA(*new AANonNullCallSiteArgument(CS, i, InfoCache), i);
+
+        // Call site argument attribute "dereferenceable".
+        registerAA(*new AADereferenceableCallSiteArgument(CS, i, InfoCache), i);
       }
     }
   }
 }
 
 /// Helpers to ease debugging through output streams and print calls.
 ///
 ///{

llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll

 ;          srec16(srec16(srec16(srec16(
 ;                        a
 ;          ))))))))))))))));
 ; }
 ;
 ; Other arguments are possible here due to the no-return behavior.
 ;
 ; FIXME: no-return missing
-; CHECK: define noalias nonnull i32* @srec16(i32* nocapture readnone %a)
+; CHECK: define noalias nonnull dereferenceable(4294967295) i32* @srec16(i32* nocapture readnone %a)
 define i32* @srec16(i32* %a) #0 {
 entry:
   %call = call i32* @srec16(i32* %a)
   %call1 = call i32* @srec16(i32* %call)
   %call2 = call i32* @srec16(i32* %call1)
   %call3 = call i32* @srec16(i32* %call2)
   %call4 = call i32* @srec16(i32* %call3)
   %call5 = call i32* @srec16(i32* %call4)

llvm/test/Transforms/FunctionAttrs/dereferenceable.ll

+; RUN: opt -attributor --attributor-disable=false -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR
+
+
+; TEST 1
+; take mininimum of return values
+;
+define i32* @test1(i32* dereferenceable(4), double* dereferenceable(8), i1 zeroext) local_unnamed_addr {
+; ATTRIBUTOR: define nonnull dereferenceable(4) i32* @test1(i32* nonnull dereferenceable(4), double* nonnull dereferenceable(8), i1 zeroext)
+  %4 = bitcast double* %1 to i32*
+  %5 = select i1 %2, i32* %0, i32* %4
+  ret i32* %5
+}
+
+; TEST 2
+define i32* @test2(i32* dereferenceable_or_null(4), double* dereferenceable(8), i1 zeroext) local_unnamed_addr {
+; ATTRIBUTOR: define dereferenceable_or_null(4) i32* @test2(i32* dereferenceable_or_null(4), double* nonnull dereferenceable(8), i1 zeroext)
+  %4 = bitcast double* %1 to i32*
+  %5 = select i1 %2, i32* %0, i32* %4
+  ret i32* %5
+}
+
+; TEST 3
+; GEP inbounds
+define i32* @test3_1(i32* dereferenceable(8)) local_unnamed_addr {
+; ATTRIBUTOR: define nonnull dereferenceable(4) i32* @test3_1(i32* nonnull dereferenceable(8))
+  %ret = getelementptr inbounds i32, i32* %0, i64 1
+  ret i32* %ret
+}
+
+; if %0 is null, we cann't assume dereferenceable_or_null for return value
+define i32* @test3_2(i32* dereferenceable_or_null(32)) local_unnamed_addr {
+; ATTRIBUTOR: define nonnull i32* @test3_2(i32* dereferenceable_or_null(32))
+  %ret = getelementptr inbounds i32, i32* %0, i64 4
+  ret i32* %ret
+}
+
+define i32* @test3_3(i32* dereferenceable(8), i32* dereferenceable(16), i1) local_unnamed_addr {
+; ATTRIBUTOR: define nonnull dereferenceable(4) i32* @test3_3(i32* nonnull dereferenceable(8), i32* nonnull dereferenceable(16), i1) local_unnamed_addr
+  %ret1 = getelementptr inbounds i32, i32* %0, i64 1
+  %ret2 = getelementptr inbounds i32, i32* %1, i64 2
+  %ret = select i1 %2, i32* %ret1, i32* %ret2
+  ret i32* %ret
+}
+
+; TEST 4
+; Better than known in IR.
+
+define dereferenceable(4) i32* @test4(i32* dereferenceable(8)) local_unnamed_addr {
+; ATTRIBUTOR: define nonnull dereferenceable(8) i32* @test4(i32* nonnull returned dereferenceable(8))
+  ret i32* %0
+}
+

llvm/test/Transforms/FunctionAttrs/nonnull.ll

; BOTH: define nonnull i8* @test3
   ret i8* %ret
 }
 
 ; Given a mutual recursive set of functions, we can mark them
 ; nonnull if neither can ever return null.  (In this case, they
 ; just never return period.)
 define i8* @test4_helper() {
 ; FNATTR: define noalias nonnull i8* @test4_helper
-; ATTRIBUTOR: define nonnull i8* @test4_helper
+; ATTRIBUTOR: define nonnull dereferenceable(4294967295) i8* @test4_helper
   %ret = call i8* @test4()
   ret i8* %ret
 }
 
 define i8* @test4() {
 ; FNATTR: define noalias nonnull i8* @test4
-; ATTRIBUTOR: define nonnull i8* @test4
+; ATTRIBUTOR: define nonnull dereferenceable(4294967295) i8* @test4
   %ret = call i8* @test4_helper()
   ret i8* %ret
 }
 
 ; Given a mutual recursive set of functions which *can* return null
 ; make sure we haven't marked them as nonnull.
 define i8* @test5_helper() {
 ; FNATTR: define noalias i8* @test5_helper

 ; FIXME: missing nonnull. It should be nonnull @f3(i32* nonnull %arg) 
 ; ATTRIBUTOR: define dso_local noalias i32* @f3(i32* %arg)
 bb:
 ; FIXME: missing nonnull. It should be @f1(i32* nonnull %arg) 
 ; ATTRIBUTOR:   %tmp = call i32* @f1(i32* %arg)
   %tmp = call i32* @f1(i32* %arg)
   ret i32* null
 }
+
+; TEST 15
+define void @f15(i8* %arg) {
+; ATTRIBUTOR:   tail call void @use1(i8* nonnull dereferenceable(4) %arg)
+
+  tail call void @use1(i8* dereferenceable(4) %arg)
+  ret void
+}
+
 ; Test propagation of nonnull callsite args back to caller.
 
 declare void @use1(i8* %x)
 declare void @use2(i8* %x, i8* %y);
 declare void @use3(i8* %x, i8* %y, i8* %z);
 
 declare void @use1nonnull(i8* nonnull %x);
 declare void @use2nonnull(i8* nonnull %x, i8* nonnull %y);