diff --git a/llvm/lib/Support/FoldingSet.cpp b/llvm/lib/Support/FoldingSet.cpp
--- a/llvm/lib/Support/FoldingSet.cpp
+++ b/llvm/lib/Support/FoldingSet.cpp
@@ -86,6 +86,10 @@
 
 void FoldingSetNodeID::AddString(StringRef String) {
   unsigned Size =  String.size();
+
+  unsigned NumInserts = 1 + divideCeil(Size, 4);
+  Bits.reserve(Bits.size() + NumInserts);
+
   Bits.push_back(Size);
   if (!Size) return;