[Attributor] Liveness for internal functions.

[sstefan1]

Summary

For an internal function, if all its call sites are dead, the body of the function is considered dead. This patch also updates checkForAllCallSites with llvm::function_ref.

[jdoerfert]

Test missing, otherwise good

llvm/lib/Transforms/IPO/Attributor.cpp

1495

Move this into a helper function as it is a copy of the init code.

[sstefan1]

• adding tests & helper function

[jdoerfert]

llvm/test/Transforms/FunctionAttrs/liveness.ll

29 ↗

(On Diff #214934)

We should kill dead functions in the manifest method.

[sstefan1]

• Replace dead functions with undef

[jdoerfert]

llvm/test/Transforms/FunctionAttrs/align.ll

130 ↗

(On Diff #215262)

Use this as scc test in liveness and make one of them live in this test so that all become live

llvm/test/Transforms/FunctionAttrs/liveness.ll

18 ↗

(On Diff #215262)

These should not be derived anymore. We stopped annotating dead stuff.

[sstefan1]

llvm/test/Transforms/FunctionAttrs/liveness.ll

18 ↗

(On Diff #215262)

Didn't intend to include this. This is actually a leftover. Didn't see you committed that.

[sstefan1]

• add scc test

[jdoerfert]

A few minor comments, otherwise LGTM.

llvm/lib/Transforms/IPO/Attributor.cpp

1286

maybe (!...empty())

llvm/test/Transforms/FunctionAttrs/align.ll

140 ↗

(On Diff #215277)

This will not pass lit

llvm/test/Transforms/FunctionAttrs/liveness.ll

18 ↗

(On Diff #215262)

Make sure this passes after rebase.

[sstefan1]

• small update
• Attributor::isAssumedDead() fix

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

1488

Only do the whole conditional once. Hence, add && AssumedLiveBlocks.empy() to the conditional in line 1838.

1523

I'm confused. When do we need this status flag here, I mean why isn't the one above sufficient. And if this one is needed, why only if we find a new NextNoReturnI and not once the path size changes (as before)?

2087

This is not a valid cast.

You want &AA::ID == &AAIsDead::ID

llvm/test/Transforms/FunctionAttrs/align.ll

95 ↗

(On Diff #215970)

Why do we loose the align?

[sstefan1]

llvm/lib/Transforms/IPO/Attributor.cpp

1523

This was actually a leftover. I was trying things when I thought I messed something with verification.

[sstefan1]

addressing comments

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

1287

Add a new STATS_DECL... here to count number of dead internal functions.

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

struct Attributor {
   void identifyDefaultAbstractAttributes(
       Function &F, DenseSet<const char *> *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 checkForAllCallSites(Function &F,
+                            const function_ref<bool(CallSite)> &Pred,
                             const AbstractAttribute &QueryingAA,
                             bool RequireAllCallSites);
 
   /// Check \p Pred on all values potentially returned by \p F.
   ///
   /// This method will evaluate \p Pred on all values potentially returned by
   /// \p F associated to their respective return instructions. Return true if
   /// \p Pred holds on all of them.

llvm/lib/Transforms/IPO/Attributor.cpp

struct AANonNullCallSiteArgument final : AANonNullImpl {
   }
 };
 
 ChangeStatus AANonNullArgument::updateImpl(Attributor &A) {
   Function &F = getAnchorScope();
   unsigned ArgNo = getArgNo();
 
   // Callback function
-  std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) {
+  auto CallSiteCheck = [&](CallSite CS) {
     assert(CS && "Sanity check: Call site was not initialized properly!");
 
     auto *NonNullAA =
         A.getAAFor<AANonNullImpl>(*this, *CS.getInstruction(), ArgNo);
 
     // Check that NonNullAA is AANonNullCallSiteArgument.
     if (NonNullAA) {
       ImmutableCallSite ICS(&NonNullAA->getAnchorValue());

 /// -------------------AAIsDead Function Attribute-----------------------
 
 struct AAIsDeadImpl : public AAIsDead {
   IRPositionConstructorForward(AAIsDeadImpl, AAIsDead);
 
   void initialize(Attributor &A) override {
     const Function &F = getAnchorScope();
 
+    if (F.hasInternalLinkage()) {
+      LLVM_DEBUG(dbgs() << "[INIT] skipped internal function\n");
+      return;
+    }
+
     ToBeExploredPaths.insert(&(F.getEntryBlock().front()));
     AssumedLiveBlocks.insert(&(F.getEntryBlock()));
     for (size_t i = 0; i < ToBeExploredPaths.size(); ++i)
       if (const Instruction *NextNoReturnI =
               findNextNoReturn(A, ToBeExploredPaths[i]))
         NoReturnCalls.insert(NextNoReturnI);
   }
 
struct AAIsDeadImpl : public AAIsDead {
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     assert(getState().isValidState() &&
            "Attempted to manifest an invalid state!");
 
     ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
     const Function &F = getAnchorScope();
 
     // 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 Instruction *NRC : NoReturnCalls) {
       Instruction *I = const_cast<Instruction *>(NRC);
       BasicBlock *BB = I->getParent();
       Instruction *SplitPos = I->getNextNode();
 
for (const BasicBlock *SuccBB : successors(BB)) {
     ToBeExploredPaths.insert(&SuccBB->front());
   }
 
   // No noreturn instruction found.
   return nullptr;
 }
 
 ChangeStatus AAIsDeadImpl::updateImpl(Attributor &A) {
+  Function &F = getAnchorScope();
+  ChangeStatus Status = ChangeStatus::UNCHANGED;
+
+  if (F.hasInternalLinkage()) {
+    auto CallSiteCheck = [&](CallSite) { return false; };
+
+    // All callsites of F are dead.
+    if (A.checkForAllCallSites(F, CallSiteCheck, *this, true)){
+      LLVM_DEBUG(dbgs() << "[UPDATEIMPL] All call sites are dead\n");
+      return ChangeStatus::UNCHANGED;
+    }
+
+    // There exists at least one live call site, so we explore the function.
+
+    Status = ChangeStatus::CHANGED;
+    ToBeExploredPaths.insert(&(F.getEntryBlock().front()));
+    AssumedLiveBlocks.insert(&(F.getEntryBlock()));
+    for (size_t i = 0; i < ToBeExploredPaths.size(); ++i)
+      if (const Instruction *NextNoReturnI =
+              findNextNoReturn(A, ToBeExploredPaths[i]))
+        NoReturnCalls.insert(NextNoReturnI);
+  }
+
   // Temporary collection to iterate over existing noreturn instructions. This
   // will alow easier modification of NoReturnCalls collection
   SmallVector<const Instruction *, 8> NoReturnChanged;
-  ChangeStatus Status = ChangeStatus::UNCHANGED;
 
   for (const Instruction *I : NoReturnCalls)
     NoReturnChanged.push_back(I);
 
   for (const Instruction *I : NoReturnChanged) {
     size_t Size = ToBeExploredPaths.size();
 
     const Instruction *NextNoReturnI = findNextNoReturn(A, I);
     if (NextNoReturnI != I) {
       Status = ChangeStatus::CHANGED;
       NoReturnCalls.remove(I);
       if (NextNoReturnI)
         NoReturnCalls.insert(NextNoReturnI);
     }
 
     // Explore new paths.
     while (Size != ToBeExploredPaths.size()) {
       Status = ChangeStatus::CHANGED;
       if (const Instruction *NextNoReturnI =
               findNextNoReturn(A, ToBeExploredPaths[Size++]))
         NoReturnCalls.insert(NextNoReturnI);
     }
   }
 
   LLVM_DEBUG(
       dbgs() << "[AAIsDead] AssumedLiveBlocks: " << AssumedLiveBlocks.size()
              << " Total number of blocks: " << getAnchorScope().size() << "\n");
 
   // If we know everything is live there is no need to query for liveness.
   if (NoReturnCalls.empty() &&
       getAnchorScope().size() == AssumedLiveBlocks.size()) {
ChangeStatus AADereferenceableArgument::updateImpl(Attributor &A) {
   unsigned ArgNo = Arg.getArgNo();
 
   syncNonNull(A.getAAFor<AANonNull>(*this, F, ArgNo));
 
   bool IsNonNull = isAssumedNonNull();
   bool IsGlobal = isAssumedGlobal();
 
   // Callback function
-  std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) -> bool {
+  auto CallSiteCheck = [&](CallSite CS) {
     assert(CS && "Sanity check: Call site was not initialized properly!");
 
     // Check that DereferenceableAA is AADereferenceableCallSiteArgument.
     if (auto *DereferenceableAA =
             A.getAAFor<AADereferenceable>(*this, *CS.getInstruction(), ArgNo)) {
       ImmutableCallSite ICS(
           &DereferenceableAA->getIRPosition().getAnchorValue());
       if (ICS && CS.getInstruction() == ICS.getInstruction()) {
ChangeStatus AAAlignArgument::updateImpl(Attributor &A) {
   Argument &Arg = cast<Argument>(getAnchorValue());
 
   unsigned ArgNo = Arg.getArgNo();
   const DataLayout &DL = A.getDataLayout();
 
   auto BeforeState = getAssumed();
 
   // Callback function
-  std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) {
+  auto CallSiteCheck = [&](CallSite CS) {
     assert(CS && "Sanity check: Call site was not initialized properly!");
 
     auto *AlignAA = A.getAAFor<AAAlign>(*this, *CS.getInstruction(), ArgNo);
 
     // Check that AlignAA is AAAlignCallSiteArgument.
     if (AlignAA) {
       ImmutableCallSite ICS(&AlignAA->getIRPosition().getAnchorValue());
       if (ICS && CS.getInstruction() == ICS.getInstruction()) {
struct AANoReturnFunction final : AANoReturnImpl {
   }
 };
 
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 bool Attributor::checkForAllCallSites(Function &F,
-                                      std::function<bool(CallSite)> &Pred,
+                                      const function_ref<bool(CallSite)> &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.
   if (RequireAllCallSites && !F.hasInternalLinkage()) {
     LLVM_DEBUG(
         dbgs()
         << "Attributor: Function " << F.getName()