[Attributor] Liveness for values

[jdoerfert]

Summary

This patch introduces liveness (AAIsDead) for all positions, thus for
all kinds of values. For now, we say an instruction is dead if it would
be removed assuming all users are dead. A call site return is different
as we just look at the users. If all call site returns have been
eliminated, the return values can return undef instead of their original
value, eliminating uses.

We try to recursively delete dead instructions now and we introduce a
simple check-like interface for use-traversal.

More explicit tests will be added.

This is the idea tried out in D68626 but implemented in the right way.

[jdoerfert]

Non-exact functions fix + more tests

[jdoerfert]

Minor updates and fixes

[sstefan1]

Some comments

llvm/lib/Transforms/IPO/Attributor.cpp

2174

nit: isAssumedDead()

3544

Should this still be here, considering changes from D68934?

4411

Can we have a value parameter here that maybe defaults to nullptr. In the default case we take AssociatedValue and in others the value parameter? Maybe this is not the best solution, but for example, h2s doesn't work with AssociatedValue.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

3544

I think D68934 replaces all this, I will undo this change here.

4411

Sure, we don't even need a default. Though we can also do this after the patch. I'll change the interface now here though.

[sstefan1]

LGTM then!

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

struct Attributor {
   /// \p F.
   void markLiveInternalFunction(const Function &F) {
     assert(F.hasLocalLinkage() &&
            "Only local linkage is assumed dead initially.");
 
     identifyDefaultAbstractAttributes(const_cast<Function &>(F));
   }
 
-  /// Record that \p I is deleted after information was manifested.
+  /// Record that \p U is to be replaces with undef after information was
+  /// manifested. This also triggers deletion of trivially dead istructions.
+  void makeUndefAfterManifest(Use &U) { ToBeMadeUndef.insert(&U); }
+
+  /// Record that \p I is deleted after information was manifested. This also
+  /// triggers deletion of trivially dead istructions.
   void deleteAfterManifest(Instruction &I) { ToBeDeletedInsts.insert(&I); }
 
-  /// Record that \p BB is deleted after information was manifested.
+  /// Record that \p BB is deleted after information was manifested. This also
+  /// triggers deletion of trivially dead istructions.
   void deleteAfterManifest(BasicBlock &BB) { ToBeDeletedBlocks.insert(&BB); }
 
   /// Record that \p F is deleted after information was manifested.
   void deleteAfterManifest(Function &F) { ToBeDeletedFunctions.insert(&F); }
 
   /// Return true if \p AA (or its context instruction) is assumed dead.
   ///
   /// If \p LivenessAA is not provided it is queried.
   bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA);
 
+  /// Check \p Pred on all (transitive) uses of the associated value.
+  ///
+  /// This method will evaluate \p Pred on all (transitive) uses of the
+  /// associated value and return true if \p Pred holds every time.
+  bool checkForAllUses(const function_ref<bool(const Use &, bool &)> &Pred,
+                       const AbstractAttribute &QueryingAA);
+
   /// 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(const function_ref<bool(AbstractCallSite)> &Pred,
                             const AbstractAttribute &QueryingAA,
                             bool RequireAllCallSites);
private:
   const unsigned DepRecomputeInterval;
 
   /// If not null, a set limiting the attribute opportunities.
   const DenseSet<const char *> *Whitelist;
 
   /// A set to remember the functions we already assume to be live and visited.
   DenseSet<const Function *> VisitedFunctions;
 
+  /// Uses we replace with undef after manifest is done. We will remove
+  /// trivially dead instructions as well.
+  SmallPtrSet<Use *, 8> ToBeMadeUndef;
+
   /// Functions, blocks, and instructions we delete after manifest is done.
   ///
   ///{
   SmallPtrSet<Function *, 8> ToBeDeletedFunctions;
   SmallPtrSet<BasicBlock *, 8> ToBeDeletedBlocks;
   SmallPtrSet<Instruction *, 8> ToBeDeletedInsts;
   ///}
 };
struct AANoReturn
   static const char ID;
 };
 
 /// An abstract interface for liveness abstract attribute.
 struct AAIsDead : public StateWrapper<BooleanState, AbstractAttribute>,
                   public IRPosition {
   AAIsDead(const IRPosition &IRP) : IRPosition(IRP) {}
 
+  /// Returns true if the underlying value is assumed dead.
+  virtual bool isAssumedDead() const = 0;
+
   /// Returns true if \p BB is assumed dead.
   virtual bool isAssumedDead(const BasicBlock *BB) const = 0;
 
   /// Returns true if \p BB is known dead.
   virtual bool isKnownDead(const BasicBlock *BB) const = 0;
 
   /// Returns true if \p I is assumed dead.
   virtual bool isAssumedDead(const Instruction *I) const = 0;

llvm/lib/Transforms/IPO/Attributor.cpp

struct AANoAliasCallSiteReturned final : AANoAliasImpl {
   }
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(noalias); }
 };
 
 /// -------------------AAIsDead Function Attribute-----------------------
 
