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