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