LLVM  13.0.0git
StackSafetyAnalysis.cpp
Go to the documentation of this file.
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 
12 #include "llvm/ADT/APInt.h"
13 #include "llvm/ADT/SmallPtrSet.h"
14 #include "llvm/ADT/SmallVector.h"
15 #include "llvm/ADT/Statistic.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"
26 #include "llvm/InitializePasses.h"
27 #include "llvm/Support/Casting.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.
72 bool isUnsafe(const ConstantRange &R) {
73  return R.isEmptySet() || R.isFullSet() || R.isUpperSignWrapped();
74 }
75 
76 ConstantRange addOverflowNever(const ConstantRange &L, const ConstantRange &R) {
78  assert(!R.isSignWrappedSet());
79  if (L.signedAddMayOverflow(R) !=
81  return ConstantRange::getFull(L.getBitWidth());
82  ConstantRange Result = L.add(R);
83  assert(!Result.isSignWrappedSet());
84  return Result;
85 }
86 
87 ConstantRange unionNoWrap(const ConstantRange &L, const ConstantRange &R) {
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 
104  CallInfo(const CalleeTy *Callee, size_t ParamNo)
105  : Callee(Callee), ParamNo(ParamNo) {}
106 
107  struct Less {
108  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 
129  UseInfo(unsigned PointerSize) : Range{PointerSize, false} {}
130 
131  void updateRange(const ConstantRange &R) { Range = unionNoWrap(Range, R); }
132 };
133 
134 template <typename CalleeTy>
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.
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 
183  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 
220  FunctionInfo<GlobalValue> Info;
221 };
222 
224  GVToSSI Info;
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:
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 
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 
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 
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 
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.
329 bool StackSafetyLocalAnalysis::analyzeAllUses(Value *Ptr,
330  UseInfo<GlobalValue> &US,
331  const StackLifetime &SL) {
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 
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 
448  for (auto &I : instructions(F))
449  if (auto *AI = dyn_cast<AllocaInst>(&I))
450  Allocas.push_back(AI);
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.
482 
483  bool updateOneUse(UseInfo<CalleeTy> &US, bool UpdateToFullSet);
484  void updateOneNode(const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS);
485  void updateOneNode(const CalleeTy *Callee) {
486  updateOneNode(Callee, Functions.find(Callee)->second);
487  }
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:
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>
509 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>
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>
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>
570 void StackSafetyDataFlowAnalysis<CalleeTy>::runDataFlow() {
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>
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 &
606 StackSafetyDataFlowAnalysis<CalleeTy>::run() {
607  runDataFlow();
608  LLVM_DEBUG(verifyFixedPoint());
609  return Functions;
610 }
611 
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 
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 
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 
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);
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 
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 
774 
776  std::function<ScalarEvolution &()> GetSE)
777  : F(F), GetSE(GetSE) {}
778 
780 
782 
784 
786  if (!Info) {
787  StackSafetyLocalAnalysis SSLA(*F, GetSE());
788  Info.reset(new InfoTy{SSLA.run()});
789  }
790  return *Info;
791 }
792 
794  getInfo().Info.print(O, F->getName(), dyn_cast<Function>(F));
795 }
796 
797 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>
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,
858  return std::tie(L.ParamNo, L.Callee) < std::tie(R.ParamNo, R.Callee);
859  });
860  }
861  return ParamAccesses;
862 }
863 
865 
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 
875  default;
876 
879 
881 
883  const auto &Info = getInfo();
884  return Info.SafeAllocas.count(&AI);
885 }
886 
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 
901 
902 AnalysisKey StackSafetyAnalysis::Key;
903 
906  return StackSafetyInfo(&F, [&AM, &F]() -> ScalarEvolution & {
907  return AM.getResult<ScalarEvolutionAnalysis>(F);
908  });
909 }
910 
913  OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n";
915  return PreservedAnalyses::all();
916 }
917 
919 
922 }
923 
926  AU.setPreservesAll();
927 }
928 
930  SSI.print(O);
931 }
932 
934  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
935  SSI = {&F, [SE]() -> ScalarEvolution & { return *SE; }};
936  return false;
937 }
938 
939 AnalysisKey StackSafetyGlobalAnalysis::Key;
940 
943  // FIXME: Lookup Module Summary.
946  return {&M,
947  [&FAM](Function &F) -> const StackSafetyInfo & {
948  return FAM.getResult<StackSafetyAnalysis>(F);
949  },
950  nullptr};
951 }
952 
954  ModuleAnalysisManager &AM) {
955  OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n";
957  return PreservedAnalyses::all();
958 }
959 
961 
963  : ModulePass(ID) {
966 }
967 
969 
971  const Module *M) const {
972  SSGI.print(O);
973 }
974 
976  AnalysisUsage &AU) const {
977  AU.setPreservesAll();
979 }
980 
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 
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 
1005  if (!Index.hasParamAccess())
1006  return;
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(
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";
1084  false, true)
1088 
1089 static const char GlobalPassName[] = "Stack Safety Analysis";
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::ConstantRange::isFullSet
bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
Definition: ConstantRange.cpp:305
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
StackSafetyAnalysis.h
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2058
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:100
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:498
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:705
llvm::StackSafetyInfo::StackSafetyInfo
StackSafetyInfo()
llvm::StackLifetime::isAliveAfter
bool isAliveAfter(const AllocaInst *AI, const Instruction *I) const
Returns true if the alloca is alive after the instruction.
Definition: StackLifetime.cpp:50
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:65
llvm::StackSafetyGlobalInfo::isSafe
bool isSafe(const AllocaInst &AI) const
Definition: StackSafetyAnalysis.cpp:882
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:111
llvm::StackSafetyInfo::print
void print(raw_ostream &O) const
Definition: StackSafetyAnalysis.cpp:793
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
llvm::Type::getInt8PtrTy
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:249
Insert
Vector Rotate Left Mask Mask Insert
Definition: README_P9.txt:112
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:238
IntrinsicInst.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
InstIterator.h
llvm::TypeSize::getFixedSize
ScalarTy getFixedSize() const
Definition: TypeSize.h:422
llvm::Function
Definition: Function.h:61
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::SetVector::pop_back
void pop_back()
Remove the last element of the SetVector.
Definition: SetVector.h:226
llvm::ImmutableModuleSummaryIndexWrapperPass
Legacy wrapper pass to provide the ModuleSummaryIndex object.
Definition: ModuleSummaryAnalysis.h:82
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::GlobalValue::isLocalLinkage
static bool isLocalLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:329
llvm::StackSafetyInfoWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: StackSafetyAnalysis.cpp:924
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
llvm::GlobalAlias
Definition: GlobalAlias.h:27
llvm::AliasSummary
Alias summary information.
Definition: ModuleSummaryIndex.h:447
LocalPassName
static const char LocalPassName[]
Definition: StackSafetyAnalysis.cpp:1082
llvm::initializeStackSafetyGlobalInfoWrapperPassPass
void initializeStackSafetyGlobalInfoWrapperPassPass(PassRegistry &)
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
APInt.h
llvm::needsParamAccessSummary
bool needsParamAccessSummary(const Module &M)
Definition: StackSafetyAnalysis.cpp:995
llvm::ConstantRange::isSignWrappedSet
bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
Definition: ConstantRange.cpp:321
llvm::MemIntrinsic
This is the common base class for memset/memcpy/memmove.
Definition: IntrinsicInst.h:668
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::StackLifetime::LivenessType::Must
@ Must
llvm::StackSafetyGlobalInfo::operator=
StackSafetyGlobalInfo & operator=(StackSafetyGlobalInfo &&)
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:894
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
llvm::StackSafetyGlobalInfo::InfoTy::SafeAllocas
SmallPtrSet< const AllocaInst *, 8 > SafeAllocas
Definition: StackSafetyAnalysis.cpp:225
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
ModuleSummaryAnalysis.h
llvm::StackSafetyAnalysis::run
StackSafetyInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: StackSafetyAnalysis.cpp:904
llvm::generateParamAccessSummary
void generateParamAccessSummary(ModuleSummaryIndex &Index)
Definition: StackSafetyAnalysis.cpp:1004
llvm::X86AS::FS
@ FS
Definition: X86.h:182
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
llvm::LinearPolySize::isScalable
bool isScalable() const
Returns whether the size is scaled by a runtime quantity (vscale).
Definition: TypeSize.h:295
ModuleSummaryIndex.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
llvm::StackSafetyAnalysis
StackSafetyInfo wrapper for the new pass manager.
Definition: StackSafetyAnalysis.h:84
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:129
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::CallInfo
Definition: GVNHoist.cpp:217
CommandLine.h
llvm::formatv
auto formatv(const char *Fmt, Ts &&... Vals) -> formatv_object< decltype(std::make_tuple(detail::build_format_adapter(std::forward< Ts >(Vals))...))>
Definition: FormatVariadic.h:250
llvm::GlobalValueSummary
Function and variable summary information to aid decisions and implementation of importing.
Definition: ModuleSummaryIndex.h:288
llvm::APInt::isNegative
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:364
llvm::AreStatisticsEnabled
bool AreStatisticsEnabled()
Check if statistics are enabled.
Definition: Statistic.cpp:131
GlobalValue.h
llvm::StackSafetyInfo::InfoTy::Info
FunctionInfo< GlobalValue > Info
Definition: StackSafetyAnalysis.cpp:220
llvm::initializeStackSafetyInfoWrapperPassPass
void initializeStackSafetyInfoWrapperPassPass(PassRegistry &)
StackLifetime.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::GlobalValue::isDeclaration
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:228
llvm::AllocaInst::getAllocatedType
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
Definition: Instructions.h:112
llvm::StackSafetyGlobalInfoWrapperPass::ID
static char ID
Definition: StackSafetyAnalysis.h:146
llvm::StackSafetyInfoWrapperPass::ID
static char ID
Definition: StackSafetyAnalysis.h:107
llvm::StackLifetime::isReachable
bool isReachable(const Instruction *I) const
Returns true if instruction is reachable from entry.
Definition: StackLifetime.cpp:46
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
LocalPassArg
static const char LocalPassArg[]
Definition: StackSafetyAnalysis.cpp:1081
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:379
false
Definition: StackSlotColoring.cpp:142
StackSafetyMaxIterations
static cl::opt< int > StackSafetyMaxIterations("stack-safety-max-iterations", cl::init(20), cl::Hidden)
GlobalPassName
static const true char GlobalPassName[]
Definition: StackSafetyAnalysis.cpp:1089
llvm::StackSafetyGlobalInfoWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: StackSafetyAnalysis.cpp:975
llvm::StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass
StackSafetyInfoWrapperPass()
Definition: StackSafetyAnalysis.cpp:920
llvm::AllocaInst::getArraySize
const Value * getArraySize() const
Get the number of elements allocated.
Definition: Instructions.h:99
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::ConstantRange::unionWith
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
Definition: ConstantRange.cpp:569
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::StackSafetyGlobalInfo::InfoTy
Definition: StackSafetyAnalysis.cpp:223
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2088
SmallPtrSet.h
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:26
llvm::ConstantRange::add
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
Definition: ConstantRange.cpp:903
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:154
FormatVariadic.h
llvm::SetVector::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::ValueInfo
Struct that holds a reference to a particular GUID in a global value summary.
Definition: ModuleSummaryIndex.h:166
llvm::AliasSummary::hasAliasee
bool hasAliasee() const
Definition: ModuleSummaryIndex.h:471
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::StackSafetyPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: StackSafetyAnalysis.cpp:911
llvm::cl::opt
Definition: CommandLine.h:1419
llvm::StackSafetyGlobalInfo::~StackSafetyGlobalInfo
~StackSafetyGlobalInfo()
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::StackSafetyInfo::getParamAccesses
std::vector< FunctionSummary::ParamAccess > getParamAccesses(ModuleSummaryIndex &Index) const
Parameters use for a FunctionSummary.
Definition: StackSafetyAnalysis.cpp:825
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:128
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::GlobalValue
Definition: GlobalValue.h:44
VI
@ VI
Definition: SIInstrInfo.cpp:7383
llvm::ConstantRange::getBitWidth
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
Definition: ConstantRange.h:173
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::StackSafetyGlobalAnalysis
This pass performs the global (interprocedural) stack safety analysis (new pass manager).
Definition: StackSafetyAnalysis.h:120
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
StackSafetyPrint
static cl::opt< bool > StackSafetyPrint("stack-safety-print", cl::init(false), cl::Hidden)
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:80
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::StackSafetyGlobalInfo::StackSafetyGlobalInfo
StackSafetyGlobalInfo()
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DenseMap
Definition: DenseMap.h:714
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
llvm::codeview::FrameCookieKind::Copy
@ Copy
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:440
llvm::StackSafetyGlobalInfo::InfoTy::Info
GVToSSI Info
Definition: StackSafetyAnalysis.cpp:224
llvm::StackLifetime
Compute live ranges of allocas.
Definition: StackLifetime.h:38
llvm::Module::functions
iterator_range< iterator > functions()
Definition: Module.h:617
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
DEBUG_TYPE
#define DEBUG_TYPE
Definition: StackSafetyAnalysis.cpp:36
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1556
llvm::GlobalValue::isExternalLinkage
static bool isExternalLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:299
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:944
llvm::GlobalValue::isWeakLinkage
static bool isWeakLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:317
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::GlobalValue::isAvailableExternallyLinkage
static bool isAvailableExternallyLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:302
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::StackSafetyGlobalAnalysis::run
Result run(Module &M, ModuleAnalysisManager &AM)
Definition: StackSafetyAnalysis.cpp:942
llvm::StackSafetyInfo
Interface to access stack safety analysis results for single function.
Definition: StackSafetyAnalysis.h:26
llvm::StackSafetyGlobalInfoWrapperPass::StackSafetyGlobalInfoWrapperPass
StackSafetyGlobalInfoWrapperPass()
Definition: StackSafetyAnalysis.cpp:962
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::StackLifetime::run
void run()
Definition: StackLifetime.cpp:321
llvm::StackSafetyInfoWrapperPass
StackSafetyInfo wrapper for the legacy pass manager.
Definition: StackSafetyAnalysis.h:103
llvm::StackSafetyInfoWrapperPass::print
void print(raw_ostream &O, const Module *M) const override
print - Print out the internal state of the pass.
Definition: StackSafetyAnalysis.cpp:929
llvm::StackSafetyGlobalInfo::dump
void dump() const
Definition: StackSafetyAnalysis.cpp:900
llvm::StackSafetyInfoWrapperPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: StackSafetyAnalysis.cpp:933
llvm::StackSafetyGlobalPrinterPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: StackSafetyAnalysis.cpp:953
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
uint32_t
llvm::AllocaInst::isArrayAllocation
bool isArrayAllocation() const
Return true if there is an allocation size parameter to the allocation instruction that is not 1.
Definition: Instructions.cpp:1352
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
ConstantRange.h
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::RecurKind::Mul
@ Mul
Product of integers.
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:295
llvm::StackSafetyInfo::operator=
StackSafetyInfo & operator=(StackSafetyInfo &&)
llvm::GlobalValue::isLinkOnceLinkage
static bool isLinkOnceLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:308
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:205
llvm::SetVector::clear
void clear()
Completely clear the SetVector.
Definition: SetVector.h:220
llvm::APInt::getNullValue
static APInt getNullValue(unsigned numBits)
Get the '0' value.
Definition: APInt.h:574
llvm::GlobalValue::isInterposable
bool isInterposable() const
Return true if this global's definition can be substituted with an arbitrary definition at link time ...
Definition: Globals.cpp:98
llvm::StackSafetyGlobalInfoWrapperPass::print
void print(raw_ostream &O, const Module *M) const override
print - Print out the internal state of the pass.
Definition: StackSafetyAnalysis.cpp:970
llvm::FunctionSummary
Function summary information to aid decisions and implementation of importing.
Definition: ModuleSummaryIndex.h:511
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
std
Definition: BitVector.h:941
llvm::Type::getIntNTy
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:201
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::FunctionSummary::ParamAccess::RangeWidth
static constexpr uint32_t RangeWidth
Definition: ModuleSummaryIndex.h:577
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::TypeSize
Definition: TypeSize.h:413
Casting.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1439
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::StackSafetyInfo::~StackSafetyInfo
~StackSafetyInfo()
llvm::ConstantRange
This class represents a range of values.
Definition: ConstantRange.h:47
llvm::StackSafetyGlobalInfoWrapperPass
This pass performs the global (interprocedural) stack safety analysis (legacy pass manager).
Definition: StackSafetyAnalysis.h:142
ScalarEvolutionExpressions.h
Instructions.h
llvm::StackSafetyInfo::getInfo
const InfoTy & getInfo() const
Definition: StackSafetyAnalysis.cpp:785
SmallVector.h
llvm::GlobalValueSummary::getBaseObject
GlobalValueSummary * getBaseObject()
If this is an alias summary, returns the summary of the aliased object (a global variable or function...
Definition: ModuleSummaryIndex.h:497
llvm::ModuleSummaryIndex
Class to hold module path string table and global value map, and encapsulate methods for operating on...
Definition: ModuleSummaryIndex.h:1026
llvm::FunctionSummary::ParamAccess
Describes the uses of a parameter by the function.
Definition: ModuleSummaryIndex.h:576
llvm::ConstantRange::signedAddMayOverflow
OverflowResult signedAddMayOverflow(const ConstantRange &Other) const
Return whether signed add of the two ranges always/never overflows.
Definition: ConstantRange.cpp:1565
llvm::FunctionSummary::ParamAccess::Call
Describes the use of a value in a call instruction, specifying the call's target, the value's paramet...
Definition: ModuleSummaryIndex.h:582
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName, false, true) INITIALIZE_PASS_END(StackSafetyInfoWrapperPass
llvm::ConstantRange::OverflowResult::NeverOverflows
@ NeverOverflows
Never overflows.
llvm::StackSafetyGlobalInfoWrapperPass::runOnModule
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
Definition: StackSafetyAnalysis.cpp:981
llvm::AnalysisUsage::addRequiredTransitive
AnalysisUsage & addRequiredTransitive()
Definition: PassAnalysisSupport.h:81
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:397
DerivedTypes.h
llvm::StackSafetyGlobalInfo
Definition: StackSafetyAnalysis.h:58
llvm::SetVector::back
const T & back() const
Return the last element of the SetVector.
Definition: SetVector.h:128
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:43
llvm::StackSafetyGlobalInfo::print
void print(raw_ostream &O) const
Definition: StackSafetyAnalysis.cpp:887
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:969
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:61
llvm::ConstantRange::isEmptySet
bool isEmptySet() const
Return true if this set contains no members.
Definition: ConstantRange.cpp:309
llvm::ConstantRange::sextOrTrunc
ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
Definition: ConstantRange.cpp:783
raw_ostream.h
llvm::SI::KernelInputOffsets::Offsets
Offsets
Offsets in bytes from the start of the input buffer.
Definition: SIInstrInfo.h:1224
llvm::StackSafetyInfo::InfoTy
Definition: StackSafetyAnalysis.cpp:219
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
llvm::CodeGenOpt::Less
@ Less
Definition: CodeGen.h:54
llvm::GlobalValue::isDSOLocal
bool isDSOLocal() const
Definition: GlobalValue.h:282
llvm::StackSafetyGlobalInfoWrapperPass::~StackSafetyGlobalInfoWrapperPass
~StackSafetyGlobalInfoWrapperPass()
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1827
llvm::ConstantRange::getUpper
const APInt & getUpper() const
Return the upper value for this range.
Definition: ConstantRange.h:170
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
StackSafetyRun
static cl::opt< bool > StackSafetyRun("stack-safety-run", cl::init(false), cl::Hidden)
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37