1 //===- GlobalsModRef.h - Simple Mod/Ref AA for Globals ----------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 /// This is the interface for a simple mod/ref and alias analysis over globals.
10 ///
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ANALYSIS_GLOBALSMODREF_H
14 #define LLVM_ANALYSIS_GLOBALSMODREF_H
15 
16 #include "llvm/Analysis/AliasAnalysis.h"
17 #include "llvm/IR/Constants.h"
18 #include "llvm/IR/Function.h"
19 #include "llvm/IR/Module.h"
20 #include "llvm/IR/ValueHandle.h"
21 #include "llvm/Pass.h"
22 #include <list>
23 
24 namespace llvm {
25 class CallGraph;
26 
27 /// An alias analysis result set for globals.
28 ///
29 /// This focuses on handling aliasing properties of globals and interprocedural
30 /// function call mod/ref information.
31 class GlobalsAAResult : public AAResultBase<GlobalsAAResult> {
32   friend AAResultBase<GlobalsAAResult>;
33 
34   class FunctionInfo;
35 
36   const DataLayout &DL;
37   std::function<const TargetLibraryInfo &(Function &F)> GetTLI;
38 
39   /// The globals that do not have their addresses taken.
40   SmallPtrSet<const GlobalValue *, 8> NonAddressTakenGlobals;
41 
42   /// Are there functions with local linkage that may modify globals.
43   bool UnknownFunctionsWithLocalLinkage = false;
44 
45   /// IndirectGlobals - The memory pointed to by this global is known to be
46   /// 'owned' by the global.
47   SmallPtrSet<const GlobalValue *, 8> IndirectGlobals;
48 
49   /// AllocsForIndirectGlobals - If an instruction allocates memory for an
50   /// indirect global, this map indicates which one.
51   DenseMap<const Value *, const GlobalValue *> AllocsForIndirectGlobals;
52 
53   /// For each function, keep track of what globals are modified or read.
54   DenseMap<const Function *, FunctionInfo> FunctionInfos;
55 
56   /// A map of functions to SCC. The SCCs are described by a simple integer
57   /// ID that is only useful for comparing for equality (are two functions
58   /// in the same SCC or not?)
59   DenseMap<const Function *, unsigned> FunctionToSCCMap;
60 
61   /// Handle to clear this analysis on deletion of values.
62   struct DeletionCallbackHandle final : CallbackVH {
63     GlobalsAAResult *GAR;
64     std::list<DeletionCallbackHandle>::iterator I;
65 
DeletionCallbackHandlefinal66     DeletionCallbackHandle(GlobalsAAResult &GAR, Value *V)
67         : CallbackVH(V), GAR(&GAR) {}
68 
69     void deleted() override;
70   };
71 
72   /// List of callbacks for globals being tracked by this analysis. Note that
73   /// these objects are quite large, but we only anticipate having one per
74   /// global tracked by this analysis. There are numerous optimizations we
75   /// could perform to the memory utilization here if this becomes a problem.
76   std::list<DeletionCallbackHandle> Handles;
77 
78   explicit GlobalsAAResult(
79       const DataLayout &DL,
80       std::function<const TargetLibraryInfo &(Function &F)> GetTLI);
81 
82 public:
83   GlobalsAAResult(GlobalsAAResult &&Arg);
84   ~GlobalsAAResult();
85 
86   bool invalidate(Module &M, const PreservedAnalyses &PA,
87                   ModuleAnalysisManager::Invalidator &);
88 
89   static GlobalsAAResult
90   analyzeModule(Module &M,
91                 std::function<const TargetLibraryInfo &(Function &F)> GetTLI,
92                 CallGraph &CG);
93 
94   //------------------------------------------------
95   // Implement the AliasAnalysis API
96   //
97   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
98                     AAQueryInfo &AAQI);
99 
100   using AAResultBase::getModRefInfo;
101   ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
102                            AAQueryInfo &AAQI);
103 
104   /// getModRefBehavior - Return the behavior of the specified function if
105   /// called from the specified call site.  The call site may be null in which
106   /// case the most generic behavior of this function should be returned.
107   FunctionModRefBehavior getModRefBehavior(const Function *F);
108 
109   /// getModRefBehavior - Return the behavior of the specified function if
110   /// called from the specified call site.  The call site may be null in which
111   /// case the most generic behavior of this function should be returned.
112   FunctionModRefBehavior getModRefBehavior(const CallBase *Call);
113 
114 private:
115   FunctionInfo *getFunctionInfo(const Function *F);
116 
117   void AnalyzeGlobals(Module &M);
118   void AnalyzeCallGraph(CallGraph &CG, Module &M);
119   bool AnalyzeUsesOfPointer(Value *V,
120                             SmallPtrSetImpl<Function *> *Readers = nullptr,
121                             SmallPtrSetImpl<Function *> *Writers = nullptr,
122                             GlobalValue *OkayStoreDest = nullptr);
123   bool AnalyzeIndirectGlobalMemory(GlobalVariable *GV);
124   void CollectSCCMembership(CallGraph &CG);
125 
126   bool isNonEscapingGlobalNoAlias(const GlobalValue *GV, const Value *V);
127   ModRefInfo getModRefInfoForArgument(const CallBase *Call,
128                                       const GlobalValue *GV, AAQueryInfo &AAQI);
129 };
130 
131 /// Analysis pass providing a never-invalidated alias analysis result.
132 class GlobalsAA : public AnalysisInfoMixin<GlobalsAA> {
133   friend AnalysisInfoMixin<GlobalsAA>;
134   static AnalysisKey Key;
135 
136 public:
137   typedef GlobalsAAResult Result;
138 
139   GlobalsAAResult run(Module &M, ModuleAnalysisManager &AM);
140 };
141 
142 /// Legacy wrapper pass to provide the GlobalsAAResult object.
143 class GlobalsAAWrapperPass : public ModulePass {
144   std::unique_ptr<GlobalsAAResult> Result;
145 
146 public:
147   static char ID;
148 
149   GlobalsAAWrapperPass();
150 
getResult()151   GlobalsAAResult &getResult() { return *Result; }
getResult()152   const GlobalsAAResult &getResult() const { return *Result; }
153 
154   bool runOnModule(Module &M) override;
155   bool doFinalization(Module &M) override;
156   void getAnalysisUsage(AnalysisUsage &AU) const override;
157 };
158 
159 //===--------------------------------------------------------------------===//
160 //
161 // createGlobalsAAWrapperPass - This pass provides alias and mod/ref info for
162 // global values that do not have their addresses taken.
163 //
164 ModulePass *createGlobalsAAWrapperPass();
165 }
166 
167 #endif
168