[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

SmallPtrSetImpl<ReturnInst *> &

llvm/lib/Transforms/IPO/Attributor.cpp

640

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.

665

& missing

708

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

583

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

593

return true;

746

I'll commit these changes as a fix today.

1229

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

1583

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

1607

return getKnown() && isAssumedDead(I)

to reduce duplication of logic.

1665

// At least one new instruction encountered.

llvm/test/Transforms/FunctionAttrs/arg_returned.ll

751

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

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

llvm/lib/Transforms/IPO/Attributor.cpp

630

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

703

Test for nullptr.

966

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

1242

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

1715

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

1719

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

llvm/test/Transforms/FunctionAttrs/liveness.ll

74

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

1242

Please pass this as a reference not pointer.

1721

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.

llvm/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;
+  }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H

llvm/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;
 
     // For now, any call site we see will prevent us from directly fixing the
     // state. However, if the information on the callees is fixed, the call
     // sites will be removed and we will fix the information for this state.
     HasCallSite = true;
 
     // Try to find a assumed unique return value for the called function.
     auto *RetCSAA = A.getAAFor<AAReturnedValuesImpl>(*this, *RV);
     if (!RetCSAA) {
       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;
 
     // If multiple, non-refinable values were found, there cannot be a unique
     // return value for the called function. The returned call is overdefined!
     if (!AssumedUniqueRV.getValue()) {
       HasOverdefinedReturnedCalls = true;
       LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site has multiple "
                            "potentially returned values\n");
       continue;
     }
 
     LLVM_DEBUG({
       bool UniqueRVIsKnown = RetCSAA->isAtFixpoint();
       dbgs() << "[AAReturnedValues] Returned call site "
              << (UniqueRVIsKnown ? "known" : "assumed")
for (auto &It : ReturnedValues) {
     if (Argument *AssumedRetArg = dyn_cast<Argument>(AssumedRetVal))
       collectValuesRecursively(A,
                                RetCS.getArgOperand(AssumedRetArg->getArgNo()),
                                ReturnInsts, AddRVs);
     else
       AddRVs[AssumedRetVal].insert(ReturnInsts.begin(), ReturnInsts.end());
   }
 
-  // Keep track of any change to trigger updates on dependent attributes.
-  ChangeStatus Changed = ChangeStatus::UNCHANGED;
-
   for (auto &It : AddRVs) {
     assert(!It.second.empty() && "Entry does not add anything.");
     auto &ReturnInsts = ReturnedValues[It.first];
     for (ReturnInst *RI : It.second)
       if (ReturnInsts.insert(RI).second) {
         LLVM_DEBUG(dbgs() << "[AAReturnedValues] Add new returned value "
                           << *It.first << " => " << *RI << "\n");
         Changed = ChangeStatus::CHANGED;
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.

 };
 
 ChangeStatus AANoFreeFunction::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);
       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.
struct AANonNullCallSiteArgument : AANonNullImpl {
   };
 
   // Return argument index of associated value.
   int getArgNo() const { return ArgNo; }
 
 private:
   unsigned ArgNo;
 };
+
 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!");
 
     auto *NonNullAA = A.getAAFor<AANonNull>(*this, *CS.getInstruction(), ArgNo);
 
     // Check that NonNullAA is AANonNullCallSiteArgument.
     if (NonNullAA) {
       ImmutableCallSite ICS(&NonNullAA->getAnchoredValue());
       if (ICS && CS.getInstruction() == ICS.getInstruction())
         return NonNullAA->isAssumedNonNull();
       return false;
     }
 
     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 *BB).
   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 *BB).
   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);
 
       if (NoReturnAA && NoReturnAA->isAssumedNoReturn()) {
         if (!NoReturnCalls.insert(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: "
+                    << " Total number of blocks: "
                     << getAnchorScope().size() << "\n");
 
   return Status;
 }
 
 /// ----------------------------------------------------------------------------
 ///                               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()) {
 
     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;
     }
 
+    Function *AnchorValue = CS->getFunction();
+    auto *LivenessAA = getAAFor<AAIsDead>(*AA, *AnchorValue);
+
+    // Skip dead calls.
+    if (LivenessAA && LivenessAA->isAssumedDead(CS.getInstruction()))
+        continue;
+
     if (Pred(CS))
       continue;
 
     LLVM_DEBUG(dbgs() << "Attributor: Call site callback failed for "
                       << *CS.getInstruction() << "\n");
     return false;
   }
 

llvm/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/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/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: