[Attributor] Propagate known information from `checkForAllCallSites`

[jdoerfert]

Summary

If we know that all call sites have been processed we can derive an
early fixpoint. The use in this patch is likely not to trigger right now
but a follow up patch will make use of it.

[merge_guards_bot]

Unit tests: pass. 61153 tests passed, 0 failed and 728 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[baziotis]

llvm/lib/Transforms/IPO/Attributor.cpp

2667

Maybe something similar can be done for AAValueSimplifyArgument?

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

2667

True, probably for others as well. Though, especially AAValueSimplifyArgument is somewhat in flux right now. The follow up applies this to AANoRecurse in order to get rid of the last FIXMEs in the norecurse test.

[baziotis]

llvm/lib/Transforms/IPO/Attributor.cpp

2667

Ok, good, I'll take a look.

[uenoku]

LGTM from me.

[baziotis]

LGTM too.

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

struct Attributor {
   bool checkForAllUses(const function_ref<bool(const Use &, bool &)> &Pred,
                        const AbstractAttribute &QueryingAA, const Value &V);
 
   /// 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.
+  /// If true is returned, \p AllCallSitesKnown is set if all possible call
+  /// sites of the function have been visited.
   bool checkForAllCallSites(const function_ref<bool(AbstractCallSite)> &Pred,
                             const AbstractAttribute &QueryingAA,
-                            bool RequireAllCallSites);
+                            bool RequireAllCallSites, bool &AllCallSitesKnown);
 
   /// Check \p Pred on all values potentially returned by \p F.
   ///
   /// This method will evaluate \p Pred on all values potentially returned by
   /// the function associated with \p QueryingAA. The returned values are
   /// matched with their respective return instructions. Returns true if \p Pred
   /// holds on all of them.
   bool checkForAllReturnedValuesAndReturnInsts(
struct Attributor {
   const DataLayout &getDataLayout() const { return InfoCache.DL; }
 
 private:
   /// Check \p Pred on all call sites of \p Fn.
   ///
   /// 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.
+  /// If true is returned, \p AllCallSitesKnown is set if all possible call
+  /// sites of the function have been visited.
   bool checkForAllCallSites(const function_ref<bool(AbstractCallSite)> &Pred,
                             const Function &Fn, bool RequireAllCallSites,
-                            const AbstractAttribute *QueryingAA);
+                            const AbstractAttribute *QueryingAA,
+                            bool &AllCallSitesKnown);
 
   /// The private version of getAAFor that allows to omit a querying abstract
   /// attribute. See also the public getAAFor method.
   template <typename AAType>
   const AAType &getOrCreateAAFor(const IRPosition &IRP,
                                  const AbstractAttribute *QueryingAA = nullptr,
                                  bool TrackDependence = false,
                                  DepClassTy DepClass = DepClassTy::OPTIONAL) {

 /// 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 the underlying value is known dead.
+  virtual bool isKnownDead() 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

if (T.hasValue())
       *T &= AAS;
     else
       T = AAS;
     LLVM_DEBUG(dbgs() << "[Attributor] AA State: " << AAS << " CSA State: " << T
                       << "\n");
     return T->isValidState();
   };
 
-  if (!A.checkForAllCallSites(CallSiteCheck, QueryingAA, true))
+  bool AllCallSitesKnown;
+  if (!A.checkForAllCallSites(CallSiteCheck, QueryingAA, true,
+                              AllCallSitesKnown))
     S.indicatePessimisticFixpoint();
   else if (T.hasValue())
     S ^= *T;
 }
 
 /// Helper class for generic deduction: call site argument -> argument position.
 template <typename AAType, typename Base,
           typename StateType = typename AAType::StateType>

 /// -------------------AAIsDead Function Attribute-----------------------
 
 struct AAIsDeadValueImpl : public AAIsDead {
   AAIsDeadValueImpl(const IRPosition &IRP) : AAIsDead(IRP) {}
 
   /// See AAIsDead::isAssumedDead().
   bool isAssumedDead() const override { return getAssumed(); }
 
+  /// See AAIsDead::isKnownDead().
+  bool isKnownDead() const override { return getKnown(); }
+
   /// 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::isAssumedDead(Instruction *I).
   bool isAssumedDead(const Instruction *I) const override {

 };
 
 struct AAIsDeadReturned : public AAIsDeadValueImpl {
   AAIsDeadReturned(const IRPosition &IRP) : AAIsDeadValueImpl(IRP) {}
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
 
+    bool AllKnownDead = true;
     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);
+      AllKnownDead &= RetIsDeadAA.isKnownDead();
       return RetIsDeadAA.isAssumedDead();
     };
 
-    if (!A.checkForAllCallSites(PredForCallSite, *this, true))
+    bool AllCallSitesKnown;
+    if (!A.checkForAllCallSites(PredForCallSite, *this, true,
+                                AllCallSitesKnown))
       return indicatePessimisticFixpoint();
 
