[Attributor] Deduce "willreturn" function attribute

[uenoku]

Summary

Deduce the "willreturn" attribute for functions.

For now, intrinsics are not willreturn. More annotation will be done in another patch.

[uenoku]

The current algorithm can deduce only for very simple cases.

• A function doesn't have any loop.
• A function doesn't have any recursion.

I'll work on allowing some loops next.

[jdoerfert]

Can you clang format the code?

What about the test changes?

llvm/lib/Transforms/IPO/Attributor.cpp

1037

Please create an AAWillReturn interface in the header so it is easier to query the attribute.

1095

for (BasicBlock *SuccBB : successors(BB)) {

1098

No braces around return

[uenoku]

Address comments and add test change.

[uenoku]

Can you clang format the code?

I always clang format before submitting a patch.
Is there something wrong?

[jdoerfert]

In D63046#1535452, @uenoku wrote:

Can you clang format the code?

I always clang format before submitting a patch.
Is there something wrong?

I forgot why I thought it was not formatted. Forget that comment.

Last comments wrt class placement.

llvm/lib/Transforms/IPO/Attributor.cpp

1037

Now I would split this again into:
struct AAWillReturn : public AbstractAttribute that lives in the header
and
struct AAWillReturnImpl : public AAWillReturn, BooleanState that lives here.
The idea is that the AAWillReturn is exposed to everybody and AAWillReturnImpl has the code shared between all AAWillReturn deductions. It is, for example, reasonable to have a call site deduction at some point.

1045

assumed and known mixed up in the comments.

1056

I think it might make sense to use the same spelling in the assumed case as we use for the attr.

[uenoku]

Address comments

[jdoerfert]

Declare isKnownWillReturn and isAssumedWillReturn in the base class. Then place the base class in the header. Otherwise, LGTM.

(Can you also make the dependences explicit so I know when I can commit these things, use the edit related revisions button).

[uenoku]

Add declarations in base class.

[nicholas]

The current algorithm can deduce only for very simple cases.

• A function doesn't have any loop.
• A function doesn't have any recursion.

What about functions that exit the program, throw an exception, or longjmp?

llvm/lib/Transforms/IPO/Attributor.cpp

1109

Loop is commonly assumed to mean "natural loop", where there is one block (the header) which dominates the other blocks in the loop (the loop body). What you're looking for here is a more general thing called a cycle (equivalent to looking for a backedge). That also explains why you need your own function and can't reuse LoopInfo.

1115–1120

FYI, with effort, this could be pushed to be more efficient. df_iterator maintains its own copy of Visited, and it does its own scan over the successors of the block, neither of which need to be done twice. Unfortunately the fix is not entirely simple.

[nicholas]

In D63046#1535804, @nicholas wrote:

The current algorithm can deduce only for very simple cases.

• A function doesn't have any loop.
• A function doesn't have any recursion.

What about functions that exit the program, throw an exception, or longjmp?

I know I just posted, but I think I figured out the right rule. The rule you want is a) doesn't have a cycle b) all calls have willreturn. A function with no calls (and no cycles) can have willreturn, and a function that calls only willreturn functions (and no cycles) can have willreturn. That's assuming you don't mind a function being both willreturn and noreturn at the same time (a function that ends in unreachable). I think we just accept that, there's no point trying to prove any code free from undefined behaviour.

If I'm right, this patch doesn't need to depend on norecurse.

[jdoerfert]

In D63046#1535808, @nicholas wrote:

In D63046#1535804, @nicholas wrote:

The current algorithm can deduce only for very simple cases.

• A function doesn't have any loop.
• A function doesn't have any recursion.

What about functions that exit the program, throw an exception, or longjmp?

That was an oversight in the comment but not the code, I think. There are tests for calls and exceptions. The former may prevent willreturn the latter doesn't (as of D62801). This way, willreturn is orthogonal to nothrow.

I know I just posted, but I think I figured out the right rule. The rule you want is a) doesn't have a cycle b) all calls have willreturn. A function with no calls (and no cycles) can have willreturn, and a function that calls only willreturn functions (and no cycles) can have willreturn. That's assuming you don't mind a function being both willreturn and noreturn at the same time (a function that ends in unreachable). I think we just accept that, there's no point trying to prove any code free from undefined behaviour.

