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