[Attributor][Fix] AAHeapToStack and AAIsDead connection

[sstefan1]

Summary

Since AAHeapToStack is deleting mallocs/frees AAIsDead needs to be aware
of that. For now, AANoFree uses this to deduce nofree function attribute
when a call to free is deleted.

[jdoerfert]

I see where you are going and we need this, however I just fiddled around with the entire isAssumedDead stuff to make the helper methods aware of dead uses (and instructions). I will see how we can combine this best with H2S and report here, OK?

[sstefan1]

In D72562#1815742, @jdoerfert wrote:

I see where you are going and we need this, however I just fiddled around with the entire isAssumedDead stuff to make the helper methods aware of dead uses (and instructions). I will see how we can combine this best with H2S and report here, OK?

That's ok with me. Are these changes commited?

[baziotis]

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

1021–1024

I think it's good to update this comment if these changes are committed - any other relevant as well).

[jdoerfert]

This needs to be integrated with D73313. I suggest we ask H2M if we have a call explicitly if it assumes to remove it.

[sstefan1]

In D72562#1837865, @jdoerfert wrote:

This needs to be integrated with D73313.

I think there is no integration with D73313 since I only need to change AAIsDeadFunction::IsAssumedDead. If that is correct I think this doesn't depend on D73313.

Also, I'll drop the changes to the existing interfaces, e.g. CheckForAllXXX.

In D72562#1837865, @jdoerfert wrote:

I suggest we ask H2M if we have a call explicitly if it assumes to remove it.

That is kind of the current implementation, but I'll change it a bit so the changes to existing interfaces are not needed.

[sstefan1]

In D72562#1841417, @sstefan1 wrote:

In D72562#1837865, @jdoerfert wrote:

This needs to be integrated with D73313.

I think there is no integration with D73313 since I only need to change AAIsDeadFunction::IsAssumedDead. If that is correct I think this doesn't depend on D73313.

Also, I'll drop the changes to the existing interfaces, e.g. CheckForAllXXX.

In D72562#1837865, @jdoerfert wrote:

I suggest we ask H2M if we have a call explicitly if it assumes to remove it.

That is kind of the current implementation, but I'll change it a bit so the changes to existing interfaces are not needed.

I was wrong. Currently we ask h2s for all mallocs that are to be deleted and mark them and their respective free calls dead. However, for some attributes (e.g. h2s) we need a way to skip checking whether or not malloc is dead (that is, if h2s marked it to be deleted). Back then the best way to do this seemed to be CheckInstSeparately flag. Could you give another look at the implementation in this patch?

[jdoerfert]

In D72562#1847774, @sstefan1 wrote:

In D72562#1841417, @sstefan1 wrote:

In D72562#1837865, @jdoerfert wrote:

This needs to be integrated with D73313.

I think there is no integration with D73313 since I only need to change AAIsDeadFunction::IsAssumedDead. If that is correct I think this doesn't depend on D73313.

Also, I'll drop the changes to the existing interfaces, e.g. CheckForAllXXX.

In D72562#1837865, @jdoerfert wrote:

I suggest we ask H2M if we have a call explicitly if it assumes to remove it.

That is kind of the current implementation, but I'll change it a bit so the changes to existing interfaces are not needed.

I was wrong. Currently we ask h2s for all mallocs that are to be deleted and mark them and their respective free calls dead. However, for some attributes (e.g. h2s) we need a way to skip checking whether or not malloc is dead (that is, if h2s marked it to be deleted). Back then the best way to do this seemed to be CheckInstSeparately flag. Could you give another look at the implementation in this patch?

I was hoping that after D73313 we could have a check this in AAIsDeadCallSiteReturned. In the init and update we ask H2S (and later others) if they assume to remove the instruction, if so, we consider it dead.

[sstefan1]

I was hoping that after D73313 we could have a check this in AAIsDeadCallSiteReturned. In the init and update we ask H2S (and later others) if they assume to remove the instruction, if so, we consider it dead.

