[Attributor] Deduce "nonnull" attribute

[uenoku]

Summary

Porting nonnull attribute to attributor.

[uenoku]

Fix test.

[uenoku]

Currently, nonnull is deduced if all the return values are defined by nonnull return function.

I'll make it see function arguments later.

[uenoku]

When a return value is an argument, see it.

[uenoku]

Fix patch.

[jdoerfert]

Please add tests that do pointer arithmetic, e.g., return a + 1.

[jdoerfert]

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

685

copy and past comment, also above

llvm/lib/Transforms/IPO/Attributor.cpp

720

Undef values are fine. undef basically allows you to "chose" a value, so we can "chose" something other than null.

725

You should (also) ask for the AANonNull attribute for the value and if you get an abstract attribute that says nonnull we are fine. That should subsume some of the code below and also trigger ones we have AANonNullArgument.

732

You should ask value tracking via isKnownNonZero here as well. It will need to be improved still to use optimistic information but it is better than nothing.

744

The predicate above will be reused later on. Maybe "generate" it in a function in AANonNullImpl for a given Attributor.

[uenoku]

Add tests and AANonNullArgument

[uenoku]

Fix typo and add comment.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

683

Explain the behavior of the generate better, what does it return, true for nonnull?

728

Why would you indicate a fixpoint here? If there is no attribute present in the IR we can still deduce it.

739

No braces around a single statement

760

Why do we need to duplicate the A.getAAFor ... code and the ceck afterwards?
Couldn't we just ask for auto *NonNullAA = A.getAAFor<AANonNull>(*this, RV); regardless whether it is an argument, call, or something else?

768

In that case, move the "indicatePessimisticFixpoint" from the init method here. Than one can at least see what is going on.

llvm/test/Transforms/FunctionAttrs/nonnull.ll

107

One more with inbounds (below, untested!) and maybe some without inbounds while we are at it.

; CHECK: define i8* @test10
; FIXME: missing nonnull
; ATTRIBUTOR: define i8* @test10
define i8* @test10(i8* %a, i64 %n) {
  %cmp = icmp ne i64 %n, null 
  call void @llvm.assume(i1 %cmp)
  %b = getelementptr inbounds i8, i8* %a, i64 %n
  ret i8* %b
}

[uenoku]

Address comments.

[uenoku]

Use isKnownNonZero.

[uenoku]

Fix comment.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

687

Why isn't isAssumedNonNull() sufficient here?

740

Please add here something like:

FIXME: The `AAReturnedValues` should provide the predicate with the `ReturnInst` vector as well such that we can use the control flow sensitive version of `isKnownNonZero`. This should fix `test11` in `test/Transforms/FunctionAttrs/nonnull.ll`

764

CHANGED

770

I don't think you need the "Impl" part.

[uenoku]

Address comments.

[uenoku]

• Deduce nonnull on functions argument if we have nonnull in whole call sites (mostly based on D59202).
• Deduce nonnull on a call site argument if the passed value is assumed nonnull.

[jdoerfert]

I think this is almost ready.

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

261

No newline and "sites" in the first line.

llvm/lib/Transforms/IPO/Attributor.cpp

682

"Generate a predicate that checks if a given value is assumed nonnull".

705

This comment is a bit out of place. I don't think you need it at all.

835

