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