1 //===- StackSafetyAnalysis.cpp - Stack memory safety analysis -------------===//
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 
11 #include "llvm/Analysis/StackSafetyAnalysis.h"
12 #include "llvm/ADT/APInt.h"
13 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
14 #include "llvm/IR/ConstantRange.h"
15 #include "llvm/IR/DerivedTypes.h"
16 #include "llvm/IR/GlobalValue.h"
17 #include "llvm/IR/InstIterator.h"
18 #include "llvm/IR/Instructions.h"
19 #include "llvm/IR/IntrinsicInst.h"
20 #include "llvm/InitializePasses.h"
21 #include "llvm/Support/Casting.h"
22 #include "llvm/Support/CommandLine.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include <algorithm>
25 #include <memory>
26 
27 using namespace llvm;
28 
29 #define DEBUG_TYPE "stack-safety"
30 
31 static cl::opt<int> StackSafetyMaxIterations("stack-safety-max-iterations",
32                                              cl::init(20), cl::Hidden);
33 
34 namespace {
35 
36 /// Rewrite an SCEV expression for a memory access address to an expression that
37 /// represents offset from the given alloca.
38 class AllocaOffsetRewriter : public SCEVRewriteVisitor<AllocaOffsetRewriter> {
39   const Value *AllocaPtr;
40 
41 public:
42   AllocaOffsetRewriter(ScalarEvolution &SE, const Value *AllocaPtr)
43       : SCEVRewriteVisitor(SE), AllocaPtr(AllocaPtr) {}
44 
45   const SCEV *visitUnknown(const SCEVUnknown *Expr) {
46     // FIXME: look through one or several levels of definitions?
47     // This can be inttoptr(AllocaPtr) and SCEV would not unwrap
48     // it for us.
49     if (Expr->getValue() == AllocaPtr)
50       return SE.getZero(Expr->getType());
51     return Expr;
52   }
53 };
54 
55 /// Describes use of address in as a function call argument.
56 struct PassAsArgInfo {
57   /// Function being called.
58   const GlobalValue *Callee = nullptr;
59   /// Index of argument which pass address.
60   size_t ParamNo = 0;
61   // Offset range of address from base address (alloca or calling function
62   // argument).
63   // Range should never set to empty-set, that is an invalid access range
64   // that can cause empty-set to be propagated with ConstantRange::add
65   ConstantRange Offset;
66   PassAsArgInfo(const GlobalValue *Callee, size_t ParamNo, ConstantRange Offset)
67       : Callee(Callee), ParamNo(ParamNo), Offset(Offset) {}
68 
69   StringRef getName() const { return Callee->getName(); }
70 };
71 
72 raw_ostream &operator<<(raw_ostream &OS, const PassAsArgInfo &P) {
73   return OS << "@" << P.getName() << "(arg" << P.ParamNo << ", " << P.Offset
74             << ")";
75 }
76 
77 /// Describe uses of address (alloca or parameter) inside of the function.
78 struct UseInfo {
79   // Access range if the address (alloca or parameters).
80   // It is allowed to be empty-set when there are no known accesses.
81   ConstantRange Range;
82 
83   // List of calls which pass address as an argument.
84   SmallVector<PassAsArgInfo, 4> Calls;
85 
86   explicit UseInfo(unsigned PointerSize) : Range{PointerSize, false} {}
87 
88   void updateRange(const ConstantRange &R) {
89     assert(!R.isUpperSignWrapped());
90     Range = Range.unionWith(R);
91     assert(!Range.isUpperSignWrapped());
92   }
93 };
94 
95 raw_ostream &operator<<(raw_ostream &OS, const UseInfo &U) {
96   OS << U.Range;
97   for (auto &Call : U.Calls)
98     OS << ", " << Call;
99   return OS;
100 }
101 
102 /// Calculate the allocation size of a given alloca. Returns 0 if the
103 /// size can not be statically determined.
104 uint64_t getStaticAllocaAllocationSize(const AllocaInst *AI) {
105   const DataLayout &DL = AI->getModule()->getDataLayout();
106   TypeSize TS = DL.getTypeAllocSize(AI->getAllocatedType());
107   if (TS.isScalable())
108     return 0;
109   uint64_t Size = TS.getFixedSize();
110   if (AI->isArrayAllocation()) {
111     auto C = dyn_cast<ConstantInt>(AI->getArraySize());
112     if (!C)
113       return 0;
114     Size *= C->getZExtValue();
115   }
116   return Size;
117 }
118 
119 /// Describes uses of allocas and parameters inside of a single function.
120 struct FunctionInfo {
121   SmallVector<UseInfo, 4> Allocas;
122   SmallVector<UseInfo, 4> Params;
123   const GlobalValue *GV = nullptr;
124   // TODO: describe return value as depending on one or more of its arguments.
125 
126   // StackSafetyDataFlowAnalysis counter stored here for faster access.
127   int UpdateCount = 0;
128 
129   FunctionInfo() = default;
130   FunctionInfo(const Function *F) : GV(F){};
131   explicit FunctionInfo(const GlobalAlias *A);
132 
133   bool IsDSOLocal() const { return GV->isDSOLocal(); };
134 
135   bool IsInterposable() const { return GV->isInterposable(); };
136 
137   StringRef getName() const { return GV->getName(); }
138 
139   void print(raw_ostream &O, StringRef Name, const Function *F) const {
140     // TODO: Consider different printout format after
141     // StackSafetyDataFlowAnalysis. Calls and parameters are irrelevant then.
142     O << "  @" << Name << (IsDSOLocal() ? "" : " dso_preemptable")
143       << (IsInterposable() ? " interposable" : "") << "\n";
144 
145     O << "    args uses:\n";
146     size_t Pos = 0;
147     for (auto &P : Params) {
148       StringRef Name = "<N/A>";
149       if (F)
150         Name = F->getArg(Pos)->getName();
151       O << "      " << Name << "[]: " << P << "\n";
152       ++Pos;
153     }
154 
155     O << "    allocas uses:\n";
156     if (F) {
157       size_t Pos = 0;
158       for (auto &I : instructions(F)) {
159         if (auto AI = dyn_cast<AllocaInst>(&I)) {
160           auto &AS = Allocas[Pos];
161           O << "      " << AI->getName() << "["
162             << getStaticAllocaAllocationSize(AI) << "]: " << AS << "\n";
163           ++Pos;
164         }
165       }
166     } else {
167       assert(Allocas.empty());
168     }
169   }
170 };
171 
172 FunctionInfo::FunctionInfo(const GlobalAlias *A) : GV(A) {
173   unsigned PointerSize = A->getParent()->getDataLayout().getPointerSizeInBits();
174   const GlobalObject *Aliasee = A->getBaseObject();
175   const FunctionType *Type = cast<FunctionType>(Aliasee->getValueType());
176   // 'Forward' all parameters to this alias to the aliasee
177   for (unsigned ArgNo = 0; ArgNo < Type->getNumParams(); ArgNo++) {
178     Params.emplace_back(PointerSize);
179     UseInfo &US = Params.back();
180     US.Calls.emplace_back(Aliasee, ArgNo, ConstantRange(APInt(PointerSize, 0)));
181   }
182 }
183 
184 } // namespace
185 
186 struct StackSafetyInfo::InfoTy {
187   FunctionInfo Info;
188 };
189 
190 StackSafetyInfo makeSSI(FunctionInfo Info) {
191   return StackSafetyInfo(StackSafetyInfo::InfoTy{std::move(Info)});
192 }
193 
194 namespace {
195 
196 // Check if we should bailout for such ranges.
197 bool isUnsafe(const ConstantRange &R) {
198   return R.isEmptySet() || R.isFullSet() || R.isUpperSignWrapped();
199 }
200 
201 class StackSafetyLocalAnalysis {
202   Function &F;
203   const DataLayout &DL;
204   ScalarEvolution &SE;
205   unsigned PointerSize = 0;
206 
207   const ConstantRange UnknownRange;
208 
209   ConstantRange offsetFrom(Value *Addr, Value *Base);
210   ConstantRange getAccessRange(Value *Addr, Value *Base,
211                                ConstantRange SizeRange);
212   ConstantRange getAccessRange(Value *Addr, Value *Base, TypeSize Size);
213   ConstantRange getMemIntrinsicAccessRange(const MemIntrinsic *MI, const Use &U,
214                                            Value *Base);
215 
216   bool analyzeAllUses(Value *Ptr, UseInfo &AS);
217 
218   ConstantRange getRange(uint64_t Lower, uint64_t Upper) const {
219     return ConstantRange(APInt(PointerSize, Lower), APInt(PointerSize, Upper));
220   }
221 
222 public:
223   StackSafetyLocalAnalysis(Function &F, ScalarEvolution &SE)
224       : F(F), DL(F.getParent()->getDataLayout()), SE(SE),
225         PointerSize(DL.getPointerSizeInBits()),
226         UnknownRange(PointerSize, true) {}
227 
228   // Run the transformation on the associated function.
229   FunctionInfo run();
230 };
231 
232 ConstantRange StackSafetyLocalAnalysis::offsetFrom(Value *Addr, Value *Base) {
233   if (!SE.isSCEVable(Addr->getType()))
234     return UnknownRange;
235 
236   AllocaOffsetRewriter Rewriter(SE, Base);
237   const SCEV *Expr = Rewriter.visit(SE.getSCEV(Addr));
238   ConstantRange Offset = SE.getSignedRange(Expr);
239   if (isUnsafe(Offset))
240     return UnknownRange;
241   return Offset.sextOrTrunc(PointerSize);
242 }
243 
244 ConstantRange
245 StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base,
246                                          ConstantRange SizeRange) {
247   // Zero-size loads and stores do not access memory.
248   if (SizeRange.isEmptySet())
249     return ConstantRange::getEmpty(PointerSize);
250   assert(!isUnsafe(SizeRange));
251 
252   ConstantRange Offsets = offsetFrom(Addr, Base);
253   if (isUnsafe(Offsets))
254     return UnknownRange;
255 
256   if (Offsets.signedAddMayOverflow(SizeRange) !=
257       ConstantRange::OverflowResult::NeverOverflows)
258     return UnknownRange;
259   Offsets = Offsets.add(SizeRange);
260   if (isUnsafe(Offsets))
261     return UnknownRange;
262   return Offsets;
263 }
264 
265 ConstantRange StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base,
266                                                        TypeSize Size) {
267   if (Size.isScalable())
268     return UnknownRange;
269   return getAccessRange(Addr, Base, getRange(0, Size.getFixedSize()));
270 }
271 
272 ConstantRange StackSafetyLocalAnalysis::getMemIntrinsicAccessRange(
273     const MemIntrinsic *MI, const Use &U, Value *Base) {
274   if (auto MTI = dyn_cast<MemTransferInst>(MI)) {
275     if (MTI->getRawSource() != U && MTI->getRawDest() != U)
276       return ConstantRange::getEmpty(PointerSize);
277   } else {
278     if (MI->getRawDest() != U)
279       return ConstantRange::getEmpty(PointerSize);
280   }
281   auto *CalculationTy = IntegerType::getIntNTy(SE.getContext(), PointerSize);
282   if (!SE.isSCEVable(MI->getLength()->getType()))
283     return UnknownRange;
284 
285   const SCEV *Expr =
286       SE.getTruncateOrZeroExtend(SE.getSCEV(MI->getLength()), CalculationTy);
287   ConstantRange Sizes = SE.getSignedRange(Expr);
288   assert(!isUnsafe(Sizes));
289   if (Sizes.getUpper().isNegative())
290     return UnknownRange;
291   Sizes = Sizes.sextOrTrunc(PointerSize);
292   ConstantRange SizeRange(APInt::getNullValue(PointerSize),
293                           Sizes.getUpper() - 1);
294   return getAccessRange(U, Base, SizeRange);
295 }
296 
297 /// The function analyzes all local uses of Ptr (alloca or argument) and
298 /// calculates local access range and all function calls where it was used.
299 bool StackSafetyLocalAnalysis::analyzeAllUses(Value *Ptr, UseInfo &US) {
300   SmallPtrSet<const Value *, 16> Visited;
301   SmallVector<const Value *, 8> WorkList;
302   WorkList.push_back(Ptr);
303 
304   // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc.
305   while (!WorkList.empty()) {
306     const Value *V = WorkList.pop_back_val();
307     for (const Use &UI : V->uses()) {
308       auto I = cast<const Instruction>(UI.getUser());
309       assert(V == UI.get());
310 
311       switch (I->getOpcode()) {
312       case Instruction::Load: {
313         US.updateRange(
314             getAccessRange(UI, Ptr, DL.getTypeStoreSize(I->getType())));
315         break;
316       }
317 
318       case Instruction::VAArg:
319         // "va-arg" from a pointer is safe.
320         break;
321       case Instruction::Store: {
322         if (V == I->getOperand(0)) {
323           // Stored the pointer - conservatively assume it may be unsafe.
324           US.updateRange(UnknownRange);
325           return false;
326         }
327         US.updateRange(getAccessRange(
328             UI, Ptr, DL.getTypeStoreSize(I->getOperand(0)->getType())));
329         break;
330       }
331 
332       case Instruction::Ret:
333         // Information leak.
334         // FIXME: Process parameters correctly. This is a leak only if we return
335         // alloca.
336         US.updateRange(UnknownRange);
337         return false;
338 
339       case Instruction::Call:
340       case Instruction::Invoke: {
341         const auto &CB = cast<CallBase>(*I);
342 
343         if (I->isLifetimeStartOrEnd())
344           break;
345 
346         if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
347           US.updateRange(getMemIntrinsicAccessRange(MI, UI, Ptr));
348           break;
349         }
350 
351         // FIXME: consult devirt?
352         // Do not follow aliases, otherwise we could inadvertently follow
353         // dso_preemptable aliases or aliases with interposable linkage.
354         const GlobalValue *Callee =
355             dyn_cast<GlobalValue>(CB.getCalledOperand()->stripPointerCasts());
356         if (!Callee) {
357           US.updateRange(UnknownRange);
358           return false;
359         }
360 
361         assert(isa<Function>(Callee) || isa<GlobalAlias>(Callee));
362 
363         auto B = CB.arg_begin(), E = CB.arg_end();
364         int Found = 0;
365         for (auto A = B; A != E; ++A) {
366           if (A->get() == V) {
367             ++Found;
368             ConstantRange Offset = offsetFrom(UI, Ptr);
369             US.Calls.emplace_back(Callee, A - B, Offset);
370           }
371         }
372         if (!Found) {
373           US.updateRange(UnknownRange);
374           return false;
375         }
376 
377         break;
378       }
379 
380       default:
381         if (Visited.insert(I).second)
382           WorkList.push_back(cast<const Instruction>(I));
383       }
384     }
385   }
386 
387   return true;
388 }
389 
390 FunctionInfo StackSafetyLocalAnalysis::run() {
391   FunctionInfo Info(&F);
392   assert(!F.isDeclaration() &&
393          "Can't run StackSafety on a function declaration");
394 
395   LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n");
396 
397   for (auto &I : instructions(F)) {
398     if (auto AI = dyn_cast<AllocaInst>(&I)) {
399       Info.Allocas.emplace_back(PointerSize);
400       UseInfo &AS = Info.Allocas.back();
401       analyzeAllUses(AI, AS);
402     }
403   }
404 
405   for (Argument &A : make_range(F.arg_begin(), F.arg_end())) {
406     Info.Params.emplace_back(PointerSize);
407     UseInfo &PS = Info.Params.back();
408     analyzeAllUses(&A, PS);
409   }
410 
411   LLVM_DEBUG(Info.print(dbgs(), F.getName(), &F));
412   LLVM_DEBUG(dbgs() << "[StackSafety] done\n");
413   return Info;
414 }
415 
416 class StackSafetyDataFlowAnalysis {
417   using FunctionMap = std::map<const GlobalValue *, FunctionInfo>;
418 
419   FunctionMap Functions;
420   // Callee-to-Caller multimap.
421   DenseMap<const GlobalValue *, SmallVector<const GlobalValue *, 4>> Callers;
422   SetVector<const GlobalValue *> WorkList;
423 
424   unsigned PointerSize = 0;
425   const ConstantRange UnknownRange;
426 
427   ConstantRange getArgumentAccessRange(const GlobalValue *Callee,
428                                        unsigned ParamNo) const;
429   bool updateOneUse(UseInfo &US, bool UpdateToFullSet);
430   void updateOneNode(const GlobalValue *Callee, FunctionInfo &FS);
431   void updateOneNode(const GlobalValue *Callee) {
432     updateOneNode(Callee, Functions.find(Callee)->second);
433   }
434   void updateAllNodes() {
435     for (auto &F : Functions)
436       updateOneNode(F.first, F.second);
437   }
438   void runDataFlow();
439 #ifndef NDEBUG
440   void verifyFixedPoint();
441 #endif
442 
443 public:
444   StackSafetyDataFlowAnalysis(
445       Module &M, std::function<const FunctionInfo &(Function &)> FI);
446   StackSafetyGlobalInfo run();
447 };
448 
449 StackSafetyDataFlowAnalysis::StackSafetyDataFlowAnalysis(
450     Module &M, std::function<const FunctionInfo &(Function &)> FI)
451     : PointerSize(M.getDataLayout().getPointerSizeInBits()),
452       UnknownRange(PointerSize, true) {
453   // Without ThinLTO, run the local analysis for every function in the TU and
454   // then run the DFA.
455   for (auto &F : M.functions())
456     if (!F.isDeclaration())
457       Functions.emplace(&F, FI(F));
458   for (auto &A : M.aliases())
459     if (isa<Function>(A.getBaseObject()))
460       Functions.emplace(&A, FunctionInfo(&A));
461 }
462 
463 ConstantRange
464 StackSafetyDataFlowAnalysis::getArgumentAccessRange(const GlobalValue *Callee,
465                                                     unsigned ParamNo) const {
466   auto IT = Functions.find(Callee);
467   // Unknown callee (outside of LTO domain or an indirect call).
468   if (IT == Functions.end())
469     return UnknownRange;
470   const FunctionInfo &FS = IT->second;
471   // The definition of this symbol may not be the definition in this linkage
472   // unit.
473   if (!FS.IsDSOLocal() || FS.IsInterposable())
474     return UnknownRange;
475   if (ParamNo >= FS.Params.size()) // possibly vararg
476     return UnknownRange;
477   return FS.Params[ParamNo].Range;
478 }
479 
480 bool StackSafetyDataFlowAnalysis::updateOneUse(UseInfo &US,
481                                                bool UpdateToFullSet) {
482   bool Changed = false;
483   for (auto &CS : US.Calls) {
484     assert(!CS.Offset.isEmptySet() &&
485            "Param range can't be empty-set, invalid offset range");
486 
487     ConstantRange CalleeRange = getArgumentAccessRange(CS.Callee, CS.ParamNo);
488     CalleeRange = CalleeRange.add(CS.Offset);
489     if (!US.Range.contains(CalleeRange)) {
490       Changed = true;
491       if (UpdateToFullSet)
492         US.Range = UnknownRange;
493       else
494         US.Range = US.Range.unionWith(CalleeRange);
495     }
496   }
497   return Changed;
498 }
499 
500 void StackSafetyDataFlowAnalysis::updateOneNode(const GlobalValue *Callee,
501                                                 FunctionInfo &FS) {
502   bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations;
503   bool Changed = false;
504   for (auto &AS : FS.Allocas)
505     Changed |= updateOneUse(AS, UpdateToFullSet);
506   for (auto &PS : FS.Params)
507     Changed |= updateOneUse(PS, UpdateToFullSet);
508 
509   if (Changed) {
510     LLVM_DEBUG(dbgs() << "=== update [" << FS.UpdateCount
511                       << (UpdateToFullSet ? ", full-set" : "") << "] " << &FS
512                       << "\n");
513     // Callers of this function may need updating.
514     for (auto &CallerID : Callers[Callee])
515       WorkList.insert(CallerID);
516 
517     ++FS.UpdateCount;
518   }
519 }
520 
521 void StackSafetyDataFlowAnalysis::runDataFlow() {
522   Callers.clear();
523   WorkList.clear();
524 
525   SmallVector<const GlobalValue *, 16> Callees;
526   for (auto &F : Functions) {
527     Callees.clear();
528     FunctionInfo &FS = F.second;
529     for (auto &AS : FS.Allocas)
530       for (auto &CS : AS.Calls)
531         Callees.push_back(CS.Callee);
532     for (auto &PS : FS.Params)
533       for (auto &CS : PS.Calls)
534         Callees.push_back(CS.Callee);
535 
536     llvm::sort(Callees);
537     Callees.erase(std::unique(Callees.begin(), Callees.end()), Callees.end());
538 
539     for (auto &Callee : Callees)
540       Callers[Callee].push_back(F.first);
541   }
542 
543   updateAllNodes();
544 
545   while (!WorkList.empty()) {
546     const GlobalValue *Callee = WorkList.back();
547     WorkList.pop_back();
548     updateOneNode(Callee);
549   }
550 }
551 
552 #ifndef NDEBUG
553 void StackSafetyDataFlowAnalysis::verifyFixedPoint() {
554   WorkList.clear();
555   updateAllNodes();
556   assert(WorkList.empty());
557 }
558 #endif
559 
560 StackSafetyGlobalInfo StackSafetyDataFlowAnalysis::run() {
561   runDataFlow();
562   LLVM_DEBUG(verifyFixedPoint());
563 
564   StackSafetyGlobalInfo SSI;
565   for (auto &F : Functions)
566     SSI.emplace(F.first, makeSSI(F.second));
567   return SSI;
568 }
569 
570 bool setStackSafetyMetadata(Module &M, const StackSafetyGlobalInfo &SSGI) {
571   bool Changed = false;
572   unsigned Width = M.getDataLayout().getPointerSizeInBits();
573   for (auto &F : M.functions()) {
574     if (F.isDeclaration() || F.hasOptNone())
575       continue;
576     auto Iter = SSGI.find(&F);
577     if (Iter == SSGI.end())
578       continue;
579     const FunctionInfo &Summary = Iter->second.getInfo().Info;
580     size_t Pos = 0;
581     for (auto &I : instructions(F)) {
582       if (auto AI = dyn_cast<AllocaInst>(&I)) {
583         auto &AS = Summary.Allocas[Pos];
584         ConstantRange AllocaRange{
585             APInt(Width, 0), APInt(Width, getStaticAllocaAllocationSize(AI))};
586         if (AllocaRange.contains(AS.Range)) {
587           AI->setMetadata(M.getMDKindID("stack-safe"),
588                           MDNode::get(M.getContext(), None));
589           Changed = true;
590         }
591         ++Pos;
592       }
593     }
594   }
595   return Changed;
596 }
597 
598 } // end anonymous namespace
599 
600 StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default;
601 StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default;
602 
603 StackSafetyInfo::StackSafetyInfo(InfoTy Info)
604     : Info(new InfoTy(std::move(Info))) {}
605 
606 StackSafetyInfo::~StackSafetyInfo() = default;
607 
608 void StackSafetyInfo::print(raw_ostream &O, const GlobalValue &F) const {
609   Info->Info.print(O, F.getName(), dyn_cast<Function>(&F));
610 }
611 
612 static void print(const StackSafetyGlobalInfo &SSI, raw_ostream &O,
613                   const Module &M) {
614   size_t Count = 0;
615   for (auto &F : M.functions())
616     if (!F.isDeclaration()) {
617       SSI.find(&F)->second.print(O, F);
618       O << "\n";
619       ++Count;
620     }
621   for (auto &A : M.aliases()) {
622     SSI.find(&A)->second.print(O, A);
623     O << "\n";
624     ++Count;
625   }
626   assert(Count == SSI.size() && "Unexpected functions in the result");
627 }
628 
629 AnalysisKey StackSafetyAnalysis::Key;
630 
631 StackSafetyInfo StackSafetyAnalysis::run(Function &F,
632                                          FunctionAnalysisManager &AM) {
633   StackSafetyLocalAnalysis SSLA(F, AM.getResult<ScalarEvolutionAnalysis>(F));
634   return makeSSI(SSLA.run());
635 }
636 
637 PreservedAnalyses StackSafetyPrinterPass::run(Function &F,
638                                               FunctionAnalysisManager &AM) {
639   OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n";
640   AM.getResult<StackSafetyAnalysis>(F).print(OS, F);
641   return PreservedAnalyses::all();
642 }
643 
644 char StackSafetyInfoWrapperPass::ID = 0;
645 
646 StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass() : FunctionPass(ID) {
647   initializeStackSafetyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
648 }
649 
650 void StackSafetyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
651   AU.addRequired<ScalarEvolutionWrapperPass>();
652   AU.setPreservesAll();
653 }
654 
655 void StackSafetyInfoWrapperPass::print(raw_ostream &O, const Module *M) const {
656   SSI->print(O, *F);
657 }
658 
659 bool StackSafetyInfoWrapperPass::runOnFunction(Function &F) {
660   StackSafetyLocalAnalysis SSLA(
661       F, getAnalysis<ScalarEvolutionWrapperPass>().getSE());
662   SSI = makeSSI(SSLA.run());
663   this->F = &F;
664   return false;
665 }
666 
667 AnalysisKey StackSafetyGlobalAnalysis::Key;
668 
669 StackSafetyGlobalInfo
670 StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
671   FunctionAnalysisManager &FAM =
672       AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
673 
674   StackSafetyDataFlowAnalysis SSDFA(
675       M, [&FAM](Function &F) -> const FunctionInfo & {
676         return FAM.getResult<StackSafetyAnalysis>(F).getInfo().Info;
677       });
678   return SSDFA.run();
679 }
680 
681 PreservedAnalyses StackSafetyGlobalPrinterPass::run(Module &M,
682                                                     ModuleAnalysisManager &AM) {
683   OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n";
684   print(AM.getResult<StackSafetyGlobalAnalysis>(M), OS, M);
685   return PreservedAnalyses::all();
686 }
687 
688 PreservedAnalyses
689 StackSafetyGlobalAnnotatorPass::run(Module &M, ModuleAnalysisManager &AM) {
690   auto &SSGI = AM.getResult<StackSafetyGlobalAnalysis>(M);
691   (void)setStackSafetyMetadata(M, SSGI);
692   return PreservedAnalyses::all();
693 }
694 
695 char StackSafetyGlobalInfoWrapperPass::ID = 0;
696 
697 StackSafetyGlobalInfoWrapperPass::StackSafetyGlobalInfoWrapperPass(
698     bool SetMetadata)
699     : ModulePass(ID), SetMetadata(SetMetadata) {
700   initializeStackSafetyGlobalInfoWrapperPassPass(
701       *PassRegistry::getPassRegistry());
702 }
703 
704 void StackSafetyGlobalInfoWrapperPass::print(raw_ostream &O,
705                                              const Module *M) const {
706   ::print(SSGI, O, *M);
707 }
708 
709 void StackSafetyGlobalInfoWrapperPass::getAnalysisUsage(
710     AnalysisUsage &AU) const {
711   AU.addRequired<StackSafetyInfoWrapperPass>();
712 }
713 
714 bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) {
715   StackSafetyDataFlowAnalysis SSDFA(
716       M, [this](Function &F) -> const FunctionInfo & {
717         return getAnalysis<StackSafetyInfoWrapperPass>(F)
718             .getResult()
719             .getInfo()
720             .Info;
721       });
722   SSGI = SSDFA.run();
723   return SetMetadata ? setStackSafetyMetadata(M, SSGI) : false;
724 }
725 
726 ModulePass *llvm::createStackSafetyGlobalInfoWrapperPass(bool SetMetadata) {
727   return new StackSafetyGlobalInfoWrapperPass(SetMetadata);
728 }
729 
730 static const char LocalPassArg[] = "stack-safety-local";
731 static const char LocalPassName[] = "Stack Safety Local Analysis";
732 INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
733                       false, true)
734 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
735 INITIALIZE_PASS_END(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
736                     false, true)
737 
738 static const char GlobalPassName[] = "Stack Safety Analysis";
739 INITIALIZE_PASS_BEGIN(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
740                       GlobalPassName, false, false)
741 INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)
742 INITIALIZE_PASS_END(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
743                     GlobalPassName, false, false)
744