If I'm right, this patch doesn't need to depend on norecurse.

Strictly speaking, it doesn't. But for now, that makes it much simpler. If you only make sure calls are optimistically willreturn you get willreturn for a potential endless recursion. That is, a function that might, depending on the input, recurse forever or not. Now, norecurse is actually "too strong" but that is fine for now.

llvm/lib/Transforms/IPO/Attributor.cpp

1115–1120

Let's not optimize it preemptively. I'll run it through LLVM-TS and SPEC2006 before I commit it anyway, if there is a change in compile or runtime I'll report it back.

[uenoku]

In D63046#1535804, @nicholas wrote:

The current algorithm can deduce only for very simple cases.

• A function doesn't have any loop.
• A function doesn't have any recursion.

What about functions that exit the program, throw an exception, or longjmp?

• longjump shouldn't be "willreturn" but I've found that the current implementation might deduce "willreturn" (llvm.eh.sjlj.longjmp is intrinsic but it has noreturn).

I'll fix it to check noreturn.

llvm/lib/Transforms/IPO/Attributor.cpp

1109

Loop is commonly assumed to mean "natural loop", where there is one block (the header) which dominates the other blocks in the loop (the loop body). What you're looking for here is a more general thing called a cycle (equivalent to looking for a backedge).

OK, I rename it.

That also explains why you need your own function and can't reuse LoopInfo.

LoopInfo doesn't contain an irreducible loop (maybe endless loop) so I check the cycle manually for now.
I'm going to use LoopInfo to check (i) whether a function has an irreducible loop and (ii) whether all loops are guaranteed to terminate.

[uenoku]

• Rename "Loop" to "Cycle".
• Prohibit noreturn intrinsic (ex. longjump) and add longjump test.
• Check AANoReturnFunction

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

1109

I'm going to use LoopInfo to check (i) whether a function has an irreducible loop and (ii) whether all loops are guaranteed to terminate.

Keep it this way for now, LoopInfo will currently not simplify things

[uenoku]

Fix patch.

[jdoerfert]

@nicholas If you want to discuss any of this further, please say so.

llvm/lib/Transforms/IPO/Attributor.cpp

1037

Could you move this struct to the header file please?

1177

I'd argue: Either do not check for noreturn at all, which I would have initially thought we do, or do it explicitly for this function but not the callees. That way, the function which is noreturn is not willreturn and callers will no be able to get willreturn. However, once willreturn is deduced, noreturn should be irrelevant (IMHO), maybe contradicting.

llvm/test/Transforms/FunctionAttrs/will-return.ll

1

since you renamed the attribute you should think about renaming the file as well ;)

[uenoku]

Address comments

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

1177

I agree with you.

[nicholas]

llvm/lib/Transforms/IPO/Attributor.cpp

1115–1120

I doubt human-written code will trigger slow compile times in this path, but I bet it could happen with machine generated code. Just leave a TODO noting how it could be more efficient.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

1115–1120

Agreed, to all of it. We will most likely see various "compile time problems" once we add more and more functionality (and actually turn it on), so keeping a record of fixes is very useful. @uenoku Can you add such a comment.

[uenoku]

Add TODO.

[uenoku]

Remove nofree.

[uenoku]

Use enum attribute.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

492

I think we should be cautious and not mark intrinsics as willreturn in the update method but instead do it explicitly as such in the Intrinsics.td file.

Also, drop the braces around single statements.

llvm/test/Transforms/FunctionAttrs/willreturn.ll

2 ↗

