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