LLVM  10.0.0svn
GlobalsModRef.cpp
Go to the documentation of this file.
1 //===- GlobalsModRef.cpp - Simple Mod/Ref Analysis for Globals ------------===//
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 // This simple pass provides alias and mod/ref information for global values
10 // that do not have their address taken, and keeps track of whether functions
11 // read or write memory (are "pure"). For this simple (but very common) case,
12 // we can provide pretty accurate and useful information.
13 //
14 //===----------------------------------------------------------------------===//
15 
17 #include "llvm/ADT/SCCIterator.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/Statistic.h"
23 #include "llvm/IR/DerivedTypes.h"
24 #include "llvm/IR/InstIterator.h"
25 #include "llvm/IR/Instructions.h"
26 #include "llvm/IR/IntrinsicInst.h"
27 #include "llvm/IR/Module.h"
28 #include "llvm/Pass.h"
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "globalsmodref-aa"
33 
34 STATISTIC(NumNonAddrTakenGlobalVars,
35  "Number of global vars without address taken");
36 STATISTIC(NumNonAddrTakenFunctions,"Number of functions without address taken");
37 STATISTIC(NumNoMemFunctions, "Number of functions that do not access memory");
38 STATISTIC(NumReadMemFunctions, "Number of functions that only read memory");
39 STATISTIC(NumIndirectGlobalVars, "Number of indirect global objects");
40 
41 // An option to enable unsafe alias results from the GlobalsModRef analysis.
42 // When enabled, GlobalsModRef will provide no-alias results which in extremely
43 // rare cases may not be conservatively correct. In particular, in the face of
44 // transforms which cause assymetry between how effective GetUnderlyingObject
45 // is for two pointers, it may produce incorrect results.
46 //
47 // These unsafe results have been returned by GMR for many years without
48 // causing significant issues in the wild and so we provide a mechanism to
49 // re-enable them for users of LLVM that have a particular performance
50 // sensitivity and no known issues. The option also makes it easy to evaluate
51 // the performance impact of these results.
53  "enable-unsafe-globalsmodref-alias-results", cl::init(false), cl::Hidden);
54 
55 /// The mod/ref information collected for a particular function.
56 ///
57 /// We collect information about mod/ref behavior of a function here, both in
58 /// general and as pertains to specific globals. We only have this detailed
59 /// information when we know *something* useful about the behavior. If we
60 /// saturate to fully general mod/ref, we remove the info for the function.
63 
64  /// Build a wrapper struct that has 8-byte alignment. All heap allocations
65  /// should provide this much alignment at least, but this makes it clear we
66  /// specifically rely on this amount of alignment.
67  struct alignas(8) AlignedMap {
68  AlignedMap() {}
69  AlignedMap(const AlignedMap &Arg) : Map(Arg.Map) {}
70  GlobalInfoMapType Map;
71  };
72 
73  /// Pointer traits for our aligned map.
74  struct AlignedMapPointerTraits {
75  static inline void *getAsVoidPointer(AlignedMap *P) { return P; }
76  static inline AlignedMap *getFromVoidPointer(void *P) {
77  return (AlignedMap *)P;
78  }
79  enum { NumLowBitsAvailable = 3 };
80  static_assert(alignof(AlignedMap) >= (1 << NumLowBitsAvailable),
81  "AlignedMap insufficiently aligned to have enough low bits.");
82  };
83 
84  /// The bit that flags that this function may read any global. This is
85  /// chosen to mix together with ModRefInfo bits.
86  /// FIXME: This assumes ModRefInfo lattice will remain 4 bits!
87  /// It overlaps with ModRefInfo::Must bit!
88  /// FunctionInfo.getModRefInfo() masks out everything except ModRef so
89  /// this remains correct, but the Must info is lost.
90  enum { MayReadAnyGlobal = 4 };
91 
92  /// Checks to document the invariants of the bit packing here.
93  static_assert((MayReadAnyGlobal & static_cast<int>(ModRefInfo::MustModRef)) ==
94  0,
95  "ModRef and the MayReadAnyGlobal flag bits overlap.");
96  static_assert(((MayReadAnyGlobal |
97  static_cast<int>(ModRefInfo::MustModRef)) >>
98  AlignedMapPointerTraits::NumLowBitsAvailable) == 0,
99  "Insufficient low bits to store our flag and ModRef info.");
100 
101 public:
104  delete Info.getPointer();
105  }
106  // Spell out the copy ond move constructors and assignment operators to get
107  // deep copy semantics and correct move semantics in the face of the
108  // pointer-int pair.
110  : Info(nullptr, Arg.Info.getInt()) {
111  if (const auto *ArgPtr = Arg.Info.getPointer())
112  Info.setPointer(new AlignedMap(*ArgPtr));
113  }
115  : Info(Arg.Info.getPointer(), Arg.Info.getInt()) {
116  Arg.Info.setPointerAndInt(nullptr, 0);
117  }
119  delete Info.getPointer();
120  Info.setPointerAndInt(nullptr, RHS.Info.getInt());
121  if (const auto *RHSPtr = RHS.Info.getPointer())
122  Info.setPointer(new AlignedMap(*RHSPtr));
123  return *this;
124  }
126  delete Info.getPointer();
127  Info.setPointerAndInt(RHS.Info.getPointer(), RHS.Info.getInt());
128  RHS.Info.setPointerAndInt(nullptr, 0);
129  return *this;
130  }
131 
132  /// This method clears MayReadAnyGlobal bit added by GlobalsAAResult to return
133  /// the corresponding ModRefInfo. It must align in functionality with
134  /// clearMust().
136  return ModRefInfo((I & static_cast<int>(ModRefInfo::ModRef)) |
137  static_cast<int>(ModRefInfo::NoModRef));
138  }
139 
140  /// Returns the \c ModRefInfo info for this function.
142  return globalClearMayReadAnyGlobal(Info.getInt());
143  }
144 
145  /// Adds new \c ModRefInfo for this function to its state.
146  void addModRefInfo(ModRefInfo NewMRI) {
147  Info.setInt(Info.getInt() | static_cast<int>(setMust(NewMRI)));
148  }
149 
150  /// Returns whether this function may read any global variable, and we don't
151  /// know which global.
152  bool mayReadAnyGlobal() const { return Info.getInt() & MayReadAnyGlobal; }
153 
154  /// Sets this function as potentially reading from any global.
155  void setMayReadAnyGlobal() { Info.setInt(Info.getInt() | MayReadAnyGlobal); }
156 
157  /// Returns the \c ModRefInfo info for this function w.r.t. a particular
158  /// global, which may be more precise than the general information above.
160  ModRefInfo GlobalMRI =
162  if (AlignedMap *P = Info.getPointer()) {
163  auto I = P->Map.find(&GV);
164  if (I != P->Map.end())
165  GlobalMRI = unionModRef(GlobalMRI, I->second);
166  }
167  return GlobalMRI;
168  }
169 
170  /// Add mod/ref info from another function into ours, saturating towards
171  /// ModRef.
172  void addFunctionInfo(const FunctionInfo &FI) {
174 
175  if (FI.mayReadAnyGlobal())
177 
178  if (AlignedMap *P = FI.Info.getPointer())
179  for (const auto &G : P->Map)
180  addModRefInfoForGlobal(*G.first, G.second);
181  }
182 
184  AlignedMap *P = Info.getPointer();
185  if (!P) {
186  P = new AlignedMap();
187  Info.setPointer(P);
188  }
189  auto &GlobalMRI = P->Map[&GV];
190  GlobalMRI = unionModRef(GlobalMRI, NewMRI);
191  }
192 
193  /// Clear a global's ModRef info. Should be used when a global is being
194  /// deleted.
196  if (AlignedMap *P = Info.getPointer())
197  P->Map.erase(&GV);
198  }
199 
200 private:
201  /// All of the information is encoded into a single pointer, with a three bit
202  /// integer in the low three bits. The high bit provides a flag for when this
203  /// function may read any global. The low two bits are the ModRefInfo. And
204  /// the pointer, when non-null, points to a map from GlobalValue to
205  /// ModRefInfo specific to that GlobalValue.
207 };
208 
209 void GlobalsAAResult::DeletionCallbackHandle::deleted() {
210  Value *V = getValPtr();
211  if (auto *F = dyn_cast<Function>(V))
212  GAR->FunctionInfos.erase(F);
213 
214  if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
215  if (GAR->NonAddressTakenGlobals.erase(GV)) {
216  // This global might be an indirect global. If so, remove it and
217  // remove any AllocRelatedValues for it.
218  if (GAR->IndirectGlobals.erase(GV)) {
219  // Remove any entries in AllocsForIndirectGlobals for this global.
220  for (auto I = GAR->AllocsForIndirectGlobals.begin(),
221  E = GAR->AllocsForIndirectGlobals.end();
222  I != E; ++I)
223  if (I->second == GV)
224  GAR->AllocsForIndirectGlobals.erase(I);
225  }
226 
227  // Scan the function info we have collected and remove this global
228  // from all of them.
229  for (auto &FIPair : GAR->FunctionInfos)
230  FIPair.second.eraseModRefInfoForGlobal(*GV);
231  }
232  }
233 
234  // If this is an allocation related to an indirect global, remove it.
235  GAR->AllocsForIndirectGlobals.erase(V);
236 
237  // And clear out the handle.
238  setValPtr(nullptr);
239  GAR->Handles.erase(I);
240  // This object is now destroyed!
241 }
242 
245 
246  if (FunctionInfo *FI = getFunctionInfo(F)) {
247  if (!isModOrRefSet(FI->getModRefInfo()))
249  else if (!isModSet(FI->getModRefInfo()))
250  Min = FMRB_OnlyReadsMemory;
251  }
252 
254 }
255 
259 
260  if (!Call->hasOperandBundles())
261  if (const Function *F = Call->getCalledFunction())
262  if (FunctionInfo *FI = getFunctionInfo(F)) {
263  if (!isModOrRefSet(FI->getModRefInfo()))
265  else if (!isModSet(FI->getModRefInfo()))
266  Min = FMRB_OnlyReadsMemory;
267  }
268 
270 }
271 
272 /// Returns the function info for the function, or null if we don't have
273 /// anything useful to say about it.
275 GlobalsAAResult::getFunctionInfo(const Function *F) {
276  auto I = FunctionInfos.find(F);
277  if (I != FunctionInfos.end())
278  return &I->second;
279  return nullptr;
280 }
281 
282 /// AnalyzeGlobals - Scan through the users of all of the internal
283 /// GlobalValue's in the program. If none of them have their "address taken"
284 /// (really, their address passed to something nontrivial), record this fact,
285 /// and record the functions that they are used directly in.
286 void GlobalsAAResult::AnalyzeGlobals(Module &M) {
287  SmallPtrSet<Function *, 32> TrackedFunctions;
288  for (Function &F : M)
289  if (F.hasLocalLinkage())
290  if (!AnalyzeUsesOfPointer(&F)) {
291  // Remember that we are tracking this global.
292  NonAddressTakenGlobals.insert(&F);
293  TrackedFunctions.insert(&F);
294  Handles.emplace_front(*this, &F);
295  Handles.front().I = Handles.begin();
296  ++NumNonAddrTakenFunctions;
297  }
298 
299  SmallPtrSet<Function *, 16> Readers, Writers;
300  for (GlobalVariable &GV : M.globals())
301  if (GV.hasLocalLinkage()) {
302  if (!AnalyzeUsesOfPointer(&GV, &Readers,
303  GV.isConstant() ? nullptr : &Writers)) {
304  // Remember that we are tracking this global, and the mod/ref fns
305  NonAddressTakenGlobals.insert(&GV);
306  Handles.emplace_front(*this, &GV);
307  Handles.front().I = Handles.begin();
308 
309  for (Function *Reader : Readers) {
310  if (TrackedFunctions.insert(Reader).second) {
311  Handles.emplace_front(*this, Reader);
312  Handles.front().I = Handles.begin();
313  }
314  FunctionInfos[Reader].addModRefInfoForGlobal(GV, ModRefInfo::Ref);
315  }
316 
317  if (!GV.isConstant()) // No need to keep track of writers to constants
318  for (Function *Writer : Writers) {
319  if (TrackedFunctions.insert(Writer).second) {
320  Handles.emplace_front(*this, Writer);
321  Handles.front().I = Handles.begin();
322  }
323  FunctionInfos[Writer].addModRefInfoForGlobal(GV, ModRefInfo::Mod);
324  }
325  ++NumNonAddrTakenGlobalVars;
326 
327  // If this global holds a pointer type, see if it is an indirect global.
328  if (GV.getValueType()->isPointerTy() &&
329  AnalyzeIndirectGlobalMemory(&GV))
330  ++NumIndirectGlobalVars;
331  }
332  Readers.clear();
333  Writers.clear();
334  }
335 }
336 
337 /// AnalyzeUsesOfPointer - Look at all of the users of the specified pointer.
338 /// If this is used by anything complex (i.e., the address escapes), return
339 /// true. Also, while we are at it, keep track of those functions that read and
340 /// write to the value.
341 ///
342 /// If OkayStoreDest is non-null, stores into this global are allowed.
343 bool GlobalsAAResult::AnalyzeUsesOfPointer(Value *V,
346  GlobalValue *OkayStoreDest) {
347  if (!V->getType()->isPointerTy())
348  return true;
349 
350  for (Use &U : V->uses()) {
351  User *I = U.getUser();
352  if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
353  if (Readers)
354  Readers->insert(LI->getParent()->getParent());
355  } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
356  if (V == SI->getOperand(1)) {
357  if (Writers)
358  Writers->insert(SI->getParent()->getParent());
359  } else if (SI->getOperand(1) != OkayStoreDest) {
360  return true; // Storing the pointer
361  }
362  } else if (Operator::getOpcode(I) == Instruction::GetElementPtr) {
363  if (AnalyzeUsesOfPointer(I, Readers, Writers))
364  return true;
365  } else if (Operator::getOpcode(I) == Instruction::BitCast) {
366  if (AnalyzeUsesOfPointer(I, Readers, Writers, OkayStoreDest))
367  return true;
368  } else if (auto *Call = dyn_cast<CallBase>(I)) {
369  // Make sure that this is just the function being called, not that it is
370  // passing into the function.
371  if (Call->isDataOperand(&U)) {
372  // Detect calls to free.
373  if (Call->isArgOperand(&U) && isFreeCall(I, &TLI)) {
374  if (Writers)
375  Writers->insert(Call->getParent()->getParent());
376  } else {
377  return true; // Argument of an unknown call.
378  }
379  }
380  } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
381  if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
382  return true; // Allow comparison against null.
383  } else if (Constant *C = dyn_cast<Constant>(I)) {
384  // Ignore constants which don't have any live uses.
385  if (isa<GlobalValue>(C) || C->isConstantUsed())
386  return true;
387  } else {
388  return true;
389  }
390  }
391 
392  return false;
393 }
394 
395 /// AnalyzeIndirectGlobalMemory - We found an non-address-taken global variable
396 /// which holds a pointer type. See if the global always points to non-aliased
397 /// heap memory: that is, all initializers of the globals are allocations, and
398 /// those allocations have no use other than initialization of the global.
399 /// Further, all loads out of GV must directly use the memory, not store the
400 /// pointer somewhere. If this is true, we consider the memory pointed to by
401 /// GV to be owned by GV and can disambiguate other pointers from it.
402 bool GlobalsAAResult::AnalyzeIndirectGlobalMemory(GlobalVariable *GV) {
403  // Keep track of values related to the allocation of the memory, f.e. the
404  // value produced by the malloc call and any casts.
405  std::vector<Value *> AllocRelatedValues;
406 
407  // If the initializer is a valid pointer, bail.
408  if (Constant *C = GV->getInitializer())
409  if (!C->isNullValue())
410  return false;
411 
412  // Walk the user list of the global. If we find anything other than a direct
413  // load or store, bail out.
414  for (User *U : GV->users()) {
415  if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
416  // The pointer loaded from the global can only be used in simple ways:
417  // we allow addressing of it and loading storing to it. We do *not* allow
418  // storing the loaded pointer somewhere else or passing to a function.
419  if (AnalyzeUsesOfPointer(LI))
420  return false; // Loaded pointer escapes.
421  // TODO: Could try some IP mod/ref of the loaded pointer.
422  } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
423  // Storing the global itself.
424  if (SI->getOperand(0) == GV)
425  return false;
426 
427  // If storing the null pointer, ignore it.
428  if (isa<ConstantPointerNull>(SI->getOperand(0)))
429  continue;
430 
431  // Check the value being stored.
432  Value *Ptr = GetUnderlyingObject(SI->getOperand(0),
433  GV->getParent()->getDataLayout());
434 
435  if (!isAllocLikeFn(Ptr, &TLI))
436  return false; // Too hard to analyze.
437 
438  // Analyze all uses of the allocation. If any of them are used in a
439  // non-simple way (e.g. stored to another global) bail out.
440  if (AnalyzeUsesOfPointer(Ptr, /*Readers*/ nullptr, /*Writers*/ nullptr,
441  GV))
442  return false; // Loaded pointer escapes.
443 
444  // Remember that this allocation is related to the indirect global.
445  AllocRelatedValues.push_back(Ptr);
446  } else {
447  // Something complex, bail out.
448  return false;
449  }
450  }
451 
452  // Okay, this is an indirect global. Remember all of the allocations for
453  // this global in AllocsForIndirectGlobals.
454  while (!AllocRelatedValues.empty()) {
455  AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV;
456  Handles.emplace_front(*this, AllocRelatedValues.back());
457  Handles.front().I = Handles.begin();
458  AllocRelatedValues.pop_back();
459  }
460  IndirectGlobals.insert(GV);
461  Handles.emplace_front(*this, GV);
462  Handles.front().I = Handles.begin();
463  return true;
464 }
465 
466 void GlobalsAAResult::CollectSCCMembership(CallGraph &CG) {
467  // We do a bottom-up SCC traversal of the call graph. In other words, we
468  // visit all callees before callers (leaf-first).
469  unsigned SCCID = 0;
470  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
471  const std::vector<CallGraphNode *> &SCC = *I;
472  assert(!SCC.empty() && "SCC with no functions?");
473 
474  for (auto *CGN : SCC)
475  if (Function *F = CGN->getFunction())
476  FunctionToSCCMap[F] = SCCID;
477  ++SCCID;
478  }
479 }
480 
481 /// AnalyzeCallGraph - At this point, we know the functions where globals are
482 /// immediately stored to and read from. Propagate this information up the call
483 /// graph to all callers and compute the mod/ref info for all memory for each
484 /// function.
485 void GlobalsAAResult::AnalyzeCallGraph(CallGraph &CG, Module &M) {
486  // We do a bottom-up SCC traversal of the call graph. In other words, we
487  // visit all callees before callers (leaf-first).
488  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
489  const std::vector<CallGraphNode *> &SCC = *I;
490  assert(!SCC.empty() && "SCC with no functions?");
491 
492  Function *F = SCC[0]->getFunction();
493 
494  if (!F || !F->isDefinitionExact()) {
495  // Calls externally or not exact - can't say anything useful. Remove any
496  // existing function records (may have been created when scanning
497  // globals).
498  for (auto *Node : SCC)
499  FunctionInfos.erase(Node->getFunction());
500  continue;
501  }
502 
503  FunctionInfo &FI = FunctionInfos[F];
504  Handles.emplace_front(*this, F);
505  Handles.front().I = Handles.begin();
506  bool KnowNothing = false;
507 
508  // Collect the mod/ref properties due to called functions. We only compute
509  // one mod-ref set.
510  for (unsigned i = 0, e = SCC.size(); i != e && !KnowNothing; ++i) {
511  if (!F) {
512  KnowNothing = true;
513  break;
514  }
515 
516  if (F->isDeclaration() || F->hasOptNone()) {
517  // Try to get mod/ref behaviour from function attributes.
518  if (F->doesNotAccessMemory()) {
519  // Can't do better than that!
520  } else if (F->onlyReadsMemory()) {
522  if (!F->isIntrinsic() && !F->onlyAccessesArgMemory())
523  // This function might call back into the module and read a global -
524  // consider every global as possibly being read by this function.
525  FI.setMayReadAnyGlobal();
526  } else {
528  // Can't say anything useful unless it's an intrinsic - they don't
529  // read or write global variables of the kind considered here.
530  KnowNothing = !F->isIntrinsic();
531  }
532  continue;
533  }
534 
535  for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end();
536  CI != E && !KnowNothing; ++CI)
537  if (Function *Callee = CI->second->getFunction()) {
538  if (FunctionInfo *CalleeFI = getFunctionInfo(Callee)) {
539  // Propagate function effect up.
540  FI.addFunctionInfo(*CalleeFI);
541  } else {
542  // Can't say anything about it. However, if it is inside our SCC,
543  // then nothing needs to be done.
544  CallGraphNode *CalleeNode = CG[Callee];
545  if (!is_contained(SCC, CalleeNode))
546  KnowNothing = true;
547  }
548  } else {
549  KnowNothing = true;
550  }
551  }
552 
553  // If we can't say anything useful about this SCC, remove all SCC functions
554  // from the FunctionInfos map.
555  if (KnowNothing) {
556  for (auto *Node : SCC)
557  FunctionInfos.erase(Node->getFunction());
558  continue;
559  }
560 
561  // Scan the function bodies for explicit loads or stores.
562  for (auto *Node : SCC) {
563  if (isModAndRefSet(FI.getModRefInfo()))
564  break; // The mod/ref lattice saturates here.
565 
566  // Don't prove any properties based on the implementation of an optnone
567  // function. Function attributes were already used as a best approximation
568  // above.
569  if (Node->getFunction()->hasOptNone())
570  continue;
571 
572  for (Instruction &I : instructions(Node->getFunction())) {
573  if (isModAndRefSet(FI.getModRefInfo()))
574  break; // The mod/ref lattice saturates here.
575 
576  // We handle calls specially because the graph-relevant aspects are
577  // handled above.
578  if (auto *Call = dyn_cast<CallBase>(&I)) {
579  if (isAllocationFn(Call, &TLI) || isFreeCall(Call, &TLI)) {
580  // FIXME: It is completely unclear why this is necessary and not
581  // handled by the above graph code.
583  } else if (Function *Callee = Call->getCalledFunction()) {
584  // The callgraph doesn't include intrinsic calls.
585  if (Callee->isIntrinsic()) {
586  if (isa<DbgInfoIntrinsic>(Call))
587  // Don't let dbg intrinsics affect alias info.
588  continue;
589 
590  FunctionModRefBehavior Behaviour =
592  FI.addModRefInfo(createModRefInfo(Behaviour));
593  }
594  }
595  continue;
596  }
597 
598  // All non-call instructions we use the primary predicates for whether
599  // they read or write memory.
600  if (I.mayReadFromMemory())
602  if (I.mayWriteToMemory())
604  }
605  }
606 
607  if (!isModSet(FI.getModRefInfo()))
608  ++NumReadMemFunctions;
609  if (!isModOrRefSet(FI.getModRefInfo()))
610  ++NumNoMemFunctions;
611 
612  // Finally, now that we know the full effect on this SCC, clone the
613  // information to each function in the SCC.
614  // FI is a reference into FunctionInfos, so copy it now so that it doesn't
615  // get invalidated if DenseMap decides to re-hash.
616  FunctionInfo CachedFI = FI;
617  for (unsigned i = 1, e = SCC.size(); i != e; ++i)
618  FunctionInfos[SCC[i]->getFunction()] = CachedFI;
619  }
620 }
621 
622 // GV is a non-escaping global. V is a pointer address that has been loaded from.
623 // If we can prove that V must escape, we can conclude that a load from V cannot
624 // alias GV.
626  const Value *V,
627  int &Depth,
628  const DataLayout &DL) {
631  Visited.insert(V);
632  Inputs.push_back(V);
633  do {
634  const Value *Input = Inputs.pop_back_val();
635 
636  if (isa<GlobalValue>(Input) || isa<Argument>(Input) || isa<CallInst>(Input) ||
637  isa<InvokeInst>(Input))
638  // Arguments to functions or returns from functions are inherently
639  // escaping, so we can immediately classify those as not aliasing any
640  // non-addr-taken globals.
641  //
642  // (Transitive) loads from a global are also safe - if this aliased
643  // another global, its address would escape, so no alias.
644  continue;
645 
646  // Recurse through a limited number of selects, loads and PHIs. This is an
647  // arbitrary depth of 4, lower numbers could be used to fix compile time
648  // issues if needed, but this is generally expected to be only be important
649  // for small depths.
650  if (++Depth > 4)
651  return false;
652 
653  if (auto *LI = dyn_cast<LoadInst>(Input)) {
654  Inputs.push_back(GetUnderlyingObject(LI->getPointerOperand(), DL));
655  continue;
656  }
657  if (auto *SI = dyn_cast<SelectInst>(Input)) {
658  const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), DL);
659  const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), DL);
660  if (Visited.insert(LHS).second)
661  Inputs.push_back(LHS);
662  if (Visited.insert(RHS).second)
663  Inputs.push_back(RHS);
664  continue;
665  }
666  if (auto *PN = dyn_cast<PHINode>(Input)) {
667  for (const Value *Op : PN->incoming_values()) {
668  Op = GetUnderlyingObject(Op, DL);
669  if (Visited.insert(Op).second)
670  Inputs.push_back(Op);
671  }
672  continue;
673  }
674 
675  return false;
676  } while (!Inputs.empty());
677 
678  // All inputs were known to be no-alias.
679  return true;
680 }
681 
682 // There are particular cases where we can conclude no-alias between
683 // a non-addr-taken global and some other underlying object. Specifically,
684 // a non-addr-taken global is known to not be escaped from any function. It is
685 // also incorrect for a transformation to introduce an escape of a global in
686 // a way that is observable when it was not there previously. One function
687 // being transformed to introduce an escape which could possibly be observed
688 // (via loading from a global or the return value for example) within another
689 // function is never safe. If the observation is made through non-atomic
690 // operations on different threads, it is a data-race and UB. If the
691 // observation is well defined, by being observed the transformation would have
692 // changed program behavior by introducing the observed escape, making it an
693 // invalid transform.
694 //
695 // This property does require that transformations which *temporarily* escape
696 // a global that was not previously escaped, prior to restoring it, cannot rely
697 // on the results of GMR::alias. This seems a reasonable restriction, although
698 // currently there is no way to enforce it. There is also no realistic
699 // optimization pass that would make this mistake. The closest example is
700 // a transformation pass which does reg2mem of SSA values but stores them into
701 // global variables temporarily before restoring the global variable's value.
702 // This could be useful to expose "benign" races for example. However, it seems
703 // reasonable to require that a pass which introduces escapes of global
704 // variables in this way to either not trust AA results while the escape is
705 // active, or to be forced to operate as a module pass that cannot co-exist
706 // with an alias analysis such as GMR.
707 bool GlobalsAAResult::isNonEscapingGlobalNoAlias(const GlobalValue *GV,
708  const Value *V) {
709  // In order to know that the underlying object cannot alias the
710  // non-addr-taken global, we must know that it would have to be an escape.
711  // Thus if the underlying object is a function argument, a load from
712  // a global, or the return of a function, it cannot alias. We can also
713  // recurse through PHI nodes and select nodes provided all of their inputs
714  // resolve to one of these known-escaping roots.
717  Visited.insert(V);
718  Inputs.push_back(V);
719  int Depth = 0;
720  do {
721  const Value *Input = Inputs.pop_back_val();
722 
723  if (auto *InputGV = dyn_cast<GlobalValue>(Input)) {
724  // If one input is the very global we're querying against, then we can't
725  // conclude no-alias.
726  if (InputGV == GV)
727  return false;
728 
729  // Distinct GlobalVariables never alias, unless overriden or zero-sized.
730  // FIXME: The condition can be refined, but be conservative for now.
731  auto *GVar = dyn_cast<GlobalVariable>(GV);
732  auto *InputGVar = dyn_cast<GlobalVariable>(InputGV);
733  if (GVar && InputGVar &&
734  !GVar->isDeclaration() && !InputGVar->isDeclaration() &&
735  !GVar->isInterposable() && !InputGVar->isInterposable()) {
736  Type *GVType = GVar->getInitializer()->getType();
737  Type *InputGVType = InputGVar->getInitializer()->getType();
738  if (GVType->isSized() && InputGVType->isSized() &&
739  (DL.getTypeAllocSize(GVType) > 0) &&
740  (DL.getTypeAllocSize(InputGVType) > 0))
741  continue;
742  }
743 
744  // Conservatively return false, even though we could be smarter
745  // (e.g. look through GlobalAliases).
746  return false;
747  }
748 
749  if (isa<Argument>(Input) || isa<CallInst>(Input) ||
750  isa<InvokeInst>(Input)) {
751  // Arguments to functions or returns from functions are inherently
752  // escaping, so we can immediately classify those as not aliasing any
753  // non-addr-taken globals.
754  continue;
755  }
756 
757  // Recurse through a limited number of selects, loads and PHIs. This is an
758  // arbitrary depth of 4, lower numbers could be used to fix compile time
759  // issues if needed, but this is generally expected to be only be important
760  // for small depths.
761  if (++Depth > 4)
762  return false;
763 
764  if (auto *LI = dyn_cast<LoadInst>(Input)) {
765  // A pointer loaded from a global would have been captured, and we know
766  // that the global is non-escaping, so no alias.
767  const Value *Ptr = GetUnderlyingObject(LI->getPointerOperand(), DL);
768  if (isNonEscapingGlobalNoAliasWithLoad(GV, Ptr, Depth, DL))
769  // The load does not alias with GV.
770  continue;
771  // Otherwise, a load could come from anywhere, so bail.
772  return false;
773  }
774  if (auto *SI = dyn_cast<SelectInst>(Input)) {
775  const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), DL);
776  const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), DL);
777  if (Visited.insert(LHS).second)
778  Inputs.push_back(LHS);
779  if (Visited.insert(RHS).second)
780  Inputs.push_back(RHS);
781  continue;
782  }
783  if (auto *PN = dyn_cast<PHINode>(Input)) {
784  for (const Value *Op : PN->incoming_values()) {
785  Op = GetUnderlyingObject(Op, DL);
786  if (Visited.insert(Op).second)
787  Inputs.push_back(Op);
788  }
789  continue;
790  }
791 
792  // FIXME: It would be good to handle other obvious no-alias cases here, but
793  // it isn't clear how to do so reasonably without building a small version
794  // of BasicAA into this code. We could recurse into AAResultBase::alias
795  // here but that seems likely to go poorly as we're inside the
796  // implementation of such a query. Until then, just conservatively return
797  // false.
798  return false;
799  } while (!Inputs.empty());
800 
801  // If all the inputs to V were definitively no-alias, then V is no-alias.
802  return true;
803 }
804 
805 /// alias - If one of the pointers is to a global that we are tracking, and the
806 /// other is some random pointer, we know there cannot be an alias, because the
807 /// address of the global isn't taken.
809  const MemoryLocation &LocB,
810  AAQueryInfo &AAQI) {
811  // Get the base object these pointers point to.
812  const Value *UV1 = GetUnderlyingObject(LocA.Ptr, DL);
813  const Value *UV2 = GetUnderlyingObject(LocB.Ptr, DL);
814 
815  // If either of the underlying values is a global, they may be non-addr-taken
816  // globals, which we can answer queries about.
817  const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
818  const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
819  if (GV1 || GV2) {
820  // If the global's address is taken, pretend we don't know it's a pointer to
821  // the global.
822  if (GV1 && !NonAddressTakenGlobals.count(GV1))
823  GV1 = nullptr;
824  if (GV2 && !NonAddressTakenGlobals.count(GV2))
825  GV2 = nullptr;
826 
827  // If the two pointers are derived from two different non-addr-taken
828  // globals we know these can't alias.
829  if (GV1 && GV2 && GV1 != GV2)
830  return NoAlias;
831 
832  // If one is and the other isn't, it isn't strictly safe but we can fake
833  // this result if necessary for performance. This does not appear to be
834  // a common problem in practice.
836  if ((GV1 || GV2) && GV1 != GV2)
837  return NoAlias;
838 
839  // Check for a special case where a non-escaping global can be used to
840  // conclude no-alias.
841  if ((GV1 || GV2) && GV1 != GV2) {
842  const GlobalValue *GV = GV1 ? GV1 : GV2;
843  const Value *UV = GV1 ? UV2 : UV1;
844  if (isNonEscapingGlobalNoAlias(GV, UV))
845  return NoAlias;
846  }
847 
848  // Otherwise if they are both derived from the same addr-taken global, we
849  // can't know the two accesses don't overlap.
850  }
851 
852  // These pointers may be based on the memory owned by an indirect global. If
853  // so, we may be able to handle this. First check to see if the base pointer
854  // is a direct load from an indirect global.
855  GV1 = GV2 = nullptr;
856  if (const LoadInst *LI = dyn_cast<LoadInst>(UV1))
857  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
858  if (IndirectGlobals.count(GV))
859  GV1 = GV;
860  if (const LoadInst *LI = dyn_cast<LoadInst>(UV2))
861  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
862  if (IndirectGlobals.count(GV))
863  GV2 = GV;
864 
865  // These pointers may also be from an allocation for the indirect global. If
866  // so, also handle them.
867  if (!GV1)
868  GV1 = AllocsForIndirectGlobals.lookup(UV1);
869  if (!GV2)
870  GV2 = AllocsForIndirectGlobals.lookup(UV2);
871 
872  // Now that we know whether the two pointers are related to indirect globals,
873  // use this to disambiguate the pointers. If the pointers are based on
874  // different indirect globals they cannot alias.
875  if (GV1 && GV2 && GV1 != GV2)
876  return NoAlias;
877 
878  // If one is based on an indirect global and the other isn't, it isn't
879  // strictly safe but we can fake this result if necessary for performance.
880  // This does not appear to be a common problem in practice.
882  if ((GV1 || GV2) && GV1 != GV2)
883  return NoAlias;
884 
885  return AAResultBase::alias(LocA, LocB, AAQI);
886 }
887 
888 ModRefInfo GlobalsAAResult::getModRefInfoForArgument(const CallBase *Call,
889  const GlobalValue *GV,
890  AAQueryInfo &AAQI) {
891  if (Call->doesNotAccessMemory())
892  return ModRefInfo::NoModRef;
893  ModRefInfo ConservativeResult =
895 
896  // Iterate through all the arguments to the called function. If any argument
897  // is based on GV, return the conservative result.
898  for (auto &A : Call->args()) {
900  GetUnderlyingObjects(A, Objects, DL);
901 
902  // All objects must be identified.
903  if (!all_of(Objects, isIdentifiedObject) &&
904  // Try ::alias to see if all objects are known not to alias GV.
905  !all_of(Objects, [&](const Value *V) {
906  return this->alias(MemoryLocation(V), MemoryLocation(GV), AAQI) ==
907  NoAlias;
908  }))
909  return ConservativeResult;
910 
911  if (is_contained(Objects, GV))
912  return ConservativeResult;
913  }
914 
915  // We identified all objects in the argument list, and none of them were GV.
916  return ModRefInfo::NoModRef;
917 }
918 
920  const MemoryLocation &Loc,
921  AAQueryInfo &AAQI) {
923 
924  // If we are asking for mod/ref info of a direct call with a pointer to a
925  // global we are tracking, return information if we have it.
926  if (const GlobalValue *GV =
927  dyn_cast<GlobalValue>(GetUnderlyingObject(Loc.Ptr, DL)))
928  if (GV->hasLocalLinkage())
929  if (const Function *F = Call->getCalledFunction())
930  if (NonAddressTakenGlobals.count(GV))
931  if (const FunctionInfo *FI = getFunctionInfo(F))
932  Known = unionModRef(FI->getModRefInfoForGlobal(*GV),
933  getModRefInfoForArgument(Call, GV, AAQI));
934 
935  if (!isModOrRefSet(Known))
936  return ModRefInfo::NoModRef; // No need to query other mod/ref analyses
937  return intersectModRef(Known, AAResultBase::getModRefInfo(Call, Loc, AAQI));
938 }
939 
940 GlobalsAAResult::GlobalsAAResult(const DataLayout &DL,
941  const TargetLibraryInfo &TLI)
942  : AAResultBase(), DL(DL), TLI(TLI) {}
943 
944 GlobalsAAResult::GlobalsAAResult(GlobalsAAResult &&Arg)
945  : AAResultBase(std::move(Arg)), DL(Arg.DL), TLI(Arg.TLI),
946  NonAddressTakenGlobals(std::move(Arg.NonAddressTakenGlobals)),
947  IndirectGlobals(std::move(Arg.IndirectGlobals)),
948  AllocsForIndirectGlobals(std::move(Arg.AllocsForIndirectGlobals)),
949  FunctionInfos(std::move(Arg.FunctionInfos)),
950  Handles(std::move(Arg.Handles)) {
951  // Update the parent for each DeletionCallbackHandle.
952  for (auto &H : Handles) {
953  assert(H.GAR == &Arg);
954  H.GAR = this;
955  }
956 }
957 
959 
960 /*static*/ GlobalsAAResult
962  CallGraph &CG) {
963  GlobalsAAResult Result(M.getDataLayout(), TLI);
964 
965  // Discover which functions aren't recursive, to feed into AnalyzeGlobals.
966  Result.CollectSCCMembership(CG);
967 
968  // Find non-addr taken globals.
969  Result.AnalyzeGlobals(M);
970 
971  // Propagate on CG.
972  Result.AnalyzeCallGraph(CG, M);
973 
974  return Result;
975 }
976 
977 AnalysisKey GlobalsAA::Key;
978 
983 }
984 
985 char GlobalsAAWrapperPass::ID = 0;
987  "Globals Alias Analysis", false, true)
991  "Globals Alias Analysis", false, true)
992 
994  return new GlobalsAAWrapperPass();
995 }
996 
999 }
1000 
1003  M, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
1004  getAnalysis<CallGraphWrapperPass>().getCallGraph())));
1005  return false;
1006 }
1007 
1009  Result.reset();
1010  return false;
1011 }
1012 
1014  AU.setPreservesAll();
1017 }
Legacy wrapper pass to provide the GlobalsAAResult object.
The access may reference and may modify the value stored in memory.
const Function & getFunction() const
Definition: Function.h:133
LLVM_NODISCARD ModRefInfo unionModRef(const ModRefInfo MRI1, const ModRefInfo MRI2)
uint64_t CallInst * C
bool hasOperandBundles() const
Return true if this User has any operand bundles.
Definition: InstrTypes.h:1733
bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates or reallocates memory (eith...
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
bool doFinalization(Module &M) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
iterator_range< use_iterator > uses()
Definition: Value.h:374
The access neither references nor modifies the value stored in memory.
bool hasLocalLinkage() const
Definition: GlobalValue.h:445
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool doesNotAccessMemory(unsigned OpNo) const
Definition: InstrTypes.h:1551
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
void addFunctionInfo(const FunctionInfo &FI)
Add mod/ref info from another function into ours, saturating towards ModRef.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
void setMayReadAnyGlobal()
Sets this function as potentially reading from any global.
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
PointerTy getPointer() const
static cl::opt< bool > EnableUnsafeGlobalsModRefAliasResults("enable-unsafe-globalsmodref-alias-results", cl::init(false), cl::Hidden)
FunctionInfo & operator=(const FunctionInfo &RHS)
ModRefInfo getModRefInfoForGlobal(const GlobalValue &GV) const
Returns the ModRefInfo info for this function w.r.t.
This is the interface for a simple mod/ref and alias analysis over globals.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
bool isSized(SmallPtrSetImpl< Type *> *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:264
This class stores info we want to provide to or retain within an alias query.
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
FunctionInfo & operator=(FunctionInfo &&RHS)
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1177
STATISTIC(NumFunctions, "Total number of functions")
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
F(f)
block Block Frequency true
An instruction for reading from memory.
Definition: Instructions.h:167
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
A node in the call graph for a module.
Definition: CallGraph.h:164
LLVM_NODISCARD bool isModAndRefSet(const ModRefInfo MRI)
The mod/ref information collected for a particular function.
ModRefInfo globalClearMayReadAnyGlobal(int I) const
This method clears MayReadAnyGlobal bit added by GlobalsAAResult to return the corresponding ModRefIn...
void addModRefInfoForGlobal(const GlobalValue &GV, ModRefInfo NewMRI)
const CallInst * isFreeCall(const Value *I, const TargetLibraryInfo *TLI)
isFreeCall - Returns non-null if the value is a call to the builtin free()
This indicates that the function could not be classified into one of the behaviors above...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
AnalysisUsage & addRequired()
bool mayReadAnyGlobal() const
Returns whether this function may read any global variable, and we don&#39;t know which global...
#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
static unsigned getInt(StringRef R)
Get an unsigned integer, including error checks.
Definition: DataLayout.cpp:214
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
The access may reference the value stored in memory.
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept...
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:225
static GlobalsAAResult analyzeModule(Module &M, const TargetLibraryInfo &TLI, CallGraph &CG)
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on...
IntType getInt() const
GlobalsAAResult run(Module &M, ModuleAnalysisManager &AM)
The access may reference, modify or both the value stored in memory, a mustAlias relation was found...
FunctionModRefBehavior
Summary of how a function affects memory in the program.
An instruction for storing to memory.
Definition: Instructions.h:320
FunctionInfo(const FunctionInfo &Arg)
ModRefInfo getModRefInfo() const
Returns the ModRefInfo info for this function.
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:258
Analysis containing CSE Info
Definition: CSEInfo.cpp:20
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:78
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
void GetUnderlyingObjects(const Value *V, SmallVectorImpl< const Value *> &Objects, const DataLayout &DL, LoopInfo *LI=nullptr, unsigned MaxLookup=6)
This method is similar to GetUnderlyingObject except that it can look through phi and select instruct...
LLVM_NODISCARD ModRefInfo setMust(const ModRefInfo MRI)
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:324
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
An alias analysis result set for globals.
Definition: GlobalsModRef.h:31
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:223
#define H(x, y, z)
Definition: MD5.cpp:57
FunctionModRefBehavior getModRefBehavior(const Function *F)
getModRefBehavior - Return the behavior of the specified function if called from the specified call s...
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.
This instruction compares its operands according to the predicate given to the constructor.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1222
Value * GetUnderlyingObject(Value *V, const DataLayout &DL, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value...
name anon globals
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This function does not perform any non-local loads or stores to memory.
void initializeGlobalsAAWrapperPassPass(PassRegistry &)
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
Provides information about what library functions are available for the current target.
void eraseModRefInfoForGlobal(const GlobalValue &GV)
Clear a global&#39;s ModRef info.
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
void addModRefInfo(ModRefInfo NewMRI)
Adds new ModRefInfo for this function to its state.
This function does not perform any non-local stores or volatile loads, but may read from any memory l...
The access may modify the value stored in memory.
amdgpu Simplify well known AMD library false FunctionCallee Callee
void setPreservesAll()
Set by analyses that do not transform their input at all.
iterator_range< user_iterator > users()
Definition: Value.h:419
An analysis pass to compute the CallGraph for a Module.
Definition: CallGraph.h:292
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:73
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
FunctionInfo()
Checks to document the invariants of the bit packing here.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1287
ModulePass * createGlobalsAAWrapperPass()
LLVM_NODISCARD ModRefInfo intersectModRef(const ModRefInfo MRI1, const ModRefInfo MRI2)
bool onlyReadsMemory(unsigned OpNo) const
Definition: InstrTypes.h:1557
#define I(x, y, z)
Definition: MD5.cpp:58
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates memory (either malloc...
INITIALIZE_PASS_BEGIN(GlobalsAAWrapperPass, "globals-aa", "Globals Alias Analysis", false, true) INITIALIZE_PASS_END(GlobalsAAWrapperPass
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:332
globals aa
std::vector< CallRecord >::iterator iterator
Definition: CallGraph.h:183
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
LLVM Value Representation.
Definition: Value.h:73
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Definition: Operator.h:40
LLVM_NODISCARD ModRefInfo createModRefInfo(const FunctionModRefBehavior FMRB)
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
inst_range instructions(Function *F)
Definition: InstIterator.h:133
A container for analyses that lazily runs them and caches their results.
LLVM_NODISCARD bool isModOrRefSet(const ModRefInfo MRI)
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
static bool isNonEscapingGlobalNoAliasWithLoad(const GlobalValue *GV, const Value *V, int &Depth, const DataLayout &DL)
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:42
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
alias - If one of the pointers is to a global that we are tracking, and the other is some random poin...
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1236
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...