LLVM  16.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  /// FunctionInfo.getModRefInfo() masks out everything except ModRef so
91  /// this remains correct.
92  enum { MayReadAnyGlobal = 4 };
93 
94  /// Checks to document the invariants of the bit packing here.
95  static_assert((MayReadAnyGlobal & static_cast<int>(ModRefInfo::ModRef)) == 0,
96  "ModRef and the MayReadAnyGlobal flag bits overlap.");
97  static_assert(((MayReadAnyGlobal | static_cast<int>(ModRefInfo::ModRef)) >>
98  AlignedMapPointerTraits::NumLowBitsAvailable) == 0,
99  "Insufficient low bits to store our flag and ModRef info.");
100 
101 public:
102  FunctionInfo() = default;
104  delete Info.getPointer();
105  }
106  // Spell out the copy ond move constructors and assignment operators to get
107  // deep copy semantics and correct move semantics in the face of the
108  // pointer-int pair.
110  : Info(nullptr, Arg.Info.getInt()) {
111  if (const auto *ArgPtr = Arg.Info.getPointer())
112  Info.setPointer(new AlignedMap(*ArgPtr));
113  }
115  : Info(Arg.Info.getPointer(), Arg.Info.getInt()) {
116  Arg.Info.setPointerAndInt(nullptr, 0);
117  }
119  delete Info.getPointer();
120  Info.setPointerAndInt(nullptr, RHS.Info.getInt());
121  if (const auto *RHSPtr = RHS.Info.getPointer())
122  Info.setPointer(new AlignedMap(*RHSPtr));
123  return *this;
124  }
126  delete Info.getPointer();
127  Info.setPointerAndInt(RHS.Info.getPointer(), RHS.Info.getInt());
128  RHS.Info.setPointerAndInt(nullptr, 0);
129  return *this;
130  }
131 
132  /// This method clears MayReadAnyGlobal bit added by GlobalsAAResult to return
133  /// the corresponding ModRefInfo.
135  return ModRefInfo(I & static_cast<int>(ModRefInfo::ModRef));
136  }
137 
138  /// Returns the \c ModRefInfo info for this function.
140  return globalClearMayReadAnyGlobal(Info.getInt());
141  }
142 
143  /// Adds new \c ModRefInfo for this function to its state.
144  void addModRefInfo(ModRefInfo NewMRI) {
145  Info.setInt(Info.getInt() | static_cast<int>(NewMRI));
146  }
147 
148  /// Returns whether this function may read any global variable, and we don't
149  /// know which global.
150  bool mayReadAnyGlobal() const { return Info.getInt() & MayReadAnyGlobal; }
151 
152  /// Sets this function as potentially reading from any global.
153  void setMayReadAnyGlobal() { Info.setInt(Info.getInt() | MayReadAnyGlobal); }
154 
155  /// Returns the \c ModRefInfo info for this function w.r.t. a particular
156  /// global, which may be more precise than the general information above.
158  ModRefInfo GlobalMRI =
160  if (AlignedMap *P = Info.getPointer()) {
161  auto I = P->Map.find(&GV);
162  if (I != P->Map.end())
163  GlobalMRI |= I->second;
164  }
165  return GlobalMRI;
166  }
167 
168  /// Add mod/ref info from another function into ours, saturating towards
169  /// ModRef.
170  void addFunctionInfo(const FunctionInfo &FI) {
172 
173  if (FI.mayReadAnyGlobal())
175 
176  if (AlignedMap *P = FI.Info.getPointer())
177  for (const auto &G : P->Map)
178  addModRefInfoForGlobal(*G.first, G.second);
179  }
180 
182  AlignedMap *P = Info.getPointer();
183  if (!P) {
184  P = new AlignedMap();
185  Info.setPointer(P);
186  }
187  auto &GlobalMRI = P->Map[&GV];
188  GlobalMRI |= NewMRI;
189  }
190 
191  /// Clear a global's ModRef info. Should be used when a global is being
192  /// deleted.
194  if (AlignedMap *P = Info.getPointer())
195  P->Map.erase(&GV);
196  }
197 
198 private:
199  /// All of the information is encoded into a single pointer, with a three bit
200  /// integer in the low three bits. The high bit provides a flag for when this
201  /// function may read any global. The low two bits are the ModRefInfo. And
202  /// the pointer, when non-null, points to a map from GlobalValue to
203  /// ModRefInfo specific to that GlobalValue.
205 };
206 
207 void GlobalsAAResult::DeletionCallbackHandle::deleted() {
208  Value *V = getValPtr();
209  if (auto *F = dyn_cast<Function>(V))
210  GAR->FunctionInfos.erase(F);
211 
212  if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
213  if (GAR->NonAddressTakenGlobals.erase(GV)) {
214  // This global might be an indirect global. If so, remove it and
215  // remove any AllocRelatedValues for it.
216  if (GAR->IndirectGlobals.erase(GV)) {
217  // Remove any entries in AllocsForIndirectGlobals for this global.
218  for (auto I = GAR->AllocsForIndirectGlobals.begin(),
219  E = GAR->AllocsForIndirectGlobals.end();
220  I != E; ++I)
221  if (I->second == GV)
222  GAR->AllocsForIndirectGlobals.erase(I);
223  }
224 
225  // Scan the function info we have collected and remove this global
226  // from all of them.
227  for (auto &FIPair : GAR->FunctionInfos)
228  FIPair.second.eraseModRefInfoForGlobal(*GV);
229  }
230  }
231 
232  // If this is an allocation related to an indirect global, remove it.
233  GAR->AllocsForIndirectGlobals.erase(V);
234 
235  // And clear out the handle.
236  setValPtr(nullptr);
237  GAR->Handles.erase(I);
238  // This object is now destroyed!
239 }
240 
242  if (FunctionInfo *FI = getFunctionInfo(F))
243  return MemoryEffects(FI->getModRefInfo());
244 
246 }
247 
248 /// Returns the function info for the function, or null if we don't have
249 /// anything useful to say about it.
251 GlobalsAAResult::getFunctionInfo(const Function *F) {
252  auto I = FunctionInfos.find(F);
253  if (I != FunctionInfos.end())
254  return &I->second;
255  return nullptr;
256 }
257 
258 /// AnalyzeGlobals - Scan through the users of all of the internal
259 /// GlobalValue's in the program. If none of them have their "address taken"
260 /// (really, their address passed to something nontrivial), record this fact,
261 /// and record the functions that they are used directly in.
262 void GlobalsAAResult::AnalyzeGlobals(Module &M) {
263  SmallPtrSet<Function *, 32> TrackedFunctions;
264  for (Function &F : M)
265  if (F.hasLocalLinkage()) {
266  if (!AnalyzeUsesOfPointer(&F)) {
267  // Remember that we are tracking this global.
268  NonAddressTakenGlobals.insert(&F);
269  TrackedFunctions.insert(&F);
270  Handles.emplace_front(*this, &F);
271  Handles.front().I = Handles.begin();
272  ++NumNonAddrTakenFunctions;
273  } else
274  UnknownFunctionsWithLocalLinkage = true;
275  }
276 
277  SmallPtrSet<Function *, 16> Readers, Writers;
278  for (GlobalVariable &GV : M.globals())
279  if (GV.hasLocalLinkage()) {
280  if (!AnalyzeUsesOfPointer(&GV, &Readers,
281  GV.isConstant() ? nullptr : &Writers)) {
282  // Remember that we are tracking this global, and the mod/ref fns
283  NonAddressTakenGlobals.insert(&GV);
284  Handles.emplace_front(*this, &GV);
285  Handles.front().I = Handles.begin();
286 
287  for (Function *Reader : Readers) {
288  if (TrackedFunctions.insert(Reader).second) {
289  Handles.emplace_front(*this, Reader);
290  Handles.front().I = Handles.begin();
291  }
292  FunctionInfos[Reader].addModRefInfoForGlobal(GV, ModRefInfo::Ref);
293  }
294 
295  if (!GV.isConstant()) // No need to keep track of writers to constants
296  for (Function *Writer : Writers) {
297  if (TrackedFunctions.insert(Writer).second) {
298  Handles.emplace_front(*this, Writer);
299  Handles.front().I = Handles.begin();
300  }
301  FunctionInfos[Writer].addModRefInfoForGlobal(GV, ModRefInfo::Mod);
302  }
303  ++NumNonAddrTakenGlobalVars;
304 
305  // If this global holds a pointer type, see if it is an indirect global.
306  if (GV.getValueType()->isPointerTy() &&
307  AnalyzeIndirectGlobalMemory(&GV))
308  ++NumIndirectGlobalVars;
309  }
310  Readers.clear();
311  Writers.clear();
312  }
313 }
314 
315 /// AnalyzeUsesOfPointer - Look at all of the users of the specified pointer.
316 /// If this is used by anything complex (i.e., the address escapes), return
317 /// true. Also, while we are at it, keep track of those functions that read and
318 /// write to the value.
319 ///
320 /// If OkayStoreDest is non-null, stores into this global are allowed.
321 bool GlobalsAAResult::AnalyzeUsesOfPointer(Value *V,
324  GlobalValue *OkayStoreDest) {
325  if (!V->getType()->isPointerTy())
326  return true;
327 
328  for (Use &U : V->uses()) {
329  User *I = U.getUser();
330  if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
331  if (Readers)
332  Readers->insert(LI->getParent()->getParent());
333  } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
334  if (V == SI->getOperand(1)) {
335  if (Writers)
336  Writers->insert(SI->getParent()->getParent());
337  } else if (SI->getOperand(1) != OkayStoreDest) {
338  return true; // Storing the pointer
339  }
340  } else if (Operator::getOpcode(I) == Instruction::GetElementPtr) {
341  if (AnalyzeUsesOfPointer(I, Readers, Writers))
342  return true;
343  } else if (Operator::getOpcode(I) == Instruction::BitCast ||
344  Operator::getOpcode(I) == Instruction::AddrSpaceCast) {
345  if (AnalyzeUsesOfPointer(I, Readers, Writers, OkayStoreDest))
346  return true;
347  } else if (auto *Call = dyn_cast<CallBase>(I)) {
348  // Make sure that this is just the function being called, not that it is
349  // passing into the function.
350  if (Call->isDataOperand(&U)) {
351  // Detect calls to free.
352  if (Call->isArgOperand(&U) &&
353  getFreedOperand(Call, &GetTLI(*Call->getFunction())) == U) {
354  if (Writers)
355  Writers->insert(Call->getParent()->getParent());
356  } else {
357  // In general, we return true for unknown calls, but there are
358  // some simple checks that we can do for functions that
359  // will never call back into the module.
360  auto *F = Call->getCalledFunction();
361  // TODO: we should be able to remove isDeclaration() check
362  // and let the function body analysis check for captures,
363  // and collect the mod-ref effects. This information will
364  // be later propagated via the call graph.
365  if (!F || !F->isDeclaration())
366  return true;
367  // Note that the NoCallback check here is a little bit too
368  // conservative. If there are no captures of the global
369  // in the module, then this call may not be a capture even
370  // if it does not have NoCallback.
371  if (!Call->hasFnAttr(Attribute::NoCallback) ||
372  !Call->isArgOperand(&U) ||
373  !Call->doesNotCapture(Call->getArgOperandNo(&U)))
374  return true;
375 
376  // Conservatively, assume the call reads and writes the global.
377  // We could use memory attributes to make it more precise.
378  if (Readers)
379  Readers->insert(Call->getParent()->getParent());
380  if (Writers)
381  Writers->insert(Call->getParent()->getParent());
382  }
383  }
384  } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
385  if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
386  return true; // Allow comparison against null.
387  } else if (Constant *C = dyn_cast<Constant>(I)) {
388  // Ignore constants which don't have any live uses.
389  if (isa<GlobalValue>(C) || C->isConstantUsed())
390  return true;
391  } else {
392  return true;
393  }
394  }
395 
396  return false;
397 }
398 
399 /// AnalyzeIndirectGlobalMemory - We found an non-address-taken global variable
400 /// which holds a pointer type. See if the global always points to non-aliased
401 /// heap memory: that is, all initializers of the globals store a value known
402 /// to be obtained via a noalias return function call which have no other use.
403 /// Further, all loads out of GV must directly use the memory, not store the
404 /// pointer somewhere. If this is true, we consider the memory pointed to by
405 /// GV to be owned by GV and can disambiguate other pointers from it.
406 bool GlobalsAAResult::AnalyzeIndirectGlobalMemory(GlobalVariable *GV) {
407  // Keep track of values related to the allocation of the memory, f.e. the
408  // value produced by the noalias call and any casts.
409  std::vector<Value *> AllocRelatedValues;
410 
411  // If the initializer is a valid pointer, bail.
412  if (Constant *C = GV->getInitializer())
413  if (!C->isNullValue())
414  return false;
415 
416  // Walk the user list of the global. If we find anything other than a direct
417  // load or store, bail out.
418  for (User *U : GV->users()) {
419  if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
420  // The pointer loaded from the global can only be used in simple ways:
421  // we allow addressing of it and loading storing to it. We do *not* allow
422  // storing the loaded pointer somewhere else or passing to a function.
423  if (AnalyzeUsesOfPointer(LI))
424  return false; // Loaded pointer escapes.
425  // TODO: Could try some IP mod/ref of the loaded pointer.
426  } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
427  // Storing the global itself.
428  if (SI->getOperand(0) == GV)
429  return false;
430 
431  // If storing the null pointer, ignore it.
432  if (isa<ConstantPointerNull>(SI->getOperand(0)))
433  continue;
434 
435  // Check the value being stored.
436  Value *Ptr = getUnderlyingObject(SI->getOperand(0));
437 
438  if (!isNoAliasCall(Ptr))
439  return false; // Too hard to analyze.
440 
441  // Analyze all uses of the allocation. If any of them are used in a
442  // non-simple way (e.g. stored to another global) bail out.
443  if (AnalyzeUsesOfPointer(Ptr, /*Readers*/ nullptr, /*Writers*/ nullptr,
444  GV))
445  return false; // Loaded pointer escapes.
446 
447  // Remember that this allocation is related to the indirect global.
448  AllocRelatedValues.push_back(Ptr);
449  } else {
450  // Something complex, bail out.
451  return false;
452  }
453  }
454 
455  // Okay, this is an indirect global. Remember all of the allocations for
456  // this global in AllocsForIndirectGlobals.
457  while (!AllocRelatedValues.empty()) {
458  AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV;
459  Handles.emplace_front(*this, AllocRelatedValues.back());
460  Handles.front().I = Handles.begin();
461  AllocRelatedValues.pop_back();
462  }
463  IndirectGlobals.insert(GV);
464  Handles.emplace_front(*this, GV);
465  Handles.front().I = Handles.begin();
466  return true;
467 }
468 
469 void GlobalsAAResult::CollectSCCMembership(CallGraph &CG) {
470  // We do a bottom-up SCC traversal of the call graph. In other words, we
471  // visit all callees before callers (leaf-first).
472  unsigned SCCID = 0;
473  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
474  const std::vector<CallGraphNode *> &SCC = *I;
475  assert(!SCC.empty() && "SCC with no functions?");
476 
477  for (auto *CGN : SCC)
478  if (Function *F = CGN->getFunction())
479  FunctionToSCCMap[F] = SCCID;
480  ++SCCID;
481  }
482 }
483 
484 /// AnalyzeCallGraph - At this point, we know the functions where globals are
485 /// immediately stored to and read from. Propagate this information up the call
486 /// graph to all callers and compute the mod/ref info for all memory for each
487 /// function.
488 void GlobalsAAResult::AnalyzeCallGraph(CallGraph &CG, Module &M) {
489  // We do a bottom-up SCC traversal of the call graph. In other words, we
490  // visit all callees before callers (leaf-first).
491  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
492  const std::vector<CallGraphNode *> &SCC = *I;
493  assert(!SCC.empty() && "SCC with no functions?");
494 
495  Function *F = SCC[0]->getFunction();
496 
497  if (!F || !F->isDefinitionExact()) {
498  // Calls externally or not exact - can't say anything useful. Remove any
499  // existing function records (may have been created when scanning
500  // globals).
501  for (auto *Node : SCC)
502  FunctionInfos.erase(Node->getFunction());
503  continue;
504  }
505 
506  FunctionInfo &FI = FunctionInfos[F];
507  Handles.emplace_front(*this, F);
508  Handles.front().I = Handles.begin();
509  bool KnowNothing = false;
510 
511  // Intrinsics, like any other synchronizing function, can make effects
512  // of other threads visible. Without nosync we know nothing really.
513  // Similarly, if `nocallback` is missing the function, or intrinsic,
514  // can call into the module arbitrarily. If both are set the function
515  // has an effect but will not interact with accesses of internal
516  // globals inside the module. We are conservative here for optnone
517  // functions, might not be necessary.
518  auto MaySyncOrCallIntoModule = [](const Function &F) {
519  return !F.isDeclaration() || !F.hasNoSync() ||
520  !F.hasFnAttribute(Attribute::NoCallback);
521  };
522 
523  // Collect the mod/ref properties due to called functions. We only compute
524  // one mod-ref set.
525  for (unsigned i = 0, e = SCC.size(); i != e && !KnowNothing; ++i) {
526  if (!F) {
527  KnowNothing = true;
528  break;
529  }
530 
531  if (F->isDeclaration() || F->hasOptNone()) {
532  // Try to get mod/ref behaviour from function attributes.
533  if (F->doesNotAccessMemory()) {
534  // Can't do better than that!
535  } else if (F->onlyReadsMemory()) {
536  FI.addModRefInfo(ModRefInfo::Ref);
537  if (!F->onlyAccessesArgMemory() && MaySyncOrCallIntoModule(*F))
538  // This function might call back into the module and read a global -
539  // consider every global as possibly being read by this function.
540  FI.setMayReadAnyGlobal();
541  } else {
542  FI.addModRefInfo(ModRefInfo::ModRef);
543  if (!F->onlyAccessesArgMemory())
544  FI.setMayReadAnyGlobal();
545  if (MaySyncOrCallIntoModule(*F)) {
546  KnowNothing = true;
547  break;
548  }
549  }
550  continue;
551  }
552 
553  for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end();
554  CI != E && !KnowNothing; ++CI)
555  if (Function *Callee = CI->second->getFunction()) {
556  if (FunctionInfo *CalleeFI = getFunctionInfo(Callee)) {
557  // Propagate function effect up.
558  FI.addFunctionInfo(*CalleeFI);
559  } else {
560  // Can't say anything about it. However, if it is inside our SCC,
561  // then nothing needs to be done.
562  CallGraphNode *CalleeNode = CG[Callee];
563  if (!is_contained(SCC, CalleeNode))
564  KnowNothing = true;
565  }
566  } else {
567  KnowNothing = true;
568  }
569  }
570 
571  // If we can't say anything useful about this SCC, remove all SCC functions
572  // from the FunctionInfos map.
573  if (KnowNothing) {
574  for (auto *Node : SCC)
575  FunctionInfos.erase(Node->getFunction());
576  continue;
577  }
578 
579  // Scan the function bodies for explicit loads or stores.
580  for (auto *Node : SCC) {
581  if (isModAndRefSet(FI.getModRefInfo()))
582  break; // The mod/ref lattice saturates here.
583 
584  // Don't prove any properties based on the implementation of an optnone
585  // function. Function attributes were already used as a best approximation
586  // above.
587  if (Node->getFunction()->hasOptNone())
588  continue;
589 
590  for (Instruction &I : instructions(Node->getFunction())) {
591  if (isModAndRefSet(FI.getModRefInfo()))
592  break; // The mod/ref lattice saturates here.
593 
594  // We handle calls specially because the graph-relevant aspects are
595  // handled above.
596  if (auto *Call = dyn_cast<CallBase>(&I)) {
597  if (Function *Callee = Call->getCalledFunction()) {
598  // The callgraph doesn't include intrinsic calls.
599  if (Callee->isIntrinsic()) {
600  if (isa<DbgInfoIntrinsic>(Call))
601  // Don't let dbg intrinsics affect alias info.
602  continue;
603 
604  MemoryEffects Behaviour = AAResultBase::getMemoryEffects(Callee);
605  FI.addModRefInfo(Behaviour.getModRef());
606  }
607  }
608  continue;
609  }
610 
611  // All non-call instructions we use the primary predicates for whether
612  // they read or write memory.
613  if (I.mayReadFromMemory())
614  FI.addModRefInfo(ModRefInfo::Ref);
615  if (I.mayWriteToMemory())
616  FI.addModRefInfo(ModRefInfo::Mod);
617  }
618  }
619 
620  if (!isModSet(FI.getModRefInfo()))
621  ++NumReadMemFunctions;
622  if (!isModOrRefSet(FI.getModRefInfo()))
623  ++NumNoMemFunctions;
624 
625  // Finally, now that we know the full effect on this SCC, clone the
626  // information to each function in the SCC.
627  // FI is a reference into FunctionInfos, so copy it now so that it doesn't
628  // get invalidated if DenseMap decides to re-hash.
629  FunctionInfo CachedFI = FI;
630  for (unsigned i = 1, e = SCC.size(); i != e; ++i)
631  FunctionInfos[SCC[i]->getFunction()] = CachedFI;
632  }
633 }
634 
635 // GV is a non-escaping global. V is a pointer address that has been loaded from.
636 // If we can prove that V must escape, we can conclude that a load from V cannot
637 // alias GV.
639  const Value *V,
640  int &Depth,
641  const DataLayout &DL) {
644  Visited.insert(V);
645  Inputs.push_back(V);
646  do {
647  const Value *Input = Inputs.pop_back_val();
648 
649  if (isa<GlobalValue>(Input) || isa<Argument>(Input) || isa<CallInst>(Input) ||
650  isa<InvokeInst>(Input))
651  // Arguments to functions or returns from functions are inherently
652  // escaping, so we can immediately classify those as not aliasing any
653  // non-addr-taken globals.
654  //
655  // (Transitive) loads from a global are also safe - if this aliased
656  // another global, its address would escape, so no alias.
657  continue;
658 
659  // Recurse through a limited number of selects, loads and PHIs. This is an
660  // arbitrary depth of 4, lower numbers could be used to fix compile time
661  // issues if needed, but this is generally expected to be only be important
662  // for small depths.
663  if (++Depth > 4)
664  return false;
665 
666  if (auto *LI = dyn_cast<LoadInst>(Input)) {
667  Inputs.push_back(getUnderlyingObject(LI->getPointerOperand()));
668  continue;
669  }
670  if (auto *SI = dyn_cast<SelectInst>(Input)) {
671  const Value *LHS = getUnderlyingObject(SI->getTrueValue());
672  const Value *RHS = getUnderlyingObject(SI->getFalseValue());
673  if (Visited.insert(LHS).second)
674  Inputs.push_back(LHS);
675  if (Visited.insert(RHS).second)
676  Inputs.push_back(RHS);
677  continue;
678  }
679  if (auto *PN = dyn_cast<PHINode>(Input)) {
680  for (const Value *Op : PN->incoming_values()) {
682  if (Visited.insert(Op).second)
683  Inputs.push_back(Op);
684  }
685  continue;
686  }
687 
688  return false;
689  } while (!Inputs.empty());
690 
691  // All inputs were known to be no-alias.
692  return true;
693 }
694 
695 // There are particular cases where we can conclude no-alias between
696 // a non-addr-taken global and some other underlying object. Specifically,
697 // a non-addr-taken global is known to not be escaped from any function. It is
698 // also incorrect for a transformation to introduce an escape of a global in
699 // a way that is observable when it was not there previously. One function
700 // being transformed to introduce an escape which could possibly be observed
701 // (via loading from a global or the return value for example) within another
702 // function is never safe. If the observation is made through non-atomic
703 // operations on different threads, it is a data-race and UB. If the
704 // observation is well defined, by being observed the transformation would have
705 // changed program behavior by introducing the observed escape, making it an
706 // invalid transform.
707 //
708 // This property does require that transformations which *temporarily* escape
709 // a global that was not previously escaped, prior to restoring it, cannot rely
710 // on the results of GMR::alias. This seems a reasonable restriction, although
711 // currently there is no way to enforce it. There is also no realistic
712 // optimization pass that would make this mistake. The closest example is
713 // a transformation pass which does reg2mem of SSA values but stores them into
714 // global variables temporarily before restoring the global variable's value.
715 // This could be useful to expose "benign" races for example. However, it seems
716 // reasonable to require that a pass which introduces escapes of global
717 // variables in this way to either not trust AA results while the escape is
718 // active, or to be forced to operate as a module pass that cannot co-exist
719 // with an alias analysis such as GMR.
720 bool GlobalsAAResult::isNonEscapingGlobalNoAlias(const GlobalValue *GV,
721  const Value *V) {
722  // In order to know that the underlying object cannot alias the
723  // non-addr-taken global, we must know that it would have to be an escape.
724  // Thus if the underlying object is a function argument, a load from
725  // a global, or the return of a function, it cannot alias. We can also
726  // recurse through PHI nodes and select nodes provided all of their inputs
727  // resolve to one of these known-escaping roots.
730  Visited.insert(V);
731  Inputs.push_back(V);
732  int Depth = 0;
733  do {
734  const Value *Input = Inputs.pop_back_val();
735 
736  if (auto *InputGV = dyn_cast<GlobalValue>(Input)) {
737  // If one input is the very global we're querying against, then we can't
738  // conclude no-alias.
739  if (InputGV == GV)
740  return false;
741 
742  // Distinct GlobalVariables never alias, unless overriden or zero-sized.
743  // FIXME: The condition can be refined, but be conservative for now.
744  auto *GVar = dyn_cast<GlobalVariable>(GV);
745  auto *InputGVar = dyn_cast<GlobalVariable>(InputGV);
746  if (GVar && InputGVar &&
747  !GVar->isDeclaration() && !InputGVar->isDeclaration() &&
748  !GVar->isInterposable() && !InputGVar->isInterposable()) {
749  Type *GVType = GVar->getInitializer()->getType();
750  Type *InputGVType = InputGVar->getInitializer()->getType();
751  if (GVType->isSized() && InputGVType->isSized() &&
752  (DL.getTypeAllocSize(GVType) > 0) &&
753  (DL.getTypeAllocSize(InputGVType) > 0))
754  continue;
755  }
756 
757  // Conservatively return false, even though we could be smarter
758  // (e.g. look through GlobalAliases).
759  return false;
760  }
761 
762  if (isa<Argument>(Input) || isa<CallInst>(Input) ||
763  isa<InvokeInst>(Input)) {
764  // Arguments to functions or returns from functions are inherently
765  // escaping, so we can immediately classify those as not aliasing any
766  // non-addr-taken globals.
767  continue;
768  }
769 
770  // Recurse through a limited number of selects, loads and PHIs. This is an
771  // arbitrary depth of 4, lower numbers could be used to fix compile time
772  // issues if needed, but this is generally expected to be only be important
773  // for small depths.
774  if (++Depth > 4)
775  return false;
776 
777  if (auto *LI = dyn_cast<LoadInst>(Input)) {
778  // A pointer loaded from a global would have been captured, and we know
779  // that the global is non-escaping, so no alias.
780  const Value *Ptr = getUnderlyingObject(LI->getPointerOperand());
782  // The load does not alias with GV.
783  continue;
784  // Otherwise, a load could come from anywhere, so bail.
785  return false;
786  }
787  if (auto *SI = dyn_cast<SelectInst>(Input)) {
788  const Value *LHS = getUnderlyingObject(SI->getTrueValue());
789  const Value *RHS = getUnderlyingObject(SI->getFalseValue());
790  if (Visited.insert(LHS).second)
791  Inputs.push_back(LHS);
792  if (Visited.insert(RHS).second)
793  Inputs.push_back(RHS);
794  continue;
795  }
796  if (auto *PN = dyn_cast<PHINode>(Input)) {
797  for (const Value *Op : PN->incoming_values()) {
799  if (Visited.insert(Op).second)
800  Inputs.push_back(Op);
801  }
802  continue;
803  }
804 
805  // FIXME: It would be good to handle other obvious no-alias cases here, but
806  // it isn't clear how to do so reasonably without building a small version
807  // of BasicAA into this code. We could recurse into AAResultBase::alias
808  // here but that seems likely to go poorly as we're inside the
809  // implementation of such a query. Until then, just conservatively return
810  // false.
811  return false;
812  } while (!Inputs.empty());
813 
814  // If all the inputs to V were definitively no-alias, then V is no-alias.
815  return true;
816 }
817 
820  // Check whether the analysis has been explicitly invalidated. Otherwise, it's
821  // stateless and remains preserved.
822  auto PAC = PA.getChecker<GlobalsAA>();
823  return !PAC.preservedWhenStateless();
824 }
825 
826 /// alias - If one of the pointers is to a global that we are tracking, and the
827 /// other is some random pointer, we know there cannot be an alias, because the
828 /// address of the global isn't taken.
830  const MemoryLocation &LocB,
831  AAQueryInfo &AAQI) {
832  // Get the base object these pointers point to.
833  const Value *UV1 =
835  const Value *UV2 =
837 
838  // If either of the underlying values is a global, they may be non-addr-taken
839  // globals, which we can answer queries about.
840  const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
841  const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
842  if (GV1 || GV2) {
843  // If the global's address is taken, pretend we don't know it's a pointer to
844  // the global.
845  if (GV1 && !NonAddressTakenGlobals.count(GV1))
846  GV1 = nullptr;
847  if (GV2 && !NonAddressTakenGlobals.count(GV2))
848  GV2 = nullptr;
849 
850  // If the two pointers are derived from two different non-addr-taken
851  // globals we know these can't alias.
852  if (GV1 && GV2 && GV1 != GV2)
853  return AliasResult::NoAlias;
854 
855  // If one is and the other isn't, it isn't strictly safe but we can fake
856  // this result if necessary for performance. This does not appear to be
857  // a common problem in practice.
859  if ((GV1 || GV2) && GV1 != GV2)
860  return AliasResult::NoAlias;
861 
862  // Check for a special case where a non-escaping global can be used to
863  // conclude no-alias.
864  if ((GV1 || GV2) && GV1 != GV2) {
865  const GlobalValue *GV = GV1 ? GV1 : GV2;
866  const Value *UV = GV1 ? UV2 : UV1;
867  if (isNonEscapingGlobalNoAlias(GV, UV))
868  return AliasResult::NoAlias;
869  }
870 
871  // Otherwise if they are both derived from the same addr-taken global, we
872  // can't know the two accesses don't overlap.
873  }
874 
875  // These pointers may be based on the memory owned by an indirect global. If
876  // so, we may be able to handle this. First check to see if the base pointer
877  // is a direct load from an indirect global.
878  GV1 = GV2 = nullptr;
879  if (const LoadInst *LI = dyn_cast<LoadInst>(UV1))
880  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
881  if (IndirectGlobals.count(GV))
882  GV1 = GV;
883  if (const LoadInst *LI = dyn_cast<LoadInst>(UV2))
884  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
885  if (IndirectGlobals.count(GV))
886  GV2 = GV;
887 
888  // These pointers may also be from an allocation for the indirect global. If
889  // so, also handle them.
890  if (!GV1)
891  GV1 = AllocsForIndirectGlobals.lookup(UV1);
892  if (!GV2)
893  GV2 = AllocsForIndirectGlobals.lookup(UV2);
894 
895  // Now that we know whether the two pointers are related to indirect globals,
896  // use this to disambiguate the pointers. If the pointers are based on
897  // different indirect globals they cannot alias.
898  if (GV1 && GV2 && GV1 != GV2)
899  return AliasResult::NoAlias;
900 
901  // If one is based on an indirect global and the other isn't, it isn't
902  // strictly safe but we can fake this result if necessary for performance.
903  // This does not appear to be a common problem in practice.
905  if ((GV1 || GV2) && GV1 != GV2)
906  return AliasResult::NoAlias;
907 
908  return AAResultBase::alias(LocA, LocB, AAQI);
909 }
910 
911 ModRefInfo GlobalsAAResult::getModRefInfoForArgument(const CallBase *Call,
912  const GlobalValue *GV,
913  AAQueryInfo &AAQI) {
914  if (Call->doesNotAccessMemory())
915  return ModRefInfo::NoModRef;
916  ModRefInfo ConservativeResult =
917  Call->onlyReadsMemory() ? ModRefInfo::Ref : ModRefInfo::ModRef;
918 
919  // Iterate through all the arguments to the called function. If any argument
920  // is based on GV, return the conservative result.
921  for (const auto &A : Call->args()) {
923  getUnderlyingObjects(A, Objects);
924 
925  // All objects must be identified.
926  if (!all_of(Objects, isIdentifiedObject) &&
927  // Try ::alias to see if all objects are known not to alias GV.
928  !all_of(Objects, [&](const Value *V) {
929  return this->alias(MemoryLocation::getBeforeOrAfter(V),
931  AAQI) == AliasResult::NoAlias;
932  }))
933  return ConservativeResult;
934 
935  if (is_contained(Objects, GV))
936  return ConservativeResult;
937  }
938 
939  // We identified all objects in the argument list, and none of them were GV.
940  return ModRefInfo::NoModRef;
941 }
942 
944  const MemoryLocation &Loc,
945  AAQueryInfo &AAQI) {
947 
948  // If we are asking for mod/ref info of a direct call with a pointer to a
949  // global we are tracking, return information if we have it.
950  if (const GlobalValue *GV =
951  dyn_cast<GlobalValue>(getUnderlyingObject(Loc.Ptr)))
952  // If GV is internal to this IR and there is no function with local linkage
953  // that has had their address taken, keep looking for a tighter ModRefInfo.
954  if (GV->hasLocalLinkage() && !UnknownFunctionsWithLocalLinkage)
955  if (const Function *F = Call->getCalledFunction())
956  if (NonAddressTakenGlobals.count(GV))
957  if (const FunctionInfo *FI = getFunctionInfo(F))
958  Known = FI->getModRefInfoForGlobal(*GV) |
959  getModRefInfoForArgument(Call, GV, AAQI);
960 
961  return Known;
962 }
963 
964 GlobalsAAResult::GlobalsAAResult(
965  const DataLayout &DL,
966  std::function<const TargetLibraryInfo &(Function &F)> GetTLI)
967  : DL(DL), GetTLI(std::move(GetTLI)) {}
968 
969 GlobalsAAResult::GlobalsAAResult(GlobalsAAResult &&Arg)
970  : AAResultBase(std::move(Arg)), DL(Arg.DL), GetTLI(std::move(Arg.GetTLI)),
971  NonAddressTakenGlobals(std::move(Arg.NonAddressTakenGlobals)),
972  IndirectGlobals(std::move(Arg.IndirectGlobals)),
973  AllocsForIndirectGlobals(std::move(Arg.AllocsForIndirectGlobals)),
974  FunctionInfos(std::move(Arg.FunctionInfos)),
975  Handles(std::move(Arg.Handles)) {
976  // Update the parent for each DeletionCallbackHandle.
977  for (auto &H : Handles) {
978  assert(H.GAR == &Arg);
979  H.GAR = this;
980  }
981 }
982 
984 
986  Module &M, std::function<const TargetLibraryInfo &(Function &F)> GetTLI,
987  CallGraph &CG) {
988  GlobalsAAResult Result(M.getDataLayout(), GetTLI);
989 
990  // Discover which functions aren't recursive, to feed into AnalyzeGlobals.
991  Result.CollectSCCMembership(CG);
992 
993  // Find non-addr taken globals.
994  Result.AnalyzeGlobals(M);
995 
996  // Propagate on CG.
997  Result.AnalyzeCallGraph(CG, M);
998 
999  return Result;
1000 }
1001 
1002 AnalysisKey GlobalsAA::Key;
1003 
1007  auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
1009  };
1010  return GlobalsAAResult::analyzeModule(M, GetTLI,
1012 }
1013 
1015  ModuleAnalysisManager &AM) {
1016  if (auto *G = AM.getCachedResult<GlobalsAA>(M)) {
1017  auto &CG = AM.getResult<CallGraphAnalysis>(M);
1018  G->NonAddressTakenGlobals.clear();
1019  G->UnknownFunctionsWithLocalLinkage = false;
1020  G->IndirectGlobals.clear();
1021  G->AllocsForIndirectGlobals.clear();
1022  G->FunctionInfos.clear();
1023  G->FunctionToSCCMap.clear();
1024  G->Handles.clear();
1025  G->CollectSCCMembership(CG);
1026  G->AnalyzeGlobals(M);
1027  G->AnalyzeCallGraph(CG, M);
1028  }
1029  return PreservedAnalyses::all();
1030 }
1031 
1032 char GlobalsAAWrapperPass::ID = 0;
1034  "Globals Alias Analysis", false, true)
1038  "Globals Alias Analysis", false, true)
1039 
1041  return new GlobalsAAWrapperPass();
1042 }
1043 
1046 }
1047 
1049  auto GetTLI = [this](Function &F) -> TargetLibraryInfo & {
1050  return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1051  };
1053  M, GetTLI, getAnalysis<CallGraphWrapperPass>().getCallGraph())));
1054  return false;
1055 }
1056 
1058  Result.reset();
1059  return false;
1060 }
1061 
1063  AU.setPreservesAll();
1066 }
i
i
Definition: README.txt:29
llvm::GlobalsAA
Analysis pass providing a never-invalidated alias analysis result.
Definition: GlobalsModRef.h:127
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:283
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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::GlobalsAAResult::analyzeModule
static GlobalsAAResult analyzeModule(Module &M, std::function< const TargetLibraryInfo &(Function &F)> GetTLI, CallGraph &CG)
Definition: GlobalsModRef.cpp:985
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
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:237
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:774
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:219
InstIterator.h
llvm::Function
Definition: Function.h:60
llvm::GlobalsAAResult::FunctionInfo::FunctionInfo
FunctionInfo(const FunctionInfo &Arg)
Definition: GlobalsModRef.cpp:109
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:1199
Statistic.h
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::isModSet
bool isModSet(const ModRefInfo MRI)
Definition: ModRef.h:48
llvm::SmallDenseMap< const GlobalValue *, ModRefInfo, 16 >
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:170
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1793
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::isModOrRefSet
bool isModOrRefSet(const ModRefInfo MRI)
Definition: ModRef.h:42
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:83
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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::GlobalsAAResult::FunctionInfo::operator=
FunctionInfo & operator=(FunctionInfo &&RHS)
Definition: GlobalsModRef.cpp:125
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:638
llvm::MemoryEffects
Summary of how a function affects memory in the program.
Definition: ModRef.h:63
llvm::GlobalsAAResult::getMemoryEffects
MemoryEffects getMemoryEffects(const Function *F)
getMemoryEffects - Return the behavior of the specified function if called from the specified call si...
Definition: GlobalsModRef.cpp:241
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
llvm::AAQueryInfo
This class stores info we want to provide to or retain within an alias query.
Definition: AliasAnalysis.h:233
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:1734
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(GlobalsAAWrapperPass, "globals-aa", "Globals Alias Analysis", false, true) INITIALIZE_PASS_END(GlobalsAAWrapperPass
llvm::isNoAliasCall
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
Definition: AliasAnalysis.cpp:879
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
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:818
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::GlobalsAAResult::FunctionInfo::addModRefInfoForGlobal
void addModRefInfoForGlobal(const GlobalValue &GV, ModRefInfo NewMRI)
Definition: GlobalsModRef.cpp:181
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:146
SI
@ SI
Definition: SIInstrInfo.cpp:7966
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:1014
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:4504
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:661
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
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::getFreedOperand
Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
Definition: MemoryBuiltins.cpp:583
llvm::createGlobalsAAWrapperPass
ModulePass * createGlobalsAAWrapperPass()
Definition: GlobalsModRef.cpp:1040
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:298
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:134
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:4549
llvm::GlobalsAAResult::FunctionInfo::getModRefInfo
ModRefInfo getModRefInfo() const
Returns the ModRefInfo info for this function.
Definition: GlobalsModRef.cpp:139
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:1186
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:475
llvm::isModAndRefSet
bool isModAndRefSet(const ModRefInfo MRI)
Definition: ModRef.h:45
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:150
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::MemoryEffects::getModRef
ModRefInfo getModRef(Location Loc) const
Get ModRefInfo for the given Location.
Definition: ModRef.h:164
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:347
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::GlobalsAAResult::FunctionInfo::operator=
FunctionInfo & operator=(const FunctionInfo &RHS)
Definition: GlobalsModRef.cpp:118
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:446
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:1868
llvm::GlobalsAAResult::FunctionInfo::getModRefInfoForGlobal
ModRefInfo getModRefInfoForGlobal(const GlobalValue &GV) const
Returns the ModRefInfo info for this function w.r.t.
Definition: GlobalsModRef.cpp:157
llvm::GlobalsAAResult::FunctionInfo::FunctionInfo
FunctionInfo(FunctionInfo &&Arg)
Definition: GlobalsModRef.cpp:114
llvm::ModRefInfo
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: ModRef.h:27
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:144
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:1861
llvm::GlobalValue::hasLocalLinkage
bool hasLocalLinkage() const
Definition: GlobalValue.h:523
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:701
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:60
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:1057
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::Function::getFunction
const Function & getFunction() const
Definition: Function.h:135
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:310
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::AliasResult::NoAlias
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:101
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:1062
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
llvm::GlobalsAAWrapperPass::runOnModule
bool runOnModule(Module &M) override
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
Definition: GlobalsModRef.cpp:1048
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:187
aa
globals aa
Definition: GlobalsModRef.cpp:1037
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:829
llvm::GlobalsAA::run
GlobalsAAResult run(Module &M, ModuleAnalysisManager &AM)
Definition: GlobalsModRef.cpp:1004
llvm::AArch64::Alias
StringRef Alias
Definition: AArch64TargetParser.h:140
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:891
llvm::GlobalsAAResult::FunctionInfo::setMayReadAnyGlobal
void setMayReadAnyGlobal()
Sets this function as potentially reading from any global.
Definition: GlobalsModRef.cpp:153
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:351
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:793
llvm::GlobalsAAResult::FunctionInfo::eraseModRefInfoForGlobal
void eraseModRefInfoForGlobal(const GlobalValue &GV)
Clear a global's ModRef info.
Definition: GlobalsModRef.cpp:193
PassManager.h
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:226
globals
dxil globals
Definition: DXContainerGlobals.cpp:66
llvm::GlobalsAAWrapperPass::GlobalsAAWrapperPass
GlobalsAAWrapperPass()
Definition: GlobalsModRef.cpp:1044
CallGraph.h
llvm::GlobalsAAResult::~GlobalsAAResult
~GlobalsAAResult()
Instructions.h
llvm::PointerIntPair< AlignedMap *, 3, unsigned, AlignedMapPointerTraits >
llvm::AAResultBase::getMemoryEffects
MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:814
llvm::GlobalsAAResult::FunctionInfo::FunctionInfo
FunctionInfo()=default
Checks to document the invariants of the bit packing here.
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:142
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:279
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:931
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:943
llvm::GlobalsAAResult::FunctionInfo::~FunctionInfo
~FunctionInfo()
Definition: GlobalsModRef.cpp:103
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:450
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::AAResultBase
A base class to help implement the function alias analysis results concept.
Definition: AliasAnalysis.h:790
llvm::ModRefInfo::ModRef
@ ModRef
The access may reference and may modify the value stored in memory.
llvm::AAResultBase::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI)
Definition: AliasAnalysis.h:800
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:211
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