Index: lib/Transforms/IPO/FunctionAttrs.cpp
===================================================================
--- lib/Transforms/IPO/FunctionAttrs.cpp
+++ lib/Transforms/IPO/FunctionAttrs.cpp
@@ -22,6 +22,7 @@
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
@@ -1425,12 +1426,36 @@
   return Changed;
 }
 
+static bool functionWillReturn(const Function &F) {
+  // Must-progress function without side-effects must return.
+  if (F.mustProgress() && F.onlyReadsMemory())
+    return true;
+
+  // Can only analyze functions with a definition.
+  if (F.isDeclaration())
+    return false;
+
+  // Functions with loops require more sophisticated analysis, as the loop
+  // may be infinite. For now, don't try to handle them.
+  SmallVector<std::pair<const BasicBlock *, const BasicBlock *>> Backedges;
+  FindFunctionBackedges(F, Backedges);
+  if (!Backedges.empty())
+    return false;
+
+  // If there are no loops, then the function is willreturn if all calls in
+  // it are willreturn.
+  return all_of(instructions(F), [](const Instruction &I) {
+    const auto *CB = dyn_cast<CallBase>(&I);
+    return !CB || CB->hasFnAttr(Attribute::WillReturn);
+  });
+}
+
 // Set the willreturn function attribute if possible.
 static bool addWillReturn(const SCCNodeSet &SCCNodes) {
   bool Changed = false;
 
   for (Function *F : SCCNodes) {
-    if (!F || !F->onlyReadsMemory() || !F->mustProgress() || F->willReturn())
+    if (!F || F->willReturn() || !functionWillReturn(*F))
       continue;
 
     F->setWillReturn();
Index: test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll
===================================================================
--- test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll
+++ test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll
@@ -72,13 +72,13 @@
 declare void @callee(i32* %p) nounwind
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8*, i8*, i64, i1) nounwind
 
-; CHECK: attributes #0 = { norecurse nounwind readnone }
-; CHECK: attributes #1 = { nofree norecurse nounwind writeonly }
+; CHECK: attributes #0 = { norecurse nounwind readnone willreturn }
+; CHECK: attributes #1 = { nofree norecurse nounwind willreturn writeonly }
 ; CHECK: attributes #2 = { nounwind readonly }
 ; CHECK: attributes #3 = { nounwind }
-; CHECK: attributes #4 = { nounwind readnone }
-; CHECK: attributes #5 = { nofree nounwind }
-; CHECK: attributes #6 = { nofree norecurse nounwind }
+; CHECK: attributes #4 = { nounwind readnone willreturn }
+; CHECK: attributes #5 = { nofree nounwind willreturn }
+; CHECK: attributes #6 = { nofree norecurse nounwind willreturn }
 ; CHECK: attributes #7 = { argmemonly nofree nosync nounwind willreturn }
 
 ; Root note.
Index: test/CodeGen/AMDGPU/inline-attr.ll
===================================================================
--- test/CodeGen/AMDGPU/inline-attr.ll
+++ test/CodeGen/AMDGPU/inline-attr.ll
@@ -6,14 +6,14 @@
 ; GCN: define amdgpu_kernel void @caller(float addrspace(1)* nocapture %p) local_unnamed_addr #1 {
 ; GCN: %mul.i = fmul float %load, 1.500000e+01
 
-; UNSAFE: attributes #0 = { norecurse nounwind readnone "unsafe-fp-math"="true" }
-; UNSAFE: attributes #1 = { nofree norecurse nounwind "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "unsafe-fp-math"="true" }
+; UNSAFE: attributes #0 = { norecurse nounwind readnone willreturn "unsafe-fp-math"="true" }
+; UNSAFE: attributes #1 = { nofree norecurse nounwind willreturn "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "unsafe-fp-math"="true" }
 
-; NOINFS: attributes #0 = { norecurse nounwind readnone "no-infs-fp-math"="true" }
-; NOINFS: attributes #1 = { nofree norecurse nounwind "less-precise-fpmad"="false" "no-infs-fp-math"="true" "no-nans-fp-math"="false" "unsafe-fp-math"="false" }
+; NOINFS: attributes #0 = { norecurse nounwind readnone willreturn "no-infs-fp-math"="true" }
+; NOINFS: attributes #1 = { nofree norecurse nounwind willreturn "less-precise-fpmad"="false" "no-infs-fp-math"="true" "no-nans-fp-math"="false" "unsafe-fp-math"="false" }
 
-; NONANS: attributes #0 = { norecurse nounwind readnone "no-nans-fp-math"="true" }
-; NONANS: attributes #1 = { nofree norecurse nounwind "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="true" "unsafe-fp-math"="false" }
+; NONANS: attributes #0 = { norecurse nounwind readnone willreturn "no-nans-fp-math"="true" }
+; NONANS: attributes #1 = { nofree norecurse nounwind willreturn "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="true" "unsafe-fp-math"="false" }
 
 define float @foo(float %x) #0 {
 entry:
Index: test/CodeGenOpenCL/convergent.cl
===================================================================
--- test/CodeGenOpenCL/convergent.cl
+++ test/CodeGenOpenCL/convergent.cl
@@ -134,7 +134,7 @@
   __asm__ volatile("s_barrier");
 }
 
