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/SmallVector.h"
15 #include "llvm/ADT/Statistic.h"
16 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
17 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
18 #include "llvm/Analysis/StackLifetime.h"
19 #include "llvm/IR/ConstantRange.h"
20 #include "llvm/IR/DerivedTypes.h"
21 #include "llvm/IR/GlobalValue.h"
22 #include "llvm/IR/InstIterator.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/IntrinsicInst.h"
25 #include "llvm/IR/ModuleSummaryIndex.h"
26 #include "llvm/InitializePasses.h"
27 #include "llvm/Support/Casting.h"
28 #include "llvm/Support/CommandLine.h"
29 #include "llvm/Support/FormatVariadic.h"
30 #include "llvm/Support/raw_ostream.h"
31 #include <algorithm>
32 #include <memory>
33 
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "stack-safety"
37 
38 STATISTIC(NumAllocaStackSafe, "Number of safe allocas");
39 STATISTIC(NumAllocaTotal, "Number of total allocas");
40 
41 STATISTIC(NumCombinedCalleeLookupTotal,
42           "Number of total callee lookups on combined index.");
43 STATISTIC(NumCombinedCalleeLookupFailed,
44           "Number of failed callee lookups on combined index.");
45 STATISTIC(NumModuleCalleeLookupTotal,
46           "Number of total callee lookups on module index.");
47 STATISTIC(NumModuleCalleeLookupFailed,
48           "Number of failed callee lookups on module index.");
49 STATISTIC(NumCombinedParamAccessesBefore,
50           "Number of total param accesses before generateParamAccessSummary.");
51 STATISTIC(NumCombinedParamAccessesAfter,
52           "Number of total param accesses after generateParamAccessSummary.");
53 STATISTIC(NumCombinedDataFlowNodes,
54           "Number of total nodes in combined index for dataflow processing.");
55 STATISTIC(NumIndexCalleeUnhandled, "Number of index callee which are unhandled.");
56 STATISTIC(NumIndexCalleeMultipleWeak, "Number of index callee non-unique weak.");
57 STATISTIC(NumIndexCalleeMultipleExternal, "Number of index callee non-unique external.");
58 
59 
60 static cl::opt<int> StackSafetyMaxIterations("stack-safety-max-iterations",
61                                              cl::init(20), cl::Hidden);
62 
63 static cl::opt<bool> StackSafetyPrint("stack-safety-print", cl::init(false),
64                                       cl::Hidden);
65 
66 static cl::opt<bool> StackSafetyRun("stack-safety-run", cl::init(false),
67                                     cl::Hidden);
68 
69 namespace {
70 
71 // Check if we should bailout for such ranges.
72 bool isUnsafe(const ConstantRange &R) {
73   return R.isEmptySet() || R.isFullSet() || R.isUpperSignWrapped();
74 }
75 
76 ConstantRange addOverflowNever(const ConstantRange &L, const ConstantRange &R) {
77   assert(!L.isSignWrappedSet());
78   assert(!R.isSignWrappedSet());
79   if (L.signedAddMayOverflow(R) !=
80       ConstantRange::OverflowResult::NeverOverflows)
81     return ConstantRange::getFull(L.getBitWidth());
82   ConstantRange Result = L.add(R);
83   assert(!Result.isSignWrappedSet());
84   return Result;
85 }
86 
87 ConstantRange unionNoWrap(const ConstantRange &L, const ConstantRange &R) {
88   assert(!L.isSignWrappedSet());
89   assert(!R.isSignWrappedSet());
90   auto Result = L.unionWith(R);
91   // Two non-wrapped sets can produce wrapped.
92   if (Result.isSignWrappedSet())
93     Result = ConstantRange::getFull(Result.getBitWidth());
94   return Result;
95 }
96 
97 /// Describes use of address in as a function call argument.
98 template <typename CalleeTy> struct CallInfo {
99   /// Function being called.
100   const CalleeTy *Callee = nullptr;
101   /// Index of argument which pass address.
102   size_t ParamNo = 0;
103 
104   CallInfo(const CalleeTy *Callee, size_t ParamNo)
105       : Callee(Callee), ParamNo(ParamNo) {}
106 
107   struct Less {
108     bool operator()(const CallInfo &L, const CallInfo &R) const {
109       return std::tie(L.ParamNo, L.Callee) < std::tie(R.ParamNo, R.Callee);
110     }
111   };
112 };
113 
114 /// Describe uses of address (alloca or parameter) inside of the function.
115 template <typename CalleeTy> struct UseInfo {
116   // Access range if the address (alloca or parameters).
117   // It is allowed to be empty-set when there are no known accesses.
118   ConstantRange Range;
119 
120   // List of calls which pass address as an argument.
121   // Value is offset range of address from base address (alloca or calling
122   // function argument). Range should never set to empty-set, that is an invalid
123   // access range that can cause empty-set to be propagated with
124   // ConstantRange::add
125   std::map<CallInfo<CalleeTy>, ConstantRange, typename CallInfo<CalleeTy>::Less>
126       Calls;
127 
128   UseInfo(unsigned PointerSize) : Range{PointerSize, false} {}
129 
130   void updateRange(const ConstantRange &R) { Range = unionNoWrap(Range, R); }
131 };
132 
133 template <typename CalleeTy>
134 raw_ostream &operator<<(raw_ostream &OS, const UseInfo<CalleeTy> &U) {
135   OS << U.Range;
136   for (auto &Call : U.Calls)
137     OS << ", "
138        << "@" << Call.first.Callee->getName() << "(arg" << Call.first.ParamNo
139        << ", " << Call.second << ")";
140   return OS;
141 }
142 
143 /// Calculate the allocation size of a given alloca. Returns empty range
144 // in case of confution.
145 ConstantRange getStaticAllocaSizeRange(const AllocaInst &AI) {
146   const DataLayout &DL = AI.getModule()->getDataLayout();
147   TypeSize TS = DL.getTypeAllocSize(AI.getAllocatedType());
148   unsigned PointerSize = DL.getMaxPointerSizeInBits();
149   // Fallback to empty range for alloca size.
150   ConstantRange R = ConstantRange::getEmpty(PointerSize);
151   if (TS.isScalable())
152     return R;
153   APInt APSize(PointerSize, TS.getFixedSize(), true);
154   if (APSize.isNonPositive())
155     return R;
156   if (AI.isArrayAllocation()) {
157     const auto *C = dyn_cast<ConstantInt>(AI.getArraySize());
158     if (!C)
159       return R;
160     bool Overflow = false;
161     APInt Mul = C->getValue();
162     if (Mul.isNonPositive())
163       return R;
164     Mul = Mul.sextOrTrunc(PointerSize);
165     APSize = APSize.smul_ov(Mul, Overflow);
166     if (Overflow)
167       return R;
168   }
169   R = ConstantRange(APInt::getNullValue(PointerSize), APSize);
170   assert(!isUnsafe(R));
171   return R;
172 }
173 
174 template <typename CalleeTy> struct FunctionInfo {
175   std::map<const AllocaInst *, UseInfo<CalleeTy>> Allocas;
176   std::map<uint32_t, UseInfo<CalleeTy>> Params;
177   // TODO: describe return value as depending on one or more of its arguments.
178 
179   // StackSafetyDataFlowAnalysis counter stored here for faster access.
180   int UpdateCount = 0;
181 
182   void print(raw_ostream &O, StringRef Name, const Function *F) const {
183     // TODO: Consider different printout format after
184     // StackSafetyDataFlowAnalysis. Calls and parameters are irrelevant then.
185     O << "  @" << Name << ((F && F->isDSOLocal()) ? "" : " dso_preemptable")
186       << ((F && F->isInterposable()) ? " interposable" : "") << "\n";
187 
188     O << "    args uses:\n";
189     for (auto &KV : Params) {
190       O << "      ";
191       if (F)
192         O << F->getArg(KV.first)->getName();
193       else
194         O << formatv("arg{0}", KV.first);
195       O << "[]: " << KV.second << "\n";
196     }
197 
198     O << "    allocas uses:\n";
199     if (F) {
200       for (auto &I : instructions(F)) {
201         if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) {
202           auto &AS = Allocas.find(AI)->second;
203           O << "      " << AI->getName() << "["
204             << getStaticAllocaSizeRange(*AI).getUpper() << "]: " << AS << "\n";
205         }
206       }
207     } else {
208       assert(Allocas.empty());
209     }
210     O << "\n";
211   }
212 };
213 
214 using GVToSSI = std::map<const GlobalValue *, FunctionInfo<GlobalValue>>;
215 
216 } // namespace
217 
218 struct StackSafetyInfo::InfoTy {
219   FunctionInfo<GlobalValue> Info;
220 };
221 
222 struct StackSafetyGlobalInfo::InfoTy {
223   GVToSSI Info;
224   SmallPtrSet<const AllocaInst *, 8> SafeAllocas;
225 };
226 
227 namespace {
228 
229 class StackSafetyLocalAnalysis {
230   Function &F;
231   const DataLayout &DL;
232   ScalarEvolution &SE;
233   unsigned PointerSize = 0;
234 
235   const ConstantRange UnknownRange;
236 
237   ConstantRange offsetFrom(Value *Addr, Value *Base);
238   ConstantRange getAccessRange(Value *Addr, Value *Base,
239                                const ConstantRange &SizeRange);
240   ConstantRange getAccessRange(Value *Addr, Value *Base, TypeSize Size);
241   ConstantRange getMemIntrinsicAccessRange(const MemIntrinsic *MI, const Use &U,
242                                            Value *Base);
243 
244   bool analyzeAllUses(Value *Ptr, UseInfo<GlobalValue> &AS,
245                       const StackLifetime &SL);
246 
247 public:
248   StackSafetyLocalAnalysis(Function &F, ScalarEvolution &SE)
249       : F(F), DL(F.getParent()->getDataLayout()), SE(SE),
250         PointerSize(DL.getPointerSizeInBits()),
251         UnknownRange(PointerSize, true) {}
252 
253   // Run the transformation on the associated function.
254   FunctionInfo<GlobalValue> run();
255 };
256 
257 ConstantRange StackSafetyLocalAnalysis::offsetFrom(Value *Addr, Value *Base) {
258   if (!SE.isSCEVable(Addr->getType()) || !SE.isSCEVable(Base->getType()))
259     return UnknownRange;
260 
261   auto *PtrTy = IntegerType::getInt8PtrTy(SE.getContext());
262   const SCEV *AddrExp = SE.getTruncateOrZeroExtend(SE.getSCEV(Addr), PtrTy);
263   const SCEV *BaseExp = SE.getTruncateOrZeroExtend(SE.getSCEV(Base), PtrTy);
264   const SCEV *Diff = SE.getMinusSCEV(AddrExp, BaseExp);
265 
266   ConstantRange Offset = SE.getSignedRange(Diff);
267   if (isUnsafe(Offset))
268     return UnknownRange;
269   return Offset.sextOrTrunc(PointerSize);
270 }
271 
272 ConstantRange
273 StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base,
274                                          const ConstantRange &SizeRange) {
275   // Zero-size loads and stores do not access memory.
276   if (SizeRange.isEmptySet())
277     return ConstantRange::getEmpty(PointerSize);
278   assert(!isUnsafe(SizeRange));
279 
280   ConstantRange Offsets = offsetFrom(Addr, Base);
281   if (isUnsafe(Offsets))
282     return UnknownRange;
283 
284   Offsets = addOverflowNever(Offsets, SizeRange);
285   if (isUnsafe(Offsets))
286     return UnknownRange;
287   return Offsets;
288 }
289 
290 ConstantRange StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base,
291                                                        TypeSize Size) {
292   if (Size.isScalable())
293     return UnknownRange;
294   APInt APSize(PointerSize, Size.getFixedSize(), true);
295   if (APSize.isNegative())
296     return UnknownRange;
297   return getAccessRange(
298       Addr, Base, ConstantRange(APInt::getNullValue(PointerSize), APSize));
299 }
300 
301 ConstantRange StackSafetyLocalAnalysis::getMemIntrinsicAccessRange(
302     const MemIntrinsic *MI, const Use &U, Value *Base) {
303   if (const auto *MTI = dyn_cast<MemTransferInst>(MI)) {
304     if (MTI->getRawSource() != U && MTI->getRawDest() != U)
305       return ConstantRange::getEmpty(PointerSize);
306   } else {
307     if (MI->getRawDest() != U)
308       return ConstantRange::getEmpty(PointerSize);
309   }
310 
311   auto *CalculationTy = IntegerType::getIntNTy(SE.getContext(), PointerSize);
312   if (!SE.isSCEVable(MI->getLength()->getType()))
313     return UnknownRange;
314 
315   const SCEV *Expr =
316       SE.getTruncateOrZeroExtend(SE.getSCEV(MI->getLength()), CalculationTy);
317   ConstantRange Sizes = SE.getSignedRange(Expr);
318   if (Sizes.getUpper().isNegative() || isUnsafe(Sizes))
319     return UnknownRange;
320   Sizes = Sizes.sextOrTrunc(PointerSize);
321   ConstantRange SizeRange(APInt::getNullValue(PointerSize),
322                           Sizes.getUpper() - 1);
323   return getAccessRange(U, Base, SizeRange);
324 }
325 
326 /// The function analyzes all local uses of Ptr (alloca or argument) and
327 /// calculates local access range and all function calls where it was used.
328 bool StackSafetyLocalAnalysis::analyzeAllUses(Value *Ptr,
329                                               UseInfo<GlobalValue> &US,
330                                               const StackLifetime &SL) {
331   SmallPtrSet<const Value *, 16> Visited;
332   SmallVector<const Value *, 8> WorkList;
333   WorkList.push_back(Ptr);
334   const AllocaInst *AI = dyn_cast<AllocaInst>(Ptr);
335 
336   // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc.
337   while (!WorkList.empty()) {
338     const Value *V = WorkList.pop_back_val();
339     for (const Use &UI : V->uses()) {
340       const auto *I = cast<Instruction>(UI.getUser());
341       if (!SL.isReachable(I))
342         continue;
343 
344       assert(V == UI.get());
345 
346       switch (I->getOpcode()) {
347       case Instruction::Load: {
348         if (AI && !SL.isAliveAfter(AI, I)) {
349           US.updateRange(UnknownRange);
350           return false;
351         }
352         US.updateRange(
353             getAccessRange(UI, Ptr, DL.getTypeStoreSize(I->getType())));
354         break;
355       }
356 
357       case Instruction::VAArg:
358         // "va-arg" from a pointer is safe.
359         break;
360       case Instruction::Store: {
361         if (V == I->getOperand(0)) {
362           // Stored the pointer - conservatively assume it may be unsafe.
363           US.updateRange(UnknownRange);
364           return false;
365         }
366         if (AI && !SL.isAliveAfter(AI, I)) {
367           US.updateRange(UnknownRange);
368           return false;
369         }
370         US.updateRange(getAccessRange(
371             UI, Ptr, DL.getTypeStoreSize(I->getOperand(0)->getType())));
372         break;
373       }
374 
375       case Instruction::Ret:
376         // Information leak.
377         // FIXME: Process parameters correctly. This is a leak only if we return
378         // alloca.
379         US.updateRange(UnknownRange);
380         return false;
381 
382       case Instruction::Call:
383       case Instruction::Invoke: {
384         if (I->isLifetimeStartOrEnd())
385           break;
386 
387         if (AI && !SL.isAliveAfter(AI, I)) {
388           US.updateRange(UnknownRange);
389           return false;
390         }
391 
392         if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
393           US.updateRange(getMemIntrinsicAccessRange(MI, UI, Ptr));
394           break;
395         }
396 
397         const auto &CB = cast<CallBase>(*I);
398         if (!CB.isArgOperand(&UI)) {
399           US.updateRange(UnknownRange);
400           return false;
401         }
402 
403         unsigned ArgNo = CB.getArgOperandNo(&UI);
404         if (CB.isByValArgument(ArgNo)) {
405           US.updateRange(getAccessRange(
406               UI, Ptr, DL.getTypeStoreSize(CB.getParamByValType(ArgNo))));
407           break;
408         }
409 
410         // FIXME: consult devirt?
411         // Do not follow aliases, otherwise we could inadvertently follow
412         // dso_preemptable aliases or aliases with interposable linkage.
413         const GlobalValue *Callee =
414             dyn_cast<GlobalValue>(CB.getCalledOperand()->stripPointerCasts());
415         if (!Callee) {
416           US.updateRange(UnknownRange);
417           return false;
418         }
419 
420         assert(isa<Function>(Callee) || isa<GlobalAlias>(Callee));
421         ConstantRange Offsets = offsetFrom(UI, Ptr);
422         auto Insert =
423             US.Calls.emplace(CallInfo<GlobalValue>(Callee, ArgNo), Offsets);
424         if (!Insert.second)
425           Insert.first->second = Insert.first->second.unionWith(Offsets);
426         break;
427       }
428 
429       default:
430         if (Visited.insert(I).second)
431           WorkList.push_back(cast<const Instruction>(I));
432       }
433     }
434   }
435 
436   return true;
437 }
438 
439 FunctionInfo<GlobalValue> StackSafetyLocalAnalysis::run() {
440   FunctionInfo<GlobalValue> Info;
441   assert(!F.isDeclaration() &&
442          "Can't run StackSafety on a function declaration");
443 
444   LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n");
445 
446   SmallVector<AllocaInst *, 64> Allocas;
447   for (auto &I : instructions(F))
448     if (auto *AI = dyn_cast<AllocaInst>(&I))
449       Allocas.push_back(AI);
450   StackLifetime SL(F, Allocas, StackLifetime::LivenessType::Must);
451   SL.run();
452 
453   for (auto *AI : Allocas) {
454     auto &UI = Info.Allocas.emplace(AI, PointerSize).first->second;
455     analyzeAllUses(AI, UI, SL);
456   }
457 
458   for (Argument &A : make_range(F.arg_begin(), F.arg_end())) {
459     // Non pointers and bypass arguments are not going to be used in any global
460     // processing.
461     if (A.getType()->isPointerTy() && !A.hasByValAttr()) {
462       auto &UI = Info.Params.emplace(A.getArgNo(), PointerSize).first->second;
463       analyzeAllUses(&A, UI, SL);
464     }
465   }
466 
467   LLVM_DEBUG(Info.print(dbgs(), F.getName(), &F));
468   LLVM_DEBUG(dbgs() << "[StackSafety] done\n");
469   return Info;
470 }
471 
472 template <typename CalleeTy> class StackSafetyDataFlowAnalysis {
473   using FunctionMap = std::map<const CalleeTy *, FunctionInfo<CalleeTy>>;
474 
475   FunctionMap Functions;
476   const ConstantRange UnknownRange;
477 
478   // Callee-to-Caller multimap.
479   DenseMap<const CalleeTy *, SmallVector<const CalleeTy *, 4>> Callers;
480   SetVector<const CalleeTy *> WorkList;
481 
482   bool updateOneUse(UseInfo<CalleeTy> &US, bool UpdateToFullSet);
483   void updateOneNode(const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS);
484   void updateOneNode(const CalleeTy *Callee) {
485     updateOneNode(Callee, Functions.find(Callee)->second);
486   }
487   void updateAllNodes() {
488     for (auto &F : Functions)
489       updateOneNode(F.first, F.second);
490   }
491   void runDataFlow();
492 #ifndef NDEBUG
493   void verifyFixedPoint();
494 #endif
495 
496 public:
497   StackSafetyDataFlowAnalysis(uint32_t PointerBitWidth, FunctionMap Functions)
498       : Functions(std::move(Functions)),
499         UnknownRange(ConstantRange::getFull(PointerBitWidth)) {}
500 
501   const FunctionMap &run();
502 
503   ConstantRange getArgumentAccessRange(const CalleeTy *Callee, unsigned ParamNo,
504                                        const ConstantRange &Offsets) const;
505 };
506 
507 template <typename CalleeTy>
508 ConstantRange StackSafetyDataFlowAnalysis<CalleeTy>::getArgumentAccessRange(
509     const CalleeTy *Callee, unsigned ParamNo,
510     const ConstantRange &Offsets) const {
511   auto FnIt = Functions.find(Callee);
512   // Unknown callee (outside of LTO domain or an indirect call).
513   if (FnIt == Functions.end())
514     return UnknownRange;
515   auto &FS = FnIt->second;
516   auto ParamIt = FS.Params.find(ParamNo);
517   if (ParamIt == FS.Params.end())
518     return UnknownRange;
519   auto &Access = ParamIt->second.Range;
520   if (Access.isEmptySet())
521     return Access;
522   if (Access.isFullSet())
523     return UnknownRange;
524   return addOverflowNever(Access, Offsets);
525 }
526 
527 template <typename CalleeTy>
528 bool StackSafetyDataFlowAnalysis<CalleeTy>::updateOneUse(UseInfo<CalleeTy> &US,
529                                                          bool UpdateToFullSet) {
530   bool Changed = false;
531   for (auto &KV : US.Calls) {
532     assert(!KV.second.isEmptySet() &&
533            "Param range can't be empty-set, invalid offset range");
534 
535     ConstantRange CalleeRange =
536         getArgumentAccessRange(KV.first.Callee, KV.first.ParamNo, KV.second);
537     if (!US.Range.contains(CalleeRange)) {
538       Changed = true;
539       if (UpdateToFullSet)
540         US.Range = UnknownRange;
541       else
542         US.updateRange(CalleeRange);
543     }
544   }
545   return Changed;
546 }
547 
548 template <typename CalleeTy>
549 void StackSafetyDataFlowAnalysis<CalleeTy>::updateOneNode(
550     const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS) {
551   bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations;
552   bool Changed = false;
553   for (auto &KV : FS.Params)
554     Changed |= updateOneUse(KV.second, UpdateToFullSet);
555 
556   if (Changed) {
557     LLVM_DEBUG(dbgs() << "=== update [" << FS.UpdateCount
558                       << (UpdateToFullSet ? ", full-set" : "") << "] " << &FS
559                       << "\n");
560     // Callers of this function may need updating.
561     for (auto &CallerID : Callers[Callee])
562       WorkList.insert(CallerID);
563 
564     ++FS.UpdateCount;
565   }
566 }
567 
568 template <typename CalleeTy>
569 void StackSafetyDataFlowAnalysis<CalleeTy>::runDataFlow() {
570   SmallVector<const CalleeTy *, 16> Callees;
571   for (auto &F : Functions) {
572     Callees.clear();
573     auto &FS = F.second;
574     for (auto &KV : FS.Params)
575       for (auto &CS : KV.second.Calls)
576         Callees.push_back(CS.first.Callee);
577 
578     llvm::sort(Callees);
579     Callees.erase(std::unique(Callees.begin(), Callees.end()), Callees.end());
580 
581     for (auto &Callee : Callees)
582       Callers[Callee].push_back(F.first);
583   }
584 
585   updateAllNodes();
586 
587   while (!WorkList.empty()) {
588     const CalleeTy *Callee = WorkList.back();
589     WorkList.pop_back();
590     updateOneNode(Callee);
591   }
592 }
593 
594 #ifndef NDEBUG
595 template <typename CalleeTy>
596 void StackSafetyDataFlowAnalysis<CalleeTy>::verifyFixedPoint() {
597   WorkList.clear();
598   updateAllNodes();
599   assert(WorkList.empty());
600 }
601 #endif
602 
603 template <typename CalleeTy>
604 const typename StackSafetyDataFlowAnalysis<CalleeTy>::FunctionMap &
605 StackSafetyDataFlowAnalysis<CalleeTy>::run() {
606   runDataFlow();
607   LLVM_DEBUG(verifyFixedPoint());
608   return Functions;
609 }
610 
611 FunctionSummary *findCalleeFunctionSummary(ValueInfo VI, StringRef ModuleId) {
612   if (!VI)
613     return nullptr;
614   auto SummaryList = VI.getSummaryList();
615   GlobalValueSummary* S = nullptr;
616   for (const auto& GVS : SummaryList) {
617     if (!GVS->isLive())
618       continue;
619     if (const AliasSummary *AS = dyn_cast<AliasSummary>(GVS.get()))
620       if (!AS->hasAliasee())
621         continue;
622     if (!isa<FunctionSummary>(GVS->getBaseObject()))
623       continue;
624     if (GlobalValue::isLocalLinkage(GVS->linkage())) {
625       if (GVS->modulePath() == ModuleId) {
626         S = GVS.get();
627         break;
628       }
629     } else if (GlobalValue::isExternalLinkage(GVS->linkage())) {
630       if (S) {
631         ++NumIndexCalleeMultipleExternal;
632         return nullptr;
633       }
634       S = GVS.get();
635     } else if (GlobalValue::isWeakLinkage(GVS->linkage())) {
636       if (S) {
637         ++NumIndexCalleeMultipleWeak;
638         return nullptr;
639       }
640       S = GVS.get();
641     } else if (GlobalValue::isAvailableExternallyLinkage(GVS->linkage()) ||
642                GlobalValue::isLinkOnceLinkage(GVS->linkage())) {
643       if (SummaryList.size() == 1)
644         S = GVS.get();
645       // According thinLTOResolvePrevailingGUID these are unlikely prevailing.
646     } else {
647       ++NumIndexCalleeUnhandled;
648     }
649   };
650   while (S) {
651     if (!S->isLive() || !S->isDSOLocal())
652       return nullptr;
653     if (FunctionSummary *FS = dyn_cast<FunctionSummary>(S))
654       return FS;
655     AliasSummary *AS = dyn_cast<AliasSummary>(S);
656     if (!AS || !AS->hasAliasee())
657       return nullptr;
658     S = AS->getBaseObject();
659     if (S == AS)
660       return nullptr;
661   }
662   return nullptr;
663 }
664 
665 const Function *findCalleeInModule(const GlobalValue *GV) {
666   while (GV) {
667     if (GV->isDeclaration() || GV->isInterposable() || !GV->isDSOLocal())
668       return nullptr;
669     if (const Function *F = dyn_cast<Function>(GV))
670       return F;
671     const GlobalAlias *A = dyn_cast<GlobalAlias>(GV);
672     if (!A)
673       return nullptr;
674     GV = A->getBaseObject();
675     if (GV == A)
676       return nullptr;
677   }
678   return nullptr;
679 }
680 
681 const ConstantRange *findParamAccess(const FunctionSummary &FS,
682                                      uint32_t ParamNo) {
683   assert(FS.isLive());
684   assert(FS.isDSOLocal());
685   for (auto &PS : FS.paramAccesses())
686     if (ParamNo == PS.ParamNo)
687       return &PS.Use;
688   return nullptr;
689 }
690 
691 void resolveAllCalls(UseInfo<GlobalValue> &Use,
692                      const ModuleSummaryIndex *Index) {
693   ConstantRange FullSet(Use.Range.getBitWidth(), true);
694   auto TmpCalls = std::move(Use.Calls);
695   for (const auto &C : TmpCalls) {
696     const Function *F = findCalleeInModule(C.first.Callee);
697     if (F) {
698       Use.Calls.emplace(CallInfo<GlobalValue>(F, C.first.ParamNo), C.second);
699       continue;
700     }
701 
702     if (!Index)
703       return Use.updateRange(FullSet);
704     FunctionSummary *FS =
705         findCalleeFunctionSummary(Index->getValueInfo(C.first.Callee->getGUID()),
706                                   C.first.Callee->getParent()->getModuleIdentifier());
707     ++NumModuleCalleeLookupTotal;
708     if (!FS) {
709       ++NumModuleCalleeLookupFailed;
710       return Use.updateRange(FullSet);
711     }
712     const ConstantRange *Found = findParamAccess(*FS, C.first.ParamNo);
713     if (!Found || Found->isFullSet())
714       return Use.updateRange(FullSet);
715     ConstantRange Access = Found->sextOrTrunc(Use.Range.getBitWidth());
716     if (!Access.isEmptySet())
717       Use.updateRange(addOverflowNever(Access, C.second));
718   }
719 }
720 
721 GVToSSI createGlobalStackSafetyInfo(
722     std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions,
723     const ModuleSummaryIndex *Index) {
724   GVToSSI SSI;
725   if (Functions.empty())
726     return SSI;
727 
728   // FIXME: Simplify printing and remove copying here.
729   auto Copy = Functions;
730 
731   for (auto &FnKV : Copy)
732     for (auto &KV : FnKV.second.Params) {
733       resolveAllCalls(KV.second, Index);
734       if (KV.second.Range.isFullSet())
735         KV.second.Calls.clear();
736     }
737 
738   uint32_t PointerSize = Copy.begin()
739                              ->first->getParent()
740                              ->getDataLayout()
741                              .getMaxPointerSizeInBits();
742   StackSafetyDataFlowAnalysis<GlobalValue> SSDFA(PointerSize, std::move(Copy));
743 
744   for (auto &F : SSDFA.run()) {
745     auto FI = F.second;
746     auto &SrcF = Functions[F.first];
747     for (auto &KV : FI.Allocas) {
748       auto &A = KV.second;
749       resolveAllCalls(A, Index);
750       for (auto &C : A.Calls) {
751         A.updateRange(SSDFA.getArgumentAccessRange(C.first.Callee,
752                                                    C.first.ParamNo, C.second));
753       }
754       // FIXME: This is needed only to preserve calls in print() results.
755       A.Calls = SrcF.Allocas.find(KV.first)->second.Calls;
756     }
757     for (auto &KV : FI.Params) {
758       auto &P = KV.second;
759       P.Calls = SrcF.Params.find(KV.first)->second.Calls;
760     }
761     SSI[F.first] = std::move(FI);
762   }
763 
764   return SSI;
765 }
766 
767 } // end anonymous namespace
768 
769 StackSafetyInfo::StackSafetyInfo() = default;
770 
771 StackSafetyInfo::StackSafetyInfo(Function *F,
772                                  std::function<ScalarEvolution &()> GetSE)
773     : F(F), GetSE(GetSE) {}
774 
775 StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default;
776 
777 StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default;
778 
779 StackSafetyInfo::~StackSafetyInfo() = default;
780 
781 const StackSafetyInfo::InfoTy &StackSafetyInfo::getInfo() const {
782   if (!Info) {
783     StackSafetyLocalAnalysis SSLA(*F, GetSE());
784     Info.reset(new InfoTy{SSLA.run()});
785   }
786   return *Info;
787 }
788 
789 void StackSafetyInfo::print(raw_ostream &O) const {
790   getInfo().Info.print(O, F->getName(), dyn_cast<Function>(F));
791 }
792 
793 const StackSafetyGlobalInfo::InfoTy &StackSafetyGlobalInfo::getInfo() const {
794   if (!Info) {
795     std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions;
796     for (auto &F : M->functions()) {
797       if (!F.isDeclaration()) {
798         auto FI = GetSSI(F).getInfo().Info;
799         Functions.emplace(&F, std::move(FI));
800       }
801     }
802     Info.reset(new InfoTy{
803         createGlobalStackSafetyInfo(std::move(Functions), Index), {}});
804     for (auto &FnKV : Info->Info) {
805       for (auto &KV : FnKV.second.Allocas) {
806         ++NumAllocaTotal;
807         const AllocaInst *AI = KV.first;
808         if (getStaticAllocaSizeRange(*AI).contains(KV.second.Range)) {
809           Info->SafeAllocas.insert(AI);
810           ++NumAllocaStackSafe;
811         }
812       }
813     }
814     if (StackSafetyPrint)
815       print(errs());
816   }
817   return *Info;
818 }
819 
820 std::vector<FunctionSummary::ParamAccess>
821 StackSafetyInfo::getParamAccesses(ModuleSummaryIndex &Index) const {
822   // Implementation transforms internal representation of parameter information
823   // into FunctionSummary format.
824   std::vector<FunctionSummary::ParamAccess> ParamAccesses;
825   for (const auto &KV : getInfo().Info.Params) {
826     auto &PS = KV.second;
827     // Parameter accessed by any or unknown offset, represented as FullSet by
828     // StackSafety, is handled as the parameter for which we have no
829     // StackSafety info at all. So drop it to reduce summary size.
830     if (PS.Range.isFullSet())
831       continue;
832 
833     ParamAccesses.emplace_back(KV.first, PS.Range);
834     FunctionSummary::ParamAccess &Param = ParamAccesses.back();
835 
836     Param.Calls.reserve(PS.Calls.size());
837     for (auto &C : PS.Calls) {
838       // Parameter forwarded into another function by any or unknown offset
839       // will make ParamAccess::Range as FullSet anyway. So we can drop the
840       // entire parameter like we did above.
841       // TODO(vitalybuka): Return already filtered parameters from getInfo().
842       if (C.second.isFullSet()) {
843         ParamAccesses.pop_back();
844         break;
845       }
846       Param.Calls.emplace_back(C.first.ParamNo,
847                                Index.getOrInsertValueInfo(C.first.Callee),
848                                C.second);
849     }
850   }
851   for (FunctionSummary::ParamAccess &Param : ParamAccesses) {
852     sort(Param.Calls, [](const FunctionSummary::ParamAccess::Call &L,
853                          const FunctionSummary::ParamAccess::Call &R) {
854       return std::tie(L.ParamNo, L.Callee) < std::tie(R.ParamNo, R.Callee);
855     });
856   }
857   return ParamAccesses;
858 }
859 
860 StackSafetyGlobalInfo::StackSafetyGlobalInfo() = default;
861 
862 StackSafetyGlobalInfo::StackSafetyGlobalInfo(
863     Module *M, std::function<const StackSafetyInfo &(Function &F)> GetSSI,
864     const ModuleSummaryIndex *Index)
865     : M(M), GetSSI(GetSSI), Index(Index) {
866   if (StackSafetyRun)
867     getInfo();
868 }
869 
870 StackSafetyGlobalInfo::StackSafetyGlobalInfo(StackSafetyGlobalInfo &&) =
871     default;
872 
873 StackSafetyGlobalInfo &
874 StackSafetyGlobalInfo::operator=(StackSafetyGlobalInfo &&) = default;
875 
876 StackSafetyGlobalInfo::~StackSafetyGlobalInfo() = default;
877 
878 bool StackSafetyGlobalInfo::isSafe(const AllocaInst &AI) const {
879   const auto &Info = getInfo();
880   return Info.SafeAllocas.count(&AI);
881 }
882 
883 void StackSafetyGlobalInfo::print(raw_ostream &O) const {
884   auto &SSI = getInfo().Info;
885   if (SSI.empty())
886     return;
887   const Module &M = *SSI.begin()->first->getParent();
888   for (auto &F : M.functions()) {
889     if (!F.isDeclaration()) {
890       SSI.find(&F)->second.print(O, F.getName(), &F);
891       O << "\n";
892     }
893   }
894 }
895 
896 LLVM_DUMP_METHOD void StackSafetyGlobalInfo::dump() const { print(dbgs()); }
897 
898 AnalysisKey StackSafetyAnalysis::Key;
899 
900 StackSafetyInfo StackSafetyAnalysis::run(Function &F,
901                                          FunctionAnalysisManager &AM) {
902   return StackSafetyInfo(&F, [&AM, &F]() -> ScalarEvolution & {
903     return AM.getResult<ScalarEvolutionAnalysis>(F);
904   });
905 }
906 
907 PreservedAnalyses StackSafetyPrinterPass::run(Function &F,
908                                               FunctionAnalysisManager &AM) {
909   OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n";
910   AM.getResult<StackSafetyAnalysis>(F).print(OS);
911   return PreservedAnalyses::all();
912 }
913 
914 char StackSafetyInfoWrapperPass::ID = 0;
915 
916 StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass() : FunctionPass(ID) {
917   initializeStackSafetyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
918 }
919 
920 void StackSafetyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
921   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
922   AU.setPreservesAll();
923 }
924 
925 void StackSafetyInfoWrapperPass::print(raw_ostream &O, const Module *M) const {
926   SSI.print(O);
927 }
928 
929 bool StackSafetyInfoWrapperPass::runOnFunction(Function &F) {
930   auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
931   SSI = {&F, [SE]() -> ScalarEvolution & { return *SE; }};
932   return false;
933 }
934 
935 AnalysisKey StackSafetyGlobalAnalysis::Key;
936 
937 StackSafetyGlobalInfo
938 StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
939   // FIXME: Lookup Module Summary.
940   FunctionAnalysisManager &FAM =
941       AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
942   return {&M,
943           [&FAM](Function &F) -> const StackSafetyInfo & {
944             return FAM.getResult<StackSafetyAnalysis>(F);
945           },
946           nullptr};
947 }
948 
949 PreservedAnalyses StackSafetyGlobalPrinterPass::run(Module &M,
950                                                     ModuleAnalysisManager &AM) {
951   OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n";
952   AM.getResult<StackSafetyGlobalAnalysis>(M).print(OS);
953   return PreservedAnalyses::all();
954 }
955 
956 char StackSafetyGlobalInfoWrapperPass::ID = 0;
957 
958 StackSafetyGlobalInfoWrapperPass::StackSafetyGlobalInfoWrapperPass()
959     : ModulePass(ID) {
960   initializeStackSafetyGlobalInfoWrapperPassPass(
961       *PassRegistry::getPassRegistry());
962 }
963 
964 StackSafetyGlobalInfoWrapperPass::~StackSafetyGlobalInfoWrapperPass() = default;
965 
966 void StackSafetyGlobalInfoWrapperPass::print(raw_ostream &O,
967                                              const Module *M) const {
968   SSGI.print(O);
969 }
970 
971 void StackSafetyGlobalInfoWrapperPass::getAnalysisUsage(
972     AnalysisUsage &AU) const {
973   AU.setPreservesAll();
974   AU.addRequired<StackSafetyInfoWrapperPass>();
975 }
976 
977 bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) {
978   const ModuleSummaryIndex *ImportSummary = nullptr;
979   if (auto *IndexWrapperPass =
980           getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>())
981     ImportSummary = IndexWrapperPass->getIndex();
982 
983   SSGI = {&M,
984           [this](Function &F) -> const StackSafetyInfo & {
985             return getAnalysis<StackSafetyInfoWrapperPass>(F).getResult();
986           },
987           ImportSummary};
988   return false;
989 }
990 
991 bool llvm::needsParamAccessSummary(const Module &M) {
992   if (StackSafetyRun)
993     return true;
994   for (auto &F : M.functions())
995     if (F.hasFnAttribute(Attribute::SanitizeMemTag))
996       return true;
997   return false;
998 }
999 
1000 void llvm::generateParamAccessSummary(ModuleSummaryIndex &Index) {
1001   if (!Index.hasParamAccess())
1002     return;
1003   const ConstantRange FullSet(FunctionSummary::ParamAccess::RangeWidth, true);
1004 
1005   auto CountParamAccesses = [&](auto &Stat) {
1006     if (!AreStatisticsEnabled())
1007       return;
1008     for (auto &GVS : Index)
1009       for (auto &GV : GVS.second.SummaryList)
1010         if (FunctionSummary *FS = dyn_cast<FunctionSummary>(GV.get()))
1011           Stat += FS->paramAccesses().size();
1012   };
1013 
1014   CountParamAccesses(NumCombinedParamAccessesBefore);
1015 
1016   std::map<const FunctionSummary *, FunctionInfo<FunctionSummary>> Functions;
1017 
1018   // Convert the ModuleSummaryIndex to a FunctionMap
1019   for (auto &GVS : Index) {
1020     for (auto &GV : GVS.second.SummaryList) {
1021       FunctionSummary *FS = dyn_cast<FunctionSummary>(GV.get());
1022       if (!FS || FS->paramAccesses().empty())
1023         continue;
1024       if (FS->isLive() && FS->isDSOLocal()) {
1025         FunctionInfo<FunctionSummary> FI;
1026         for (auto &PS : FS->paramAccesses()) {
1027           auto &US =
1028               FI.Params
1029                   .emplace(PS.ParamNo, FunctionSummary::ParamAccess::RangeWidth)
1030                   .first->second;
1031           US.Range = PS.Use;
1032           for (auto &Call : PS.Calls) {
1033             assert(!Call.Offsets.isFullSet());
1034             FunctionSummary *S =
1035                 findCalleeFunctionSummary(Call.Callee, FS->modulePath());
1036             ++NumCombinedCalleeLookupTotal;
1037             if (!S) {
1038               ++NumCombinedCalleeLookupFailed;
1039               US.Range = FullSet;
1040               US.Calls.clear();
1041               break;
1042             }
1043             US.Calls.emplace(CallInfo<FunctionSummary>(S, Call.ParamNo),
1044                              Call.Offsets);
1045           }
1046         }
1047         Functions.emplace(FS, std::move(FI));
1048       }
1049       // Reset data for all summaries. Alive and DSO local will be set back from
1050       // of data flow results below. Anything else will not be accessed
1051       // by ThinLTO backend, so we can save on bitcode size.
1052       FS->setParamAccesses({});
1053     }
1054   }
1055   NumCombinedDataFlowNodes += Functions.size();
1056   StackSafetyDataFlowAnalysis<FunctionSummary> SSDFA(
1057       FunctionSummary::ParamAccess::RangeWidth, std::move(Functions));
1058   for (auto &KV : SSDFA.run()) {
1059     std::vector<FunctionSummary::ParamAccess> NewParams;
1060     NewParams.reserve(KV.second.Params.size());
1061     for (auto &Param : KV.second.Params) {
1062       // It's not needed as FullSet is processed the same as a missing value.
1063       if (Param.second.Range.isFullSet())
1064         continue;
1065       NewParams.emplace_back();
1066       FunctionSummary::ParamAccess &New = NewParams.back();
1067       New.ParamNo = Param.first;
1068       New.Use = Param.second.Range; // Only range is needed.
1069     }
1070     const_cast<FunctionSummary *>(KV.first)->setParamAccesses(
1071         std::move(NewParams));
1072   }
1073 
1074   CountParamAccesses(NumCombinedParamAccessesAfter);
1075 }
1076 
1077 static const char LocalPassArg[] = "stack-safety-local";
1078 static const char LocalPassName[] = "Stack Safety Local Analysis";
1079 INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
1080                       false, true)
1081 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
1082 INITIALIZE_PASS_END(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
1083                     false, true)
1084 
1085 static const char GlobalPassName[] = "Stack Safety Analysis";
1086 INITIALIZE_PASS_BEGIN(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
1087                       GlobalPassName, false, true)
1088 INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)
1089 INITIALIZE_PASS_DEPENDENCY(ImmutableModuleSummaryIndexWrapperPass)
1090 INITIALIZE_PASS_END(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
1091                     GlobalPassName, false, true)
1092