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