LCOV - code coverage report
Current view: top level - lib/Analysis - GlobalsModRef.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 274 325 84.3 %
Date: 2018-09-23 13:06:45 Functions: 30 33 90.9 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13