-// CHECK: attributes #0 = { nofree noinline norecurse nounwind "
+// CHECK: attributes #0 = { nofree noinline norecurse nounwind willreturn "
 // CHECK: attributes #1 = { {{[^}]*}}convergent{{[^}]*}} }
 // CHECK: attributes #2 = { {{[^}]*}}convergent{{[^}]*}} }
 // CHECK: attributes #3 = { {{[^}]*}}convergent noduplicate{{[^}]*}} }
Index: test/Transforms/FunctionAttrs/atomic.ll
===================================================================
--- test/Transforms/FunctionAttrs/atomic.ll
+++ test/Transforms/FunctionAttrs/atomic.ll
@@ -20,5 +20,5 @@
   ret i32 %r
 }
 
-; CHECK: attributes #0 = { norecurse nounwind readnone ssp uwtable }
-; CHECK: attributes #1 = { nofree norecurse nounwind ssp uwtable }
+; CHECK: attributes #0 = { norecurse nounwind readnone ssp uwtable willreturn }
+; CHECK: attributes #1 = { nofree norecurse nounwind ssp uwtable willreturn }
Index: test/Transforms/FunctionAttrs/incompatible_fn_attrs.ll
===================================================================
--- test/Transforms/FunctionAttrs/incompatible_fn_attrs.ll
+++ test/Transforms/FunctionAttrs/incompatible_fn_attrs.ll
@@ -28,5 +28,5 @@
 attributes #0 = { argmemonly }
 attributes #1 = { inaccessiblememonly }
 attributes #2 = { inaccessiblemem_or_argmemonly }
-; CHECK: attributes #0 = { norecurse nounwind readnone }
+; CHECK: attributes #0 = { norecurse nounwind readnone willreturn }
 ; CHECK-NOT: attributes
Index: test/Transforms/FunctionAttrs/nofree.ll
===================================================================
--- test/Transforms/FunctionAttrs/nofree.ll
+++ test/Transforms/FunctionAttrs/nofree.ll
@@ -107,7 +107,7 @@
 ; CHECK: attributes #0 = { uwtable }
 ; CHECK: attributes #1 = { nounwind uwtable }
 ; CHECK: attributes #2 = { nounwind }
-; CHECK: attributes #3 = { norecurse nounwind readonly uwtable }
+; CHECK: attributes #3 = { norecurse nounwind readonly uwtable willreturn }
 ; CHECK: attributes #4 = { nobuiltin nounwind }
 ; CHECK: attributes #5 = { builtin nounwind }
 
Index: test/Transforms/FunctionAttrs/optnone.ll
===================================================================
--- test/Transforms/FunctionAttrs/optnone.ll
+++ test/Transforms/FunctionAttrs/optnone.ll
@@ -20,6 +20,6 @@
 ; CHECK: (i8*) #1
 
 ; CHECK-LABEL: attributes #0