You can pass this value to the AbstractAttribute constructor (via a new AANonNullImpl and AANonNull constructor so there is no need to overload this method and keep track of the argument number.

854

isKnowNonNull(&V, ...) ?

1064

Could you move this to the remaining Attributor impl, please.

llvm/test/Transforms/FunctionAttrs/nonnull.ll

344

These are a lot of copies. Could we somehow make the "default" check and only specialize/copy when the two (-funcattr and -attributor) generate different code? Or is this already what you did and I just missed it? Also, could you add FIXMEs where we fail to deduce something with the attributor?

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

854

isKnowNonNull(&V, ...)?

Could you explain more detail?

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

854

Sorry. Any reason you do not use the isKnownNonNull functionality here (as you did above)? The check for an AANonNullImpl attribute will only succeed if the values is a call or argument.

[xbolva00]

Hello,

Maybe you remember https://reviews.llvm.org/D53342 ? Should we do it “InstCombine”-way or some alternative one ?

It could fit Atributor nicely, but not sure if nonnull dropping isn’t something weird for Attributor.

[jdoerfert]

In D63604#1578854, @xbolva00 wrote:

Maybe you remember https://reviews.llvm.org/D53342 ? Should we do it “InstCombine”-way or some alternative one ?

I did not, thanks for reminding me. What do you mean by the "InstCombine"-way and what alternatives do you have in mind?
Sorry that I'm a bit lost at the moment, I looked at D53342 and I seemed there are still problems with that patch even though the idea is very useful and we should add it.

[xbolva00]

In D63604#1578875, @jdoerfert wrote:

In D63604#1578854, @xbolva00 wrote:

Maybe you remember https://reviews.llvm.org/D53342 ? Should we do it “InstCombine”-way or some alternative one ?

I did not, thanks for reminding me. What do you mean by the "InstCombine"-way and what alternatives do you have in mind?
Sorry that I'm a bit lost at the moment, I looked at D53342 and I seemed there are still problems with that patch even though the idea is very useful and we should add it.

I want to ask, whether it is okay to set/drop nonnull attribute in InstCombine or you would like to see this setting/dropping in Attributor.

If you are OK with “InstCombine”-way, I can rebase/update my patch.

[jdoerfert]

In D63604#1578887, @xbolva00 wrote:

In D63604#1578875, @jdoerfert wrote:

In D63604#1578854, @xbolva00 wrote:

Maybe you remember https://reviews.llvm.org/D53342 ? Should we do it “InstCombine”-way or some alternative one ?

I did not, thanks for reminding me. What do you mean by the "InstCombine"-way and what alternatives do you have in mind?
Sorry that I'm a bit lost at the moment, I looked at D53342 and I seemed there are still problems with that patch even though the idea is very useful and we should add it.

I want to ask, whether it is okay to set/drop nonnull attribute in InstCombine or you would like to see this setting/dropping in Attributor.

If you are OK with “InstCombine”-way, I can rebase/update my patch.

I think placing attributes for known library functions should not be part of the Attributor. So, rebase & update your patch and I'll review it.

[uenoku]

Address comments.

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

854

I understand you are saying about isKnownNonZero :).

[jdoerfert]

define internal i32* @f1(i32* %arg) {
bb:
  %tmp = icmp eq i32* %arg, null
  br i1 %tmp, label %bb9, label %bb1

bb1:                                              ; preds = %bb
  %tmp2 = load i32, i32* %arg, align 4
  %tmp3 = icmp eq i32 %tmp2, 0
  br i1 %tmp3, label %bb6, label %bb4

bb4:                                              ; preds = %bb1
  %tmp5 = getelementptr inbounds i32, i32* %arg, i64 1
  %tmp5b = tail call i32* @f3(i32* %tmp5)
  br label %bb9

bb6:                                              ; preds = %bb1
  %tmp7 = tail call i32* @f2(i32* %arg)
  ret i32* %tmp7

bb9:                                              ; preds = %bb4, %bb
  %tmp10 = phi i32* [ %tmp5, %bb4 ], [ inttoptr (i64 4 to i32*), %bb ]
  ret i32* %tmp10
}

define internal i32* @f2(i32* %arg) {
bb:
  %tmp = tail call i32* @f1(i32* %arg)
  ret i32* %tmp
}

define dso_local noalias i32* @f3(i32* %arg) {
bb:
  %tmp = call i32* @f1(i32* %arg)
  ret i32* null
}

Another test case to show some shortcomings of the current approach.

llvm/lib/Transforms/IPO/Attributor.cpp

676

Copy & Paste

801

We have to make sure we do not get the AANonNullImpl for the argument back when none exists for the call site argument. So you have to test that the associated value of NonNullCSArgAA is the call site operand, or you check that NonNullCSArgAA is not this.

835

It seems without the argument number you have to do a linear search. I didn't realize that. Can we store the argument number but still pass the CS.getArgOperand(ArgNo) to the AANonNullImpl constructor as well?

838

Add a strongly worded comment here telling people they should not (explicitly) look at the argument of the callee in this method.

843

It's only about the assumed state. So, UNCHANGED as we assumed non-null already otherwise updateImpl wouldn't be called.

854

That is what I meant all along ;)

llvm/test/Transforms/FunctionAttrs/nonnull.ll

152

We derive nonnull here because test13 is dead, correct? Maybe that is not what you wanted to test ;)

[sstefan1]

We accumulated some unnecessary virtual declarations in the Attributor. I created D64637 to remove them in already committed patches. It would be good if you remove them in your active patches too.

[uenoku]

Add test and address comments.

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

801

We have to make sure we do not get the AANonNullImpl for the argument back when none exists for the call site argument. So you have to test that the associated value of NonNullCSArgAA is the call site operand, or you check that NonNullCSArgAA is not this.

I could understand the previous implementation didn't work well. But I couldn't understand the latter. I think it is sufficient to query CS.getArgOperand(ArgNo) to Attributor, isn't it?

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

1058

registerAA(*new AANonNullCallSiteArgument(CS, i, InfoCache), i);

