[Attributor] Look at internal functions only on-demand

[jdoerfert]

Summary

Instead of building attributes for internal functions which we do not
update as long as we assume they are dead, we now do not create
attributes until we assume the internal function to be live. This
improves the number of required iterations, as well as the number of
required updates, in real code. On our tests, the results are mixed.

[jdoerfert]

Update tests

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

144–155

Is AADummy used in this patch? What is the purpose?

llvm/test/Transforms/FunctionAttrs/align.ll

1

Why does max-iterations increase?

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

144–155

It was, then I removed the use -.-, will remove the dummy AA as well. Was used as QueryingAA but no need anymore.

llvm/test/Transforms/FunctionAttrs/align.ll

1

Because we look at internal functions later. That should not increase the overall time spend or number of total updates. Once these patches are through I'll also add a test I distilled from a benchmark to verify we keep a low number of iterations in an actual "corner case" that exists.

[uenoku]

LGTM

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

struct Attributor {
   ~Attributor() { DeleteContainerPointers(AllAbstractAttributes); }
 
   /// Run the analyses until a fixpoint is reached or enforced (timeout).
   ///
   /// The attributes registered with this Attributor can be used after as long
   /// as the Attributor is not destroyed (it owns the attributes now).
   ///
   /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
-  ChangeStatus run();
+  ChangeStatus run(Module &M);
 
   /// Lookup an abstract attribute of type \p AAType at position \p IRP. While
   /// no abstract attribute is found equivalent positions are checked, see
   /// SubsumingPositionIterator. Thus, the returned abstract attribute
   /// might be anchored at a different position, e.g., the callee if \p IRP is a
   /// call base.
   ///
   /// This method is the only (supported) way an abstract attribute can retrieve
struct Attributor {
   ///
   /// Note that abstract attribute instances are generally created even if the
   /// IR already contains the information they would deduce. The most important
   /// reason for this is the single interface, the one of the abstract attribute
   /// instance, which can be queried without the need to look at the IR in
   /// various places.
   void identifyDefaultAbstractAttributes(Function &F);
 
+  /// Mark the internal function \p F as live.
+  ///
+  /// This will trigger the identification and initialization of attributes for
+  /// \p F.
+  void markLiveInternalFunction(const Function &F) {
+    assert(F.hasInternalLinkage() &&
+            "Only internal linkage is assumed dead initially.");
+    identifyDefaultAbstractAttributes(const_cast<Function &>(F));
+  }
+
   /// Record that \p I is deleted after information was manifested.
   void deleteAfterManifest(Instruction &I) { ToBeDeletedInsts.insert(&I); }
 
   /// Record that \p BB is deleted after information was manifested.
   void deleteAfterManifest(BasicBlock &BB) { ToBeDeletedBlocks.insert(&BB); }
 
   /// Record that \p F is deleted after information was manifested.
   void deleteAfterManifest(Function &F) { ToBeDeletedFunctions.insert(&F); }
private:
 
   /// Number of iterations until the dependences between abstract attributes are
   /// recomputed.
   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;
+
   /// Functions, blocks, and instructions we delete after manifest is done.
   ///
   ///{
   SmallPtrSet<Function *, 8> ToBeDeletedFunctions;
   SmallPtrSet<BasicBlock *, 8> ToBeDeletedBlocks;
   SmallPtrSet<Instruction *, 8> ToBeDeletedInsts;
   ///}
 };

llvm/lib/Transforms/IPO/Attributor.cpp

 ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) {
   return l == ChangeStatus::CHANGED ? l : r;
 }
 ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) {
   return l == ChangeStatus::UNCHANGED ? l : r;
 }
 ///}
 
