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