diff --git a/llvm/docs/ReleaseNotes.rst b/llvm/docs/ReleaseNotes.rst
--- a/llvm/docs/ReleaseNotes.rst
+++ b/llvm/docs/ReleaseNotes.rst
@@ -93,6 +93,11 @@
 * ``Callbacks`` have been added to ``CommandLine Options``.  These can
   be used to validate of selectively enable other options.
 
+* The function attributes ``no-frame-pointer-elim`` and
+  ``no-frame-pointer-elim-non-leaf`` have been replaced by ``frame-pointer``,
+  which has 3 values: ``none``, ``non-leaf``, and ``all``. The values mean what
+  functions should retain frame pointers.
+
 Changes to the LLVM IR
 ----------------------
 
diff --git a/llvm/include/llvm/IR/AutoUpgrade.h b/llvm/include/llvm/IR/AutoUpgrade.h
--- a/llvm/include/llvm/IR/AutoUpgrade.h
+++ b/llvm/include/llvm/IR/AutoUpgrade.h
@@ -16,6 +16,7 @@
 #include "llvm/ADT/StringRef.h"
 
 namespace llvm {
+  class AttrBuilder;
   class CallInst;
   class Constant;
   class Function;
@@ -91,6 +92,10 @@
   /// pointers.
   std::string UpgradeDataLayoutString(StringRef DL, StringRef Triple);
 
+  /// Upgrade function attributes "no-frame-pointer-elim" and
+  /// "no-frame-pointer-elim-non-leaf" to "frame-pointer".
+  void UpgradeFramePointerAttributes(AttrBuilder &B);
+
 } // End llvm namespace
 
 #endif
diff --git a/llvm/lib/Bitcode/Reader/BitcodeReader.cpp b/llvm/lib/Bitcode/Reader/BitcodeReader.cpp
--- a/llvm/lib/Bitcode/Reader/BitcodeReader.cpp
+++ b/llvm/lib/Bitcode/Reader/BitcodeReader.cpp
@@ -1661,6 +1661,7 @@
         }
       }
 
+      UpgradeFramePointerAttributes(B);
       MAttributeGroups[GrpID] = AttributeList::get(Context, Idx, B);
       break;
     }
diff --git a/llvm/lib/CodeGen/TargetOptionsImpl.cpp b/llvm/lib/CodeGen/TargetOptionsImpl.cpp
--- a/llvm/lib/CodeGen/TargetOptionsImpl.cpp
+++ b/llvm/lib/CodeGen/TargetOptionsImpl.cpp
@@ -28,20 +28,8 @@
 
   const Function &F = MF.getFunction();
 
-  // TODO: Remove support for old `fp elim` function attributes after fully
-  //       migrate to use "frame-pointer"
-  if (!F.hasFnAttribute("frame-pointer")) {
-    // Check to see if we should eliminate all frame pointers.
-    if (F.getFnAttribute("no-frame-pointer-elim").getValueAsString() == "true")
-      return true;
-
-    // Check to see if we should eliminate non-leaf frame pointers.
-    if (F.hasFnAttribute("no-frame-pointer-elim-non-leaf"))
-      return MF.getFrameInfo().hasCalls();
-
+  if (!F.hasFnAttribute("frame-pointer"))
     return false;
-  }
-
   StringRef FP = F.getFnAttribute("frame-pointer").getValueAsString();
   if (FP == "all")
     return true;
diff --git a/llvm/lib/IR/AutoUpgrade.cpp b/llvm/lib/IR/AutoUpgrade.cpp
--- a/llvm/lib/IR/AutoUpgrade.cpp
+++ b/llvm/lib/IR/AutoUpgrade.cpp
@@ -4177,3 +4177,23 @@
   std::string Res = (Groups[1] + AddrSpaces + Groups[3]).toStringRef(Buf).str();
   return Res;
 }
+
+void llvm::UpgradeFramePointerAttributes(AttrBuilder &B) {
+  StringRef FramePointer;
+  if (B.contains("no-frame-pointer-elim")) {
+    // The value can be "true" or "false".
+    for (const auto &I : B.td_attrs())
+      if (I.first == "no-frame-pointer-elim")
+        FramePointer = I.second == "true" ? "all" : "none";
+    B.removeAttribute("no-frame-pointer-elim");
+  }
+  if (B.contains("no-frame-pointer-elim-non-leaf")) {
+    // The value is ignored. "no-frame-pointer-elim"="true" takes priority.
+    if (FramePointer != "all")
+      FramePointer = "non-leaf";
+    B.removeAttribute("no-frame-pointer-elim-non-leaf");
+  }
+
+  if (!FramePointer.empty())
+    B.addAttribute("frame-pointer", FramePointer);
+}
diff --git a/llvm/test/Bitcode/upgrade-frame-pointer.ll b/llvm/test/Bitcode/upgrade-frame-pointer.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Bitcode/upgrade-frame-pointer.ll
@@ -0,0 +1,33 @@
+;; Test that function attributes "no-frame-pointer-elim" ("true" or "false") and
+;; "no-frame-pointer-elim-non-leaf" (value is ignored) can be upgraded to
+;; "frame-pointer".
+
+; RUN: llvm-as %s -o - | llvm-dis - | FileCheck %s
+
+; CHECK: define void @all0() #0
+define void @all0() "no-frame-pointer-elim"="true" { ret void }
+; CHECK: define void @all1() #1
+define void @all1() #0 { ret void }
+
+; CHECK: define void @non_leaf0() #2
+define void @non_leaf0() "no-frame-pointer-elim-non-leaf" { ret void }
+; CHECK: define void @non_leaf1() #3
+define void @non_leaf1() #1 { ret void }
+
+; CHECK: define void @none() #4
+define void @none() "no-frame-pointer-elim"="false" { ret void }
+
+;; Don't add "frame-pointer" if neither "no-frame-pointer-elim" nor
+;; "no-frame-pointer-elim-non-leaf" is present.
+; CHECK: define void @no_attr() {
+define void @no_attr() { ret void }
+
+attributes #0 = { readnone "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" }
+attributes #1 = { readnone "no-frame-pointer-elim"="false" "no-frame-pointer-elim-non-leaf" }
+
+;; Other attributes (e.g. readnone) are unaffected.
+; CHECK: attributes #0 = { "frame-pointer"="all" }
+; CHECK: attributes #1 = { readnone "frame-pointer"="all" }
+; CHECK: attributes #2 = { "frame-pointer"="non-leaf" }
+; CHECK: attributes #3 = { readnone "frame-pointer"="non-leaf" }
+; CHECK: attributes #4 = { "frame-pointer"="none" }