(On Diff #206597)

Explicitly activate the attributor.

[uenoku]

Annotate "willreturn" in Intrinsics.td and add related test changes.

[uenoku]

@jdoerfert
In the current implementation, updateImpl depends on AANoRecurseFunction. However, norecurse patch is abandoned and what should I do?

[jdoerfert]

In D63046#1580744, @uenoku wrote:

@jdoerfert
In the current implementation, updateImpl depends on AANoRecurseFunction. However, norecurse patch is abandoned and what should I do?

Take the AANoRecurse abstract attribute interface (no implementation) and add it to this patch. That will not improve the results but will make it work once we derive it.

[uenoku]

Rebase and add NoRecurse interface. check-all passed.

[uenoku]

For some intrinsics, I can not judge whether it is allowed to mark willreturn. I want to hear an opinion.

• Standard C libray: especially memcpy, memmove, memset

[jdoerfert]

In D63046#1583471, @uenoku wrote:

For some intrinsics, I can not judge whether it is allowed to mark willreturn. I want to hear an opinion.

• Standard C libray: especially memcpy, memmove, memset

Can we do the following:

• Commit this with conservative intrinsic handling. That is, without all the intrinsics marking stuff.
• Open another patch for the marking stuff as you have it now in here.

Basically, split the patch in two and commit the first part assuming the comments in (https://reviews.llvm.org/D63046#1572140) have been addressed.

To answer your question: memcpy, memmove, memset are willreturn

[uenoku]

In D63046#1583582, @jdoerfert wrote:

In D63046#1583471, @uenoku wrote:

For some intrinsics, I can not judge whether it is allowed to mark willreturn. I want to hear an opinion.

• Standard C libray: especially memcpy, memmove, memset

Can we do the following:

• Commit this with conservative intrinsic handling. That is, without all the intrinsics marking stuff.
• Open another patch for the marking stuff as you have it now in here.

Basically, split the patch in two and commit the first part assuming the comments in (https://reviews.llvm.org/D63046#1572140) have been addressed.

To answer your question: memcpy, memmove, memset are willreturn

OK, I'll split a patch for mem*or other stuff.
In my opinion, the annotation in this patch is enough conservative (I annotated to arithmetic function and debugging function). Is there any problem with this annotation?

[uenoku]

Remove annotation for now.

[uenoku]

Rebase.

[nikic]

llvm/trunk/lib/Transforms/IPO/Attributor.cpp

1284 ↗

(On Diff #210334)

In line with isGuaranteedToTransferExecutionToSuccessor(), isn't it also necessary to check for volatile memory operations, which may trap?

[uenoku]

llvm/trunk/lib/Transforms/IPO/Attributor.cpp

1284 ↗

(On Diff #210334)

In D53184, it is clarified in LangRef that volatile memory operations wouldn't trap. Therefore, in my opinion, we need to fix rather isGuaranteedToTransferExecutionToSuccessor, isn't it?

[nikic]

llvm/trunk/lib/Transforms/IPO/Attributor.cpp

1284 ↗

(On Diff #210334)

Thanks for pointing that out! In that case indeed the implementation of guaranteed-to-transfer should be changed. Especially the paragraph

The compiler may assume execution will continue after a volatile operation,
so operations which modify memory or may have undefined behavior can be
hoisted past a volatile operation.

seems pretty clear on this point -- this not only precludes trapping, but also a volatile MMIO operation that hangs forever.

[uenoku]

llvm/trunk/lib/Transforms/IPO/Attributor.cpp

1284 ↗

(On Diff #210334)

Btw AtomicCmpXchgInst are checked in isGuaranteedToTransfer.. whether the instruction is volatile. However, I think in some cases AtomicCmpXchgInst never return so we need to fix also isGuaranteedToTransfer.. in this point. For the same reason, AtomicCmpXchgInst should be checked in willreturn deduction.

[uenoku]

llvm/trunk/lib/Transforms/IPO/Attributor.cpp

1284 ↗

(On Diff #210334)

Above was a misunderstanding of me about AtomicCmpXchgInst. Please ignore.

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 which walk the call-graph
 // deducing and/or propagating attributes along the way. 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/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/IR/Argument.h"
for (Instruction *RI : OpcodeInstMap[Instruction::Ret]) {
                                ReturnedValues);
     }
   }
 
   /// See AbstractAttribute::manifest(...).
   virtual ChangeStatus manifest(Attributor &A) override;
 
   /// See AbstractAttribute::getState(...).
   virtual AbstractState &getState() override { return *this; }
 
   /// See AbstractAttribute::getState(...).
   virtual const AbstractState &getState() const override { return *this; }
 
   /// See AbstractAttribute::getManifestPosition().
   virtual ManifestPosition getManifestPosition() const override {
     return MP_ARGUMENT;
   }
if (RVAA && RVAA->getState().isValidState()) {
     }
   }
 
   // Fallthrough if we failed to keep the no-capture state.
   indicatePessimisticFixpoint();
   return ChangeStatus::CHANGED;
 }
 
+/// ------------------------ Will-Return Attributes ----------------------------
+struct AAWillReturn : public AbstractAttribute, BooleanState {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AAWillReturn(Function &F, InformationCache &InfoCache)
+      : AbstractAttribute(F, InfoCache) {}
+
+  /// Return true if "willreturn" is assumed.
+  bool isKnownWillReturn() const { return getKnown(); }
+
+  /// Return true if "willreturn" is known.
+  bool isAssumedWillReturn() const { return getAssumed(); }
+
+  /// See AbstractAttribute::getState(...).
+  virtual AbstractState &getState() override { return *this; }
+
+  /// See AbstractAttribute::getState(...).
+  virtual const AbstractState &getState() const override { return *this; }
+
+  /// See AbstractAttribute::getAsStr()
+  virtual const std::string getAsStr() const override {
+    return getAssumed() ? "will-return" : "may-noreturn";
+  }
+
+  /// Return the deduced attributes in \p Attrs.
+  virtual void
+  getDeducedAttributes(SmallVectorImpl<Attribute> &Attrs) const override {
+    LLVMContext &Ctx = AnchoredVal.getContext();
+    Attrs.emplace_back(Attribute::get(Ctx, "willreturn"));
+  }
+
+  /// See AbstractAttribute::getAttrKind()
+  virtual Attribute::AttrKind getAttrKind() const override {
+    return Attribute::None;
+  }
+
+  /// The identifier used by the Attributor for this class of attributes.
+  /// FIXME: I use Attribute::None + 2 for now.
+  static constexpr Attribute::AttrKind ID =
+      Attribute::AttrKind(Attribute::None + 2);
+};
+
+struct AAWillReturnFunction final : AAWillReturn {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AAWillReturnFunction(Function &F, InformationCache &InfoCache)
+      : AAWillReturn(F, InfoCache) {}
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_FUNCTION;
+  }
+
+  /// See AbstractAttribute::initialize(...).
+  virtual void initialize(Attributor &A) override;
+
+  /// See AbstractAttribute::updateImpl(...).
+  virtual ChangeStatus updateImpl(Attributor &A) override;
+};
+
+// Helper function that checks whether a function has any loop.
+bool containsLoop(Function &F) {
+  SmallPtrSet<BasicBlock *, 32> Visited;
+
+  // Traverse BB by dfs and check whether successor is already visited.
+  for (BasicBlock *BB : depth_first(&F)) {
+    Visited.insert(BB);
+    for (auto *SuccBB : successors(BB)) {
+      if (Visited.count(SuccBB))
+        return true;
+    }
+  }
+  return false;
+}
+
+// Helper function that checks the function have a loop which might become an
+// endless loop
+// FIXME: Any loop is regarded as endless loop for now.
+//        We have to allow some patterns.
+bool containsPossiblyEndlessLoop(Function &F) { return containsLoop(F); }
+
+void AAWillReturnFunction::initialize(Attributor &A) {
+  Function &F = getAnchorScope();
+  if (containsPossiblyEndlessLoop(F))
+    indicatePessimisticFixpoint();
+}
+
+ChangeStatus AAWillReturnFunction::updateImpl(Attributor &A) {
+  Function &F = getAnchorScope();
+
+  // The map from instruction opcodes to those instructions in the function.
+  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
+
+  for (unsigned Opcode :
+       {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
+        (unsigned)Instruction::Call}) {
+    for (Instruction *I : OpcodeInstMap[Opcode]) {
+      // Assume that all intrinsic will return
+      if (isa<IntrinsicInst>(I))
+        continue;
+
+      auto ICS = ImmutableCallSite(I);
+
+      auto *WillReturnAA = A.getAAFor<AAWillReturnFunction>(*this, *I);
+      if ((!WillReturnAA || !WillReturnAA->isValidState() ||
+           !WillReturnAA->isAssumedWillReturn()) &&
+          !ICS.hasFnAttr("willreturn")) {
+        indicatePessimisticFixpoint();
+        return ChangeStatus::CHANGED;
+      }
+
+      // FIXME: Prohibit any recursion for now
+      auto *NoRecurseAA = A.getAAFor<AANoRecurseFunction>(*this, *I);
+      if ((!NoRecurseAA || !NoRecurseAA->isValidState() ||
+           !NoRecurseAA->isAssumedNoRecurse()) &&
+          !ICS.hasFnAttr(Attribute::NoRecurse)) {
+        indicatePessimisticFixpoint();
+        return ChangeStatus::CHANGED;
+      }
+    }
+  }
+
+  return ChangeStatus::UNCHANGED;
+}
 
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
 
 ChangeStatus Attributor::run() {
   // Initialize all abstract attributes.
   for (AbstractAttribute *AA : AllAbstractAttributes)
     AA->initialize(*this);
 
   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;
 
   SmallVector<AbstractAttribute *, 64> ChangedAAs;
   SetVector<AbstractAttribute *> Worklist;
   Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
 
   do {
     LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
                       << ", Worklist size: " << Worklist.size() << "\n");
 
void Attributor::identifyDefaultAbstractAttributes(
   registerAA(*new AANoRecurseFunction(F, InfoCache));
 
   // Every function might be "no-free".
   registerAA(*new AANoFreeFunction(F, InfoCache));
 
   // Every function might be "no-return".
   registerAA(*new AANoReturnFunction(F, InfoCache));
 
+  // Every function might be "will-return".
+  registerAA(*new AAWillReturnFunction(F, InfoCache));
+
   // Walk all instructions to find more attribute opportunities and also
   // interesting instructions that might be queried by abstract attributes
   // during their initialization or update.
   auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
   auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
 
   for (Instruction &I : instructions(&F)) {
     bool IsInterestingOpcode = false;

llvm/test/Transforms/FunctionAttrs/will-return.ll

 ; RUN: opt -functionattrs -S < %s | FileCheck %s --check-prefix=FNATTR
+; RUN: opt -attributor -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 the "willreturn" function attribute.
 ; We use FIXME's to indicate problems and missing attributes.
 
 
 ; TEST 1 (positive case)
-; FIXME: missing "willreturn"
 ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable
 ; FNATTR-NEXT: define void @only_return()
+; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "nofree" "willreturn"
+; ATTRIBUTOR-NEXT: define void @only_return() 
 define void @only_return() #0 {
     ret void
 }
 
 
 ; TEST 2 (positive & negative case)
 ; 2.1 (positive case)
 ; recursive function which will halt
 ; int fib(int n){
 ;    return n<=1? n : fib(n-1) + fib(n-2);
 ; }
 
 ; FIXME: missing "willreturn"
 ; FNATTR: Function Attrs: noinline nounwind readnone uwtable
 ; FNATTR-NEXT: define i32 @fib(i32)
+; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable "nofree"
+; ATTRIBUTOR-NEXT: define i32 @fib(i32) local_unnamed_addr 
 define i32 @fib(i32) local_unnamed_addr #0 {
   %2 = icmp slt i32 %0, 2
   br i1 %2, label %9, label %3
 
 ; <label>:3:                                      ; preds = %1
   %4 = add nsw i32 %0, -1
   %5 = tail call i32 @fib(i32 %4)
   %6 = add nsw i32 %0, -2

 ;   }
 ;   return fact_maybe_not_halt( n > 0 ? n-1 : n) * n;
 ; }
 ; fact_maybe_not(-1) doesn't stop.
 
 ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable
 ; FNATTR-NOT: "willreturn"
 ; FNATTR-NEXT: define i32 @fact_maybe_not_halt(i32) local_unnamed_addr
+; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "nofree"
+; ATTRIBUTOR-NOT: "willreturn"
+; ATTRIBUTOR-NEXT: define i32 @fact_maybe_not_halt(i32) local_unnamed_addr
 define i32 @fact_maybe_not_halt(i32) local_unnamed_addr #0 {
   %2 = icmp eq i32 %0, 0
   br i1 %2, label %11, label %3
 
 ; <label>:3:                                      ; preds = %1, %3
   %4 = phi i32 [ %8, %3 ], [ %0, %1 ]
   %5 = phi i32 [ %9, %3 ], [ 1, %1 ]
   %6 = icmp sgt i32 %4, 0

 ;     ans *= i;
 ;   }
 ;   return ans;
 ; }
 
 ; FIXME: missing "willreturn"
 ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable
 ; FNATTR-NEXT: define i32 @fact_loop(i32)
+; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "nofree"
+; ATTRIBUTOR-NEXT: define i32 @fact_loop(i32) local_unnamed_addr 
 define i32 @fact_loop(i32) local_unnamed_addr #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
 

 ; }
 ; void mutual_recursion2(){
 ;     mutual_recursion1();
 ; }
 
 ; FNATTR: Function Attrs: noinline nounwind readnone uwtable
 ; FNATTR-NOT: "willreturn"
 ; FNATTR-NEXT: define void @mutual_recursion1()