[uenoku]

Fix AANonNullArgument::updateImpl.

[uenoku]

Add other tests and check-all passed.

[uenoku]

Fix typo.

[jdoerfert]

Small nits that should be fixed but other than that this looks good to me.

llvm/lib/Transforms/IPO/Attributor.cpp

833

I think we should switch the order here. If we have an AANonNull for the call site we should use it for sure. Otherwise, look at the paramAttr and ask isKnownNonZero. The latter is not necessarily cheap so we should use information computed already first.

You want CallBase not CallInst, or better, compare the anchoredvalue with the CS inst.

846

The whole "direction" concept is something I talked about but I don't think we actually need it. Let's just say we need to do it to avoid circular conclusions.

853

This seems like something we can move in the initialize method as it should not change over time.

857

I improved getAAFor such that whenever it returns a non-null pointer the state of that abstract attribute is valid. That means we do not need to check for a valid state at the call sites.

llvm/test/Transforms/FunctionAttrs/nonnull.ll

4

We need a target layout here. The test is now dependent on the sizes of pointer (I think) and without target layout it might take the host values which would be bad for 32bit machines.

175

Will be fixed with D64708.

[uenoku]

Address comments. I'll commit when D64708 have been landed.

[jdoerfert]

In D63604#1584847, @uenoku wrote:

Address comments. I'll commit when D64708 have been landed.

landed.

[uenoku]

Fix test.

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

struct Attributor {
   /// IR already contains the information they would deduce. The most important
   /// reason for this is the single interface, the one of the abstract attribute
   /// instance, which can be queried without the need to look at the IR in
   /// various places.
   void identifyDefaultAbstractAttributes(
       Function &F, InformationCache &InfoCache,
       DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist = nullptr);
 
+  /// Check \p Pred on all function call cites.
+  ///
+  /// This method will evaluate \p Pred on call sites and return
+  /// true if \p Pred holds in every call sites. However, this is only possible
+  /// all call sites are known, hence the function has internal linkage.
+
+  bool checkForAllCallSites(Function &F, std::function<bool(CallSite)> &Pred,
+                            bool RequireAllCallSites);
+
 private:
   /// The set of all abstract attributes.
   ///{
   using AAVector = SmallVector<AbstractAttribute *, 64>;
   AAVector AllAbstractAttributes;
   ///}
 
   /// A nested map to lookup abstract attributes based on the anchored value and
struct AAReturnedValues : public AbstractAttribute {
 
   /// See AbstractAttribute::getAttrKind()
   virtual Attribute::AttrKind getAttrKind() const override { return ID; }
 
   /// The identifier used by the Attributor for this class of attributes.
   static constexpr Attribute::AttrKind ID = Attribute::Returned;
 };
 
+/// An abstract interface for all nonnull attributes.
+struct AANonNull : public AbstractAttribute {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AANonNull(Value &V, InformationCache &InfoCache)
+      : AbstractAttribute(V, 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;
+
+  /// 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;
+};
+
 } // 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/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 
ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
   if (!HasCallSite) {
     indicateOptimisticFixpoint();
     return ChangeStatus::CHANGED;
   }
 
   return Changed;
 }
 
