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