+; ATTRIBUTOR: Function Attrs: noinline noreturn nounwind uwtable "nofree"
+; ATTRIBUTOR-NOT: "willreturn"
+; ATTRIBUTOR-NEXT: define void @mutual_recursion1()
 define void @mutual_recursion1() #0 {
   call void @mutual_recursion2()
   ret void
 }
 
 
 ; FNATTR: Function Attrs: noinline nounwind readnone uwtable
 ; FNATTR-NOT: "willreturn"
 ; FNATTR-NEXT: define void @mutual_recursion2()
+; ATTRIBUTOR: Function Attrs: noinline noreturn nounwind uwtable "nofree"
+; ATTRIBUTOR-NOT: "willreturn"
+; ATTRIBUTOR-NEXT: define void @mutual_recursion2() 
 define void @mutual_recursion2() #0 {
   call void @mutual_recursion1()
   ret void
 }
 
 
 ; TEST 5 (negative case)
 ; call exit/abort (has noreturn attribute)
 ; FNATTR: Function Attrs: noreturn
 ; FNATTR-NEXT: declare void @exit(i32) local_unnamed_addr
+; ATTRIBUTOR: Function Attrs: noreturn
+; ATTRIBUTOR-NEXT: declare void @exit(i32) local_unnamed_add
 declare void @exit(i32) local_unnamed_addr noreturn
 
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NOT: "willreturn"
 ; FNATTR-NEXT: define void @only_exit()
