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

source code of llvm/lib/Analysis/StackSafetyAnalysis.cpp