Sorry for the delay.
Ok, I think this makes much more sense now.

Can you do a rebase on D73313 & D73311? I'm having trouble applying the patches.

[jdoerfert]

In D72562#1857658, @sstefan1 wrote:

I was hoping that after D73313 we could have a check this in AAIsDeadCallSiteReturned. In the init and update we ask H2S (and later others) if they assume to remove the instruction, if so, we consider it dead.

Sorry for the delay.
Ok, I think this makes much more sense now.

Can you do a rebase on D73313 & D73311? I'm having trouble applying the patches.

Done, though I have some minor patches before them I'll commit tomorrow. If you find the time to review the two above I can commit the whole series ;)

[sstefan1]

Done, though I have some minor patches before them I'll commit tomorrow. If you find the time to review the two above I can commit the whole series ;)

Reviewed.
I'm sorry, but I won't be able to do any real work until the weekend.

[sstefan1]

Changing the implementation to use new fine-grained liveness helpers.

[jdoerfert]

This is basically what I was hoping for, thx for rebasing it on the new scheme. Some comments inlined.

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

2463

This is "assumed" information, correct? We should put it in the name (or Known if that is what it is)

llvm/lib/Transforms/IPO/Attributor.cpp

2915

Would it work the other way around, as well? Deleting them here not in H2S. If so it would remove the special case here and some code in H2S, right?

3067

Do not track dependences by default but manually register one in the conditional when H2S information is used.

---

the entire H2s thing should be in an scope like:

} else if (isa<CallBase>(CtxI)) {
<h2s>
}

to avoid calling it if we know its side effect free or not a call.

4929

I think we can just iterate over all of them with some helpers to keep the code simpler:

auto IsI = [I](Instruction *C) { return C == I; };
if (llvm::any_of(MallocCalls, IsI))
  ...
for (auto &It : FreesForMalloc)
  if (llvm::any_of(It.second, IsI))
    ...

wdyt?

7435

I would hope the existing single Attributor::isAssumedDead check would suffice. The problem is we will play whack-a-mole all over the place if we cannot "generalize" liveness queries.

Can you explain why it's not. What would it take to make it work with a single Attributor::isAssumedDead call here, moving the logic into Attributor::isAssumedDead.

[sstefan1]

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

2463

Makes sense.

llvm/lib/Transforms/IPO/Attributor.cpp

2915

I had this in mind, but I don't think it would work because isAssumedSideEffectFree() will be false.

3067

default tracking was leftover actually. Changes in max iterations should've been a red flag.

If I'm not wrong, everything in here should be a CallBase.

4929

Thanks for the suggestion. That indeed looks nicer :)

7435

Actually it works. I should've taken a closer look at IRPosition::value()...

[sstefan1]

addressing comments

[sstefan1]

small update

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

2915

I see. In that case, can you move the special logic into isAssumedSideEffectFree to cut down on the duplication and allow reuse later on?

3048

This is assumed information, correct? If so, we cannot indicate a fixpoint and we need to record a dependence if we use the information.

4921

if(IsMalloc)
  return llvm::any_of(MallocCalls, IsI);

[sstefan1]

llvm/lib/Transforms/IPO/Attributor.cpp

2915

I've given this some more thought. While it would indeed be nicer to delete H2S stuff here as well, I think that can't work. Consider this example from the tests:

define void @nofree_arg_only(i8* %p1, i8* %p2) {
  tail call void @free(i8* %p2)
  tail call void @nofree_func(i8* %p1)
  ret void
}

Here free() is neither nounwind nor readonly but would be considered side effect free because we made isAssumedSideEffectFree consider it that way. As a result, since it is void value, it is deleted. Although it shouldn't have been.

If you still think we can/should do it, let me know.

3048

Correct. Interestingly, though, it doesn't work without indicating fixpoint.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

2915

I did confuse you by putting the comment here, sorry. The code I want to move into isAssumedSideEffectFree is the code below, not the code here. By moving the logic from updateImpl into isAssumedSideEffectFree we should be able to remove the code here, that is what I should have said.

