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