LLVM  9.0.0svn
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 
13 #include "llvm/IR/CallSite.h"
14 #include "llvm/IR/InstIterator.h"
15 #include "llvm/IR/IntrinsicInst.h"
17 
18 using namespace llvm;
19 
20 #define DEBUG_TYPE "stack-safety"
21 
22 static cl::opt<int> StackSafetyMaxIterations("stack-safety-max-iterations",
23  cl::init(20), cl::Hidden);
24 
25 namespace {
26 
27 /// Rewrite an SCEV expression for a memory access address to an expression that
28 /// represents offset from the given alloca.
29 class AllocaOffsetRewriter : public SCEVRewriteVisitor<AllocaOffsetRewriter> {
30  const Value *AllocaPtr;
31 
32 public:
33  AllocaOffsetRewriter(ScalarEvolution &SE, const Value *AllocaPtr)
34  : SCEVRewriteVisitor(SE), AllocaPtr(AllocaPtr) {}
35 
36  const SCEV *visit(const SCEV *Expr) {
37  // Only re-write the expression if the alloca is used in an addition
38  // expression (it can be used in other types of expressions if it's cast to
39  // an int and passed as an argument.)
40  if (!isa<SCEVAddRecExpr>(Expr) && !isa<SCEVAddExpr>(Expr) &&
41  !isa<SCEVUnknown>(Expr))
42  return Expr;
44  }
45 
46  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
47  // FIXME: look through one or several levels of definitions?
48  // This can be inttoptr(AllocaPtr) and SCEV would not unwrap
49  // it for us.
50  if (Expr->getValue() == AllocaPtr)
51  return SE.getZero(Expr->getType());
52  return Expr;
53  }
54 };
55 
56 /// Describes use of address in as a function call argument.
57 struct PassAsArgInfo {
58  /// Function being called.
59  const GlobalValue *Callee = nullptr;
60  /// Index of argument which pass address.
61  size_t ParamNo = 0;
62  // Offset range of address from base address (alloca or calling function
63  // argument).
64  // Range should never set to empty-set, that is an invalid access range
65  // that can cause empty-set to be propagated with ConstantRange::add
67  PassAsArgInfo(const GlobalValue *Callee, size_t ParamNo, ConstantRange Offset)
68  : Callee(Callee), ParamNo(ParamNo), Offset(Offset) {}
69 
70  StringRef getName() const { return Callee->getName(); }
71 };
72 
73 raw_ostream &operator<<(raw_ostream &OS, const PassAsArgInfo &P) {
74  return OS << "@" << P.getName() << "(arg" << P.ParamNo << ", " << P.Offset
75  << ")";
76 }
77 
78 /// Describe uses of address (alloca or parameter) inside of the function.
79 struct UseInfo {
80  // Access range if the address (alloca or parameters).
81  // It is allowed to be empty-set when there are no known accesses.
82  ConstantRange Range;
83 
84  // List of calls which pass address as an argument.
86 
87  explicit UseInfo(unsigned PointerSize) : Range{PointerSize, false} {}
88 
89  void updateRange(ConstantRange R) { Range = Range.unionWith(R); }
90 };
91 
92 raw_ostream &operator<<(raw_ostream &OS, const UseInfo &U) {
93  OS << U.Range;
94  for (auto &Call : U.Calls)
95  OS << ", " << Call;
96  return OS;
97 }
98 
99 struct AllocaInfo {
100  const AllocaInst *AI = nullptr;
101  uint64_t Size = 0;
102  UseInfo Use;
103 
104  AllocaInfo(unsigned PointerSize, const AllocaInst *AI, uint64_t Size)
105  : AI(AI), Size(Size), Use(PointerSize) {}
106 
107  StringRef getName() const { return AI->getName(); }
108 };
109 
110 raw_ostream &operator<<(raw_ostream &OS, const AllocaInfo &A) {
111  return OS << A.getName() << "[" << A.Size << "]: " << A.Use;
112 }
113 
114 struct ParamInfo {
115  const Argument *Arg = nullptr;
116  UseInfo Use;
117 
118  explicit ParamInfo(unsigned PointerSize, const Argument *Arg)
119  : Arg(Arg), Use(PointerSize) {}
120 
121  StringRef getName() const { return Arg ? Arg->getName() : "<N/A>"; }
122 };
123 
124 raw_ostream &operator<<(raw_ostream &OS, const ParamInfo &P) {
125  return OS << P.getName() << "[]: " << P.Use;
126 }
127 
128 /// Calculate the allocation size of a given alloca. Returns 0 if the
129 /// size can not be statically determined.
130 uint64_t getStaticAllocaAllocationSize(const AllocaInst *AI) {
131  const DataLayout &DL = AI->getModule()->getDataLayout();
132  uint64_t Size = DL.getTypeAllocSize(AI->getAllocatedType());
133  if (AI->isArrayAllocation()) {
134  auto C = dyn_cast<ConstantInt>(AI->getArraySize());
135  if (!C)
136  return 0;
137  Size *= C->getZExtValue();
138  }
139  return Size;
140 }
141 
142 } // end anonymous namespace
143 
144 /// Describes uses of allocas and parameters inside of a single function.
146  // May be a Function or a GlobalAlias
147  const GlobalValue *GV = nullptr;
148  // Informations about allocas uses.
150  // Informations about parameters uses.
152  // TODO: describe return value as depending on one or more of its arguments.
153 
154  // StackSafetyDataFlowAnalysis counter stored here for faster access.
155  int UpdateCount = 0;
156 
158 
159  explicit FunctionInfo(const Function *F) : GV(F){};
160  // Creates FunctionInfo that forwards all the parameters to the aliasee.
161  explicit FunctionInfo(const GlobalAlias *A);
162 
163  FunctionInfo(FunctionInfo &&) = default;
164 
165  bool IsDSOLocal() const { return GV->isDSOLocal(); };
166 
167  bool IsInterposable() const { return GV->isInterposable(); };
168 
169  StringRef getName() const { return GV->getName(); }
170 
171  void print(raw_ostream &O) const {
172  // TODO: Consider different printout format after
173  // StackSafetyDataFlowAnalysis. Calls and parameters are irrelevant then.
174  O << " @" << getName() << (IsDSOLocal() ? "" : " dso_preemptable")
175  << (IsInterposable() ? " interposable" : "") << "\n";
176  O << " args uses:\n";
177  for (auto &P : Params)
178  O << " " << P << "\n";
179  O << " allocas uses:\n";
180  for (auto &AS : Allocas)
181  O << " " << AS << "\n";
182  }
183 
184 private:
185  FunctionInfo(const FunctionInfo &) = default;
186 };
187 
189  unsigned PointerSize = A->getParent()->getDataLayout().getPointerSizeInBits();
190  const GlobalObject *Aliasee = A->getBaseObject();
191  const FunctionType *Type = cast<FunctionType>(Aliasee->getValueType());
192  // 'Forward' all parameters to this alias to the aliasee
193  for (unsigned ArgNo = 0; ArgNo < Type->getNumParams(); ArgNo++) {
194  Params.emplace_back(PointerSize, nullptr);
195  UseInfo &US = Params.back().Use;
196  US.Calls.emplace_back(Aliasee, ArgNo, ConstantRange(APInt(PointerSize, 0)));
197  }
198 }
199 
200 namespace {
201 
202 class StackSafetyLocalAnalysis {
203  const Function &F;
204  const DataLayout &DL;
205  ScalarEvolution &SE;
206  unsigned PointerSize = 0;
207 
208  const ConstantRange UnknownRange;
209 
210  ConstantRange offsetFromAlloca(Value *Addr, const Value *AllocaPtr);
211  ConstantRange getAccessRange(Value *Addr, const Value *AllocaPtr,
212  uint64_t AccessSize);
213  ConstantRange getMemIntrinsicAccessRange(const MemIntrinsic *MI, const Use &U,
214  const Value *AllocaPtr);
215 
216  bool analyzeAllUses(const Value *Ptr, UseInfo &AS);
217 
218  ConstantRange getRange(uint64_t Lower, uint64_t Upper) const {
219  return ConstantRange(APInt(PointerSize, Lower), APInt(PointerSize, Upper));
220  }
221 
222 public:
223  StackSafetyLocalAnalysis(const Function &F, ScalarEvolution &SE)
224  : F(F), DL(F.getParent()->getDataLayout()), SE(SE),
225  PointerSize(DL.getPointerSizeInBits()),
226  UnknownRange(PointerSize, true) {}
227 
228  // Run the transformation on the associated function.
229  StackSafetyInfo run();
230 };
231 
233 StackSafetyLocalAnalysis::offsetFromAlloca(Value *Addr,
234  const Value *AllocaPtr) {
235  if (!SE.isSCEVable(Addr->getType()))
236  return UnknownRange;
237 
238  AllocaOffsetRewriter Rewriter(SE, AllocaPtr);
239  const SCEV *Expr = Rewriter.visit(SE.getSCEV(Addr));
240  ConstantRange Offset = SE.getUnsignedRange(Expr).zextOrTrunc(PointerSize);
241  assert(!Offset.isEmptySet());
242  return Offset;
243 }
244 
245 ConstantRange StackSafetyLocalAnalysis::getAccessRange(Value *Addr,
246  const Value *AllocaPtr,
247  uint64_t AccessSize) {
248  if (!SE.isSCEVable(Addr->getType()))
249  return UnknownRange;
250 
251  AllocaOffsetRewriter Rewriter(SE, AllocaPtr);
252  const SCEV *Expr = Rewriter.visit(SE.getSCEV(Addr));
253 
254  ConstantRange AccessStartRange =
255  SE.getUnsignedRange(Expr).zextOrTrunc(PointerSize);
256  ConstantRange SizeRange = getRange(0, AccessSize);
257  ConstantRange AccessRange = AccessStartRange.add(SizeRange);
258  assert(!AccessRange.isEmptySet());
259  return AccessRange;
260 }
261 
262 ConstantRange StackSafetyLocalAnalysis::getMemIntrinsicAccessRange(
263  const MemIntrinsic *MI, const Use &U, const Value *AllocaPtr) {
264  if (auto MTI = dyn_cast<MemTransferInst>(MI)) {
265  if (MTI->getRawSource() != U && MTI->getRawDest() != U)
266  return getRange(0, 1);
267  } else {
268  if (MI->getRawDest() != U)
269  return getRange(0, 1);
270  }
271  const auto *Len = dyn_cast<ConstantInt>(MI->getLength());
272  // Non-constant size => unsafe. FIXME: try SCEV getRange.
273  if (!Len)
274  return UnknownRange;
275  ConstantRange AccessRange = getAccessRange(U, AllocaPtr, Len->getZExtValue());
276  return AccessRange;
277 }
278 
279 /// The function analyzes all local uses of Ptr (alloca or argument) and
280 /// calculates local access range and all function calls where it was used.
281 bool StackSafetyLocalAnalysis::analyzeAllUses(const Value *Ptr, UseInfo &US) {
284  WorkList.push_back(Ptr);
285 
286  // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc.
287  while (!WorkList.empty()) {
288  const Value *V = WorkList.pop_back_val();
289  for (const Use &UI : V->uses()) {
290  auto I = cast<const Instruction>(UI.getUser());
291  assert(V == UI.get());
292 
293  switch (I->getOpcode()) {
294  case Instruction::Load: {
295  US.updateRange(
296  getAccessRange(UI, Ptr, DL.getTypeStoreSize(I->getType())));
297  break;
298  }
299 
300  case Instruction::VAArg:
301  // "va-arg" from a pointer is safe.
302  break;
303  case Instruction::Store: {
304  if (V == I->getOperand(0)) {
305  // Stored the pointer - conservatively assume it may be unsafe.
306  US.updateRange(UnknownRange);
307  return false;
308  }
309  US.updateRange(getAccessRange(
310  UI, Ptr, DL.getTypeStoreSize(I->getOperand(0)->getType())));
311  break;
312  }
313 
314  case Instruction::Ret:
315  // Information leak.
316  // FIXME: Process parameters correctly. This is a leak only if we return
317  // alloca.
318  US.updateRange(UnknownRange);
319  return false;
320 
321  case Instruction::Call:
322  case Instruction::Invoke: {
323  ImmutableCallSite CS(I);
324 
325  if (I->isLifetimeStartOrEnd())
326  break;
327 
328  if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
329  US.updateRange(getMemIntrinsicAccessRange(MI, UI, Ptr));
330  break;
331  }
332 
333  // FIXME: consult devirt?
334  // Do not follow aliases, otherwise we could inadvertently follow
335  // dso_preemptable aliases or aliases with interposable linkage.
336  const GlobalValue *Callee = dyn_cast<GlobalValue>(
338  if (!Callee) {
339  US.updateRange(UnknownRange);
340  return false;
341  }
342 
343  assert(isa<Function>(Callee) || isa<GlobalAlias>(Callee));
344 
346  for (ImmutableCallSite::arg_iterator A = B; A != E; ++A) {
347  if (A->get() == V) {
348  ConstantRange Offset = offsetFromAlloca(UI, Ptr);
349  US.Calls.emplace_back(Callee, A - B, Offset);
350  }
351  }
352 
353  break;
354  }
355 
356  default:
357  if (Visited.insert(I).second)
358  WorkList.push_back(cast<const Instruction>(I));
359  }
360  }
361  }
362 
363  return true;
364 }
365 
366 StackSafetyInfo StackSafetyLocalAnalysis::run() {
368  assert(!F.isDeclaration() &&
369  "Can't run StackSafety on a function declaration");
370 
371  LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n");
372 
373  for (auto &I : instructions(F)) {
374  if (auto AI = dyn_cast<AllocaInst>(&I)) {
375  Info.Allocas.emplace_back(PointerSize, AI,
376  getStaticAllocaAllocationSize(AI));
377  AllocaInfo &AS = Info.Allocas.back();
378  analyzeAllUses(AI, AS.Use);
379  }
380  }
381 
382  for (const Argument &A : make_range(F.arg_begin(), F.arg_end())) {
383  Info.Params.emplace_back(PointerSize, &A);
384  ParamInfo &PS = Info.Params.back();
385  analyzeAllUses(&A, PS.Use);
386  }
387 
388  LLVM_DEBUG(dbgs() << "[StackSafety] done\n");
389  LLVM_DEBUG(Info.print(dbgs()));
390  return StackSafetyInfo(std::move(Info));
391 }
392 
393 class StackSafetyDataFlowAnalysis {
394  using FunctionMap =
395  std::map<const GlobalValue *, StackSafetyInfo::FunctionInfo>;
396 
397  FunctionMap Functions;
398  // Callee-to-Caller multimap.
401 
402  unsigned PointerSize = 0;
403  const ConstantRange UnknownRange;
404 
405  ConstantRange getArgumentAccessRange(const GlobalValue *Callee,
406  unsigned ParamNo) const;
407  bool updateOneUse(UseInfo &US, bool UpdateToFullSet);
408  void updateOneNode(const GlobalValue *Callee,
410  void updateOneNode(const GlobalValue *Callee) {
411  updateOneNode(Callee, Functions.find(Callee)->second);
412  }
413  void updateAllNodes() {
414  for (auto &F : Functions)
415  updateOneNode(F.first, F.second);
416  }
417  void runDataFlow();
418  void verifyFixedPoint();
419 
420 public:
421  StackSafetyDataFlowAnalysis(
422  Module &M, std::function<const StackSafetyInfo &(Function &)> FI);
423  StackSafetyGlobalInfo run();
424 };
425 
426 StackSafetyDataFlowAnalysis::StackSafetyDataFlowAnalysis(
427  Module &M, std::function<const StackSafetyInfo &(Function &)> FI)
428  : PointerSize(M.getDataLayout().getPointerSizeInBits()),
429  UnknownRange(PointerSize, true) {
430  // Without ThinLTO, run the local analysis for every function in the TU and
431  // then run the DFA.
432  for (auto &F : M.functions())
433  if (!F.isDeclaration())
434  Functions.emplace(&F, FI(F));
435  for (auto &A : M.aliases())
436  if (isa<Function>(A.getBaseObject()))
437  Functions.emplace(&A, StackSafetyInfo::FunctionInfo(&A));
438 }
439 
441 StackSafetyDataFlowAnalysis::getArgumentAccessRange(const GlobalValue *Callee,
442  unsigned ParamNo) const {
443  auto IT = Functions.find(Callee);
444  // Unknown callee (outside of LTO domain or an indirect call).
445  if (IT == Functions.end())
446  return UnknownRange;
447  const StackSafetyInfo::FunctionInfo &FS = IT->second;
448  // The definition of this symbol may not be the definition in this linkage
449  // unit.
450  if (!FS.IsDSOLocal() || FS.IsInterposable())
451  return UnknownRange;
452  if (ParamNo >= FS.Params.size()) // possibly vararg
453  return UnknownRange;
454  return FS.Params[ParamNo].Use.Range;
455 }
456 
457 bool StackSafetyDataFlowAnalysis::updateOneUse(UseInfo &US,
458  bool UpdateToFullSet) {
459  bool Changed = false;
460  for (auto &CS : US.Calls) {
461  assert(!CS.Offset.isEmptySet() &&
462  "Param range can't be empty-set, invalid offset range");
463 
464  ConstantRange CalleeRange = getArgumentAccessRange(CS.Callee, CS.ParamNo);
465  CalleeRange = CalleeRange.add(CS.Offset);
466  if (!US.Range.contains(CalleeRange)) {
467  Changed = true;
468  if (UpdateToFullSet)
469  US.Range = UnknownRange;
470  else
471  US.Range = US.Range.unionWith(CalleeRange);
472  }
473  }
474  return Changed;
475 }
476 
477 void StackSafetyDataFlowAnalysis::updateOneNode(
478  const GlobalValue *Callee, StackSafetyInfo::FunctionInfo &FS) {
479  bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations;
480  bool Changed = false;
481  for (auto &AS : FS.Allocas)
482  Changed |= updateOneUse(AS.Use, UpdateToFullSet);
483  for (auto &PS : FS.Params)
484  Changed |= updateOneUse(PS.Use, UpdateToFullSet);
485 
486  if (Changed) {
487  LLVM_DEBUG(dbgs() << "=== update [" << FS.UpdateCount
488  << (UpdateToFullSet ? ", full-set" : "") << "] "
489  << FS.getName() << "\n");
490  // Callers of this function may need updating.
491  for (auto &CallerID : Callers[Callee])
492  WorkList.insert(CallerID);
493 
494  ++FS.UpdateCount;
495  }
496 }
497 
498 void StackSafetyDataFlowAnalysis::runDataFlow() {
499  Callers.clear();
500  WorkList.clear();
501 
503  for (auto &F : Functions) {
504  Callees.clear();
505  StackSafetyInfo::FunctionInfo &FS = F.second;
506  for (auto &AS : FS.Allocas)
507  for (auto &CS : AS.Use.Calls)
508  Callees.push_back(CS.Callee);
509  for (auto &PS : FS.Params)
510  for (auto &CS : PS.Use.Calls)
511  Callees.push_back(CS.Callee);
512 
513  llvm::sort(Callees);
514  Callees.erase(std::unique(Callees.begin(), Callees.end()), Callees.end());
515 
516  for (auto &Callee : Callees)
517  Callers[Callee].push_back(F.first);
518  }
519 
520  updateAllNodes();
521 
522  while (!WorkList.empty()) {
523  const GlobalValue *Callee = WorkList.back();
524  WorkList.pop_back();
525  updateOneNode(Callee);
526  }
527 }
528 
529 void StackSafetyDataFlowAnalysis::verifyFixedPoint() {
530  WorkList.clear();
531  updateAllNodes();
532  assert(WorkList.empty());
533 }
534 
535 StackSafetyGlobalInfo StackSafetyDataFlowAnalysis::run() {
536  runDataFlow();
537  LLVM_DEBUG(verifyFixedPoint());
538 
540  for (auto &F : Functions)
541  SSI.emplace(F.first, std::move(F.second));
542  return SSI;
543 }
544 
545 void print(const StackSafetyGlobalInfo &SSI, raw_ostream &O, const Module &M) {
546  size_t Count = 0;
547  for (auto &F : M.functions())
548  if (!F.isDeclaration()) {
549  SSI.find(&F)->second.print(O);
550  O << "\n";
551  ++Count;
552  }
553  for (auto &A : M.aliases()) {
554  SSI.find(&A)->second.print(O);
555  O << "\n";
556  ++Count;
557  }
558  assert(Count == SSI.size() && "Unexpected functions in the result");
559 }
560 
561 } // end anonymous namespace
562 
563 StackSafetyInfo::StackSafetyInfo() = default;
564 StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default;
565 StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default;
566 
567 StackSafetyInfo::StackSafetyInfo(FunctionInfo &&Info)
568  : Info(new FunctionInfo(std::move(Info))) {}
569 
571 
572 void StackSafetyInfo::print(raw_ostream &O) const { Info->print(O); }
573 
574 AnalysisKey StackSafetyAnalysis::Key;
575 
578  StackSafetyLocalAnalysis SSLA(F, AM.getResult<ScalarEvolutionAnalysis>(F));
579  return SSLA.run();
580 }
581 
584  OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n";
586  return PreservedAnalyses::all();
587 }
588 
590 
593 }
594 
597  AU.setPreservesAll();
598 }
599 
601  SSI.print(O);
602 }
603 
605  StackSafetyLocalAnalysis SSLA(
606  F, getAnalysis<ScalarEvolutionWrapperPass>().getSE());
607  SSI = StackSafetyInfo(SSLA.run());
608  return false;
609 }
610 
611 AnalysisKey StackSafetyGlobalAnalysis::Key;
612 
616  AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
617 
618  StackSafetyDataFlowAnalysis SSDFA(
619  M, [&FAM](Function &F) -> const StackSafetyInfo & {
620  return FAM.getResult<StackSafetyAnalysis>(F);
621  });
622  return SSDFA.run();
623 }
624 
626  ModuleAnalysisManager &AM) {
627  OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n";
629  return PreservedAnalyses::all();
630 }
631 
633 
635  : ModulePass(ID) {
638 }
639 
641  const Module *M) const {
642  ::print(SSI, O, *M);
643 }
644 
646  AnalysisUsage &AU) const {
648 }
649 
651  StackSafetyDataFlowAnalysis SSDFA(
652  M, [this](Function &F) -> const StackSafetyInfo & {
653  return getAnalysis<StackSafetyInfoWrapperPass>(F).getResult();
654  });
655  SSI = SSDFA.run();
656  return false;
657 }
658 
659 static const char LocalPassArg[] = "stack-safety-local";
660 static const char LocalPassName[] = "Stack Safety Local Analysis";
661 INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
662  false, true)
664 INITIALIZE_PASS_END(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
665  false, true)
666 
667 static const char GlobalPassName[] = "Stack Safety Analysis";
669  GlobalPassName, false, false)
670 INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)
671 INITIALIZE_PASS_END(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
672  GlobalPassName, false, false)
IterTy arg_end() const
Definition: CallSite.h:583
uint64_t CallInst * C
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
Result run(Module &M, ModuleAnalysisManager &AM)
const GlobalObject * getBaseObject() const
iterator_range< use_iterator > uses()
Definition: Value.h:354
FunctionInfo(const StackSafetyInfo &SSI)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
ConstantRange unionWith(const ConstantRange &CR) const
Return the range that results from the union of this range with another range.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
IterTy arg_begin() const
Definition: CallSite.h:579
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
void print(raw_ostream &O, const Module *M) const override
print - Print out the internal state of the pass.
The main scalar evolution driver.
bool isInterposable() const
Return true if this global&#39;s definition can be substituted with an arbitrary definition at link time...
Definition: GlobalValue.h:419
unsigned getPointerSizeInBits(unsigned AS=0) const
Layout pointer size, in bits FIXME: The defaults need to be removed once all of the backends/clients ...
Definition: DataLayout.h:362
StringRef getName() const
Get a short "name" for the module.
Definition: Module.h:226
F(f)
block Block Frequency true
Value * getLength() const
const SCEV * visit(const SCEV *S)
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Definition: BitVector.h:937
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
bool isDSOLocal() const
Definition: GlobalValue.h:279
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
ValTy * getCalledValue() const
Return the pointer to function that is being called.
Definition: CallSite.h:104
static StringRef getName(Value *V)
void print(raw_ostream &O, const Module *M) const override
print - Print out the internal state of the pass.
ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static const char LocalPassArg[]
Class to represent function types.
Definition: DerivedTypes.h:102
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
Describes uses of allocas and parameters inside of a single function.
INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName, false, true) INITIALIZE_PASS_END(StackSafetyInfoWrapperPass
This pass performs the global (interprocedural) stack safety analysis (legacy pass manager)...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
The operation itself must be expressed in terms of simpler actions on this target.
Definition: LegalizerInfo.h:72
Analysis containing CSE Info
Definition: CSEInfo.cpp:20
const StackSafetyGlobalInfo & getResult() const
StackSafetyInfo wrapper for the new pass manager.
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on...
#define P(N)
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:422
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
iterator_range< iterator > functions()
Definition: Module.h:608
StackSafetyInfo run(Function &F, FunctionAnalysisManager &AM)
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Interface to access stack safety analysis results for single function.
unsigned getNumParams() const
Return the number of fixed parameters this function type requires.
Definition: DerivedTypes.h:138
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:370
Represent the analysis usage information of a pass.
Select target instructions out of generic instructions
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
iterator erase(const_iterator CI)
Definition: SmallVector.h:437
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
This pass performs the global (interprocedural) stack safety analysis (new pass manager).
const Value * getArraySize() const
Get the number of elements allocated.
Definition: Instructions.h:92
size_t size() const
Definition: SmallVector.h:52
StackSafetyInfo wrapper for the legacy pass manager.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
Definition: Instructions.h:105
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
static cl::opt< int > StackSafetyMaxIterations("stack-safety-max-iterations", cl::init(20), cl::Hidden)
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1115
bool isEmptySet() const
Return true if this set contains no members.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
#define DEBUG_TYPE
This is the common base class for memset/memcpy/memmove.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
static const char LocalPassName[]
void print(raw_ostream &O) const
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:839
std::map< const GlobalValue *, StackSafetyInfo > StackSafetyGlobalInfo
This class represents a range of values.
Definition: ConstantRange.h:46
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:373
static true const char GlobalPassName[]
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:55
Class for arbitrary precision integers.
Definition: APInt.h:69
amdgpu Simplify well known AMD library false FunctionCallee Callee
void setPreservesAll()
Set by analyses that do not transform their input at all.
Analysis pass that exposes the ScalarEvolution for a function.
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::ZeroOrMore, cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate IT block based on arch"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow deprecated IT based on ARMv8"), clEnumValN(NoRestrictedIT, "arm-no-restrict-it", "Allow IT blocks based on ARMv7")))
uint64_t getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:435
Virtual Register Rewriter
Definition: VirtRegMap.cpp:221
block Block Frequency Analysis
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:644
This class represents an analyzed expression in the program.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
const Value * stripPointerCastsNoFollowAliases() const
Strip off pointer casts and all-zero GEPs.
Definition: Value.cpp:533
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
Establish a view to a call site for examination.
Definition: CallSite.h:892
#define I(x, y, z)
Definition: MD5.cpp:58
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
void initializeStackSafetyGlobalInfoWrapperPassPass(PassRegistry &)
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:322
Type * getValueType() const
Definition: GlobalValue.h:275
uint32_t Size
Definition: Profile.cpp:46
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2038
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool isArrayAllocation() const
Return true if there is an allocation size parameter to the allocation instruction that is not 1...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void initializeStackSafetyInfoWrapperPassPass(PassRegistry &)
aarch64 promote const
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
LLVM Value Representation.
Definition: Value.h:72
uint64_t getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type...
Definition: DataLayout.h:418
A vector that has set insertion semantics.
Definition: SetVector.h:40
SmallVector< AllocaInfo, 4 > Allocas
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
print Print MemDeps of function
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
A container for analyses that lazily runs them and caches their results.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
Value * getRawDest() const
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
This visitor recursively visits a SCEV expression and re-writes it.
an instruction to allocate memory on the stack
Definition: Instructions.h:59
iterator_range< alias_iterator > aliases()
Definition: Module.h:626
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:1037