+namespace {
+/// A dummy abstract attribute that can be used in the query APIs.
+struct AADummy : public StateWrapper<BooleanState, AbstractAttribute>,
+                 public IRPosition {
+  AADummy(const IRPosition &IRP) : IRPosition(IRP) {}
+  IRPosition &getIRPosition() override { return *this; }
+  const IRPosition &getIRPosition() const override { return *this; }
+  const std::string getAsStr() const override { return ""; }
+  void trackStatistics() const override {}
+  ChangeStatus updateImpl(Attributor &A) override {
+    return ChangeStatus::CHANGED;
+  };
+};
+}
+
 /// Recursively visit all values that might become \p IRP at some point. This
 /// will be done by looking through cast instructions, selects, phis, and calls
 /// with the "returned" attribute. Once we cannot look through the value any
 /// further, the callback \p VisitValueCB is invoked and passed the current
 /// value, the \p State, and a flag to indicate if we stripped anything. To
 /// limit how much effort is invested, we will never visit more values than
 /// specified by \p MaxValues.
 template <typename AAType, typename StateTy>

 };
 
 /// -------------------AAIsDead Function Attribute-----------------------
 
 struct AAIsDeadImpl : public AAIsDead {
   AAIsDeadImpl(const IRPosition &IRP) : AAIsDead(IRP) {}
 
   void initialize(Attributor &A) override {
-    const Function *F = getAssociatedFunction();
-
-    if (F->hasInternalLinkage())
-      return;
-
-    if (!F || !F->hasExactDefinition()) {
-      indicatePessimisticFixpoint();
-      return;
-    }
-
+    if (const Function *F = getAssociatedFunction())
       exploreFromEntry(A, F);
   }
 
   void exploreFromEntry(Attributor &A, const Function *F) {
     ToBeExploredPaths.insert(&(F->getEntryBlock().front()));
     AssumedLiveBlocks.insert(&(F->getEntryBlock()));
 
     for (size_t i = 0; i < ToBeExploredPaths.size(); ++i)
       if (const Instruction *NextNoReturnI =
struct AAIsDeadImpl : public AAIsDead {
   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(
-        DeadInternalFunction, Function,
-        "Number of internal functions classified as dead (no live callsite)");
-    BUILD_STAT_NAME(DeadInternalFunction, Function) +=
-        (getAssociatedFunction()->hasInternalLinkage() &&
-         AssumedLiveBlocks.empty())
-            ? 1
-            : 0;
-    STATS_DECL(DeadBlocks, Function,
-               "Number of basic blocks classified as dead");
-    BUILD_STAT_NAME(DeadBlocks, Function) +=
-        getAssociatedFunction()->size() - AssumedLiveBlocks.size();
     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 {
   const Instruction *PrevI = I->getPrevNode();
const Instruction *AAIsDeadImpl::findNextNoReturn(Attributor &A,
   //       Edges could be from an instruction to the next or from a terminator
   //       to the successor. For now, we need to special case the unwind block
   //       of InvokeInst below.
 
   while (I) {
     ImmutableCallSite ICS(I);
 
     if (ICS) {
+      // We asume ICS is live now and if it calls an internal function we will
+      // assume that one is live as well.
+      if (const Function *F = ICS.getCalledFunction())
+        if (F->hasInternalLinkage())
+          A.markLiveInternalFunction(*F);
+
       const IRPosition &IPos = IRPosition::callsite_function(ICS);
       // Regarless of the no-return property of an invoke instruction we only
       // learn that the regular successor is not reachable through this
       // instruction but the unwind block might still be.
       if (auto *Invoke = dyn_cast<InvokeInst>(I)) {
         // Use nounwind to justify the unwind block is dead as well.
         const auto &AANoUnw = A.getAAFor<AANoUnwind>(*this, IPos);
         if (!Invoke2CallAllowed || !AANoUnw.isAssumedNoUnwind()) {
for (const BasicBlock *SuccBB : successors(BB)) {
     ToBeExploredPaths.insert(&SuccBB->front());
   }
 
   // No noreturn instruction found.
   return nullptr;
 }
 
 ChangeStatus AAIsDeadImpl::updateImpl(Attributor &A) {
-  const Function *F = getAssociatedFunction();
   ChangeStatus Status = ChangeStatus::UNCHANGED;
 
-  if (F->hasInternalLinkage() && AssumedLiveBlocks.empty()) {
-    auto CallSiteCheck = [&](CallSite) { return false; };
-
-    // All callsites of F are dead.
-    if (A.checkForAllCallSites(CallSiteCheck, *this, true))
-      return ChangeStatus::UNCHANGED;
-
-    // There exists at least one live call site, so we explore the function.
-    Status = ChangeStatus::CHANGED;
-
-    exploreFromEntry(A, F);
-  }
-
   // 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);
 
   for (const Instruction *I : NoReturnChanged) {
bool Attributor::checkForAllReadWriteInstructions(
 
   // If we actually used liveness information so we have to record a dependence.
   if (AnyDead)
     recordDependence(LivenessAA, QueryingAA);
 
   return true;
 }
 
-ChangeStatus Attributor::run() {
-  // Initialize all abstract attributes, allow new ones to be created.
-  for (unsigned u = 0; u < AllAbstractAttributes.size(); u++)
-    AllAbstractAttributes[u]->initialize(*this);
-
+ChangeStatus Attributor::run(Module &M) {
   LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
                     << AllAbstractAttributes.size()
                     << " abstract attributes.\n");
 
   // Now that all abstract attributes are collected and initialized we start
   // the abstract analysis.
 
   unsigned IterationCounter = 1;
ChangeStatus Attributor::run(Module &M) {
   LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
                     << IterationCounter << "/" << MaxFixpointIterations
                     << " iterations\n");
 
   size_t NumFinalAAs = AllAbstractAttributes.size();
 
   bool FinishedAtFixpoint = Worklist.empty();
 
+  // Identify dead internal functions and mark them to be deleted.
+  for (Function &F : M)
+    if (F.hasInternalLinkage() && !VisitedFunctions.count(&F))
+      deleteAfterManifest(F);
+
   // Reset abstract arguments not settled in a sound fixpoint by now. This
   // happens when we stopped the fixpoint iteration early. Note that only the
   // ones marked as "changed" *and* the ones transitively depending on them
   // need to be reverted to a pessimistic state. Others might not be in a
   // fixpoint state but we can use the optimistic results for them anyway.
   SmallPtrSet<AbstractAttribute *, 32> Visited;
   for (unsigned u = 0; u < ChangedAAs.size(); u++) {
     AbstractAttribute *ChangedAA = ChangedAAs[u];
ChangeStatus Attributor::run(Module &M) {
   // IR was changed, we re-run the whole fixpoint analysis, starting at
   // re-initialization of the arguments. This re-run should not result in an IR
   // change. Though, the (virtual) state of attributes at the end of the re-run
   // might be more optimistic than the known state or the IR state if the better
   // state cannot be manifested.
   if (VerifyAttributor && FinishedAtFixpoint &&
       ManifestChange == ChangeStatus::CHANGED) {
     VerifyAttributor = false;
-    ChangeStatus VerifyStatus = run();
+    ChangeStatus VerifyStatus = run(M);
     if (VerifyStatus != ChangeStatus::UNCHANGED)
       llvm_unreachable(
           "Attributor verification failed, re-run did result in an IR change "
           "even after a fixpoint was reached in the original run. (False "
           "positives possible!)");
     VerifyAttributor = true;
   }
 
for (Instruction *I : ToBeDeletedInsts) {
     I->eraseFromParent();
   }
 
   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.");
   }
 
   for (Function *Fn : ToBeDeletedFunctions) {
     Fn->replaceAllUsesWith(UndefValue::get(Fn->getType()));
     Fn->eraseFromParent();
+    STATS_DECLTRACK(AAIsDead, Function, "Number of dead functions.");
   }
 
   if (VerifyMaxFixpointIterations &&
       IterationCounter != MaxFixpointIterations) {
     errs() << "\n[Attributor] Fixpoint iteration done after: "
            << IterationCounter << "/" << MaxFixpointIterations
            << " iterations\n";
     llvm_unreachable("The fixpoint was not reached with exactly the number of "
                      "specified iterations!");
   }
 
   return ManifestChange;
 }
 
 void Attributor::identifyDefaultAbstractAttributes(Function &F) {
+  if (!VisitedFunctions.insert(&F).second)
+    return;
 
   IRPosition FPos = IRPosition::function(F);
 
   // Check for dead BasicBlocks in every function.
   // We need dead instruction detection because we do not want to deal with
   // broken IR in which SSA rules do not apply.
   getOrCreateAAFor<AAIsDead>(FPos);
 
for (Function &F : M) {
 
     // For now we ignore naked and optnone functions.
     if (F.hasFnAttribute(Attribute::Naked) ||
         F.hasFnAttribute(Attribute::OptimizeNone))
       continue;
 
     NumFnWithExactDefinition++;
 
+    // We look at internal functions only on-demand but if any use is not a
+    // direct call we have to do it eagerly.
+    if (F.hasInternalLinkage()) {
+      if (llvm::all_of(F.uses(), [](const Use &U) {
+            if (ImmutableCallSite ICS = ImmutableCallSite(U.getUser()))
+              return ICS.isCallee(&U);
+            return false;
+          }))
+        continue;
+    }
+
     // Populate the Attributor with abstract attribute opportunities in the
     // function and the information cache with IR information.
     A.identifyDefaultAbstractAttributes(F);
   }
 
-  return A.run() == ChangeStatus::CHANGED;
+  return A.run(M) == ChangeStatus::CHANGED;
 }
 
 PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) {
   if (runAttributorOnModule(M)) {
     // FIXME: Think about passes we will preserve and add them here.
     return PreservedAnalyses::none();
   }
   return PreservedAnalyses::all();

llvm/test/Transforms/FunctionAttrs/align.ll

-; RUN: opt -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=6 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
+; RUN: opt -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=7 -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.
 
 
 ; TEST 1

llvm/test/Transforms/FunctionAttrs/read_write_returned_arguments_scc.ll

-; RUN: opt -functionattrs -enable-nonnull-arg-prop -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=9 -S < %s | FileCheck %s
+; RUN: opt -functionattrs -enable-nonnull-arg-prop -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=6 -S < %s | FileCheck %s
 ;
 ; This is an evolved example to stress test SCC parameter attribute propagation.
 ; The SCC in this test is made up of the following six function, three of which
 ; are internal and three externally visible:
 ;
 ; static int *internal_ret0_nw(int *n0, int *w0);
 ; static int *internal_ret1_rw(int *r0, int *w0);
 ; static int *internal_ret1_rrw(int *r0, int *r1, int *w0);