+    if (AllCallSitesKnown && AllKnownDead)
+      indicateOptimisticFixpoint();
+
     return ChangeStatus::UNCHANGED;
   }
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     // TODO: Rewrite the signature to return void?
     bool AnyChange = false;
     UndefValue &UV = *UndefValue::get(getAssociatedFunction()->getReturnType());
struct AAIsDeadFunction : public AAIsDead {
   ChangeStatus updateImpl(Attributor &A) override;
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {}
 
   /// Returns true if the function is assumed dead.
   bool isAssumedDead() const override { return false; }
 
+  /// See AAIsDead::isKnownDead().
+  bool isKnownDead() 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);
auto PredForCallSite = [&](AbstractCallSite ACS) {
       // be different for the caller and callee, making it invalid to propagate.
       if (ACS.isCallbackCall())
         if (auto *C = dyn_cast<Constant>(ArgOp))
           if (C->isThreadDependent())
             return false;
       return checkAndUpdate(A, *this, *ArgOp, SimplifiedAssociatedValue);
     };
 
-    if (!A.checkForAllCallSites(PredForCallSite, *this, true))
+    bool AllCallSitesKnown;
+    if (!A.checkForAllCallSites(PredForCallSite, *this, true,
+                                AllCallSitesKnown))
       return indicatePessimisticFixpoint();
 
     // If a candicate was found in this update, return CHANGED.
     return HasValueBefore == SimplifiedAssociatedValue.hasValue()
                ? ChangeStatus::UNCHANGED
                : ChangeStatus ::CHANGED;
   }
 
bool Attributor::checkForAllUses(
   if (AnyDead)
     recordDependence(*LivenessAA, QueryingAA, DepClassTy::OPTIONAL);
 
   return true;
 }
 
 bool Attributor::checkForAllCallSites(
     const function_ref<bool(AbstractCallSite)> &Pred,
-    const AbstractAttribute &QueryingAA, bool RequireAllCallSites) {
+    const AbstractAttribute &QueryingAA, bool RequireAllCallSites,
+    bool &AllCallSitesKnown) {
   // 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();
   if (!AssociatedFunction) {
     LLVM_DEBUG(dbgs() << "[Attributor] No function associated with " << IRP
                       << "\n");
+    AllCallSitesKnown = false;
     return false;
   }
 
   return checkForAllCallSites(Pred, *AssociatedFunction, RequireAllCallSites,
-                              &QueryingAA);
+                              &QueryingAA, AllCallSitesKnown);
 }
 
 bool Attributor::checkForAllCallSites(
     const function_ref<bool(AbstractCallSite)> &Pred, const Function &Fn,
-    bool RequireAllCallSites, const AbstractAttribute *QueryingAA) {
+    bool RequireAllCallSites, const AbstractAttribute *QueryingAA,
+    bool &AllCallSitesKnown) {
   if (RequireAllCallSites && !Fn.hasLocalLinkage()) {
     LLVM_DEBUG(
         dbgs()
         << "[Attributor] Function " << Fn.getName()
         << " has no internal linkage, hence not all call sites are known\n");
+    AllCallSitesKnown = false;
     return false;
   }
 
+  // If we do not require all call sites we might not see all.
+  AllCallSitesKnown = RequireAllCallSites;
+
   for (const Use &U : Fn.uses()) {
     AbstractCallSite ACS(&U);
     if (!ACS) {
       LLVM_DEBUG(dbgs() << "[Attributor] Function " << Fn.getName()
                         << " has non call site use " << *U.get() << " in "
                         << *U.getUser() << "\n");
       // BlockAddress users are allowed.
       if (isa<BlockAddress>(U.getUser()))
const auto *LivenessAA =
                               /* TrackDependence */ false);
 
     // Skip dead calls.
     if (LivenessAA && LivenessAA->isAssumedDead(I)) {
       // We actually used liveness information so we have to record a
       // dependence.
       if (QueryingAA)
         recordDependence(*LivenessAA, *QueryingAA, DepClassTy::OPTIONAL);
+      AllCallSitesKnown = false;
       continue;
     }
 
     const Use *EffectiveUse =
         ACS.isCallbackCall() ? &ACS.getCalleeUseForCallback() : &U;
     if (!ACS.isCallee(EffectiveUse)) {
       if (!RequireAllCallSites)
         continue;
// Delete stuff at the end to avoid invalid references and a nice order.
     bool FoundDeadFn = true;
     while (FoundDeadFn) {
       FoundDeadFn = false;
       for (unsigned u = 0, e = InternalFns.size(); u < e; ++u) {
         Function *F = InternalFns[u];
         if (!F)
           continue;
 
+        bool AllCallSitesKnown;
         if (!checkForAllCallSites([](AbstractCallSite ACS) { return false; },
-                                  *F, true, nullptr))
+                                  *F, true, nullptr, AllCallSitesKnown))
           continue;
 
         STATS_TRACK(AAIsDead, Function);
         ToBeDeletedFunctions.insert(F);
         F->deleteBody();
         F->replaceAllUsesWith(UndefValue::get(F->getType()));
         F->eraseFromParent();
         InternalFns[u] = nullptr;