[Attributor] Using liveness in other attributes.

[sstefan1]

Summary

Modifying other AbstractAttributes to use Liveness AA and skip dead instructions.

[jdoerfert]

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

676 ↗

(On Diff #211599)

SmallPtrSetImpl<ReturnInst *> &

llvm/lib/Transforms/IPO/Attributor.cpp

639 ↗

(On Diff #211599)

Do not modify UniqueRV and do return true to indicate this return value was handled and all is OK. The idea is, when dead then ignore the return value.

675 ↗

(On Diff #211599)

& missing

715 ↗

(On Diff #211599)

Move into a helper function.

[sstefan1]

• adding instruction-wise is Assumed/Known Dead checks. This resolves FIXME in TEST 2.
• addressing comments
  
  It should be noted that there is still a problem in AAReturnedValues. I will have to do a debug build, which will take quiet a lot of time, to investigate further.

[sstefan1]

• Fixing returnedvalues issues and some minor fixes

[jdoerfert]

some comments, no major problem though.

llvm/lib/Transforms/IPO/Attributor.cpp

582 ↗

(On Diff #212298)

Maybe move this as a member into AAIsDead with the argument beeing a ArrayRef<Instruction *> so we can reuse it

592 ↗

(On Diff #212298)

return true;

767 ↗

(On Diff #212298)

I'll commit these changes as a fix today.

1252 ↗

(On Diff #212298)

Let's move this logic into the checkForAllCallSites call so all users benefit.

1587 ↗

(On Diff #212298)

please add an assert (also above) to verify I (or BB) is in the AnchoredScope.

1611 ↗

(On Diff #212298)

return getKnown() && isAssumedDead(I)

to reduce duplication of logic.

1709 ↗

(On Diff #212298)

// At least one new instruction encountered.

llvm/test/Transforms/FunctionAttrs/arg_returned.ll

751 ↗

(On Diff #212298)

Please keep these and add the additional attribute sets instead.

[sstefan1]

• addressing comments.

[sstefan1]

• removed leftover comments

[jdoerfert]

Almost there. I added a last set of comments, most minor.

Could you add one more test case:

internal function foo, called 2 times but one call site is dead. We want to derive something about foo from the call site.

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

866 ↗

(On Diff #212595)

Thanks for this generic version. Please add doxygen documentation as well.

llvm/lib/Transforms/IPO/Attributor.cpp

630 ↗

(On Diff #212595)

If you want LivenessAA might not be available, check for null.

702 ↗

(On Diff #212595)

Test for nullptr.

965 ↗

(On Diff #212595)

Comments here and elsewhere say "blocks" but check instructions.

1241 ↗

(On Diff #212595)

Pass this as reference (as we always do in the Attributor).

1714 ↗

(On Diff #212595)

Nit: CS->getFunction() or CS.getInstruction()->getFunction()

1718 ↗

(On Diff #212595)

not return true but continue! Only this call site is OK if it is dead.

llvm/test/Transforms/FunctionAttrs/liveness.ll

64 ↗

(On Diff #212595)

remove the comment.

[sstefan1]

• Added 1 test case, addressed comments.

[sstefan1]

In D65243#1608667, @jdoerfert wrote:

Could you add one more test case:

internal function foo, called 2 times but one call site is dead. We want to derive something about foo from the call site.

Is this what you had in mind?

[jdoerfert]

One minor thing and one change request + test. Other than that, LGTM.

llvm/lib/Transforms/IPO/Attributor.cpp

1721 ↗

(On Diff #212787)

Move the liveness stuff before the CallSite CS stuff. If the user is dead, it does not matter if it is a call site, a direct call site, etc., it is dead after all.

Also add a test for this please, e.g., pass the function pointer to a another unknown function or store it away but the instruction that does so is dead.

1241 ↗

(On Diff #212595)

Please pass this as a reference not pointer.

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

void identifyDefaultAbstractAttributes(
       DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist = nullptr);
 
   /// Check \p Pred on all function call sites.
   ///
   /// 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);
+                            bool RequireAllCallSites, AbstractAttribute &AA);
 
 private:
   /// The set of all abstract attributes.
   ///{
   using AAVector = SmallVector<AbstractAttribute *, 64>;
   AAVector AllAbstractAttributes;
   ///}
 
struct AAReturnedValues : public AbstractAttribute {
   AAReturnedValues(Function &F, InformationCache &InfoCache)
       : AbstractAttribute(F, InfoCache) {}
 
   /// Check \p Pred on all returned values.
   ///
   /// This method will evaluate \p Pred on returned values and return
   /// true if (1) all returned values are known, and (2) \p Pred returned true
   /// for all returned values.
-  virtual bool
-  checkForallReturnedValues(std::function<bool(Value &)> &Pred) const = 0;
+  virtual bool checkForallReturnedValues(
+      std::function<bool(Value &, const SmallPtrSetImpl<ReturnInst *> &)> &Pred)
+      const = 0;
 
   /// See AbstractAttribute::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::Returned;
 };
 
struct AAIsDead : public AbstractAttribute {
   static constexpr Attribute::AttrKind ID =
       Attribute::AttrKind(Attribute::EndAttrKinds + 1);
 
   /// 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;
+
+  /// Returns true if \p I is assumed dead.
+  virtual bool isAssumedDead(Instruction *I) const = 0;
+
+  /// Returns true if \p I is known dead.
+  virtual bool isKnownDead(Instruction *I) const = 0;
+
+  /// This method is used to check if at least one instruction in a collection
+  /// of instructions is live.
+  template <typename T> bool isLiveInstSet(T begin, T end) const {
+    for (T I = begin; I != end; ++I) {
+      assert(isa<Instruction>(*I) && "It has to be collection of Instructions");
+      assert((*I)->getParent()->getParent() == &getAnchorScope() &&
+             "Instruction must be in the same anchor scope function.");
+
+      if (!isAssumedDead(*I))
+        return true;
+    }
+
+    return false;
+  }
 };
 
 /// An abstract interface for all dereferenceable attribute.
 struct AADereferenceable : public AbstractAttribute {
 
   /// See AbstractAttribute::AbstractAttribute(...).
   AADereferenceable(Value &V, InformationCache &InfoCache)
       : AbstractAttribute(V, InfoCache) {}

llvm/trunk/lib/Transforms/IPO/Attributor.cpp

ChangeStatus AANoUnwindFunction::updateImpl(Attributor &A) {
 
   // The map from instruction opcodes to those instructions in the function.
   auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
   auto Opcodes = {
       (unsigned)Instruction::Invoke,      (unsigned)Instruction::CallBr,
       (unsigned)Instruction::Call,        (unsigned)Instruction::CleanupRet,
       (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume};
 
+  auto *LivenessAA = A.getAAFor<AAIsDead>(*this, F);
+
   for (unsigned Opcode : Opcodes) {
     for (Instruction *I : OpcodeInstMap[Opcode]) {
+      // Skip dead instructions.
+      if (LivenessAA && LivenessAA->isAssumedDead(I))
+        continue;
+
       if (!I->mayThrow())
         continue;
 
       auto *NoUnwindAA = A.getAAFor<AANoUnwind>(*this, *I);
 
       if (!NoUnwindAA || !NoUnwindAA->isAssumedNoUnwind()) {
         indicatePessimisticFixpoint();
         return ChangeStatus::CHANGED;
public:
   /// Return the number of potential return values, -1 if unknown.
   size_t getNumReturnValues() const {
     return isValidState() ? ReturnedValues.size() : -1;
   }
 
   /// Return an assumed unique return value if a single candidate is found. If
   /// there cannot be one, return a nullptr. If it is not clear yet, return the
   /// Optional::NoneType.
-  Optional<Value *> getAssumedUniqueReturnValue() const;
+  Optional<Value *> getAssumedUniqueReturnValue(const AAIsDead *LivenessAA) const;
 
   /// See AbstractState::checkForallReturnedValues(...).
-  bool
-  checkForallReturnedValues(std::function<bool(Value &)> &Pred) const override;
+  bool checkForallReturnedValues(
+      std::function<bool(Value &, const SmallPtrSetImpl<ReturnInst *> &)> &Pred)
+      const override;
 
   /// Pretty print the attribute similar to the IR representation.
   const std::string getAsStr() const override;
 
   /// See AbstractState::isAtFixpoint().
   bool isAtFixpoint() const override { return IsFixed; }
 
   /// See AbstractState::isValidState().
   bool isValidState() const override { return IsValidState; }
 
   /// See AbstractState::indicateOptimisticFixpoint(...).
   void indicateOptimisticFixpoint() override {
     IsFixed = true;
     IsValidState &= true;
   }
+
   void indicatePessimisticFixpoint() override {
     IsFixed = true;
     IsValidState = false;
   }
 };
 
 ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) {
   ChangeStatus Changed = ChangeStatus::UNCHANGED;
 
   // Bookkeeping.
   assert(isValidState());
   NumFnKnownReturns++;
 
+  auto *LivenessAA = A.getAAFor<AAIsDead>(*this, getAnchorScope());
+
   // Check if we have an assumed unique return value that we could manifest.
-  Optional<Value *> UniqueRV = getAssumedUniqueReturnValue();
+  Optional<Value *> UniqueRV = getAssumedUniqueReturnValue(LivenessAA);
 
   if (!UniqueRV.hasValue() || !UniqueRV.getValue())
     return Changed;
 
   // Bookkeeping.
   NumFnUniqueReturned++;
 
   // If the assumed unique return value is an argument, annotate it.
   if (auto *UniqueRVArg = dyn_cast<Argument>(UniqueRV.getValue())) {
     AssociatedVal = UniqueRVArg;
     Changed = AbstractAttribute::manifest(A) | Changed;
   }
 
   return Changed;
 }
 
 const std::string AAReturnedValuesImpl::getAsStr() const {
   return (isAtFixpoint() ? "returns(#" : "may-return(#") +
          (isValidState() ? std::to_string(getNumReturnValues()) : "?") + ")";
 }
 
-Optional<Value *> AAReturnedValuesImpl::getAssumedUniqueReturnValue() const {
+Optional<Value *> AAReturnedValuesImpl::getAssumedUniqueReturnValue(
+    const AAIsDead *LivenessAA) const {
   // If checkForallReturnedValues provides a unique value, ignoring potential
   // undef values that can also be present, it is assumed to be the actual
   // return value and forwarded to the caller of this method. If there are
   // multiple, a nullptr is returned indicating there cannot be a unique
   // returned value.
   Optional<Value *> UniqueRV;
 
-  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
+  std::function<bool(Value &, const SmallPtrSetImpl<ReturnInst *> &)> Pred =
+      [&](Value &RV, const SmallPtrSetImpl<ReturnInst *> &RetInsts) -> bool {
+
+    // If all ReturnInsts are dead, then ReturnValue is dead as well
+    // and can be ignored.
+    if (LivenessAA &&
+        !LivenessAA->isLiveInstSet(RetInsts.begin(), RetInsts.end()))
+      return true;
+
     // If we found a second returned value and neither the current nor the saved
     // one is an undef, there is no unique returned value. Undefs are special
     // since we can pretend they have any value.
     if (UniqueRV.hasValue() && UniqueRV != &RV &&
         !(isa<UndefValue>(RV) || isa<UndefValue>(UniqueRV.getValue()))) {
       UniqueRV = nullptr;
       return false;
     }
 
     // Do not overwrite a value with an undef.
     if (!UniqueRV.hasValue() || !isa<UndefValue>(RV))
       UniqueRV = &RV;
 
     return true;
   };
 
   if (!checkForallReturnedValues(Pred))
     UniqueRV = nullptr;
 
   return UniqueRV;
 }
 
 bool AAReturnedValuesImpl::checkForallReturnedValues(
-    std::function<bool(Value &)> &Pred) const {
+    std::function<bool(Value &, const SmallPtrSetImpl<ReturnInst *> &)> &Pred)
+    const {
   if (!isValidState())
     return false;
 
   // Check all returned values but ignore call sites as long as we have not
   // encountered an overdefined one during an update.
   for (auto &It : ReturnedValues) {
     Value *RV = It.first;
+    const SmallPtrSetImpl<ReturnInst *> &RetInsts = It.second;
 
     ImmutableCallSite ICS(RV);
     if (ICS && !HasOverdefinedReturnedCalls)
       continue;
 
-    if (!Pred(*RV))
+    if (!Pred(*RV, RetInsts))
       return false;
   }
 
   return true;
 }
 
 ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
 
   // Check if we know of any values returned by the associated function,
   // if not, we are done.
   if (getNumReturnValues() == 0) {
     indicateOptimisticFixpoint();
     return ChangeStatus::UNCHANGED;
   }
 
   // Check if any of the returned values is a call site we can refine.
   decltype(ReturnedValues) AddRVs;
   bool HasCallSite = false;
 
   // Keep track of any change to trigger updates on dependent attributes.
   ChangeStatus Changed = ChangeStatus::UNCHANGED;
 
+  auto *LivenessAA = A.getAAFor<AAIsDead>(*this, getAnchorScope());
+
   // Look at all returned call sites.
   for (auto &It : ReturnedValues) {
     SmallPtrSet<ReturnInst *, 2> &ReturnInsts = It.second;
     Value *RV = It.first;
+
+    // Ignore dead ReturnValues.
+    if (LivenessAA && !LivenessAA->isLiveInstSet(ReturnInsts.begin(), ReturnInsts.end()))
+      continue;
+
     LLVM_DEBUG(dbgs() << "[AAReturnedValues] Potentially returned value " << *RV
                       << "\n");
 
     // Only call sites can change during an update, ignore the rest.
     CallSite RetCS(RV);
     if (!RetCS)
       continue;
 
if (!RetCSAA) {
         Changed = ChangeStatus::CHANGED;
       HasOverdefinedReturnedCalls = true;
       LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site (" << *RV
                         << ") with " << (RetCSAA ? "invalid" : "no")
                         << " associated state\n");
       continue;
     }
 
+    auto *LivenessCSAA = A.getAAFor<AAIsDead>(*this, RetCSAA->getAnchorScope());
+
     // Try to find a assumed unique return value for the called function.
-    Optional<Value *> AssumedUniqueRV = RetCSAA->getAssumedUniqueReturnValue();
+    Optional<Value *> AssumedUniqueRV =
+        RetCSAA->getAssumedUniqueReturnValue(LivenessCSAA);
 
     // If no assumed unique return value was found due to the lack of
     // candidates, we may need to resolve more calls (through more update
     // iterations) or the called function will not return. Either way, we simply
     // stick with the call sites as return values. Because there were not
     // multiple possibilities, we do not treat it as overdefined.
     if (!AssumedUniqueRV.hasValue())
       continue;
bool AANoSyncFunction::isVolatile(Instruction *I) {
   default:
     return false;
   }
 }
 
 ChangeStatus AANoSyncFunction::updateImpl(Attributor &A) {
   Function &F = getAnchorScope();
 
+  auto *LivenessAA = A.getAAFor<AAIsDead>(*this, F);
+
   /// We are looking for volatile instructions or Non-Relaxed atomics.
   /// FIXME: We should ipmrove the handling of intrinsics.
   for (Instruction *I : InfoCache.getReadOrWriteInstsForFunction(F)) {
+    // Skip assumed dead instructions.
+    if (LivenessAA && LivenessAA->isAssumedDead(I))
+      continue;
+
     ImmutableCallSite ICS(I);
     auto *NoSyncAA = A.getAAFor<AANoSyncFunction>(*this, *I);
 
     if (isa<IntrinsicInst>(I) && isNoSyncIntrinsic(I))
       continue;
 
     if (ICS && (!NoSyncAA || !NoSyncAA->isAssumedNoSync()) &&
         !ICS.hasFnAttr(Attribute::NoSync)) {
ChangeStatus AANoSyncFunction::updateImpl(Attributor &A) {
   }
 
   auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
   auto Opcodes = {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
                   (unsigned)Instruction::Call};
 
   for (unsigned Opcode : Opcodes) {
     for (Instruction *I : OpcodeInstMap[Opcode]) {
+      // Skip assumed dead instructions.
+      if (LivenessAA && LivenessAA->isAssumedDead(I))
+        continue;
       // At this point we handled all read/write effects and they are all
       // nosync, so they can be skipped.
       if (I->mayReadOrWriteMemory())
         continue;
 
       ImmutableCallSite ICS(I);
 
       // non-convergent and readnone imply nosync.
struct AANoFreeFunction : AbstractAttribute, BooleanState {
 
   /// The identifier used by the Attributor for this class of attributes.
   static constexpr Attribute::AttrKind ID = Attribute::NoFree;
 };
 
 ChangeStatus AANoFreeFunction::updateImpl(Attributor &A) {
   Function &F = getAnchorScope();
 
+  auto *LivenessAA = A.getAAFor<AAIsDead>(*this, F);
+
   // The map from instruction opcodes to those instructions in the function.
   auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
 
   for (unsigned Opcode :
        {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
         (unsigned)Instruction::Call}) {
     for (Instruction *I : OpcodeInstMap[Opcode]) {
-
+      // Skip assumed dead instructions.
+      if (LivenessAA && LivenessAA->isAssumedDead(I))
+        continue;
       auto ICS = ImmutableCallSite(I);
       auto *NoFreeAA = A.getAAFor<AANoFreeFunction>(*this, *I);
 
       if ((!NoFreeAA || !NoFreeAA->isAssumedNoFree()) &&
           !ICS.hasFnAttr(Attribute::NoFree)) {
         indicatePessimisticFixpoint();
         return ChangeStatus::CHANGED;
       }
struct AANonNullImpl : AANonNull, BooleanState {
   bool isKnownNonNull() const override { return getKnown(); }
 
   /// Generate a predicate that checks if a given value is assumed 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 &, const SmallPtrSetImpl<ReturnInst *> &)>
+  generatePredicate(Attributor &);
 };
 
-std::function<bool(Value &)> AANonNullImpl::generatePredicate(Attributor &A) {
+std::function<bool(Value &, const SmallPtrSetImpl<ReturnInst *> &)>
+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()))
+  std::function<bool(Value &, const SmallPtrSetImpl<ReturnInst *> &)> Pred =
+      [&](Value &RV, const SmallPtrSetImpl<ReturnInst *> &RetInsts) -> bool {
+    Function &F = getAnchorScope();
+
+    if (isKnownNonZero(&RV, F.getParent()->getDataLayout()))
       return true;
 
     auto *NonNullAA = A.getAAFor<AANonNull>(*this, RV);
 
     ImmutableCallSite ICS(&RV);
 
     if ((!NonNullAA || !NonNullAA->isAssumedNonNull()) &&
         (!ICS || !ICS.hasRetAttr(Attribute::NonNull)))
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);
+  std::function<bool(Value &, const SmallPtrSetImpl<ReturnInst *> &)> Pred =
+      this->generatePredicate(A);
+
   if (!AARetVal->checkForallReturnedValues(Pred)) {
     indicatePessimisticFixpoint();
     return ChangeStatus::CHANGED;
   }
   return ChangeStatus::UNCHANGED;
 }
 
 /// NonNull attribute for function argument.
if (CS.paramHasAttr(ArgNo, Attribute::NonNull))
       return true;
 
     Value *V = CS.getArgOperand(ArgNo);
     if (isKnownNonZero(V, getAnchorScope().getParent()->getDataLayout()))
       return true;
 
     return false;
   };
-  if (!A.checkForAllCallSites(F, CallSiteCheck, true)) {
+  if (!A.checkForAllCallSites(F, CallSiteCheck, true, *this)) {
     indicatePessimisticFixpoint();
     return ChangeStatus::CHANGED;
   }
   return ChangeStatus::UNCHANGED;
 }
 
 ChangeStatus AANonNullCallSiteArgument::updateImpl(Attributor &A) {
   // NOTE: Never look at the argument of the callee in this method.

 }
 
 ChangeStatus AAWillReturnFunction::updateImpl(Attributor &A) {
   Function &F = getAnchorScope();
 
   // The map from instruction opcodes to those instructions in the function.
   auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
 
+  auto *LivenessAA = A.getAAFor<AAIsDead>(*this, F);
+
   for (unsigned Opcode :
        {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
         (unsigned)Instruction::Call}) {
     for (Instruction *I : OpcodeInstMap[Opcode]) {
+      // Skip assumed dead instructions.
+      if (LivenessAA && LivenessAA->isAssumedDead(I))
+        continue;
+
       auto ICS = ImmutableCallSite(I);
 
       if (ICS.hasFnAttr(Attribute::WillReturn))
         continue;
 
       auto *WillReturnAA = A.getAAFor<AAWillReturn>(*this, *I);
       if (!WillReturnAA || !WillReturnAA->isAssumedWillReturn()) {
         indicatePessimisticFixpoint();
ChangeStatus AANoAliasReturned::updateImpl(Attributor &A) {
   Function &F = getAnchorScope();
 
   auto *AARetValImpl = A.getAAFor<AAReturnedValuesImpl>(*this, F);
   if (!AARetValImpl) {
     indicatePessimisticFixpoint();
     return ChangeStatus::CHANGED;
   }
 
-  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
+  std::function<bool(Value &, const SmallPtrSetImpl<ReturnInst *> &)> Pred =
+      [&](Value &RV, const SmallPtrSetImpl<ReturnInst *> &RetInsts) -> bool {
     if (Constant *C = dyn_cast<Constant>(&RV))
       if (C->isNullValue() || isa<UndefValue>(C))
         return true;
 
     /// For now, we can only deduce noalias if we have call sites.
     /// FIXME: add more support.
     ImmutableCallSite ICS(&RV);
     if (!ICS)
ChangeStatus manifest(Attributor &A) override {
     }
 
     return HasChanged;
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override;
 
-  /// See AAIsDead::isAssumedDead().
+  /// See AAIsDead::isAssumedDead(BasicBlock *).
   bool isAssumedDead(BasicBlock *BB) const override {
+    assert(BB->getParent() == &getAnchorScope() &&
+           "BB must be in the same anchor scope function.");
+
     if (!getAssumed())
       return false;
     return !AssumedLiveBlocks.count(BB);
   }
 
-  /// See AAIsDead::isKnownDead().
+  /// See AAIsDead::isKnownDead(BasicBlock *).
   bool isKnownDead(BasicBlock *BB) const override {
-    if (!getKnown())
+    return getKnown() && isAssumedDead(BB);
+  }
+
+  /// See AAIsDead::isAssumed(Instruction *I).
+  bool isAssumedDead(Instruction *I) const override {
+    assert(I->getParent()->getParent() == &getAnchorScope() &&
+           "Instruction must be in the same anchor scope function.");
+
+    if(!getAssumed())
       return false;
-    return !AssumedLiveBlocks.count(BB);
+
+    // If it is not in AssumedLiveBlocks then it for sure dead.
+    // Otherwise, it can still be after noreturn call in a live block.
+    if (!AssumedLiveBlocks.count(I->getParent()))
+      return true;
+
+    // If it is not after a noreturn call, than it is live.
+    if (!isAfterNoReturn(I))
+      return false;
+
+    // Definitely dead.
+    return true;
   }
 
+  /// See AAIsDead::isKnownDead(Instruction *I).
+  bool isKnownDead(Instruction *I) const override {
+    return getKnown() && isAssumedDead(I);
+  }
+
+  /// Check if instruction is after noreturn call, in other words, assumed dead.
+  bool isAfterNoReturn(Instruction *I) const;
+
   /// Collection of to be explored paths.
   SmallSetVector<Instruction *, 8> ToBeExploredPaths;
 
   /// Collection of all assumed live BasicBlocks.
   DenseSet<BasicBlock *> AssumedLiveBlocks;
 
   /// Collection of calls with noreturn attribute, assumed or knwon.
   SmallSetVector<Instruction *, 4> NoReturnCalls;
 };
 
+bool AAIsDeadFunction::isAfterNoReturn(Instruction *I) const {
+  Instruction *PrevI = I->getPrevNode();
+  while (PrevI) {
+    if (NoReturnCalls.count(PrevI))
+      return true;
+    PrevI = PrevI->getPrevNode();
+  }
+  return false;
+}
+
 bool AAIsDeadFunction::explorePath(Attributor &A, Instruction *I) {
   BasicBlock *BB = I->getParent();
 
   while (I) {
     ImmutableCallSite ICS(I);
 
     if (ICS) {
       auto *NoReturnAA = A.getAAFor<AANoReturn>(*this, *I);
for (Instruction *I : NoReturnChanged) {
     size_t Size = ToBeExploredPaths.size();
 
     // Still noreturn.
     if (!explorePath(A, I))
       continue;
 
     NoReturnCalls.remove(I);
 
+    // At least one new path.
+    Status = ChangeStatus::CHANGED;
+
     // No new paths.
     if (Size == ToBeExploredPaths.size())
       continue;
 
-    // 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");
+             << " Total number of blocks: " << getAnchorScope().size() << "\n");
 
   return Status;
 }
 
 /// -------------------- Dereferenceable Argument Attribute --------------------
 
 struct DerefState : AbstractState {
 
ChangeStatus AADereferenceableReturned::updateImpl(Attributor &A) {
   if (!AARetVal) {
     indicatePessimisticFixpoint();
     return ChangeStatus::CHANGED;
   }
 
   bool IsNonNull = isAssumedNonNull();
   bool IsGlobal = isAssumedGlobal();
 
-  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
+  std::function<bool(Value &, const SmallPtrSetImpl<ReturnInst *> &)> Pred =
+      [&](Value &RV, const SmallPtrSetImpl<ReturnInst *> &RetInsts) -> bool {
     takeAssumedDerefBytesMinimum(
         computeAssumedDerefenceableBytes(A, RV, IsNonNull, IsGlobal));
     return isValidState();
   };
 
   if (AARetVal->checkForallReturnedValues(Pred)) {
     updateAssumedNonNullGlobalState(IsNonNull, IsGlobal);
     return BeforeState == static_cast<DerefState>(*this)
std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) -> bool {
     }
 
     takeAssumedDerefBytesMinimum(computeAssumedDerefenceableBytes(
         A, *CS.getArgOperand(ArgNo), IsNonNull, IsGlobal));
 
     return isValidState();
   };
 
-  if (!A.checkForAllCallSites(F, CallSiteCheck, true)) {
+  if (!A.checkForAllCallSites(F, CallSiteCheck, true, *this)) {
     indicatePessimisticFixpoint();
     return ChangeStatus::CHANGED;
   }
 
   updateAssumedNonNullGlobalState(IsNonNull, IsGlobal);
 
   return BeforeState == static_cast<DerefState>(*this) ? ChangeStatus::UNCHANGED
                                                        : ChangeStatus::CHANGED;
ChangeStatus AAAlignReturned::updateImpl(Attributor &A) {
   }
 
   // Currently, align<n> is deduced if alignments in return values are assumed
   // as greater than n. We reach pessimistic fixpoint if any of the return value
   // wouldn't have align. If no assumed state was used for reasoning, an
   // optimistic fixpoint is reached earlier.
 
   base_t BeforeState = getAssumed();
-  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
+  std::function<bool(Value &, const SmallPtrSetImpl<ReturnInst *> &)> Pred =
+      [&](Value &RV, const SmallPtrSetImpl<ReturnInst *> &RetInsts) -> bool {
     auto *AlignAA = A.getAAFor<AAAlign>(*this, RV);
 
     if (AlignAA)
       takeAssumedMinimum(AlignAA->getAssumedAlign());
     else
       // Use IR information.
       takeAssumedMinimum(RV.getPointerAlignment(
           getAnchorScope().getParent()->getDataLayout()));
if (AlignAA) {
       }
     }
 
     Value *V = CS.getArgOperand(ArgNo);
     takeAssumedMinimum(V->getPointerAlignment(DL));
     return isValidState();
   };
 
-  if (!A.checkForAllCallSites(F, CallSiteCheck, true))
+  if (!A.checkForAllCallSites(F, CallSiteCheck, true, *this))
     indicatePessimisticFixpoint();
 
   return BeforeState == getAssumed() ? ChangeStatus::UNCHANGED
                                      : ChangeStatus ::CHANGED;
 }
 
 struct AAAlignCallSiteArgument : AAAlignImpl {
 

 }
 
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 bool Attributor::checkForAllCallSites(Function &F,
                                       std::function<bool(CallSite)> &Pred,
-                                      bool RequireAllCallSites) {
+                                      bool RequireAllCallSites,
+                                      AbstractAttribute &AA) {
   // 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()) {
+    Instruction *I = cast<Instruction>(U.getUser());
+    Function *AnchorValue = I->getParent()->getParent();
+
+    auto *LivenessAA = getAAFor<AAIsDead>(AA, *AnchorValue);
+
+    // Skip dead calls.
+    if (LivenessAA && LivenessAA->isAssumedDead(I))
+      continue;
 
     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");

llvm/trunk/test/Transforms/FunctionAttrs/arg_returned.ll

 
 attributes #0 = { noinline nounwind uwtable }
 
 ; BOTH-NOT: attributes #
 ; BOTH-DAG: attributes #{{[0-9]*}} = { nofree noinline norecurse nosync nounwind readnone uwtable willreturn }
 ; BOTH-DAG: attributes #{{[0-9]*}} = { nofree noinline nosync nounwind readnone uwtable }
 ; BOTH-DAG: attributes #{{[0-9]*}} = { nofree noinline nosync nounwind readonly uwtable }
 ; BOTH-DAG: attributes #{{[0-9]*}} = { noinline nounwind uwtable }
+; BOTH-DAG: attributes #{{[0-9]*}} = { nofree noinline nosync nounwind readnone uwtable willreturn }
+; BOTH-DAG: attributes #{{[0-9]*}} = { nofree noinline nosync nounwind uwtable willreturn }
 ; BOTH-NOT: attributes #

llvm/trunk/test/Transforms/FunctionAttrs/liveness.ll

 ; RUN: opt -attributor --attributor-disable=false -S < %s | FileCheck %s
 
-declare void @no_return_call() noreturn
+declare void @no_return_call() nofree noreturn nounwind readnone
 
-declare void @normal_call()
+declare void @normal_call() readnone
 
 declare i32 @foo()
 
 declare i32 @foo_noreturn() noreturn
 
-declare i32 @bar()
+declare i32 @bar() nosync readnone
 
-; TEST 1: cond.true is dead, but cond.end is not, since cond.false is live
+; CHECK: Function Attrs: nofree norecurse nounwind uwtable willreturn
+define i32 @volatile_load(i32*) norecurse nounwind uwtable {
+  %2 = load volatile i32, i32* %0, align 4
+  ret i32 %2
+}
+
+; CHECK: Function Attrs: nofree norecurse nosync nounwind uwtable willreturn
+; CHECK-NEXT: define internal i32 @internal_load(i32* nonnull)
+define internal i32 @internal_load(i32*) norecurse nounwind uwtable {
+  %2 = load i32, i32* %0, align 4
+  ret i32 %2
+}
+; TEST 1: Only first block is live.
+
+; CHECK: Function Attrs: nofree nosync nounwind
+; CHECK-NEXT: define i32 @first_block_no_return(i32 %a, i32* nonnull %ptr1, i32* %ptr2)
+define i32 @first_block_no_return(i32 %a, i32* nonnull %ptr1, i32* %ptr2) #0 {
+entry:
+  call i32 @internal_load(i32* %ptr1)
+  ; CHECK: call i32 @internal_load(i32* nonnull %ptr1)
+  call void @no_return_call()
+  ; CHECK: call void @no_return_call()
+  ; CHECK-NEXT: unreachable
+  %cmp = icmp eq i32 %a, 0
+  br i1 %cmp, label %cond.true, label %cond.false
+
+cond.true:                                        ; preds = %entry
+  call i32 @internal_load(i32* %ptr2)
+  ; CHECK: call i32 @internal_load(i32* %ptr2)
+  %load = call i32 @volatile_load(i32* %ptr1)
+  call void @normal_call()
+  %call = call i32 @foo()
+  br label %cond.end
+
+cond.false:                                       ; preds = %entry
+  call void @normal_call()
+  %call1 = call i32 @bar()
+  br label %cond.end
+
+cond.end:                                         ; preds = %cond.false, %cond.true
+  %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ]
+  ret i32 %cond
+}
+
+; TEST 2: cond.true is dead, but cond.end is not, since cond.false is live
 
 ; This is just an example. For example we can put a sync call in a
 ; dead block and check if it is deduced.
 
-define i32 @dead_block_present(i32 %a) #0 {
+; CHECK: Function Attrs: nosync
+; CHECK-NEXT: define i32 @dead_block_present(i32 %a, i32* %ptr1)
+define i32 @dead_block_present(i32 %a, i32* %ptr1) #0 {
 entry:
   %cmp = icmp eq i32 %a, 0
   br i1 %cmp, label %cond.true, label %cond.false
 
 cond.true:                                        ; preds = %entry
   call void @no_return_call()
   ; CHECK: call void @no_return_call()
   ; CHECK-NEXT: unreachable
-  %call = call i32 @foo()
+  %call = call i32 @volatile_load(i32* %ptr1)
   br label %cond.end
 
 cond.false:                                       ; preds = %entry
   call void @normal_call()
   %call1 = call i32 @bar()
   br label %cond.end
 
 cond.end:                                         ; preds = %cond.false, %cond.true
   %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ]
   ret i32 %cond
 }
 
-; TEST 2: both cond.true and cond.false are dead, therfore cond.end is dead as well.
+; TEST 3: both cond.true and cond.false are dead, therfore cond.end is dead as well.
 
 define i32 @all_dead(i32 %a) #0 {
 entry:
   %cmp = icmp eq i32 %a, 0
   br i1 %cmp, label %cond.true, label %cond.false
 
 cond.true:                                        ; preds = %entry
   call void @no_return_call()

 
 cond.end:                                         ; preds = %cond.false, %cond.true
   %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ]
   ret i32 %cond
 }
 
 declare i32 @__gxx_personality_v0(...)
 
-; TEST 3: All blocks are live.
+; TEST 4: All blocks are live.
 
 ; CHECK: define i32 @all_live(i32 %a)
 define i32 @all_live(i32 %a) #0 {
 entry:
   %cmp = icmp eq i32 %a, 0
   br i1 %cmp, label %cond.true, label %cond.false
 
 cond.true:                                        ; preds = %entry
   call void @normal_call()
   %call = call i32 @foo_noreturn()
   br label %cond.end
 
 cond.false:                                       ; preds = %entry
   call void @normal_call()
   %call1 = call i32 @bar()
   br label %cond.end
 
 cond.end:                                         ; preds = %cond.false, %cond.true
   %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ]
   ret i32 %cond
 }
 
-; TEST 4 noreturn invoke instruction replaced by a call and an unreachable instruction
+; TEST 5 noreturn invoke instruction replaced by a call and an unreachable instruction
 ; put after it.
 
 ; CHECK: define i32 @invoke_noreturn(i32 %a)
 define i32 @invoke_noreturn(i32 %a) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
 entry:
   %cmp = icmp eq i32 %a, 0
   br i1 %cmp, label %cond.true, label %cond.false
 
continue:
   br label %cond.end
 
 cleanup:
   %res = landingpad { i8*, i32 }
   catch i8* null
   ret i32 0
 }
 
-; TEST 5: Undefined behvior, taken from LangRef.
+; TEST 6: Undefined behvior, taken from LangRef.
 ; FIXME: Should be able to detect undefined behavior.
 
 ; CHECK define @ub(i32)
 define void @ub(i32* ) {
   %poison = sub nuw i32 0, 1           ; Results in a poison value.
   %still_poison = and i32 %poison, 0   ; 0, but also poison.
   %poison_yet_again = getelementptr i32, i32* %0, i32 %still_poison
   store i32 0, i32* %poison_yet_again  ; Undefined behavior due to store to poison.
   ret void
 }
 
 define void @inf_loop() #0 {
 entry:
   br label %while.body
 
 while.body:                                       ; preds = %entry, %while.body
   br label %while.body
 }
 
-; TEST 6: Infinite loop.
+; TEST 7: Infinite loop.
 ; FIXME: Detect infloops, and mark affected blocks dead.
 
 define i32 @test5(i32, i32) #0 {
   %3 = icmp sgt i32 %0, %1
   br i1 %3, label %cond.if, label %cond.elseif
 
 cond.if:                                                ; preds = %2
   %4 = tail call i32 @bar()

 }
 
 define void @rec() #0 {
 entry:
   call void @rec()
   ret void
 }
 
-; TEST 7: Recursion
+; TEST 8: Recursion
 ; FIXME: everything after first block should be marked dead
 ; and unreachable should be put after call to @rec().
 
 define i32 @test6(i32, i32) #0 {
   call void @rec()
   %3 = icmp sgt i32 %0, %1
   br i1 %3, label %cond.if, label %cond.elseif
 

 cond.else:                                                ; preds = %cond.elseif
   %6 = tail call i32 @foo()
   br label %cond.end
 
 cond.end:                                               ; preds = %cond.if, %cond.else, %cond.elseif
   %7 = phi i32 [ %1, %cond.elseif ], [ 0, %cond.else ], [ 0, %cond.if ]
   ret i32 %7
 }
-; TEST 8: Recursion
+; TEST 9: Recursion
 ; FIXME: contains recursive call to itself in cond.elseif block
 
 define i32 @test7(i32, i32) #0 {
   %3 = icmp sgt i32 %0, %1
   br i1 %3, label %cond.if, label %cond.elseif
 
 cond.if:                                                ; preds = %2
   %4 = tail call i32 @bar()
   br label %cond.end
 
 cond.elseif:                                                ; preds = %2
   %5 = tail call i32 @test7(i32 %0, i32 %1)
   %6 = icmp slt i32 %0, %1
   br i1 %6, label %cond.end, label %cond.else
 
 cond.else:                                                ; preds = %cond.elseif
   %7 = tail call i32 @foo()
   br label %cond.end
 
 cond.end:                                               ; preds = %cond.if, %cond.else, %cond.elseif
   %8 = phi i32 [ %1, %cond.elseif ], [ 0, %cond.else ], [ 0, %cond.if ]
   ret i32 %8
 }
-
-; TEST 9: Only first block is live.
-
-define i32 @first_block_no_return(i32 %a) #0 {
-entry:
-  call void @no_return_call()
-  ; CHECK: call void @no_return_call()
-  ; CHECK-NEXT: unreachable
-  %cmp = icmp eq i32 %a, 0
-  br i1 %cmp, label %cond.true, label %cond.false
-
-cond.true:                                        ; preds = %entry
-  call void @normal_call()
-  %call = call i32 @foo()
-  br label %cond.end
-
-cond.false:                                       ; preds = %entry
-  call void @normal_call()
-  %call1 = call i32 @bar()
-  br label %cond.end
-
-cond.end:                                         ; preds = %cond.false, %cond.true
-  %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ]
-  ret i32 %cond
-}

llvm/trunk/test/Transforms/FunctionAttrs/willreturn.ll

 f:
   ret i32 0
 }
 
 ; TEST 15 (positive & negative case)
 ; unreachable exit
 
 ; 15.1 (positive case)
-; FIXME: missing willreturn
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NEXT: define void @unreachable_exit_positive1()
-; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable willreturn
 ; ATTRIBUTOR-NEXT: define void @unreachable_exit_positive1()
 define void @unreachable_exit_positive1() #0 {
   tail call void @will_return()
   ret void
 
 unreachable_label:
   tail call void @exit(i32 0)
   unreachable
 }
 
 ; FIXME: missing willreturn
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NEXT: define i32 @unreachable_exit_positive2(i32)
-; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable
 ; ATTRIBUTOR-NEXT: define i32 @unreachable_exit_positive2(i32)
 define i32 @unreachable_exit_positive2(i32) local_unnamed_addr #0 {
   %2 = icmp slt i32 %0, 1
   br i1 %2, label %3, label %5
 
 ; <label>:3:                                      ; preds = %5, %1
   %4 = phi i32 [ 1, %1 ], [ %8, %5 ]
   ret i32 %4

 unreachable_label:
   tail call void @exit(i32 0)
   unreachable
 }
 
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NOT: willreturn
 ; FNATTR-NEXT: define void @unreachable_exit_negative2()
-; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable
 ; ATTRIBUTOR-NOT: willreturn
 ; ATTRIBUTOR-NEXT: define void @unreachable_exit_negative2()
 define void @unreachable_exit_negative2() #0 {
 
   br label %L1
 L1:
   br label %L2
 L2: