LLVM  14.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/DerivedTypes.h"
25 #include "llvm/IR/InstIterator.h"
26 #include "llvm/IR/Instructions.h"
27 #include "llvm/IR/IntrinsicInst.h"
28 #include "llvm/IR/Module.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() {}
72  AlignedMap(const AlignedMap &Arg) : Map(Arg.Map) {}
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:
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 are allocations, and
405 /// those allocations have no use other than initialization of the global.
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 malloc 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 (!isAllocLikeFn(Ptr, &GetTLI(*SI->getFunction())))
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  // Collect the mod/ref properties due to called functions. We only compute
515  // one mod-ref set.
516  for (unsigned i = 0, e = SCC.size(); i != e && !KnowNothing; ++i) {
517  if (!F) {
518  KnowNothing = true;
519  break;
520  }
521 
522  if (F->isDeclaration() || F->hasOptNone()) {
523  // Try to get mod/ref behaviour from function attributes.
524  if (F->doesNotAccessMemory()) {
525  // Can't do better than that!
526  } else if (F->onlyReadsMemory()) {
527  FI.addModRefInfo(ModRefInfo::Ref);
528  if (!F->isIntrinsic() && !F->onlyAccessesArgMemory())
529  // This function might call back into the module and read a global -
530  // consider every global as possibly being read by this function.
531  FI.setMayReadAnyGlobal();
532  } else {
533  FI.addModRefInfo(ModRefInfo::ModRef);
534  if (!F->onlyAccessesArgMemory())
535  FI.setMayReadAnyGlobal();
536  if (!F->isIntrinsic()) {
537  KnowNothing = true;
538  break;
539  }
540  }
541  continue;
542  }
543 
544  for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end();
545  CI != E && !KnowNothing; ++CI)
546  if (Function *Callee = CI->second->getFunction()) {
547  if (FunctionInfo *CalleeFI = getFunctionInfo(Callee)) {
548  // Propagate function effect up.
549  FI.addFunctionInfo(*CalleeFI);
550  } else {
551  // Can't say anything about it. However, if it is inside our SCC,
552  // then nothing needs to be done.
553  CallGraphNode *CalleeNode = CG[Callee];
554  if (!is_contained(SCC, CalleeNode))
555  KnowNothing = true;
556  }
557  } else {
558  KnowNothing = true;
559  }
560  }
561 
562  // If we can't say anything useful about this SCC, remove all SCC functions
563  // from the FunctionInfos map.
564  if (KnowNothing) {
565  for (auto *Node : SCC)
566  FunctionInfos.erase(Node->getFunction());
567  continue;
568  }
569 
570  // Scan the function bodies for explicit loads or stores.
571  for (auto *Node : SCC) {
572  if (isModAndRefSet(FI.getModRefInfo()))
573  break; // The mod/ref lattice saturates here.
574 
575  // Don't prove any properties based on the implementation of an optnone
576  // function. Function attributes were already used as a best approximation
577  // above.
578  if (Node->getFunction()->hasOptNone())
579  continue;
580 
581  for (Instruction &I : instructions(Node->getFunction())) {
582  if (isModAndRefSet(FI.getModRefInfo()))
583  break; // The mod/ref lattice saturates here.
584 
585  // We handle calls specially because the graph-relevant aspects are
586  // handled above.
587  if (auto *Call = dyn_cast<CallBase>(&I)) {
588  auto &TLI = GetTLI(*Node->getFunction());
589  if (isAllocationFn(Call, &TLI) || isFreeCall(Call, &TLI)) {
590  // FIXME: It is completely unclear why this is necessary and not
591  // handled by the above graph code.
592  FI.addModRefInfo(ModRefInfo::ModRef);
593  } else if (Function *Callee = Call->getCalledFunction()) {
594  // The callgraph doesn't include intrinsic calls.
595  if (Callee->isIntrinsic()) {
596  if (isa<DbgInfoIntrinsic>(Call))
597  // Don't let dbg intrinsics affect alias info.
598  continue;
599 
600  FunctionModRefBehavior Behaviour =
602  FI.addModRefInfo(createModRefInfo(Behaviour));
603  }
604  }
605  continue;
606  }
607 
608  // All non-call instructions we use the primary predicates for whether
609  // they read or write memory.
610  if (I.mayReadFromMemory())
611  FI.addModRefInfo(ModRefInfo::Ref);
612  if (I.mayWriteToMemory())
613  FI.addModRefInfo(ModRefInfo::Mod);
614  }
615  }
616 
617  if (!isModSet(FI.getModRefInfo()))
618  ++NumReadMemFunctions;
619  if (!isModOrRefSet(FI.getModRefInfo()))
620  ++NumNoMemFunctions;
621 
622  // Finally, now that we know the full effect on this SCC, clone the
623  // information to each function in the SCC.
624  // FI is a reference into FunctionInfos, so copy it now so that it doesn't
625  // get invalidated if DenseMap decides to re-hash.
626  FunctionInfo CachedFI = FI;
627  for (unsigned i = 1, e = SCC.size(); i != e; ++i)
628  FunctionInfos[SCC[i]->getFunction()] = CachedFI;
629  }
630 }
631 
632 // GV is a non-escaping global. V is a pointer address that has been loaded from.
633 // If we can prove that V must escape, we can conclude that a load from V cannot
634 // alias GV.
636  const Value *V,
637  int &Depth,
638  const DataLayout &DL) {
641  Visited.insert(V);
642  Inputs.push_back(V);
643  do {
644  const Value *Input = Inputs.pop_back_val();
645 
646  if (isa<GlobalValue>(Input) || isa<Argument>(Input) || isa<CallInst>(Input) ||
647  isa<InvokeInst>(Input))
648  // Arguments to functions or returns from functions are inherently
649  // escaping, so we can immediately classify those as not aliasing any
650  // non-addr-taken globals.
651  //
652  // (Transitive) loads from a global are also safe - if this aliased
653  // another global, its address would escape, so no alias.
654  continue;
655 
656  // Recurse through a limited number of selects, loads and PHIs. This is an
657  // arbitrary depth of 4, lower numbers could be used to fix compile time
658  // issues if needed, but this is generally expected to be only be important
659  // for small depths.
660  if (++Depth > 4)
661  return false;
662 
663  if (auto *LI = dyn_cast<LoadInst>(Input)) {
664  Inputs.push_back(getUnderlyingObject(LI->getPointerOperand()));
665  continue;
666  }
667  if (auto *SI = dyn_cast<SelectInst>(Input)) {
668  const Value *LHS = getUnderlyingObject(SI->getTrueValue());
669  const Value *RHS = getUnderlyingObject(SI->getFalseValue());
670  if (Visited.insert(LHS).second)
671  Inputs.push_back(LHS);
672  if (Visited.insert(RHS).second)
673  Inputs.push_back(RHS);
674  continue;
675  }
676  if (auto *PN = dyn_cast<PHINode>(Input)) {
677  for (const Value *Op : PN->incoming_values()) {
679  if (Visited.insert(Op).second)
680  Inputs.push_back(Op);
681  }
682  continue;
683  }
684 
685  return false;
686  } while (!Inputs.empty());
687 
688  // All inputs were known to be no-alias.
689  return true;
690 }
691 
692 // There are particular cases where we can conclude no-alias between
693 // a non-addr-taken global and some other underlying object. Specifically,
694 // a non-addr-taken global is known to not be escaped from any function. It is
695 // also incorrect for a transformation to introduce an escape of a global in
696 // a way that is observable when it was not there previously. One function
697 // being transformed to introduce an escape which could possibly be observed
698 // (via loading from a global or the return value for example) within another
699 // function is never safe. If the observation is made through non-atomic
700 // operations on different threads, it is a data-race and UB. If the
701 // observation is well defined, by being observed the transformation would have
702 // changed program behavior by introducing the observed escape, making it an
703 // invalid transform.
704 //
705 // This property does require that transformations which *temporarily* escape
706 // a global that was not previously escaped, prior to restoring it, cannot rely
707 // on the results of GMR::alias. This seems a reasonable restriction, although
708 // currently there is no way to enforce it. There is also no realistic
709 // optimization pass that would make this mistake. The closest example is
710 // a transformation pass which does reg2mem of SSA values but stores them into
711 // global variables temporarily before restoring the global variable's value.
712 // This could be useful to expose "benign" races for example. However, it seems
713 // reasonable to require that a pass which introduces escapes of global
714 // variables in this way to either not trust AA results while the escape is
715 // active, or to be forced to operate as a module pass that cannot co-exist
716 // with an alias analysis such as GMR.
717 bool GlobalsAAResult::isNonEscapingGlobalNoAlias(const GlobalValue *GV,
718  const Value *V) {
719  // In order to know that the underlying object cannot alias the
720  // non-addr-taken global, we must know that it would have to be an escape.
721  // Thus if the underlying object is a function argument, a load from
722  // a global, or the return of a function, it cannot alias. We can also
723  // recurse through PHI nodes and select nodes provided all of their inputs
724  // resolve to one of these known-escaping roots.
727  Visited.insert(V);
728  Inputs.push_back(V);
729  int Depth = 0;
730  do {
731  const Value *Input = Inputs.pop_back_val();
732 
733  if (auto *InputGV = dyn_cast<GlobalValue>(Input)) {
734  // If one input is the very global we're querying against, then we can't
735  // conclude no-alias.
736  if (InputGV == GV)
737  return false;
738 
739  // Distinct GlobalVariables never alias, unless overriden or zero-sized.
740  // FIXME: The condition can be refined, but be conservative for now.
741  auto *GVar = dyn_cast<GlobalVariable>(GV);
742  auto *InputGVar = dyn_cast<GlobalVariable>(InputGV);
743  if (GVar && InputGVar &&
744  !GVar->isDeclaration() && !InputGVar->isDeclaration() &&
745  !GVar->isInterposable() && !InputGVar->isInterposable()) {
746  Type *GVType = GVar->getInitializer()->getType();
747  Type *InputGVType = InputGVar->getInitializer()->getType();
748  if (GVType->isSized() && InputGVType->isSized() &&
749  (DL.getTypeAllocSize(GVType) > 0) &&
750  (DL.getTypeAllocSize(InputGVType) > 0))
751  continue;
752  }
753 
754  // Conservatively return false, even though we could be smarter
755  // (e.g. look through GlobalAliases).
756  return false;
757  }
758 
759  if (isa<Argument>(Input) || isa<CallInst>(Input) ||
760  isa<InvokeInst>(Input)) {
761  // Arguments to functions or returns from functions are inherently
762  // escaping, so we can immediately classify those as not aliasing any
763  // non-addr-taken globals.
764  continue;
765  }
766 
767  // Recurse through a limited number of selects, loads and PHIs. This is an
768  // arbitrary depth of 4, lower numbers could be used to fix compile time
769  // issues if needed, but this is generally expected to be only be important
770  // for small depths.
771  if (++Depth > 4)
772  return false;
773 
774  if (auto *LI = dyn_cast<LoadInst>(Input)) {
775  // A pointer loaded from a global would have been captured, and we know
776  // that the global is non-escaping, so no alias.
777  const Value *Ptr = getUnderlyingObject(LI->getPointerOperand());
778  if (isNonEscapingGlobalNoAliasWithLoad(GV, Ptr, Depth, DL))
779  // The load does not alias with GV.
780  continue;
781  // Otherwise, a load could come from anywhere, so bail.
782  return false;
783  }
784  if (auto *SI = dyn_cast<SelectInst>(Input)) {
785  const Value *LHS = getUnderlyingObject(SI->getTrueValue());
786  const Value *RHS = getUnderlyingObject(SI->getFalseValue());
787  if (Visited.insert(LHS).second)
788  Inputs.push_back(LHS);
789  if (Visited.insert(RHS).second)
790  Inputs.push_back(RHS);
791  continue;
792  }
793  if (auto *PN = dyn_cast<PHINode>(Input)) {
794  for (const Value *Op : PN->incoming_values()) {
796  if (Visited.insert(Op).second)
797  Inputs.push_back(Op);
798  }
799  continue;
800  }
801 
802  // FIXME: It would be good to handle other obvious no-alias cases here, but
803  // it isn't clear how to do so reasonably without building a small version
804  // of BasicAA into this code. We could recurse into AAResultBase::alias
805  // here but that seems likely to go poorly as we're inside the
806  // implementation of such a query. Until then, just conservatively return
807  // false.
808  return false;
809  } while (!Inputs.empty());
810 
811  // If all the inputs to V were definitively no-alias, then V is no-alias.
812  return true;
813 }
814 
817  // Check whether the analysis has been explicitly invalidated. Otherwise, it's
818  // stateless and remains preserved.
819  auto PAC = PA.getChecker<GlobalsAA>();
820  return !PAC.preservedWhenStateless();
821 }
822 
823 /// alias - If one of the pointers is to a global that we are tracking, and the
824 /// other is some random pointer, we know there cannot be an alias, because the
825 /// address of the global isn't taken.
827  const MemoryLocation &LocB,
828  AAQueryInfo &AAQI) {
829  // Get the base object these pointers point to.
830  const Value *UV1 =
832  const Value *UV2 =
834 
835  // If either of the underlying values is a global, they may be non-addr-taken
836  // globals, which we can answer queries about.
837  const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
838  const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
839  if (GV1 || GV2) {
840  // If the global's address is taken, pretend we don't know it's a pointer to
841  // the global.
842  if (GV1 && !NonAddressTakenGlobals.count(GV1))
843  GV1 = nullptr;
844  if (GV2 && !NonAddressTakenGlobals.count(GV2))
845  GV2 = nullptr;
846 
847  // If the two pointers are derived from two different non-addr-taken
848  // globals we know these can't alias.
849  if (GV1 && GV2 && GV1 != GV2)
850  return AliasResult::NoAlias;
851 
852  // If one is and the other isn't, it isn't strictly safe but we can fake
853  // this result if necessary for performance. This does not appear to be
854  // a common problem in practice.
856  if ((GV1 || GV2) && GV1 != GV2)
857  return AliasResult::NoAlias;
858 
859  // Check for a special case where a non-escaping global can be used to
860  // conclude no-alias.
861  if ((GV1 || GV2) && GV1 != GV2) {
862  const GlobalValue *GV = GV1 ? GV1 : GV2;
863  const Value *UV = GV1 ? UV2 : UV1;
864  if (isNonEscapingGlobalNoAlias(GV, UV))
865  return AliasResult::NoAlias;
866  }
867 
868  // Otherwise if they are both derived from the same addr-taken global, we
869  // can't know the two accesses don't overlap.
870  }
871 
872  // These pointers may be based on the memory owned by an indirect global. If
873  // so, we may be able to handle this. First check to see if the base pointer
874  // is a direct load from an indirect global.
875  GV1 = GV2 = nullptr;
876  if (const LoadInst *LI = dyn_cast<LoadInst>(UV1))
877  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
878  if (IndirectGlobals.count(GV))
879  GV1 = GV;
880  if (const LoadInst *LI = dyn_cast<LoadInst>(UV2))
881  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
882  if (IndirectGlobals.count(GV))
883  GV2 = GV;
884 
885  // These pointers may also be from an allocation for the indirect global. If
886  // so, also handle them.
887  if (!GV1)
888  GV1 = AllocsForIndirectGlobals.lookup(UV1);
889  if (!GV2)
890  GV2 = AllocsForIndirectGlobals.lookup(UV2);
891 
892  // Now that we know whether the two pointers are related to indirect globals,
893  // use this to disambiguate the pointers. If the pointers are based on
894  // different indirect globals they cannot alias.
895  if (GV1 && GV2 && GV1 != GV2)
896  return AliasResult::NoAlias;
897 
898  // If one is based on an indirect global and the other isn't, it isn't
899  // strictly safe but we can fake this result if necessary for performance.
900  // This does not appear to be a common problem in practice.
902  if ((GV1 || GV2) && GV1 != GV2)
903  return AliasResult::NoAlias;
904 
905  return AAResultBase::alias(LocA, LocB, AAQI);
906 }
907 
908 ModRefInfo GlobalsAAResult::getModRefInfoForArgument(const CallBase *Call,
909  const GlobalValue *GV,
910  AAQueryInfo &AAQI) {
911  if (Call->doesNotAccessMemory())
912  return ModRefInfo::NoModRef;
913  ModRefInfo ConservativeResult =
914  Call->onlyReadsMemory() ? ModRefInfo::Ref : ModRefInfo::ModRef;
915 
916  // Iterate through all the arguments to the called function. If any argument
917  // is based on GV, return the conservative result.
918  for (auto &A : Call->args()) {
920  getUnderlyingObjects(A, Objects);
921 
922  // All objects must be identified.
923  if (!all_of(Objects, isIdentifiedObject) &&
924  // Try ::alias to see if all objects are known not to alias GV.
925  !all_of(Objects, [&](const Value *V) {
926  return this->alias(MemoryLocation::getBeforeOrAfter(V),
928  AAQI) == AliasResult::NoAlias;
929  }))
930  return ConservativeResult;
931 
932  if (is_contained(Objects, GV))
933  return ConservativeResult;
934  }
935 
936  // We identified all objects in the argument list, and none of them were GV.
937  return ModRefInfo::NoModRef;
938 }
939 
941  const MemoryLocation &Loc,
942  AAQueryInfo &AAQI) {
944 
945  // If we are asking for mod/ref info of a direct call with a pointer to a
946  // global we are tracking, return information if we have it.
947  if (const GlobalValue *GV =
948  dyn_cast<GlobalValue>(getUnderlyingObject(Loc.Ptr)))
949  // If GV is internal to this IR and there is no function with local linkage
950  // that has had their address taken, keep looking for a tighter ModRefInfo.
951  if (GV->hasLocalLinkage() && !UnknownFunctionsWithLocalLinkage)
952  if (const Function *F = Call->getCalledFunction())
953  if (NonAddressTakenGlobals.count(GV))
954  if (const FunctionInfo *FI = getFunctionInfo(F))
955  Known = unionModRef(FI->getModRefInfoForGlobal(*GV),
956  getModRefInfoForArgument(Call, GV, AAQI));
957 
958  if (!isModOrRefSet(Known))
959  return ModRefInfo::NoModRef; // No need to query other mod/ref analyses
960  return intersectModRef(Known, AAResultBase::getModRefInfo(Call, Loc, AAQI));
961 }
962 
963 GlobalsAAResult::GlobalsAAResult(
964  const DataLayout &DL,
965  std::function<const TargetLibraryInfo &(Function &F)> GetTLI)
966  : AAResultBase(), DL(DL), GetTLI(std::move(GetTLI)) {}
967 
968 GlobalsAAResult::GlobalsAAResult(GlobalsAAResult &&Arg)
969  : AAResultBase(std::move(Arg)), DL(Arg.DL), GetTLI(std::move(Arg.GetTLI)),
970  NonAddressTakenGlobals(std::move(Arg.NonAddressTakenGlobals)),
971  IndirectGlobals(std::move(Arg.IndirectGlobals)),
972  AllocsForIndirectGlobals(std::move(Arg.AllocsForIndirectGlobals)),
973  FunctionInfos(std::move(Arg.FunctionInfos)),
974  Handles(std::move(Arg.Handles)) {
975  // Update the parent for each DeletionCallbackHandle.
976  for (auto &H : Handles) {
977  assert(H.GAR == &Arg);
978  H.GAR = this;
979  }
980 }
981 
983 
985  Module &M, std::function<const TargetLibraryInfo &(Function &F)> GetTLI,
986  CallGraph &CG) {
987  GlobalsAAResult Result(M.getDataLayout(), GetTLI);
988 
989  // Discover which functions aren't recursive, to feed into AnalyzeGlobals.
990  Result.CollectSCCMembership(CG);
991 
992  // Find non-addr taken globals.
993  Result.AnalyzeGlobals(M);
994 
995  // Propagate on CG.
996  Result.AnalyzeCallGraph(CG, M);
997 
998  return Result;
999 }
1000 
1001 AnalysisKey GlobalsAA::Key;
1002 
1006  auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
1008  };
1009  return GlobalsAAResult::analyzeModule(M, GetTLI,
1011 }
1012 
1013 char GlobalsAAWrapperPass::ID = 0;
1015  "Globals Alias Analysis", false, true)
1019  "Globals Alias Analysis", false, true)
1020 
1022  return new GlobalsAAWrapperPass();
1023 }
1024 
1027 }
1028 
1030  auto GetTLI = [this](Function &F) -> TargetLibraryInfo & {
1031  return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1032  };
1034  M, GetTLI, getAnalysis<CallGraphWrapperPass>().getCallGraph())));
1035  return false;
1036 }
1037 
1039  Result.reset();
1040  return false;
1041 }
1042 
1044  AU.setPreservesAll();
1047 }
i
i
Definition: README.txt:29
llvm::GlobalsAA
Analysis pass providing a never-invalidated alias analysis result.
Definition: GlobalsModRef.h:132
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::GlobalsAAResult
An alias analysis result set for globals.
Definition: GlobalsModRef.h:31
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:274
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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:194
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
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:984
llvm::CallGraphAnalysis
An analysis pass to compute the CallGraph for a Module.
Definition: CallGraph.h:305
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:238
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:228
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:779
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:217
InstIterator.h
llvm::Function
Definition: Function.h:61
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:1168
Statistic.h
llvm::GlobalVariable
Definition: GlobalVariable.h:40
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:73
llvm::isAllocLikeFn
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,...
Definition: MemoryBuiltins.cpp:305
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
GlobalsModRef.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
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
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::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
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:449
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
getInt
static Error getInt(StringRef R, IntTy &Result)
Get an unsigned integer, including error checks.
Definition: DataLayout.cpp:229
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
llvm::isAllocationFn
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...
Definition: MemoryBuiltins.cpp:241
F
#define F(x, y, z)
Definition: MD5.cpp:56
isNonEscapingGlobalNoAliasWithLoad
static bool isNonEscapingGlobalNoAliasWithLoad(const GlobalValue *GV, const Value *V, int &Depth, const DataLayout &DL)
Definition: GlobalsModRef.cpp:635
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
llvm::AAQueryInfo
This class stores info we want to provide to or retain within an alias query.
Definition: AliasAnalysis.h:414
CommandLine.h
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:1551
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::GlobalsAAResult::FunctionInfo::FunctionInfo
FunctionInfo()
Checks to document the invariants of the bit packing here.
Definition: GlobalsModRef.cpp:105
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:815
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:147
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:377
false
Definition: StackSlotColoring.cpp:142
llvm::Instruction
Definition: Instruction.h:45
llvm::Operator::getOpcode
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Definition: Operator.h:41
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
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:4377
SmallPtrSet.h
llvm::CallGraphNode
A node in the call graph for a module.
Definition: CallGraph.h:167
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:666
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
llvm::isModSet
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:196
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:228
llvm::AAResultBase::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:1164
llvm::createGlobalsAAWrapperPass
ModulePass * createGlobalsAAWrapperPass()
Definition: GlobalsModRef.cpp:1021
llvm::PointerIntPair::getPointer
PointerTy getPointer() const
Definition: PointerIntPair.h:59
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
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:304
llvm::GlobalValue
Definition: GlobalValue.h:44
llvm::GlobalVariable::getInitializer
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
Definition: GlobalVariable.h:136
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:4422
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:1203
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:463
llvm::scc_iterator
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:42
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:72
llvm::CallGraphWrapperPass
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:337
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::PointerIntPair::getInt
IntType getInt() const
Definition: PointerIntPair.h:61
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:443
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:1616
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:1609
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::GlobalValue::hasLocalLinkage
bool hasLocalLinkage() const
Definition: GlobalValue.h:445
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:703
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
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:1038
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
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:1178
llvm::Function::getFunction
const Function & getFunction() const
Definition: Function.h:136
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:292
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
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:1043
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:175
llvm::GlobalsAAWrapperPass::runOnModule
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
Definition: GlobalsModRef.cpp:1029
llvm::AAResultBase::getModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:1186
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:206
aa
globals aa
Definition: GlobalsModRef.cpp:1018
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:826
llvm::GlobalsAA::run
GlobalsAAResult run(Module &M, ModuleAnalysisManager &AM)
Definition: GlobalsModRef.cpp:1003
std
Definition: BitVector.h:838
llvm::isIdentifiedObject
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
Definition: AliasAnalysis.cpp:973
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:58
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:321
EnableUnsafeGlobalsModRefAliasResults
static cl::opt< bool > EnableUnsafeGlobalsModRefAliasResults("enable-unsafe-globalsmodref-alias-results", cl::init(false), cl::Hidden)
llvm::GlobalsAAResult::FunctionInfo::eraseModRefInfoForGlobal
void eraseModRefInfoForGlobal(const GlobalValue &GV)
Clear a global's ModRef info.
Definition: GlobalsModRef.cpp:198
globals
name anon globals
Definition: NameAnonGlobals.cpp:113
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:219
llvm::GlobalsAAWrapperPass::GlobalsAAWrapperPass
GlobalsAAWrapperPass()
Definition: GlobalsModRef.cpp:1025
CallGraph.h
llvm::GlobalsAAResult::~GlobalsAAResult
~GlobalsAAResult()
Definition: GlobalsModRef.cpp:982
Instructions.h
llvm::PointerIntPair< AlignedMap *, 3, unsigned, AlignedMapPointerTraits >
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
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:275
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
DerivedTypes.h
llvm::SmallPtrSetImpl< Function * >
llvm::PreservedAnalyses::getChecker
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:313
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:936
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:940
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
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1815
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:438
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::AAResultBase
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept.
Definition: AliasAnalysis.h:1076
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:209
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:486
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
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:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
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:498