[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

2953

Maybe something similar can be done for AAValueSimplifyArgument?

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

2953

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

2953

Ok, good, I'll take a look.

[uenoku]

LGTM from me.

[baziotis]

LGTM too.

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

bool registerFunctionSignatureRewrite(
       ArgumentReplacementInfo::CalleeRepairCBTy &&CalleeRepairCB,
       ArgumentReplacementInfo::ACSRepairCBTy &&ACSRepairCB);
 
   /// 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

 //===- Attributor.cpp - Module-wide attribute deduction -------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements an inter procedural pass that deduces and/or propagating
 // attributes. This is done in an abstract interpretation style fixpoint
 // iteration. See the Attributor.h file comment and the class descriptions in
 // that file for more information.
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Transforms/IPO/Attributor.h" 
+#include "llvm/Transforms/IPO/Attributor.h"
 
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/EHPersonalities.h"
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>
ChangeStatus updateImpl(Attributor &A) override {
     // If the argument is read-only, no-alias cannot break synchronization.
     const auto &MemBehaviorAA =
         A.getAAFor<AAMemoryBehavior>(*this, getIRPosition());
     if (MemBehaviorAA.isAssumedReadOnly())
       return Base::updateImpl(A);
 
     // If the argument is never passed through callbacks, no-alias cannot break
     // synchronization.
+    bool AllCallSitesKnown;
     if (A.checkForAllCallSites(
             [](AbstractCallSite ACS) { return !ACS.isCallbackCall(); }, *this,
-            true))
+            true, AllCallSitesKnown))
       return Base::updateImpl(A);
 
     // TODO: add no-alias but make sure it doesn't break synchronization by
     // introducing fake uses. See:
     // [1] Compiler Optimizations for OpenMP, J. Doerfert and H. Finkel,
     //     International Workshop on OpenMP 2018,
     //     http://compilers.cs.uni-saarland.de/people/doerfert/par_opt18.pdf
 

 /// -------------------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))
       if (!askSimplifiedValueForAAValueConstantRange(A))
         return indicatePessimisticFixpoint();
 
     // If a candicate was found in this update, return CHANGED.
     return HasValueBefore == SimplifiedAssociatedValue.hasValue()
                ? ChangeStatus::UNCHANGED
                : ChangeStatus ::CHANGED;
   }

 struct AAPrivatizablePtrArgument final : public AAPrivatizablePtrImpl {
   AAPrivatizablePtrArgument(const IRPosition &IRP)
       : AAPrivatizablePtrImpl(IRP) {}
 
   /// See AAPrivatizablePtrImpl::identifyPrivatizableType(...)
   Optional<Type *> identifyPrivatizableType(Attributor &A) override {
     // If this is a byval argument and we know all the call sites (so we can
     // rewrite them), there is no need to check them explicitly.
+    bool AllCallSitesKnown;
     if (getIRPosition().hasAttr(Attribute::ByVal) &&
         A.checkForAllCallSites([](AbstractCallSite ACS) { return true; }, *this,
-                               true))
+                               true, AllCallSitesKnown))
       return getAssociatedValue().getType()->getPointerElementType();
 
     Optional<Type *> Ty;
     unsigned ArgNo = getIRPosition().getArgNo();
 
     // Make sure the associated call site argument has the same type at all call
     // sites and it is an allocation we know is safe to privatize, for now that
     // means we only allow alloca instructions.
auto CallSiteCheck = [&](AbstractCallSite ACS) {
         else
           dbgs() << "<none>";
         dbgs() << "\n";
       });
 
       return !Ty.hasValue() || Ty.getValue();
     };
 
-    if (!A.checkForAllCallSites(CallSiteCheck, *this, true))
+    if (!A.checkForAllCallSites(CallSiteCheck, *this, true, AllCallSitesKnown))
       return nullptr;
     return Ty;
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     PrivatizableType = identifyPrivatizableType(A);
     if (!PrivatizableType.hasValue())
ChangeStatus updateImpl(Attributor &A) override {
     auto IsCompatiblePrivArgOfOtherCallSite = [&](AbstractCallSite ACS) {
       if (ACS.isDirectCall())
         return IsCompatiblePrivArgOfCallback(ACS.getCallSite());
       if (ACS.isCallbackCall())
         return IsCompatiblePrivArgOfDirectCS(ACS);
       return false;
     };
 
-    if (!A.checkForAllCallSites(IsCompatiblePrivArgOfOtherCallSite, *this,
-                                true))
+    bool AllCallSitesKnown;
+    if (!A.checkForAllCallSites(IsCompatiblePrivArgOfOtherCallSite, *this, true,
+                                AllCallSitesKnown))
       return indicatePessimisticFixpoint();
 
     return ChangeStatus::UNCHANGED;
   }
 
   /// Given a type to private \p PrivType, collect the constituates (which are
   /// used) in \p ReplacementTypes.
   static void
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(
                 [this](AbstractCallSite ACS) {
                   return ToBeDeletedFunctions.count(
                       ACS.getInstruction()->getFunction());
                 },
-                *F, true, nullptr))
+                *F, true, nullptr, AllCallSitesKnown))
           continue;
 
         ToBeDeletedFunctions.insert(F);
         InternalFns[u] = nullptr;
         FoundDeadFn = true;
       }
     }
   }
if (FnAttributeList.hasAttrSomewhere(Attribute::Nest) ||
       FnAttributeList.hasAttrSomewhere(Attribute::StructRet) ||
       FnAttributeList.hasAttrSomewhere(Attribute::InAlloca)) {
     LLVM_DEBUG(
         dbgs() << "[Attributor] Cannot rewrite due to complex attribute\n");
     return false;
   }
 
   // Avoid callbacks for now.
-  if (!checkForAllCallSites(CallSiteCanBeChanged, *Fn, true, nullptr)) {
+  bool AllCallSitesKnown;
+  if (!checkForAllCallSites(CallSiteCanBeChanged, *Fn, true, nullptr,
+                            AllCallSitesKnown)) {
     LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite all call sites\n");
     return false;
   }
 
   auto InstPred = [](Instruction &I) {
     if (auto *CI = dyn_cast<CallInst>(&I))
       return !CI->isMustTailCall();
     return true;
auto CallSiteReplacementCreator = [&](AbstractCallSite ACS) {
           Ctx, OldCallAttributeList.getFnAttributes(),
           OldCallAttributeList.getRetAttributes(), NewArgOperandAttributes));
 
       CallSitePairs.push_back({OldCB, NewCB});
       return true;
     };
 
     // Use the CallSiteReplacementCreator to create replacement call sites.
-    bool Success =
-        checkForAllCallSites(CallSiteReplacementCreator, *OldFn, true, nullptr);
+    bool AllCallSitesKnown;
+    bool Success = checkForAllCallSites(CallSiteReplacementCreator, *OldFn,
+                                        true, nullptr, AllCallSitesKnown);
     (void)Success;
     assert(Success && "Assumed call site replacement to succeed!");
 
     // Rewire the arguments.
     auto OldFnArgIt = OldFn->arg_begin();
     auto NewFnArgIt = NewFn->arg_begin();
     for (unsigned OldArgNum = 0; OldArgNum < ARIs.size();
          ++OldArgNum, ++OldFnArgIt) {