Here free() is neither nounwind nor readonly but would be considered side effect free because we made isAssumedSideEffectFree consider it that way.

I don't think this is what should happen. isAssumedSideEffectFree will ask H2S and H2S::isAssumedToBeDeleted() will return false which will cause the normal logic in isAssumedSideEffectFree to continue and conclude we don't know anything about free and we need to assume it has side effects.

3048

"Doesn't work" is a symptom not an explanation ;)

We cannot indicate an optimistic fixpoint based on assumed information. If the tests fail it needs to be investigated why. See my other comment though.

[sstefan1]

llvm/lib/Transforms/IPO/Attributor.cpp

2915

That was the case :). The quoted comment was explaining how things would go if I were to move the code from above into the isAssumedSideEffectFree.

I think that should work.

3048

This was a quick comment. Didn't have time to look into it more carefully. I'll take a closer look tomorrow.

[sstefan1]

small fix

[sstefan1]

llvm/lib/Transforms/IPO/Attributor.cpp

2915

Unfortunately, I have to go back to being against this idea as I've stumbled upon another problem...

define void @test3() {
  %1 = tail call noalias i8* @malloc(i64 4)
  tail call void @no_sync_func(i8* %1)
  tail call void @free(i8* %1)
  ret void
}

If isAssumedSideEffectFree() returned true the malloc would end up having live users in no_sync_func(). We need to skip checking areAllUsesAssumedDead for H2S stuff. I'm not sure if sticking with this would be worth it in the end.

3048

H2S stuff needed to be checked before the if statement below. In latter updates IsAssumedSideEffectFree is true but isAssumedSideEffectFree() returns false causing update to return CHANGED.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

2915

OK, but we have to avoid duplication of H2S related code (here the ismalloc/isfree query). Having AAIsDead delete the code also has some appeal to it.

What if we add a boolean that tracks if we replace the value and therefore do not need to look at the users. We would not need this change here as isAssumedSideEffectFree returns true then. We also don't need to delete in H2S anymore.

4910

if (BadMallocCalls.count(I))
  return false;

4921

if it is a malloc we don't need to check the free's below, right?

[sstefan1]

llvm/lib/Transforms/IPO/Attributor.cpp

2915

I've given this another try.

If we delegate the deletion to AAIsDead we need 2 runs of Attributor. As a result H2S does its job on the first run but only converts mallocs to allocas leaving malloc behind. On the second run, leftover malloc is again converted to alloca and then finally deleted leaving us with 2 allocas. Which is of course not good. The only thing that can be removed from here is isFreeCall check as it has no uses to be replaced with undef.

If we still want avoid deleting stuff in H2S, perhaps H2S needs a rework?
If that is the case I can abandon this and start looking in that direction, if possible. Otherwise, I don't think this is doable...

4910

This doesn't take frees into account.

4921

Right. I'll change this to your suggestion from above.

[sstefan1]

llvm/lib/Transforms/IPO/Attributor.cpp

2915

Another thing that might work is to pass the TargetLibraryInfo to wouldInstructionBeTriviallyDead which would remove the isMallocCall check here, but would end up calling deleteAfterManifest which should be ok since it won't add it if it already exists. Will have to give this a try tomorrow first.

[sstefan1]

small update.

[sstefan1]

ping

[jdoerfert]

Can we postpone this until we figured out how AAIsDead and AAUB are working together? We need to figure this out and decide how much interaction with AAIsDead we want, e.g., if a rerun is sufficient do we need to integrate it.

[sstefan1]

In D72562#1915623, @jdoerfert wrote:

Can we postpone this until we figured out how AAIsDead and AAUB are working together? We need to figure this out and decide how much interaction with AAIsDead we want, e.g., if a rerun is sufficient do we need to integrate it.

Sure, just wanted to check the status.

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

struct Attributor {
 
