[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

1855

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

50

We should kill dead functions in the manifest method.

[sstefan1]

• Replace dead functions with undef

[jdoerfert]

llvm/test/Transforms/FunctionAttrs/align.ll

146

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

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

[sstefan1]

llvm/test/Transforms/FunctionAttrs/liveness.ll

18

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

1639

maybe (!...empty())

llvm/test/Transforms/FunctionAttrs/align.ll

154–155

This will not pass lit

llvm/test/Transforms/FunctionAttrs/liveness.ll

18

Make sure this passes after rebase.

[sstefan1]

• small update
• Attributor::isAssumedDead() fix

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

1848

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

1878

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)?

2370

This is not a valid cast.

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

llvm/test/Transforms/FunctionAttrs/align.ll

95

Why do we loose the align?

[sstefan1]

llvm/lib/Transforms/IPO/Attributor.cpp

1878

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

1640

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

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

struct IRPosition {
   ///{
   Instruction *getCtxI() {
     Value &V = getAnchorValue();
     if (auto *I = dyn_cast<Instruction>(&V))
       return I;
     if (auto *Arg = dyn_cast<Argument>(&V))
       if (!Arg->getParent()->isDeclaration())
         return &Arg->getParent()->getEntryBlock().front();
+    if (auto *F = dyn_cast<Function>(&V))
+      if (!F->isDeclaration())
+        return &(F->getEntryBlock().front());
     return nullptr;
   }
   const Instruction *getCtxI() const {
     return const_cast<IRPosition *>(this)->getCtxI();
   }
   ///}
 
   /// Return the value this abstract attribute is associated with.

llvm/lib/Transforms/IPO/Attributor.cpp

 struct AANonNullArgument final : AANonNullImpl {
   AANonNullArgument(const IRPosition &IRP) : AANonNullImpl(IRP) {}
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     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!");
 
       IRPosition CSArgPos = IRPosition::callsite_argument(CS, ArgNo);
       if (CSArgPos.hasAttr({Attribute::NonNull, Attribute::Dereferenceable}))
         return true;
 
       // Check that NonNullAA is AANonNullCallSiteArgument.
       if (auto *NonNullAA = A.getAAFor<AANonNullImpl>(*this, CSArgPos)) {

 
 /// -------------------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;
     }
 
+    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 =
               findNextNoReturn(A, ToBeExploredPaths[i]))
         NoReturnCalls.insert(NextNoReturnI);
   }
 
   /// Find the next assumed noreturn instruction in the block of \p I starting
   /// from, thus including, \p I.
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 = *getAssociatedFunction();
+    Function &F = *getAssociatedFunction();
+
+    if (AssumedLiveBlocks.empty()) {
+      F.replaceAllUsesWith(UndefValue::get(F.getType()));
+      return ChangeStatus::CHANGED;
+    }
 
     // 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);
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()) {
+    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;
+
+    // Only do initial explore once.
+    if (NoReturnCalls.empty()) {
+      exploreFromEntry(A, F);
+    }
+  }
+
   // 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);
+      Status = ChangeStatus::CHANGED;
       if (NextNoReturnI)
         NoReturnCalls.insert(NextNoReturnI);
     }
 
     // Explore new paths.
     while (Size != ToBeExploredPaths.size()) {
-      Status = ChangeStatus::CHANGED;
       if (const Instruction *NextNoReturnI =
-              findNextNoReturn(A, ToBeExploredPaths[Size++]))
+              findNextNoReturn(A, ToBeExploredPaths[Size++])){
         NoReturnCalls.insert(NextNoReturnI);
+        Status = ChangeStatus::CHANGED;
+      }
     }
   }
 
   LLVM_DEBUG(dbgs() << "[AAIsDead] AssumedLiveBlocks: "
                     << AssumedLiveBlocks.size() << " Total number of blocks: "
                     << getAssociatedFunction()->size() << "\n");
 
   // If we know everything is live there is no need to query for liveness.
