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) &&
374  isFreeCall(I, &GetTLI(*Call->getFunction()))) {
375  if (Writers)
376  Writers->insert(Call->getParent()->getParent());
377  } else {
378  return true; // Argument of an unknown call.
379  }
380  }
381  } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
382  if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
383  return true; // Allow comparison against null.
384  } else if (Constant *C = dyn_cast<Constant>(I)) {
385  // Ignore constants which don't have any live uses.
386  if (isa<GlobalValue>(C) || C->isConstantUsed())
387  return true;
388  } else {
389  return true;
390  }
391  }
392 
393  return false;
394 }
395 
396 /// AnalyzeIndirectGlobalMemory - We found an non-address-taken global variable
397 /// which holds a pointer type. See if the global always points to non-aliased
398 /// heap memory: that is, all initializers of the globals are allocations, and
399 /// those allocations have no use other than initialization of the global.
400 /// Further, all loads out of GV must directly use the memory, not store the
401 /// pointer somewhere. If this is true, we consider the memory pointed to by
402 /// GV to be owned by GV and can disambiguate other pointers from it.
403 bool GlobalsAAResult::AnalyzeIndirectGlobalMemory(GlobalVariable *GV) {
404  // Keep track of values related to the allocation of the memory, f.e. the
405  // value produced by the malloc call and any casts.
406  std::vector<Value *> AllocRelatedValues;
407 
408  // If the initializer is a valid pointer, bail.
409  if (Constant *C = GV->getInitializer())
410  if (!C->isNullValue())
411  return false;
412 
413  // Walk the user list of the global. If we find anything other than a direct
414  // load or store, bail out.
415  for (User *U : GV->users()) {
416  if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
417  // The pointer loaded from the global can only be used in simple ways:
418  // we allow addressing of it and loading storing to it. We do *not* allow
419  // storing the loaded pointer somewhere else or passing to a function.
420  if (AnalyzeUsesOfPointer(LI))
421  return false; // Loaded pointer escapes.
422  // TODO: Could try some IP mod/ref of the loaded pointer.
423  } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
424  // Storing the global itself.
425  if (SI->getOperand(0) == GV)
426  return false;
427 
428  // If storing the null pointer, ignore it.
429  if (isa<ConstantPointerNull>(SI->getOperand(0)))
430  continue;
431 
432  // Check the value being stored.
433  Value *Ptr = GetUnderlyingObject(SI->getOperand(0),
434  GV->getParent()->getDataLayout());
435 
436  if (!isAllocLikeFn(Ptr, &GetTLI(*SI->getFunction())))
437  return false; // Too hard to analyze.
438 
439  // Analyze all uses of the allocation. If any of them are used in a
440  // non-simple way (e.g. stored to another global) bail out.
441  if (AnalyzeUsesOfPointer(Ptr, /*Readers*/ nullptr, /*Writers*/ nullptr,
442  GV))
443  return false; // Loaded pointer escapes.
444 
445  // Remember that this allocation is related to the indirect global.
446  AllocRelatedValues.push_back(Ptr);
447  } else {
448  // Something complex, bail out.
449  return false;
450  }
451  }
452 
453  // Okay, this is an indirect global. Remember all of the allocations for
454  // this global in AllocsForIndirectGlobals.
455  while (!AllocRelatedValues.empty()) {
456  AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV;
457  Handles.emplace_front(*this, AllocRelatedValues.back());
458  Handles.front().I = Handles.begin();
459  AllocRelatedValues.pop_back();
460  }
461  IndirectGlobals.insert(GV);
462  Handles.emplace_front(*this, GV);
463  Handles.front().I = Handles.begin();
464  return true;
465 }
466 
467 void GlobalsAAResult::CollectSCCMembership(CallGraph &CG) {
468  // We do a bottom-up SCC traversal of the call graph. In other words, we
469  // visit all callees before callers (leaf-first).
470  unsigned SCCID = 0;
471  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
472  const std::vector<CallGraphNode *> &SCC = *I;
473  assert(!SCC.empty() && "SCC with no functions?");
474 
475  for (auto *CGN : SCC)
476  if (Function *F = CGN->getFunction())
477  FunctionToSCCMap[F] = SCCID;
478  ++SCCID;
479  }
480 }
481 
482 /// AnalyzeCallGraph - At this point, we know the functions where globals are
483 /// immediately stored to and read from. Propagate this information up the call
484 /// graph to all callers and compute the mod/ref info for all memory for each
485 /// function.
486 void GlobalsAAResult::AnalyzeCallGraph(CallGraph &CG, Module &M) {
487  // We do a bottom-up SCC traversal of the call graph. In other words, we
488  // visit all callees before callers (leaf-first).
489  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
490  const std::vector<CallGraphNode *> &SCC = *I;
491  assert(!SCC.empty() && "SCC with no functions?");
492 
493  Function *F = SCC[0]->getFunction();
494 
495  if (!F || !F->isDefinitionExact()) {
496  // Calls externally or not exact - can't say anything useful. Remove any
497  // existing function records (may have been created when scanning
498  // globals).
499  for (auto *Node : SCC)
500  FunctionInfos.erase(Node->getFunction());
501  continue;
502  }
503 
504  FunctionInfo &FI = FunctionInfos[F];
505  Handles.emplace_front(*this, F);
506  Handles.front().I = Handles.begin();
507  bool KnowNothing = false;
508 
509  // Collect the mod/ref properties due to called functions. We only compute
510  // one mod-ref set.
511  for (unsigned i = 0, e = SCC.size(); i != e && !KnowNothing; ++i) {
512  if (!F) {
513  KnowNothing = true;
514  break;
515  }
516 
517  if (F->isDeclaration() || F->hasOptNone()) {
518  // Try to get mod/ref behaviour from function attributes.
519  if (F->doesNotAccessMemory()) {
520  // Can't do better than that!
521  } else if (F->onlyReadsMemory()) {
523  if (!F->isIntrinsic() && !F->onlyAccessesArgMemory())
524  // This function might call back into the module and read a global -
525  // consider every global as possibly being read by this function.
526  FI.setMayReadAnyGlobal();
527  } else {
529  // Can't say anything useful unless it's an intrinsic - they don't
530  // read or write global variables of the kind considered here.
531  KnowNothing = !F->isIntrinsic();
532  }
533  continue;
534  }
535 
536  for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end();
537  CI != E && !KnowNothing; ++CI)
538  if (Function *Callee = CI->second->getFunction()) {
539  if (FunctionInfo *CalleeFI = getFunctionInfo(Callee)) {
540  // Propagate function effect up.
541  FI.addFunctionInfo(*CalleeFI);
542  } else {
543  // Can't say anything about it. However, if it is inside our SCC,
544  // then nothing needs to be done.
545  CallGraphNode *CalleeNode = CG[Callee];
546  if (!is_contained(SCC, CalleeNode))
547  KnowNothing = true;
548  }
549  } else {
550  KnowNothing = true;
551  }
552  }
553 
554  // If we can't say anything useful about this SCC, remove all SCC functions
555  // from the FunctionInfos map.
556  if (KnowNothing) {
557  for (auto *Node : SCC)
558  FunctionInfos.erase(Node->getFunction());
559  continue;
560  }
561 
562  // Scan the function bodies for explicit loads or stores.
563  for (auto *Node : SCC) {
564  if (isModAndRefSet(FI.getModRefInfo()))
565  break; // The mod/ref lattice saturates here.
566 
567  // Don't prove any properties based on the implementation of an optnone
568  // function. Function attributes were already used as a best approximation
569  // above.
570  if (Node->getFunction()->hasOptNone())
571  continue;
572 
573  for (Instruction &I : instructions(Node->getFunction())) {
574  if (isModAndRefSet(FI.getModRefInfo()))
575  break; // The mod/ref lattice saturates here.
576 
577  // We handle calls specially because the graph-relevant aspects are
578  // handled above.
579  if (auto *Call = dyn_cast<CallBase>(&I)) {
580  auto &TLI = GetTLI(*Node->getFunction());
581  if (isAllocationFn(Call, &TLI) || isFreeCall(Call, &TLI)) {
582  // FIXME: It is completely unclear why this is necessary and not
583  // handled by the above graph code.
585  } else if (Function *Callee = Call->getCalledFunction()) {
586  // The callgraph doesn't include intrinsic calls.
587  if (Callee->isIntrinsic()) {
588  if (isa<DbgInfoIntrinsic>(Call))
589  // Don't let dbg intrinsics affect alias info.
590  continue;
591 
592  FunctionModRefBehavior Behaviour =
594  FI.addModRefInfo(createModRefInfo(Behaviour));
595  }
596  }
597  continue;
598  }
599 
600  // All non-call instructions we use the primary predicates for whether
601  // they read or write memory.
602  if (I.mayReadFromMemory())
604  if (I.mayWriteToMemory())
606  }
607  }
608 
609  if (!isModSet(FI.getModRefInfo()))
610  ++NumReadMemFunctions;
611  if (!isModOrRefSet(FI.getModRefInfo()))
612  ++NumNoMemFunctions;
613 
614  // Finally, now that we know the full effect on this SCC, clone the
615  // information to each function in the SCC.
616  // FI is a reference into FunctionInfos, so copy it now so that it doesn't
617  // get invalidated if DenseMap decides to re-hash.
618  FunctionInfo CachedFI = FI;
619  for (unsigned i = 1, e = SCC.size(); i != e; ++i)
620  FunctionInfos[SCC[i]->getFunction()] = CachedFI;
621  }
622 }
623 
624 // GV is a non-escaping global. V is a pointer address that has been loaded from.
625 // If we can prove that V must escape, we can conclude that a load from V cannot
626 // alias GV.
628  const Value *V,
629  int &Depth,
630  const DataLayout &DL) {
633  Visited.insert(V);
634  Inputs.push_back(V);
635  do {
636  const Value *Input = Inputs.pop_back_val();
637 
638  if (isa<GlobalValue>(Input) || isa<Argument>(Input) || isa<CallInst>(Input) ||
639  isa<InvokeInst>(Input))
640  // Arguments to functions or returns from functions are inherently
641  // escaping, so we can immediately classify those as not aliasing any
642  // non-addr-taken globals.
643  //
644  // (Transitive) loads from a global are also safe - if this aliased
645  // another global, its address would escape, so no alias.
646  continue;
647 
648  // Recurse through a limited number of selects, loads and PHIs. This is an
649  // arbitrary depth of 4, lower numbers could be used to fix compile time
650  // issues if needed, but this is generally expected to be only be important
651  // for small depths.
652  if (++Depth > 4)
653  return false;
654 
655  if (auto *LI = dyn_cast<LoadInst>(Input)) {
656  Inputs.push_back(GetUnderlyingObject(LI->getPointerOperand(), DL));
657  continue;
658  }
659  if (auto *SI = dyn_cast<SelectInst>(Input)) {
660  const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), DL);
661  const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), DL);
662  if (Visited.insert(LHS).second)
663  Inputs.push_back(LHS);
664  if (Visited.insert(RHS).second)
665  Inputs.push_back(RHS);
666  continue;
667  }
668  if (auto *PN = dyn_cast<PHINode>(Input)) {
669  for (const Value *Op : PN->incoming_values()) {
670  Op = GetUnderlyingObject(Op, DL);
671  if (Visited.insert(Op).second)
672  Inputs.push_back(Op);
673  }
674  continue;
675  }
676 
677  return false;
678  } while (!Inputs.empty());
679 
680  // All inputs were known to be no-alias.
681  return true;
682 }
683 
684 // There are particular cases where we can conclude no-alias between
685 // a non-addr-taken global and some other underlying object. Specifically,
686 // a non-addr-taken global is known to not be escaped from any function. It is
687 // also incorrect for a transformation to introduce an escape of a global in
688 // a way that is observable when it was not there previously. One function
689 // being transformed to introduce an escape which could possibly be observed
690 // (via loading from a global or the return value for example) within another
691 // function is never safe. If the observation is made through non-atomic
692 // operations on different threads, it is a data-race and UB. If the
693 // observation is well defined, by being observed the transformation would have
694 // changed program behavior by introducing the observed escape, making it an
695 // invalid transform.
696 //
697 // This property does require that transformations which *temporarily* escape
698 // a global that was not previously escaped, prior to restoring it, cannot rely
699 // on the results of GMR::alias. This seems a reasonable restriction, although
700 // currently there is no way to enforce it. There is also no realistic
701 // optimization pass that would make this mistake. The closest example is
702 // a transformation pass which does reg2mem of SSA values but stores them into
703 // global variables temporarily before restoring the global variable's value.
704 // This could be useful to expose "benign" races for example. However, it seems
705 // reasonable to require that a pass which introduces escapes of global
706 // variables in this way to either not trust AA results while the escape is
707 // active, or to be forced to operate as a module pass that cannot co-exist
708 // with an alias analysis such as GMR.
709 bool GlobalsAAResult::isNonEscapingGlobalNoAlias(const GlobalValue *GV,
710  const Value *V) {
711  // In order to know that the underlying object cannot alias the
712  // non-addr-taken global, we must know that it would have to be an escape.
713  // Thus if the underlying object is a function argument, a load from
714  // a global, or the return of a function, it cannot alias. We can also
715  // recurse through PHI nodes and select nodes provided all of their inputs
716  // resolve to one of these known-escaping roots.
719  Visited.insert(V);
720  Inputs.push_back(V);
721  int Depth = 0;
722  do {
723  const Value *Input = Inputs.pop_back_val();
724 
725  if (auto *InputGV = dyn_cast<GlobalValue>(Input)) {
726  // If one input is the very global we're querying against, then we can't
727  // conclude no-alias.
728  if (InputGV == GV)
729  return false;
730 
731  // Distinct GlobalVariables never alias, unless overriden or zero-sized.
732  // FIXME: The condition can be refined, but be conservative for now.
733  auto *GVar = dyn_cast<GlobalVariable>(GV);
734  auto *InputGVar = dyn_cast<GlobalVariable>(InputGV);
735  if (GVar && InputGVar &&
736  !GVar->isDeclaration() && !InputGVar->isDeclaration() &&
737  !GVar->isInterposable() && !InputGVar->isInterposable()) {
738  Type *GVType = GVar->getInitializer()->getType();
739  Type *InputGVType = InputGVar->getInitializer()->getType();
740  if (GVType->isSized() && InputGVType->isSized() &&
741  (DL.getTypeAllocSize(GVType) > 0) &&
742  (DL.getTypeAllocSize(InputGVType) > 0))
743  continue;
744  }
745 
746  // Conservatively return false, even though we could be smarter
747  // (e.g. look through GlobalAliases).
748  return false;
749  }
750 
751  if (isa<Argument>(Input) || isa<CallInst>(Input) ||
752  isa<InvokeInst>(Input)) {
753  // Arguments to functions or returns from functions are inherently
754  // escaping, so we can immediately classify those as not aliasing any
755  // non-addr-taken globals.
756  continue;
757  }
758 
759  // Recurse through a limited number of selects, loads and PHIs. This is an
760  // arbitrary depth of 4, lower numbers could be used to fix compile time
761  // issues if needed, but this is generally expected to be only be important
762  // for small depths.
763  if (++Depth > 4)
764  return false;
765 
766  if (auto *LI = dyn_cast<LoadInst>(Input)) {
767  // A pointer loaded from a global would have been captured, and we know
768  // that the global is non-escaping, so no alias.
769  const Value *Ptr = GetUnderlyingObject(LI->getPointerOperand(), DL);
770  if (isNonEscapingGlobalNoAliasWithLoad(GV, Ptr, Depth, DL))
771  // The load does not alias with GV.
772  continue;
773  // Otherwise, a load could come from anywhere, so bail.
774  return false;
775  }
776  if (auto *SI = dyn_cast<SelectInst>(Input)) {
777  const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), DL);
778  const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), DL);
779  if (Visited.insert(LHS).second)
780  Inputs.push_back(LHS);
781  if (Visited.insert(RHS).second)
782  Inputs.push_back(RHS);
783  continue;
784  }
785  if (auto *PN = dyn_cast<PHINode>(Input)) {
786  for (const Value *Op : PN->incoming_values()) {
787  Op = GetUnderlyingObject(Op, DL);
788  if (Visited.insert(Op).second)
789  Inputs.push_back(Op);
790  }
791  continue;
792  }
793 
794  // FIXME: It would be good to handle other obvious no-alias cases here, but
795  // it isn't clear how to do so reasonably without building a small version
796  // of BasicAA into this code. We could recurse into AAResultBase::alias
797  // here but that seems likely to go poorly as we're inside the
798  // implementation of such a query. Until then, just conservatively return
799  // false.
800  return false;
801  } while (!Inputs.empty());
802 
803  // If all the inputs to V were definitively no-alias, then V is no-alias.
804  return true;
805 }
806 
807 /// alias - If one of the pointers is to a global that we are tracking, and the
808 /// other is some random pointer, we know there cannot be an alias, because the
809 /// address of the global isn't taken.
811  const MemoryLocation &LocB,
812  AAQueryInfo &AAQI) {
813  // Get the base object these pointers point to.
814  const Value *UV1 = GetUnderlyingObject(LocA.Ptr, DL);
815  const Value *UV2 = GetUnderlyingObject(LocB.Ptr, DL);
816 
817  // If either of the underlying values is a global, they may be non-addr-taken
818  // globals, which we can answer queries about.
819  const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
820  const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
821  if (GV1 || GV2) {
822  // If the global's address is taken, pretend we don't know it's a pointer to
823  // the global.
824  if (GV1 && !NonAddressTakenGlobals.count(GV1))
825  GV1 = nullptr;
826  if (GV2 && !NonAddressTakenGlobals.count(GV2))
827  GV2 = nullptr;
828 
829  // If the two pointers are derived from two different non-addr-taken
830  // globals we know these can't alias.
831  if (GV1 && GV2 && GV1 != GV2)
832  return NoAlias;
833 
834  // If one is and the other isn't, it isn't strictly safe but we can fake
835  // this result if necessary for performance. This does not appear to be
836  // a common problem in practice.
838  if ((GV1 || GV2) && GV1 != GV2)
839  return NoAlias;
840 
841  // Check for a special case where a non-escaping global can be used to
842  // conclude no-alias.
843  if ((GV1 || GV2) && GV1 != GV2) {
844  const GlobalValue *GV = GV1 ? GV1 : GV2;
845  const Value *UV = GV1 ? UV2 : UV1;
846  if (isNonEscapingGlobalNoAlias(GV, UV))
847  return NoAlias;
848  }
849 
850  // Otherwise if they are both derived from the same addr-taken global, we
851  // can't know the two accesses don't overlap.
852  }
853 
854  // These pointers may be based on the memory owned by an indirect global. If
855  // so, we may be able to handle this. First check to see if the base pointer
856  // is a direct load from an indirect global.
857  GV1 = GV2 = nullptr;
858  if (const LoadInst *LI = dyn_cast<LoadInst>(UV1))
859  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
860  if (IndirectGlobals.count(GV))
861  GV1 = GV;
862  if (const LoadInst *LI = dyn_cast<LoadInst>(UV2))
863  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
864  if (IndirectGlobals.count(GV))
865  GV2 = GV;
866 
867  // These pointers may also be from an allocation for the indirect global. If
868  // so, also handle them.
869  if (!GV1)
870  GV1 = AllocsForIndirectGlobals.lookup(UV1);
871  if (!GV2)
872  GV2 = AllocsForIndirectGlobals.lookup(UV2);
873 
874  // Now that we know whether the two pointers are related to indirect globals,
875  // use this to disambiguate the pointers. If the pointers are based on
876  // different indirect globals they cannot alias.
877  if (GV1 && GV2 && GV1 != GV2)
878  return NoAlias;
879 
880  // If one is based on an indirect global and the other isn't, it isn't
881  // strictly safe but we can fake this result if necessary for performance.
882  // This does not appear to be a common problem in practice.
884  if ((GV1 || GV2) && GV1 != GV2)
885  return NoAlias;
886 
887  return AAResultBase::alias(LocA, LocB, AAQI);
888 }
889 
890 ModRefInfo GlobalsAAResult::getModRefInfoForArgument(const CallBase *Call,
891  const GlobalValue *GV,
892  AAQueryInfo &AAQI) {
893  if (Call->doesNotAccessMemory())
894  return ModRefInfo::NoModRef;
895  ModRefInfo ConservativeResult =
897 
898  // Iterate through all the arguments to the called function. If any argument
899  // is based on GV, return the conservative result.
900  for (auto &A : Call->args()) {
902  GetUnderlyingObjects(A, Objects, DL);
903 
904  // All objects must be identified.
905  if (!all_of(Objects, isIdentifiedObject) &&
906  // Try ::alias to see if all objects are known not to alias GV.
907  !all_of(Objects, [&](const Value *V) {
908  return this->alias(MemoryLocation(V), MemoryLocation(GV), AAQI) ==
909  NoAlias;
910  }))
911  return ConservativeResult;
912 
913  if (is_contained(Objects, GV))
914  return ConservativeResult;
915  }
916 
917  // We identified all objects in the argument list, and none of them were GV.
918  return ModRefInfo::NoModRef;
919 }
920 
922  const MemoryLocation &Loc,
923  AAQueryInfo &AAQI) {
925 
926  // If we are asking for mod/ref info of a direct call with a pointer to a
927  // global we are tracking, return information if we have it.
928  if (const GlobalValue *GV =
929  dyn_cast<GlobalValue>(GetUnderlyingObject(Loc.Ptr, DL)))
930  if (GV->hasLocalLinkage())
931  if (const Function *F = Call->getCalledFunction())
932  if (NonAddressTakenGlobals.count(GV))
933  if (const FunctionInfo *FI = getFunctionInfo(F))
934  Known = unionModRef(FI->getModRefInfoForGlobal(*GV),
935  getModRefInfoForArgument(Call, GV, AAQI));
936 
937  if (!isModOrRefSet(Known))
938  return ModRefInfo::NoModRef; // No need to query other mod/ref analyses
939  return intersectModRef(Known, AAResultBase::getModRefInfo(Call, Loc, AAQI));
940 }
941 
942 GlobalsAAResult::GlobalsAAResult(
943  const DataLayout &DL,
944  std::function<const TargetLibraryInfo &(Function &F)> GetTLI)
945  : AAResultBase(), DL(DL), GetTLI(std::move(GetTLI)) {}
946 
947 GlobalsAAResult::GlobalsAAResult(GlobalsAAResult &&Arg)
948  : AAResultBase(std::move(Arg)), DL(Arg.DL), GetTLI(std::move(Arg.GetTLI)),
949  NonAddressTakenGlobals(std::move(Arg.NonAddressTakenGlobals)),
950  IndirectGlobals(std::move(Arg.IndirectGlobals)),
951  AllocsForIndirectGlobals(std::move(Arg.AllocsForIndirectGlobals)),
952  FunctionInfos(std::move(Arg.FunctionInfos)),
953  Handles(std::move(Arg.Handles)) {
954  // Update the parent for each DeletionCallbackHandle.
955  for (auto &H : Handles) {
956  assert(H.GAR == &Arg);
957  H.GAR = this;
958  }
959 }
960 
962 
964  Module &M, std::function<const TargetLibraryInfo &(Function &F)> GetTLI,
965  CallGraph &CG) {
966  GlobalsAAResult Result(M.getDataLayout(), GetTLI);
967 
968  // Discover which functions aren't recursive, to feed into AnalyzeGlobals.
969  Result.CollectSCCMembership(CG);
970 
971  // Find non-addr taken globals.
972  Result.AnalyzeGlobals(M);
973 
974  // Propagate on CG.
975  Result.AnalyzeCallGraph(CG, M);
976 
977  return Result;
978 }
979 
980 AnalysisKey GlobalsAA::Key;
981 
984  AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
985  auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
986  return FAM.getResult<TargetLibraryAnalysis>(F);
987  };
988  return GlobalsAAResult::analyzeModule(M, GetTLI,
990 }
991 
992 char GlobalsAAWrapperPass::ID = 0;
994  "Globals Alias Analysis", false, true)
998  "Globals Alias Analysis", false, true)
999 
1001  return new GlobalsAAWrapperPass();
1002 }
1003 
1006 }
1007 
1009  auto GetTLI = [this](Function &F) -> TargetLibraryInfo & {
1010  return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1011  };
1013  M, GetTLI, getAnalysis<CallGraphWrapperPass>().getCallGraph())));
1014  return false;
1015 }
1016 
1018  Result.reset();
1019  return false;
1020 }
1021 
1023  AU.setPreservesAll();
1026 }
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:1165
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:213
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
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
static GlobalsAAResult analyzeModule(Module &M, std::function< const TargetLibraryInfo &(Function &F)> GetTLI, CallGraph &CG)
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.
print Print MemDeps of function
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...
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:1044
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:1224
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...