[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

379 ↗

(On Diff #210414)

-1 instead

1125 ↗

(On Diff #210414)

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.)

1148 ↗

(On Diff #210414)

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.

1226 ↗

(On Diff #210414)

comments describing the members missing

1229 ↗

(On Diff #210414)

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

1379 ↗

(On Diff #210414)

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

1382 ↗

(On Diff #210414)

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

if (auto *DerefAA = ... )

1397 ↗

(On Diff #210414)

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?

1410 ↗

(On Diff #210414)

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?

1467 ↗

(On Diff #210414)

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

1804 ↗

(On Diff #210414)

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

1148 ↗

(On Diff #210414)

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.

1229 ↗

(On Diff #210414)

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

1397 ↗

(On Diff #210414)

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.

1467 ↗

(On Diff #210414)

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

1377 ↗

(On Diff #210591)

make it static

1386 ↗

(On Diff #210591)

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

1229 ↗

(On Diff #210692)

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

1395 ↗

(On Diff #210692)

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/trunk/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 AAIsDead : public AbstractAttribute {
 
   /// Returns true if \p BB is assumed dead.
   virtual bool isAssumedDead(BasicBlock *BB) const = 0;
 
   /// Returns true if \p BB is known dead.
   virtual bool isKnownDead(BasicBlock *BB) const = 0;
 };
 
+/// 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/trunk/lib/Transforms/IPO/Attributor.cpp

 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CaptureTracking.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/CFG.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"

 STATISTIC(NumFnNoSync, "Number of functions marked nosync");
 STATISTIC(NumFnNoFree, "Number of functions marked nofree");
 STATISTIC(NumFnReturnedNonNull,
           "Number of function return values marked nonnull");
 STATISTIC(NumFnArgumentNonNull, "Number of function arguments marked nonnull");
 STATISTIC(NumCSArgumentNonNull, "Number of call site arguments marked nonnull");
 STATISTIC(NumFnWillReturn, "Number of functions marked willreturn");
 STATISTIC(NumFnArgumentNoAlias, "Number of function arguments marked noalias");
+STATISTIC(NumFnReturnedDereferenceable,
+          "Number of function return values marked dereferenceable");
+STATISTIC(NumFnArgumentDereferenceable,
+          "Number of function arguments marked dereferenceable");
+STATISTIC(NumCSArgumentDereferenceable,
+          "Number of call site arguments marked dereferenceable");
 
 // TODO: Determine a good default value.
 //
 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
 // (when run with the first 5 abstract attributes). The results also indicate
 // that we never reach 32 iterations but always find a fixpoint sooner.
 //
 // This will become more evolved once we perform two interleaved fixpoint

 ///}
 
 /// Helper to adjust the statistics.
 static void bookkeeping(AbstractAttribute::ManifestPosition MP,
                         const Attribute &Attr) {
   if (!AreStatisticsEnabled())
     return;
 
-  if (!Attr.isEnumAttribute())
-    return;
   switch (Attr.getKindAsEnum()) {
+  case Attribute::Dereferenceable:
+    switch (MP) {
+    case AbstractAttribute::MP_RETURNED:
+      NumFnReturnedDereferenceable++;
+      break;
+    case AbstractAttribute::MP_ARGUMENT:
+      NumFnArgumentDereferenceable++;
+      break;
+    case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
+      NumCSArgumentDereferenceable++;
+      break;
+    default:
+      break;
+    }
+    break;
   case Attribute::NoUnwind:
     NumFnNoUnwind++;
     return;
   case Attribute::Returned:
     NumFnArgumentReturned++;
     return;
   case Attribute::NoSync:
     NumFnNoSync++;
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.removeAttribute(Ctx, AttrIdx, Kind);
+    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;
if (isa<Instruction>(V))
     return *cast<Instruction>(V).getFunction();
   llvm_unreachable("No scope for anchored value found!");
 }
 
 const Function &AbstractAttribute::getAnchorScope() const {
   return const_cast<AbstractAttribute *>(this)->getAnchorScope();
 }
 
+// Helper function that returns argument index of value.
+// If the value is not an argument, this returns -1.
+static int getArgNo(Value &V) {
+  if (auto *Arg = dyn_cast<Argument>(&V))
+    return Arg->getArgNo();
+  return -1;
+}
+
 /// -----------------------NoUnwind Function Attribute--------------------------
 
 struct AANoUnwindFunction : AANoUnwind, BooleanState {
 
   AANoUnwindFunction(Function &F, InformationCache &InfoCache)
       : AANoUnwind(F, InfoCache) {}
 
   /// See AbstractAttribute::getState()
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) {
struct AANonNullCallSiteArgument : 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, getAttrKind()))
+    if (CS.paramHasAttr(ArgNo, getAttrKind()) ||
+        CS.paramHasAttr(ArgNo, Attribute::Dereferenceable) ||
+        isKnownNonZero(getAssociatedValue(),
+                       getAnchorScope().getParent()->getDataLayout()))
       indicateOptimisticFixpoint();
   }
 
   /// See AbstractAttribute::updateImpl(Attributor &A).
   ChangeStatus updateImpl(Attributor &A) override;
 
   /// See AbstractAttribute::getManifestPosition().
   ManifestPosition getManifestPosition() const override {
for (Instruction *I : NoReturnChanged) {
     // At least one new path.
     Status = ChangeStatus::CHANGED;
 
     // explore new paths.
     while (Size != ToBeExploredPaths.size())
       explorePath(A, ToBeExploredPaths[Size++]);
   }
 
-  LLVM_DEBUG(dbgs() << "[AAIsDead] AssumedLiveBlocks: "
-                    << AssumedLiveBlocks.size()
-                    << "Total number of blocks: "
-                    << getAnchorScope().size() << "\n");
+  LLVM_DEBUG(
+      dbgs() << "[AAIsDead] AssumedLiveBlocks: " << AssumedLiveBlocks.size()
+             << "Total number of blocks: " << getAnchorScope().size() << "\n");
 
   return Status;
 }
 
+/// -------------------- Dereferenceable Argument Attribute --------------------
+
+struct DerefState : AbstractState {
+
+  /// State representing for dereferenceable bytes.
+  IntegerState DerefBytesState;
+
+  /// State representing that whether the value is nonnull or global.
+  IntegerState NonNullGlobalState;
+
+  /// Bits encoding for NonNullGlobalState.
+  enum {
+    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);
+  }
+
+  /// Update assumed NonNullGlobalState
+  void updateAssumedNonNullGlobalState(bool IsNonNull, bool IsGlobal) {
+    if (!IsNonNull)
+      NonNullGlobalState.removeAssumedBits(DEREF_NONNULL);
+    if (!IsGlobal)
+      NonNullGlobalState.removeAssumedBits(DEREF_GLOBAL);
+  }
+
+  /// 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,
+                                            bool &IsNonNull, bool &IsGlobal);
+
+  void initialize(Attributor &A) override {
+    Function &F = getAnchorScope();
+    unsigned AttrIdx =
+        getAttrIndex(getManifestPosition(), getArgNo(getAnchoredValue()));
+
+    for (Attribute::AttrKind AK :
+         {Attribute::Dereferenceable, Attribute::DereferenceableOrNull})
+      if (F.getAttributes().hasAttribute(AttrIdx, AK))
+        takeKnownDerefBytesMaximum(F.getAttribute(AttrIdx, AK).getValueAsInt());
+  }
+
+  /// 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 AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override;
+};
+
+// Helper function that returns dereferenceable bytes.
+static 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, bool &IsNonNull, bool &IsGlobal) {
+  // TODO: Tracking the globally flag.
+  IsGlobal = false;
+
+  // First, we try to get information about V from Attributor.
+  if (auto *DerefAA = A.getAAFor<AADereferenceable>(*this, V)) {
+    IsNonNull &= DerefAA->isAssumedNonNull();
+    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);
+
+  if (auto *BaseDerefAA = A.getAAFor<AADereferenceable>(*this, *Base)) {
+    IsNonNull &= Offset != 0;
+    return calcDifferenceIfBaseIsNonNull(
+        BaseDerefAA->getAssumedDereferenceableBytes(), Offset.getSExtValue(),
+        Offset != 0 || BaseDerefAA->isAssumedNonNull());
+  }
+
+  // Then, use IR information.
+
+  if (isDereferenceablePointer(Base, Base->getType(), DL))
+    return calcDifferenceIfBaseIsNonNull(
+        DL.getTypeStoreSize(Base->getType()->getPointerElementType()),
+        Offset.getSExtValue(),
+        !NullPointerIsDefined(&getAnchorScope(),
+                              V.getType()->getPointerAddressSpace()));
+
+  IsNonNull = false;
+  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;
+  }
+
+  bool IsNonNull = isAssumedNonNull();
+  bool IsGlobal = isAssumedGlobal();
+
+  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
+    takeAssumedDerefBytesMinimum(
+        computeAssumedDerefenceableBytes(A, RV, IsNonNull, IsGlobal));
+    return isValidState();
+  };
+
+  if (AARetVal->checkForallReturnedValues(Pred)) {
+    updateAssumedNonNullGlobalState(IsNonNull, IsGlobal);
+    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 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));
+
+  bool IsNonNull = isAssumedNonNull();
+  bool IsGlobal = isAssumedGlobal();
+
+  // Callback function
+  std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) -> bool {
+    assert(CS && "Sanity check: Call site was not initialized properly!");
+
+    // Check that DereferenceableAA is AADereferenceableCallSiteArgument.
+    if (auto *DereferenceableAA =
+            A.getAAFor<AADereferenceable>(*this, *CS.getInstruction(), ArgNo)) {
+      ImmutableCallSite ICS(&DereferenceableAA->getAnchoredValue());
+      if (ICS && CS.getInstruction() == ICS.getInstruction()) {
+        takeAssumedDerefBytesMinimum(
+            DereferenceableAA->getAssumedDereferenceableBytes());
+        IsNonNull &= DereferenceableAA->isAssumedNonNull();
+        IsGlobal &= DereferenceableAA->isAssumedGlobal();
+        return isValidState();
+      }
+    }
+
+    takeAssumedDerefBytesMinimum(computeAssumedDerefenceableBytes(
+        A, *CS.getArgOperand(ArgNo), IsNonNull, IsGlobal));
+
+    return isValidState();
+  };
+
+  if (!A.checkForAllCallSites(F, CallSiteCheck, true)) {
+    indicatePessimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
+
+  updateAssumedNonNullGlobalState(IsNonNull, IsGlobal);
+
+  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));
+
+    if (CS.paramHasAttr(ArgNo, Attribute::DereferenceableOrNull))
+      takeKnownDerefBytesMaximum(CS.getDereferenceableOrNullBytes(ArgNo));
+  }
+
+  /// 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));
+  bool IsNonNull = isAssumedNonNull();
+  bool IsGlobal = isKnownGlobal();
+
+  takeAssumedDerefBytesMinimum(
+      computeAssumedDerefenceableBytes(A, V, IsNonNull, IsGlobal));
+  updateAssumedNonNullGlobalState(IsNonNull, IsGlobal);
+
+  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
if (!ReturnType->isVoidTy()) {
     if (ReturnType->isPointerTy()) {
       // Every function with pointer return type might be marked nonnull.
       if (!Whitelist || Whitelist->count(AANonNullReturned::ID))
         registerAA(*new AANonNullReturned(F, InfoCache));
 
       // Every function with pointer return type might be marked noalias.
       if (!Whitelist || Whitelist->count(AANoAliasReturned::ID))
         registerAA(*new AANoAliasReturned(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.
+      if (!Whitelist || Whitelist->count(AANonNullArgument::ID))
         registerAA(*new AANonNullArgument(Arg, InfoCache));
+
+      // Every argument with pointer type might be marked dereferenceable.
+      if (!Whitelist || Whitelist->count(AADereferenceableArgument::ID))
+        registerAA(*new AADereferenceableArgument(Arg, InfoCache));
+    }
   }
 
   // Every function might be "will-return".
   registerAA(*new AAWillReturnFunction(F, InfoCache));
 
   // Check for dead BasicBlocks in every function.
   registerAA(*new AAIsDeadFunction(F, InfoCache));
 
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".
+        if (!Whitelist || Whitelist->count(AANonNullCallSiteArgument::ID))
           registerAA(*new AANonNullCallSiteArgument(CS, i, InfoCache), i);
+
+        // Call site argument attribute "dereferenceable".
+        if (!Whitelist ||
+            Whitelist->count(AADereferenceableCallSiteArgument::ID))
+          registerAA(*new AADereferenceableCallSiteArgument(CS, i, InfoCache),
+                     i);
       }
     }
   }
 }
 
 /// Helpers to ease debugging through output streams and print calls.
 ///
 ///{

llvm/trunk/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/trunk/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
+}
+
+define i32* @test3_2(i32* dereferenceable_or_null(32)) local_unnamed_addr {
+; FIXME: Argument should be mark dereferenceable because of GEP `inbounds`.
+; ATTRIBUTOR: define nonnull dereferenceable(16) 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/trunk/test/Transforms/FunctionAttrs/noalias_returned.ll

5:                                                ; preds = %1, %3
   ret i8* %6
 }
 
 declare i8* @baz(...) nounwind uwtable
 
 ; TEST 5
 
 ; Returning global pointer. Should not be noalias.
-; CHECK: define nonnull i8** @getter()
+; CHECK: define nonnull dereferenceable(8) i8** @getter()
 define i8** @getter() {
   ret i8** @G
 }
 
 ; Returning global pointer. Should not be noalias.
-; CHECK: define nonnull i8** @calle1()
+; CHECK: define nonnull dereferenceable(8) i8** @calle1()
 define i8** @calle1(){
   %1 = call i8** @getter()
   ret i8** %1
 }
 
 ; TEST 6
 declare noalias i8* @strdup(i8* nocapture) nounwind
 

llvm/trunk/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 noalias nonnull i8* @test4_helper
+; ATTRIBUTOR: define noalias nonnull dereferenceable(4294967295) i8* @test4_helper
   %ret = call i8* @test4()
   ret i8* %ret
 }
 
 define i8* @test4() {
 ; FNATTR: define noalias nonnull i8* @test4
-; ATTRIBUTOR: define noalias nonnull i8* @test4
+; ATTRIBUTOR: define noalias 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);