+/// ------------------------ NonNull Argument Attribute ------------------------
+struct AANonNullImpl : AANonNull, BooleanState {
+
+  AANonNullImpl(Value &V, InformationCache &InfoCache)
+      : AANonNull(V, InfoCache) {}
+
+  /// See AbstractAttribute::getState()
+  /// {
+  AbstractState &getState() override { return *this; }
+  const AbstractState &getState() const override { return *this; }
+  /// }
+
+  virtual const std::string getAsStr() const override {
+    return getAssumed() ? "nonnull" : "may-null";
+  }
+
+  /// See AANonNull::isAssumedNonNull().
+  virtual bool isAssumedNonNull() const override { return getAssumed(); }
+
+  /// See AANonNull::isKnownNonNull().
+  virtual bool isKnownNonNull() const override { return getKnown(); }
+
+  /// Generate a function to check whether the value is known as nonnull.
+  /// The generated function returns true if a value satisfies any of
+  /// following conditions.
+  /// (i) A value is known nonZero(=nonnull).
+  /// (ii) A value is associated with AANonNull and its isAssumedNonNull() is
+  /// true.
+  std::function<bool(Value &)> generatePredicate(Attributor &);
+};
+
+std::function<bool(Value &)> AANonNullImpl::generatePredicate(Attributor &A) {
+  // FIXME: The `AAReturnedValues` should provide the predicate with the
+  // `ReturnInst` vector as well such that we can use the control flow sensitive
+  // version of `isKnownNonZero`. This should fix `test11` in
+  // `test/Transforms/FunctionAttrs/nonnull.ll`
+
+  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
+    if (isKnownNonZero(&RV, getAnchorScope().getParent()->getDataLayout()))
+      return true;
+
+    auto *NonNullAA = A.getAAFor<AANonNullImpl>(*this, RV);
+
+    ImmutableCallSite ICS(&RV);
+
+    // We can deduce nonnull if all return value has nonnull attribute.
+
+    if ((!NonNullAA || !NonNullAA->isValidState() ||
+         !NonNullAA->isAssumedNonNull()) &&
+        (!ICS || !ICS.hasRetAttr(Attribute::NonNull)))
+      return false;
+
+    return true;
+  };
+
+  return Pred;
+}
+
+/// NonNull attribute for function return value.
+struct AANonNullReturned : AANonNullImpl {
+
+  AANonNullReturned(Function &F, InformationCache &InfoCache)
+      : AANonNullImpl(F, InfoCache) {}
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual 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))
+      indicateOptimisticFixpoint();
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  virtual ChangeStatus updateImpl(Attributor &A) override;
+};
+
+ChangeStatus AANonNullReturned::updateImpl(Attributor &A) {
+  Function &F = getAnchorScope();
+
+  auto *AARetVal = A.getAAFor<AAReturnedValues>(*this, F);
+  if (!AARetVal) {
+    indicatePessimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
+
+  std::function<bool(Value &)> Pred = this->generatePredicate(A);
+  if (!AARetVal->checkForallReturnedValues(Pred)) {
+    indicatePessimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
+  return ChangeStatus::UNCHANGED;
+}
+
+/// NonNull attribute for function argument.
+struct AANonNullArgument : AANonNullImpl {
+
+  AANonNullArgument(Argument &A, InformationCache &InfoCache)
+      : AANonNullImpl(A, InfoCache) {}
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_ARGUMENT;
+  }
+
+  /// See AbstractAttriubute::initialize(...).
+  void initialize(Attributor &A) override {
+    Argument *Arg = cast<Argument>(getAssociatedValue());
+    if (Arg->hasNonNullAttr())
+      indicateOptimisticFixpoint();
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  virtual ChangeStatus updateImpl(Attributor &A) override;
+};
+
+ChangeStatus AANonNullArgument::updateImpl(Attributor &A) {
+  Function &F = getAnchorScope();
+  Argument &Arg = cast<Argument>(getAnchoredValue());
+
+  unsigned ArgNo = Arg.getArgNo();
+
+  // Callback function
+  std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) {
+    assert(CS && "Sanity check: Call site was not initialized properly!");
+
+    if (CS.paramHasAttr(ArgNo, Attribute::NonNull))
+      return true;
+
+    auto *NonNullCSArgAA =
+        A.getAAFor<AANonNullImpl>(*this, *CS.getInstruction(), ArgNo);
+    if (!NonNullCSArgAA || !NonNullCSArgAA->isAssumedNonNull())
+      return false;
+
+    return true;
+  };
+
+  if (!A.checkForAllCallSites(F, CallSiteCheck, true)) {
+    indicatePessimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
+  return ChangeStatus::UNCHANGED;
+}
+
+/// NonNull attribute for a call site argument.
+struct AANonNullCallSiteArgument : public AANonNullImpl {
+
+  /// See AANonNullImpl::AANonNullImpl(...).
+  AANonNullCallSiteArgument(CallSite CS, InformationCache &InfoCache,
+                            uint32_t ArgNo)
+      : AANonNullImpl(*CS.getInstruction(), InfoCache), ArgNo(ArgNo) {}
+
+  void initialize(Attributor &A) override {
+    // Determine if the IR already provides enough information.
+    if (CallSite(&getAnchoredValue()).paramHasAttr(ArgNo, getAttrKind()))
+      indicateOptimisticFixpoint();
+  }
+
+  /// See AbstractAttribute::updateImpl(Attributor &A).
+  virtual ChangeStatus updateImpl(Attributor &A) override;
+
+  /// See AbstractAttribute::getAssociatedValue().
+  virtual Value *getAssociatedValue() override {
+    return CallSite(&getAnchoredValue()).getArgument(ArgNo);
+  }
+
+  /// See AbstractAttribute::getAssociatedValue().
+  virtual const Value *getAssociatedValue() const override {
+    return ImmutableCallSite(&getAnchoredValue()).getArgument(ArgNo);
+  }
+
+  /// Return associated values's argument index.
+  int getArgumentNo() const { return ArgNo; }
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_CALL_SITE_ARGUMENT;
+  };
+
+private:
+  /// The underlying value is the argument at position "ArgNo" of the call site
+  /// that is used as the underyling anchor. See
+  /// AbstractAttribute::getAssociatedValue().
+  const unsigned ArgNo;
+};
+
+ChangeStatus AANonNullCallSiteArgument::updateImpl(Attributor &A) {
+  Value &V = *getAssociatedValue();
+
+  auto *AANonNull = A.getAAFor<AANonNullImpl>(*this, V);
+  if (!AANonNull || !AANonNull->isAssumedNonNull()) {
+    indicatePessimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
+
+  return ChangeStatus::UNCHANGED;
+}
+
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 ChangeStatus Attributor::run() {
   // Initialize all abstract attributes.
   for (AbstractAttribute *AA : AllAbstractAttributes)
     AA->initialize(*this);
void Attributor::identifyDefaultAbstractAttributes(
 
   // Return attributes are only appropriate if the return type is non void.
   Type *ReturnType = F.getReturnType();
   if (!ReturnType->isVoidTy()) {
     // Argument attribute "returned" --- Create only one per function even
     // 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 argument with pointer type might be marked nonnull.
+  for (Argument &Arg : F.args()) {
+    if (Arg.getType()->isPointerTy())
+      registerAA(*new AANonNullArgument(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];
 
default:
       break;
     case Instruction::Ret: // ReturnInst are interesting for AAReturnedValues.
       IsInterestingOpcode = true;
     }
     if (IsInterestingOpcode)
       InstOpcodeMap[I.getOpcode()].push_back(&I);
     if (I.mayReadOrWriteMemory())
       ReadOrWriteInsts.push_back(&I);
-  }
+
+    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, InfoCache, i));
+      }
+    }
+  }
+
+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());
+    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 (Pred(CS))
+      continue;
+
+    LLVM_DEBUG(dbgs() << "Attributor: Call site callback failed for "
+                      << *CS.getInstruction() << "\n");
+    return false;
+  }
+
+  return true;
 }
 
 /// Helpers to ease debugging through output streams and print calls.
 ///
 ///{
 raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) {
   return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
 }

