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