-struct AAIsDeadImpl : public AAIsDead {
-  AAIsDeadImpl(const IRPosition &IRP) : AAIsDead(IRP) {}
+struct AAIsDeadValueImpl : public AAIsDead {
+  AAIsDeadValueImpl(const IRPosition &IRP) : AAIsDead(IRP) {}
 
+  /// See AAIsDead::isAssumedDead().
+  bool isAssumedDead() const override { return getAssumed(); }
+
+  /// See AAIsDead::isAssumedDead(BasicBlock *).
+  bool isAssumedDead(const BasicBlock *BB) const override { return false; }
+
+  /// See AAIsDead::isKnownDead(BasicBlock *).
+  bool isKnownDead(const BasicBlock *BB) const override { return false; }
+
+  /// See AAIsDead::isAssumed(Instruction *I).
+  bool isAssumedDead(const Instruction *I) const override { return false; }
+
+  /// See AAIsDead::isKnownDead(Instruction *I).
+  bool isKnownDead(const Instruction *I) const override { return false; }
+
+  /// See AbstractAttribute::getAsStr().
+  const std::string getAsStr() const override {
+    return isAssumedDead() ? "assumed-dead" : "assumed-live";
+  }
+};
+
+struct AAIsDeadFloating : public AAIsDeadValueImpl {
+  AAIsDeadFloating(const IRPosition &IRP) : AAIsDeadValueImpl(IRP) {}
+
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {
+    if (Instruction *I = dyn_cast<Instruction>(&getAssociatedValue()))
+      if (!wouldInstructionBeTriviallyDead(I))
+        indicatePessimisticFixpoint();
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    auto UsePred = [&](const Use &U, bool &Follow) {
+      Instruction *UserI = cast<Instruction>(U.getUser());
+      if (CallSite CS = CallSite(UserI)) {
+        const IRPosition &CSArgPos =
+            IRPosition::callsite_argument(CS, CS.getArgumentNo(&U));
+        const auto &CSArgIsDead = A.getAAFor<AAIsDead>(*this, CSArgPos);
+        return CSArgIsDead.isAssumedDead();
+      }
+      if (ReturnInst *RI = dyn_cast<ReturnInst>(UserI)) {
+        const IRPosition &RetPos = IRPosition::returned(*RI->getFunction());
+        const auto &RetIsDeadAA = A.getAAFor<AAIsDead>(*this, RetPos);
+        return RetIsDeadAA.isAssumedDead();
+      }
+      Follow = true;
+      return wouldInstructionBeTriviallyDead(UserI);
+    };
+
+    if (!A.checkForAllUses(UsePred, *this))
+      return indicatePessimisticFixpoint();
+    return ChangeStatus::UNCHANGED;
+  }
+
+  /// See AbstractAttribute::manifest(...).
+  ChangeStatus manifest(Attributor &A) override {
+    Value &V = getAssociatedValue();
+    if (V.use_empty())
+      return ChangeStatus::UNCHANGED;
+
+    for (Use &U : V.uses())
+      A.makeUndefAfterManifest(U);
+    return ChangeStatus::CHANGED;
+  }
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECLTRACK_FLOATING_ATTR(IsDead)
+  }
+};
+
+struct AAIsDeadArgument : public AAIsDeadFloating {
+  AAIsDeadArgument(const IRPosition &IRP) : AAIsDeadFloating(IRP) {}
+
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {
+    if (!getAssociatedFunction()->hasExactDefinition())
+      indicatePessimisticFixpoint();
+  }
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(IsDead) }
+};
+
+struct AAIsDeadCallSiteArgument : public AAIsDeadValueImpl {
+  AAIsDeadCallSiteArgument(const IRPosition &IRP) : AAIsDeadValueImpl(IRP) {}
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    // TODO: Once we have call site specific value information we can provide
+    //       call site specific liveness information and then it makes
+    //       sense to specialize attributes for call sites arguments instead of
+    //       redirecting requests to the callee argument.
+    Argument *Arg = getAssociatedArgument();
+    if (!Arg)
+      return indicatePessimisticFixpoint();
+    const IRPosition &ArgPos = IRPosition::argument(*Arg);
+    auto &ArgAA = A.getAAFor<AAIsDead>(*this, ArgPos);
+    return clampStateAndIndicateChange(
+        getState(), static_cast<const AAIsDead::StateType &>(ArgAA.getState()));
+  }
+
+  /// See AbstractAttribute::manifest(...).
+  ChangeStatus manifest(Attributor &A) override {
+    CallBase &CB = cast<CallBase>(getAnchorValue());
+    A.makeUndefAfterManifest(CB.getArgOperandUse(getArgNo()));
+    return ChangeStatus::CHANGED;
+  }
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(IsDead) }
+};
+
+struct AAIsDeadReturned : public AAIsDeadValueImpl {
+  AAIsDeadReturned(const IRPosition &IRP) : AAIsDeadValueImpl(IRP) {}
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+
+    auto PredForCallSite = [&](AbstractCallSite ACS) {
+      if (ACS.isCallbackCall())
+        return false;
+      const IRPosition &CSRetPos =
+          IRPosition::callsite_returned(ACS.getCallSite());
+      const auto &RetIsDeadAA = A.getAAFor<AAIsDead>(*this, CSRetPos);
+      return RetIsDeadAA.isAssumedDead();
+    };
+
+    if (!A.checkForAllCallSites(PredForCallSite, *this, true))
+      return indicatePessimisticFixpoint();
+
+    return ChangeStatus::UNCHANGED;
+  }
+
+  /// See AbstractAttribute::manifest(...).
+  ChangeStatus manifest(Attributor &A) override {
+    // TODO: Rewrite the signature to return void?
+    bool AnyChange = false;
+    auto RetInstPred = [&](Instruction &I) {
+      ReturnInst &RI = cast<ReturnInst>(I);
+      if (!isa<UndefValue>(RI.getReturnValue())) {
+        AnyChange = true;
+        A.makeUndefAfterManifest(RI.getOperandUse(0));
+      }
+      return true;
+    };
+    A.checkForAllInstructions(RetInstPred, *this, {Instruction::Ret});
+    return AnyChange ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED;
+  }
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(IsDead) }
+};
+
+struct AAIsDeadCallSiteReturned : public AAIsDeadFloating {
+  AAIsDeadCallSiteReturned(const IRPosition &IRP) : AAIsDeadFloating(IRP) {}
+
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {}
+
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(IsDead) }
+};
+
+struct AAIsDeadFunction : public AAIsDead {
+  AAIsDeadFunction(const IRPosition &IRP) : AAIsDead(IRP) {}
+
+  /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     const Function *F = getAssociatedFunction();
     if (F && !F->isDeclaration())
       exploreFromEntry(A, F);
   }
 
   void exploreFromEntry(Attributor &A, const Function *F) {
     ToBeExploredPaths.insert(&(F->getEntryBlock().front()));
for (BasicBlock &BB : F)
         A.deleteAfterManifest(BB);
 
     return HasChanged;
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override;
 
+  /// See AbstractAttribute::trackStatistics()
+  void trackStatistics() const override {
+    STATS_DECL(PartiallyDeadBlocks, Function,
+               "Number of basic blocks classified as partially dead");
+    BUILD_STAT_NAME(PartiallyDeadBlocks, Function) += NoReturnCalls.size();
+  }
+
+  /// Returns true if the function is assumed dead.
+  bool isAssumedDead() const override { return false; }
+
   /// See AAIsDead::isAssumedDead(BasicBlock *).
   bool isAssumedDead(const BasicBlock *BB) const override {
     assert(BB->getParent() == getAssociatedFunction() &&
            "BB must be in the same anchor scope function.");
 
     if (!getAssumed())
       return false;
     return !AssumedLiveBlocks.count(BB);
struct AAIsDeadFunction : public AAIsDead {
 
   /// Collection of all assumed live BasicBlocks.
   DenseSet<const BasicBlock *> AssumedLiveBlocks;
 
   /// Collection of calls with noreturn attribute, assumed or knwon.
   SmallSetVector<const Instruction *, 4> NoReturnCalls;
 };
 
-struct AAIsDeadFunction final : public AAIsDeadImpl {
-  AAIsDeadFunction(const IRPosition &IRP) : AAIsDeadImpl(IRP) {}
-
-  /// See AbstractAttribute::trackStatistics()
-  void trackStatistics() const override {
-    STATS_DECL(PartiallyDeadBlocks, Function,
-               "Number of basic blocks classified as partially dead");
-    BUILD_STAT_NAME(PartiallyDeadBlocks, Function) += NoReturnCalls.size();
-  }
-};
-
-bool AAIsDeadImpl::isAfterNoReturn(const Instruction *I) const {
+bool AAIsDeadFunction::isAfterNoReturn(const Instruction *I) const {
   const Instruction *PrevI = I->getPrevNode();
   while (PrevI) {
     if (NoReturnCalls.count(PrevI))
       return true;
     PrevI = PrevI->getPrevNode();
   }
   return false;
 }
 
-const Instruction *AAIsDeadImpl::findNextNoReturn(Attributor &A,
+const Instruction *AAIsDeadFunction::findNextNoReturn(Attributor &A,
                                                       const Instruction *I) {
   const BasicBlock *BB = I->getParent();
   const Function &F = *BB->getParent();
 
   // Flag to determine if we can change an invoke to a call assuming the callee
   // is nounwind. This is not possible if the personality of the function allows
   // to catch asynchronous exceptions.
   bool Invoke2CallAllowed = !mayCatchAsynchronousExceptions(F);
 
for (const BasicBlock *SuccBB : successors(BB)) {
     assumeLive(A, *SuccBB);
     ToBeExploredPaths.insert(&SuccBB->front());
   }
 
   // No noreturn instruction found.
   return nullptr;
 }
 
-ChangeStatus AAIsDeadImpl::updateImpl(Attributor &A) {
+ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) {
   ChangeStatus Status = ChangeStatus::UNCHANGED;
 
   // Temporary collection to iterate over existing noreturn instructions. This
   // will alow easier modification of NoReturnCalls collection
   SmallVector<const Instruction *, 8> NoReturnChanged;
 
   for (const Instruction *I : NoReturnCalls)
     NoReturnChanged.push_back(I);
if (NoReturnCalls.empty() &&
     assert(!isValidState() && "Expected an invalid state!");
     Status = ChangeStatus::CHANGED;
   }
 
   return Status;
 }
 
 /// Liveness information for a call sites.
-struct AAIsDeadCallSite final : AAIsDeadImpl {
-  AAIsDeadCallSite(const IRPosition &IRP) : AAIsDeadImpl(IRP) {}
+struct AAIsDeadCallSite final : AAIsDeadFunction {
+  AAIsDeadCallSite(const IRPosition &IRP) : AAIsDeadFunction(IRP) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     // TODO: Once we have call site specific value information we can provide
     //       call site specific liveness information and then it makes
     //       sense to specialize attributes for call sites instead of
     //       redirecting requests to the callee.
     llvm_unreachable("Abstract attributes for liveness are not "
struct AAValueSimplifyImpl : AAValueSimplify {
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     ChangeStatus Changed = ChangeStatus::UNCHANGED;
 
     if (!SimplifiedAssociatedValue.hasValue() ||
         !SimplifiedAssociatedValue.getValue())
       return Changed;
+    Value &V = getAssociatedValue();
+    if (isa<Constant>(V))
+      return Changed;
 
     if (auto *C = dyn_cast<Constant>(SimplifiedAssociatedValue.getValue())) {
       // We can replace the AssociatedValue with the constant.
-      Value &V = getAssociatedValue();
       if (!V.user_empty() && &V != C && V.getType() == C->getType()) {
         LLVM_DEBUG(dbgs() << "[Attributor][ValueSimplify] " << V << " -> " << *C
                           << "\n");
         V.replaceAllUsesWith(C);
         Changed = ChangeStatus::CHANGED;
       }
     }
 
if (!LivenessAA->isAssumedDead(CtxI))
     return false;
 
   // We actually used liveness information so we have to record a dependence.
   recordDependence(*LivenessAA, AA);
 
   return true;
 }
 
+bool Attributor::checkForAllUses(
+    const function_ref<bool(const Use &, bool &)> &Pred,
+    const AbstractAttribute &QueryingAA) {
+  const IRPosition &IRP = QueryingAA.getIRPosition();
+  const Value &AssociatedValue = IRP.getAssociatedValue();
+  SmallVector<const Use *, 16> Worklist;
+  SmallPtrSet<const Use *, 16> Visited;
+
+  for (const Use &U : AssociatedValue.uses())
+    Worklist.push_back(&U);
+
+  LLVM_DEBUG(dbgs() << "[Attributor] Got " << Worklist.size()
+                    << " initial uses to check\n");
+
+  if (Worklist.empty())
+    return true;
+
+  bool AnyDead = false;
+  const Function *ScopeFn = IRP.getAnchorScope();
+  const auto *LivenessAA =
+      ScopeFn ? &getAAFor<AAIsDead>(QueryingAA, IRPosition::function(*ScopeFn),
+                                    /* TrackDependence */ false)
+              : nullptr;
+
+  while (!Worklist.empty()) {
+    const Use *U = Worklist.pop_back_val();
+    if (!Visited.insert(U).second)
+      continue;
+    LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << *U << "\n");
+    if (Instruction *UserI = dyn_cast<Instruction>(U->getUser()))
+      if (LivenessAA && LivenessAA->isAssumedDead(UserI)) {
+        AnyDead = true;
+        continue;
+      }
+
+    bool Follow = false;
+    if (!Pred(*U, Follow))
+      return false;
+    if (!Follow)
+      continue;
+    for (const Use &UU : U->getUser()->uses())
+      Worklist.push_back(&UU);
+  }
+
+  if (AnyDead)
+    recordDependence(*LivenessAA, QueryingAA);
+
+  return true;
+}
+
 bool Attributor::checkForAllCallSites(
     const function_ref<bool(AbstractCallSite)> &Pred,
     const AbstractAttribute &QueryingAA, 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.
   const IRPosition &IRP = QueryingAA.getIRPosition();
   const Function *AssociatedFunction = IRP.getAssociatedFunction();
assert(
       NumFinalAAs == AllAbstractAttributes.size() &&
       "Expected the final number of abstract attributes to remain unchanged!");
 
   // Delete stuff at the end to avoid invalid references and a nice order.
   {
     LLVM_DEBUG(dbgs() << "\n[Attributor] Delete at least "
                       << ToBeDeletedFunctions.size() << " functions and "
                       << ToBeDeletedBlocks.size() << " blocks and "
-                      << ToBeDeletedInsts.size() << " instructions\n");
+                      << ToBeDeletedInsts.size() << " instructions and "
+                      << ToBeMadeUndef.size() << " uses\n");
+
+    SmallVector<Instruction *, 32> DeadInsts;
     for (Instruction *I : ToBeDeletedInsts) {
-      if (!I->use_empty())
-        I->replaceAllUsesWith(UndefValue::get(I->getType()));
+      if (isInstructionTriviallyDead(I))
+        DeadInsts.push_back(I);
+      else
         I->eraseFromParent();
     }
+    RecursivelyDeleteTriviallyDeadInstructions(DeadInsts);
+
+    for (Use *U : ToBeMadeUndef) {
+      Value *V = U->get();
+      UndefValue *UV = UndefValue::get(V->getType());
+      U->set(UV);
+      if (Instruction *I = dyn_cast<Instruction>(V))
+        if (isInstructionTriviallyDead(I))
+          ToBeDeletedInsts.insert(I);
+    }
 
     if (unsigned NumDeadBlocks = ToBeDeletedBlocks.size()) {
       SmallVector<BasicBlock *, 8> ToBeDeletedBBs;
       ToBeDeletedBBs.reserve(NumDeadBlocks);
       ToBeDeletedBBs.append(ToBeDeletedBlocks.begin(), ToBeDeletedBlocks.end());
       DeleteDeadBlocks(ToBeDeletedBBs);
       STATS_DECLTRACK(AAIsDead, BasicBlock,
                       "Number of dead basic blocks deleted.");
void Attributor::identifyDefaultAbstractAttributes(Function &F) {
   Type *ReturnType = F.getReturnType();
   if (!ReturnType->isVoidTy()) {
     // Argument attribute "returned" --- Create only one per function even
     // though it is an argument attribute.
     getOrCreateAAFor<AAReturnedValues>(FPos);
 
     IRPosition RetPos = IRPosition::returned(F);
 
+    // Every returned value might be dead.
+    getOrCreateAAFor<AAIsDead>(RetPos);
+
     // Every function might be simplified.
     getOrCreateAAFor<AAValueSimplify>(RetPos);
 
     if (ReturnType->isPointerTy()) {
 
       // Every function with pointer return type might be marked align.
       getOrCreateAAFor<AAAlign>(RetPos);
 
if (Arg.getType()->isPointerTy()) {
       // Every argument with pointer type might be marked
       // "readnone/readonly/writeonly/..."
       getOrCreateAAFor<AAMemoryBehavior>(ArgPos);
     }
   }
 
   auto CallSitePred = [&](Instruction &I) -> bool {
     CallSite CS(&I);
-    if (CS.getCalledFunction()) {
-      for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) {
+    if (Function *Callee = CS.getCalledFunction()) {
+      if (!Callee->getReturnType()->isVoidTy()) {
+        IRPosition CSRetPos = IRPosition::callsite_returned(CS);
+
+        // Call site return values might be dead.
+        getOrCreateAAFor<AAIsDead>(CSRetPos);
+      }
+
+      for (int i = 0, e = Callee->arg_size(); i < e; i++) {
 
         IRPosition CSArgPos = IRPosition::callsite_argument(CS, i);
 
+        // Every call site argument might be dead.
+        getOrCreateAAFor<AAIsDead>(CSArgPos);
+
         // Call site argument might be simplified.
         getOrCreateAAFor<AAValueSimplify>(CSArgPos);
 
         if (!CS.getArgument(i)->getType()->isPointerTy())
           continue;
 
         // Call site argument attribute "non-null".
         getOrCreateAAFor<AANonNull>(CSArgPos);
#define CREATE_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION(CLASS)                  \
   }
 
 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoUnwind)
 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoSync)
 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoFree)
 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoRecurse)
 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAWillReturn)
 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoReturn)
-CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead)
 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReturnedValues)
 
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANonNull)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoAlias)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AADereferenceable)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAAlign)
 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoCapture)
 
 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueSimplify)
+CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead)
 
 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAHeapToStack)
 
 CREATE_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAMemoryBehavior)
 
 #undef CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef CREATE_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION

llvm/test/Transforms/FunctionAttrs/align.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=6 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Test cases specifically designed for "align" attribute.
 ; We use FIXME's to indicate problems and missing attributes.
 
 

 ;     return a?&a1: f1(&a2);
 ; }
 
 @a1 = common global i8 0, align 8
 @a2 = common global i8 0, align 16
 
 ; Function Attrs: nounwind readnone ssp uwtable
 define internal i8* @f1(i8* readnone %0) local_unnamed_addr #0 {
-; ATTRIBUTOR: define internal nonnull align 8 dereferenceable(1) i8* @f1(i8* nonnull readnone align 8 dereferenceable(1) "no-capture-maybe-returned" %0)
+; ATTRIBUTOR-LABEL: define {{[^@]+}}@f1
+; ATTRIBUTOR-SAME: (i8* nonnull readnone align 8 dereferenceable(1) "no-capture-maybe-returned" [[TMP0:%.*]]) local_unnamed_addr
+; ATTRIBUTOR-NEXT:    [[TMP2:%.*]] = icmp eq i8* [[TMP0]], null
+; ATTRIBUTOR-NEXT:    br i1 [[TMP2]], label [[TMP3:%.*]], label [[TMP5:%.*]]
+; ATTRIBUTOR:       3:
+; ATTRIBUTOR-NEXT:    [[TMP4:%.*]] = tail call align 8 i8* @f2(i8* nonnull align 8 dereferenceable(1) @a1)
+; ATTRIBUTOR-NEXT:    [[L:%.*]] = load i8, i8* undef, align 8
+; ATTRIBUTOR-NEXT:    br label [[TMP5]]
+; ATTRIBUTOR:       5:
+; ATTRIBUTOR-NEXT:    [[TMP6:%.*]] = phi i8* [ undef, [[TMP3]] ], [ [[TMP0]], [[TMP1:%.*]] ]
+; ATTRIBUTOR-NEXT:    ret i8* undef
+;
   %2 = icmp eq i8* %0, null
   br i1 %2, label %3, label %5
 
 ; <label>:3:                                      ; preds = %1
