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