llvm/test/Transforms/FunctionAttrs/arg_returned.ll

 ;
 ; int* rt1(int *a) {
 ;   return *a ? undef : rt1(a);
 ; }
 ;
 ; FIXME: no-return missing
 ; FNATTR:  define noalias i32* @rt1(i32* nocapture readonly %a)
 ; BOTH: Function Attrs: noinline nounwind readonly uwtable
-; BOTH-NEXT:    define noalias i32* @rt1(i32* nocapture readonly %a)
+; BOTH-NEXT:    define noalias nonnull i32* @rt1(i32* nocapture readonly %a)
 define i32* @rt1(i32* %a) #0 {
 entry:
   %v = load i32, i32* %a, align 4
   %tobool = icmp ne i32 %v, 0
   %call = call i32* @rt1(i32* %a)
   %sel = select i1 %tobool, i32* undef, i32* %call
   ret i32* %sel
 }

llvm/test/Transforms/FunctionAttrs/nonnull.ll

 ; RUN: opt -S -functionattrs -enable-nonnull-arg-prop %s | FileCheck %s
 ; RUN: opt -S -passes=function-attrs -enable-nonnull-arg-prop %s | FileCheck %s
+; RUN: opt -attributor --attributor-disable=false -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
 
 declare nonnull i8* @ret_nonnull()
 
 ; Return a pointer trivially nonnull (call return attribute)
 define i8* @test1() {
 ; CHECK: define nonnull i8* @test1
+; ATTRIBUTOR: define nonnull i8* @test1
   %ret = call i8* @ret_nonnull()
   ret i8* %ret
 }
 
 ; Return a pointer trivially nonnull (argument attribute)
 define i8* @test2(i8* nonnull %p) {
 ; CHECK: define nonnull i8* @test2
+; ATTRIBUTOR: define nonnull i8* @test2
   ret i8* %p
 }
 
 ; Given an SCC where one of the functions can not be marked nonnull,
 ; can we still mark the other one which is trivially nonnull
 define i8* @scc_binder() {
 ; CHECK: define i8* @scc_binder
+; ATTRIBUTOR: define i8* @scc_binder
   call i8* @test3()
   ret i8* null
 }
 
 define i8* @test3() {
 ; CHECK: define nonnull i8* @test3
+; ATTRIBUTOR: define nonnull i8* @test3
   call i8* @scc_binder()
   %ret = call i8* @ret_nonnull()
   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() {
 ; CHECK: define noalias nonnull i8* @test4_helper
+; ATTRIBUTOR: define nonnull i8* @test4_helper
   %ret = call i8* @test4()
   ret i8* %ret
 }
 
 define i8* @test4() {
 ; CHECK: define noalias nonnull i8* @test4
+; ATTRIBUTOR: define nonnull 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() {
 ; CHECK: define noalias i8* @test5_helper
+; ATTRIBUTOR: define i8* @test5_helper
   %ret = call i8* @test5()
   ret i8* null
 }
 
 define i8* @test5() {
 ; CHECK: define noalias i8* @test5
+; ATTRIBUTOR: define i8* @test5
   %ret = call i8* @test5_helper()
   ret i8* %ret
 }
 
 ; Local analysis, but going through a self recursive phi
 define i8* @test6() {
 entry:
 ; CHECK: define nonnull i8* @test6
+; ATTRIBUTOR: define nonnull i8* @test6
   %ret = call i8* @ret_nonnull()
   br label %loop
 loop:
   %phi = phi i8* [%ret, %entry], [%phi, %loop]
   br i1 undef, label %loop, label %exit
 exit:
   ret i8* %phi
 }
 
+; CHECK: define i8* @test7
+; ATTRIBUTOR: define i8* @test7
+define i8* @test7(i8* %a) {
+  %b = getelementptr inbounds i8, i8* %a, i64 0
+  ret i8* %b
+}
+
+; CHECK: define nonnull i8* @test8
+; ATTRIBUTOR: define nonnull i8* @test8
+define i8* @test8(i8* %a) {
+  %b = getelementptr inbounds i8, i8* %a, i64 1
+  ret i8* %b
+}
+
+; CHECK: define i8* @test9
+; ATTRIBUTOR: define i8* @test9
+define i8* @test9(i8* %a, i64 %n) {
+  %b = getelementptr inbounds i8, i8* %a, i64 %n
+  ret i8* %b
+}
+
+declare void @llvm.assume(i1)
+; CHECK: define i8* @test10
+; FIXME: missing nonnull
+; ATTRIBUTOR: define i8* @test10
+define i8* @test10(i8* %a, i64 %n) {
+  %cmp = icmp ne i64 %n, 0 
+  call void @llvm.assume(i1 %cmp)
+  %b = getelementptr inbounds i8, i8* %a, i64 %n
+  ret i8* %b
+}
+
+; TEST 11
+; char* test11(char *p) {
+;   return p? p: nonnull();
+; }
+; CHECK: define i8* @test11
+; FIXME: missing nonnull
+; ATTRIBUTOR: define i8* @test11
+define i8* @test11(i8*) local_unnamed_addr {
+  %2 = icmp eq i8* %0, null
+  br i1 %2, label %3, label %5
+
+; <label>:3:                                      ; preds = %1
+  %4 = tail call i8* @nonnull(i64 1)
+  br label %5
+
+; <label>:5:                                      ; preds = %3, %1
+  %6 = phi i8* [ %4, %3 ], [ %0, %1 ]
+  ret i8* %6
+}
+
+; TEST 12
+; Simple CallSite Test
+declare void @test12_helper(i8*)
+define void @test12(i8* nonnull %a) {
+; ATTRIBUTOR: define void @test12(i8* nonnull %a)
+; ATTRIBUTOR-NEXT: tail call void @test12_helper(i8* nonnull %a)
+  tail call void @test12_helper(i8* %a)
+  ret void
+}
+
+; TEST 13
+; Simple Argument Tests
+define void @test13_helper(i8* nonnull %a) {
+; ATTRIBUTOR: define void @test13_helper(i8* nonnull %a)
+  ret void
+}
+define internal void @test13(i8* %a) {
+; ATTRIBUTOR: define internal void @test13(i8* nonnull %a)
+  tail call void @test13_helper(i8* %a)
+  ret void
+}
+
+declare nonnull i8* @nonnull(i64)
+
+
 ; 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);
 declare void @use3nonnull(i8* nonnull %x, i8* nonnull %y, i8* nonnull %z);
 
 declare i8 @use1safecall(i8* %x) readonly nounwind ; readonly+nounwind guarantees that execution continues to successor
 
 ; Can't extend non-null to parent for any argument because the 2nd call is not guaranteed to execute.
 
 define void @parent1(i8* %a, i8* %b, i8* %c) {
 ; CHECK-LABEL: @parent1(i8* %a, i8* %b, i8* %c)
 ; CHECK-NEXT:    call void @use3(i8* %c, i8* %a, i8* %b)
 ; CHECK-NEXT:    call void @use3nonnull(i8* %b, i8* %c, i8* %a)
 ; CHECK-NEXT:    ret void
 ;
+; ATTRIBUTOR-LABEL: @parent1(i8* %a, i8* %b, i8* %c)
+; ATTRIBUTOR-NEXT:    call void @use3(i8* %c, i8* %a, i8* %b)
+; ATTRIBUTOR-NEXT:    call void @use3nonnull(i8* nonnull %b, i8* nonnull %c, i8* nonnull %a)
+; ATTRIBUTOR-NEXT:    ret void
+
   call void @use3(i8* %c, i8* %a, i8* %b)
   call void @use3nonnull(i8* %b, i8* %c, i8* %a)
   ret void
 }
 
 ; Extend non-null to parent for all arguments.
 
 define void @parent2(i8* %a, i8* %b, i8* %c) {
 ; CHECK-LABEL: @parent2(i8* nonnull %a, i8* nonnull %b, i8* nonnull %c)
 ; CHECK-NEXT:    call void @use3nonnull(i8* %b, i8* %c, i8* %a)
 ; CHECK-NEXT:    call void @use3(i8* %c, i8* %a, i8* %b)
 ; CHECK-NEXT:    ret void
 ;
+; ATTRIBUTOR-LABEL: @parent2(i8* %a, i8* %b, i8* %c)
+; ATTRIBUTOR-NEXT:    call void @use3nonnull(i8* nonnull %b, i8* nonnull %c, i8* nonnull %a)
+; ATTRIBUTOR-NEXT:    call void @use3(i8* %c, i8* %a, i8* %b)
+; ATTRIBUTOR-NEXT:    ret void
+
   call void @use3nonnull(i8* %b, i8* %c, i8* %a)
   call void @use3(i8* %c, i8* %a, i8* %b)
   ret void
 }
 
 ; Extend non-null to parent for 1st argument.
 
 define void @parent3(i8* %a, i8* %b, i8* %c) {
 ; CHECK-LABEL: @parent3(i8* nonnull %a, i8* %b, i8* %c)
 ; CHECK-NEXT:    call void @use1nonnull(i8* %a)
 ; CHECK-NEXT:    call void @use3(i8* %c, i8* %b, i8* %a)
 ; CHECK-NEXT:    ret void
 ;
+; ATTRIBUTOR-LABEL: @parent3(i8* %a, i8* %b, i8* %c)
+; ATTRIBUTOR-NEXT:    call void @use1nonnull(i8* nonnull %a)
+; ATTRIBUTOR-NEXT:    call void @use3(i8* %c, i8* %b, i8* %a)
+; ATTRIBUTOR-NEXT:    ret void
+
   call void @use1nonnull(i8* %a)
   call void @use3(i8* %c, i8* %b, i8* %a)
   ret void
 }
 
 ; Extend non-null to parent for last 2 arguments.
 
 define void @parent4(i8* %a, i8* %b, i8* %c) {
 ; CHECK-LABEL: @parent4(i8* %a, i8* nonnull %b, i8* nonnull %c)
 ; CHECK-NEXT:    call void @use2nonnull(i8* %c, i8* %b)
 ; CHECK-NEXT:    call void @use2(i8* %a, i8* %c)
 ; CHECK-NEXT:    call void @use1(i8* %b)
 ; CHECK-NEXT:    ret void
 ;
+; ATTRIBUTOR-LABEL: @parent4(i8* %a, i8* %b, i8* %c)
+; ATTRIBUTOR-NEXT:    call void @use2nonnull(i8* nonnull %c, i8* nonnull %b)
+; ATTRIBUTOR-NEXT:    call void @use2(i8* %a, i8* %c)
+; ATTRIBUTOR-NEXT:    call void @use1(i8* %b)
+; ATTRIBUTOR-NEXT:    ret void
+ 
   call void @use2nonnull(i8* %c, i8* %b)
   call void @use2(i8* %a, i8* %c)
   call void @use1(i8* %b)
   ret void
 }
 
 ; The callsite must execute in order for the attribute to transfer to the parent.
 ; It appears benign to extend non-null to the parent in this case, but we can't do that
 ; because it would incorrectly propagate the wrong information to its callers.
 
 define void @parent5(i8* %a, i1 %a_is_notnull) {
 ; CHECK-LABEL: @parent5(i8* %a, i1 %a_is_notnull)
 ; CHECK-NEXT:    br i1 %a_is_notnull, label %t, label %f
 ; CHECK:       t:
 ; CHECK-NEXT:    call void @use1nonnull(i8* %a)
 ; CHECK-NEXT:    ret void
 ; CHECK:       f:
 ; CHECK-NEXT:    ret void
 ;
+; ATTRIBUTOR-LABEL: @parent5(i8* %a, i1 %a_is_notnull)
+; ATTRIBUTOR-NEXT:    br i1 %a_is_notnull, label %t, label %f
+; ATTRIBUTOR:       t:
+; ATTRIBUTOR-NEXT:    call void @use1nonnull(i8* nonnull %a)
+; ATTRIBUTOR-NEXT:    ret void
+; ATTRIBUTOR:       f:
+; ATTRIBUTOR-NEXT:    ret void
+
   br i1 %a_is_notnull, label %t, label %f
 t:
   call void @use1nonnull(i8* %a)
   ret void
 f:
   ret void
 }
 
 ; The callsite must execute in order for the attribute to transfer to the parent.
 ; The volatile load might trap, so there's no guarantee that we'll ever get to the call.
 
 define i8 @parent6(i8* %a, i8* %b) {
 ; CHECK-LABEL: @parent6(i8* %a, i8* %b)
 ; CHECK-NEXT:    [[C:%.*]] = load volatile i8, i8* %b
 ; CHECK-NEXT:    call void @use1nonnull(i8* %a)
 ; CHECK-NEXT:    ret i8 [[C]]
 ;
+; ATTRIBUTOR-LABEL: @parent6(i8* %a, i8* %b)
+; ATTRIBUTOR-NEXT:    [[C:%.*]] = load volatile i8, i8* %b
+; ATTRIBUTOR-NEXT:    call void @use1nonnull(i8* nonnull %a)
+; ATTRIBUTOR-NEXT:    ret i8 [[C]]
+
   %c = load volatile i8, i8* %b
   call void @use1nonnull(i8* %a)
   ret i8 %c
 }
 
 ; The nonnull callsite is guaranteed to execute, so the argument must be nonnull throughout the parent.
 
 define i8 @parent7(i8* %a) {
 ; CHECK-LABEL: @parent7(i8* nonnull %a)
 ; CHECK-NEXT:    [[RET:%.*]] = call i8 @use1safecall(i8* %a)
 ; CHECK-NEXT:    call void @use1nonnull(i8* %a)
 ; CHECK-NEXT:    ret i8 [[RET]]
 ;
+; ATTRIBUTOR-LABEL: @parent7(i8* %a)
+; ATTRIBUTOR-NEXT:    [[RET:%.*]] = call i8 @use1safecall(i8* %a)
+; ATTRIBUTOR-NEXT:    call void @use1nonnull(i8* nonnull %a)
+; ATTRIBUTOR-NEXT:    ret i8 [[RET]]
+ 
   %ret = call i8 @use1safecall(i8* %a)
   call void @use1nonnull(i8* %a)
   ret i8 %ret
 }
 
 ; Make sure that an invoke works similarly to a call.
 
 declare i32 @esfp(...)
 
 define i1 @parent8(i8* %a, i8* %bogus1, i8* %b) personality i8* bitcast (i32 (...)* @esfp to i8*){
 ; CHECK-LABEL: @parent8(i8* nonnull %a, i8* nocapture readnone %bogus1, i8* nonnull %b)
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    invoke void @use2nonnull(i8* %a, i8* %b)
 ; CHECK-NEXT:    to label %cont unwind label %exc
 ; CHECK:       cont:
 ; CHECK-NEXT:    [[NULL_CHECK:%.*]] = icmp eq i8* %b, null
 ; CHECK-NEXT:    ret i1 [[NULL_CHECK]]
 ; CHECK:       exc:
 ; CHECK-NEXT:    [[LP:%.*]] = landingpad { i8*, i32 }
 ; CHECK-NEXT:    filter [0 x i8*] zeroinitializer
 ; CHECK-NEXT:    unreachable
 ;
+; ATTRIBUTOR-LABEL: @parent8(i8* %a, i8* %bogus1, i8* %b)
+; ATTRIBUTOR-NEXT:  entry:
+; ATTRIBUTOR-NEXT:    invoke void @use2nonnull(i8* nonnull %a, i8* nonnull %b)
+; ATTRIBUTOR-NEXT:    to label %cont unwind label %exc
+; ATTRIBUTOR:       cont:
+; ATTRIBUTOR-NEXT:    [[NULL_ATTRIBUTOR:%.*]] = icmp eq i8* %b, null
+; ATTRIBUTOR-NEXT:    ret i1 [[NULL_ATTRIBUTOR]]
+; ATTRIBUTOR:       exc:
+; ATTRIBUTOR-NEXT:    [[LP:%.*]] = landingpad { i8*, i32 }
+; ATTRIBUTOR-NEXT:    filter [0 x i8*] zeroinitializer
+; ATTRIBUTOR-NEXT:    unreachable
+ 
 entry:
   invoke void @use2nonnull(i8* %a, i8* %b)
   to label %cont unwind label %exc
 
 cont:
   %null_check = icmp eq i8* %b, null
   ret i1 %null_check