-; ATTRIBUTOR: %4 = tail call align 8 i8* @f2(i8* nonnull align 8 dereferenceable(1) @a1)
   %4 = tail call i8* @f2(i8* nonnull @a1)
-; ATTRIBUTOR: %l = load i8, i8* %4, align 8
   %l = load i8, i8* %4
   br label %5
 
 ; <label>:5:                                      ; preds = %1, %3
   %6 = phi i8* [ %4, %3 ], [ %0, %1 ]
   ret i8* %6
 }
 
 ; Function Attrs: nounwind readnone ssp uwtable
 define internal i8* @f2(i8* readnone %0) local_unnamed_addr #0 {
-; ATTRIBUTOR: define internal nonnull align 8 dereferenceable(1) i8* @f2(i8* nonnull readnone align 8 dereferenceable(1) "no-capture-maybe-returned" %0)
+; ATTRIBUTOR-LABEL: define {{[^@]+}}@f2
+; ATTRIBUTOR-SAME: (i8* nonnull readnone align 8 dereferenceable(1) "no-capture-maybe-returned" [[TMP0:%.*]]) local_unnamed_addr
+; ATTRIBUTOR-NEXT:    [[TMP2:%.*]] = icmp eq i8* @a1, null
+; ATTRIBUTOR-NEXT:    br i1 [[TMP2]], label [[TMP5:%.*]], label [[TMP3:%.*]]
+; ATTRIBUTOR:       3:
+; ATTRIBUTOR-NEXT:    [[TMP4:%.*]] = tail call i8* @f1(i8* nonnull align 8 dereferenceable(1) "no-capture-maybe-returned" @a1)
+; ATTRIBUTOR-NEXT:    br label [[TMP7:%.*]]
+; ATTRIBUTOR:       5:
+; ATTRIBUTOR-NEXT:    [[TMP6:%.*]] = tail call i8* @f3(i8* nonnull align 16 dereferenceable(1) @a2)
+; ATTRIBUTOR-NEXT:    br label [[TMP7]]
+; ATTRIBUTOR:       7:
+; ATTRIBUTOR-NEXT:    [[TMP8:%.*]] = phi i8* [ undef, [[TMP3]] ], [ undef, [[TMP5]] ]
+; ATTRIBUTOR-NEXT:    ret i8* undef
+;
   %2 = icmp eq i8* %0, null
   br i1 %2, label %5, label %3
 
 ; <label>:3:                                      ; preds = %1
 
