diff --git a/llvm/include/llvm/Transforms/Utils/SizeOpts.h b/llvm/include/llvm/Transforms/Utils/SizeOpts.h
--- a/llvm/include/llvm/Transforms/Utils/SizeOpts.h
+++ b/llvm/include/llvm/Transforms/Utils/SizeOpts.h
@@ -62,9 +62,13 @@
     // Even if the working set size isn't large, size-optimize cold code.
     return AdapterT::isFunctionColdInCallGraph(F, PSI, *BFI);
   }
-  return !AdapterT::isFunctionHotInCallGraphNthPercentile(
-      PSI->hasSampleProfile() ? PgsoCutoffSampleProf : PgsoCutoffInstrProf,
-      F, PSI, *BFI);
+  if (PSI->hasSampleProfile())
+    // The "isCold" check seems to work better for Sample PGO as it could have
+    // many profile-unannotated functions.
+    return AdapterT::isFunctionColdInCallGraphNthPercentile(PgsoCutoffSampleProf,
+                                                            F, PSI, *BFI);
+  return !AdapterT::isFunctionHotInCallGraphNthPercentile(PgsoCutoffInstrProf,
+                                                          F, PSI, *BFI);
 }
 
 template<typename AdapterT, typename BlockTOrBlockFreq, typename BFIT>
@@ -88,9 +92,13 @@
     // Even if the working set size isn't large, size-optimize cold code.
     return AdapterT::isColdBlock(BBOrBlockFreq, PSI, BFI);
   }
-  return !AdapterT::isHotBlockNthPercentile(
-      PSI->hasSampleProfile() ? PgsoCutoffSampleProf : PgsoCutoffInstrProf,
-      BBOrBlockFreq, PSI, BFI);
+  if (PSI->hasSampleProfile())
+    // The "isCold" check seems to work better for Sample PGO as it could have
+    // many profile-unannotated functions.
+    return AdapterT::isColdBlockNthPercentile(PgsoCutoffSampleProf,
+                                              BBOrBlockFreq, PSI, BFI);
+  return !AdapterT::isHotBlockNthPercentile(PgsoCutoffInstrProf,
+                                            BBOrBlockFreq, PSI, BFI);
 }
 
 /// Returns true if function \p F is suggested to be size-optimized based on the
diff --git a/llvm/lib/CodeGen/MachineSizeOpts.cpp b/llvm/lib/CodeGen/MachineSizeOpts.cpp
--- a/llvm/lib/CodeGen/MachineSizeOpts.cpp
+++ b/llvm/lib/CodeGen/MachineSizeOpts.cpp
@@ -59,6 +59,22 @@
   return Count && PSI->isHotCountNthPercentile(PercentileCutoff, *Count);
 }
 
+static bool isColdBlockNthPercentile(int PercentileCutoff,
+                                     const MachineBasicBlock *MBB,
+                                     ProfileSummaryInfo *PSI,
+                                     const MachineBlockFrequencyInfo *MBFI) {
+  auto Count = MBFI->getBlockProfileCount(MBB);
+  return Count && PSI->isColdCountNthPercentile(PercentileCutoff, *Count);
+}
+
+static bool isColdBlockNthPercentile(int PercentileCutoff,
+                                     BlockFrequency BlockFreq,
+                                     ProfileSummaryInfo *PSI,
+                                     const MachineBlockFrequencyInfo *MBFI) {
+  auto Count = MBFI->getProfileCountFromFreq(BlockFreq.getFrequency());
+  return Count && PSI->isColdCountNthPercentile(PercentileCutoff, *Count);
+}
+
 /// Like ProfileSummaryInfo::isFunctionColdInCallGraph but for
 /// MachineFunction.
 bool isFunctionColdInCallGraph(
@@ -90,6 +106,21 @@
       return true;
   return false;
 }
