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.getMaxPointerSizeInBits();
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->getBaseObject();
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 
755  uint32_t PointerSize = Copy.begin()
756  ->first->getParent()
757  ->getDataLayout()
758  .getMaxPointerSizeInBits();
759  StackSafetyDataFlowAnalysis<GlobalValue> SSDFA(PointerSize, std::move(Copy));
760 
761  for (auto &F : SSDFA.run()) {
762  auto FI = F.second;
763  auto &SrcF = Functions[F.first];
764  for (auto &KV : FI.Allocas) {
765  auto &A = KV.second;
766  resolveAllCalls(A, Index);
767  for (auto &C : A.Calls) {
768  A.updateRange(SSDFA.getArgumentAccessRange(C.first.Callee,
769  C.first.ParamNo, C.second));
770  }
771  // FIXME: This is needed only to preserve calls in print() results.
772  A.Calls = SrcF.Allocas.find(KV.first)->second.Calls;
773  }
774  for (auto &KV : FI.Params) {
775  auto &P = KV.second;
776  P.Calls = SrcF.Params.find(KV.first)->second.Calls;
777  }
778  SSI[F.first] = std::move(FI);
779  }
780 
781  return SSI;
782 }
783 
784 } // end anonymous namespace
785 
787 
789  std::function<ScalarEvolution &()> GetSE)
790  : F(F), GetSE(GetSE) {}
791 
793 
795 
797 
799  if (!Info) {
800  StackSafetyLocalAnalysis SSLA(*F, GetSE());
801  Info.reset(new InfoTy{SSLA.run()});
802  }
803  return *Info;
804 }
805 
807  getInfo().Info.print(O, F->getName(), dyn_cast<Function>(F));
808  O << "\n";
809 }
810 
811 const StackSafetyGlobalInfo::InfoTy &StackSafetyGlobalInfo::getInfo() const {
812  if (!Info) {
813  std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions;
814  for (auto &F : M->functions()) {
815  if (!F.isDeclaration()) {
816  auto FI = GetSSI(F).getInfo().Info;
817  Functions.emplace(&F, std::move(FI));
818  }
819  }
820  Info.reset(new InfoTy{
821  createGlobalStackSafetyInfo(std::move(Functions), Index), {}, {}});
822 
823  for (auto &FnKV : Info->Info) {
824  for (auto &KV : FnKV.second.Allocas) {
825  ++NumAllocaTotal;
826  const AllocaInst *AI = KV.first;
827  auto AIRange = getStaticAllocaSizeRange(*AI);
828  if (AIRange.contains(KV.second.Range)) {
829  Info->SafeAllocas.insert(AI);
830  ++NumAllocaStackSafe;
831  }
832  for (const auto &A : KV.second.Accesses)
833  Info->AccessIsUnsafe[A.first] |= !AIRange.contains(A.second);
834  }
835  }
836 
837  if (StackSafetyPrint)
838  print(errs());
839  }
840  return *Info;
841 }
842 
843 std::vector<FunctionSummary::ParamAccess>
845  // Implementation transforms internal representation of parameter information
846  // into FunctionSummary format.
847  std::vector<FunctionSummary::ParamAccess> ParamAccesses;
848  for (const auto &KV : getInfo().Info.Params) {
849  auto &PS = KV.second;
850  // Parameter accessed by any or unknown offset, represented as FullSet by
851  // StackSafety, is handled as the parameter for which we have no
852  // StackSafety info at all. So drop it to reduce summary size.
853  if (PS.Range.isFullSet())
854  continue;
855 
856  ParamAccesses.emplace_back(KV.first, PS.Range);
857  FunctionSummary::ParamAccess &Param = ParamAccesses.back();
858 
859  Param.Calls.reserve(PS.Calls.size());
860  for (auto &C : PS.Calls) {
861  // Parameter forwarded into another function by any or unknown offset
862  // will make ParamAccess::Range as FullSet anyway. So we can drop the
863  // entire parameter like we did above.
864  // TODO(vitalybuka): Return already filtered parameters from getInfo().
865  if (C.second.isFullSet()) {
866  ParamAccesses.pop_back();
867  break;
868  }
869  Param.Calls.emplace_back(C.first.ParamNo,
870  Index.getOrInsertValueInfo(C.first.Callee),
871  C.second);
872  }
873  }
874  for (FunctionSummary::ParamAccess &Param : ParamAccesses) {
875  sort(Param.Calls, [](const FunctionSummary::ParamAccess::Call &L,
877  return std::tie(L.ParamNo, L.Callee) < std::tie(R.ParamNo, R.Callee);
878  });
879  }
880  return ParamAccesses;
881 }
882 
884 
886  Module *M, std::function<const StackSafetyInfo &(Function &F)> GetSSI,
887  const ModuleSummaryIndex *Index)
888  : M(M), GetSSI(GetSSI), Index(Index) {
889  if (StackSafetyRun)
890  getInfo();
891 }
892 
894  default;
895 
898 
900 
902  const auto &Info = getInfo();
903  return Info.SafeAllocas.count(&AI);
904 }
905 
907  const auto &Info = getInfo();
908  auto It = Info.AccessIsUnsafe.find(&I);
909  if (It == Info.AccessIsUnsafe.end()) {
910  return true;
911  }
912  return !It->second;
913 }
914 
916  auto &SSI = getInfo().Info;
917  if (SSI.empty())
918  return;
919  const Module &M = *SSI.begin()->first->getParent();
920  for (auto &F : M.functions()) {
921  if (!F.isDeclaration()) {
922  SSI.find(&F)->second.print(O, F.getName(), &F);
923  O << " safe accesses:"
924  << "\n";
925  for (const auto &I : instructions(F)) {
926  const CallInst *Call = dyn_cast<CallInst>(&I);
927  if ((isa<StoreInst>(I) || isa<LoadInst>(I) || isa<MemIntrinsic>(I) ||
928  (Call && Call->hasByValArgument())) &&
929  stackAccessIsSafe(I)) {
930  O << " " << I << "\n";
931  }
932  }
933  O << "\n";
934  }
935  }
936 }
937 
939 
940 AnalysisKey StackSafetyAnalysis::Key;
941 
944  return StackSafetyInfo(&F, [&AM, &F]() -> ScalarEvolution & {
945  return AM.getResult<ScalarEvolutionAnalysis>(F);
946  });
947 }
948 
951  OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n";
953  return PreservedAnalyses::all();
954 }
955 
957 
960 }
961 
964  AU.setPreservesAll();
965 }
966 
968  SSI.print(O);
969 }
970 
972  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
973  SSI = {&F, [SE]() -> ScalarEvolution & { return *SE; }};
974  return false;
975 }
976 
977 AnalysisKey StackSafetyGlobalAnalysis::Key;
978 
981  // FIXME: Lookup Module Summary.
984  return {&M,
985  [&FAM](Function &F) -> const StackSafetyInfo & {
987  },
988  nullptr};
989 }
990 
992  ModuleAnalysisManager &AM) {
993  OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n";
995  return PreservedAnalyses::all();
996 }
997 
999 
1001  : ModulePass(ID) {
1004 }
1005 
1007 
1009  const Module *M) const {
1010  SSGI.print(O);
1011 }
1012 
1014  AnalysisUsage &AU) const {
1015  AU.setPreservesAll();
1017 }
1018 
1020  const ModuleSummaryIndex *ImportSummary = nullptr;
1021  if (auto *IndexWrapperPass =
1022  getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>())
1023  ImportSummary = IndexWrapperPass->getIndex();
1024 
1025  SSGI = {&M,
1026  [this](Function &F) -> const StackSafetyInfo & {
1027  return getAnalysis<StackSafetyInfoWrapperPass>(F).getResult();
1028  },
1029  ImportSummary};
1030  return false;
1031 }
1032 
1034  if (StackSafetyRun)
1035  return true;
1036  for (auto &F : M.functions())
1037  if (F.hasFnAttribute(Attribute::SanitizeMemTag))
1038  return true;
1039  return false;
1040 }
1041 
1043  if (!Index.hasParamAccess())
1044  return;
1046 
1047  auto CountParamAccesses = [&](auto &Stat) {
1048  if (!AreStatisticsEnabled())
1049  return;
1050  for (auto &GVS : Index)
1051  for (auto &GV : GVS.second.SummaryList)
1052  if (FunctionSummary *FS = dyn_cast<FunctionSummary>(GV.get()))
1053  Stat += FS->paramAccesses().size();
1054  };
1055 
1056  CountParamAccesses(NumCombinedParamAccessesBefore);
1057 
1058  std::map<const FunctionSummary *, FunctionInfo<FunctionSummary>> Functions;
1059 
1060  // Convert the ModuleSummaryIndex to a FunctionMap
1061  for (auto &GVS : Index) {
1062  for (auto &GV : GVS.second.SummaryList) {
1063  FunctionSummary *FS = dyn_cast<FunctionSummary>(GV.get());
1064  if (!FS || FS->paramAccesses().empty())
1065  continue;
1066  if (FS->isLive() && FS->isDSOLocal()) {
1067  FunctionInfo<FunctionSummary> FI;
1068  for (auto &PS : FS->paramAccesses()) {
1069  auto &US =
1070  FI.Params
1071  .emplace(PS.ParamNo, FunctionSummary::ParamAccess::RangeWidth)
1072  .first->second;
1073  US.Range = PS.Use;
1074  for (auto &Call : PS.Calls) {
1075  assert(!Call.Offsets.isFullSet());
1076  FunctionSummary *S =
1077  findCalleeFunctionSummary(Call.Callee, FS->modulePath());
1078  ++NumCombinedCalleeLookupTotal;
1079  if (!S) {
1080  ++NumCombinedCalleeLookupFailed;
1081  US.Range = FullSet;
1082  US.Calls.clear();
1083  break;
1084  }
1085  US.Calls.emplace(CallInfo<FunctionSummary>(S, Call.ParamNo),
1086  Call.Offsets);
1087  }
1088  }
1089  Functions.emplace(FS, std::move(FI));
1090  }
1091  // Reset data for all summaries. Alive and DSO local will be set back from
1092  // of data flow results below. Anything else will not be accessed
1093  // by ThinLTO backend, so we can save on bitcode size.
1094  FS->setParamAccesses({});
1095  }
1096  }
1097  NumCombinedDataFlowNodes += Functions.size();
1098  StackSafetyDataFlowAnalysis<FunctionSummary> SSDFA(
1100  for (auto &KV : SSDFA.run()) {
1101  std::vector<FunctionSummary::ParamAccess> NewParams;
1102  NewParams.reserve(KV.second.Params.size());
1103  for (auto &Param : KV.second.Params) {
1104  // It's not needed as FullSet is processed the same as a missing value.
1105  if (Param.second.Range.isFullSet())
1106  continue;
1107  NewParams.emplace_back();
1108  FunctionSummary::ParamAccess &New = NewParams.back();
1109  New.ParamNo = Param.first;
1110  New.Use = Param.second.Range; // Only range is needed.
1111  }
1112  const_cast<FunctionSummary *>(KV.first)->setParamAccesses(
1113  std::move(NewParams));
1114  }
1115 
1116  CountParamAccesses(NumCombinedParamAccessesAfter);
1117 }
1118 
1119 static const char LocalPassArg[] = "stack-safety-local";
1120 static const char LocalPassName[] = "Stack Safety Local Analysis";
1122  false, true)
1126 
1127 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:2036
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
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:491
llvm
---------------------— PointerInfo ------------------------------------—
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:901
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::StackSafetyInfo::print
void print(raw_ostream &O) const
Definition: StackSafetyAnalysis.cpp:806
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:255
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:779
InstIterator.h
llvm::TypeSize::getFixedSize
ScalarTy getFixedSize() const
Definition: TypeSize.h:426
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::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:962
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:461
llvm::GlobalAlias
Definition: GlobalAlias.h:27
llvm::AliasSummary
Alias summary information.
Definition: ModuleSummaryIndex.h:449
LocalPassName
static const char LocalPassName[]
Definition: StackSafetyAnalysis.cpp:1120
llvm::initializeStackSafetyGlobalInfoWrapperPassPass
void initializeStackSafetyGlobalInfoWrapperPassPass(PassRegistry &)
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
APInt.h
llvm::needsParamAccessSummary
bool needsParamAccessSummary(const Module &M)
Definition: StackSafetyAnalysis.cpp:1033
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:892
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:942
llvm::generateParamAccessSummary
void generateParamAccessSummary(ModuleSummaryIndex &Index)
Definition: StackSafetyAnalysis.cpp:1042
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:314
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:1119
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:377
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:1127
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:1013
llvm::Instruction
Definition: Instruction.h:45
llvm::StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass
StackSafetyInfoWrapperPass()
Definition: StackSafetyAnalysis.cpp:958
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:2066
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:949
llvm::cl::opt
Definition: CommandLine.h:1434
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:844
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:7679
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:443
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
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: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:980
llvm::StackSafetyInfo
Interface to access stack safety analysis results for single function.
Definition: StackSafetyAnalysis.h:26
llvm::StackSafetyGlobalInfoWrapperPass::StackSafetyGlobalInfoWrapperPass
StackSafetyGlobalInfoWrapperPass()
Definition: StackSafetyAnalysis.cpp:1000
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:967
llvm::StackSafetyGlobalInfo::dump
void dump() const
Definition: StackSafetyAnalysis.cpp:938
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:971
llvm::StackSafetyGlobalPrinterPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: StackSafetyAnalysis.cpp:991
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::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
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: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:1008
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:207
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:579
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::X86AS::FS
@ FS
Definition: X86.h:188
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:906
Instructions.h
llvm::StackSafetyInfo::getInfo
const InfoTy & getInfo() const
Definition: StackSafetyAnalysis.cpp:798
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:1030
llvm::FunctionSummary::ParamAccess
Describes the uses of a parameter by the function.
Definition: ModuleSummaryIndex.h:578
llvm::ConstantRange::signedAddMayOverflow
OverflowResult signedAddMayOverflow(const ConstantRange &Other) const
Return whether signed add of the two ranges always/never overflows.
Definition: ConstantRange.cpp:1587
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:584
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:1019
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:915
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:936
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:1262
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:1857
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:75
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