ChangeStatus AADereferenceableArgument::updateImpl(Attributor &A) {
 
   auto BeforeState = static_cast<DerefState>(*this);
 
   unsigned ArgNo = Arg.getArgNo();
 
   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, IRPosition::callsite_argument(CS, ArgNo))) {
       ImmutableCallSite ICS(
           &DereferenceableAA->getIRPosition().getAnchorValue());
       if (ICS && CS.getInstruction() == ICS.getInstruction()) {

 
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 bool Attributor::isAssumedDead(const AbstractAttribute &AA,
                                const AAIsDead *LivenessAA) {
   const Instruction *CtxI = AA.getIRPosition().getCtxI();
+
   if (!CtxI)
     return false;
 
   if (!LivenessAA)
     LivenessAA =
         getAAFor<AAIsDead>(AA, IRPosition::function(*CtxI->getFunction()));
+
+  // Don't check liveness for AAIsDead.
+  if (static_cast<const AAIsDead *>(&AA) == LivenessAA)
+    return false;
+
   if (!LivenessAA || !LivenessAA->isAssumedDead(CtxI))
     return false;
 
   // TODO: Do not track dependences automatically but add it here as only a
   //       "is-assumed-dead" result causes a dependence.
   return true;
 }
 

llvm/test/Transforms/FunctionAttrs/align.ll

 @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 {
 ; FIXME: Until we have "on-demand" attribute generation we do not determine the
 ;        alignment for the return value here.
 ;             define internal nonnull align 8 i8* @f1(i8* nonnull readnone align 8 %0)
-; ATTRIBUTOR: define internal nonnull i8* @f1(i8* nonnull readnone align 8 %0)
+; ATTRIBUTOR: define internal nonnull i8* @f1(i8* nonnull readnone %0)
   %2 = icmp eq i8* %0, null
   br i1 %2, label %3, label %5
 
 ; <label>:3:                                      ; preds = %1
 ; ATTRIBUTOR: %4 = tail call i8* @f2(i8* nonnull align 8 @a1)
   %4 = tail call i8* @f2(i8* nonnull @a1)
   br label %5
 

 ;             define internal nonnull align 8 i8* @f3(i8* nonnull readnone align 16 %0)
 ; ATTRIBUTOR: define internal nonnull i8* @f3(i8* nonnull readnone align 16 %0)
   %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 @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* returned align 32 %p)
-define align 4 i32* @test7(i32* align 32 %p) #0 {
+; ATTRIBUTOR: define align 32 i32* @test7(i32* returned align 32 %p, i8* readnone %c)
+define align 4 i32* @test7(i32* align 32 %p, i8* readnone %c) #0 {
+  tail call i8* @f1(i8* nonnull %c)
   ret i32* %p
 }
 
 
 ; TEST 8
 define void @test8_helper() {
   %ptr0 = tail call i32* @unknown()
   %ptr1 = tail call align 4 i32* @unknown()

llvm/test/Transforms/FunctionAttrs/liveness.ll

 ; RUN: opt -attributor --attributor-disable=false -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
 
 declare i32 @foo_noreturn() noreturn
 
 declare i32 @bar() nosync readnone
 
+; This internal function has no live call sites, so all its BBs are considered dead,
+; and nothing should be deduced for it.
+
+; CHECK: define internal i32 @dead_internal_func(i32 %0)
+define internal i32 @dead_internal_func(i32 %0) {
+  %2 = icmp slt i32 %0, 1
+  br i1 %2, label %3, label %5
+
+; <label>:3:                                      ; preds = %5, %1
+  %4 = phi i32 [ 1, %1 ], [ %8, %5 ]
+  ret i32 %4
+
+; <label>:5:                                      ; preds = %1, %5
+  %6 = phi i32 [ %9, %5 ], [ 1, %1 ]
+  %7 = phi i32 [ %8, %5 ], [ 1, %1 ]
+  %8 = mul nsw i32 %6, %7
+  %9 = add nuw nsw i32 %6, 1
+  %10 = icmp eq i32 %6, %0
+  br i1 %10, label %3, label %5
+}
+
 ; CHECK: Function Attrs: nofree norecurse nounwind uwtable willreturn
 define i32 @volatile_load(i32*) norecurse nounwind uwtable {
   %2 = load volatile i32, i32* %0, align 4
   ret i32 %2
 }
 
 ; CHECK: Function Attrs: nofree norecurse nosync nounwind uwtable willreturn
 ; CHECK-NEXT: define internal i32 @internal_load(i32* nonnull %0)
 define internal i32 @internal_load(i32*) norecurse nounwind uwtable {
   %2 = load i32, i32* %0, align 4
   ret i32 %2
 }
+
 ; 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* nonnull %ptr1, i32* %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* nonnull %ptr1)
   call void @no_return_call()
   ; CHECK: call void @no_return_call()
   ; CHECK-NEXT: unreachable
+  call i32 @dead_internal_func(i32 10)
+  ; CHECK call i32 undef(i32 10)
   %cmp = icmp eq i32 %a, 0
   br i1 %cmp, label %cond.true, label %cond.false
 
 cond.true:                                        ; preds = %entry
   call i32 @internal_load(i32* %ptr2)
   ; CHECK: call i32 @internal_load(i32* %ptr2)
   %load = call i32 @volatile_load(i32* %ptr1)
   call void @normal_call()

 entry:
   %cmp = icmp eq i32 %a, 0
   br i1 %cmp, label %cond.true, label %cond.false
 
 cond.true:                                        ; preds = %entry
   call void @no_return_call()
   ; CHECK: call void @no_return_call()
   ; CHECK-NEXT: unreachable
+  call i32 @dead_internal_func(i32 10)
+  ; CHECK call i32 undef(i32 10)
   %call = call i32 @foo()
   br label %cond.end
 
 cond.false:                                       ; preds = %entry
   call void @no_return_call()
   ; CHECK: call void @no_return_call()
   ; CHECK-NEXT: unreachable
+  call i32 @dead_internal_func(i32 10)
+  ; CHECK call i32 undef(i32 10)
   %call1 = call i32 @bar()
   br label %cond.end
 
 cond.end:                                         ; preds = %cond.false, %cond.true
   %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ]
   ret i32 %cond
 }
 

 cond.else:                                                ; preds = %cond.elseif
   %7 = tail call i32 @foo()
   br label %cond.end
 
 cond.end:                                               ; preds = %cond.if, %cond.else, %cond.elseif
   %8 = phi i32 [ %1, %cond.elseif ], [ 0, %cond.else ], [ 0, %cond.if ]
   ret i32 %8
 }
