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