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 static cl::opt<int> StackSafetyPrint("stack-safety-print", cl::init(0),
35                                      cl::Hidden);
36 
37 namespace {
38 
39 /// Rewrite an SCEV expression for a memory access address to an expression that
40 /// represents offset from the given alloca.
41 class AllocaOffsetRewriter : public SCEVRewriteVisitor<AllocaOffsetRewriter> {
42   const Value *AllocaPtr;
43 
44 public:
45   AllocaOffsetRewriter(ScalarEvolution &SE, const Value *AllocaPtr)
46       : SCEVRewriteVisitor(SE), AllocaPtr(AllocaPtr) {}
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(const ConstantRange &R) {
92     assert(!R.isUpperSignWrapped());
93     Range = Range.unionWith(R);
94     assert(!Range.isUpperSignWrapped());
95   }
96 };
97 
98 raw_ostream &operator<<(raw_ostream &OS, const UseInfo &U) {
99   OS << U.Range;
100   for (auto &Call : U.Calls)
101     OS << ", " << Call;
102   return OS;
103 }
104 
105 // Check if we should bailout for such ranges.
106 bool isUnsafe(const ConstantRange &R) {
107   return R.isEmptySet() || R.isFullSet() || R.isUpperSignWrapped();
108 }
109 
110 /// Calculate the allocation size of a given alloca. Returns empty range
111 // in case of confution.
112 ConstantRange getStaticAllocaSizeRange(const AllocaInst &AI) {
113   const DataLayout &DL = AI.getModule()->getDataLayout();
114   TypeSize TS = DL.getTypeAllocSize(AI.getAllocatedType());
115   unsigned PointerSize = DL.getMaxPointerSizeInBits();
116   // Fallback to empty range for alloca size.
117   ConstantRange R = ConstantRange::getEmpty(PointerSize);
118   if (TS.isScalable())
119     return R;
120   APInt APSize(PointerSize, TS.getFixedSize(), true);
121   if (APSize.isNonPositive())
122     return R;
123   if (AI.isArrayAllocation()) {
124     const auto *C = dyn_cast<ConstantInt>(AI.getArraySize());
125     if (!C)
126       return R;
127     bool Overflow = false;
128     APInt Mul = C->getValue();
129     if (Mul.isNonPositive())
130       return R;
131     Mul = Mul.sextOrTrunc(PointerSize);
132     APSize = APSize.smul_ov(Mul, Overflow);
133     if (Overflow)
134       return R;
135   }
136   R = ConstantRange(APInt::getNullValue(PointerSize), APSize);
137   assert(!isUnsafe(R));
138   return R;
139 }
140 
141 struct FunctionInfo {
142   SmallVector<UseInfo, 4> Allocas;
143   SmallVector<UseInfo, 4> Params;
144   // TODO: describe return value as depending on one or more of its arguments.
145 
146   // StackSafetyDataFlowAnalysis counter stored here for faster access.
147   int UpdateCount = 0;
148 
149   void print(raw_ostream &O, StringRef Name, const Function *F) const {
150     // TODO: Consider different printout format after
151     // StackSafetyDataFlowAnalysis. Calls and parameters are irrelevant then.
152     O << "  @" << Name << ((F && F->isDSOLocal()) ? "" : " dso_preemptable")
153       << ((F && F->isInterposable()) ? " interposable" : "") << "\n";
154 
155     O << "    args uses:\n";
156     size_t Pos = 0;
157     for (auto &P : Params) {
158       StringRef Name = "<N/A>";
159       if (F)
160         Name = F->getArg(Pos)->getName();
161       O << "      " << Name << "[]: " << P << "\n";
162       ++Pos;
163     }
164 
165     O << "    allocas uses:\n";
166     if (F) {
167       size_t Pos = 0;
168       for (auto &I : instructions(F)) {
169         if (const auto *AI = dyn_cast<AllocaInst>(&I)) {
170           auto &AS = Allocas[Pos];
171           O << "      " << AI->getName() << "["
172             << getStaticAllocaSizeRange(*AI).getUpper() << "]: " << AS << "\n";
173           ++Pos;
174         }
175       }
176     } else {
177       assert(Allocas.empty());
178     }
179   }
180 };
181 
182 using GVToSSI = std::map<const GlobalValue *, FunctionInfo>;
183 
184 } // namespace
185 
186 struct StackSafetyInfo::InfoTy {
187   FunctionInfo Info;
188 };
189 
190 struct StackSafetyGlobalInfo::InfoTy {
191   GVToSSI 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 offsetFrom(Value *Addr, Value *Base);
205   ConstantRange getAccessRange(Value *Addr, Value *Base,
206                                ConstantRange SizeRange);
207   ConstantRange getAccessRange(Value *Addr, Value *Base, TypeSize Size);
208   ConstantRange getMemIntrinsicAccessRange(const MemIntrinsic *MI, const Use &U,
209                                            Value *Base);
210 
211   bool analyzeAllUses(Value *Ptr, UseInfo &AS);
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 (isUnsafe(Offset))
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   assert(!isUnsafe(SizeRange));
242 
243   ConstantRange Offsets = offsetFrom(Addr, Base);
244   if (isUnsafe(Offsets))
245     return UnknownRange;
246 
247   if (Offsets.signedAddMayOverflow(SizeRange) !=
248       ConstantRange::OverflowResult::NeverOverflows)
249     return UnknownRange;
250   Offsets = Offsets.add(SizeRange);
251   if (isUnsafe(Offsets))
252     return UnknownRange;
253   return Offsets;
254 }
255 
256 ConstantRange StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base,
257                                                        TypeSize Size) {
258   if (Size.isScalable())
259     return UnknownRange;
260   APInt APSize(PointerSize, Size.getFixedSize(), true);
261   if (APSize.isNegative())
262     return UnknownRange;
263   return getAccessRange(
264       Addr, Base, ConstantRange(APInt::getNullValue(PointerSize), APSize));
265 }
266 
267 ConstantRange StackSafetyLocalAnalysis::getMemIntrinsicAccessRange(
268     const MemIntrinsic *MI, const Use &U, Value *Base) {
269   if (const auto *MTI = dyn_cast<MemTransferInst>(MI)) {
270     if (MTI->getRawSource() != U && MTI->getRawDest() != U)
271       return ConstantRange::getEmpty(PointerSize);
272   } else {
273     if (MI->getRawDest() != U)
274       return ConstantRange::getEmpty(PointerSize);
275   }
276 
277   auto *CalculationTy = IntegerType::getIntNTy(SE.getContext(), PointerSize);
278   if (!SE.isSCEVable(MI->getLength()->getType()))
279     return UnknownRange;
280 
281   const SCEV *Expr =
282       SE.getTruncateOrZeroExtend(SE.getSCEV(MI->getLength()), CalculationTy);
283   ConstantRange Sizes = SE.getSignedRange(Expr);
284   if (Sizes.getUpper().isNegative() || isUnsafe(Sizes))
285     return UnknownRange;
286   Sizes = Sizes.sextOrTrunc(PointerSize);
287   ConstantRange SizeRange(APInt::getNullValue(PointerSize),
288                           Sizes.getUpper() - 1);
289   return getAccessRange(U, Base, SizeRange);
290 }
291 
292 /// The function analyzes all local uses of Ptr (alloca or argument) and
293 /// calculates local access range and all function calls where it was used.
294 bool StackSafetyLocalAnalysis::analyzeAllUses(Value *Ptr, UseInfo &US) {
295   SmallPtrSet<const Value *, 16> Visited;
296   SmallVector<const Value *, 8> WorkList;
297   WorkList.push_back(Ptr);
298 
299   // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc.
300   while (!WorkList.empty()) {
301     const Value *V = WorkList.pop_back_val();
302     for (const Use &UI : V->uses()) {
303       const auto *I = cast<const Instruction>(UI.getUser());
304       assert(V == UI.get());
305 
306       switch (I->getOpcode()) {
307       case Instruction::Load: {
308         US.updateRange(
309             getAccessRange(UI, Ptr, DL.getTypeStoreSize(I->getType())));
310         break;
311       }
312 
313       case Instruction::VAArg:
314         // "va-arg" from a pointer is safe.
315         break;
316       case Instruction::Store: {
317         if (V == I->getOperand(0)) {
318           // Stored the pointer - conservatively assume it may be unsafe.
319           US.updateRange(UnknownRange);
320           return false;
321         }
322         US.updateRange(getAccessRange(
323             UI, Ptr, DL.getTypeStoreSize(I->getOperand(0)->getType())));
324         break;
325       }
326 
327       case Instruction::Ret:
328         // Information leak.
329         // FIXME: Process parameters correctly. This is a leak only if we return
330         // alloca.
331         US.updateRange(UnknownRange);
332         return false;
333 
334       case Instruction::Call:
335       case Instruction::Invoke: {
336         const auto &CB = cast<CallBase>(*I);
337 
338         if (I->isLifetimeStartOrEnd())
339           break;
340 
341         if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
342           US.updateRange(getMemIntrinsicAccessRange(MI, UI, Ptr));
343           break;
344         }
345 
346         // FIXME: consult devirt?
347         // Do not follow aliases, otherwise we could inadvertently follow
348         // dso_preemptable aliases or aliases with interposable linkage.
349         const GlobalValue *Callee =
350             dyn_cast<GlobalValue>(CB.getCalledOperand()->stripPointerCasts());
351         if (!Callee) {
352           US.updateRange(UnknownRange);
353           return false;
354         }
355 
356         assert(isa<Function>(Callee) || isa<GlobalAlias>(Callee));
357 
358         int Found = 0;
359         for (size_t ArgNo = 0; ArgNo < CB.getNumArgOperands(); ++ArgNo) {
360           if (CB.getArgOperand(ArgNo) == V) {
361             ++Found;
362             US.Calls.emplace_back(Callee, ArgNo, offsetFrom(UI, Ptr));
363           }
364         }
365         if (!Found) {
366           US.updateRange(UnknownRange);
367           return false;
368         }
369 
370         break;
371       }
372 
373       default:
374         if (Visited.insert(I).second)
375           WorkList.push_back(cast<const Instruction>(I));
376       }
377     }
378   }
379 
380   return true;
381 }
382 
383 FunctionInfo StackSafetyLocalAnalysis::run() {
384   FunctionInfo Info;
385   assert(!F.isDeclaration() &&
386          "Can't run StackSafety on a function declaration");
387 
388   LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n");
389 
390   for (auto &I : instructions(F)) {
391     if (auto *AI = dyn_cast<AllocaInst>(&I)) {
392       Info.Allocas.emplace_back(PointerSize);
393       UseInfo &AS = Info.Allocas.back();
394       analyzeAllUses(AI, AS);
395     }
396   }
397 
398   for (Argument &A : make_range(F.arg_begin(), F.arg_end())) {
399     Info.Params.emplace_back(PointerSize);
400     UseInfo &PS = Info.Params.back();
401     analyzeAllUses(&A, PS);
402   }
403 
404   LLVM_DEBUG(Info.print(dbgs(), F.getName(), &F));
405   LLVM_DEBUG(dbgs() << "[StackSafety] done\n");
406   return Info;
407 }
408 
409 class StackSafetyDataFlowAnalysis {
410   using FunctionMap = std::map<const GlobalValue *, FunctionInfo>;
411 
412   FunctionMap Functions;
413   const ConstantRange UnknownRange;
414 
415   // Callee-to-Caller multimap.
416   DenseMap<const GlobalValue *, SmallVector<const GlobalValue *, 4>> Callers;
417   SetVector<const GlobalValue *> WorkList;
418 
419 
420   bool updateOneUse(UseInfo &US, bool UpdateToFullSet);
421   void updateOneNode(const GlobalValue *Callee, FunctionInfo &FS);
422   void updateOneNode(const GlobalValue *Callee) {
423     updateOneNode(Callee, Functions.find(Callee)->second);
424   }
425   void updateAllNodes() {
426     for (auto &F : Functions)
427       updateOneNode(F.first, F.second);
428   }
429   void runDataFlow();
430 #ifndef NDEBUG
431   void verifyFixedPoint();
432 #endif
433 
434 public:
435   StackSafetyDataFlowAnalysis(uint32_t PointerBitWidth, FunctionMap Functions)
436       : Functions(std::move(Functions)),
437         UnknownRange(ConstantRange::getFull(PointerBitWidth)) {}
438 
439   const FunctionMap &run();
440 
441   ConstantRange getArgumentAccessRange(const GlobalValue *Callee,
442                                        unsigned ParamNo,
443                                        const ConstantRange &Offsets) const;
444 };
445 
446 ConstantRange StackSafetyDataFlowAnalysis::getArgumentAccessRange(
447     const GlobalValue *Callee, unsigned ParamNo,
448     const ConstantRange &Offsets) const {
449   auto IT = Functions.find(Callee);
450   // Unknown callee (outside of LTO domain or an indirect call).
451   if (IT == Functions.end())
452     return UnknownRange;
453   const FunctionInfo &FS = IT->second;
454   if (ParamNo >= FS.Params.size()) // possibly vararg
455     return UnknownRange;
456   auto &Access = FS.Params[ParamNo].Range;
457   if (Access.isEmptySet())
458     return Access;
459   if (Access.isFullSet() || Offsets.isFullSet())
460     return UnknownRange;
461   if (Offsets.signedAddMayOverflow(Access) !=
462       ConstantRange::OverflowResult::NeverOverflows)
463     return UnknownRange;
464   return Access.add(Offsets);
465 }
466 
467 bool StackSafetyDataFlowAnalysis::updateOneUse(UseInfo &US,
468                                                bool UpdateToFullSet) {
469   bool Changed = false;
470   for (auto &CS : US.Calls) {
471     assert(!CS.Offset.isEmptySet() &&
472            "Param range can't be empty-set, invalid offset range");
473 
474     ConstantRange CalleeRange =
475         getArgumentAccessRange(CS.Callee, CS.ParamNo, CS.Offset);
476     if (!US.Range.contains(CalleeRange)) {
477       Changed = true;
478       if (UpdateToFullSet)
479         US.Range = UnknownRange;
480       else
481         US.Range = US.Range.unionWith(CalleeRange);
482     }
483   }
484   return Changed;
485 }
486 
487 void StackSafetyDataFlowAnalysis::updateOneNode(const GlobalValue *Callee,
488                                                 FunctionInfo &FS) {
489   bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations;
490   bool Changed = false;
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 &PS : FS.Params)
515       for (auto &CS : PS.Calls)
516         Callees.push_back(CS.Callee);
517 
518     llvm::sort(Callees);
519     Callees.erase(std::unique(Callees.begin(), Callees.end()), Callees.end());
520 
521     for (auto &Callee : Callees)
522       Callers[Callee].push_back(F.first);
523   }
524 
525   updateAllNodes();
526 
527   while (!WorkList.empty()) {
528     const GlobalValue *Callee = WorkList.back();
529     WorkList.pop_back();
530     updateOneNode(Callee);
531   }
532 }
533 
534 #ifndef NDEBUG
535 void StackSafetyDataFlowAnalysis::verifyFixedPoint() {
536   WorkList.clear();
537   updateAllNodes();
538   assert(WorkList.empty());
539 }
540 #endif
541 
542 const StackSafetyDataFlowAnalysis::FunctionMap &
543 StackSafetyDataFlowAnalysis::run() {
544   runDataFlow();
545   LLVM_DEBUG(verifyFixedPoint());
546   return Functions;
547 }
548 
549 bool setStackSafetyMetadata(Module &M, const GVToSSI &SSGI) {
550   bool Changed = false;
551   for (auto &F : M.functions()) {
552     if (F.isDeclaration() || F.hasOptNone())
553       continue;
554     auto Iter = SSGI.find(&F);
555     if (Iter == SSGI.end())
556       continue;
557     const FunctionInfo &Summary = Iter->second;
558     size_t Pos = 0;
559     for (auto &I : instructions(F)) {
560       if (auto *AI = dyn_cast<AllocaInst>(&I)) {
561         auto &AS = Summary.Allocas[Pos];
562         if (getStaticAllocaSizeRange(*AI).contains(AS.Range)) {
563           AI->setMetadata(M.getMDKindID("stack-safe"),
564                           MDNode::get(M.getContext(), None));
565           Changed = true;
566         }
567         ++Pos;
568       }
569     }
570   }
571   return Changed;
572 }
573 
574 const Function *findCalleeInModule(const GlobalValue *GV) {
575   while (GV) {
576     if (GV->isInterposable() || !GV->isDSOLocal())
577       return nullptr;
578     if (const Function *F = dyn_cast<Function>(GV))
579       return F;
580     const GlobalAlias *A = dyn_cast<GlobalAlias>(GV);
581     if (!A)
582       return nullptr;
583     GV = A->getBaseObject();
584     if (GV == A)
585       return nullptr;
586   }
587   return nullptr;
588 }
589 
590 void resolveAllCalls(UseInfo &Use) {
591   ConstantRange FullSet(Use.Range.getBitWidth(), true);
592   for (auto &C : Use.Calls) {
593     const Function *F = findCalleeInModule(C.Callee);
594     if (F) {
595       C.Callee = F;
596       continue;
597     }
598 
599     return Use.updateRange(FullSet);
600   }
601 }
602 
603 void resolveAllCalls(SmallVectorImpl<UseInfo> &Values) {
604   for (auto &V : Values)
605     resolveAllCalls(V);
606 }
607 
608 GVToSSI createGlobalStackSafetyInfo(
609     std::map<const GlobalValue *, FunctionInfo> Functions) {
610   GVToSSI SSI;
611   if (Functions.empty())
612     return SSI;
613 
614   // FIXME: Simplify printing and remove copying here.
615   auto Copy = Functions;
616 
617   for (auto &FI : Copy)
618     resolveAllCalls(FI.second.Params);
619 
620   uint32_t PointerSize = Copy.begin()
621                              ->first->getParent()
622                              ->getDataLayout()
623                              .getMaxPointerSizeInBits();
624   StackSafetyDataFlowAnalysis SSDFA(PointerSize, std::move(Copy));
625 
626   for (auto &F : SSDFA.run()) {
627     auto FI = F.second;
628     size_t Pos = 0;
629     auto &SrcF = Functions[F.first];
630     for (auto &A : FI.Allocas) {
631       resolveAllCalls(A);
632       for (auto &C : A.Calls) {
633         A.updateRange(
634             SSDFA.getArgumentAccessRange(C.Callee, C.ParamNo, C.Offset));
635       }
636       // FIXME: This is needed only to preserve calls in print() results.
637       A.Calls = SrcF.Allocas[Pos].Calls;
638       ++Pos;
639     }
640     Pos = 0;
641     for (auto &P : FI.Params) {
642       P.Calls = SrcF.Params[Pos].Calls;
643       ++Pos;
644     }
645     SSI[F.first] = std::move(FI);
646   }
647 
648   return SSI;
649 }
650 
651 } // end anonymous namespace
652 
653 StackSafetyInfo::StackSafetyInfo() = default;
654 
655 StackSafetyInfo::StackSafetyInfo(Function *F,
656                                  std::function<ScalarEvolution &()> GetSE)
657     : F(F), GetSE(GetSE) {}
658 
659 StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default;
660 
661 StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default;
662 
663 StackSafetyInfo::~StackSafetyInfo() = default;
664 
665 const StackSafetyInfo::InfoTy &StackSafetyInfo::getInfo() const {
666   if (!Info) {
667     StackSafetyLocalAnalysis SSLA(*F, GetSE());
668     Info.reset(new InfoTy{SSLA.run()});
669   }
670   return *Info;
671 }
672 
673 void StackSafetyInfo::print(raw_ostream &O) const {
674   getInfo().Info.print(O, F->getName(), dyn_cast<Function>(F));
675 }
676 
677 const StackSafetyGlobalInfo::InfoTy &StackSafetyGlobalInfo::getInfo() const {
678   if (!Info) {
679     std::map<const GlobalValue *, FunctionInfo> Functions;
680     for (auto &F : M->functions()) {
681       if (!F.isDeclaration()) {
682         auto FI = GetSSI(F).getInfo().Info;
683         Functions.emplace(&F, std::move(FI));
684       }
685     }
686     Info.reset(new InfoTy{createGlobalStackSafetyInfo(std::move(Functions))});
687     if (StackSafetyPrint)
688       print(errs());
689   }
690   return *Info;
691 }
692 
693 StackSafetyGlobalInfo::StackSafetyGlobalInfo() = default;
694 
695 StackSafetyGlobalInfo::StackSafetyGlobalInfo(
696     Module *M, std::function<const StackSafetyInfo &(Function &F)> GetSSI)
697     : M(M), GetSSI(GetSSI) {
698   if (StackSafetyPrint > 1)
699     getInfo();
700 }
701 
702 StackSafetyGlobalInfo::StackSafetyGlobalInfo(StackSafetyGlobalInfo &&) =
703     default;
704 
705 StackSafetyGlobalInfo &
706 StackSafetyGlobalInfo::operator=(StackSafetyGlobalInfo &&) = default;
707 
708 StackSafetyGlobalInfo::~StackSafetyGlobalInfo() = default;
709 
710 bool StackSafetyGlobalInfo::setMetadata(Module &M) const {
711   return setStackSafetyMetadata(M, getInfo().Info);
712 }
713 
714 void StackSafetyGlobalInfo::print(raw_ostream &O) const {
715   auto &SSI = getInfo().Info;
716   if (SSI.empty())
717     return;
718   const Module &M = *SSI.begin()->first->getParent();
719   for (auto &F : M.functions()) {
720     if (!F.isDeclaration()) {
721       SSI.find(&F)->second.print(O, F.getName(), &F);
722       O << "\n";
723     }
724   }
725 }
726 
727 LLVM_DUMP_METHOD void StackSafetyGlobalInfo::dump() const { print(dbgs()); }
728 
729 AnalysisKey StackSafetyAnalysis::Key;
730 
731 StackSafetyInfo StackSafetyAnalysis::run(Function &F,
732                                          FunctionAnalysisManager &AM) {
733   return StackSafetyInfo(&F, [&AM, &F]() -> ScalarEvolution & {
734     return AM.getResult<ScalarEvolutionAnalysis>(F);
735   });
736 }
737 
738 PreservedAnalyses StackSafetyPrinterPass::run(Function &F,
739                                               FunctionAnalysisManager &AM) {
740   OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n";
741   AM.getResult<StackSafetyAnalysis>(F).print(OS);
742   return PreservedAnalyses::all();
743 }
744 
745 char StackSafetyInfoWrapperPass::ID = 0;
746 
747 StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass() : FunctionPass(ID) {
748   initializeStackSafetyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
749 }
750 
751 void StackSafetyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
752   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
753   AU.setPreservesAll();
754 }
755 
756 void StackSafetyInfoWrapperPass::print(raw_ostream &O, const Module *M) const {
757   SSI.print(O);
758 }
759 
760 bool StackSafetyInfoWrapperPass::runOnFunction(Function &F) {
761   auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
762   SSI = {&F, [SE]() -> ScalarEvolution & { return *SE; }};
763   return false;
764 }
765 
766 AnalysisKey StackSafetyGlobalAnalysis::Key;
767 
768 StackSafetyGlobalInfo
769 StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
770   FunctionAnalysisManager &FAM =
771       AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
772   return {&M, [&FAM](Function &F) -> const StackSafetyInfo & {
773             return FAM.getResult<StackSafetyAnalysis>(F);
774           }};
775 }
776 
777 PreservedAnalyses StackSafetyGlobalPrinterPass::run(Module &M,
778                                                     ModuleAnalysisManager &AM) {
779   OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n";
780   AM.getResult<StackSafetyGlobalAnalysis>(M).print(OS);
781   return PreservedAnalyses::all();
782 }
783 
784 PreservedAnalyses
785 StackSafetyGlobalAnnotatorPass::run(Module &M, ModuleAnalysisManager &AM) {
786   auto &SSGI = AM.getResult<StackSafetyGlobalAnalysis>(M);
787   SSGI.setMetadata(M);
788   return PreservedAnalyses::all();
789 }
790 
791 char StackSafetyGlobalInfoWrapperPass::ID = 0;
792 
793 StackSafetyGlobalInfoWrapperPass::StackSafetyGlobalInfoWrapperPass()
794     : ModulePass(ID) {
795   initializeStackSafetyGlobalInfoWrapperPassPass(
796       *PassRegistry::getPassRegistry());
797 }
798 
799 StackSafetyGlobalInfoWrapperPass::~StackSafetyGlobalInfoWrapperPass() = default;
800 
801 void StackSafetyGlobalInfoWrapperPass::print(raw_ostream &O,
802                                              const Module *M) const {
803   SSGI.print(O);
804 }
805 
806 void StackSafetyGlobalInfoWrapperPass::getAnalysisUsage(
807     AnalysisUsage &AU) const {
808   AU.addRequired<StackSafetyInfoWrapperPass>();
809 }
810 
811 bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) {
812   SSGI = {&M, [this](Function &F) -> const StackSafetyInfo & {
813             return getAnalysis<StackSafetyInfoWrapperPass>(F).getResult();
814           }};
815   return SSGI.setMetadata(M);
816 }
817 
818 ModulePass *llvm::createStackSafetyGlobalInfoWrapperPass() {
819   return new StackSafetyGlobalInfoWrapperPass();
820 }
821 
822 static const char LocalPassArg[] = "stack-safety-local";
823 static const char LocalPassName[] = "Stack Safety Local Analysis";
824 INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
825                       false, true)
826 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
827 INITIALIZE_PASS_END(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
828                     false, true)
829 
830 static const char GlobalPassName[] = "Stack Safety Analysis";
831 INITIALIZE_PASS_BEGIN(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
832                       GlobalPassName, false, false)
833 INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)
834 INITIALIZE_PASS_END(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
835                     GlobalPassName, false, false)
836