-; ATTRIBUTOR: %4 = tail call i8* @f1(i8* nonnull align 8 dereferenceable(1) "no-capture-maybe-returned" @a1)
   %4 = tail call i8* @f1(i8* nonnull %0)
   br label %7
 
 ; <label>:5:                                      ; preds = %1
-; ATTRIBUTOR: %6 = tail call i8* @f3(i8* nonnull align 16 dereferenceable(1) @a2)
   %6 = tail call i8* @f3(i8* nonnull @a2)
   br label %7
 
 ; <label>:7:                                      ; preds = %5, %3
   %8 = phi i8* [ %4, %3 ], [ %6, %5 ]
   ret i8* %8
 }
 
 ; Function Attrs: nounwind readnone ssp uwtable
 define internal i8* @f3(i8* readnone %0) local_unnamed_addr #0 {
-; ATTRIBUTOR: define internal nonnull align 8 dereferenceable(1) i8* @f3(i8* nocapture nonnull readnone align 16 dereferenceable(1) %0)
+; ATTRIBUTOR-LABEL: define {{[^@]+}}@f3
+; ATTRIBUTOR-SAME: (i8* nocapture nonnull readnone align 16 dereferenceable(1) [[TMP0:%.*]]) local_unnamed_addr
+; ATTRIBUTOR-NEXT:    [[TMP2:%.*]] = icmp eq i8* @a2, null
+; ATTRIBUTOR-NEXT:    br i1 [[TMP2]], label [[TMP3:%.*]], label [[TMP5:%.*]]
+; ATTRIBUTOR:       3:
+; ATTRIBUTOR-NEXT:    [[TMP4:%.*]] = tail call i8* @f1(i8* nonnull align 16 dereferenceable(1) @a2)
+; ATTRIBUTOR-NEXT:    br label [[TMP5]]
+; ATTRIBUTOR:       5:
+; ATTRIBUTOR-NEXT:    [[TMP6:%.*]] = phi i8* [ undef, [[TMP3]] ], [ @a1, [[TMP1:%.*]] ]
+; ATTRIBUTOR-NEXT:    ret i8* undef
+;
   %2 = icmp eq i8* %0, null
   br i1 %2, label %3, label %5
 
 ; <label>:3:                                      ; preds = %1
