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         unsigned ArgNo = CB.getArgOperandNo(&UI);
345         if (CB.isByValArgument(ArgNo)) {
346           US.updateRange(getAccessRange(
347               UI, Ptr, DL.getTypeStoreSize(CB.getParamByValType(ArgNo))));
348           break;
349         }
350 
351         // FIXME: consult devirt?
352         // Do not follow aliases, otherwise we could inadvertently follow
353         // dso_preemptable aliases or aliases with interposable linkage.
354         const GlobalValue *Callee =
355             dyn_cast<GlobalValue>(CB.getCalledOperand()->stripPointerCasts());
356         if (!Callee) {
357           US.updateRange(UnknownRange);
358           return false;
359         }
360 
361         assert(isa<Function>(Callee) || isa<GlobalAlias>(Callee));
362         US.Calls.emplace_back(Callee, ArgNo, offsetFrom(UI, Ptr));
363         break;
364       }
365 
366       default:
367         if (Visited.insert(I).second)
368           WorkList.push_back(cast<const Instruction>(I));
369       }
370     }
371   }
372 
373   return true;
374 }
375 
376 FunctionInfo<GlobalValue> StackSafetyLocalAnalysis::run() {
377   FunctionInfo<GlobalValue> Info;
378   assert(!F.isDeclaration() &&
379          "Can't run StackSafety on a function declaration");
380 
381   LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n");
382 
383   for (auto &I : instructions(F)) {
384     if (auto *AI = dyn_cast<AllocaInst>(&I)) {
385       auto &UI = Info.Allocas.emplace(AI, PointerSize).first->second;
386       analyzeAllUses(AI, UI);
387     }
388   }
389 
390   for (Argument &A : make_range(F.arg_begin(), F.arg_end())) {
391     // Non pointers and bypass arguments are not going to be used in any global
392     // processing.
393     if (A.getType()->isPointerTy() && !A.hasByValAttr()) {
394       auto &UI = Info.Params.emplace(A.getArgNo(), PointerSize).first->second;
395       analyzeAllUses(&A, UI);
396     }
397   }
398 
399   LLVM_DEBUG(Info.print(dbgs(), F.getName(), &F));
400   LLVM_DEBUG(dbgs() << "[StackSafety] done\n");
401   return Info;
402 }
403 
404 template <typename CalleeTy> class StackSafetyDataFlowAnalysis {
405   using FunctionMap = std::map<const CalleeTy *, FunctionInfo<CalleeTy>>;
406 
407   FunctionMap Functions;
408   const ConstantRange UnknownRange;
409 
410   // Callee-to-Caller multimap.
411   DenseMap<const CalleeTy *, SmallVector<const CalleeTy *, 4>> Callers;
412   SetVector<const CalleeTy *> WorkList;
413 
414   bool updateOneUse(UseInfo<CalleeTy> &US, bool UpdateToFullSet);
415   void updateOneNode(const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS);
416   void updateOneNode(const CalleeTy *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(uint32_t PointerBitWidth, FunctionMap Functions)
430       : Functions(std::move(Functions)),
431         UnknownRange(ConstantRange::getFull(PointerBitWidth)) {}
432 
433   const FunctionMap &run();
434 
435   ConstantRange getArgumentAccessRange(const CalleeTy *Callee, unsigned ParamNo,
436                                        const ConstantRange &Offsets) const;
437 };
438 
439 template <typename CalleeTy>
440 ConstantRange StackSafetyDataFlowAnalysis<CalleeTy>::getArgumentAccessRange(
441     const CalleeTy *Callee, unsigned ParamNo,
442     const ConstantRange &Offsets) const {
443   auto FnIt = Functions.find(Callee);
444   // Unknown callee (outside of LTO domain or an indirect call).
445   if (FnIt == Functions.end())
446     return UnknownRange;
447   auto &FS = FnIt->second;
448   auto ParamIt = FS.Params.find(ParamNo);
449   if (ParamIt == FS.Params.end())
450     return UnknownRange;
451   auto &Access = ParamIt->second.Range;
452   if (Access.isEmptySet())
453     return Access;
454   if (Access.isFullSet())
455     return UnknownRange;
456   if (Offsets.signedAddMayOverflow(Access) !=
457       ConstantRange::OverflowResult::NeverOverflows)
458     return UnknownRange;
459   return Access.add(Offsets);
460 }
461 
462 template <typename CalleeTy>
463 bool StackSafetyDataFlowAnalysis<CalleeTy>::updateOneUse(UseInfo<CalleeTy> &US,
464                                                          bool UpdateToFullSet) {
465   bool Changed = false;
466   for (auto &CS : US.Calls) {
467     assert(!CS.Offset.isEmptySet() &&
468            "Param range can't be empty-set, invalid offset range");
469 
470     ConstantRange CalleeRange =
471         getArgumentAccessRange(CS.Callee, CS.ParamNo, CS.Offset);
472     if (!US.Range.contains(CalleeRange)) {
473       Changed = true;
474       if (UpdateToFullSet)
475         US.Range = UnknownRange;
476       else
477         US.Range = US.Range.unionWith(CalleeRange);
478     }
479   }
480   return Changed;
481 }
482 
483 template <typename CalleeTy>
484 void StackSafetyDataFlowAnalysis<CalleeTy>::updateOneNode(
485     const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS) {
486   bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations;
487   bool Changed = false;
488   for (auto &KV : FS.Params)
489     Changed |= updateOneUse(KV.second, UpdateToFullSet);
490 
491   if (Changed) {
492     LLVM_DEBUG(dbgs() << "=== update [" << FS.UpdateCount
493                       << (UpdateToFullSet ? ", full-set" : "") << "] " << &FS
494                       << "\n");
495     // Callers of this function may need updating.
496     for (auto &CallerID : Callers[Callee])
497       WorkList.insert(CallerID);
498 
499     ++FS.UpdateCount;
500   }
501 }
502 
503 template <typename CalleeTy>
504 void StackSafetyDataFlowAnalysis<CalleeTy>::runDataFlow() {
505   SmallVector<const CalleeTy *, 16> Callees;
506   for (auto &F : Functions) {
507     Callees.clear();
508     auto &FS = F.second;
509     for (auto &KV : FS.Params)
510       for (auto &CS : KV.second.Calls)
511         Callees.push_back(CS.Callee);
512 
513     llvm::sort(Callees);
514     Callees.erase(std::unique(Callees.begin(), Callees.end()), Callees.end());
515 
516     for (auto &Callee : Callees)
517       Callers[Callee].push_back(F.first);
518   }
519 
520   updateAllNodes();
521 
522   while (!WorkList.empty()) {
523     const CalleeTy *Callee = WorkList.back();
524     WorkList.pop_back();
525     updateOneNode(Callee);
526   }
527 }
528 
529 #ifndef NDEBUG
530 template <typename CalleeTy>
531 void StackSafetyDataFlowAnalysis<CalleeTy>::verifyFixedPoint() {
532   WorkList.clear();
533   updateAllNodes();
534   assert(WorkList.empty());
535 }
536 #endif
537 
538 template <typename CalleeTy>
539 const typename StackSafetyDataFlowAnalysis<CalleeTy>::FunctionMap &
540 StackSafetyDataFlowAnalysis<CalleeTy>::run() {
541   runDataFlow();
542   LLVM_DEBUG(verifyFixedPoint());
543   return Functions;
544 }
545 
546 const Function *findCalleeInModule(const GlobalValue *GV) {
547   while (GV) {
548     if (GV->isDeclaration() || GV->isInterposable() || !GV->isDSOLocal())
549       return nullptr;
550     if (const Function *F = dyn_cast<Function>(GV))
551       return F;
552     const GlobalAlias *A = dyn_cast<GlobalAlias>(GV);
553     if (!A)
554       return nullptr;
555     GV = A->getBaseObject();
556     if (GV == A)
557       return nullptr;
558   }
559   return nullptr;
560 }
561 
562 template <typename CalleeTy> void resolveAllCalls(UseInfo<CalleeTy> &Use) {
563   ConstantRange FullSet(Use.Range.getBitWidth(), true);
564   for (auto &C : Use.Calls) {
565     const Function *F = findCalleeInModule(C.Callee);
566     if (F) {
567       C.Callee = F;
568       continue;
569     }
570 
571     return Use.updateRange(FullSet);
572   }
573 }
574 
575 GVToSSI createGlobalStackSafetyInfo(
576     std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions,
577     const ModuleSummaryIndex *Index) {
578   GVToSSI SSI;
579   if (Functions.empty())
580     return SSI;
581 
582   // FIXME: Simplify printing and remove copying here.
583   auto Copy = Functions;
584 
585   for (auto &FnKV : Copy)
586     for (auto &KV : FnKV.second.Params)
587       resolveAllCalls(KV.second);
588 
589   uint32_t PointerSize = Copy.begin()
590                              ->first->getParent()
591                              ->getDataLayout()
592                              .getMaxPointerSizeInBits();
593   StackSafetyDataFlowAnalysis<GlobalValue> SSDFA(PointerSize, std::move(Copy));
594 
595   for (auto &F : SSDFA.run()) {
596     auto FI = F.second;
597     auto &SrcF = Functions[F.first];
598     for (auto &KV : FI.Allocas) {
599       auto &A = KV.second;
600       resolveAllCalls(A);
601       for (auto &C : A.Calls) {
602         A.updateRange(
603             SSDFA.getArgumentAccessRange(C.Callee, C.ParamNo, C.Offset));
604       }
605       // FIXME: This is needed only to preserve calls in print() results.
606       A.Calls = SrcF.Allocas.find(KV.first)->second.Calls;
607     }
608     for (auto &KV : FI.Params) {
609       auto &P = KV.second;
610       P.Calls = SrcF.Params.find(KV.first)->second.Calls;
611     }
612     SSI[F.first] = std::move(FI);
613   }
614 
615   return SSI;
616 }
617 
618 } // end anonymous namespace
619 
620 StackSafetyInfo::StackSafetyInfo() = default;
621 
622 StackSafetyInfo::StackSafetyInfo(Function *F,
623                                  std::function<ScalarEvolution &()> GetSE)
624     : F(F), GetSE(GetSE) {}
625 
626 StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default;
627 
628 StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default;
629 
630 StackSafetyInfo::~StackSafetyInfo() = default;
631 
632 const StackSafetyInfo::InfoTy &StackSafetyInfo::getInfo() const {
633   if (!Info) {
634     StackSafetyLocalAnalysis SSLA(*F, GetSE());
635     Info.reset(new InfoTy{SSLA.run()});
636   }
637   return *Info;
638 }
639 
640 void StackSafetyInfo::print(raw_ostream &O) const {
641   getInfo().Info.print(O, F->getName(), dyn_cast<Function>(F));
642 }
643 
644 const StackSafetyGlobalInfo::InfoTy &StackSafetyGlobalInfo::getInfo() const {
645   if (!Info) {
646     std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions;
647     for (auto &F : M->functions()) {
648       if (!F.isDeclaration()) {
649         auto FI = GetSSI(F).getInfo().Info;
650         Functions.emplace(&F, std::move(FI));
651       }
652     }
653     Info.reset(new InfoTy{
654         createGlobalStackSafetyInfo(std::move(Functions), Index), {}});
655     for (auto &FnKV : Info->Info) {
656       for (auto &KV : FnKV.second.Allocas) {
657         ++NumAllocaTotal;
658         const AllocaInst *AI = KV.first;
659         if (getStaticAllocaSizeRange(*AI).contains(KV.second.Range)) {
660           Info->SafeAllocas.insert(AI);
661           ++NumAllocaStackSafe;
662         }
663       }
664     }
665     if (StackSafetyPrint)
666       print(errs());
667   }
668   return *Info;
669 }
670 
671 // Converts a StackSafetyFunctionInfo to the relevant FunctionSummary
672 // constructor fields
673 std::vector<FunctionSummary::ParamAccess>
674 StackSafetyInfo::getParamAccesses() const {
675   assert(needsParamAccessSummary(*F->getParent()));
676 
677   std::vector<FunctionSummary::ParamAccess> ParamAccesses;
678   for (const auto &KV : getInfo().Info.Params) {
679     auto &PS = KV.second;
680     if (PS.Range.isFullSet())
681       continue;
682 
683     ParamAccesses.emplace_back(KV.first, PS.Range);
684     FunctionSummary::ParamAccess &Param = ParamAccesses.back();
685 
686     Param.Calls.reserve(PS.Calls.size());
687     for (auto &C : PS.Calls) {
688       if (C.Offset.isFullSet()) {
689         ParamAccesses.pop_back();
690         break;
691       }
692       Param.Calls.emplace_back(C.ParamNo, C.Callee->getGUID(), C.Offset);
693     }
694   }
695   return ParamAccesses;
696 }
697 
698 StackSafetyGlobalInfo::StackSafetyGlobalInfo() = default;
699 
700 StackSafetyGlobalInfo::StackSafetyGlobalInfo(
701     Module *M, std::function<const StackSafetyInfo &(Function &F)> GetSSI,
702     const ModuleSummaryIndex *Index)
703     : M(M), GetSSI(GetSSI), Index(Index) {
704   if (StackSafetyRun)
705     getInfo();
706 }
707 
708 StackSafetyGlobalInfo::StackSafetyGlobalInfo(StackSafetyGlobalInfo &&) =
709     default;
710 
711 StackSafetyGlobalInfo &
712 StackSafetyGlobalInfo::operator=(StackSafetyGlobalInfo &&) = default;
713 
714 StackSafetyGlobalInfo::~StackSafetyGlobalInfo() = default;
715 
716 bool StackSafetyGlobalInfo::isSafe(const AllocaInst &AI) const {
717   const auto &Info = getInfo();
718   return Info.SafeAllocas.count(&AI);
719 }
720 
721 void StackSafetyGlobalInfo::print(raw_ostream &O) const {
722   auto &SSI = getInfo().Info;
723   if (SSI.empty())
724     return;
725   const Module &M = *SSI.begin()->first->getParent();
726   for (auto &F : M.functions()) {
727     if (!F.isDeclaration()) {
728       SSI.find(&F)->second.print(O, F.getName(), &F);
729       O << "\n";
730     }
731   }
732 }
733 
734 LLVM_DUMP_METHOD void StackSafetyGlobalInfo::dump() const { print(dbgs()); }
735 
736 AnalysisKey StackSafetyAnalysis::Key;
737 
738 StackSafetyInfo StackSafetyAnalysis::run(Function &F,
739                                          FunctionAnalysisManager &AM) {
740   return StackSafetyInfo(&F, [&AM, &F]() -> ScalarEvolution & {
741     return AM.getResult<ScalarEvolutionAnalysis>(F);
742   });
743 }
744 
745 PreservedAnalyses StackSafetyPrinterPass::run(Function &F,
746                                               FunctionAnalysisManager &AM) {
747   OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n";
748   AM.getResult<StackSafetyAnalysis>(F).print(OS);
749   return PreservedAnalyses::all();
750 }
751 
752 char StackSafetyInfoWrapperPass::ID = 0;
753 
754 StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass() : FunctionPass(ID) {
755   initializeStackSafetyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
756 }
757 
758 void StackSafetyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
759   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
760   AU.setPreservesAll();
761 }
762 
763 void StackSafetyInfoWrapperPass::print(raw_ostream &O, const Module *M) const {
764   SSI.print(O);
765 }
766 
767 bool StackSafetyInfoWrapperPass::runOnFunction(Function &F) {
768   auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
769   SSI = {&F, [SE]() -> ScalarEvolution & { return *SE; }};
770   return false;
771 }
772 
773 AnalysisKey StackSafetyGlobalAnalysis::Key;
774 
775 StackSafetyGlobalInfo
776 StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
777   // FIXME: Lookup Module Summary.
778   FunctionAnalysisManager &FAM =
779       AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
780   return {&M,
781           [&FAM](Function &F) -> const StackSafetyInfo & {
782             return FAM.getResult<StackSafetyAnalysis>(F);
783           },
784           nullptr};
785 }
786 
787 PreservedAnalyses StackSafetyGlobalPrinterPass::run(Module &M,
788                                                     ModuleAnalysisManager &AM) {
789   OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n";
790   AM.getResult<StackSafetyGlobalAnalysis>(M).print(OS);
791   return PreservedAnalyses::all();
792 }
793 
794 char StackSafetyGlobalInfoWrapperPass::ID = 0;
795 
796 StackSafetyGlobalInfoWrapperPass::StackSafetyGlobalInfoWrapperPass()
797     : ModulePass(ID) {
798   initializeStackSafetyGlobalInfoWrapperPassPass(
799       *PassRegistry::getPassRegistry());
800 }
801 
802 StackSafetyGlobalInfoWrapperPass::~StackSafetyGlobalInfoWrapperPass() = default;
803 
804 void StackSafetyGlobalInfoWrapperPass::print(raw_ostream &O,
805                                              const Module *M) const {
806   SSGI.print(O);
807 }
808 
809 void StackSafetyGlobalInfoWrapperPass::getAnalysisUsage(
810     AnalysisUsage &AU) const {
811   AU.setPreservesAll();
812   AU.addRequired<StackSafetyInfoWrapperPass>();
813 }
814 
815 bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) {
816   const ModuleSummaryIndex *ImportSummary = nullptr;
817   if (auto *IndexWrapperPass =
818           getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>())
819     ImportSummary = IndexWrapperPass->getIndex();
820 
821   SSGI = {&M,
822           [this](Function &F) -> const StackSafetyInfo & {
823             return getAnalysis<StackSafetyInfoWrapperPass>(F).getResult();
824           },
825           ImportSummary};
826   return false;
827 }
828 
829 bool llvm::needsParamAccessSummary(const Module &M) {
830   if (StackSafetyRun)
831     return true;
832   for (auto &F : M.functions())
833     if (F.hasFnAttribute(Attribute::SanitizeMemTag))
834       return true;
835   return false;
836 }
837 
838 static const char LocalPassArg[] = "stack-safety-local";
839 static const char LocalPassName[] = "Stack Safety Local Analysis";
840 INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
841                       false, true)
842 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
843 INITIALIZE_PASS_END(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
844                     false, true)
845 
846 static const char GlobalPassName[] = "Stack Safety Analysis";
847 INITIALIZE_PASS_BEGIN(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
848                       GlobalPassName, false, true)
849 INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)
850 INITIALIZE_PASS_DEPENDENCY(ImmutableModuleSummaryIndexWrapperPass)
851 INITIALIZE_PASS_END(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
852                     GlobalPassName, false, true)
853