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