/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Analysis/GlobalsModRef.cpp
Line | Count | Source (jump to first uncovered line) |
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 | | struct LLVM_ALIGNAS(8) AlignedMap { |
69 | 38.8k | AlignedMap() {} |
70 | 2.26k | AlignedMap(const AlignedMap &Arg) : Map(Arg.Map) {} |
71 | | GlobalInfoMapType Map; |
72 | | }; |
73 | | |
74 | | /// Pointer traits for our aligned map. |
75 | | struct AlignedMapPointerTraits { |
76 | 278k | static inline void *getAsVoidPointer(AlignedMap *P) { return P; } |
77 | 11.2M | static inline AlignedMap *getFromVoidPointer(void *P) { |
78 | 11.2M | return (AlignedMap *)P; |
79 | 11.2M | } |
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 | 614k | FunctionInfo() : Info() {} |
98 | 806k | ~FunctionInfo() { |
99 | 806k | delete Info.getPointer(); |
100 | 806k | } |
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 | | FunctionInfo(const FunctionInfo &Arg) |
105 | 146k | : Info(nullptr, Arg.Info.getInt()) { |
106 | 146k | if (const auto *ArgPtr = Arg.Info.getPointer()) |
107 | 2.26k | Info.setPointer(new AlignedMap(*ArgPtr)); |
108 | 146k | } |
109 | | FunctionInfo(FunctionInfo &&Arg) |
110 | 45.2k | : Info(Arg.Info.getPointer(), Arg.Info.getInt()) { |
111 | 45.2k | Arg.Info.setPointerAndInt(nullptr, 0); |
112 | 45.2k | } |
113 | 28 | FunctionInfo &operator=(const FunctionInfo &RHS) { |
114 | 28 | delete Info.getPointer(); |
115 | 28 | Info.setPointerAndInt(nullptr, RHS.Info.getInt()); |
116 | 28 | if (const auto *RHSPtr = RHS.Info.getPointer()) |
117 | 0 | Info.setPointer(new AlignedMap(*RHSPtr)); |
118 | 28 | return *this; |
119 | 28 | } |
120 | 0 | FunctionInfo &operator=(FunctionInfo &&RHS) { |
121 | 0 | delete Info.getPointer(); |
122 | 0 | Info.setPointerAndInt(RHS.Info.getPointer(), RHS.Info.getInt()); |
123 | 0 | RHS.Info.setPointerAndInt(nullptr, 0); |
124 | 0 | return *this; |
125 | 0 | } |
126 | | |
127 | | /// Returns the \c ModRefInfo info for this function. |
128 | 12.6M | ModRefInfo getModRefInfo() const { |
129 | 12.6M | return ModRefInfo(Info.getInt() & MRI_ModRef); |
130 | 12.6M | } |
131 | | |
132 | | /// Adds new \c ModRefInfo for this function to its state. |
133 | 608k | void addModRefInfo(ModRefInfo NewMRI) { |
134 | 608k | Info.setInt(Info.getInt() | NewMRI); |
135 | 608k | } |
136 | | |
137 | | /// Returns whether this function may read any global variable, and we don't |
138 | | /// know which global. |
139 | 139k | bool mayReadAnyGlobal() const { return Info.getInt() & MayReadAnyGlobal; } |
140 | | |
141 | | /// Sets this function as potentially reading from any global. |
142 | 32.8k | 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 | 38.4k | ModRefInfo getModRefInfoForGlobal(const GlobalValue &GV) const { |
147 | 38.4k | ModRefInfo GlobalMRI = mayReadAnyGlobal() ? MRI_Ref8.67k : MRI_NoModRef29.7k ; |
148 | 38.4k | if (AlignedMap *P38.4k = Info.getPointer()) { |
149 | 2.19k | auto I = P->Map.find(&GV); |
150 | 2.19k | if (I != P->Map.end()) |
151 | 1.03k | GlobalMRI = ModRefInfo(GlobalMRI | I->second); |
152 | 2.19k | } |
153 | 38.4k | return GlobalMRI; |
154 | 38.4k | } |
155 | | |
156 | | /// Add mod/ref info from another function into ours, saturating towards |
157 | | /// MRI_ModRef. |
158 | 101k | void addFunctionInfo(const FunctionInfo &FI) { |
159 | 101k | addModRefInfo(FI.getModRefInfo()); |
160 | 101k | |
161 | 101k | if (FI.mayReadAnyGlobal()) |
162 | 13.1k | setMayReadAnyGlobal(); |
163 | 101k | |
164 | 101k | if (AlignedMap *P = FI.Info.getPointer()) |
165 | 1.39k | for (const auto &G : P->Map) |
166 | 2.91k | addModRefInfoForGlobal(*G.first, G.second); |
167 | 101k | } |
168 | | |
169 | 67.4k | void addModRefInfoForGlobal(const GlobalValue &GV, ModRefInfo NewMRI) { |
170 | 67.4k | AlignedMap *P = Info.getPointer(); |
171 | 67.4k | if (!P67.4k ) { |
172 | 38.8k | P = new AlignedMap(); |
173 | 38.8k | Info.setPointer(P); |
174 | 38.8k | } |
175 | 67.4k | auto &GlobalMRI = P->Map[&GV]; |
176 | 67.4k | GlobalMRI = ModRefInfo(GlobalMRI | NewMRI); |
177 | 67.4k | } |
178 | | |
179 | | /// Clear a global's ModRef info. Should be used when a global is being |
180 | | /// deleted. |
181 | 10.0M | void eraseModRefInfoForGlobal(const GlobalValue &GV) { |
182 | 10.0M | if (AlignedMap *P = Info.getPointer()) |
183 | 57.4k | P->Map.erase(&GV); |
184 | 10.0M | } |
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 | 30.6k | void GlobalsAAResult::DeletionCallbackHandle::deleted() { |
196 | 30.6k | Value *V = getValPtr(); |
197 | 30.6k | if (auto *F = dyn_cast<Function>(V)) |
198 | 23.0k | GAR->FunctionInfos.erase(F); |
199 | 30.6k | |
200 | 30.6k | if (GlobalValue *GV30.6k = dyn_cast<GlobalValue>(V)) { |
201 | 30.6k | if (GAR->NonAddressTakenGlobals.erase(GV)30.6k ) { |
202 | 30.6k | // This global might be an indirect global. If so, remove it and |
203 | 30.6k | // remove any AllocRelatedValues for it. |
204 | 30.6k | if (GAR->IndirectGlobals.erase(GV)30.6k ) { |
205 | 0 | // 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 != E0 ; ++I0 ) |
209 | 0 | if (0 I->second == GV0 ) |
210 | 0 | GAR->AllocsForIndirectGlobals.erase(I); |
211 | 0 | } |
212 | 30.6k | |
213 | 30.6k | // Scan the function info we have collected and remove this global |
214 | 30.6k | // from all of them. |
215 | 30.6k | for (auto &FIPair : GAR->FunctionInfos) |
216 | 10.0M | FIPair.second.eraseModRefInfoForGlobal(*GV); |
217 | 30.6k | } |
218 | 30.6k | } |
219 | 30.6k | |
220 | 30.6k | // If this is an allocation related to an indirect global, remove it. |
221 | 30.6k | GAR->AllocsForIndirectGlobals.erase(V); |
222 | 30.6k | |
223 | 30.6k | // And clear out the handle. |
224 | 30.6k | setValPtr(nullptr); |
225 | 30.6k | GAR->Handles.erase(I); |
226 | 30.6k | // This object is now destroyed! |
227 | 30.6k | } |
228 | | |
229 | 21.7M | FunctionModRefBehavior GlobalsAAResult::getModRefBehavior(const Function *F) { |
230 | 21.7M | FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; |
231 | 21.7M | |
232 | 21.7M | if (FunctionInfo *FI21.7M = getFunctionInfo(F)) { |
233 | 2.91M | if (FI->getModRefInfo() == MRI_NoModRef) |
234 | 16.2k | Min = FMRB_DoesNotAccessMemory; |
235 | 2.89M | else if (2.89M (FI->getModRefInfo() & MRI_Mod) == 02.89M ) |
236 | 547k | Min = FMRB_OnlyReadsMemory; |
237 | 2.91M | } |
238 | 21.7M | |
239 | 21.7M | return FunctionModRefBehavior(AAResultBase::getModRefBehavior(F) & Min); |
240 | 21.7M | } |
241 | | |
242 | | FunctionModRefBehavior |
243 | 22.0M | GlobalsAAResult::getModRefBehavior(ImmutableCallSite CS) { |
244 | 22.0M | FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior; |
245 | 22.0M | |
246 | 22.0M | if (!CS.hasOperandBundles()) |
247 | 22.0M | if (const Function *22.0M F22.0M = CS.getCalledFunction()) |
248 | 20.9M | if (FunctionInfo *20.9M FI20.9M = getFunctionInfo(F)) { |
249 | 2.84M | if (FI->getModRefInfo() == MRI_NoModRef) |
250 | 6 | Min = FMRB_DoesNotAccessMemory; |
251 | 2.84M | else if (2.84M (FI->getModRefInfo() & MRI_Mod) == 02.84M ) |
252 | 527k | Min = FMRB_OnlyReadsMemory; |
253 | 22.0M | } |
254 | 22.0M | |
255 | 22.0M | return FunctionModRefBehavior(AAResultBase::getModRefBehavior(CS) & Min); |
256 | 22.0M | } |
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 | 43.0M | GlobalsAAResult::getFunctionInfo(const Function *F) { |
262 | 43.0M | auto I = FunctionInfos.find(F); |
263 | 43.0M | if (I != FunctionInfos.end()) |
264 | 5.89M | return &I->second; |
265 | 37.1M | return nullptr; |
266 | 37.1M | } |
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 | 34.8k | void GlobalsAAResult::AnalyzeGlobals(Module &M) { |
273 | 34.8k | SmallPtrSet<Function *, 32> TrackedFunctions; |
274 | 34.8k | for (Function &F : M) |
275 | 1.40M | if (1.40M F.hasLocalLinkage()1.40M ) |
276 | 34.0k | if (34.0k !AnalyzeUsesOfPointer(&F)34.0k ) { |
277 | 28.1k | // Remember that we are tracking this global. |
278 | 28.1k | NonAddressTakenGlobals.insert(&F); |
279 | 28.1k | TrackedFunctions.insert(&F); |
280 | 28.1k | Handles.emplace_front(*this, &F); |
281 | 28.1k | Handles.front().I = Handles.begin(); |
282 | 28.1k | ++NumNonAddrTakenFunctions; |
283 | 28.1k | } |
284 | 34.8k | |
285 | 34.8k | SmallPtrSet<Function *, 16> Readers, Writers; |
286 | 34.8k | for (GlobalVariable &GV : M.globals()) |
287 | 1.53M | if (1.53M GV.hasLocalLinkage()1.53M ) { |
288 | 1.28M | if (!AnalyzeUsesOfPointer(&GV, &Readers, |
289 | 1.28M | GV.isConstant() ? nullptr1.23M : &Writers49.5k )) { |
290 | 34.3k | // Remember that we are tracking this global, and the mod/ref fns |
291 | 34.3k | NonAddressTakenGlobals.insert(&GV); |
292 | 34.3k | Handles.emplace_front(*this, &GV); |
293 | 34.3k | Handles.front().I = Handles.begin(); |
294 | 34.3k | |
295 | 34.2k | for (Function *Reader : Readers) { |
296 | 34.2k | if (TrackedFunctions.insert(Reader).second34.2k ) { |
297 | 22.8k | Handles.emplace_front(*this, Reader); |
298 | 22.8k | Handles.front().I = Handles.begin(); |
299 | 22.8k | } |
300 | 34.2k | FunctionInfos[Reader].addModRefInfoForGlobal(GV, MRI_Ref); |
301 | 34.2k | } |
302 | 34.3k | |
303 | 34.3k | if (!GV.isConstant()) // No need to keep track of writers to constants |
304 | 13.9k | for (Function *Writer : Writers) 13.9k { |
305 | 30.2k | if (TrackedFunctions.insert(Writer).second30.2k ) { |
306 | 14.1k | Handles.emplace_front(*this, Writer); |
307 | 14.1k | Handles.front().I = Handles.begin(); |
308 | 14.1k | } |
309 | 13.9k | FunctionInfos[Writer].addModRefInfoForGlobal(GV, MRI_Mod); |
310 | 13.9k | } |
311 | 34.3k | ++NumNonAddrTakenGlobalVars; |
312 | 34.3k | |
313 | 34.3k | // If this global holds a pointer type, see if it is an indirect global. |
314 | 34.3k | if (GV.getValueType()->isPointerTy() && |
315 | 3.92k | AnalyzeIndirectGlobalMemory(&GV)) |
316 | 3 | ++NumIndirectGlobalVars; |
317 | 34.3k | } |
318 | 1.53M | Readers.clear(); |
319 | 1.53M | Writers.clear(); |
320 | 1.53M | } |
321 | 34.8k | } |
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 | | bool GlobalsAAResult::AnalyzeUsesOfPointer(Value *V, |
330 | | SmallPtrSetImpl<Function *> *Readers, |
331 | | SmallPtrSetImpl<Function *> *Writers, |
332 | 2.61M | GlobalValue *OkayStoreDest) { |
333 | 2.61M | if (!V->getType()->isPointerTy()) |
334 | 0 | return true; |
335 | 2.61M | |
336 | 2.61M | for (Use &U : V->uses()) 2.61M { |
337 | 2.88M | User *I = U.getUser(); |
338 | 2.88M | if (LoadInst *LI2.88M = dyn_cast<LoadInst>(I)) { |
339 | 87.4k | if (Readers) |
340 | 83.9k | Readers->insert(LI->getParent()->getParent()); |
341 | 2.88M | } else if (StoreInst *2.79M SI2.79M = dyn_cast<StoreInst>(I)) { |
342 | 80.6k | if (V == SI->getOperand(1)80.6k ) { |
343 | 77.4k | if (Writers) |
344 | 76.4k | Writers->insert(SI->getParent()->getParent()); |
345 | 80.6k | } else if (3.23k SI->getOperand(1) != OkayStoreDest3.23k ) { |
346 | 3.22k | return true; // Storing the pointer |
347 | 3.22k | } |
348 | 2.71M | } else if (2.71M Operator::getOpcode(I) == Instruction::GetElementPtr2.71M ) { |
349 | 1.26M | if (AnalyzeUsesOfPointer(I, Readers, Writers)) |
350 | 1.19M | return true; |
351 | 1.45M | } else if (1.45M Operator::getOpcode(I) == Instruction::BitCast1.45M ) { |
352 | 32.1k | if (AnalyzeUsesOfPointer(I, Readers, Writers, OkayStoreDest)) |
353 | 27.3k | return true; |
354 | 1.41M | } else if (auto 1.41M CS1.41M = CallSite(I)) { |
355 | 1.22M | // Make sure that this is just the function being called, not that it is |
356 | 1.22M | // passing into the function. |
357 | 1.22M | if (CS.isDataOperand(&U)1.22M ) { |
358 | 1.05M | // Detect calls to free. |
359 | 1.05M | if (CS.isArgOperand(&U) && 1.05M isFreeCall(I, &TLI)1.05M ) { |
360 | 66 | if (Writers) |
361 | 0 | Writers->insert(CS->getParent()->getParent()); |
362 | 1.05M | } else { |
363 | 1.05M | return true; // Argument of an unknown call. |
364 | 1.05M | } |
365 | 1.41M | } |
366 | 196k | } else if (ICmpInst *196k ICI196k = dyn_cast<ICmpInst>(I)) { |
367 | 270 | if (!isa<ConstantPointerNull>(ICI->getOperand(1))) |
368 | 82 | return true; // Allow comparison against null. |
369 | 195k | } else if (Constant *195k C195k = dyn_cast<Constant>(I)) { |
370 | 133k | // Ignore constants which don't have any live uses. |
371 | 133k | if (isa<GlobalValue>(C) || 133k C->isConstantUsed()131k ) |
372 | 133k | return true; |
373 | 62.8k | } else { |
374 | 62.8k | return true; |
375 | 62.8k | } |
376 | 137k | } |
377 | 137k | |
378 | 137k | return false; |
379 | 137k | } |
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 | 3.92k | bool GlobalsAAResult::AnalyzeIndirectGlobalMemory(GlobalVariable *GV) { |
389 | 3.92k | // Keep track of values related to the allocation of the memory, f.e. the |
390 | 3.92k | // value produced by the malloc call and any casts. |
391 | 3.92k | std::vector<Value *> AllocRelatedValues; |
392 | 3.92k | |
393 | 3.92k | // If the initializer is a valid pointer, bail. |
394 | 3.92k | if (Constant *C = GV->getInitializer()) |
395 | 3.92k | if (3.92k !C->isNullValue()3.92k ) |
396 | 62 | return false; |
397 | 3.86k | |
398 | 3.86k | // Walk the user list of the global. If we find anything other than a direct |
399 | 3.86k | // load or store, bail out. |
400 | 3.86k | for (User *U : GV->users()) 3.86k { |
401 | 7.22k | if (LoadInst *LI7.22k = dyn_cast<LoadInst>(U)) { |
402 | 5.05k | // The pointer loaded from the global can only be used in simple ways: |
403 | 5.05k | // we allow addressing of it and loading storing to it. We do *not* allow |
404 | 5.05k | // storing the loaded pointer somewhere else or passing to a function. |
405 | 5.05k | if (AnalyzeUsesOfPointer(LI)) |
406 | 1.84k | return false; // Loaded pointer escapes. |
407 | 7.22k | // TODO: Could try some IP mod/ref of the loaded pointer. |
408 | 2.17k | } else if (StoreInst *2.17k SI2.17k = dyn_cast<StoreInst>(U)) { |
409 | 1.24k | // Storing the global itself. |
410 | 1.24k | if (SI->getOperand(0) == GV) |
411 | 0 | return false; |
412 | 1.24k | |
413 | 1.24k | // If storing the null pointer, ignore it. |
414 | 1.24k | if (1.24k isa<ConstantPointerNull>(SI->getOperand(0))1.24k ) |
415 | 151 | continue; |
416 | 1.09k | |
417 | 1.09k | // Check the value being stored. |
418 | 1.09k | Value *Ptr = GetUnderlyingObject(SI->getOperand(0), |
419 | 1.09k | GV->getParent()->getDataLayout()); |
420 | 1.09k | |
421 | 1.09k | if (!isAllocLikeFn(Ptr, &TLI)) |
422 | 1.05k | return false; // Too hard to analyze. |
423 | 36 | |
424 | 36 | // Analyze all uses of the allocation. If any of them are used in a |
425 | 36 | // non-simple way (e.g. stored to another global) bail out. |
426 | 36 | if (36 AnalyzeUsesOfPointer(Ptr, /*Readers*/ nullptr, /*Writers*/ nullptr, |
427 | 36 | GV)) |
428 | 24 | return false; // Loaded pointer escapes. |
429 | 12 | |
430 | 12 | // Remember that this allocation is related to the indirect global. |
431 | 12 | AllocRelatedValues.push_back(Ptr); |
432 | 2.17k | } else { |
433 | 934 | // Something complex, bail out. |
434 | 934 | return false; |
435 | 934 | } |
436 | 3 | } |
437 | 3 | |
438 | 3 | // Okay, this is an indirect global. Remember all of the allocations for |
439 | 3 | // this global in AllocsForIndirectGlobals. |
440 | 5 | while (3 !AllocRelatedValues.empty()5 ) { |
441 | 2 | AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV; |
442 | 2 | Handles.emplace_front(*this, AllocRelatedValues.back()); |
443 | 2 | Handles.front().I = Handles.begin(); |
444 | 2 | AllocRelatedValues.pop_back(); |
445 | 2 | } |
446 | 3.92k | IndirectGlobals.insert(GV); |
447 | 3.92k | Handles.emplace_front(*this, GV); |
448 | 3.92k | Handles.front().I = Handles.begin(); |
449 | 3.92k | return true; |
450 | 3.92k | } |
451 | | |
452 | 34.8k | void GlobalsAAResult::CollectSCCMembership(CallGraph &CG) { |
453 | 34.8k | // We do a bottom-up SCC traversal of the call graph. In other words, we |
454 | 34.8k | // visit all callees before callers (leaf-first). |
455 | 34.8k | unsigned SCCID = 0; |
456 | 1.49M | for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd()1.49M ; ++I1.46M ) { |
457 | 1.46M | const std::vector<CallGraphNode *> &SCC = *I; |
458 | 1.46M | assert(!SCC.empty() && "SCC with no functions?"); |
459 | 1.46M | |
460 | 1.46M | for (auto *CGN : SCC) |
461 | 1.46M | if (Function *1.46M F1.46M = CGN->getFunction()) |
462 | 1.40M | FunctionToSCCMap[F] = SCCID; |
463 | 1.46M | ++SCCID; |
464 | 1.46M | } |
465 | 34.8k | } |
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 | 34.8k | void GlobalsAAResult::AnalyzeCallGraph(CallGraph &CG, Module &M) { |
472 | 34.8k | // We do a bottom-up SCC traversal of the call graph. In other words, we |
473 | 34.8k | // visit all callees before callers (leaf-first). |
474 | 1.49M | for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd()1.49M ; ++I1.46M ) { |
475 | 1.46M | const std::vector<CallGraphNode *> &SCC = *I; |
476 | 1.46M | assert(!SCC.empty() && "SCC with no functions?"); |
477 | 1.46M | |
478 | 1.46M | Function *F = SCC[0]->getFunction(); |
479 | 1.46M | |
480 | 1.46M | if (!F || 1.46M !F->isDefinitionExact()1.40M ) { |
481 | 866k | // Calls externally or not exact - can't say anything useful. Remove any |
482 | 866k | // existing function records (may have been created when scanning |
483 | 866k | // globals). |
484 | 866k | for (auto *Node : SCC) |
485 | 866k | FunctionInfos.erase(Node->getFunction()); |
486 | 866k | continue; |
487 | 866k | } |
488 | 597k | |
489 | 597k | FunctionInfo &FI = FunctionInfos[F]; |
490 | 597k | bool KnowNothing = false; |
491 | 597k | |
492 | 597k | // Collect the mod/ref properties due to called functions. We only compute |
493 | 597k | // one mod-ref set. |
494 | 1.19M | for (unsigned i = 0, e = SCC.size(); i != e && 1.19M !KnowNothing598k ; ++i597k ) { |
495 | 597k | if (!F597k ) { |
496 | 0 | KnowNothing = true; |
497 | 0 | break; |
498 | 0 | } |
499 | 597k | |
500 | 597k | if (597k F->isDeclaration() || 597k F->hasFnAttribute(Attribute::OptimizeNone)175k ) { |
501 | 422k | // Try to get mod/ref behaviour from function attributes. |
502 | 422k | if (F->doesNotAccessMemory()422k ) { |
503 | 18.9k | // Can't do better than that! |
504 | 422k | } else if (403k F->onlyReadsMemory()403k ) { |
505 | 27.2k | FI.addModRefInfo(MRI_Ref); |
506 | 27.2k | if (!F->isIntrinsic() && 27.2k !F->onlyAccessesArgMemory()26.4k ) |
507 | 27.2k | // This function might call back into the module and read a global - |
508 | 27.2k | // consider every global as possibly being read by this function. |
509 | 19.7k | FI.setMayReadAnyGlobal(); |
510 | 403k | } else { |
511 | 376k | FI.addModRefInfo(MRI_ModRef); |
512 | 376k | // Can't say anything useful unless it's an intrinsic - they don't |
513 | 376k | // read or write global variables of the kind considered here. |
514 | 376k | KnowNothing = !F->isIntrinsic(); |
515 | 376k | } |
516 | 422k | continue; |
517 | 422k | } |
518 | 175k | |
519 | 175k | for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end(); |
520 | 390k | CI != E && 390k !KnowNothing297k ; ++CI215k ) |
521 | 215k | if (Function *215k Callee215k = CI->second->getFunction()) { |
522 | 208k | if (FunctionInfo *CalleeFI208k = getFunctionInfo(Callee)) { |
523 | 101k | // Propagate function effect up. |
524 | 101k | FI.addFunctionInfo(*CalleeFI); |
525 | 208k | } else { |
526 | 107k | // Can't say anything about it. However, if it is inside our SCC, |
527 | 107k | // then nothing needs to be done. |
528 | 107k | CallGraphNode *CalleeNode = CG[Callee]; |
529 | 107k | if (!is_contained(SCC, CalleeNode)) |
530 | 107k | KnowNothing = true; |
531 | 107k | } |
532 | 215k | } else { |
533 | 6.51k | KnowNothing = true; |
534 | 6.51k | } |
535 | 597k | } |
536 | 597k | |
537 | 597k | // If we can't say anything useful about this SCC, remove all SCC functions |
538 | 597k | // from the FunctionInfos map. |
539 | 597k | if (KnowNothing597k ) { |
540 | 451k | for (auto *Node : SCC) |
541 | 451k | FunctionInfos.erase(Node->getFunction()); |
542 | 451k | continue; |
543 | 451k | } |
544 | 146k | |
545 | 146k | // Scan the function bodies for explicit loads or stores. |
546 | 146k | for (auto *Node : SCC) 146k { |
547 | 146k | if (FI.getModRefInfo() == MRI_ModRef) |
548 | 42.3k | break; // The mod/ref lattice saturates here. |
549 | 104k | |
550 | 104k | // Don't prove any properties based on the implementation of an optnone |
551 | 104k | // function. Function attributes were already used as a best approximation |
552 | 104k | // above. |
553 | 104k | if (104k Node->getFunction()->hasFnAttribute(Attribute::OptimizeNone)104k ) |
554 | 2 | continue; |
555 | 104k | |
556 | 104k | for (Instruction &I : instructions(Node->getFunction())) 104k { |
557 | 647k | if (FI.getModRefInfo() == MRI_ModRef) |
558 | 17.2k | break; // The mod/ref lattice saturates here. |
559 | 630k | |
560 | 630k | // We handle calls specially because the graph-relevant aspects are |
561 | 630k | // handled above. |
562 | 630k | if (auto 630k CS630k = CallSite(&I)) { |
563 | 16.6k | if (isAllocationFn(&I, &TLI) || 16.6k isFreeCall(&I, &TLI)16.6k ) { |
564 | 0 | // FIXME: It is completely unclear why this is necessary and not |
565 | 0 | // handled by the above graph code. |
566 | 0 | FI.addModRefInfo(MRI_ModRef); |
567 | 16.6k | } else if (Function *16.6k Callee16.6k = CS.getCalledFunction()) { |
568 | 16.6k | // The callgraph doesn't include intrinsic calls. |
569 | 16.6k | if (Callee->isIntrinsic()16.6k ) { |
570 | 6.50k | FunctionModRefBehavior Behaviour = |
571 | 6.50k | AAResultBase::getModRefBehavior(Callee); |
572 | 6.50k | FI.addModRefInfo(ModRefInfo(Behaviour & MRI_ModRef)); |
573 | 6.50k | } |
574 | 16.6k | } |
575 | 16.6k | continue; |
576 | 16.6k | } |
577 | 613k | |
578 | 613k | // All non-call instructions we use the primary predicates for whether |
579 | 613k | // thay read or write memory. |
580 | 613k | if (613k I.mayReadFromMemory()613k ) |
581 | 68.6k | FI.addModRefInfo(MRI_Ref); |
582 | 613k | if (I.mayWriteToMemory()) |
583 | 28.0k | FI.addModRefInfo(MRI_Mod); |
584 | 647k | } |
585 | 146k | } |
586 | 146k | |
587 | 146k | if ((FI.getModRefInfo() & MRI_Mod) == 0) |
588 | 82.8k | ++NumReadMemFunctions; |
589 | 146k | if (FI.getModRefInfo() == MRI_NoModRef) |
590 | 46.4k | ++NumNoMemFunctions; |
591 | 146k | |
592 | 146k | // Finally, now that we know the full effect on this SCC, clone the |
593 | 146k | // information to each function in the SCC. |
594 | 146k | // FI is a reference into FunctionInfos, so copy it now so that it doesn't |
595 | 146k | // get invalidated if DenseMap decides to re-hash. |
596 | 146k | FunctionInfo CachedFI = FI; |
597 | 146k | for (unsigned i = 1, e = SCC.size(); i != e146k ; ++i28 ) |
598 | 28 | FunctionInfos[SCC[i]->getFunction()] = CachedFI; |
599 | 1.46M | } |
600 | 34.8k | } |
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 | | static bool isNonEscapingGlobalNoAliasWithLoad(const GlobalValue *GV, |
606 | | const Value *V, |
607 | | int &Depth, |
608 | 452k | const DataLayout &DL) { |
609 | 452k | SmallPtrSet<const Value *, 8> Visited; |
610 | 452k | SmallVector<const Value *, 8> Inputs; |
611 | 452k | Visited.insert(V); |
612 | 452k | Inputs.push_back(V); |
613 | 741k | do { |
614 | 741k | const Value *Input = Inputs.pop_back_val(); |
615 | 741k | |
616 | 741k | if (isa<GlobalValue>(Input) || 741k isa<Argument>(Input)439k || isa<CallInst>(Input)354k || |
617 | 345k | isa<InvokeInst>(Input)) |
618 | 741k | // Arguments to functions or returns from functions are inherently |
619 | 741k | // escaping, so we can immediately classify those as not aliasing any |
620 | 741k | // non-addr-taken globals. |
621 | 741k | // |
622 | 741k | // (Transitive) loads from a global are also safe - if this aliased |
623 | 741k | // another global, its address would escape, so no alias. |
624 | 395k | continue; |
625 | 345k | |
626 | 345k | // Recurse through a limited number of selects, loads and PHIs. This is an |
627 | 345k | // arbitrary depth of 4, lower numbers could be used to fix compile time |
628 | 345k | // issues if needed, but this is generally expected to be only be important |
629 | 345k | // for small depths. |
630 | 345k | if (345k ++Depth > 4345k ) |
631 | 54.7k | return false; |
632 | 291k | |
633 | 291k | if (auto *291k LI291k = dyn_cast<LoadInst>(Input)) { |
634 | 206k | Inputs.push_back(GetUnderlyingObject(LI->getPointerOperand(), DL)); |
635 | 206k | continue; |
636 | 206k | } |
637 | 85.0k | if (auto *85.0k SI85.0k = dyn_cast<SelectInst>(Input)) { |
638 | 638 | const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), DL); |
639 | 638 | const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), DL); |
640 | 638 | if (Visited.insert(LHS).second) |
641 | 638 | Inputs.push_back(LHS); |
642 | 638 | if (Visited.insert(RHS).second) |
643 | 402 | Inputs.push_back(RHS); |
644 | 638 | continue; |
645 | 638 | } |
646 | 84.4k | if (auto *84.4k PN84.4k = dyn_cast<PHINode>(Input)) { |
647 | 188k | for (const Value *Op : PN->incoming_values()) { |
648 | 188k | Op = GetUnderlyingObject(Op, DL); |
649 | 188k | if (Visited.insert(Op).second) |
650 | 110k | Inputs.push_back(Op); |
651 | 188k | } |
652 | 71.7k | continue; |
653 | 71.7k | } |
654 | 12.6k | |
655 | 12.6k | return false; |
656 | 673k | } while (!Inputs.empty()); |
657 | 452k | |
658 | 452k | // All inputs were known to be no-alias. |
659 | 385k | return true; |
660 | 452k | } |
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 | | bool GlobalsAAResult::isNonEscapingGlobalNoAlias(const GlobalValue *GV, |
688 | 908k | const Value *V) { |
689 | 908k | // In order to know that the underlying object cannot alias the |
690 | 908k | // non-addr-taken global, we must know that it would have to be an escape. |
691 | 908k | // Thus if the underlying object is a function argument, a load from |
692 | 908k | // a global, or the return of a function, it cannot alias. We can also |
693 | 908k | // recurse through PHI nodes and select nodes provided all of their inputs |
694 | 908k | // resolve to one of these known-escaping roots. |
695 | 908k | SmallPtrSet<const Value *, 8> Visited; |
696 | 908k | SmallVector<const Value *, 8> Inputs; |
697 | 908k | Visited.insert(V); |
698 | 908k | Inputs.push_back(V); |
699 | 908k | int Depth = 0; |
700 | 1.40M | do { |
701 | 1.40M | const Value *Input = Inputs.pop_back_val(); |
702 | 1.40M | |
703 | 1.40M | if (auto *InputGV1.40M = dyn_cast<GlobalValue>(Input)) { |
704 | 10.3k | // If one input is the very global we're querying against, then we can't |
705 | 10.3k | // conclude no-alias. |
706 | 10.3k | if (InputGV == GV) |
707 | 200 | return false; |
708 | 10.1k | |
709 | 10.1k | // Distinct GlobalVariables never alias, unless overriden or zero-sized. |
710 | 10.1k | // FIXME: The condition can be refined, but be conservative for now. |
711 | 10.1k | auto *GVar = dyn_cast<GlobalVariable>(GV); |
712 | 10.1k | auto *InputGVar = dyn_cast<GlobalVariable>(InputGV); |
713 | 10.1k | if (GVar && 10.1k InputGVar10.1k && |
714 | 10.1k | !GVar->isDeclaration()10.1k && !InputGVar->isDeclaration()10.1k && |
715 | 10.1k | !GVar->isInterposable()10.0k && !InputGVar->isInterposable()10.0k ) { |
716 | 9.82k | Type *GVType = GVar->getInitializer()->getType(); |
717 | 9.82k | Type *InputGVType = InputGVar->getInitializer()->getType(); |
718 | 9.82k | if (GVType->isSized() && 9.82k InputGVType->isSized()9.82k && |
719 | 9.82k | (DL.getTypeAllocSize(GVType) > 0) && |
720 | 9.82k | (DL.getTypeAllocSize(InputGVType) > 0)) |
721 | 9.82k | continue; |
722 | 344 | } |
723 | 344 | |
724 | 344 | // Conservatively return false, even though we could be smarter |
725 | 344 | // (e.g. look through GlobalAliases). |
726 | 344 | return false; |
727 | 344 | } |
728 | 1.39M | |
729 | 1.39M | if (1.39M isa<Argument>(Input) || 1.39M isa<CallInst>(Input)1.23M || |
730 | 1.39M | isa<InvokeInst>(Input)1.19M ) { |
731 | 200k | // Arguments to functions or returns from functions are inherently |
732 | 200k | // escaping, so we can immediately classify those as not aliasing any |
733 | 200k | // non-addr-taken globals. |
734 | 200k | continue; |
735 | 200k | } |
736 | 1.19M | |
737 | 1.19M | // Recurse through a limited number of selects, loads and PHIs. This is an |
738 | 1.19M | // arbitrary depth of 4, lower numbers could be used to fix compile time |
739 | 1.19M | // issues if needed, but this is generally expected to be only be important |
740 | 1.19M | // for small depths. |
741 | 1.19M | if (1.19M ++Depth > 41.19M ) |
742 | 28.0k | return false; |
743 | 1.16M | |
744 | 1.16M | if (auto *1.16M LI1.16M = dyn_cast<LoadInst>(Input)) { |
745 | 452k | // A pointer loaded from a global would have been captured, and we know |
746 | 452k | // that the global is non-escaping, so no alias. |
747 | 452k | const Value *Ptr = GetUnderlyingObject(LI->getPointerOperand(), DL); |
748 | 452k | if (isNonEscapingGlobalNoAliasWithLoad(GV, Ptr, Depth, DL)) |
749 | 452k | // The load does not alias with GV. |
750 | 385k | continue; |
751 | 67.3k | // Otherwise, a load could come from anywhere, so bail. |
752 | 67.3k | return false; |
753 | 67.3k | } |
754 | 709k | if (auto *709k SI709k = dyn_cast<SelectInst>(Input)) { |
755 | 3.94k | const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), DL); |
756 | 3.94k | const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), DL); |
757 | 3.94k | if (Visited.insert(LHS).second) |
758 | 3.21k | Inputs.push_back(LHS); |
759 | 3.94k | if (Visited.insert(RHS).second) |
760 | 3.03k | Inputs.push_back(RHS); |
761 | 3.94k | continue; |
762 | 3.94k | } |
763 | 705k | if (auto *705k PN705k = dyn_cast<PHINode>(Input)) { |
764 | 1.17M | for (const Value *Op : PN->incoming_values()) { |
765 | 1.17M | Op = GetUnderlyingObject(Op, DL); |
766 | 1.17M | if (Visited.insert(Op).second) |
767 | 548k | Inputs.push_back(Op); |
768 | 1.17M | } |
769 | 453k | continue; |
770 | 453k | } |
771 | 252k | |
772 | 252k | // FIXME: It would be good to handle other obvious no-alias cases here, but |
773 | 252k | // it isn't clear how to do so reasonbly without building a small version |
774 | 252k | // of BasicAA into this code. We could recurse into AAResultBase::alias |
775 | 252k | // here but that seems likely to go poorly as we're inside the |
776 | 252k | // implementation of such a query. Until then, just conservatievly retun |
777 | 252k | // false. |
778 | 252k | return false; |
779 | 1.05M | } while (!Inputs.empty()); |
780 | 908k | |
781 | 908k | // If all the inputs to V were definitively no-alias, then V is no-alias. |
782 | 559k | return true; |
783 | 908k | } |
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 | | AliasResult GlobalsAAResult::alias(const MemoryLocation &LocA, |
789 | 45.5M | const MemoryLocation &LocB) { |
790 | 45.5M | // Get the base object these pointers point to. |
791 | 45.5M | const Value *UV1 = GetUnderlyingObject(LocA.Ptr, DL); |
792 | 45.5M | const Value *UV2 = GetUnderlyingObject(LocB.Ptr, DL); |
793 | 45.5M | |
794 | 45.5M | // If either of the underlying values is a global, they may be non-addr-taken |
795 | 45.5M | // globals, which we can answer queries about. |
796 | 45.5M | const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1); |
797 | 45.5M | const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2); |
798 | 45.5M | if (GV1 || 45.5M GV240.8M ) { |
799 | 7.62M | // If the global's address is taken, pretend we don't know it's a pointer to |
800 | 7.62M | // the global. |
801 | 7.62M | if (GV1 && 7.62M !NonAddressTakenGlobals.count(GV1)4.62M ) |
802 | 4.00M | GV1 = nullptr; |
803 | 7.62M | if (GV2 && 7.62M !NonAddressTakenGlobals.count(GV2)3.33M ) |
804 | 2.96M | GV2 = nullptr; |
805 | 7.62M | |
806 | 7.62M | // If the two pointers are derived from two different non-addr-taken |
807 | 7.62M | // globals we know these can't alias. |
808 | 7.62M | if (GV1 && 7.62M GV2618k && GV1 != GV239.0k ) |
809 | 0 | return NoAlias; |
810 | 7.62M | |
811 | 7.62M | // If one is and the other isn't, it isn't strictly safe but we can fake |
812 | 7.62M | // this result if necessary for performance. This does not appear to be |
813 | 7.62M | // a common problem in practice. |
814 | 7.62M | if (7.62M EnableUnsafeGlobalsModRefAliasResults7.62M ) |
815 | 4 | if (4 (GV1 || 4 GV20 ) && GV1 != GV24 ) |
816 | 4 | return NoAlias; |
817 | 7.62M | |
818 | 7.62M | // Check for a special case where a non-escaping global can be used to |
819 | 7.62M | // conclude no-alias. |
820 | 7.62M | if (7.62M (GV1 || 7.62M GV27.00M ) && GV1 != GV2947k ) { |
821 | 908k | const GlobalValue *GV = GV1 ? GV1579k : GV2329k ; |
822 | 908k | const Value *UV = GV1 ? UV2579k : UV1329k ; |
823 | 908k | if (isNonEscapingGlobalNoAlias(GV, UV)) |
824 | 559k | return NoAlias; |
825 | 44.9M | } |
826 | 7.62M | |
827 | 7.62M | // Otherwise if they are both derived from the same addr-taken global, we |
828 | 7.62M | // can't know the two accesses don't overlap. |
829 | 7.62M | } |
830 | 44.9M | |
831 | 44.9M | // These pointers may be based on the memory owned by an indirect global. If |
832 | 44.9M | // so, we may be able to handle this. First check to see if the base pointer |
833 | 44.9M | // is a direct load from an indirect global. |
834 | 44.9M | GV1 = GV2 = nullptr; |
835 | 44.9M | if (const LoadInst *LI = dyn_cast<LoadInst>(UV1)) |
836 | 16.7M | if (GlobalVariable *16.7M GV16.7M = dyn_cast<GlobalVariable>(LI->getOperand(0))) |
837 | 1.58M | if (1.58M IndirectGlobals.count(GV)1.58M ) |
838 | 0 | GV1 = GV; |
839 | 44.9M | if (const LoadInst *LI = dyn_cast<LoadInst>(UV2)) |
840 | 22.0M | if (const GlobalVariable *22.0M GV22.0M = dyn_cast<GlobalVariable>(LI->getOperand(0))) |
841 | 1.71M | if (1.71M IndirectGlobals.count(GV)1.71M ) |
842 | 2 | GV2 = GV; |
843 | 44.9M | |
844 | 44.9M | // These pointers may also be from an allocation for the indirect global. If |
845 | 44.9M | // so, also handle them. |
846 | 44.9M | if (!GV1) |
847 | 44.9M | GV1 = AllocsForIndirectGlobals.lookup(UV1); |
848 | 44.9M | if (!GV2) |
849 | 44.9M | GV2 = AllocsForIndirectGlobals.lookup(UV2); |
850 | 44.9M | |
851 | 44.9M | // Now that we know whether the two pointers are related to indirect globals, |
852 | 44.9M | // use this to disambiguate the pointers. If the pointers are based on |
853 | 44.9M | // different indirect globals they cannot alias. |
854 | 44.9M | if (GV1 && 44.9M GV20 && GV1 != GV20 ) |
855 | 0 | return NoAlias; |
856 | 44.9M | |
857 | 44.9M | // If one is based on an indirect global and the other isn't, it isn't |
858 | 44.9M | // strictly safe but we can fake this result if necessary for performance. |
859 | 44.9M | // This does not appear to be a common problem in practice. |
860 | 44.9M | if (44.9M EnableUnsafeGlobalsModRefAliasResults44.9M ) |
861 | 2 | if (2 (GV1 || 2 GV22 ) && GV1 != GV22 ) |
862 | 2 | return NoAlias; |
863 | 44.9M | |
864 | 44.9M | return AAResultBase::alias(LocA, LocB); |
865 | 44.9M | } |
866 | | |
867 | | ModRefInfo GlobalsAAResult::getModRefInfoForArgument(ImmutableCallSite CS, |
868 | 38.4k | const GlobalValue *GV) { |
869 | 38.4k | if (CS.doesNotAccessMemory()) |
870 | 3.05k | return MRI_NoModRef; |
871 | 35.3k | ModRefInfo ConservativeResult = CS.onlyReadsMemory() ? 35.3k MRI_Ref6.11k : MRI_ModRef29.2k ; |
872 | 35.3k | |
873 | 35.3k | // Iterate through all the arguments to the called function. If any argument |
874 | 35.3k | // is based on GV, return the conservative result. |
875 | 53.8k | for (auto &A : CS.args()) { |
876 | 53.8k | SmallVector<Value*, 4> Objects; |
877 | 53.8k | GetUnderlyingObjects(A, Objects, DL); |
878 | 53.8k | |
879 | 53.8k | // All objects must be identified. |
880 | 53.8k | if (!all_of(Objects, isIdentifiedObject) && |
881 | 53.8k | // Try ::alias to see if all objects are known not to alias GV. |
882 | 43.8k | !all_of(Objects, [&](Value *V) 43.8k { |
883 | 47.8k | return this->alias(MemoryLocation(V), MemoryLocation(GV)) == NoAlias; |
884 | 47.8k | })) |
885 | 23.5k | return ConservativeResult; |
886 | 30.2k | |
887 | 30.2k | if (30.2k is_contained(Objects, GV)30.2k ) |
888 | 0 | return ConservativeResult; |
889 | 11.7k | } |
890 | 11.7k | |
891 | 11.7k | // We identified all objects in the argument list, and none of them were GV. |
892 | 11.7k | return MRI_NoModRef; |
893 | 11.7k | } |
894 | | |
895 | | ModRefInfo GlobalsAAResult::getModRefInfo(ImmutableCallSite CS, |
896 | 8.45M | const MemoryLocation &Loc) { |
897 | 8.45M | unsigned Known = MRI_ModRef; |
898 | 8.45M | |
899 | 8.45M | // If we are asking for mod/ref info of a direct call with a pointer to a |
900 | 8.45M | // global we are tracking, return information if we have it. |
901 | 8.45M | if (const GlobalValue *GV = |
902 | 8.45M | dyn_cast<GlobalValue>(GetUnderlyingObject(Loc.Ptr, DL))) |
903 | 1.70M | if (1.70M GV->hasLocalLinkage()1.70M ) |
904 | 257k | if (const Function *257k F257k = CS.getCalledFunction()) |
905 | 245k | if (245k NonAddressTakenGlobals.count(GV)245k ) |
906 | 188k | if (const FunctionInfo *188k FI188k = getFunctionInfo(F)) |
907 | 38.4k | Known = FI->getModRefInfoForGlobal(*GV) | |
908 | 38.4k | getModRefInfoForArgument(CS, GV); |
909 | 8.45M | |
910 | 8.45M | if (Known == MRI_NoModRef) |
911 | 7.24k | return MRI_NoModRef; // No need to query other mod/ref analyses |
912 | 8.44M | return ModRefInfo(Known & AAResultBase::getModRefInfo(CS, Loc)); |
913 | 8.44M | } |
914 | | |
915 | | GlobalsAAResult::GlobalsAAResult(const DataLayout &DL, |
916 | | const TargetLibraryInfo &TLI) |
917 | 34.8k | : AAResultBase(), DL(DL), TLI(TLI) {} |
918 | | |
919 | | GlobalsAAResult::GlobalsAAResult(GlobalsAAResult &&Arg) |
920 | | : AAResultBase(std::move(Arg)), DL(Arg.DL), TLI(Arg.TLI), |
921 | | NonAddressTakenGlobals(std::move(Arg.NonAddressTakenGlobals)), |
922 | | IndirectGlobals(std::move(Arg.IndirectGlobals)), |
923 | | AllocsForIndirectGlobals(std::move(Arg.AllocsForIndirectGlobals)), |
924 | | FunctionInfos(std::move(Arg.FunctionInfos)), |
925 | 158 | Handles(std::move(Arg.Handles)) { |
926 | 158 | // Update the parent for each DeletionCallbackHandle. |
927 | 48 | for (auto &H : Handles) { |
928 | 48 | assert(H.GAR == &Arg); |
929 | 48 | H.GAR = this; |
930 | 48 | } |
931 | 158 | } |
932 | | |
933 | 34.9k | GlobalsAAResult::~GlobalsAAResult() {} |
934 | | |
935 | | /*static*/ GlobalsAAResult |
936 | | GlobalsAAResult::analyzeModule(Module &M, const TargetLibraryInfo &TLI, |
937 | 34.8k | CallGraph &CG) { |
938 | 34.8k | GlobalsAAResult Result(M.getDataLayout(), TLI); |
939 | 34.8k | |
940 | 34.8k | // Discover which functions aren't recursive, to feed into AnalyzeGlobals. |
941 | 34.8k | Result.CollectSCCMembership(CG); |
942 | 34.8k | |
943 | 34.8k | // Find non-addr taken globals. |
944 | 34.8k | Result.AnalyzeGlobals(M); |
945 | 34.8k | |
946 | 34.8k | // Propagate on CG. |
947 | 34.8k | Result.AnalyzeCallGraph(CG, M); |
948 | 34.8k | |
949 | 34.8k | return Result; |
950 | 34.8k | } |
951 | | |
952 | | AnalysisKey GlobalsAA::Key; |
953 | | |
954 | 79 | GlobalsAAResult GlobalsAA::run(Module &M, ModuleAnalysisManager &AM) { |
955 | 79 | return GlobalsAAResult::analyzeModule(M, |
956 | 79 | AM.getResult<TargetLibraryAnalysis>(M), |
957 | 79 | AM.getResult<CallGraphAnalysis>(M)); |
958 | 79 | } |
959 | | |
960 | | char GlobalsAAWrapperPass::ID = 0; |
961 | 90.2k | INITIALIZE_PASS_BEGIN90.2k (GlobalsAAWrapperPass, "globals-aa",
|
962 | 90.2k | "Globals Alias Analysis", false, true) |
963 | 90.2k | INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) |
964 | 90.2k | INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) |
965 | 90.2k | INITIALIZE_PASS_END(GlobalsAAWrapperPass, "globals-aa", |
966 | | "Globals Alias Analysis", false, true) |
967 | | |
968 | 34.7k | ModulePass *llvm::createGlobalsAAWrapperPass() { |
969 | 34.7k | return new GlobalsAAWrapperPass(); |
970 | 34.7k | } |
971 | | |
972 | 34.7k | GlobalsAAWrapperPass::GlobalsAAWrapperPass() : ModulePass(ID) { |
973 | 34.7k | initializeGlobalsAAWrapperPassPass(*PassRegistry::getPassRegistry()); |
974 | 34.7k | } |
975 | | |
976 | 34.7k | bool GlobalsAAWrapperPass::runOnModule(Module &M) { |
977 | 34.7k | Result.reset(new GlobalsAAResult(GlobalsAAResult::analyzeModule( |
978 | 34.7k | M, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(), |
979 | 34.7k | getAnalysis<CallGraphWrapperPass>().getCallGraph()))); |
980 | 34.7k | return false; |
981 | 34.7k | } |
982 | | |
983 | 34.7k | bool GlobalsAAWrapperPass::doFinalization(Module &M) { |
984 | 34.7k | Result.reset(); |
985 | 34.7k | return false; |
986 | 34.7k | } |
987 | | |
988 | 34.7k | void GlobalsAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { |
989 | 34.7k | AU.setPreservesAll(); |
990 | 34.7k | AU.addRequired<CallGraphWrapperPass>(); |
991 | 34.7k | AU.addRequired<TargetLibraryInfoWrapperPass>(); |
992 | 34.7k | } |