-; ATTRIBUTOR: %4 = tail call i8* @f1(i8* nonnull align 16 dereferenceable(1) @a2)
   %4 = tail call i8* @f1(i8* nonnull @a2)
   br label %5
 
 ; <label>:5:                                      ; preds = %1, %3
   %6 = phi i8* [ %4, %3 ], [ @a1, %1 ]
   ret i8* %6
 }
 
 ; TEST 7
 ; Better than IR information
 ; ATTRIBUTOR: define align 32 i32* @test7(i32* readnone returned align 32 "no-capture-maybe-returned" %p)
 define align 4 i32* @test7(i32* align 32 %p) #0 {
   tail call i8* @f1(i8* align 8 dereferenceable(1) @a1)
   ret i32* %p
 }
 
+; TEST 7b
+; Function Attrs: nounwind readnone ssp uwtable
+define internal i8* @f1b(i8* readnone %0) local_unnamed_addr #0 {
+;
+; ATTRIBUTOR-LABEL: define {{[^@]+}}@f1b
+; ATTRIBUTOR-SAME: (i8* nonnull readnone align 8 dereferenceable(1) "no-capture-maybe-returned" [[TMP0:%.*]]) local_unnamed_addr
+; ATTRIBUTOR-NEXT:    [[TMP2:%.*]] = icmp eq i8* [[TMP0]], null
+; ATTRIBUTOR-NEXT:    br i1 [[TMP2]], label [[TMP3:%.*]], label [[TMP5:%.*]]
+; ATTRIBUTOR:       3:
+; ATTRIBUTOR-NEXT:    [[TMP4:%.*]] = tail call align 8 i8* @f2b(i8* nonnull align 8 dereferenceable(1) @a1)
+; ATTRIBUTOR-NEXT:    [[L:%.*]] = load i8, i8* [[TMP4]], align 8
+; ATTRIBUTOR-NEXT:    store i8 [[L]], i8* @a1, align 8
+; ATTRIBUTOR-NEXT:    br label [[TMP5]]
+; ATTRIBUTOR:       5:
+; ATTRIBUTOR-NEXT:    [[TMP6:%.*]] = phi i8* [ [[TMP4]], [[TMP3]] ], [ [[TMP0]], [[TMP1:%.*]] ]
+; ATTRIBUTOR-NEXT:    ret i8* [[TMP6]]
+;
+  %2 = icmp eq i8* %0, null
+  br i1 %2, label %3, label %5
+
+; <label>:3:                                      ; preds = %1
+  %4 = tail call i8* @f2b(i8* nonnull @a1)
+  %l = load i8, i8* %4
+  store i8 %l, i8* @a1
+  br label %5
+
+; <label>:5:                                      ; preds = %1, %3
+  %6 = phi i8* [ %4, %3 ], [ %0, %1 ]
+  ret i8* %6
+}
+
+; Function Attrs: nounwind readnone ssp uwtable
+define internal i8* @f2b(i8* readnone %0) local_unnamed_addr #0 {
+;
+; ATTRIBUTOR-LABEL: define {{[^@]+}}@f2b
+; ATTRIBUTOR-SAME: (i8* nonnull readnone align 8 dereferenceable(1) "no-capture-maybe-returned" [[TMP0:%.*]]) local_unnamed_addr
+; ATTRIBUTOR-NEXT:    [[TMP2:%.*]] = icmp eq i8* @a1, null
+; ATTRIBUTOR-NEXT:    br i1 [[TMP2]], label [[TMP5:%.*]], label [[TMP3:%.*]]
+; ATTRIBUTOR:       3:
+; ATTRIBUTOR-NEXT:    [[TMP4:%.*]] = tail call i8* @f1b(i8* nonnull align 8 dereferenceable(1) "no-capture-maybe-returned" @a1)
+; ATTRIBUTOR-NEXT:    br label [[TMP7:%.*]]
+; ATTRIBUTOR:       5:
+; ATTRIBUTOR-NEXT:    [[TMP6:%.*]] = tail call i8* @f3b(i8* nonnull align 16 dereferenceable(1) @a2)
+; ATTRIBUTOR-NEXT:    br label [[TMP7]]
+; ATTRIBUTOR:       7:
+; ATTRIBUTOR-NEXT:    [[TMP8:%.*]] = phi i8* [ [[TMP4]], [[TMP3]] ], [ [[TMP6]], [[TMP5]] ]
+; ATTRIBUTOR-NEXT:    ret i8* [[TMP8]]
+;
+  %2 = icmp eq i8* %0, null
+  br i1 %2, label %5, label %3
+
+; <label>:3:                                      ; preds = %1
+
+  %4 = tail call i8* @f1b(i8* nonnull %0)
+  br label %7
+
+; <label>:5:                                      ; preds = %1
+  %6 = tail call i8* @f3b(i8* nonnull @a2)
+  br label %7
+
+; <label>:7:                                      ; preds = %5, %3
+  %8 = phi i8* [ %4, %3 ], [ %6, %5 ]
+  ret i8* %8
+}
+
+; Function Attrs: nounwind readnone ssp uwtable
+define internal i8* @f3b(i8* readnone %0) local_unnamed_addr #0 {
+;
+; ATTRIBUTOR-LABEL: define {{[^@]+}}@f3b
+; ATTRIBUTOR-SAME: (i8* nocapture nonnull readnone align 16 dereferenceable(1) [[TMP0:%.*]]) local_unnamed_addr
+; ATTRIBUTOR-NEXT:    [[TMP2:%.*]] = icmp eq i8* @a2, null
+; ATTRIBUTOR-NEXT:    br i1 [[TMP2]], label [[TMP3:%.*]], label [[TMP5:%.*]]
+; ATTRIBUTOR:       3:
+; ATTRIBUTOR-NEXT:    [[TMP4:%.*]] = tail call i8* @f1b(i8* nonnull align 16 dereferenceable(1) @a2)
+; ATTRIBUTOR-NEXT:    br label [[TMP5]]
+; ATTRIBUTOR:       5:
+; ATTRIBUTOR-NEXT:    [[TMP6:%.*]] = phi i8* [ [[TMP4]], [[TMP3]] ], [ @a1, [[TMP1:%.*]] ]
+; ATTRIBUTOR-NEXT:    ret i8* [[TMP6]]
+;
+  %2 = icmp eq i8* %0, null
+  br i1 %2, label %3, label %5
+
+; <label>:3:                                      ; preds = %1
+  %4 = tail call i8* @f1b(i8* nonnull @a2)
+  br label %5
+
+; <label>:5:                                      ; preds = %1, %3
+  %6 = phi i8* [ %4, %3 ], [ @a1, %1 ]
+  ret i8* %6
+}
+
+define align 4 i32* @test7b(i32* align 32 %p) #0 {
+  tail call i8* @f1b(i8* align 8 dereferenceable(1) @a1)
+  ret i32* %p
+}
+
 
 ; TEST 8
 define void @test8_helper() {
   %ptr0 = tail call i32* @unknown()
   %ptr1 = tail call align 4 i32* @unknown()
   %ptr2 = tail call align 8 i32* @unknown()
 
   tail call void @test8(i32* %ptr1, i32* %ptr1, i32* %ptr0)
 ; ATTRIBUTOR: tail call void @test8(i32* align 4 %ptr1, i32* align 4 %ptr1, i32* %ptr0)
   tail call void @test8(i32* %ptr2, i32* %ptr1, i32* %ptr1)
 ; ATTRIBUTOR: tail call void @test8(i32* align 8 %ptr2, i32* align 4 %ptr1, i32* align 4 %ptr1)
   tail call void @test8(i32* %ptr2, i32* %ptr1, i32* %ptr1)
 ; ATTRIBUTOR: tail call void @test8(i32* align 8 %ptr2, i32* align 4 %ptr1, i32* align 4 %ptr1)
   ret void
 }
 
