diff --git a/bolt/include/bolt/Core/BinaryFunction.h b/bolt/include/bolt/Core/BinaryFunction.h
--- a/bolt/include/bolt/Core/BinaryFunction.h
+++ b/bolt/include/bolt/Core/BinaryFunction.h
@@ -377,6 +377,10 @@
   /// Indicates the type of profile the function is using.
   uint16_t ProfileFlags{PF_NONE};
 
+  /// True if the function's input profile data has been inaccurate but has
+  /// been adjusted by the profile inference algorithm.
+  bool HasInferredProfile{false};
+
   /// For functions with mismatched profile we store all call profile
   /// information at a function level (as opposed to tying it to
   /// specific call sites).
@@ -1643,6 +1647,12 @@
   /// Return flags describing a profile for this function.
   uint16_t getProfileFlags() const { return ProfileFlags; }
 
+  /// Return true if the function's input profile data has been inaccurate but
+  /// has been corrected by the profile inference algorithm.
+  bool hasInferredProfile() const { return HasInferredProfile; }
+
+  void setHasInferredProfile(bool Inferred) { HasInferredProfile = Inferred; }
+
   void addCFIInstruction(uint64_t Offset, MCCFIInstruction &&Inst) {
     assert(!Instructions.empty());
 
diff --git a/bolt/include/bolt/Profile/YAMLProfileReader.h b/bolt/include/bolt/Profile/YAMLProfileReader.h
--- a/bolt/include/bolt/Profile/YAMLProfileReader.h
+++ b/bolt/include/bolt/Profile/YAMLProfileReader.h
@@ -70,6 +70,10 @@
   bool parseFunctionProfile(BinaryFunction &Function,
                             const yaml::bolt::BinaryFunctionProfile &YamlBF);
 
+  /// Infer function profile from stale data (collected on older binaries).
+  bool inferStaleProfile(BinaryFunction &Function,
+                         const yaml::bolt::BinaryFunctionProfile &YamlBF);
+
   /// Initialize maps for profile matching.
   void buildNameMaps(std::map<uint64_t, BinaryFunction> &Functions);
 
diff --git a/bolt/lib/Passes/BinaryPasses.cpp b/bolt/lib/Passes/BinaryPasses.cpp
--- a/bolt/lib/Passes/BinaryPasses.cpp
+++ b/bolt/lib/Passes/BinaryPasses.cpp
@@ -1317,10 +1317,12 @@
 void PrintProgramStats::runOnFunctions(BinaryContext &BC) {
   uint64_t NumRegularFunctions = 0;
   uint64_t NumStaleProfileFunctions = 0;
+  uint64_t NumInferredFunctions = 0;
   uint64_t NumNonSimpleProfiledFunctions = 0;
   uint64_t NumUnknownControlFlowFunctions = 0;
   uint64_t TotalSampleCount = 0;
   uint64_t StaleSampleCount = 0;
+  uint64_t InferredSampleCount = 0;
   std::vector<const BinaryFunction *> ProfiledFunctions;
   const char *StaleFuncsHeader = "BOLT-INFO: Functions with stale profile:\n";
   for (auto &BFI : BC.getBinaryFunctions()) {
@@ -1355,6 +1357,10 @@
 
     if (Function.hasValidProfile()) {
       ProfiledFunctions.push_back(&Function);
+      if (Function.hasInferredProfile()) {
+        ++NumInferredFunctions;
+        InferredSampleCount += SampleCount;
+      }
     } else {
       if (opts::ReportStaleFuncs) {
         outs() << StaleFuncsHeader;
@@ -1409,6 +1415,13 @@
       exit(1);
     }
   }
+  if (NumInferredFunctions) {
+    outs() << format("BOLT-INFO: inferred profile for %d (%.2f%% of all "
+                     "profiled) functions responsible for %.2f%% samples\n",
+                     NumInferredFunctions,
+                     100.0 * NumInferredFunctions / NumAllProfiledFunctions,
+                     100.0 * InferredSampleCount / TotalSampleCount);
+  }
 
   if (const uint64_t NumUnusedObjects = BC.getNumUnusedProfiledObjects()) {
     outs() << "BOLT-INFO: profile for " << NumUnusedObjects
diff --git a/bolt/lib/Profile/CMakeLists.txt b/bolt/lib/Profile/CMakeLists.txt
--- a/bolt/lib/Profile/CMakeLists.txt
+++ b/bolt/lib/Profile/CMakeLists.txt
@@ -4,6 +4,7 @@
   DataReader.cpp
   Heatmap.cpp
   ProfileReaderBase.cpp
+  StaleProfileMatching.cpp
   YAMLProfileReader.cpp
   YAMLProfileWriter.cpp
 
diff --git a/bolt/lib/Profile/StaleProfileMatching.cpp b/bolt/lib/Profile/StaleProfileMatching.cpp
new file mode 100644
--- /dev/null
+++ b/bolt/lib/Profile/StaleProfileMatching.cpp
@@ -0,0 +1,386 @@
+//===- bolt/Profile/StaleProfileMatching.cpp - Profile data matching   ----===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+// Here
+//
+//===----------------------------------------------------------------------===//
+#include "bolt/Core/HashUtilities.h"
+#include "bolt/Profile/YAMLProfileReader.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Transforms/Utils/SampleProfileInference.h"
+
+using namespace llvm;
+
+namespace opts {
+
+extern cl::OptionCategory BoltOptCategory;
+
+llvm::cl::opt<bool>
+    InferStaleProfile("infer-stale-profile",
+                      cl::desc("infer counts from stale profile data"),
+                      cl::init(false), cl::Hidden, cl::cat(BoltOptCategory));
+} // namespace opts
+
+namespace llvm {
+namespace bolt {
+
+/// Create CFG. Initialize function jumps and misc metadata
+void createFlowFunction(const BinaryFunction::BasicBlockOrderType &BlockOrder,
+                        FlowFunction &Func) {
+  // Add a special "dummy" source so that there is always a unique entry point
+  FlowBlock EntryBlock;
+  EntryBlock.Index = 0;
+  Func.Blocks.push_back(EntryBlock);
+
+  // Create FlowBlock for each basic block in the function
+  std::unordered_map<const BinaryBasicBlock *, size_t> BlockIndex;
+  for (const BinaryBasicBlock *BB : BlockOrder) {
+    Func.Blocks.emplace_back();
+    FlowBlock &Block = Func.Blocks.back();
+    Block.Index = Func.Blocks.size() - 1;
+    BlockIndex[BB] = Block.Index;
+    assert(Block.Flow == 0);
+    assert(Block.SuccJumps.empty() && Block.PredJumps.empty());
+  }
+
+  // Create FlowJump for each jump between basic blocks in the function
+  std::vector<uint64_t> InDegree(Func.Blocks.size(), 0);
+  std::vector<uint64_t> OutDegree(Func.Blocks.size(), 0);
+  for (const BinaryBasicBlock *SrcBB : BlockOrder) {
+    for (const BinaryBasicBlock *DstBB : SrcBB->successors()) {
+      Func.Jumps.emplace_back();
+      FlowJump &Jump = Func.Jumps.back();
+      Jump.Source = BlockIndex.at(SrcBB);
+      Jump.Target = BlockIndex.at(DstBB);
+      InDegree[Jump.Target]++;
+      OutDegree[Jump.Source]++;
+    }
+  }
+
+  // Add dummy edges to extra sources
+  // If there are multiple entry blocks, add an unlikely edge from 0 to the
+  // subsequent ones.
+  assert(InDegree[0] == 0 && "dummy entry blocks shouldn't have counts");
+  for (size_t I = 1; I < Func.Blocks.size(); I++) {
+    if (I == 1 || InDegree[I] == 0) {
+      uint64_t Src = 0;
+      uint64_t Dst = I;
+      Func.Jumps.emplace_back();
+      FlowJump &Jump = Func.Jumps.back();
+      Jump.Source = Src;
+      Jump.Target = Dst;
+      if (I > 1)
+        Jump.IsUnlikely = true;
+    }
+  }
+
+  // Create necessary metadata
+  for (auto &Jump : Func.Jumps) {
+    uint64_t Src = Jump.Source;
+    uint64_t Dst = Jump.Target;
+    Func.Blocks.at(Src).SuccJumps.push_back(&Jump);
+    Func.Blocks.at(Dst).PredJumps.push_back(&Jump);
+  }
+}
+
+/// Bla.
+/// Assign initial block/jump weights based on stale profile data. The goal is
+/// to extract as much information from the stale profile data as possible. For
+/// now, we assume each basic block is specified via an address range
+/// [StartAddr, EndAddr). Whenever an address of a (stale) jump is within the
+/// range, the jump is considered to belong (as a source or as a target) to
+/// the basic block. If both the source and the target addresses belong to some
+/// basic blocks, the jump is "matched" and its count is recorded in CFG.
+void matchWeightsByHashes(const BinaryFunction::BasicBlockOrderType &BlockOrder,
+                          const yaml::bolt::BinaryFunctionProfile &YamlBF,
+                          FlowFunction &Func) {
+  assert(Func.Blocks.size() == BlockOrder.size() + 1);
+  // Initialize stale matcher
+  // TODO: maps => DenseMap
+  std::unordered_map<uint16_t, std::vector<FlowBlock *>> HashToBlocks;
+  for (size_t I = 0; I < BlockOrder.size(); I++) {
+    const BinaryBasicBlock *BB = BlockOrder[I];
+    assert(BB->getHash() != 0 && "empty hash of BinaryBasicBlock");
+    HashToBlocks[BB->getHash()].push_back(&Func.Blocks[I + 1]);
+  }
+
+  // Index in yaml profile => correspondent (matched) block
+  std::unordered_map<uint64_t, const FlowBlock *> MatchedBlocks;
+  // Match blocks from the profile to the blocks in CFG
+  for (const yaml::bolt::BinaryBasicBlockProfile &YamlBB : YamlBF.Blocks) {
+    assert(YamlBB.Hash != 0 && "empty hash of BinaryBasicBlockProfile");
+    auto It = HashToBlocks.find(YamlBB.Hash);
+    if (It != HashToBlocks.end()) {
+      const FlowBlock *MatchedBlock = It->second.front();
+      MatchedBlocks[YamlBB.Index] = MatchedBlock;
+    }
+  }
+
+  // Match jumps from the profile to the jumps from CFG
+  std::vector<uint64_t> OutWeight(Func.Blocks.size(), 0);
+  std::vector<uint64_t> InWeight(Func.Blocks.size(), 0);
+  for (const yaml::bolt::BinaryBasicBlockProfile &YamlBB : YamlBF.Blocks) {
+    for (const yaml::bolt::SuccessorInfo &YamlSI : YamlBB.Successors) {
+      if (YamlSI.Count == 0)
+        continue;
+
+      // Try to find the jump for a given (src, dst) pair from the profile and
+      // assign the jump weight based on the profile count
+      uint64_t SrcIndex = YamlBB.Index;
+      uint64_t DstIndex = YamlSI.Index;
+
+      const FlowBlock *MatchedSrcBlock =
+          MatchedBlocks.find(SrcIndex) != MatchedBlocks.end()
+              ? MatchedBlocks[SrcIndex]
+              : nullptr;
+      const FlowBlock *MatchedDstBlock =
+          MatchedBlocks.find(DstIndex) != MatchedBlocks.end()
+              ? MatchedBlocks[DstIndex]
+              : nullptr;
+
+      if (MatchedSrcBlock != nullptr && MatchedDstBlock != nullptr) {
+        // Find a jump between the two blocks
+        FlowJump *Jump = nullptr;
+        for (FlowJump *SuccJump : MatchedSrcBlock->SuccJumps) {
+          if (SuccJump->Target == MatchedDstBlock->Index) {
+            Jump = SuccJump;
+            break;
+          }
+        }
+        // Assign the weight, if the corresponding jump is found
+        if (Jump != nullptr) {
+          Jump->Weight = YamlSI.Count;
+          Jump->HasUnknownWeight = false;
+        }
+      }
+      // Assign the weight for the src block, if it is found
+      if (MatchedSrcBlock != nullptr) {
+        OutWeight[MatchedSrcBlock->Index] += YamlSI.Count;
+      }
+      // Assign the weight for the dst block, if it is found
+      if (MatchedDstBlock != nullptr) {
+        InWeight[MatchedDstBlock->Index] += YamlSI.Count;
+      }
+    }
+  }
+
+  // Assign block counts based on in-/out- jumps
+  for (FlowBlock &Block : Func.Blocks) {
+    if (OutWeight[Block.Index] == 0 && InWeight[Block.Index] == 0) {
+      // Bla
+      assert(Block.HasUnknownWeight);
+      continue;
+    }
+    // Bla
+    Block.HasUnknownWeight = false;
+    Block.Weight = std::max(OutWeight[Block.Index], InWeight[Block.Index]);
+  }
+}
+
+/// The function finds all blocks that are (i) reachable from the Entry block
+/// and (ii) do not have a path to an exit, and marks all such blocks 'cold'
+/// so that profi does not send any flow to such blocks.
+void preprocessUnreachableBlocks(FlowFunction &Func) {
+  const uint64_t NumBlocks = Func.Blocks.size();
+
+  // Start bfs from the source
+  std::queue<uint64_t> Queue;
+  auto VisitedEntry = std::vector<bool>(NumBlocks, false);
+  for (uint64_t I = 0; I < NumBlocks; I++) {
+    auto &Block = Func.Blocks[I];
+    if (Block.isEntry()) {
+      Queue.push(I);
+      VisitedEntry[I] = true;
+      break;
+    }
+  }
+  while (!Queue.empty()) {
+    uint64_t Src = Queue.front();
+    Queue.pop();
+    for (auto Jump : Func.Blocks[Src].SuccJumps) {
+      uint64_t Dst = Jump->Target;
+      if (!VisitedEntry[Dst]) {
+        Queue.push(Dst);
+        VisitedEntry[Dst] = true;
+      }
+    }
+  }
+
+  // Start bfs from all sinks
+  auto VisitedExit = std::vector<bool>(NumBlocks, false);
+  for (uint64_t I = 0; I < NumBlocks; I++) {
+    auto &Block = Func.Blocks[I];
+    if (Block.isExit() && VisitedEntry[I]) {
+      Queue.push(I);
+      VisitedExit[I] = true;
+    }
+  }
+  while (!Queue.empty()) {
+    uint64_t Src = Queue.front();
+    Queue.pop();
+    for (auto Jump : Func.Blocks[Src].PredJumps) {
+      uint64_t Dst = Jump->Source;
+      if (!VisitedExit[Dst]) {
+        Queue.push(Dst);
+        VisitedExit[Dst] = true;
+      }
+    }
+  }
+
+  // Make all blocks of zero weight so that flow is not sent
+  for (uint64_t I = 0; I < NumBlocks; I++) {
+    auto &Block = Func.Blocks[I];
+    if (Block.Weight == 0)
+      continue;
+    if (!VisitedEntry[I] || !VisitedExit[I]) {
+      Block.Weight = 0;
+      Block.HasUnknownWeight = true;
+      Block.IsUnlikely = true;
+    }
+  }
+}
+
+/// Apply the profile inference algorithm for a given flow function
+void applyInference(FlowFunction &Func) {
+  ProfiParams Params;
+  // TODO: make params
+  // Set the params from the command-line flags.
+  Params.EvenFlowDistribution = true;
+  Params.RebalanceUnknown = false;
+  Params.JoinIslands = true;
+
+  Params.CostBlockInc = 110;
+  Params.CostBlockDec = 100;
+  Params.CostBlockEntryInc = 110;
+  Params.CostBlockEntryDec = 100;
+  Params.CostBlockZeroInc = 10;
+  Params.CostBlockUnknownInc = 10;
+
+  Params.CostJumpInc = 100;
+  Params.CostJumpFTInc = 100;
+  Params.CostJumpDec = 110;
+  Params.CostJumpFTDec = 110;
+  Params.CostJumpUnknownInc = 50;
+  Params.CostJumpUnknownFTInc = 5;
+
+  applyFlowInferenceBOLT(Params, Func);
+}
+
+/// Bla.
+void assignAnnotations(BinaryFunction &BF,
+                       const BinaryFunction::BasicBlockOrderType &BlockOrder,
+                       FlowFunction &Func) {
+  BinaryContext &BC = BF.getBinaryContext();
+
+  assert(Func.Blocks.size() == BlockOrder.size() + 1);
+  for (size_t I = 0; I < BlockOrder.size(); I++) {
+    FlowBlock &Block = Func.Blocks[I + 1];
+    BinaryBasicBlock *BB = BlockOrder[I];
+
+    // Update block's count
+    BB->setExecutionCount(Block.Flow);
+
+    // Update jump counts: (i) clean existing counts and then (ii) set new ones
+    auto BI = BB->branch_info_begin();
+    for (const BinaryBasicBlock *DstBB : BB->successors()) {
+      (void)DstBB;
+      BI->Count = 0;
+      BI->MispredictedCount = 0;
+      ++BI;
+    }
+    for (FlowJump *Jump : Block.SuccJumps) {
+      if (Jump->IsUnlikely)
+        continue;
+      BinaryBasicBlock &SuccBB = *BlockOrder[Jump->Target - 1];
+      BinaryBasicBlock::BinaryBranchInfo &BI = BB->getBranchInfo(SuccBB);
+      BI.Count += Jump->Flow;
+    }
+
+    // Update call-site annotations
+    auto setOrUpdateAnnotation = [&](MCInst &Instr, StringRef Name,
+                                     uint64_t Count) {
+      if (BC.MIB->hasAnnotation(Instr, Name)) {
+        BC.MIB->removeAnnotation(Instr, Name);
+      }
+      // Do not add zero-count annotations
+      if (Count == 0)
+        return;
+      BC.MIB->addAnnotation(Instr, Name, Count);
+    };
+
+    for (MCInst &Instr : *BB) {
+      // Ignore pseudo instructions
+      if (BC.MIB->isPseudo(Instr))
+        continue;
+      // Ignore jump tables
+      const MCInst *LastInstr = BB->getLastNonPseudoInstr();
+      if (BC.MIB->getJumpTable(*LastInstr) && LastInstr == &Instr)
+        continue;
+
+      if (BC.MIB->isIndirectCall(Instr) || BC.MIB->isIndirectBranch(Instr)) {
+        auto &ICSP = BC.MIB->getOrCreateAnnotationAs<IndirectCallSiteProfile>(
+            Instr, "CallProfile");
+        if (!ICSP.empty()) {
+          // Try to evenly distribute the counts among the call sites
+          uint64_t TotalCount = Block.Flow;
+          uint64_t NumSites = ICSP.size();
+          for (size_t Idx = 0; Idx < ICSP.size(); Idx++) {
+            IndirectCallProfile &CSP = ICSP[Idx];
+            uint64_t CountPerSite = TotalCount / NumSites;
+            // When counts cannot be exactly distributed, increase by 1 the
+            // counts of the first (TotalCount % NumSites) call sites
+            if (Idx < TotalCount % NumSites)
+              CountPerSite++;
+            CSP.Count = CountPerSite;
+          }
+        } else {
+          ICSP.emplace_back(nullptr, Block.Flow, 0);
+        }
+      } else if (BC.MIB->getConditionalTailCall(Instr)) {
+        // TODO: this isn't quite correct
+        setOrUpdateAnnotation(Instr, "CTCTakenCount", Block.Flow);
+        setOrUpdateAnnotation(Instr, "CTCMispredCount", 0);
+      } else if (BC.MIB->isCall(Instr)) {
+        setOrUpdateAnnotation(Instr, "Count", Block.Flow);
+      }
+    }
+  }
+
+  // Update function's execution count and mark the function inferred.
+  BF.setExecutionCount(Func.Blocks[0].Flow);
+  BF.setHasInferredProfile(true);
+}
+
+bool YAMLProfileReader::inferStaleProfile(
+    BinaryFunction &BF, const yaml::bolt::BinaryFunctionProfile &YamlBF) {
+  // Make sure that block indices and hashes are up to date
+  BF.getLayout().updateLayoutIndices();
+  BF.computeBlockHashes();
+
+  BinaryFunction::BasicBlockOrderType BlockOrder(BF.getLayout().block_begin(),
+                                                 BF.getLayout().block_end());
+
+  // readCFG
+  FlowFunction Func;
+  createFlowFunction(BlockOrder, Func);
+
+  // matchWeightsWithHash
+  matchWeightsByHashes(BlockOrder, YamlBF, Func);
+
+  // preprocessUnreachableBlocks
+  preprocessUnreachableBlocks(Func);
+
+  // Apply profile inference
+  applyInference(Func);
+
+  // Collect inferred counts and update function annotation
+  assignAnnotations(BF, BlockOrder, Func);
+
+  return true;
+}
+
+} // end namespace bolt
+} // end namespace llvm
diff --git a/bolt/lib/Profile/YAMLProfileReader.cpp b/bolt/lib/Profile/YAMLProfileReader.cpp
--- a/bolt/lib/Profile/YAMLProfileReader.cpp
+++ b/bolt/lib/Profile/YAMLProfileReader.cpp
@@ -20,6 +20,7 @@
 
 extern cl::opt<unsigned> Verbosity;
 extern cl::OptionCategory BoltOptCategory;
+extern cl::opt<bool> InferStaleProfile;
 
 static llvm::cl::opt<bool>
     IgnoreHash("profile-ignore-hash",
@@ -241,6 +242,13 @@
            << MismatchedCalls << " calls, and " << MismatchedEdges
            << " edges in profile did not match function " << BF << '\n';
 
+  if (!ProfileMatched && opts::InferStaleProfile) {
+    if (inferStaleProfile(BF, YamlBF)) {
+      ProfileMatched = true;
+      BF.markProfiled(YamlBP.Header.Flags);
+    }
+  }
+
   return ProfileMatched;
 }
 
diff --git a/llvm/include/llvm/Transforms/Utils/SampleProfileInference.h b/llvm/include/llvm/Transforms/Utils/SampleProfileInference.h
--- a/llvm/include/llvm/Transforms/Utils/SampleProfileInference.h
+++ b/llvm/include/llvm/Transforms/Utils/SampleProfileInference.h
@@ -135,6 +135,7 @@
 };
 
 void applyFlowInference(const ProfiParams &Params, FlowFunction &Func);
+void applyFlowInferenceBOLT(const ProfiParams &Params, FlowFunction &Func);
 void applyFlowInference(FlowFunction &Func);
 
 /// Sample profile inference pass.
diff --git a/llvm/lib/Transforms/Utils/SampleProfileInference.cpp b/llvm/lib/Transforms/Utils/SampleProfileInference.cpp
--- a/llvm/lib/Transforms/Utils/SampleProfileInference.cpp
+++ b/llvm/lib/Transforms/Utils/SampleProfileInference.cpp
@@ -1329,6 +1329,48 @@
 #endif
 }
 
+/// Apply the profile inference algorithm for a given function
+void llvm::applyFlowInferenceBOLT(const ProfiParams &Params,
+                                  FlowFunction &Func) {
+  // Check if the function has samples and assign initial flow values
+  bool HasSamples = false;
+  for (auto &Block : Func.Blocks) {
+    if (Block.Weight > 0) {
+      HasSamples = true;
+    }
+    Block.Flow = Block.Weight;
+  }
+  for (auto &Jump : Func.Jumps) {
+    if (Jump.Weight > 0) {
+      HasSamples = true;
+    }
+    Jump.Flow = Jump.Weight;
+  }
+
+  // Quit early for functions with a single block or ones w/o samples
+  if (Func.Blocks.size() <= 1 || !HasSamples) {
+    return;
+  }
+
+  // Verify the input data
+  verifyInput(Func);
+
+  // Create and apply an inference network model
+  auto InferenceNetwork = MinCostMaxFlow(Params);
+  initializeNetwork(Params, InferenceNetwork, Func);
+  InferenceNetwork.run();
+
+  // Extract flow values for every block and every edge
+  extractWeights(Params, InferenceNetwork, Func);
+
+  // Post-processing adjustments to the flow
+  auto Adjuster = FlowAdjuster(Params, Func);
+  Adjuster.run();
+
+  // Verify the result
+  verifyOutput(Func);
+}
+
 /// Apply the profile inference algorithm for a given flow function
 void llvm::applyFlowInference(FlowFunction &Func) {
   ProfiParams Params;