diff --git a/bolt/lib/Passes/MCF.cpp b/bolt/lib/Passes/MCF.cpp
--- a/bolt/lib/Passes/MCF.cpp
+++ b/bolt/lib/Passes/MCF.cpp
@@ -262,6 +262,7 @@
       continue;
 
     Pred->getBranchInfo(*BB).Count = Guessed;
+    GuessedArcs.insert(std::make_pair(Pred, BB));
     return true;
   }
   llvm_unreachable("Expected unguessed arc");