+
+; SCC test
+;
+; char a1 __attribute__((aligned(8)));
+; char a2 __attribute__((aligned(16)));
+;
+; char* f1(char* a ){
+;     return a?a:f2(&a1);
+; }
+; char* f2(char* a){
+;     return a?f1(a):f3(&a2);
+; }
+;
+; char* f3(char* a){
+;     return a?&a1: f1(&a2);
+; }
+
+@a1 = common global i8 0, align 8
+@a2 = common global i8 0, align 16
+
+define internal i8* @f1(i8* readnone %0) local_unnamed_addr #0 {
+; ATTRIBUTOR: define internal i8* @f1(i8* readnone %0)
+  %2 = icmp eq i8* %0, null
+  br i1 %2, label %3, label %5
+
+; <label>:3:                                      ; preds = %1
+; ATTRIBUTOR: %4 = tail call i8* undef(i8* nonnull align 8 @a1)
+  %4 = tail call i8* @f2(i8* nonnull @a1)
+  br label %5
+
+; <label>:5:                                      ; preds = %1, %3
+  %6 = phi i8* [ %4, %3 ], [ %0, %1 ]
+  ret i8* %6
+}
+
+define internal i8* @f2(i8* readnone %0) local_unnamed_addr #0 {
+; ATTRIBUTOR: define internal i8* @f2(i8* readnone %0)
+  %2 = icmp eq i8* %0, null
+  br i1 %2, label %5, label %3
+
+; <label>:3:                                      ; preds = %1
+
+; ATTRIBUTOR: %4 = tail call i8* undef(i8* nonnull align 8 %0)
+  %4 = tail call i8* @f1(i8* nonnull %0)
+  br label %7
+
+; <label>:5:                                      ; preds = %1
+; ATTRIBUTOR: %6 = tail call i8* undef(i8* nonnull align 16 @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
+}
+
+define internal i8* @f3(i8* readnone %0) local_unnamed_addr #0 {
+; ATTRIBUTOR: define internal i8* @f3(i8* readnone %0)
+  %2 = icmp eq i8* %0, null
+  br i1 %2, label %3, label %5
+
+; <label>:3:                                      ; preds = %1
+; ATTRIBUTOR: %4 = tail call i8* undef(i8* nonnull align 16 @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
+}

llvm/test/Transforms/FunctionAttrs/read_write_returned_arguments_scc.ll

if.end:                                           ; preds = %entry
   br label %return
 
 return:                                           ; preds = %if.end, %if.then
   %retval.0 = phi i32* [ %call5, %if.end ], [ %n0, %if.then ]
   ret i32* %retval.0
 }
 
 ; CHECK: Function Attrs: nofree nosync nounwind
-; CHECK-NEXT: define internal i32* @internal_ret1_rrw(i32* %r0, i32* returned %r1, i32* %w0)
+; CHECK-NEXT: define internal align 4 i32* @internal_ret1_rrw(i32* align 4 %r0, i32* returned align 4 %r1, i32* %w0)
 define internal i32* @internal_ret1_rrw(i32* %r0, i32* %r1, i32* %w0) {
 entry:
   %0 = load i32, i32* %r0, align 4
   %tobool = icmp ne i32 %0, 0
   br i1 %tobool, label %if.end, label %if.then
 
 if.then:                                          ; preds = %entry
   br label %return