[BOLT] Increase coverage of shrink wrapping [1/5]

[rafauler]

Summary

Change how function score is calculated and provide more
detailed statistics when reporting back frame optimizer and shrink
wrapping results. In this new statistics, we provide dynamic coverage
numbers. The main metric for shrink wrapping is the number of executed
stores that were saved because of shrink wrapping (push instructions
that were either entirely moved away from the hot block or converted
to a stack adjustment instruction). There is still a number of reduced
load instructions (pop) that we are not counting at the moment. Also
update alloc combiner to report dynamic numbers, as well as frame
optimizer.

For debugging purposes, we also include a list of top 10 functions
optimized by shrink wrapping. These changes are aimed at better
understanding the impact of shrink wrapping in a given binary.

We also remove an assertion in dataflow analysis to do not choke on
empty functions (which makes no sense).

[Amir]

bolt/include/bolt/Passes/ShrinkWrapping.h

522

clang-format?

[rafauler]

Fix formatting

[Amir]

LGTM, at least the code changes match the description.
One quick question: does this diff result in a functional change because the score is computed differently? Or the change from getKnownExecutionCount == 0 to getFunctionScore == 0 shouldn't result in a functional change?

[rafauler]

You're right that it does result in functional changes.

bolt/include/bolt/Passes/AllocCombiner.h

 #include "bolt/Passes/BinaryPasses.h"
 
 namespace llvm {
 namespace bolt {
 
 class AllocCombinerPass : public BinaryFunctionPass {
   /// Stats aggregating variables
   uint64_t NumCombined{0};
+  uint64_t DynamicCountCombined{0};
   DenseSet<const BinaryFunction *> FuncsChanged;
 
   void combineAdjustments(BinaryFunction &BF);
 
 public:
   explicit AllocCombinerPass(const cl::opt<bool> &PrintPass)
       : BinaryFunctionPass(PrintPass) {}
 

bolt/include/bolt/Passes/DataflowAnalysis.h

void cleanAnnotations() {
     }
   }
 
   /// Public entry point that will perform the entire analysis form start to
   /// end.
   void run() {
     derived().preflight();
 
+    if (Func.begin() == Func.end())
+      return;
     // Initialize state for all points of the function
     for (BinaryBasicBlock &BB : Func) {
       StateTy &St = getOrCreateStateAt(BB);
       St = derived().getStartingStateAtBB(BB);
       for (MCInst &Inst : BB) {
         StateTy &St = getOrCreateStateAt(Inst);
         St = derived().getStartingStateAtPoint(Inst);
       }
     }
-    assert(Func.begin() != Func.end() && "Unexpected empty function");
 
     std::queue<BinaryBasicBlock *> Worklist;
     // TODO: Pushing this in a DFS ordering will greatly speed up the dataflow
     // performance.
     if (!Backward) {
       for (BinaryBasicBlock &BB : Func) {
         Worklist.push(&BB);
         MCInst *Prev = nullptr;

bolt/include/bolt/Passes/FrameAnalysis.h

class FrameAnalysis {
   /// attached to instructions as indexes to this vector, in MCAnnotations.
   std::vector<ArgAccesses> ArgAccessesVector;
   /// Same for FrameIndexEntries.
   std::vector<FrameIndexEntry> FIEVector;
 
   /// Analysis stats counters
   uint64_t NumFunctionsNotOptimized{0};
   uint64_t NumFunctionsFailedRestoreFI{0};
-  uint64_t CountFunctionsNotOptimized{0};
   uint64_t CountFunctionsFailedRestoreFI{0};
   uint64_t CountDenominator{0};
 
   /// Convenience functions for appending MCAnnotations to instructions with
   /// our specific data
   void addArgAccessesFor(MCInst &Inst, ArgAccesses &&AA);
   void addArgInStackAccessFor(MCInst &Inst, const ArgInStackAccess &Arg);
   void addFIEFor(MCInst &Inst, const FrameIndexEntry &FIE);

bolt/include/bolt/Passes/FrameOptimizer.h

 /// Finally, another analysis propagates information about which instructions
 /// are using (loading from) a stack position -- see StackReachingUses. If a
 /// store sees no use of the value it is storing, it is eliminated.
 ///
 class FrameOptimizerPass : public BinaryFunctionPass {
   /// Stats aggregating variables
   uint64_t NumRedundantLoads{0};
   uint64_t NumRedundantStores{0};
-  uint64_t NumLoadsChangedToReg{0};
-  uint64_t NumLoadsChangedToImm{0};
+  uint64_t FreqRedundantLoads{0};
+  uint64_t FreqRedundantStores{0};
+  uint64_t FreqLoadsChangedToReg{0};
+  uint64_t FreqLoadsChangedToImm{0};
   uint64_t NumLoadsDeleted{0};
+  uint64_t FreqLoadsDeleted{0};
 
   DenseSet<const BinaryFunction *> FuncsChanged;
 
   std::mutex FuncsChangedMutex;
 
   /// Perform a dataflow analysis in \p BF to reveal unnecessary reloads from
   /// the frame. Use the analysis to convert memory loads to register moves or
   /// immediate loads. Delete redundant register moves.

bolt/include/bolt/Passes/ShrinkWrapping.h

class ShrinkWrapping {
   CalleeSavedAnalysis CSA;
   std::vector<SmallSetVector<MCInst *, 4>> SavePos;
   std::vector<uint64_t> BestSaveCount;
   std::vector<MCInst *> BestSavePos;
 
   /// Pass stats
   static std::atomic_uint64_t SpillsMovedRegularMode;
   static std::atomic_uint64_t SpillsMovedPushPopMode;
+  static std::atomic_uint64_t SpillsMovedDynamicCount;
+  static std::atomic_uint64_t SpillsFailedDynamicCount;
+  static std::atomic_uint64_t InstrDynamicCount;
+  static std::atomic_uint64_t StoreDynamicCount;
 
   Optional<unsigned> AnnotationIndex;
 
   /// Allow our custom worklist-sensitive analysis
   /// PredictiveStackPointerTracking to access WorklistItem
 public:
   struct WorklistItem {
     enum ActionType : uint8_t {
ShrinkWrapping(const FrameAnalysis &FA, BinaryFunction &BF,
         CSA(FA, BF, Info, AllocId) {}
 
   ~ShrinkWrapping() {
     for (BinaryBasicBlock &BB : BF)
       for (MCInst &Inst : BB)
         BC.MIB->removeAnnotation(Inst, getAnnotationIndex());
   }
 
-  bool perform();
+  bool perform(bool HotOnly = false);
 
   static void printStats();
 };
 
 } // end namespace bolt
 } // end namespace llvm
 
 #endif

bolt/lib/Core/BinaryFunction.cpp

if (!isSimple() || !hasValidProfile()) {
     return FunctionScore;
   }
 
   uint64_t TotalScore = 0ULL;
   for (BinaryBasicBlock *BB : layout()) {
     uint64_t BBExecCount = BB->getExecutionCount();
     if (BBExecCount == BinaryBasicBlock::COUNT_NO_PROFILE)
       continue;
-    TotalScore += BBExecCount;
+    TotalScore += BBExecCount * BB->getNumNonPseudos();
   }
   FunctionScore = TotalScore;
   return FunctionScore;
 }
 
 void BinaryFunction::annotateCFIState() {
   assert(CurrentState == State::Disassembled && "unexpected function state");
   assert(!BasicBlocks.empty() && "basic block list should not be empty");

bolt/lib/Passes/AllocCombiner.cpp

for (auto I = BB.rbegin(), E = BB.rend(); I != E; ++I) {
 
       LLVM_DEBUG({
         dbgs() << "After adjustment:\n";
         Inst.dump();
       });
 
       BB.eraseInstruction(BB.findInstruction(Prev));
       ++NumCombined;
+      DynamicCountCombined += BB.getKnownExecutionCount();
       FuncsChanged.insert(&BF);
       Prev = &Inst;
     }
   }
 }
 
 void AllocCombinerPass::runOnFunctions(BinaryContext &BC) {
   if (opts::FrameOptimization == FOP_NONE)
     return;
 
   runForAllWeCare(BC.getBinaryFunctions(), [&](BinaryFunction &Function) {
     combineAdjustments(Function);
   });
 
   outs() << "BOLT-INFO: Allocation combiner: " << NumCombined
-         << " empty spaces coalesced.\n";
+         << " empty spaces coalesced (dyn count: " << DynamicCountCombined
+         << ").\n";
 }
 
 } // end namespace bolt
 } // end namespace llvm

bolt/lib/Passes/FrameAnalysis.cpp

FrameAnalysis::FrameAnalysis(BinaryContext &BC, BinaryFunctionCallGraph &CG)
 
   {
     NamedRegionTimer T1("traversecg", "traverse call graph", "FA",
                         "FA breakdown", opts::TimeFA);
     traverseCG(CG);
   }
 
   for (auto &I : BC.getBinaryFunctions()) {
-    uint64_t Count = I.second.getExecutionCount();
-    if (Count != BinaryFunction::COUNT_NO_PROFILE)
-      CountDenominator += Count;
+    CountDenominator += I.second.getFunctionScore();
 
     // "shouldOptimize" for passes that run after finalize
     if (!(I.second.isSimple() && I.second.hasCFG() && !I.second.isIgnored()) ||
         !opts::shouldFrameOptimize(I.second)) {
       ++NumFunctionsNotOptimized;
-      if (Count != BinaryFunction::COUNT_NO_PROFILE)
-        CountFunctionsNotOptimized += Count;
       continue;
     }
 
     {
       NamedRegionTimer T1("restorefi", "restore frame index", "FA",
                           "FA breakdown", opts::TimeFA);
       if (!restoreFrameIndex(I.second)) {
         ++NumFunctionsFailedRestoreFI;
-        uint64_t Count = I.second.getExecutionCount();
-        if (Count != BinaryFunction::COUNT_NO_PROFILE)
-          CountFunctionsFailedRestoreFI += Count;
+        CountFunctionsFailedRestoreFI += I.second.getFunctionScore();
         continue;
       }
     }
     AnalyzedFunctions.insert(&I.second);
   }
 
   {
     NamedRegionTimer T1("clearspt", "clear spt", "FA", "FA breakdown",
                         opts::TimeFA);
     clearSPTMap();
 
     // Clean up memory allocated for annotation values
     if (!opts::NoThreads)
       for (MCPlusBuilder::AllocatorIdTy Id : SPTAllocatorsId)
         BC.MIB->freeValuesAllocator(Id);
   }
 }
 
 void FrameAnalysis::printStats() {
   outs() << "BOLT-INFO: FRAME ANALYSIS: " << NumFunctionsNotOptimized
-         << " function(s) "
-         << format("(%.1lf%% dyn cov)",
-                   (100.0 * CountFunctionsNotOptimized / CountDenominator))
-         << " were not optimized.\n"
+         << " function(s) were not optimized.\n"
          << "BOLT-INFO: FRAME ANALYSIS: " << NumFunctionsFailedRestoreFI
          << " function(s) "
          << format("(%.1lf%% dyn cov)",
                    (100.0 * CountFunctionsFailedRestoreFI / CountDenominator))
          << " could not have its frame indices restored.\n";
 }
 
 void FrameAnalysis::clearSPTMap() {

bolt/lib/Passes/FrameOptimizer.cpp

for (MCInst &Inst : BB) {
         assert(FIEY->IsStore && FIEY->IsSimple);
         if (FIEX->StackOffset != FIEY->StackOffset || FIEX->Size != FIEY->Size)
           continue;
         // TODO: Change push/pops to stack adjustment instruction
         if (MIB->isPop(Inst))
           continue;
 
         ++NumRedundantLoads;
+        FreqRedundantLoads += BB.getKnownExecutionCount();
         Changed = true;
         LLVM_DEBUG(dbgs() << "Redundant load instruction: ");
         LLVM_DEBUG(Inst.dump());
         LLVM_DEBUG(dbgs() << "Related store instruction: ");
         LLVM_DEBUG(AvailableInst->dump());
         LLVM_DEBUG(dbgs() << "@BB: " << BB.getName() << "\n");
         // Replace load
         if (FIEY->IsStoreFromReg) {
           if (!MIB->replaceMemOperandWithReg(Inst, FIEY->RegOrImm)) {
             LLVM_DEBUG(dbgs() << "FAILED to change operand to a reg\n");
             break;
           }
-          ++NumLoadsChangedToReg;
+          FreqLoadsChangedToReg += BB.getKnownExecutionCount();
           MIB->removeAnnotation(Inst, "FrameAccessEntry");
           LLVM_DEBUG(dbgs() << "Changed operand to a reg\n");
           if (MIB->isRedundantMove(Inst)) {
             ++NumLoadsDeleted;
+            FreqLoadsDeleted += BB.getKnownExecutionCount();
             LLVM_DEBUG(dbgs() << "Created a redundant move\n");
             // Delete it!
             ToErase.push_front(std::make_pair(&BB, &Inst));
           }
         } else {
           char Buf[8] = {0, 0, 0, 0, 0, 0, 0, 0};
           support::ulittle64_t::ref(Buf + 0) = FIEY->RegOrImm;
           LLVM_DEBUG(dbgs() << "Changing operand to an imm... ");
           if (!MIB->replaceMemOperandWithImm(Inst, StringRef(Buf, 8), 0)) {
             LLVM_DEBUG(dbgs() << "FAILED\n");
           } else {
-            ++NumLoadsChangedToImm;
+            FreqLoadsChangedToImm += BB.getKnownExecutionCount();
             MIB->removeAnnotation(Inst, "FrameAccessEntry");
             LLVM_DEBUG(dbgs() << "Ok\n");
           }
         }
         LLVM_DEBUG(dbgs() << "Changed to: ");
         LLVM_DEBUG(Inst.dump());
         break;
       }
for (auto I = BB.rbegin(), E = BB.rend(); I != E; ++I) {
         Prev = &Inst;
         continue;
       }
       // TODO: Change push/pops to stack adjustment instruction
       if (BF.getBinaryContext().MIB->isPush(Inst))
         continue;
 
       ++NumRedundantStores;
+      FreqRedundantStores += BB.getKnownExecutionCount();
       Changed = true;
       LLVM_DEBUG(dbgs() << "Unused store instruction: ");
       LLVM_DEBUG(Inst.dump());
       LLVM_DEBUG(dbgs() << "@BB: " << BB.getName() << "\n");
       LLVM_DEBUG(dbgs() << "FIE offset = " << FIEX->StackOffset
                         << " size = " << (int)FIEX->Size << "\n");
       // Delete it!
       ToErase.emplace_back(&BB, &Inst);
for (auto &I : BC.getBinaryFunctions()) {
     NamedRegionTimer T1("shrinkwrapping", "shrink wrapping", "FOP",
                         "FOP breakdown", opts::TimeOpts);
     performShrinkWrapping(*RA, *FA, BC);
   }
 
   outs() << "BOLT-INFO: FOP optimized " << NumRedundantLoads
          << " redundant load(s) and " << NumRedundantStores
          << " unused store(s)\n";
-  outs() << "BOLT-INFO: FOP changed " << NumLoadsChangedToReg
-         << " load(s) to use a register instead of a stack access, and "
-         << NumLoadsChangedToImm << " to use an immediate.\n"
-         << "BOLT-INFO: FOP deleted " << NumLoadsDeleted << " load(s) and "
-         << NumRedundantStores << " store(s).\n";
+  outs() << "BOLT-INFO: Frequency of redundant loads is " << FreqRedundantLoads
+         << " and frequency of unused stores is " << FreqRedundantStores
+         << "\n";
+  outs() << "BOLT-INFO: Frequency of loads changed to use a register is "
+         << FreqLoadsChangedToReg
+         << " and frequency of loads changed to use an immediate is "
+         << FreqLoadsChangedToImm << "\n";
+  outs() << "BOLT-INFO: FOP deleted " << NumLoadsDeleted
+         << " load(s) (dyn count: " << FreqLoadsDeleted << ") and "
+         << NumRedundantStores << " store(s)\n";
   FA->printStats();
   ShrinkWrapping::printStats();
 }
 
 void FrameOptimizerPass::performShrinkWrapping(const RegAnalysis &RA,
                                                const FrameAnalysis &FA,
                                                BinaryContext &BC) {
   // Initialize necessary annotations to allow safe parallel accesses to
void FrameOptimizerPass::performShrinkWrapping(const RegAnalysis &RA,
   BC.MIB->getOrCreateAnnotationIndex("StackAllocationAnalysis");
   BC.MIB->getOrCreateAnnotationIndex("ShrinkWrap-Todo");
   BC.MIB->getOrCreateAnnotationIndex("PredictiveStackPointerTracking");
   BC.MIB->getOrCreateAnnotationIndex("ReachingInsnsBackward");
   BC.MIB->getOrCreateAnnotationIndex("ReachingInsns");
   BC.MIB->getOrCreateAnnotationIndex("AccessesDeletedPos");
   BC.MIB->getOrCreateAnnotationIndex("DeleteMe");
 
-  ParallelUtilities::PredicateTy SkipPredicate = [&](const BinaryFunction &BF) {
-    if (!FA.hasFrameInfo(BF))
-      return true;
-
-    if (opts::FrameOptimization == FOP_HOT &&
-        (BF.getKnownExecutionCount() < BC.getHotThreshold()))
-      return true;
+  std::vector<std::pair<uint64_t, const BinaryFunction *>> Top10Funcs;
+  auto LogFunc = [&](BinaryFunction &BF) {
+    auto Lower = std::lower_bound(
+        Top10Funcs.begin(), Top10Funcs.end(), BF.getKnownExecutionCount(),
+        [](const std::pair<uint64_t, const BinaryFunction *> &Elmt,
+           uint64_t Value) { return Elmt.first > Value; });
+    if (Lower == Top10Funcs.end() && Top10Funcs.size() >= 10)
+      return;
+    Top10Funcs.insert(Lower,
+                      std::make_pair<>(BF.getKnownExecutionCount(), &BF));
+    if (Top10Funcs.size() > 10)
+      Top10Funcs.resize(10);
+  };
+  (void)LogFunc;
 
-    if (BF.getKnownExecutionCount() == 0)
+  ParallelUtilities::PredicateTy SkipPredicate = [&](const BinaryFunction &BF) {
+    if (BF.getFunctionScore() == 0)
       return true;
 
     return false;
   };
 
+  const bool HotOnly = opts::FrameOptimization == FOP_HOT;
+
   ParallelUtilities::WorkFuncWithAllocTy WorkFunction =
       [&](BinaryFunction &BF, MCPlusBuilder::AllocatorIdTy AllocatorId) {
         DataflowInfoManager Info(BF, &RA, &FA, AllocatorId);
         ShrinkWrapping SW(FA, BF, Info, AllocatorId);
 
-        if (SW.perform()) {
+        if (SW.perform(HotOnly)) {
           std::lock_guard<std::mutex> Lock(FuncsChangedMutex);
           FuncsChanged.insert(&BF);
+          LLVM_DEBUG(LogFunc(BF));
         }
       };
 
   ParallelUtilities::runOnEachFunctionWithUniqueAllocId(
       BC, ParallelUtilities::SchedulingPolicy::SP_INST_QUADRATIC, WorkFunction,
       SkipPredicate, "shrink-wrapping");
+
+  if (!Top10Funcs.empty()) {
+    outs() << "BOLT-INFO: top 10 functions changed by shrink wrapping:\n";
+    for (const auto &Elmt : Top10Funcs)
+      outs() << Elmt.first << " : " << Elmt.second->getPrintName() << "\n";
+  }
 }
 
 } // namespace bolt
 } // namespace llvm

bolt/lib/Passes/ShrinkWrapping.cpp

 void StackLayoutModifier::initialize() {
   classifyStackAccesses();
   classifyCFIs();
   IsInitialized = true;
 }
 
 std::atomic_uint64_t ShrinkWrapping::SpillsMovedRegularMode{0};
 std::atomic_uint64_t ShrinkWrapping::SpillsMovedPushPopMode{0};
+std::atomic_uint64_t ShrinkWrapping::SpillsMovedDynamicCount{0};
+std::atomic_uint64_t ShrinkWrapping::SpillsFailedDynamicCount{0};
+std::atomic_uint64_t ShrinkWrapping::InstrDynamicCount{0};
+std::atomic_uint64_t ShrinkWrapping::StoreDynamicCount{0};
 
 using BBIterTy = BinaryBasicBlock::iterator;
 
 void ShrinkWrapping::classifyCSRUses() {
   DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();
   StackPointerTracking &SPT = Info.getStackPointerTracking();
   UsesByReg = std::vector<BitVector>(BC.MRI->getNumRegs(),
                                      BitVector(DA.NumInstrs, false));

 }
 
 void ShrinkWrapping::moveSaveRestores() {
   bool DisablePushPopMode = false;
   bool UsedPushPopMode = false;
   // Keeps info about successfully moved regs: reg index, save position and
   // save size
   std::vector<std::tuple<unsigned, MCInst *, size_t>> MovedRegs;
+  uint64_t TotalEstimatedWin = 0;
 
   for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {
     MCInst *BestPosSave = nullptr;
-    uint64_t TotalEstimatedWin = 0;
-    if (!isBestSavePosCold(I, BestPosSave, TotalEstimatedWin))
+    uint64_t EstimatedWin = 0;
+    if (!isBestSavePosCold(I, BestPosSave, EstimatedWin))
       continue;
     SmallVector<ProgramPoint, 4> RestorePoints =
-        doRestorePlacement(BestPosSave, I, TotalEstimatedWin);
-    if (RestorePoints.empty())
+        doRestorePlacement(BestPosSave, I, EstimatedWin);
+    if (RestorePoints.empty()) {
+      SpillsFailedDynamicCount += EstimatedWin;
       continue;
+    }
 
     const FrameIndexEntry *FIESave = CSA.SaveFIEByReg[I];
     const FrameIndexEntry *FIELoad = CSA.LoadFIEByReg[I];
     (void)FIELoad;
     assert(FIESave && FIELoad);
     StackPointerTracking &SPT = Info.getStackPointerTracking();
     const std::pair<int, int> SPFP = *SPT.getStateBefore(*BestPosSave);
     int SaveOffset = SPFP.first;
     uint8_t SaveSize = FIESave->Size;
 
     // If we don't know stack state at this point, bail
     if ((SPFP.first == SPT.SUPERPOSITION || SPFP.first == SPT.EMPTY) &&
-        (SPFP.second == SPT.SUPERPOSITION || SPFP.second == SPT.EMPTY))
+        (SPFP.second == SPT.SUPERPOSITION || SPFP.second == SPT.EMPTY)) {
+      SpillsFailedDynamicCount += EstimatedWin;
       continue;
+    }
 
     // Operation mode: if true, will insert push/pops instead of loads/restores
     bool UsePushPops = validatePushPopsMode(I, BestPosSave, SaveOffset);
 
     if (UsePushPops) {
       SmallVector<ProgramPoint, 4> FixedRestorePoints =
           fixPopsPlacements(RestorePoints, SaveOffset, I);
       if (FixedRestorePoints.empty())
         UsePushPops = false;
       else
         RestorePoints = FixedRestorePoints;
     }
 
     // Disable push-pop mode for all CSRs in this function
     if (!UsePushPops)
       DisablePushPopMode = true;
     else
       UsedPushPopMode = true;
 
     scheduleOldSaveRestoresRemoval(I, UsePushPops);
     scheduleSaveRestoreInsertions(I, BestPosSave, RestorePoints, UsePushPops);
     MovedRegs.emplace_back(std::make_tuple(I, BestPosSave, SaveSize));
+    TotalEstimatedWin += EstimatedWin;
   }
 
   // Revert push-pop mode if it failed for a single CSR
   if (DisablePushPopMode && UsedPushPopMode) {
     UsedPushPopMode = false;
     for (BinaryBasicBlock &BB : BF) {
       auto WRI = Todo.find(&BB);
       if (WRI != Todo.end()) {
for (BinaryBasicBlock &BB : BF) {
           if (Item.Action == WorklistItem::InsertPushOrPop)
             Item.Action = WorklistItem::InsertLoadOrStore;
           if (!isCFI && Item.Action == WorklistItem::Erase)
             Item.Action = WorklistItem::ChangeToAdjustment;
         }
       }
     }
   }
+  SpillsMovedDynamicCount += TotalEstimatedWin;
 
   // Update statistics
   if (!UsedPushPopMode) {
     SpillsMovedRegularMode += MovedRegs.size();
     return;
   }
 
   // Schedule modifications to stack-accessing instructions via
if (PushOffsetByReg[I] == 0 || PopOffsetByReg[I] == 0)
       continue;
     const int64_t SPValPush = PushOffsetByReg[I];
     const int64_t SPValPop = PopOffsetByReg[I];
     insertUpdatedCFI(I, SPValPush, SPValPop);
     Info.invalidateAll();
   }
 }
 
-bool ShrinkWrapping::perform() {
+bool ShrinkWrapping::perform(bool HotOnly) {
   HasDeletedOffsetCFIs = BitVector(BC.MRI->getNumRegs(), false);
   PushOffsetByReg = std::vector<int64_t>(BC.MRI->getNumRegs(), 0LL);
   PopOffsetByReg = std::vector<int64_t>(BC.MRI->getNumRegs(), 0LL);
   DomOrder = std::vector<MCPhysReg>(BC.MRI->getNumRegs(), 0);
 
+  // Update pass statistics
+  uint64_t TotalInstrs = 0ULL;
+  uint64_t TotalStoreInstrs = 0ULL;
+  for (BinaryBasicBlock *BB : BF.layout()) {
+    uint64_t BBExecCount = BB->getExecutionCount();
+    if (!BBExecCount || BBExecCount == BinaryBasicBlock::COUNT_NO_PROFILE)
+      continue;
+    for (const auto &Instr : *BB) {
+      if (BC.MIB->isPseudo(Instr))
+        continue;
+      if (BC.MIB->isStore(Instr))
+        TotalStoreInstrs += BBExecCount;
+      TotalInstrs += BBExecCount;
+    }
+  }
+  InstrDynamicCount += TotalInstrs;
+  StoreDynamicCount += TotalStoreInstrs;
+
+  if (!FA.hasFrameInfo(BF))
+    return false;
+
+  if (HotOnly && (BF.getKnownExecutionCount() < BC.getHotThreshold()))
+    return false;
+
   if (BF.checkForAmbiguousJumpTables()) {
     LLVM_DEBUG(dbgs() << "BOLT-DEBUG: ambiguous JTs in " << BF.getPrintName()
                       << ".\n");
     // We could call disambiguateJumpTables here, but it is probably not worth
     // the cost (of duplicating potentially large jump tables that could regress
     // dcache misses). Moreover, ambiguous JTs are rare and coming from code
     // written in assembly language. Just bail.
     return false;
bool ShrinkWrapping::perform(bool HotOnly) {
   });
   return true;
 }
 
 void ShrinkWrapping::printStats() {
   outs() << "BOLT-INFO: Shrink wrapping moved " << SpillsMovedRegularMode
          << " spills inserting load/stores and " << SpillsMovedPushPopMode
          << " spills inserting push/pops\n";
+  if (!InstrDynamicCount || !StoreDynamicCount)
+    return;
+  outs() << "BOLT-INFO: Shrink wrapping reduced " << SpillsMovedDynamicCount
+         << " store executions ("
+         << format("%.1lf%%",
+                   (100.0 * SpillsMovedDynamicCount / InstrDynamicCount))
+         << " total instructions executed, "
+         << format("%.1lf%%",
+                   (100.0 * SpillsMovedDynamicCount / StoreDynamicCount))
+         << " store instructions)\n";
+  outs() << "BOLT-INFO: Shrink wrapping failed at reducing "
+         << SpillsFailedDynamicCount << " store executions ("
+         << format("%.1lf%%",
+                   (100.0 * SpillsFailedDynamicCount / InstrDynamicCount))
+         << " total instructions executed, "
+         << format("%.1lf%%",
+                   (100.0 * SpillsFailedDynamicCount / StoreDynamicCount))
+         << " store instructions)\n";
 }
 
 // Operators necessary as a result of using MCAnnotation
 raw_ostream &operator<<(raw_ostream &OS,
                         const std::vector<ShrinkWrapping::WorklistItem> &Vec) {
   OS << "SWTodo[";
   const char *Sep = "";
   for (const ShrinkWrapping::WorklistItem &Item : Vec) {

bolt/test/X86/shrinkwrapping-pop-order.s

 # push and pop will be sinked into this block.
 a:
     ud2
     .cfi_endproc
 
 
 # Check shrink wrapping results:
 # CHECK: BOLT-INFO: Shrink wrapping moved 0 spills inserting load/stores and 2 spills inserting push/pops
+# CHECK: BOLT-INFO: Shrink wrapping reduced 6 store executions (28.6% total instructions executed, 100.0% store instructions)
+# CHECK: BOLT-INFO: Shrink wrapping failed at reducing 0 store executions (0.0% total instructions executed, 0.0% store instructions)
 
 # Check that order is correct
 # CHECK:      Binary Function "_start" after frame-optimizer
 # Pushes are ordered according to their reg number and come first
 # CHECK:      pushq   %rbp
 # CHECK:      pushq   %rbx
 # Pops are ordered according to their dominance relation and come last
 # CHECK:      popq    %rbx
 # CHECK:      popq    %rbp