+
+bool isFunctionColdInCallGraphNthPercentile(
+    int PercentileCutoff,
+    const MachineFunction *MF,
+    ProfileSummaryInfo *PSI,
+    const MachineBlockFrequencyInfo &MBFI) {
+  if (auto FunctionCount = MF->getFunction().getEntryCount())
+    if (!PSI->isColdCountNthPercentile(PercentileCutoff,
+                                      FunctionCount.getCount()))
+      return false;
+  for (const auto &MBB : *MF)
+    if (!isColdBlockNthPercentile(PercentileCutoff, &MBB, PSI, &MBFI))
+      return false;
+  return true;
+}
 } // namespace machine_size_opts_detail
 
 struct MachineBasicBlockBFIAdapter {
@@ -106,6 +137,14 @@
     return machine_size_opts_detail::isFunctionHotInCallGraphNthPercentile(
         CutOff, MF, PSI, MBFI);
   }
+  static bool isFunctionColdInCallGraphNthPercentile(
+      int CutOff,
+      const MachineFunction *MF,
+      ProfileSummaryInfo *PSI,
+      const MachineBlockFrequencyInfo &MBFI) {
+    return machine_size_opts_detail::isFunctionColdInCallGraphNthPercentile(
+        CutOff, MF, PSI, MBFI);
+  }
   static bool isColdBlock(const MachineBasicBlock *MBB,
                           ProfileSummaryInfo *PSI,
                           const MachineBlockFrequencyInfo *MBFI) {
@@ -130,6 +169,20 @@
     return machine_size_opts_detail::isHotBlockNthPercentile(
         CutOff, BlockFreq, PSI, MBFI);
   }
+  static bool isColdBlockNthPercentile(int CutOff,
+                                       const MachineBasicBlock *MBB,
+                                       ProfileSummaryInfo *PSI,
+                                       const MachineBlockFrequencyInfo *MBFI) {
+    return machine_size_opts_detail::isColdBlockNthPercentile(
+        CutOff, MBB, PSI, MBFI);
+  }
+  static bool isColdBlockNthPercentile(int CutOff,
+                                       BlockFrequency BlockFreq,
+                                       ProfileSummaryInfo *PSI,
+                                       const MachineBlockFrequencyInfo *MBFI) {
+    return machine_size_opts_detail::isColdBlockNthPercentile(
+        CutOff, BlockFreq, PSI, MBFI);
+  }
 };
 } // end anonymous namespace
 
diff --git a/llvm/lib/Transforms/Utils/SizeOpts.cpp b/llvm/lib/Transforms/Utils/SizeOpts.cpp
--- a/llvm/lib/Transforms/Utils/SizeOpts.cpp
+++ b/llvm/lib/Transforms/Utils/SizeOpts.cpp
@@ -70,6 +70,12 @@
                                                     BlockFrequencyInfo &BFI) {
     return PSI->isFunctionHotInCallGraphNthPercentile(CutOff, F, BFI);
   }
+  static bool isFunctionColdInCallGraphNthPercentile(int CutOff,
+                                                     const Function *F,
+                                                     ProfileSummaryInfo *PSI,
+                                                     BlockFrequencyInfo &BFI) {
+    return PSI->isFunctionColdInCallGraphNthPercentile(CutOff, F, BFI);
+  }
   static bool isColdBlock(const BasicBlock *BB,
                           ProfileSummaryInfo *PSI,
                           BlockFrequencyInfo *BFI) {
@@ -81,6 +87,12 @@
                                       BlockFrequencyInfo *BFI) {
     return PSI->isHotBlockNthPercentile(CutOff, BB, BFI);
   }
+  static bool isColdBlockNthPercentile(int CutOff,
+                                       const BasicBlock *BB,
+                                       ProfileSummaryInfo *PSI,
+                                       BlockFrequencyInfo *BFI) {
+    return PSI->isColdBlockNthPercentile(CutOff, BB, BFI);
+  }
 };
 } // end anonymous namespace