LLVM 19.0.0git
ScopedNoAliasAA.cpp
Go to the documentation of this file.
1//===- ScopedNoAliasAA.cpp - Scoped No-Alias Alias Analysis ---------------===//
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 file defines the ScopedNoAlias alias-analysis pass, which implements
10// metadata-based scoped no-alias support.
11//
12// Alias-analysis scopes are defined by an id (which can be a string or some
13// other metadata node), a domain node, and an optional descriptive string.
14// A domain is defined by an id (which can be a string or some other metadata
15// node), and an optional descriptive string.
16//
17// !dom0 = metadata !{ metadata !"domain of foo()" }
18// !scope1 = metadata !{ metadata !scope1, metadata !dom0, metadata !"scope 1" }
19// !scope2 = metadata !{ metadata !scope2, metadata !dom0, metadata !"scope 2" }
20//
21// Loads and stores can be tagged with an alias-analysis scope, and also, with
22// a noalias tag for a specific scope:
23//
24// ... = load %ptr1, !alias.scope !{ !scope1 }
25// ... = load %ptr2, !alias.scope !{ !scope1, !scope2 }, !noalias !{ !scope1 }
26//
27// When evaluating an aliasing query, if one of the instructions is associated
28// has a set of noalias scopes in some domain that is a superset of the alias
29// scopes in that domain of some other instruction, then the two memory
30// accesses are assumed not to alias.
31//
32//===----------------------------------------------------------------------===//
33
38#include "llvm/IR/InstrTypes.h"
39#include "llvm/IR/LLVMContext.h"
40#include "llvm/IR/Metadata.h"
42#include "llvm/Pass.h"
45
46using namespace llvm;
47
48// A handy option for disabling scoped no-alias functionality. The same effect
49// can also be achieved by stripping the associated metadata tags from IR, but
50// this option is sometimes more convenient.
51static cl::opt<bool> EnableScopedNoAlias("enable-scoped-noalias",
52 cl::init(true), cl::Hidden);
53
55 const MemoryLocation &LocB,
56 AAQueryInfo &AAQI,
57 const Instruction *) {
60
61 // Get the attached MDNodes.
62 const MDNode *AScopes = LocA.AATags.Scope, *BScopes = LocB.AATags.Scope;
63
64 const MDNode *ANoAlias = LocA.AATags.NoAlias, *BNoAlias = LocB.AATags.NoAlias;
65
66 if (!mayAliasInScopes(AScopes, BNoAlias))
68
69 if (!mayAliasInScopes(BScopes, ANoAlias))
71
73}
74
76 const MemoryLocation &Loc,
77 AAQueryInfo &AAQI) {
79 return ModRefInfo::ModRef;
80
81 if (!mayAliasInScopes(Loc.AATags.Scope,
82 Call->getMetadata(LLVMContext::MD_noalias)))
84
85 if (!mayAliasInScopes(Call->getMetadata(LLVMContext::MD_alias_scope),
86 Loc.AATags.NoAlias))
88
89 return ModRefInfo::ModRef;
90}
91
93 const CallBase *Call2,
94 AAQueryInfo &AAQI) {
96 return ModRefInfo::ModRef;
97
98 if (!mayAliasInScopes(Call1->getMetadata(LLVMContext::MD_alias_scope),
99 Call2->getMetadata(LLVMContext::MD_noalias)))
101
102 if (!mayAliasInScopes(Call2->getMetadata(LLVMContext::MD_alias_scope),
103 Call1->getMetadata(LLVMContext::MD_noalias)))
105
106 return ModRefInfo::ModRef;
107}
108
109static void collectMDInDomain(const MDNode *List, const MDNode *Domain,
111 for (const MDOperand &MDOp : List->operands())
112 if (const MDNode *MD = dyn_cast<MDNode>(MDOp))
113 if (AliasScopeNode(MD).getDomain() == Domain)
114 Nodes.insert(MD);
115}
116
117bool ScopedNoAliasAAResult::mayAliasInScopes(const MDNode *Scopes,
118 const MDNode *NoAlias) const {
119 if (!Scopes || !NoAlias)
120 return true;
121
122 // Collect the set of scope domains relevant to the noalias scopes.
124 for (const MDOperand &MDOp : NoAlias->operands())
125 if (const MDNode *NAMD = dyn_cast<MDNode>(MDOp))
126 if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain())
127 Domains.insert(Domain);
128
129 // We alias unless, for some domain, the set of noalias scopes in that domain
130 // is a superset of the set of alias scopes in that domain.
131 for (const MDNode *Domain : Domains) {
133 collectMDInDomain(Scopes, Domain, ScopeNodes);
134 if (ScopeNodes.empty())
135 continue;
136
138 collectMDInDomain(NoAlias, Domain, NANodes);
139
140 // To not alias, all of the nodes in ScopeNodes must be in NANodes.
141 if (llvm::set_is_subset(ScopeNodes, NANodes))
142 return false;
143 }
144
145 return true;
146}
147
148AnalysisKey ScopedNoAliasAA::Key;
149
152 return ScopedNoAliasAAResult();
153}
154
156
158 "Scoped NoAlias Alias Analysis", false, true)
159
161 return new ScopedNoAliasAAWrapperPass();
162}
163
166}
167
169 Result.reset(new ScopedNoAliasAAResult());
170 return false;
171}
172
174 Result.reset();
175 return false;
176}
177
179 AU.setPreservesAll();
180}
static Domain getDomain(const ConstantRange &CR)
#define F(x, y, z)
Definition: MD5.cpp:55
This file provides utility analysis objects describing memory locations.
This file contains the declarations for metadata subclasses.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
static void collectMDInDomain(const MDNode *List, const MDNode *Domain, SmallPtrSetImpl< const MDNode * > &Nodes)
static cl::opt< bool > EnableScopedNoAlias("enable-scoped-noalias", cl::init(true), cl::Hidden)
This is the interface for a metadata-based scoped no-alias analysis.
This file defines generic set operations that may be used on set's of different types,...
This file defines the SmallPtrSet class.
This class stores info we want to provide to or retain within an alias query.
The possible results of an alias query.
Definition: AliasAnalysis.h:81
@ MayAlias
The two locations may or may not alias.
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:99
This is a simple wrapper around an MDNode which provides a higher-level interface by hiding the detai...
Definition: Metadata.h:1565
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
Represent the analysis usage information of a pass.
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:1455
ImmutablePass class - This class is used to provide information that does not need to be run.
Definition: Pass.h:282
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:357
Metadata node.
Definition: Metadata.h:1067
ArrayRef< MDOperand > operands() const
Definition: Metadata.h:1426
Tracking metadata reference owned by Metadata.
Definition: Metadata.h:889
Representation for a specific memory location.
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A simple AA result which uses scoped-noalias metadata to answer queries.
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI, const Instruction *CtxI)
Legacy wrapper pass to provide the ScopedNoAliasAAResult object.
bool doInitialization(Module &M) override
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
bool doFinalization(Module &M) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
ScopedNoAliasAAResult run(Function &F, FunctionAnalysisManager &AM)
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:321
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:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void initializeScopedNoAliasAAWrapperPassPass(PassRegistry &)
ImmutablePass * createScopedNoAliasAAWrapperPass()
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: ModRef.h:27
@ ModRef
The access may reference and may modify the value stored in memory.
@ NoModRef
The access neither references nor modifies the value stored in memory.
MDNode * Scope
The tag for alias scope specification (used with noalias).
Definition: Metadata.h:783
MDNode * NoAlias
The tag specifying the noalias scope.
Definition: Metadata.h:786
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26