bolt/lib/Passes/FrameAnalysis.cpp

   1 //===- bolt/Passes/FrameAnalysis.cpp --------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the FrameAnalysis class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "bolt/Passes/FrameAnalysis.h"
  14 #include "bolt/Core/CallGraphWalker.h"
  15 #include "bolt/Core/ParallelUtilities.h"
  16 #include "llvm/MC/MCRegisterInfo.h"
  17 #include "llvm/Support/Timer.h"
  18 #include <fstream>
  19 #include <stack>
  20
  21 #define DEBUG_TYPE "fa"
  22
  23 using namespace llvm;
  24
  25 namespace opts {
  26 extern cl::OptionCategory BoltOptCategory;
  27 extern cl::opt<unsigned> Verbosity;
  28
  29 static cl::list<std::string>
  30     FrameOptFunctionNames("funcs-fop", cl::CommaSeparated,
  31                           cl::desc("list of functions to apply frame opts"),
  32                           cl::value_desc("func1,func2,func3,..."));
  33
  34 static cl::opt<std::string> FrameOptFunctionNamesFile(
  35     "funcs-file-fop",
  36     cl::desc("file with list of functions to frame optimize"));
  37
  38 static cl::opt<bool> TimeFA("time-fa", cl::desc("time frame analysis steps"),
  39                             cl::ReallyHidden, cl::cat(BoltOptCategory));
  40
  41 static cl::opt<bool>
  42     ExperimentalSW("experimental-shrink-wrapping",
  43                    cl::desc("process functions with stack pointer arithmetic"),
  44                    cl::ReallyHidden, cl::ZeroOrMore, cl::cat(BoltOptCategory));
  45
  46 bool shouldFrameOptimize(const llvm::bolt::BinaryFunction &Function) {
  47   if (Function.hasUnknownControlFlow())
  48     return false;
  49
  50   if (!FrameOptFunctionNamesFile.empty()) {
  51     assert(!FrameOptFunctionNamesFile.empty() && "unexpected empty file name");
  52     std::ifstream FuncsFile(FrameOptFunctionNamesFile, std::ios::in);
  53     std::string FuncName;
  54     while (std::getline(FuncsFile, FuncName))
  55       FrameOptFunctionNames.push_back(FuncName);
  56     FrameOptFunctionNamesFile = "";
  57   }
  58
  59   if (FrameOptFunctionNames.empty())
  60     return true;
  61   return llvm::any_of(FrameOptFunctionNames, [&](std::string &Name) {
  62     return Function.hasName(Name);
  63   });
  64 }
  65 } // namespace opts
  66
  67 namespace llvm {
  68 namespace bolt {
  69
  70 raw_ostream &operator<<(raw_ostream &OS, const FrameIndexEntry &FIE) {
  71   OS << "FrameIndexEntry<IsLoad: " << FIE.IsLoad << ", IsStore: " << FIE.IsStore
  72      << ", IsStoreFromReg: " << FIE.IsStoreFromReg
  73      << ", RegOrImm: " << FIE.RegOrImm << ", StackOffset: ";
  74   if (FIE.StackOffset < 0)
  75     OS << "-" << Twine::utohexstr(-FIE.StackOffset);
  76   else
  77     OS << "+" << Twine::utohexstr(FIE.StackOffset);
  78   OS << ", Size: " << static_cast<int>(FIE.Size)
  79      << ", IsSimple: " << FIE.IsSimple << ">";
  80   return OS;
  81 }
  82
  83 namespace {
  84
  85 /// This class should be used to iterate through basic blocks in layout order
  86 /// to analyze instructions for frame accesses. The user should call
  87 /// enterNewBB() whenever starting analyzing a new BB and doNext() for each
  88 /// instruction. After doNext(), if isValidAccess() returns true, it means the
  89 /// current instruction accesses the frame and getFIE() may be used to obtain
  90 /// details about this access.
  91 class FrameAccessAnalysis {
  92   /// We depend on Stack Pointer Tracking to figure out the current SP offset
  93   /// value at a given program point
  94   StackPointerTracking &SPT;
  95
  96   /// Context vars
  97   const BinaryContext &BC;
  98   const BinaryFunction &BF;
  99   // Vars used for storing useful CFI info to give us a hint about how the stack
 100   // is used in this function
 101   int SPOffset{0};
 102   int FPOffset{0};
 103   int64_t CfaOffset{-8};
 104   uint16_t CfaReg{7};
 105   std::stack<std::pair<int64_t, uint16_t>> CFIStack;
 106   /// Our pointer to access SPT info
 107   const MCInst *Prev{nullptr};
 108   /// Info about the last frame access
 109   bool IsValidAccess{false};
 110   bool EscapesStackAddress{false};
 111   FrameIndexEntry FIE;
 112
 113   bool decodeFrameAccess(const MCInst &Inst) {
 114     int32_t SrcImm = 0;
 115     MCPhysReg Reg = 0;
 116     int64_t StackOffset = 0;
 117     bool IsIndexed = false;
 118     if (!BC.MIB->isStackAccess(
 119             Inst, FIE.IsLoad, FIE.IsStore, FIE.IsStoreFromReg, Reg, SrcImm,
 120             FIE.StackPtrReg, StackOffset, FIE.Size, FIE.IsSimple, IsIndexed)) {
 121       return true;
 122     }
 123
 124     if (IsIndexed || (!FIE.Size && (FIE.IsLoad || FIE.IsStore))) {
 125       LLVM_DEBUG(dbgs() << "Giving up on indexed memory access/unknown size\n");
 126       LLVM_DEBUG(dbgs() << "Blame insn: ");
 127       LLVM_DEBUG(BC.printInstruction(dbgs(), Inst, 0, &BF, true, false, false));
 128       LLVM_DEBUG(Inst.dump());
 129       return false;
 130     }
 131
 132     assert(FIE.Size != 0 || (!FIE.IsLoad && !FIE.IsStore));
 133
 134     FIE.RegOrImm = SrcImm;
 135     if (FIE.IsLoad || FIE.IsStoreFromReg)
 136       FIE.RegOrImm = Reg;
 137
 138     if (FIE.StackPtrReg == BC.MIB->getStackPointer() && SPOffset != SPT.EMPTY &&
 139         SPOffset != SPT.SUPERPOSITION) {
 140       LLVM_DEBUG(
 141           dbgs() << "Adding access via SP while CFA reg is another one\n");
 142       FIE.StackOffset = SPOffset + StackOffset;
 143     } else if (FIE.StackPtrReg == BC.MIB->getFramePointer() &&
 144                FPOffset != SPT.EMPTY && FPOffset != SPT.SUPERPOSITION) {
 145       LLVM_DEBUG(
 146           dbgs() << "Adding access via FP while CFA reg is another one\n");
 147       FIE.StackOffset = FPOffset + StackOffset;
 148     } else if (FIE.StackPtrReg ==
 149                *BC.MRI->getLLVMRegNum(CfaReg, /*isEH=*/false)) {
 150       FIE.StackOffset = CfaOffset + StackOffset;
 151     } else {
 152       LLVM_DEBUG(
 153           dbgs() << "Found stack access with reg different than cfa reg.\n");
 154       LLVM_DEBUG(dbgs() << "\tCurrent CFA reg: " << CfaReg
 155                         << "\n\tStack access reg: " << FIE.StackPtrReg << "\n");
 156       LLVM_DEBUG(dbgs() << "Blame insn: ");
 157       LLVM_DEBUG(Inst.dump());
 158       return false;
 159     }
 160     IsValidAccess = true;
 161     return true;
 162   }
 163
 164 public:
 165   FrameAccessAnalysis(BinaryFunction &BF, StackPointerTracking &SPT)
 166       : SPT(SPT), BC(BF.getBinaryContext()), BF(BF) {}
 167
 168   void enterNewBB() { Prev = nullptr; }
 169   const FrameIndexEntry &getFIE() const { return FIE; }
 170   int getSPOffset() const { return SPOffset; }
 171   bool isValidAccess() const { return IsValidAccess; }
 172   bool doesEscapeStackAddress() const { return EscapesStackAddress; }
 173
 174   bool doNext(const BinaryBasicBlock &BB, const MCInst &Inst) {
 175     IsValidAccess = false;
 176     EscapesStackAddress = false;
 177     std::tie(SPOffset, FPOffset) =
 178         Prev ? *SPT.getStateAt(*Prev) : *SPT.getStateAt(BB);
 179     Prev = &Inst;
 180     // Use CFI information to keep track of which register is being used to
 181     // access the frame
 182     if (BC.MIB->isCFI(Inst)) {
 183       const MCCFIInstruction *CFI = BF.getCFIFor(Inst);
 184       switch (CFI->getOperation()) {
 185       case MCCFIInstruction::OpDefCfa:
 186         CfaOffset = CFI->getOffset();
 187         [[fallthrough]];
 188       case MCCFIInstruction::OpDefCfaRegister:
 189         CfaReg = CFI->getRegister();
 190         break;
 191       case MCCFIInstruction::OpDefCfaOffset:
 192         CfaOffset = CFI->getOffset();
 193         break;
 194       case MCCFIInstruction::OpRememberState:
 195         CFIStack.push(std::make_pair(CfaOffset, CfaReg));
 196         break;
 197       case MCCFIInstruction::OpRestoreState: {
 198         if (CFIStack.empty())
 199           dbgs() << "Assertion is about to fail: " << BF.getPrintName() << "\n";
 200         assert(!CFIStack.empty() && "Corrupt CFI stack");
 201         std::pair<int64_t, uint16_t> &Elem = CFIStack.top();
 202         CFIStack.pop();
 203         CfaOffset = Elem.first;
 204         CfaReg = Elem.second;
 205         break;
 206       }
 207       case MCCFIInstruction::OpAdjustCfaOffset:
 208         llvm_unreachable("Unhandled AdjustCfaOffset");
 209         break;
 210       default:
 211         break;
 212       }
 213       return true;
 214     }
 215
 216     if (BC.MIB->escapesVariable(Inst, SPT.HasFramePointer)) {
 217       EscapesStackAddress = true;
 218       if (!opts::ExperimentalSW) {
 219         LLVM_DEBUG(
 220             dbgs() << "Leaked stack address, giving up on this function.\n");
 221         LLVM_DEBUG(dbgs() << "Blame insn: ");
 222         LLVM_DEBUG(Inst.dump());
 223         return false;
 224       }
 225     }
 226
 227     return decodeFrameAccess(Inst);
 228   }
 229 };
 230
 231 } // end anonymous namespace
 232
 233 void FrameAnalysis::addArgAccessesFor(MCInst &Inst, ArgAccesses &&AA) {
 234   if (ErrorOr<ArgAccesses &> OldAA = getArgAccessesFor(Inst)) {
 235     if (OldAA->AssumeEverything)
 236       return;
 237     *OldAA = std::move(AA);
 238     return;
 239   }
 240   if (AA.AssumeEverything) {
 241     // Index 0 in ArgAccessesVector represents an "assumeeverything" entry
 242     BC.MIB->addAnnotation(Inst, "ArgAccessEntry", 0U);
 243     return;
 244   }
 245   BC.MIB->addAnnotation(Inst, "ArgAccessEntry",
 246                         (unsigned)ArgAccessesVector.size());
 247   ArgAccessesVector.emplace_back(std::move(AA));
 248 }
 249
 250 void FrameAnalysis::addArgInStackAccessFor(MCInst &Inst,
 251                                            const ArgInStackAccess &Arg) {
 252   ErrorOr<ArgAccesses &> AA = getArgAccessesFor(Inst);
 253   if (!AA) {
 254     addArgAccessesFor(Inst, ArgAccesses(false));
 255     AA = getArgAccessesFor(Inst);
 256     assert(AA && "Object setup failed");
 257   }
 258   std::set<ArgInStackAccess> &Set = AA->Set;
 259   assert(!AA->AssumeEverything && "Adding arg to AssumeEverything set");
 260   Set.emplace(Arg);
 261 }
 262
 263 void FrameAnalysis::addFIEFor(MCInst &Inst, const FrameIndexEntry &FIE) {
 264   BC.MIB->addAnnotation(Inst, "FrameAccessEntry", (unsigned)FIEVector.size());
 265   FIEVector.emplace_back(FIE);
 266 }
 267
 268 ErrorOr<ArgAccesses &> FrameAnalysis::getArgAccessesFor(const MCInst &Inst) {
 269   if (auto Idx = BC.MIB->tryGetAnnotationAs<unsigned>(Inst, "ArgAccessEntry")) {
 270     assert(ArgAccessesVector.size() > *Idx && "Out of bounds");
 271     return ArgAccessesVector[*Idx];
 272   }
 273   return make_error_code(errc::result_out_of_range);
 274 }
 275
 276 ErrorOr<const ArgAccesses &>
 277 FrameAnalysis::getArgAccessesFor(const MCInst &Inst) const {
 278   if (auto Idx = BC.MIB->tryGetAnnotationAs<unsigned>(Inst, "ArgAccessEntry")) {
 279     assert(ArgAccessesVector.size() > *Idx && "Out of bounds");
 280     return ArgAccessesVector[*Idx];
 281   }
 282   return make_error_code(errc::result_out_of_range);
 283 }
 284
 285 ErrorOr<const FrameIndexEntry &>
 286 FrameAnalysis::getFIEFor(const MCInst &Inst) const {
 287   if (auto Idx =
 288           BC.MIB->tryGetAnnotationAs<unsigned>(Inst, "FrameAccessEntry")) {
 289     assert(FIEVector.size() > *Idx && "Out of bounds");
 290     return FIEVector[*Idx];
 291   }
 292   return make_error_code(errc::result_out_of_range);
 293 }
 294
 295 void FrameAnalysis::traverseCG(BinaryFunctionCallGraph &CG) {
 296   CallGraphWalker CGWalker(CG);
 297
 298   CGWalker.registerVisitor(
 299       [&](BinaryFunction *Func) -> bool { return computeArgsAccessed(*Func); });
 300
 301   CGWalker.walk();
 302
 303   DEBUG_WITH_TYPE("ra", {
 304     for (auto &MapEntry : ArgsTouchedMap) {
 305       const BinaryFunction *Func = MapEntry.first;
 306       const auto &Set = MapEntry.second;
 307       dbgs() << "Args accessed for " << Func->getPrintName() << ": ";
 308       if (!Set.empty() && Set.count(std::make_pair(-1, 0)))
 309         dbgs() << "assume everything";
 310       else
 311         for (const std::pair<int64_t, uint8_t> &Entry : Set)
 312           dbgs() << "[" << Entry.first << ", " << (int)Entry.second << "] ";
 313       dbgs() << "\n";
 314     }
 315   });
 316 }
 317
 318 bool FrameAnalysis::updateArgsTouchedFor(const BinaryFunction &BF, MCInst &Inst,
 319                                          int CurOffset) {
 320   if (!BC.MIB->isCall(Inst))
 321     return false;
 322
 323   std::set<int64_t> Res;
 324   const MCSymbol *TargetSymbol = BC.MIB->getTargetSymbol(Inst);
 325   // If indirect call, we conservatively assume it accesses all stack positions
 326   if (TargetSymbol == nullptr) {
 327     addArgAccessesFor(Inst, ArgAccesses(/*AssumeEverything=*/true));
 328     if (!FunctionsRequireAlignment.count(&BF)) {
 329       FunctionsRequireAlignment.insert(&BF);
 330       return true;
 331     }
 332     return false;
 333   }
 334
 335   const BinaryFunction *Function = BC.getFunctionForSymbol(TargetSymbol);
 336   // Call to a function without a BinaryFunction object. Conservatively assume
 337   // it accesses all stack positions
 338   if (Function == nullptr) {
 339     addArgAccessesFor(Inst, ArgAccesses(/*AssumeEverything=*/true));
 340     if (!FunctionsRequireAlignment.count(&BF)) {
 341       FunctionsRequireAlignment.insert(&BF);
 342       return true;
 343     }
 344     return false;
 345   }
 346
 347   auto Iter = ArgsTouchedMap.find(Function);
 348
 349   bool Changed = false;
 350   if (BC.MIB->isTailCall(Inst) && Iter != ArgsTouchedMap.end()) {
 351     // Ignore checking CurOffset because we can't always reliably determine the
 352     // offset specially after an epilogue, where tailcalls happen. It should be
 353     // -8.
 354     for (std::pair<int64_t, uint8_t> Elem : Iter->second) {
 355       if (!llvm::is_contained(ArgsTouchedMap[&BF], Elem)) {
 356         ArgsTouchedMap[&BF].emplace(Elem);
 357         Changed = true;
 358       }
 359     }
 360   }
 361   if (FunctionsRequireAlignment.count(Function) &&
 362       !FunctionsRequireAlignment.count(&BF)) {
 363     Changed = true;
 364     FunctionsRequireAlignment.insert(&BF);
 365   }
 366   if (Iter == ArgsTouchedMap.end())
 367     return Changed;
 368
 369   if (CurOffset == StackPointerTracking::EMPTY ||
 370       CurOffset == StackPointerTracking::SUPERPOSITION) {
 371     addArgAccessesFor(Inst, ArgAccesses(/*AssumeEverything=*/true));
 372     return Changed;
 373   }
 374
 375   for (std::pair<int64_t, uint8_t> Elem : Iter->second) {
 376     if (Elem.first == -1) {
 377       addArgAccessesFor(Inst, ArgAccesses(/*AssumeEverything=*/true));
 378       break;
 379     }
 380     LLVM_DEBUG(dbgs() << "Added arg in stack access annotation "
 381                       << CurOffset + Elem.first << "\n");
 382     addArgInStackAccessFor(
 383         Inst, ArgInStackAccess{/*StackOffset=*/CurOffset + Elem.first,
 384                                /*Size=*/Elem.second});
 385   }
 386   return Changed;
 387 }
 388
 389 bool FrameAnalysis::computeArgsAccessed(BinaryFunction &BF) {
 390   if (!BF.isSimple() || !BF.hasCFG()) {
 391     LLVM_DEBUG(dbgs() << "Treating " << BF.getPrintName()
 392                       << " conservatively.\n");
 393     ArgsTouchedMap[&BF].emplace(std::make_pair(-1, 0));
 394     if (!FunctionsRequireAlignment.count(&BF)) {
 395       FunctionsRequireAlignment.insert(&BF);
 396       return true;
 397     }
 398     return false;
 399   }
 400
 401   LLVM_DEBUG(dbgs() << "Now computing args accessed for: " << BF.getPrintName()
 402                     << "\n");
 403   bool UpdatedArgsTouched = false;
 404   bool NoInfo = false;
 405   FrameAccessAnalysis FAA(BF, getSPT(BF));
 406
 407   for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
 408     FAA.enterNewBB();
 409
 410     for (MCInst &Inst : *BB) {
 411       if (!FAA.doNext(*BB, Inst) || FAA.doesEscapeStackAddress()) {
 412         ArgsTouchedMap[&BF].emplace(std::make_pair(-1, 0));
 413         NoInfo = true;
 414         break;
 415       }
 416
 417       // Check for calls -- attach stack accessing info to them regarding their
 418       // target
 419       if (updateArgsTouchedFor(BF, Inst, FAA.getSPOffset()))
 420         UpdatedArgsTouched = true;
 421
 422       // Check for stack accesses that affect callers
 423       if (!FAA.isValidAccess())
 424         continue;
 425
 426       const FrameIndexEntry &FIE = FAA.getFIE();
 427       if (FIE.StackOffset < 0)
 428         continue;
 429       if (ArgsTouchedMap[&BF].find(std::make_pair(FIE.StackOffset, FIE.Size)) !=
 430           ArgsTouchedMap[&BF].end())
 431         continue;
 432
 433       // Record accesses to the previous stack frame
 434       ArgsTouchedMap[&BF].emplace(std::make_pair(FIE.StackOffset, FIE.Size));
 435       UpdatedArgsTouched = true;
 436       LLVM_DEBUG({
 437         dbgs() << "Arg access offset " << FIE.StackOffset << " added to:\n";
 438         BC.printInstruction(dbgs(), Inst, 0, &BF, true);
 439       });
 440     }
 441     if (NoInfo)
 442       break;
 443   }
 444   if (FunctionsRequireAlignment.count(&BF))
 445     return UpdatedArgsTouched;
 446
 447   if (NoInfo) {
 448     FunctionsRequireAlignment.insert(&BF);
 449     return true;
 450   }
 451
 452   for (BinaryBasicBlock &BB : BF) {
 453     for (MCInst &Inst : BB) {
 454       if (BC.MIB->requiresAlignedAddress(Inst)) {
 455         FunctionsRequireAlignment.insert(&BF);
 456         return true;
 457       }
 458     }
 459   }
 460   return UpdatedArgsTouched;
 461 }
 462
 463 bool FrameAnalysis::restoreFrameIndex(BinaryFunction &BF) {
 464   FrameAccessAnalysis FAA(BF, getSPT(BF));
 465
 466   LLVM_DEBUG(dbgs() << "Restoring frame indices for \"" << BF.getPrintName()
 467                     << "\"\n");
 468   for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
 469     LLVM_DEBUG(dbgs() << "\tNow at BB " << BB->getName() << "\n");
 470     FAA.enterNewBB();
 471
 472     for (MCInst &Inst : *BB) {
 473       if (!FAA.doNext(*BB, Inst))
 474         return false;
 475       LLVM_DEBUG({
 476         dbgs() << "\t\tNow at ";
 477         Inst.dump();
 478         dbgs() << "\t\t\tSP offset is " << FAA.getSPOffset() << "\n";
 479       });
 480
 481       if (FAA.doesEscapeStackAddress()) {
 482         if (!FunctionsWithStackArithmetic.count(&BF))
 483           FunctionsWithStackArithmetic.insert(&BF);
 484         continue;
 485       }
 486
 487       if (!FAA.isValidAccess())
 488         continue;
 489
 490       const FrameIndexEntry &FIE = FAA.getFIE();
 491
 492       addFIEFor(Inst, FIE);
 493       LLVM_DEBUG({
 494         dbgs() << "Frame index annotation " << FIE << " added to:\n";
 495         BC.printInstruction(dbgs(), Inst, 0, &BF, true);
 496       });
 497     }
 498   }
 499   return true;
 500 }
 501
 502 void FrameAnalysis::cleanAnnotations() {
 503   NamedRegionTimer T("cleanannotations", "clean annotations", "FA",
 504                      "FA breakdown", opts::TimeFA);
 505
 506   ParallelUtilities::WorkFuncTy CleanFunction = [&](BinaryFunction &BF) {
 507     for (BinaryBasicBlock &BB : BF) {
 508       for (MCInst &Inst : BB) {
 509         BC.MIB->removeAnnotation(Inst, "ArgAccessEntry");
 510         BC.MIB->removeAnnotation(Inst, "FrameAccessEntry");
 511       }
 512     }
 513   };
 514
 515   ParallelUtilities::runOnEachFunction(
 516       BC, ParallelUtilities::SchedulingPolicy::SP_INST_LINEAR, CleanFunction,
 517       ParallelUtilities::PredicateTy(nullptr), "cleanAnnotations");
 518 }
 519
 520 FrameAnalysis::FrameAnalysis(BinaryContext &BC, BinaryFunctionCallGraph &CG)
 521     : BC(BC) {
 522   // Position 0 of the vector should be always associated with "assume access
 523   // everything".
 524   ArgAccessesVector.emplace_back(ArgAccesses(/*AssumeEverything*/ true));
 525
 526   if (!opts::NoThreads) {
 527     NamedRegionTimer T1("precomputespt", "pre-compute spt", "FA",
 528                         "FA breakdown", opts::TimeFA);
 529     preComputeSPT();
 530   }
 531
 532   {
 533     NamedRegionTimer T1("traversecg", "traverse call graph", "FA",
 534                         "FA breakdown", opts::TimeFA);
 535     traverseCG(CG);
 536   }
 537
 538   for (auto &I : BC.getBinaryFunctions()) {
 539     CountDenominator += I.second.getFunctionScore();
 540
 541     // "shouldOptimize" for passes that run after finalize
 542     if (!(I.second.isSimple() && I.second.hasCFG() && !I.second.isIgnored()) ||
 543         !opts::shouldFrameOptimize(I.second)) {
 544       ++NumFunctionsNotOptimized;
 545       continue;
 546     }
 547
 548     {
 549       NamedRegionTimer T1("restorefi", "restore frame index", "FA",
 550                           "FA breakdown", opts::TimeFA);
 551       if (!restoreFrameIndex(I.second)) {
 552         ++NumFunctionsFailedRestoreFI;
 553         CountFunctionsFailedRestoreFI += I.second.getFunctionScore();
 554         continue;
 555       }
 556     }
 557     AnalyzedFunctions.insert(&I.second);
 558   }
 559
 560   {
 561     NamedRegionTimer T1("clearspt", "clear spt", "FA", "FA breakdown",
 562                         opts::TimeFA);
 563     clearSPTMap();
 564   }
 565 }
 566
 567 void FrameAnalysis::printStats() {
 568   BC.outs() << "BOLT-INFO: FRAME ANALYSIS: " << NumFunctionsNotOptimized
 569             << " function(s) were not optimized.\n"
 570             << "BOLT-INFO: FRAME ANALYSIS: " << NumFunctionsFailedRestoreFI
 571             << " function(s) "
 572             << format(
 573                    "(%.1lf%% dyn cov)",
 574                    (100.0 * CountFunctionsFailedRestoreFI / CountDenominator))
 575             << " could not have its frame indices restored.\n";
 576 }
 577
 578 void FrameAnalysis::clearSPTMap() {
 579   if (opts::NoThreads) {
 580     SPTMap.clear();
 581     return;
 582   }
 583
 584   ParallelUtilities::WorkFuncTy ClearFunctionSPT = [&](BinaryFunction &BF) {
 585     std::unique_ptr<StackPointerTracking> &SPTPtr = SPTMap.find(&BF)->second;
 586     SPTPtr.reset();
 587   };
 588
 589   ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {
 590     return !BF.isSimple() || !BF.hasCFG();
 591   };
 592
 593   ParallelUtilities::runOnEachFunction(
 594       BC, ParallelUtilities::SchedulingPolicy::SP_INST_LINEAR, ClearFunctionSPT,
 595       SkipFunc, "clearSPTMap");
 596
 597   SPTMap.clear();
 598 }
 599
 600 void FrameAnalysis::preComputeSPT() {
 601   // Make sure that the SPTMap is empty
 602   assert(SPTMap.size() == 0);
 603
 604   // Create map entries to allow lock-free parallel execution
 605   for (auto &BFI : BC.getBinaryFunctions()) {
 606     BinaryFunction &BF = BFI.second;
 607     if (!BF.isSimple() || !BF.hasCFG())
 608       continue;
 609     SPTMap.emplace(&BF, std::unique_ptr<StackPointerTracking>());
 610   }
 611
 612   // Create an index for the SPT annotation to allow lock-free parallel
 613   // execution
 614   BC.MIB->getOrCreateAnnotationIndex("StackPointerTracking");
 615
 616   // Run SPT in parallel
 617   ParallelUtilities::WorkFuncWithAllocTy ProcessFunction =
 618       [&](BinaryFunction &BF, MCPlusBuilder::AllocatorIdTy AllocId) {
 619         std::unique_ptr<StackPointerTracking> &SPTPtr =
 620             SPTMap.find(&BF)->second;
 621         SPTPtr = std::make_unique<StackPointerTracking>(BF, AllocId);
 622         SPTPtr->run();
 623       };
 624
 625   ParallelUtilities::PredicateTy SkipPredicate = [&](const BinaryFunction &BF) {
 626     return !BF.isSimple() || !BF.hasCFG();
 627   };
 628
 629   ParallelUtilities::runOnEachFunctionWithUniqueAllocId(
 630       BC, ParallelUtilities::SchedulingPolicy::SP_BB_QUADRATIC, ProcessFunction,
 631       SkipPredicate, "preComputeSPT");
 632 }
 633
 634 } // namespace bolt
 635 } // namespace llvm