+declare void @user_i32_ptr(i32*) readnone nounwind
 define internal void @test8(i32* %a, i32* %b, i32* %c) {
 ; ATTRIBUTOR: define internal void @test8(i32* nocapture readnone align 4 %a, i32* nocapture readnone align 4 %b, i32* nocapture readnone %c)
+  call void @user_i32_ptr(i32* %a)
+  call void @user_i32_ptr(i32* %b)
+  call void @user_i32_ptr(i32* %c)
   ret void
 }
 
 declare void @test9_helper(i32* %A)
 define void @test9_traversal(i1 %c, i32* align 4 %B, i32* align 8 %C) {
   %sel = select i1 %c, i32* %B, i32* %C
   call void @test9_helper(i32* %sel)
   ret void

llvm/test/Transforms/FunctionAttrs/liveness.ll

-; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s
+; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=4 -S < %s | FileCheck %s
 
 declare void @no_return_call() nofree noreturn nounwind readnone
 
 declare void @normal_call() readnone
 
 declare i32 @foo()
 
 declare i32 @foo_noreturn_nounwind() noreturn nounwind

 }
 ; TEST 1: Only first block is live.
 
 ; CHECK: Function Attrs: nofree noreturn nosync nounwind
 ; CHECK-NEXT: define i32 @first_block_no_return(i32 %a, i32* nocapture nonnull readonly %ptr1, i32* nocapture readnone %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* nocapture nonnull readonly %ptr1)
