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