diff --git a/llvm/tools/llvm-profgen/CSPreInliner.h b/llvm/tools/llvm-profgen/CSPreInliner.h
--- a/llvm/tools/llvm-profgen/CSPreInliner.h
+++ b/llvm/tools/llvm-profgen/CSPreInliner.h
@@ -41,6 +41,14 @@
 struct ProfiledCandidateComparer {
   bool operator()(const ProfiledInlineCandidate &LHS,
                   const ProfiledInlineCandidate &RHS) {
+    // Always prioritize inlining zero-sized functions as they do not affect the
+    // size budget. This could happen when all of the callee's code is gone and
+    // only pseudo probes are left.
+    if (LHS.SizeCost == 0 || RHS.SizeCost == 0) {
+      if (LHS.SizeCost != RHS.SizeCost)
+        return RHS.SizeCost == 0;
+    }
+
     if (LHS.CallsiteCount != RHS.CallsiteCount)
       return LHS.CallsiteCount < RHS.CallsiteCount;