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