+; ATTRIBUTOR: Function Attrs: noinline noreturn nounwind uwtable
+; ATTRIBUTOR-NOT: "willreturn"
+; ATTRIBUTOR-NEXT: define void @only_exit() local_unnamed_addr 
 define void @only_exit() local_unnamed_addr #0 {
   tail call void @exit(i32 0)
   unreachable
 }
 
 ; conditional exit
 ; void conditional_exit(int cond, int *p){
 ;     if(cond){
 ;       exit(0);
 ;     }
 ;     if(*p){
 ;       exit(1);
 ;     }
 ;     return;
 ; }
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NOT: "willreturn"
 ; FNATTR-NEXT: define void @conditional_exit(i32, i32* nocapture readonly) local_unnamed_addr
+; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR-NOT: "willreturn"
+; ATTRIBUTOR-NEXT: define void @conditional_exit(i32, i32* nocapture readonly) local_unnamed_addr
 define void @conditional_exit(i32, i32* nocapture readonly) local_unnamed_addr #0 {
   %3 = icmp eq i32 %0, 0
   br i1 %3, label %5, label %4
 
 ; <label>:4:                                      ; preds = %2
   tail call void @exit(i32 0)
   unreachable
 

 ; <label>:9:                                      ; preds = %5
   ret void
 }
 
 ; TEST 6 (positive case)
 ; Call intrinsic function
 ; FNATTRS: Function Attrs: noinline readnone speculatable
 ; FNATTRS-NEXT: declare float @llvm.floor.f32(float)
