diff --git a/llvm/tools/llvm-profgen/CSPreInliner.cpp b/llvm/tools/llvm-profgen/CSPreInliner.cpp
--- a/llvm/tools/llvm-profgen/CSPreInliner.cpp
+++ b/llvm/tools/llvm-profgen/CSPreInliner.cpp
@@ -207,12 +207,19 @@
 
   ProfiledCandidateQueue CQueue;
   getInlineCandidates(CQueue, FSamples);
+  std::vector<ProfiledInlineCandidate> IngoredDuetoSizeLimit;
 
-  while (!CQueue.empty() && FuncFinalSize < SizeLimit) {
+  while (!CQueue.empty()) {
     ProfiledInlineCandidate Candidate = CQueue.top();
     CQueue.pop();
-    bool ShouldInline = false;
-    if ((ShouldInline = shouldInline(Candidate))) {
+    // Always continue processing zero-sized functions even if the size budget
+    // is hit. This could happen when all of the callee's code is gone and only
+    // pseudo probes are left.
+    bool ShouldInline = (!Candidate.SizeCost ||
+                         Candidate.SizeCost + FuncFinalSize < SizeLimit) &&
+                        shouldInline(Candidate);
+
+    if (ShouldInline) {
       // We mark context as inlined as the corresponding context profile
       // won't be merged into that function's base profile.
       ++PreInlNumCSInlined;
@@ -223,6 +230,8 @@
       getInlineCandidates(CQueue, Candidate.CalleeSamples);
     } else {
       ++PreInlNumCSNotInlined;
+      if (Candidate.SizeCost + FuncFinalSize >= SizeLimit)
+        IngoredDuetoSizeLimit.push_back(Candidate);
     }
     LLVM_DEBUG(
         dbgs() << (ShouldInline ? "  Inlined" : "  Outlined")
@@ -232,7 +241,7 @@
                << ", call count:" << Candidate.CallsiteCount << ")\n");
   }
 
-  if (!CQueue.empty()) {
+  if (!IngoredDuetoSizeLimit.empty()) {
     if (SizeLimit == (unsigned)ProfileInlineLimitMax)
       ++PreInlNumCSInlinedHitMaxLimit;
     else if (SizeLimit == (unsigned)ProfileInlineLimitMin)
@@ -242,13 +251,13 @@
   }
 
   LLVM_DEBUG({
-    if (!CQueue.empty())
+    if (!IngoredDuetoSizeLimit.empty())
       dbgs() << "  Inline candidates ignored due to size limit (inliner "
                 "original size: "
              << FuncSize << ", inliner final size: " << FuncFinalSize
              << ", size limit: " << SizeLimit << ")\n";
 
-    while (!CQueue.empty()) {
+    while (!IngoredDuetoSizeLimit.empty()) {
       ProfiledInlineCandidate Candidate = CQueue.top();
       CQueue.pop();
       bool WasInlined =