   /// Check \p Pred on all values potentially returned by the function
   /// associated with \p QueryingAA.
   ///
   /// This is the context insensitive version of the method above.
   bool checkForAllReturnedValues(const function_ref<bool(Value &)> &Pred,
                                  const AbstractAttribute &QueryingAA);
 
   /// Check \p Pred on all instructions with an opcode present in \p Opcodes.
   ///
   /// This method will evaluate \p Pred on all instructions with an opcode
   /// present in \p Opcode and return true if \p Pred holds on all of them.
   bool checkForAllInstructions(const function_ref<bool(Instruction &)> &Pred,
                                const AbstractAttribute &QueryingAA,
                                const ArrayRef<unsigned> &Opcodes,
                                bool CheckBBLivenessOnly = false);
 
   /// Check \p Pred on all call-like instructions (=CallBased derived).
   ///
   /// See checkForAllCallLikeInstructions(...) for more information.
struct AAHeapToStack : public StateWrapper<BooleanState, AbstractAttribute>,
   AAHeapToStack(const IRPosition &IRP) : IRPosition(IRP) {}
 
   /// Returns true if HeapToStack conversion is assumed to be possible.
   bool isAssumedHeapToStack() const { return getAssumed(); }
 
   /// Returns true if HeapToStack conversion is known to be possible.
   bool isKnownHeapToStack() const { return getKnown(); }
 
+  /// Returns true if instruction (malloc/free) is identified for deletion.
+  virtual bool isAssumedToBeDeleted(Attributor &A, Instruction *I) const;
+
   /// Return an IR position, see struct IRPosition.
   const IRPosition &getIRPosition() const { return *this; }
 
   /// Create an abstract attribute view for the position \p IRP.
   static AAHeapToStack &createForPosition(const IRPosition &IRP, Attributor &A);
 
   /// Unique ID (due to the unique address)
   static const char ID;

llvm/lib/Transforms/IPO/Attributor.cpp

 
 struct AANoFreeImpl : public AANoFree {
   AANoFreeImpl(const IRPosition &IRP) : AANoFree(IRP) {}
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     auto CheckForNoFree = [&](Instruction &I) {
       ImmutableCallSite ICS(&I);
+
       if (ICS.hasFnAttr(Attribute::NoFree))
         return true;
 
       const auto &NoFreeAA =
           A.getAAFor<AANoFree>(*this, IRPosition::callsite_function(ICS));
+
       return NoFreeAA.isAssumedNoFree();
     };
 