+; ATTRIBUTOR: Function Attrs: nounwind readnone speculatable
+; ATTRIBUTOR-NEXT: declare float @llvm.floor.f32(float
 declare float @llvm.floor.f32(float)
 
-; FIXME: missing "willreturn"
 ; FNATTRS: Function Attrs: noinline nounwind uwtable
 ; FNATTRS-NEXT: define void @call_floor(float %a)
+; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "willreturn"
+; ATTRIBUTOR-NEXT: define void @call_floor(float %a)
 define void @call_floor(float %a) #0 {
     tail call float @llvm.floor.f32(float %a)
     ret void
 }
 
 
 ; TEST 7 (negative case)
 ; Call function declaration without "willreturn"
 
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NOT: "willreturn"
 ; FNATTR-NEXT: declare void @maybe_noreturn()
+; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR-NOT: "willreturn"
+; ATTRIBUTOR-NEXT: declare void @maybe_noreturn()
 declare void @maybe_noreturn() #0
 
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NOT: "willreturn"
 ; FNATTR-NEXT: define void @call_maybe_noreturn()
+; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR-NOT: "willreturn"
+; ATTRIBUTOR-NEXT: define void @call_maybe_noreturn() 
 define void @call_maybe_noreturn() #0 {
     tail call void @maybe_noreturn()
     ret void
 }
 
 
 ; TEST 8 (positive case)
 ; Check propagation.
 
 ; FNATTR: Function Attrs: "willreturn"
 ; FNATTR-NEXT: declare void @will_return()
