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