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