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