     if (!A.checkForAllCallLikeInstructions(CheckForNoFree, *this))
       return indicatePessimisticFixpoint();
     return ChangeStatus::UNCHANGED;
   }
 
if (!areAllUsesAssumedDead(A, getAssociatedValue()))
       return indicatePessimisticFixpoint();
     return ChangeStatus::UNCHANGED;
   }
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     Value &V = getAssociatedValue();
     if (auto *I = dyn_cast<Instruction>(&V)) {
+      const auto *TLI = A.getInfoCache().getTargetLibraryInfoForFunction(
+          *(I->getParent()->getParent()));
+
+      // These are Mallocs/Frees that are marked for deletion by H2S.
+      // No need to delete them after manifest (already deleted by H2S).
+      if (isMallocOrCallocLikeFn(I, TLI))
+        return ChangeStatus::CHANGED;
+
       // If we get here we basically know the users are all dead. We check if
       // isAssumedSideEffectFree returns true here again because it might not be
       // the case and only the users are dead but the instruction (=call) is
       // still needed.
       if (isAssumedSideEffectFree(A, I) && !isa<InvokeInst>(I)) {
         A.deleteAfterManifest(*I);
         return ChangeStatus::CHANGED;
       }
void initialize(Attributor &A) override {
 
     // We track this separately as a secondary state.
     IsAssumedSideEffectFree = isAssumedSideEffectFree(A, getCtxI());
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     ChangeStatus Changed = ChangeStatus::UNCHANGED;
-    if (IsAssumedSideEffectFree && !isAssumedSideEffectFree(A, getCtxI())) {
+    Instruction *CtxI = getCtxI();
+
+    const IRPosition &IRPFunction =
+        IRPosition::function(*(CtxI->getParent()->getParent()));
+
+    // Check for any mallocs/frees that will be deleted (dead).
+    const auto &HeapToStackAA = A.getAAFor<AAHeapToStack>(
+        *this, IRPFunction, /* TrackDepencence */ false);
+
+    if (HeapToStackAA.isAssumedToBeDeleted(A, CtxI)) {
+      // So isAssumedDead() can actually return true.
+      IsAssumedSideEffectFree = true;
+      A.recordDependence(HeapToStackAA, *this, DepClassTy::OPTIONAL);
+      return Changed;
+    }
+
+    if (IsAssumedSideEffectFree && !isAssumedSideEffectFree(A, CtxI)) {
       IsAssumedSideEffectFree = false;
       Changed = ChangeStatus::CHANGED;
     }
 
     if (!areAllUsesAssumedDead(A, getAssociatedValue()))
       return indicatePessimisticFixpoint();
     return Changed;
   }
 
   /// See AbstractAttribute::manifest(...).
   ChangeStatus manifest(Attributor &A) override {
     if (auto *CI = dyn_cast<CallInst>(&getAssociatedValue()))
       if (CI->isMustTailCall())
         return ChangeStatus::UNCHANGED;
     return AAIsDeadFloating::manifest(A);
   }
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {
     if (IsAssumedSideEffectFree)
       STATS_DECLTRACK_CSRET_ATTR(IsDead)
     else
       STATS_DECLTRACK_CSRET_ATTR(UnusedResult)
   }
struct AAHeapToStackImpl : public AAHeapToStack {
 
   /// Collection of malloc calls that cannot be converted.
   DenseSet<const Instruction *> BadMallocCalls;
 
   /// A map for each malloc call to the set of associated free calls.
   DenseMap<Instruction *, SmallPtrSet<Instruction *, 4>> FreesForMalloc;
 
   ChangeStatus updateImpl(Attributor &A) override;
+
+  // Checks if any malloc/frees is marked for deletion.
+  bool isAssumedToBeDeleted(Attributor &A, Instruction *I) const override {
+    if (!getAssumed())
+      return false;
+
+    const auto *TLI = A.getInfoCache().getTargetLibraryInfoForFunction(
+        *(I->getParent()->getParent()));
+
+    bool IsMalloc = isMallocOrCallocLikeFn(I, TLI);
+    if (!IsMalloc && !isFreeCall(I, TLI))
+      return false;
+
+    auto IsI = [I](Instruction *C) { return C == I; };
+    if (IsMalloc)
+      return llvm::any_of(MallocCalls, IsI);
+
+    for (auto &It : FreesForMalloc)
+      if (llvm::any_of(It.second, IsI))
+        return true;
+
+    return false;
+  }
 };
 
 ChangeStatus AAHeapToStackImpl::updateImpl(Attributor &A) {
   const Function *F = getAssociatedFunction();
   const auto *TLI = A.getInfoCache().getTargetLibraryInfoForFunction(*F);
 
   MustBeExecutedContextExplorer &Explorer =
       A.getInfoCache().getMustBeExecutedContextExplorer();
 
for (Instruction *I : OpcodeInstMap[Opcode]) {
 
       if (!Pred(*I))
         return false;
     }
   }
   return true;
 }
 
 bool Attributor::checkForAllInstructions(
     const llvm::function_ref<bool(Instruction &)> &Pred,
     const AbstractAttribute &QueryingAA, const ArrayRef<unsigned> &Opcodes,
     bool CheckBBLivenessOnly) {
 
   const IRPosition &IRP = QueryingAA.getIRPosition();
   // Since we need to provide instructions we have to have an exact definition.
   const Function *AssociatedFunction = IRP.getAssociatedFunction();
   if (!AssociatedFunction)

llvm/test/Transforms/Attributor/ArgumentPromotion/aggregate-promote.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
-; RUN: opt -disable-output -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=1 < %s
+; RUN: opt -disable-output -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 < %s
 
 %T = type { i32, i32, i32, i32 }
 @G = constant %T { i32 0, i32 0, i32 17, i32 25 }
 
 define internal i32 @test(%T* %p) {
 ; CHECK-LABEL: define {{[^@]+}}@test
 ; CHECK-SAME: (i32 [[P_0_2_VAL:%.*]], i32 [[P_0_3_VAL:%.*]])
 ; CHECK-NEXT:  entry:

llvm/test/Transforms/Attributor/ArgumentPromotion/chained.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
-; RUN: opt -S -passes='attributor' -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=1 < %s | FileCheck %s
+; RUN: opt -S -passes='attributor' -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 < %s | FileCheck %s
 
 @G1 = constant i32 0
 @G2 = constant i32* @G1
 
 define internal i32 @test(i32** %x) {
 ; CHECK-LABEL: define {{[^@]+}}@test
 ; CHECK-SAME: (i32** nocapture nofree nonnull readonly align 8 dereferenceable(8) [[X:%.*]])
 ; CHECK-NEXT:  entry:

llvm/test/Transforms/Attributor/ArgumentPromotion/musttail.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
-; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=1 < %s | FileCheck %s
+; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 < %s | FileCheck %s
 ; PR36543
 
 ; Don't promote arguments of musttail callee
 
 %T = type { i32, i32, i32, i32 }
 
 define internal i32 @test(%T* %p) {
 ; CHECK-LABEL: define {{[^@]+}}@test

llvm/test/Transforms/Attributor/IPConstantProp/PR26044.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
-; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=1 < %s | FileCheck %s
+; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 < %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @fn2(i32* %P) {
 ; CHECK-LABEL: define {{[^@]+}}@fn2
 ; CHECK-SAME: (i32* nocapture nofree writeonly [[P:%.*]])
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[IF_END:%.*]]

llvm/test/Transforms/Attributor/heap_to_stack.ll

define void @test2() {
   ; CHECK-NEXT: @sync_func(i8* %1)
   tail call void @sync_func(i8* %1)
   tail call void @free(i8* %1)
   ret void
 }
 
 ; TEST 3 - 1 malloc, 1 free
 
+; CHECK: Function Attrs: nofree nosync willreturn
+; CHECK-NEXT: define void @test3
 define void @test3() {
   %1 = tail call noalias i8* @malloc(i64 4)
   ; CHECK: %1 = alloca i8, i64 4
   ; CHECK-NEXT: @no_sync_func(i8* noalias nocapture nofree %1)
   tail call void @no_sync_func(i8* %1)
   ; CHECK-NOT: @free(i8* %1)
   tail call void @free(i8* %1)
   ret void
 }
 
 define void @test3a(i8* %p) {
   %1 = tail call noalias i8* @malloc(i64 4)
   ; CHECK: %1 = alloca i8, i64 4
   ; CHECK-NEXT: tail call void @nofree_arg_only
   tail call void @nofree_arg_only(i8* %1, i8* %p)
   ; CHECK-NOT: @free(i8* %1)
   tail call void @free(i8* %1)
   ret void
 }
 
 declare noalias i8* @calloc(i64, i64)
 
+; CHECK: Function Attrs: nofree nosync willreturn
+; CHECK-NEXT: define void @test0
 define void @test0() {
   %1 = tail call noalias i8* @calloc(i64 2, i64 4)
   ; CHECK: %1 = alloca i8, i64 8
   ; CHECK-NEXT: %calloc_bc = bitcast i8* %1 to i8*
   ; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* %calloc_bc, i8 0, i64 8, i1 false)
   ; CHECK-NEXT: @no_sync_func(i8* noalias nocapture nofree %1)
   tail call void @no_sync_func(i8* %1)
   ; CHECK-NOT: @free(i8* %1)
   tail call void @free(i8* %1)
   ret void
 }
 
-; TEST 4 
+; TEST 4
+
+; CHECK: Function Attrs: nofree nosync willreturn
+; CHECK-NEXT: define void @test4
 define void @test4() {
   %1 = tail call noalias i8* @malloc(i64 4)
   ; CHECK: %1 = alloca i8, i64 4
   ; CHECK-NEXT: @nofree_func(i8* noalias nocapture nofree %1)
   tail call void @nofree_func(i8* %1)
   ret void
 }
 
5:                                                ; preds = %1
   br label %6
 
 6:                                                ; preds = %5, %4
   ret void
 }
 
 ; TEST 6 - all exit paths have a call to free
 
+; CHECK: Function Attrs: nofree nosync
+; CHECK-NEXT: define void @test6
 define void @test6(i32) {
   %2 = tail call noalias i8* @malloc(i64 4)
   ; CHECK: %2 = alloca i8, i64 4
   ; CHECK-NEXT: icmp eq i32 %0, 0
   %3 = icmp eq i32 %0, 0
   br i1 %3, label %5, label %4
 
 4:                                                ; preds = %1
define void @test9() {
   tail call void @foo_nounw(i32* %2)
   ; CHECK: @free(i8* %1)
   tail call void @free(i8* %1)
   ret void
 }
 
 ; TEST 10 - 1 malloc, 1 free
 
+; CHECK: Function Attrs: nofree nosync willreturn
+; CHECK-NEXT: define i32 @test10
 define i32 @test10() {
   %1 = tail call noalias i8* @malloc(i64 4)
   ; CHECK: %1 = alloca i8, i64 4
   ; CHECK-NEXT: @no_sync_func(i8* noalias nocapture nofree %1)
   tail call void @no_sync_func(i8* %1)
   %2 = bitcast i8* %1 to i32*
   store i32 10, i32* %2
   %3 = load i32, i32* %2
   ; CHECK-NOT: @free(i8* %1)
   tail call void @free(i8* %1)
   ret i32 %3
 }
 
+; CHECK: Function Attrs: willreturn
+; CHECK-NEXT: define i32 @test_lifetime
 define i32 @test_lifetime() {
   %1 = tail call noalias i8* @malloc(i64 4)
   ; CHECK: %1 = alloca i8, i64 4
   ; CHECK-NEXT: @no_sync_func(i8* noalias nocapture nofree %1)
   tail call void @no_sync_func(i8* %1)
   call void @llvm.lifetime.start.p0i8(i64 4, i8* %1)
   %2 = bitcast i8* %1 to i32*
   store i32 10, i32* %2
   %3 = load i32, i32* %2
   ; CHECK-NOT: @free(i8* %1)
   tail call void @free(i8* %1)
   ret i32 %3
 }
 
-; TEST 11 
+; TEST 11
 
+; CHECK: Function Attrs: nounwind willreturn
+; CHECK-NEXT: define void @test11
 define void @test11() {
   %1 = tail call noalias i8* @malloc(i64 4)
-  ; CHECK: test11
   ; CHECK-NEXT: alloc
   ; CHECK-NEXT: @sync_will_return(i8* %1)
   tail call void @sync_will_return(i8* %1)
   tail call void @free(i8* %1)
   ret void
 }
 
 ; TEST 12
+
+; CHECK: Function Attrs: nofree nosync nounwind
+; CHECK-NEXT: define i32 @irreducible_cfg
 define i32 @irreducible_cfg(i32 %0) {
   ; CHECK: alloca i8, i64 4
   ; CHECK-NEXT: %3 = bitcast
   %2 = call noalias i8* @malloc(i64 4)
   %3 = bitcast i8* %2 to i32*
   store i32 10, i32* %3, align 4
   %4 = icmp eq i32 %0, 1
   br i1 %4, label %5, label %7
15:                                               ; preds = %8
   %16 = load i32, i32* %3, align 4
   %17 = bitcast i32* %3 to i8*
   call void @free(i8* %17)
   %18 = load i32, i32* %3, align 4
   ret i32 %18
 }
 
 
+; CHECK: Function Attrs: nofree nosync nounwind
+; CHECK-NEXT: define i32 @malloc_in_loop
 define i32 @malloc_in_loop(i32 %0) {
   %2 = alloca i32, align 4
   %3 = alloca i32*, align 8
   store i32 %0, i32* %2, align 4
   br label %4
 
 4:                                                ; preds = %8, %1
   %5 = load i32, i32* %2, align 4
define void @test15(i64 %S) {
   %1 = tail call noalias i8* @malloc(i64 %S)
   ; CHECK-NEXT: @no_sync_func(i8* noalias nofree %1)
   tail call void @no_sync_func(i8* %1)
   ; CHECK-NEXT: @free(i8* noalias %1)
   tail call void @free(i8* %1)
   ret void
 }
 
+; CHECK: Function Attrs: nofree nosync willreturn
+; CHECK-NEXT: define void @test16a
 define void @test16a(i8 %v, i8** %P) {
   ; CHECK: %1 = alloca
   %1 = tail call noalias i8* @malloc(i64 4)
   ; CHECK-NEXT: store i8 %v, i8* %1
   store i8 %v, i8* %1
   ; CHECK-NEXT: @no_sync_func(i8* noalias nocapture nofree %1)
   tail call void @no_sync_func(i8* %1)
   ; CHECK-NOT: @free(i8* %1)
   tail call void @free(i8* %1)
   ret void
 }
 
 define void @test16b(i8 %v, i8** %P) {
   ; CHECK: %1 = tail call noalias i8* @malloc(i64 4)
   %1 = tail call noalias i8* @malloc(i64 4)
   ; CHECK-NEXT: store i8* %1, i8** %P
   store i8* %1, i8** %P
   ; CHECK-NEXT: @no_sync_func(i8* nocapture nofree %1)
   tail call void @no_sync_func(i8* %1)
   ; CHECK-NEXT: @free(i8* %1)
   tail call void @free(i8* %1)
   ret void
 }
 
+; CHECK: Function Attrs: nofree nosync nounwind willreturn
+; CHECK-NEXT: define void @test16c
 define void @test16c(i8 %v, i8** %P) {
   ; CHECK: %1 = alloca
   %1 = tail call noalias i8* @malloc(i64 4)
   ; CHECK-NEXT: store i8* %1, i8** %P
   store i8* %1, i8** %P
   ; CHECK-NEXT: @no_sync_func(i8* nocapture nofree %1)
   tail call void @no_sync_func(i8* %1) nounwind
   ; CHECK-NOT: @free

llvm/test/Transforms/Attributor/liveness_chains.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
-; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=1 -S < %s | FileCheck %s
-; RUN: opt -attributor-cgscc --attributor-disable=false -attributor-annotate-decl-cs -attributor-max-iterations=1 -S < %s | FileCheck %s
-; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=1 -S < %s | FileCheck %s
-; RUN: opt -passes='attributor-cgscc' --attributor-disable=false -attributor-annotate-decl-cs -attributor-max-iterations=1 -S < %s | FileCheck %s
+; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=2 -S < %s | FileCheck %s
+; RUN: opt -attributor-cgscc --attributor-disable=false -attributor-annotate-decl-cs -attributor-max-iterations=2 -S < %s | FileCheck %s
+; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=2 -S < %s | FileCheck %s
+; RUN: opt -passes='attributor-cgscc' --attributor-disable=false -attributor-annotate-decl-cs -attributor-max-iterations=2 -S < %s | FileCheck %s
 
 ; Make sure we need a single iteration to determine the chains are dead/alive.
 
 declare i32 @source() nounwind readonly
 
 define i32 @chain_dead(i32 %arg) {
 ; CHECK-LABEL: define {{[^@]+}}@chain_dead
 ; CHECK-SAME: (i32 [[ARG:%.*]])