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