-; CHECK: = { norecurse nounwind readnone }
+; CHECK: = { norecurse nounwind readnone willreturn }
 ; CHECK-LABEL: attributes #1
 ; CHECK: = { noinline optnone }
Index: test/Transforms/FunctionAttrs/willreturn.ll
===================================================================
--- test/Transforms/FunctionAttrs/willreturn.ll
+++ test/Transforms/FunctionAttrs/willreturn.ll
@@ -71,9 +71,10 @@
   ret i64 0
 }
 
+; Function without loops or non-willreturn calls will return.
 define void @willreturn_no_loop(i1 %c, i32* %p) {
-; CHECK-NOT: Function Attrs: {{.*}}willreturn
-; CHECK: define void @willreturn_no_loop(
+; CHECK: Function Attrs: willreturn
+; CHECK-NEXT: define void @willreturn_no_loop(
 ;
   br i1 %c, label %if, label %else
 
@@ -90,6 +91,7 @@
   ret void
 }
 
+; Calls a function that is not guaranteed to return, not willreturn.
 define void @willreturn_non_returning_function(i1 %c, i32* %p) {
 ; CHECK-NOT: Function Attrs: {{.*}}willreturn
 ; CHECK: define void @willreturn_non_returning_function(
@@ -98,6 +100,7 @@
   ret void
 }
 
+; Infinite loop without mustprogress, will not return.
 define void @willreturn_loop() {
 ; CHECK-NOT: Function Attrs: {{.*}}willreturn
 ; CHECK: define void @willreturn_loop(
@@ -108,6 +111,8 @@
   br label %loop
 }
 
+; Finite loop. Could be willreturn but not detected.
+; FIXME
 define void @willreturn_finite_loop() {
 ; CHECK-NOT: Function Attrs: {{.*}}willreturn
 ; CHECK: define void @willreturn_finite_loop(
@@ -125,5 +130,28 @@
   ret void
 }
 
+; Infinite recursion without mustprogress, will not return.
+define void @willreturn_recursion() {
+; CHECK-NOT: Function Attrs: {{.*}}willreturn
+; CHECK: define void @willreturn_recursion(
+;
+  tail call void @willreturn_recursion()
+  ret void
+}
+
+; Irreducible infinite loop, will not return.
+define void @willreturn_irreducible(i1 %c) {
+; CHECK-NOT: Function Attrs: {{.*}}willreturn
+; CHECK: define void @willreturn_irreducible(
+;
+  br i1 %c, label %bb1, label %bb2
+
+bb1:
+  br label %bb2
+
+bb2:
+  br label %bb1
+}
+
 declare i64 @fn_noread() readnone
 declare void @fn_willreturn() willreturn
Index: test/Transforms/FunctionAttrs/writeonly.ll
===================================================================
--- test/Transforms/FunctionAttrs/writeonly.ll
+++ test/Transforms/FunctionAttrs/writeonly.ll
@@ -25,6 +25,6 @@
   ret void
 }
 
-; CHECK: attributes #0 = { {{.*}} readnone }
-; CHECK: attributes #1 = { {{.*}} readonly }
+; CHECK: attributes #0 = { {{.*}} readnone {{.*}} }
+; CHECK: attributes #1 = { {{.*}} readonly {{.*}} }
 ; CHECK: attributes #2 = { {{.*}} writeonly }
Index: test/Transforms/InferFunctionAttrs/norecurse_debug.ll
===================================================================
--- test/Transforms/InferFunctionAttrs/norecurse_debug.ll
+++ test/Transforms/InferFunctionAttrs/norecurse_debug.ll
@@ -52,5 +52,5 @@
 !28 = !DILocation(line: 9, column: 18, scope: !2)
 !29 = !DILocation(line: 10, column: 1, scope: !2)
 
-; CHECK: attributes #0 = { nofree norecurse nounwind }
+; CHECK: attributes #0 = { nofree norecurse nounwind willreturn }
 ; CHECK-NOT: foo.coefficient1