+; ATTRIBUTOR: Function Attrs: "willreturn"
+; ATTRIBUTOR-NEXT: declare void @will_return()
 declare void @will_return() "willreturn"
 
 ; FIXME: missing "willreturn"
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NEXT: define void @f1()
+; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR-NEXT: define void @f1() 
 define void @f1() #0 {
     tail call void @will_return()
     ret void
 }
 
 ; FIXME: missing "willreturn"
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NEXT: define void @f2()
+; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR-NEXT: define void @f2() 
 define void @f2() #0 {
     tail call void @f1()
     ret void
 }
 
 
 ; TEST 9 (negative case)
 ; call willreturn function in endless loop.
 
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NOT: "willreturn"
 ; FNATTR-NEXT: define void @call_will_return_but_has_loop()
+; ATTRIBUTOR: Function Attrs: noinline noreturn nounwind uwtable
+; ATTRIBUTOR-NOT: "willreturn"
+; ATTRIBUTOR-NEXT: define void @call_will_return_but_has_loop() 
 define void @call_will_return_but_has_loop() #0 {
   br label %label1
 label1:
   tail call void @will_return()
   br label %label2
 label2:
   br label %label1
 }
 
 
 ; TEST 10 (positive case)
 ; invoke a function with "willreturn"
 
 ; FNATTR: Function Attrs: noinline uwtable "willreturn"
 ; FNATTR-NEXT: declare i1 @maybe_raise_exception()
+; ATTRIBUTOR: Function Attrs: noinline uwtable "willreturn"
+; ATTRIBUTOR-NEXT: declare i1 @maybe_raise_exception()
 declare i1 @maybe_raise_exception() #1 "willreturn"
 
 ; FIXME: missing "willreturn"
 ; FNATTR: Function Attrs: nounwind
 ; FNATTR-NEXT: define void @invoke_test()
+; ATTRIBUTOR: define void @invoke_test()
 define void @invoke_test() personality i32 (...)* @__gxx_personality_v0 {
   invoke i1 @maybe_raise_exception()
       to label %N unwind label %F
   N:
     ret void
   F:
     %val = landingpad { i8*, i32 }
                   catch i8* null

 ;        ans += p[i];
 ;    }
 ;    return ans;
 ; }
 
 ; FIXME: missing "willreturn"
 ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable
 ; FNATTR-NEXT: define i32 @loop_constant_trip_count(i32* nocapture readonly)
+; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "nofree"
+; ATTRIBUTOR-NEXT: define i32 @loop_constant_trip_count(i32* nocapture readonly) 
 define i32 @loop_constant_trip_count(i32* nocapture readonly) #0 {
   br label %3
 
 ; <label>:2:                                      ; preds = %3
   ret i32 %8
 
 ; <label>:3:                                      ; preds = %3, %1
   %4 = phi i64 [ 0, %1 ], [ %9, %3 ]

 ;     for(unsigned i = s;i != e;i+=offset){
 ;         ans += p[i];
 ;     }
 ;     return ans;
 ; }
 ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable
 ; FNATTR-NOT: "willreturn"
 ; FNATTR-NEXT: define i32 @loop_trip_count_unbound(i32, i32, i32* nocapture readonly, i32) local_unnamed_addr
+; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "nofree"
+; ATTRIBUTOR-NOT: "willreturn"
+; ATTRIBUTOR-NEXT: define i32 @loop_trip_count_unbound(i32, i32, i32* nocapture readonly, i32) local_unnamed_addr 
 define i32 @loop_trip_count_unbound(i32, i32, i32* nocapture readonly, i32) local_unnamed_addr #0 {
   %5 = icmp eq i32 %0, %1
   br i1 %5, label %6, label %8
 
 ; <label>:6:                                      ; preds = %8, %4
   %7 = phi i32 [ 0, %4 ], [ %14, %8 ]
   ret i32 %7
 

 ;    }
 ;    return ans;
 ;  }
 
 
 ; FIXME: missing "willreturn"
 ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable
 ; FNATTR-NEXT: define i32 @loop_trip_dec(i32, i32* nocapture readonly)
+; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "nofree"
+; ATTRIBUTOR-NEXT: define i32 @loop_trip_dec(i32, i32* nocapture readonly) local_unnamed_addr 
 
 define i32 @loop_trip_dec(i32, i32* nocapture readonly) local_unnamed_addr #0 {
   %3 = icmp sgt i32 %0, -1
   br i1 %3, label %4, label %14
 
 ; <label>:4:                                      ; preds = %2
   %5 = sext i32 %0 to i64
   br label %6

 }
 
 ; TEST 14 (positive case)
 ; multiple return
 
 ; FIXME: missing "willreturn"
 ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable
 ; FNATTR-NEXT: define i32 @multiple_return(i32 %a)
+; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable "nofree" "willreturn"
+; ATTRIBUTOR-NEXT: define i32 @multiple_return(i32 %a) 
 define i32 @multiple_return(i32 %a) #0 {
   %b =  icmp eq i32 %a, 0
   br i1 %b, label %t, label %f
 
 t:
   ret i32 1
 f:
   ret i32 0
 }
 
 ; TEST 15 (positive & negative case)
 ; unreachable exit
 
 ; 15.1 (positive case)
 ; FIXME: missing "willreturn"
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NEXT: define void @unreachable_exit_positive1()
+; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR-NEXT: define void @unreachable_exit_positive1()
 define void @unreachable_exit_positive1() #0 {
   tail call void @will_return()
   ret void
 
 unreachable_label:
   tail call void @exit(i32 0)
   unreachable
 }
 
 ; FIXME: missing "willreturn"
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NEXT: define i32 @unreachable_exit_positive2(i32)
+; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR-NEXT: define i32 @unreachable_exit_positive2(i32) 
 define i32 @unreachable_exit_positive2(i32) local_unnamed_addr #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
 
unreachable_label:
   unreachable
 }
 
 ;15.2
 
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NOT: "willreturn"
 ; FNATTR-NEXT: define void @unreachable_exit_negative1()
+; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR-NOT: "willreturn"
+; ATTRIBUTOR-NEXT: define void @unreachable_exit_negative1() 
 define void @unreachable_exit_negative1() #0 {
   tail call void @exit(i32 0)
   ret void
 
 unreachable_label:
   tail call void @exit(i32 0)
   unreachable
 }
 
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NOT: "willreturn"
 ; FNATTR-NEXT: define void @unreachable_exit_negative2()
+; ATTRIBUTOR: Function Attrs: noinline noreturn nounwind uwtable
+; ATTRIBUTOR-NOT: "willreturn"
+; ATTRIBUTOR-NEXT: define void @unreachable_exit_negative2() 
 define void @unreachable_exit_negative2() #0 {
 
   br label %L1
 L1:
   br label %L2
 L2:
   br label %L1
 
 unreachable_label:
   tail call void @exit(i32 0)
   unreachable
 }
 
 
 attributes #0 = { nounwind uwtable noinline }
 attributes #1 = { uwtable noinline }