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