+  ; CHECK: call i32 @internal_load(i32* nocapture nonnull readonly undef)
   call void @no_return_call()
   ; CHECK: call void @no_return_call()
   ; CHECK-NEXT: unreachable
   ; CHECK-NEXT: }
   call i32 @dead_internal_func(i32 10)
   %cmp = icmp eq i32 %a, 0
   br i1 %cmp, label %cond.true, label %cond.false
 
lp1:
   %lp = landingpad { i8*, i32 } catch i8* null
   invoke void @blowup() to label %live_with_dead_entry unwind label %lp2
 lp2:
   %0 = landingpad { i8*, i32 } catch i8* null
   br label %live_with_dead_entry
 live_with_dead_entry:
   ret void
 }
+
+; CHECK: define internal void @useless_arg_sink(i32* nocapture readnone %a)
+define internal void @useless_arg_sink(i32* %a) {
+  ret void
+}
+
+; CHECK: define internal void @useless_arg_almost_sink(i32* nocapture readnone %a)
+define internal void @useless_arg_almost_sink(i32* %a) {
+; CHECK: call void @useless_arg_sink(i32* nocapture undef)
+  call void @useless_arg_sink(i32* %a)
+  ret void
+}
+
+; Check we do not annotate the function interface of this weak function.
+; CHECK: define weak_odr void @useless_arg_ext(i32* %a)
+define weak_odr void @useless_arg_ext(i32* %a) {
+; CHECK: call void @useless_arg_almost_sink(i32* undef)
+  call void @useless_arg_almost_sink(i32* %a)
+  ret void
+}
+
+; CHECK: define internal void @useless_arg_ext_int(i32* %a)
+define internal void @useless_arg_ext_int(i32* %a) {
+; CHECK: call void @useless_arg_ext(i32* %a)
+  call void @useless_arg_ext(i32* %a)
+  ret void
+}
+
+define void @useless_arg_ext_int_ext(i32* %a) {
+; CHECK: call void @useless_arg_ext_int(i32* %a)
+  call void @useless_arg_ext_int(i32* %a)
+  ret void
+}

llvm/test/Transforms/FunctionAttrs/new_attributes.ll

 declare i32 @foo2()
 declare i32 @foo3()
 
 ; CHECK-NOT: Function
 ; CHECK:      define internal i32 @bar() {
 ; CHECK-NEXT:   %1 = call i32 @foo1()
 ; CHECK-NEXT:   %2 = call i32 @foo2()
 ; CHECK-NEXT:   %3 = call i32 @foo3()
-; CHECK-NEXT:   ret i32 1
+; CHECK-NEXT:   ret i32 undef
 ; CHECK-NEXT: }
 define internal i32 @bar() {
   %1 = call i32 @foo1()
   %2 = call i32 @foo2()
   %3 = call i32 @foo3()
   ret i32 1
 }
 

llvm/test/Transforms/FunctionAttrs/noalias_returned.ll

 }
 
 
 ; TEST 10
 ; Simple CallSite Test
 
 declare void @test10_helper_1(i8* %a)
 define void @test10_helper_2(i8* noalias %a) {
+; CHECK:   tail call void @test10_helper_1(i8* %a)
+  tail call void @test10_helper_1(i8* %a)
   ret void
 }
 define void @test10(i8* noalias %a) {
 ; CHECK: define void @test10(i8* noalias %a)
 ; FIXME: missing noalias
 ; CHECK-NEXT:   tail call void @test10_helper_1(i8* %a)
   tail call void @test10_helper_1(i8* %a)