LCOV - code coverage report
Current view: top level - lib/Analysis - GlobalsModRef.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 365 403 90.6 %
Date: 2017-09-14 15:23:50 Functions: 34 35 97.1 %
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       72306 : static cl::opt<bool> EnableUnsafeGlobalsModRefAliasResults(
      54      144612 :     "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         518 :   struct LLVM_ALIGNAS(8) AlignedMap {
      69         388 :     AlignedMap() {}
      70         130 :     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             :   enum { MayReadAnyGlobal = 4 };
      88             : 
      89             :   /// Checks to document the invariants of the bit packing here.
      90             :   static_assert((MayReadAnyGlobal & MRI_ModRef) == 0,
      91             :                 "ModRef and the MayReadAnyGlobal flag bits overlap.");
      92             :   static_assert(((MayReadAnyGlobal | MRI_ModRef) >>
      93             :                  AlignedMapPointerTraits::NumLowBitsAvailable) == 0,
      94             :                 "Insufficient low bits to store our flag and ModRef info.");
      95             : 
      96             : public:
      97       61362 :   FunctionInfo() : Info() {}
      98      120624 :   ~FunctionInfo() {
      99      120883 :     delete Info.getPointer();
     100       60312 :   }
     101             :   // Spell out the copy ond move constructors and assignment operators to get
     102             :   // deep copy semantics and correct move semantics in the face of the
     103             :   // pointer-int pair.
     104       14833 :   FunctionInfo(const FunctionInfo &Arg)
     105       44499 :       : Info(nullptr, Arg.Info.getInt()) {
     106       29666 :     if (const auto *ArgPtr = Arg.Info.getPointer())
     107         130 :       Info.setPointer(new AlignedMap(*ArgPtr));
     108       14833 :   }
     109             :   FunctionInfo(FunctionInfo &&Arg)
     110       59192 :       : Info(Arg.Info.getPointer(), Arg.Info.getInt()) {
     111       29596 :     Arg.Info.setPointerAndInt(nullptr, 0);
     112             :   }
     113           0 :   FunctionInfo &operator=(const FunctionInfo &RHS) {
     114           0 :     delete Info.getPointer();
     115           0 :     Info.setPointerAndInt(nullptr, RHS.Info.getInt());
     116           0 :     if (const auto *RHSPtr = RHS.Info.getPointer())
     117           0 :       Info.setPointer(new AlignedMap(*RHSPtr));
     118           0 :     return *this;
     119             :   }
     120             :   FunctionInfo &operator=(FunctionInfo &&RHS) {
     121             :     delete Info.getPointer();
     122             :     Info.setPointerAndInt(RHS.Info.getPointer(), RHS.Info.getInt());
     123             :     RHS.Info.setPointerAndInt(nullptr, 0);
     124             :     return *this;
     125             :   }
     126             : 
     127             :   /// Returns the \c ModRefInfo info for this function.
     128             :   ModRefInfo getModRefInfo() const {
     129    27642314 :     return ModRefInfo(Info.getInt() & MRI_ModRef);
     130             :   }
     131             : 
     132             :   /// Adds new \c ModRefInfo for this function to its state.
     133             :   void addModRefInfo(ModRefInfo NewMRI) {
     134       72537 :     Info.setInt(Info.getInt() | NewMRI);
     135             :   }
     136             : 
     137             :   /// Returns whether this function may read any global variable, and we don't
     138             :   /// know which global.
     139       11824 :   bool mayReadAnyGlobal() const { return Info.getInt() & MayReadAnyGlobal; }
     140             : 
     141             :   /// Sets this function as potentially reading from any global.
     142         948 :   void setMayReadAnyGlobal() { Info.setInt(Info.getInt() | MayReadAnyGlobal); }
     143             : 
     144             :   /// Returns the \c ModRefInfo info for this function w.r.t. a particular
     145             :   /// global, which may be more precise than the general information above.
     146        1708 :   ModRefInfo getModRefInfoForGlobal(const GlobalValue &GV) const {
     147        1708 :     ModRefInfo GlobalMRI = mayReadAnyGlobal() ? MRI_Ref : MRI_NoModRef;
     148        3416 :     if (AlignedMap *P = Info.getPointer()) {
     149           0 :       auto I = P->Map.find(&GV);
     150           0 :       if (I != P->Map.end())
     151           0 :         GlobalMRI = ModRefInfo(GlobalMRI | I->second);
     152             :     }
     153        1708 :     return GlobalMRI;
     154             :   }
     155             : 
     156             :   /// Add mod/ref info from another function into ours, saturating towards
     157             :   /// MRI_ModRef.
     158        4204 :   void addFunctionInfo(const FunctionInfo &FI) {
     159        8408 :     addModRefInfo(FI.getModRefInfo());
     160             : 
     161        4204 :     if (FI.mayReadAnyGlobal())
     162             :       setMayReadAnyGlobal();
     163             : 
     164        8408 :     if (AlignedMap *P = FI.Info.getPointer())
     165          96 :       for (const auto &G : P->Map)
     166          24 :         addModRefInfoForGlobal(*G.first, G.second);
     167        4204 :   }
     168             : 
     169         308 :   void addModRefInfoForGlobal(const GlobalValue &GV, ModRefInfo NewMRI) {
     170         616 :     AlignedMap *P = Info.getPointer();
     171         308 :     if (!P) {
     172         388 :       P = new AlignedMap();
     173         194 :       Info.setPointer(P);
     174             :     }
     175         616 :     auto &GlobalMRI = P->Map[&GV];
     176         308 :     GlobalMRI = ModRefInfo(GlobalMRI | NewMRI);
     177         308 :   }
     178             : 
     179             :   /// Clear a global's ModRef info. Should be used when a global is being
     180             :   /// deleted.
     181             :   void eraseModRefInfoForGlobal(const GlobalValue &GV) {
     182     5754720 :     if (AlignedMap *P = Info.getPointer())
     183         393 :       P->Map.erase(&GV);
     184             :   }
     185             : 
     186             : private:
     187             :   /// All of the information is encoded into a single pointer, with a three bit
     188             :   /// integer in the low three bits. The high bit provides a flag for when this
     189             :   /// function may read any global. The low two bits are the ModRefInfo. And
     190             :   /// the pointer, when non-null, points to a map from GlobalValue to
     191             :   /// ModRefInfo specific to that GlobalValue.
     192             :   PointerIntPair<AlignedMap *, 3, unsigned, AlignedMapPointerTraits> Info;
     193             : };
     194             : 
     195        4819 : void GlobalsAAResult::DeletionCallbackHandle::deleted() {
     196        4819 :   Value *V = getValPtr();
     197        3361 :   if (auto *F = dyn_cast<Function>(V))
     198        3361 :     GAR->FunctionInfos.erase(F);
     199             : 
     200        4819 :   if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
     201        9638 :     if (GAR->NonAddressTakenGlobals.erase(GV)) {
     202             :       // This global might be an indirect global.  If so, remove it and
     203             :       // remove any AllocRelatedValues for it.
     204        9638 :       if (GAR->IndirectGlobals.erase(GV)) {
     205             :         // Remove any entries in AllocsForIndirectGlobals for this global.
     206           0 :         for (auto I = GAR->AllocsForIndirectGlobals.begin(),
     207           0 :                   E = GAR->AllocsForIndirectGlobals.end();
     208           0 :              I != E; ++I)
     209           0 :           if (I->second == GV)
     210           0 :             GAR->AllocsForIndirectGlobals.erase(I);
     211             :       }
     212             : 
     213             :       // Scan the function info we have collected and remove this global
     214             :       // from all of them.
     215     2891817 :       for (auto &FIPair : GAR->FunctionInfos)
     216     5754720 :         FIPair.second.eraseModRefInfoForGlobal(*GV);
     217             :     }
     218             :   }
     219             : 
     220             :   // If this is an allocation related to an indirect global, remove it.
     221        4819 :   GAR->AllocsForIndirectGlobals.erase(V);
     222             : 
     223             :   // And clear out the handle.
     224        9638 :   setValPtr(nullptr);
     225       14457 :   GAR->Handles.erase(I);
     226             :   // This object is now destroyed!
     227        4819 : }
     228             : 
     229     8202968 : FunctionModRefBehavior GlobalsAAResult::getModRefBehavior(const Function *F) {
     230     8202968 :   FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
     231             : 
     232     8202968 :   if (FunctionInfo *FI = getFunctionInfo(F)) {
     233     3438407 :     if (FI->getModRefInfo() == MRI_NoModRef)
     234             :       Min = FMRB_DoesNotAccessMemory;
     235     3436307 :     else if ((FI->getModRefInfo() & MRI_Mod) == 0)
     236       23556 :       Min = FMRB_OnlyReadsMemory;
     237             :   }
     238             : 
     239     8202968 :   return FunctionModRefBehavior(AAResultBase::getModRefBehavior(F) & Min);
     240             : }
     241             : 
     242             : FunctionModRefBehavior
     243     8187420 : GlobalsAAResult::getModRefBehavior(ImmutableCallSite CS) {
     244     8187420 :   FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
     245             : 
     246     8187420 :   if (!CS.hasOperandBundles())
     247     8165090 :     if (const Function *F = CS.getCalledFunction())
     248     8165090 :       if (FunctionInfo *FI = getFunctionInfo(F)) {
     249     3431515 :         if (FI->getModRefInfo() == MRI_NoModRef)
     250             :           Min = FMRB_DoesNotAccessMemory;
     251     3431509 :         else if ((FI->getModRefInfo() & MRI_Mod) == 0)
     252       23099 :           Min = FMRB_OnlyReadsMemory;
     253             :       }
     254             : 
     255     8187420 :   return FunctionModRefBehavior(AAResultBase::getModRefBehavior(CS) & Min);
     256             : }
     257             : 
     258             : /// Returns the function info for the function, or null if we don't have
     259             : /// anything useful to say about it.
     260             : GlobalsAAResult::FunctionInfo *
     261    16381071 : GlobalsAAResult::getFunctionInfo(const Function *F) {
     262    16381071 :   auto I = FunctionInfos.find(F);
     263    49143213 :   if (I != FunctionInfos.end())
     264     6875834 :     return &I->second;
     265             :   return nullptr;
     266             : }
     267             : 
     268             : /// AnalyzeGlobals - Scan through the users of all of the internal
     269             : /// GlobalValue's in the program.  If none of them have their "address taken"
     270             : /// (really, their address passed to something nontrivial), record this fact,
     271             : /// and record the functions that they are used directly in.
     272        2079 : void GlobalsAAResult::AnalyzeGlobals(Module &M) {
     273        4158 :   SmallPtrSet<Function *, 32> TrackedFunctions;
     274       65185 :   for (Function &F : M)
     275       58948 :     if (F.hasLocalLinkage())
     276        4642 :       if (!AnalyzeUsesOfPointer(&F)) {
     277             :         // Remember that we are tracking this global.
     278        3809 :         NonAddressTakenGlobals.insert(&F);
     279        3809 :         TrackedFunctions.insert(&F);
     280        7618 :         Handles.emplace_front(*this, &F);
     281       11427 :         Handles.front().I = Handles.begin();
     282             :         ++NumNonAddrTakenFunctions;
     283             :       }
     284             : 
     285        8316 :   SmallPtrSet<Function *, 16> Readers, Writers;
     286      117808 :   for (GlobalVariable &GV : M.globals())
     287      115729 :     if (GV.hasLocalLinkage()) {
     288      108916 :       if (!AnalyzeUsesOfPointer(&GV, &Readers,
     289      108916 :                                 GV.isConstant() ? nullptr : &Writers)) {
     290             :         // Remember that we are tracking this global, and the mod/ref fns
     291        1558 :         NonAddressTakenGlobals.insert(&GV);
     292        3116 :         Handles.emplace_front(*this, &GV);
     293        4674 :         Handles.front().I = Handles.begin();
     294             : 
     295        1730 :         for (Function *Reader : Readers) {
     296         172 :           if (TrackedFunctions.insert(Reader).second) {
     297         246 :             Handles.emplace_front(*this, Reader);
     298         369 :             Handles.front().I = Handles.begin();
     299             :           }
     300         344 :           FunctionInfos[Reader].addModRefInfoForGlobal(GV, MRI_Ref);
     301             :         }
     302             : 
     303        1558 :         if (!GV.isConstant()) // No need to keep track of writers to constants
     304         786 :           for (Function *Writer : Writers) {
     305         112 :             if (TrackedFunctions.insert(Writer).second) {
     306          46 :               Handles.emplace_front(*this, Writer);
     307          69 :               Handles.front().I = Handles.begin();
     308             :             }
     309         224 :             FunctionInfos[Writer].addModRefInfoForGlobal(GV, MRI_Mod);
     310             :           }
     311        1558 :         ++NumNonAddrTakenGlobalVars;
     312             : 
     313             :         // If this global holds a pointer type, see if it is an indirect global.
     314        3116 :         if (GV.getValueType()->isPointerTy() &&
     315          19 :             AnalyzeIndirectGlobalMemory(&GV))
     316             :           ++NumIndirectGlobalVars;
     317             :       }
     318      108916 :       Readers.clear();
     319      108916 :       Writers.clear();
     320             :     }
     321        2079 : }
     322             : 
     323             : /// AnalyzeUsesOfPointer - Look at all of the users of the specified pointer.
     324             : /// If this is used by anything complex (i.e., the address escapes), return
     325             : /// true.  Also, while we are at it, keep track of those functions that read and
     326             : /// write to the value.
     327             : ///
     328             : /// If OkayStoreDest is non-null, stores into this global are allowed.
     329      320661 : bool GlobalsAAResult::AnalyzeUsesOfPointer(Value *V,
     330             :                                            SmallPtrSetImpl<Function *> *Readers,
     331             :                                            SmallPtrSetImpl<Function *> *Writers,
     332             :                                            GlobalValue *OkayStoreDest) {
     333      641322 :   if (!V->getType()->isPointerTy())
     334             :     return true;
     335             : 
     336     1046799 :   for (Use &U : V->uses()) {
     337      614317 :     User *I = U.getUser();
     338       48278 :     if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
     339       48278 :       if (Readers)
     340       48268 :         Readers->insert(LI->getParent()->getParent());
     341      155591 :     } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
     342      155591 :       if (V == SI->getOperand(1)) {
     343      153939 :         if (Writers)
     344      153938 :           Writers->insert(SI->getParent()->getParent());
     345        1652 :       } else if (SI->getOperand(1) != OkayStoreDest) {
     346             :         return true; // Storing the pointer
     347             :       }
     348      407528 :     } else if (Operator::getOpcode(I) == Instruction::GetElementPtr) {
     349      185901 :       if (AnalyzeUsesOfPointer(I, Readers, Writers))
     350             :         return true;
     351      221627 :     } else if (Operator::getOpcode(I) == Instruction::BitCast) {
     352       21185 :       if (AnalyzeUsesOfPointer(I, Readers, Writers, OkayStoreDest))
     353             :         return true;
     354      406724 :     } else if (auto CS = CallSite(I)) {
     355             :       // Make sure that this is just the function being called, not that it is
     356             :       // passing into the function.
     357      200121 :       if (CS.isDataOperand(&U)) {
     358             :         // Detect calls to free.
     359      206626 :         if (CS.isArgOperand(&U) && isFreeCall(I, &TLI)) {
     360           0 :           if (Writers)
     361           0 :             Writers->insert(CS->getParent()->getParent());
     362             :         } else {
     363      106549 :           return true; // Argument of an unknown call.
     364             :         }
     365             :       }
     366           2 :     } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
     367           6 :       if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
     368             :         return true; // Allow comparison against null.
     369        2934 :     } else if (Constant *C = dyn_cast<Constant>(I)) {
     370             :       // Ignore constants which don't have any live uses.
     371        5804 :       if (isa<GlobalValue>(C) || C->isConstantUsed())
     372             :         return true;
     373             :     } else {
     374             :       return true;
     375             :     }
     376             :   }
     377             : 
     378             :   return false;
     379             : }
     380             : 
     381             : /// AnalyzeIndirectGlobalMemory - We found an non-address-taken global variable
     382             : /// which holds a pointer type.  See if the global always points to non-aliased
     383             : /// heap memory: that is, all initializers of the globals are allocations, and
     384             : /// those allocations have no use other than initialization of the global.
     385             : /// Further, all loads out of GV must directly use the memory, not store the
     386             : /// pointer somewhere.  If this is true, we consider the memory pointed to by
     387             : /// GV to be owned by GV and can disambiguate other pointers from it.
     388          19 : bool GlobalsAAResult::AnalyzeIndirectGlobalMemory(GlobalVariable *GV) {
     389             :   // Keep track of values related to the allocation of the memory, f.e. the
     390             :   // value produced by the malloc call and any casts.
     391          38 :   std::vector<Value *> AllocRelatedValues;
     392             : 
     393             :   // If the initializer is a valid pointer, bail.
     394          38 :   if (Constant *C = GV->getInitializer())
     395          19 :     if (!C->isNullValue())
     396             :       return false;
     397             :     
     398             :   // Walk the user list of the global.  If we find anything other than a direct
     399             :   // load or store, bail out.
     400          85 :   for (User *U : GV->users()) {
     401          15 :     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
     402             :       // The pointer loaded from the global can only be used in simple ways:
     403             :       // we allow addressing of it and loading storing to it.  We do *not* allow
     404             :       // storing the loaded pointer somewhere else or passing to a function.
     405          15 :       if (AnalyzeUsesOfPointer(LI))
     406             :         return false; // Loaded pointer escapes.
     407             :       // TODO: Could try some IP mod/ref of the loaded pointer.
     408           3 :     } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
     409             :       // Storing the global itself.
     410           3 :       if (SI->getOperand(0) == GV)
     411           0 :         return false;
     412             : 
     413             :       // If storing the null pointer, ignore it.
     414           6 :       if (isa<ConstantPointerNull>(SI->getOperand(0)))
     415           1 :         continue;
     416             : 
     417             :       // Check the value being stored.
     418           4 :       Value *Ptr = GetUnderlyingObject(SI->getOperand(0),
     419           2 :                                        GV->getParent()->getDataLayout());
     420             : 
     421           2 :       if (!isAllocLikeFn(Ptr, &TLI))
     422             :         return false; // Too hard to analyze.
     423             : 
     424             :       // Analyze all uses of the allocation.  If any of them are used in a
     425             :       // non-simple way (e.g. stored to another global) bail out.
     426           2 :       if (AnalyzeUsesOfPointer(Ptr, /*Readers*/ nullptr, /*Writers*/ nullptr,
     427             :                                GV))
     428             :         return false; // Loaded pointer escapes.
     429             : 
     430             :       // Remember that this allocation is related to the indirect global.
     431           2 :       AllocRelatedValues.push_back(Ptr);
     432             :     } else {
     433             :       // Something complex, bail out.
     434             :       return false;
     435             :     }
     436             :   }
     437             : 
     438             :   // Okay, this is an indirect global.  Remember all of the allocations for
     439             :   // this global in AllocsForIndirectGlobals.
     440           5 :   while (!AllocRelatedValues.empty()) {
     441           4 :     AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV;
     442           6 :     Handles.emplace_front(*this, AllocRelatedValues.back());
     443           6 :     Handles.front().I = Handles.begin();
     444           2 :     AllocRelatedValues.pop_back();
     445             :   }
     446           3 :   IndirectGlobals.insert(GV);
     447           6 :   Handles.emplace_front(*this, GV);
     448           9 :   Handles.front().I = Handles.begin();
     449           3 :   return true;
     450             : }
     451             : 
     452        2079 : void GlobalsAAResult::CollectSCCMembership(CallGraph &CG) {  
     453             :   // We do a bottom-up SCC traversal of the call graph.  In other words, we
     454             :   // visit all callees before callers (leaf-first).
     455        2079 :   unsigned SCCID = 0;
     456       68022 :   for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
     457             :     const std::vector<CallGraphNode *> &SCC = *I;
     458             :     assert(!SCC.empty() && "SCC with no functions?");
     459             : 
     460      123643 :     for (auto *CGN : SCC)
     461       61858 :       if (Function *F = CGN->getFunction())
     462      117894 :         FunctionToSCCMap[F] = SCCID;
     463       61785 :     ++SCCID;
     464             :   }
     465        2079 : }
     466             : 
     467             : /// AnalyzeCallGraph - At this point, we know the functions where globals are
     468             : /// immediately stored to and read from.  Propagate this information up the call
     469             : /// graph to all callers and compute the mod/ref info for all memory for each
     470             : /// function.
     471        2079 : void GlobalsAAResult::AnalyzeCallGraph(CallGraph &CG, Module &M) {
     472             :   // We do a bottom-up SCC traversal of the call graph.  In other words, we
     473             :   // visit all callees before callers (leaf-first).
     474       68022 :   for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
     475       61785 :     const std::vector<CallGraphNode *> &SCC = *I;
     476             :     assert(!SCC.empty() && "SCC with no functions?");
     477             : 
     478       61785 :     Function *F = SCC[0]->getFunction();
     479             : 
     480      120659 :     if (!F || !F->isDefinitionExact()) {
     481             :       // Calls externally or not exact - can't say anything useful. Remove any
     482             :       // existing function records (may have been created when scanning
     483             :       // globals).
     484       62348 :       for (auto *Node : SCC)
     485       31210 :         FunctionInfos.erase(Node->getFunction());
     486       78090 :       continue;
     487             :     }
     488             : 
     489       61294 :     FunctionInfo &FI = FunctionInfos[F];
     490       30647 :     bool KnowNothing = false;
     491             : 
     492             :     // Collect the mod/ref properties due to called functions.  We only compute
     493             :     // one mod-ref set.
     494      153235 :     for (unsigned i = 0, e = SCC.size(); i != e && !KnowNothing; ++i) {
     495             :       if (!F) {
     496             :         KnowNothing = true;
     497             :         break;
     498             :       }
     499             : 
     500       61361 :       if (F->isDeclaration() || F->hasFnAttribute(Attribute::OptimizeNone)) {
     501             :         // Try to get mod/ref behaviour from function attributes.
     502       13673 :         if (F->doesNotAccessMemory()) {
     503             :           // Can't do better than that!
     504       11723 :         } else if (F->onlyReadsMemory()) {
     505         416 :           FI.addModRefInfo(MRI_Ref);
     506         702 :           if (!F->isIntrinsic() && !F->onlyAccessesArgMemory())
     507             :             // This function might call back into the module and read a global -
     508             :             // consider every global as possibly being read by this function.
     509             :             FI.setMayReadAnyGlobal();
     510             :         } else {
     511       11307 :           FI.addModRefInfo(MRI_ModRef);
     512             :           // Can't say anything useful unless it's an intrinsic - they don't
     513             :           // read or write global variables of the kind considered here.
     514       11307 :           KnowNothing = !F->isIntrinsic();
     515             :         }
     516       13673 :         continue;
     517             :       }
     518             : 
     519       67896 :       for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end();
     520       27262 :            CI != E && !KnowNothing; ++CI)
     521       10288 :         if (Function *Callee = CI->second->getFunction()) {
     522       10055 :           if (FunctionInfo *CalleeFI = getFunctionInfo(Callee)) {
     523             :             // Propagate function effect up.
     524        4204 :             FI.addFunctionInfo(*CalleeFI);
     525             :           } else {
     526             :             // Can't say anything about it.  However, if it is inside our SCC,
     527             :             // then nothing needs to be done.
     528        5851 :             CallGraphNode *CalleeNode = CG[Callee];
     529        5851 :             if (!is_contained(SCC, CalleeNode))
     530        5850 :               KnowNothing = true;
     531             :           }
     532             :         } else {
     533             :           KnowNothing = true;
     534             :         }
     535             :     }
     536             : 
     537             :     // If we can't say anything useful about this SCC, remove all SCC functions
     538             :     // from the FunctionInfos map.
     539       30647 :     if (KnowNothing) {
     540       79071 :       for (auto *Node : SCC)
     541       15815 :         FunctionInfos.erase(Node->getFunction());
     542       15814 :       continue;
     543             :     }
     544             : 
     545             :     // Scan the function bodies for explicit loads or stores.
     546       71825 :     for (auto *Node : SCC) {
     547       14833 :       if (FI.getModRefInfo() == MRI_ModRef)
     548             :         break; // The mod/ref lattice saturates here.
     549             : 
     550             :       // Don't prove any properties based on the implementation of an optnone
     551             :       // function. Function attributes were already used as a best approximation
     552             :       // above.
     553       24986 :       if (Node->getFunction()->hasFnAttribute(Attribute::OptimizeNone))
     554           2 :         continue;
     555             : 
     556      101727 :       for (Instruction &I : instructions(Node->getFunction())) {
     557       34716 :         if (FI.getModRefInfo() == MRI_ModRef)
     558             :           break; // The mod/ref lattice saturates here.
     559             : 
     560             :         // We handle calls specially because the graph-relevant aspects are
     561             :         // handled above.
     562       59076 :         if (auto CS = CallSite(&I)) {
     563       10412 :           if (isAllocationFn(&I, &TLI) || isFreeCall(&I, &TLI)) {
     564             :             // FIXME: It is completely unclear why this is necessary and not
     565             :             // handled by the above graph code.
     566             :             FI.addModRefInfo(MRI_ModRef);
     567        5206 :           } else if (Function *Callee = CS.getCalledFunction()) {
     568             :             // The callgraph doesn't include intrinsic calls.
     569        5206 :             if (Callee->isIntrinsic()) {
     570             :               FunctionModRefBehavior Behaviour =
     571        3884 :                   AAResultBase::getModRefBehavior(Callee);
     572        3884 :               FI.addModRefInfo(ModRefInfo(Behaviour & MRI_ModRef));
     573             :             }
     574             :           }
     575        5206 :           continue;
     576             :         }
     577             : 
     578             :         // All non-call instructions we use the primary predicates for whether
     579             :         // thay read or write memory.
     580       24332 :         if (I.mayReadFromMemory())
     581             :           FI.addModRefInfo(MRI_Ref);
     582       24332 :         if (I.mayWriteToMemory())
     583             :           FI.addModRefInfo(MRI_Mod);
     584             :       }
     585             :     }
     586             : 
     587       14833 :     if ((FI.getModRefInfo() & MRI_Mod) == 0)
     588             :       ++NumReadMemFunctions;
     589       14833 :     if (FI.getModRefInfo() == MRI_NoModRef)
     590             :       ++NumNoMemFunctions;
     591             : 
     592             :     // Finally, now that we know the full effect on this SCC, clone the
     593             :     // information to each function in the SCC.
     594             :     // FI is a reference into FunctionInfos, so copy it now so that it doesn't
     595             :     // get invalidated if DenseMap decides to re-hash.
     596       29666 :     FunctionInfo CachedFI = FI;
     597       29666 :     for (unsigned i = 1, e = SCC.size(); i != e; ++i)
     598           0 :       FunctionInfos[SCC[i]->getFunction()] = CachedFI;
     599             :   }
     600        2079 : }
     601             : 
     602             : // GV is a non-escaping global. V is a pointer address that has been loaded from.
     603             : // If we can prove that V must escape, we can conclude that a load from V cannot
     604             : // alias GV.
     605        1900 : static bool isNonEscapingGlobalNoAliasWithLoad(const GlobalValue *GV,
     606             :                                                const Value *V,
     607             :                                                int &Depth,
     608             :                                                const DataLayout &DL) {
     609        3800 :   SmallPtrSet<const Value *, 8> Visited;
     610        3800 :   SmallVector<const Value *, 8> Inputs;
     611        1900 :   Visited.insert(V);
     612        1900 :   Inputs.push_back(V);
     613             :   do {
     614        2633 :     const Value *Input = Inputs.pop_back_val();
     615             :     
     616        7543 :     if (isa<GlobalValue>(Input) || isa<Argument>(Input) || isa<CallInst>(Input) ||
     617        1917 :         isa<InvokeInst>(Input))
     618             :       // Arguments to functions or returns from functions are inherently
     619             :       // escaping, so we can immediately classify those as not aliasing any
     620             :       // non-addr-taken globals.
     621             :       //
     622             :       // (Transitive) loads from a global are also safe - if this aliased
     623             :       // another global, its address would escape, so no alias.
     624        1457 :       continue;
     625             : 
     626             :     // Recurse through a limited number of selects, loads and PHIs. This is an
     627             :     // arbitrary depth of 4, lower numbers could be used to fix compile time
     628             :     // issues if needed, but this is generally expected to be only be important
     629             :     // for small depths.
     630        1909 :     if (++Depth > 4)
     631             :       return false;
     632             : 
     633        2577 :     if (auto *LI = dyn_cast<LoadInst>(Input)) {
     634         668 :       Inputs.push_back(GetUnderlyingObject(LI->getPointerOperand(), DL));
     635             :       continue;
     636             :     }  
     637        1575 :     if (auto *SI = dyn_cast<SelectInst>(Input)) {
     638           0 :       const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), DL);
     639           0 :       const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), DL);
     640           0 :       if (Visited.insert(LHS).second)
     641           0 :         Inputs.push_back(LHS);
     642           0 :       if (Visited.insert(RHS).second)
     643           0 :         Inputs.push_back(RHS);
     644           0 :       continue;
     645             :     }
     646        1974 :     if (auto *PN = dyn_cast<PHINode>(Input)) {
     647        1197 :       for (const Value *Op : PN->incoming_values()) {
     648        1596 :         Op = GetUnderlyingObject(Op, DL);
     649         798 :         if (Visited.insert(Op).second)
     650         745 :           Inputs.push_back(Op);
     651             :       }
     652         399 :       continue;
     653             :     }
     654             :     
     655             :     return false;
     656        1457 :   } while (!Inputs.empty());
     657             : 
     658             :   // All inputs were known to be no-alias.
     659             :   return true;
     660             : }
     661             : 
     662             : // There are particular cases where we can conclude no-alias between
     663             : // a non-addr-taken global and some other underlying object. Specifically,
     664             : // a non-addr-taken global is known to not be escaped from any function. It is
     665             : // also incorrect for a transformation to introduce an escape of a global in
     666             : // a way that is observable when it was not there previously. One function
     667             : // being transformed to introduce an escape which could possibly be observed
     668             : // (via loading from a global or the return value for example) within another
     669             : // function is never safe. If the observation is made through non-atomic
     670             : // operations on different threads, it is a data-race and UB. If the
     671             : // observation is well defined, by being observed the transformation would have
     672             : // changed program behavior by introducing the observed escape, making it an
     673             : // invalid transform.
     674             : //
     675             : // This property does require that transformations which *temporarily* escape
     676             : // a global that was not previously escaped, prior to restoring it, cannot rely
     677             : // on the results of GMR::alias. This seems a reasonable restriction, although
     678             : // currently there is no way to enforce it. There is also no realistic
     679             : // optimization pass that would make this mistake. The closest example is
     680             : // a transformation pass which does reg2mem of SSA values but stores them into
     681             : // global variables temporarily before restoring the global variable's value.
     682             : // This could be useful to expose "benign" races for example. However, it seems
     683             : // reasonable to require that a pass which introduces escapes of global
     684             : // variables in this way to either not trust AA results while the escape is
     685             : // active, or to be forced to operate as a module pass that cannot co-exist
     686             : // with an alias analysis such as GMR.
     687        3264 : bool GlobalsAAResult::isNonEscapingGlobalNoAlias(const GlobalValue *GV,
     688             :                                                  const Value *V) {
     689             :   // In order to know that the underlying object cannot alias the
     690             :   // non-addr-taken global, we must know that it would have to be an escape.
     691             :   // Thus if the underlying object is a function argument, a load from
     692             :   // a global, or the return of a function, it cannot alias. We can also
     693             :   // recurse through PHI nodes and select nodes provided all of their inputs
     694             :   // resolve to one of these known-escaping roots.
     695        6528 :   SmallPtrSet<const Value *, 8> Visited;
     696        6528 :   SmallVector<const Value *, 8> Inputs;
     697        3264 :   Visited.insert(V);
     698        3264 :   Inputs.push_back(V);
     699        3264 :   int Depth = 0;
     700             :   do {
     701        3473 :     const Value *Input = Inputs.pop_back_val();
     702             : 
     703        3473 :     if (auto *InputGV = dyn_cast<GlobalValue>(Input)) {
     704             :       // If one input is the very global we're querying against, then we can't
     705             :       // conclude no-alias.
     706           0 :       if (InputGV == GV)
     707             :         return false;
     708             : 
     709             :       // Distinct GlobalVariables never alias, unless overriden or zero-sized.
     710             :       // FIXME: The condition can be refined, but be conservative for now.
     711           0 :       auto *GVar = dyn_cast<GlobalVariable>(GV);
     712           0 :       auto *InputGVar = dyn_cast<GlobalVariable>(InputGV);
     713           0 :       if (GVar && InputGVar &&
     714           0 :           !GVar->isDeclaration() && !InputGVar->isDeclaration() &&
     715           0 :           !GVar->isInterposable() && !InputGVar->isInterposable()) {
     716           0 :         Type *GVType = GVar->getInitializer()->getType();
     717           0 :         Type *InputGVType = InputGVar->getInitializer()->getType();
     718           0 :         if (GVType->isSized() && InputGVType->isSized() &&
     719           0 :             (DL.getTypeAllocSize(GVType) > 0) &&
     720           0 :             (DL.getTypeAllocSize(InputGVType) > 0))
     721        1261 :           continue;
     722             :       }
     723             : 
     724             :       // Conservatively return false, even though we could be smarter
     725             :       // (e.g. look through GlobalAliases).
     726             :       return false;
     727             :     }
     728             : 
     729        7282 :     if (isa<Argument>(Input) || isa<CallInst>(Input) ||
     730        3266 :         isa<InvokeInst>(Input)) {
     731             :       // Arguments to functions or returns from functions are inherently
     732             :       // escaping, so we can immediately classify those as not aliasing any
     733             :       // non-addr-taken globals.
     734         336 :       continue;
     735             :     }
     736             :     
     737             :     // Recurse through a limited number of selects, loads and PHIs. This is an
     738             :     // arbitrary depth of 4, lower numbers could be used to fix compile time
     739             :     // issues if needed, but this is generally expected to be only be important
     740             :     // for small depths.
     741        3137 :     if (++Depth > 4)
     742             :       return false;
     743             : 
     744        5031 :     if (auto *LI = dyn_cast<LoadInst>(Input)) {
     745             :       // A pointer loaded from a global would have been captured, and we know
     746             :       // that the global is non-escaping, so no alias.
     747        5700 :       const Value *Ptr = GetUnderlyingObject(LI->getPointerOperand(), DL);
     748        1900 :       if (isNonEscapingGlobalNoAliasWithLoad(GV, Ptr, Depth, DL))
     749             :         // The load does not alias with GV.
     750         724 :         continue;
     751             :       // Otherwise, a load could come from anywhere, so bail.
     752             :       return false;
     753             :     }
     754        1333 :     if (auto *SI = dyn_cast<SelectInst>(Input)) {
     755         306 :       const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), DL);
     756         306 :       const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), DL);
     757         102 :       if (Visited.insert(LHS).second)
     758         102 :         Inputs.push_back(LHS);
     759         102 :       if (Visited.insert(RHS).second)
     760           0 :         Inputs.push_back(RHS);
     761         102 :       continue;
     762             :     }
     763        1228 :     if (auto *PN = dyn_cast<PHINode>(Input)) {
     764         315 :       for (const Value *Op : PN->incoming_values()) {
     765         432 :         Op = GetUnderlyingObject(Op, DL);
     766         216 :         if (Visited.insert(Op).second)
     767         186 :           Inputs.push_back(Op);
     768             :       }
     769          99 :       continue;
     770             :     }
     771             : 
     772             :     // FIXME: It would be good to handle other obvious no-alias cases here, but
     773             :     // it isn't clear how to do so reasonbly without building a small version
     774             :     // of BasicAA into this code. We could recurse into AAResultBase::alias
     775             :     // here but that seems likely to go poorly as we're inside the
     776             :     // implementation of such a query. Until then, just conservatievly retun
     777             :     // false.
     778             :     return false;
     779        1261 :   } while (!Inputs.empty());
     780             : 
     781             :   // If all the inputs to V were definitively no-alias, then V is no-alias.
     782             :   return true;
     783             : }
     784             : 
     785             : /// alias - If one of the pointers is to a global that we are tracking, and the
     786             : /// other is some random pointer, we know there cannot be an alias, because the
     787             : /// address of the global isn't taken.
     788     1874175 : AliasResult GlobalsAAResult::alias(const MemoryLocation &LocA,
     789             :                                    const MemoryLocation &LocB) {
     790             :   // Get the base object these pointers point to.
     791     3748350 :   const Value *UV1 = GetUnderlyingObject(LocA.Ptr, DL);
     792     3748350 :   const Value *UV2 = GetUnderlyingObject(LocB.Ptr, DL);
     793             : 
     794             :   // If either of the underlying values is a global, they may be non-addr-taken
     795             :   // globals, which we can answer queries about.
     796     1874175 :   const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
     797     1874175 :   const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
     798     1874175 :   if (GV1 || GV2) {
     799             :     // If the global's address is taken, pretend we don't know it's a pointer to
     800             :     // the global.
     801     1585152 :     if (GV1 && !NonAddressTakenGlobals.count(GV1))
     802             :       GV1 = nullptr;
     803     1585152 :     if (GV2 && !NonAddressTakenGlobals.count(GV2))
     804             :       GV2 = nullptr;
     805             : 
     806             :     // If the two pointers are derived from two different non-addr-taken
     807             :     // globals we know these can't alias.
     808     1585152 :     if (GV1 && GV2 && GV1 != GV2)
     809             :       return NoAlias;
     810             : 
     811             :     // If one is and the other isn't, it isn't strictly safe but we can fake
     812             :     // this result if necessary for performance. This does not appear to be
     813             :     // a common problem in practice.
     814     1585152 :     if (EnableUnsafeGlobalsModRefAliasResults)
     815           4 :       if ((GV1 || GV2) && GV1 != GV2)
     816             :         return NoAlias;
     817             : 
     818             :     // Check for a special case where a non-escaping global can be used to
     819             :     // conclude no-alias.
     820     1585148 :     if ((GV1 || GV2) && GV1 != GV2) {
     821        3264 :       const GlobalValue *GV = GV1 ? GV1 : GV2;
     822        3264 :       const Value *UV = GV1 ? UV2 : UV1;
     823        3264 :       if (isNonEscapingGlobalNoAlias(GV, UV))
     824             :         return NoAlias;
     825             :     }
     826             : 
     827             :     // Otherwise if they are both derived from the same addr-taken global, we
     828             :     // can't know the two accesses don't overlap.
     829             :   }
     830             : 
     831             :   // These pointers may be based on the memory owned by an indirect global.  If
     832             :   // so, we may be able to handle this.  First check to see if the base pointer
     833             :   // is a direct load from an indirect global.
     834     1873119 :   GV1 = GV2 = nullptr;
     835       78771 :   if (const LoadInst *LI = dyn_cast<LoadInst>(UV1))
     836      158162 :     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
     837         620 :       if (IndirectGlobals.count(GV))
     838           0 :         GV1 = GV;
     839      266412 :   if (const LoadInst *LI = dyn_cast<LoadInst>(UV2))
     840      534299 :     if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
     841        1475 :       if (IndirectGlobals.count(GV))
     842           2 :         GV2 = GV;
     843             : 
     844             :   // These pointers may also be from an allocation for the indirect global.  If
     845             :   // so, also handle them.
     846     1873119 :   if (!GV1)
     847     3746238 :     GV1 = AllocsForIndirectGlobals.lookup(UV1);
     848     1873119 :   if (!GV2)
     849     3746234 :     GV2 = AllocsForIndirectGlobals.lookup(UV2);
     850             : 
     851             :   // Now that we know whether the two pointers are related to indirect globals,
     852             :   // use this to disambiguate the pointers. If the pointers are based on
     853             :   // different indirect globals they cannot alias.
     854     1873119 :   if (GV1 && GV2 && GV1 != GV2)
     855             :     return NoAlias;
     856             : 
     857             :   // If one is based on an indirect global and the other isn't, it isn't
     858             :   // strictly safe but we can fake this result if necessary for performance.
     859             :   // This does not appear to be a common problem in practice.
     860     1873119 :   if (EnableUnsafeGlobalsModRefAliasResults)
     861           2 :     if ((GV1 || GV2) && GV1 != GV2)
     862             :       return NoAlias;
     863             : 
     864     1873117 :   return AAResultBase::alias(LocA, LocB);
     865             : }
     866             : 
     867        1708 : ModRefInfo GlobalsAAResult::getModRefInfoForArgument(ImmutableCallSite CS,
     868             :                                                      const GlobalValue *GV) {
     869        1708 :   if (CS.doesNotAccessMemory())
     870             :     return MRI_NoModRef;
     871        1698 :   ModRefInfo ConservativeResult = CS.onlyReadsMemory() ? MRI_Ref : MRI_ModRef;
     872             : 
     873             :   // Iterate through all the arguments to the called function. If any argument
     874             :   // is based on GV, return the conservative result.
     875        3129 :   for (auto &A : CS.args()) {
     876        3806 :     SmallVector<Value*, 4> Objects;
     877        2375 :     GetUnderlyingObjects(A, Objects, DL);
     878             : 
     879             :     // All objects must be identified.
     880        3513 :     if (!all_of(Objects, isIdentifiedObject) &&
     881             :         // Try ::alias to see if all objects are known not to alias GV.
     882        3436 :         !all_of(Objects, [&](Value *V) {
     883        4640 :           return this->alias(MemoryLocation(V), MemoryLocation(GV)) == NoAlias;
     884        2320 :         }))
     885         944 :       return ConservativeResult;
     886             : 
     887        1431 :     if (is_contained(Objects, GV))
     888             :       return ConservativeResult;
     889             :   }
     890             : 
     891             :   // We identified all objects in the argument list, and none of them were GV.
     892             :   return MRI_NoModRef;
     893             : }
     894             : 
     895     3967864 : ModRefInfo GlobalsAAResult::getModRefInfo(ImmutableCallSite CS,
     896             :                                           const MemoryLocation &Loc) {
     897     3967864 :   unsigned Known = MRI_ModRef;
     898             : 
     899             :   // If we are asking for mod/ref info of a direct call with a pointer to a
     900             :   // global we are tracking, return information if we have it.
     901             :   if (const GlobalValue *GV =
     902    11216720 :           dyn_cast<GlobalValue>(GetUnderlyingObject(Loc.Ptr, DL)))
     903             :     if (GV->hasLocalLinkage())
     904     3253126 :       if (const Function *F = CS.getCalledFunction())
     905     3253126 :         if (NonAddressTakenGlobals.count(GV))
     906        2958 :           if (const FunctionInfo *FI = getFunctionInfo(F))
     907        3416 :             Known = FI->getModRefInfoForGlobal(*GV) |
     908        1708 :               getModRefInfoForArgument(CS, GV);
     909             : 
     910      688580 :   if (Known == MRI_NoModRef)
     911             :     return MRI_NoModRef; // No need to query other mod/ref analyses
     912     3967117 :   return ModRefInfo(Known & AAResultBase::getModRefInfo(CS, Loc));
     913             : }
     914             : 
     915        2079 : GlobalsAAResult::GlobalsAAResult(const DataLayout &DL,
     916        2079 :                                  const TargetLibraryInfo &TLI)
     917       14553 :     : AAResultBase(), DL(DL), TLI(TLI) {}
     918             : 
     919         158 : GlobalsAAResult::GlobalsAAResult(GlobalsAAResult &&Arg)
     920         474 :     : AAResultBase(std::move(Arg)), DL(Arg.DL), TLI(Arg.TLI),
     921         158 :       NonAddressTakenGlobals(std::move(Arg.NonAddressTakenGlobals)),
     922         158 :       IndirectGlobals(std::move(Arg.IndirectGlobals)),
     923         158 :       AllocsForIndirectGlobals(std::move(Arg.AllocsForIndirectGlobals)),
     924         158 :       FunctionInfos(std::move(Arg.FunctionInfos)),
     925        1738 :       Handles(std::move(Arg.Handles)) {
     926             :   // Update the parent for each DeletionCallbackHandle.
     927         522 :   for (auto &H : Handles) {
     928             :     assert(H.GAR == &Arg);
     929          48 :     H.GAR = this;
     930             :   }
     931         158 : }
     932             : 
     933       15659 : GlobalsAAResult::~GlobalsAAResult() {}
     934             : 
     935             : /*static*/ GlobalsAAResult
     936        2079 : GlobalsAAResult::analyzeModule(Module &M, const TargetLibraryInfo &TLI,
     937             :                                CallGraph &CG) {
     938        2079 :   GlobalsAAResult Result(M.getDataLayout(), TLI);
     939             : 
     940             :   // Discover which functions aren't recursive, to feed into AnalyzeGlobals.
     941        2079 :   Result.CollectSCCMembership(CG);
     942             : 
     943             :   // Find non-addr taken globals.
     944        2079 :   Result.AnalyzeGlobals(M);
     945             : 
     946             :   // Propagate on CG.
     947        2079 :   Result.AnalyzeCallGraph(CG, M);
     948             : 
     949        2079 :   return Result;
     950             : }
     951             : 
     952             : AnalysisKey GlobalsAA::Key;
     953             : 
     954          79 : GlobalsAAResult GlobalsAA::run(Module &M, ModuleAnalysisManager &AM) {
     955             :   return GlobalsAAResult::analyzeModule(M,
     956          79 :                                         AM.getResult<TargetLibraryAnalysis>(M),
     957         158 :                                         AM.getResult<CallGraphAnalysis>(M));
     958             : }
     959             : 
     960             : char GlobalsAAWrapperPass::ID = 0;
     961       53265 : INITIALIZE_PASS_BEGIN(GlobalsAAWrapperPass, "globals-aa",
     962             :                       "Globals Alias Analysis", false, true)
     963       53265 : INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
     964       53265 : INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
     965     1978209 : INITIALIZE_PASS_END(GlobalsAAWrapperPass, "globals-aa",
     966             :                     "Globals Alias Analysis", false, true)
     967             : 
     968        1971 : ModulePass *llvm::createGlobalsAAWrapperPass() {
     969        1971 :   return new GlobalsAAWrapperPass();
     970             : }
     971             : 
     972        5997 : GlobalsAAWrapperPass::GlobalsAAWrapperPass() : ModulePass(ID) {
     973        1999 :   initializeGlobalsAAWrapperPassPass(*PassRegistry::getPassRegistry());
     974        1999 : }
     975             : 
     976        1999 : bool GlobalsAAWrapperPass::runOnModule(Module &M) {
     977        9995 :   Result.reset(new GlobalsAAResult(GlobalsAAResult::analyzeModule(
     978        1999 :       M, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
     979        3998 :       getAnalysis<CallGraphWrapperPass>().getCallGraph())));
     980        1999 :   return false;
     981             : }
     982             : 
     983        1999 : bool GlobalsAAWrapperPass::doFinalization(Module &M) {
     984        3998 :   Result.reset();
     985        1999 :   return false;
     986             : }
     987             : 
     988        1999 : void GlobalsAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
     989        3998 :   AU.setPreservesAll();
     990        1999 :   AU.addRequired<CallGraphWrapperPass>();
     991        1999 :   AU.addRequired<TargetLibraryInfoWrapperPass>();
     992      218917 : }

Generated by: LCOV version 1.13