LLVM 17.0.0git
AliasSetTracker.h
Go to the documentation of this file.
1//===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines two classes: AliasSetTracker and AliasSet. These interfaces
10// are used to classify a collection of pointer references into a maximal number
11// of disjoint sets. Each AliasSet object constructed by the AliasSetTracker
12// object refers to memory disjoint from the other sets.
13//
14// An AliasSetTracker can only be used on immutable IR.
15//
16//===----------------------------------------------------------------------===//
17
18#ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H
19#define LLVM_ANALYSIS_ALIASSETTRACKER_H
20
21#include "llvm/ADT/DenseMap.h"
23#include "llvm/ADT/ilist.h"
24#include "llvm/ADT/ilist_node.h"
26#include "llvm/IR/Instruction.h"
27#include "llvm/IR/PassManager.h"
28#include "llvm/IR/ValueHandle.h"
29#include <cassert>
30#include <cstddef>
31#include <iterator>
32#include <vector>
33
34namespace llvm {
35
36class AliasResult;
37class AliasSetTracker;
38class AnyMemSetInst;
39class AnyMemTransferInst;
40class BasicBlock;
41class BatchAAResults;
42class LoadInst;
43enum class ModRefInfo : uint8_t;
44class raw_ostream;
45class StoreInst;
46class VAArgInst;
47class Value;
48
49class AliasSet : public ilist_node<AliasSet> {
50 friend class AliasSetTracker;
51
52 class PointerRec {
53 Value *Val; // The pointer this record corresponds to.
54 PointerRec **PrevInList = nullptr;
55 PointerRec *NextInList = nullptr;
56 AliasSet *AS = nullptr;
58 AAMDNodes AAInfo;
59
60 // Whether the size for this record has been set at all. This makes no
61 // guarantees about the size being known.
62 bool isSizeSet() const { return Size != LocationSize::mapEmpty(); }
63
64 public:
65 PointerRec(Value *V)
66 : Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {}
67
68 Value *getValue() const { return Val; }
69
70 PointerRec *getNext() const { return NextInList; }
71 bool hasAliasSet() const { return AS != nullptr; }
72
73 PointerRec** setPrevInList(PointerRec **PIL) {
74 PrevInList = PIL;
75 return &NextInList;
76 }
77
78 bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) {
79 bool SizeChanged = false;
80 if (NewSize != Size) {
81 LocationSize OldSize = Size;
82 Size = isSizeSet() ? Size.unionWith(NewSize) : NewSize;
83 SizeChanged = OldSize != Size;
84 }
85
86 if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
87 // We don't have a AAInfo yet. Set it to NewAAInfo.
88 AAInfo = NewAAInfo;
89 else {
90 AAMDNodes Intersection(AAInfo.intersect(NewAAInfo));
91 SizeChanged |= Intersection != AAInfo;
92 AAInfo = Intersection;
93 }
94 return SizeChanged;
95 }
96
97 LocationSize getSize() const {
98 assert(isSizeSet() && "Getting an unset size!");
99 return Size;
100 }
101
102 /// Return the AAInfo, or null if there is no information or conflicting
103 /// information.
104 AAMDNodes getAAInfo() const {
105 // If we have missing or conflicting AAInfo, return null.
106 if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() ||
107 AAInfo == DenseMapInfo<AAMDNodes>::getTombstoneKey())
108 return AAMDNodes();
109 return AAInfo;
110 }
111
112 AliasSet *getAliasSet(AliasSetTracker &AST) {
113 assert(AS && "No AliasSet yet!");
114 if (AS->Forward) {
115 AliasSet *OldAS = AS;
116 AS = OldAS->getForwardedTarget(AST);
117 AS->addRef();
118 OldAS->dropRef(AST);
119 }
120 return AS;
121 }
122
123 void setAliasSet(AliasSet *as) {
124 assert(!AS && "Already have an alias set!");
125 AS = as;
126 }
127
128 void eraseFromList() {
129 if (NextInList) NextInList->PrevInList = PrevInList;
130 *PrevInList = NextInList;
131 if (AS->PtrListEnd == &NextInList) {
132 AS->PtrListEnd = PrevInList;
133 assert(*AS->PtrListEnd == nullptr && "List not terminated right!");
134 }
135 delete this;
136 }
137 };
138
139 // Doubly linked list of nodes.
140 PointerRec *PtrList = nullptr;
141 PointerRec **PtrListEnd;
142 // Forwarding pointer.
143 AliasSet *Forward = nullptr;
144
145 /// All instructions without a specific address in this alias set.
146 std::vector<AssertingVH<Instruction>> UnknownInsts;
147
148 /// Number of nodes pointing to this AliasSet plus the number of AliasSets
149 /// forwarding to it.
150 unsigned RefCount : 27;
151
152 // Signifies that this set should be considered to alias any pointer.
153 // Use when the tracker holding this set is saturated.
154 unsigned AliasAny : 1;
155
156 /// The kinds of access this alias set models.
157 ///
158 /// We keep track of whether this alias set merely refers to the locations of
159 /// memory (and not any particular access), whether it modifies or references
160 /// the memory, or whether it does both. The lattice goes from "NoAccess" to
161 /// either RefAccess or ModAccess, then to ModRefAccess as necessary.
162 enum AccessLattice {
163 NoAccess = 0,
164 RefAccess = 1,
165 ModAccess = 2,
166 ModRefAccess = RefAccess | ModAccess
167 };
168 unsigned Access : 2;
169
170 /// The kind of alias relationship between pointers of the set.
171 ///
172 /// These represent conservatively correct alias results between any members
173 /// of the set. We represent these independently of the values of alias
174 /// results in order to pack it into a single bit. Lattice goes from
175 /// MustAlias to MayAlias.
176 enum AliasLattice {
177 SetMustAlias = 0, SetMayAlias = 1
178 };
179 unsigned Alias : 1;
180
181 unsigned SetSize = 0;
182
183 void addRef() { ++RefCount; }
184
185 void dropRef(AliasSetTracker &AST) {
186 assert(RefCount >= 1 && "Invalid reference count detected!");
187 if (--RefCount == 0)
188 removeFromTracker(AST);
189 }
190
191public:
192 AliasSet(const AliasSet &) = delete;
193 AliasSet &operator=(const AliasSet &) = delete;
194
195 /// Accessors...
196 bool isRef() const { return Access & RefAccess; }
197 bool isMod() const { return Access & ModAccess; }
198 bool isMustAlias() const { return Alias == SetMustAlias; }
199 bool isMayAlias() const { return Alias == SetMayAlias; }
200
201 /// Return true if this alias set should be ignored as part of the
202 /// AliasSetTracker object.
203 bool isForwardingAliasSet() const { return Forward; }
204
205 /// Merge the specified alias set into this alias set.
206 void mergeSetIn(AliasSet &AS, AliasSetTracker &AST, BatchAAResults &BatchAA);
207
208 // Alias Set iteration - Allow access to all of the pointers which are part of
209 // this alias set.
210 class iterator;
211 iterator begin() const { return iterator(PtrList); }
212 iterator end() const { return iterator(); }
213 bool empty() const { return PtrList == nullptr; }
214
215 // Unfortunately, ilist::size() is linear, so we have to add code to keep
216 // track of the list's exact size.
217 unsigned size() { return SetSize; }
218
219 void print(raw_ostream &OS) const;
220 void dump() const;
221
222 /// Define an iterator for alias sets... this is just a forward iterator.
223 class iterator {
224 PointerRec *CurNode;
225
226 public:
227 using iterator_category = std::forward_iterator_tag;
228 using value_type = PointerRec;
229 using difference_type = std::ptrdiff_t;
232
233 explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {}
234
235 bool operator==(const iterator& x) const {
236 return CurNode == x.CurNode;
237 }
238 bool operator!=(const iterator& x) const { return !operator==(x); }
239
241 assert(CurNode && "Dereferencing AliasSet.end()!");
242 return *CurNode;
243 }
244 value_type *operator->() const { return &operator*(); }
245
246 Value *getPointer() const { return CurNode->getValue(); }
247 LocationSize getSize() const { return CurNode->getSize(); }
248 AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); }
249
250 iterator& operator++() { // Preincrement
251 assert(CurNode && "Advancing past AliasSet.end()!");
252 CurNode = CurNode->getNext();
253 return *this;
254 }
255 iterator operator++(int) { // Postincrement
256 iterator tmp = *this; ++*this; return tmp;
257 }
258 };
259
260private:
261 // Can only be created by AliasSetTracker.
262 AliasSet()
263 : PtrListEnd(&PtrList), RefCount(0), AliasAny(false), Access(NoAccess),
264 Alias(SetMustAlias) {}
265
266 PointerRec *getSomePointer() const {
267 return PtrList;
268 }
269
270 /// Return the real alias set this represents. If this has been merged with
271 /// another set and is forwarding, return the ultimate destination set. This
272 /// also implements the union-find collapsing as well.
273 AliasSet *getForwardedTarget(AliasSetTracker &AST) {
274 if (!Forward) return this;
275
276 AliasSet *Dest = Forward->getForwardedTarget(AST);
277 if (Dest != Forward) {
278 Dest->addRef();
279 Forward->dropRef(AST);
280 Forward = Dest;
281 }
282 return Dest;
283 }
284
285 void removeFromTracker(AliasSetTracker &AST);
286
287 void addPointer(AliasSetTracker &AST, PointerRec &Entry, LocationSize Size,
288 const AAMDNodes &AAInfo, bool KnownMustAlias = false,
289 bool SkipSizeUpdate = false);
290 void addUnknownInst(Instruction *I, BatchAAResults &AA);
291
292public:
293 /// If the specified pointer "may" (or must) alias one of the members in the
294 /// set return the appropriate AliasResult. Otherwise return NoAlias.
295 AliasResult aliasesPointer(const Value *Ptr, LocationSize Size,
296 const AAMDNodes &AAInfo, BatchAAResults &AA) const;
297 ModRefInfo aliasesUnknownInst(const Instruction *Inst,
298 BatchAAResults &AA) const;
299};
300
302 AS.print(OS);
303 return OS;
304}
305
307 BatchAAResults &AA;
308 ilist<AliasSet> AliasSets;
309
310 using PointerMapType = DenseMap<AssertingVH<Value>, AliasSet::PointerRec *>;
311
312 // Map from pointers to their node
313 PointerMapType PointerMap;
314
315public:
316 /// Create an empty collection of AliasSets, and use the specified alias
317 /// analysis object to disambiguate load and store addresses.
318 explicit AliasSetTracker(BatchAAResults &AA) : AA(AA) {}
320
321 /// These methods are used to add different types of instructions to the alias
322 /// sets. Adding a new instruction can result in one of three actions
323 /// happening:
324 ///
325 /// 1. If the instruction doesn't alias any other sets, create a new set.
326 /// 2. If the instruction aliases exactly one set, add it to the set
327 /// 3. If the instruction aliases multiple sets, merge the sets, and add
328 /// the instruction to the result.
329 ///
330 /// These methods return true if inserting the instruction resulted in the
331 /// addition of a new alias set (i.e., the pointer did not alias anything).
332 ///
333 void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo); // Add a loc
334 void add(LoadInst *LI);
335 void add(StoreInst *SI);
336 void add(VAArgInst *VAAI);
337 void add(AnyMemSetInst *MSI);
338 void add(AnyMemTransferInst *MTI);
339 void add(Instruction *I); // Dispatch to one of the other add methods...
340 void add(BasicBlock &BB); // Add all instructions in basic block
341 void add(const AliasSetTracker &AST); // Add alias relations from another AST
342 void addUnknown(Instruction *I);
343
344 void clear();
345
346 /// Return the alias sets that are active.
347 const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
348
349 /// Return the alias set which contains the specified memory location. If
350 /// the memory location aliases two or more existing alias sets, will have
351 /// the effect of merging those alias sets before the single resulting alias
352 /// set is returned.
353 AliasSet &getAliasSetFor(const MemoryLocation &MemLoc);
354
355 /// Return the underlying alias analysis object used by this tracker.
356 BatchAAResults &getAliasAnalysis() const { return AA; }
357
360
361 const_iterator begin() const { return AliasSets.begin(); }
362 const_iterator end() const { return AliasSets.end(); }
363
364 iterator begin() { return AliasSets.begin(); }
365 iterator end() { return AliasSets.end(); }
366
367 void print(raw_ostream &OS) const;
368 void dump() const;
369
370private:
371 friend class AliasSet;
372
373 // The total number of pointers contained in all "may" alias sets.
374 unsigned TotalMayAliasSetSize = 0;
375
376 // A non-null value signifies this AST is saturated. A saturated AST lumps
377 // all pointers into a single "May" set.
378 AliasSet *AliasAnyAS = nullptr;
379
380 void removeAliasSet(AliasSet *AS);
381
382 /// Just like operator[] on the map, except that it creates an entry for the
383 /// pointer if it doesn't already exist.
384 AliasSet::PointerRec &getEntryFor(Value *V) {
385 AliasSet::PointerRec *&Entry = PointerMap[V];
386 if (!Entry)
387 Entry = new AliasSet::PointerRec(V);
388 return *Entry;
389 }
390
391 AliasSet &addPointer(MemoryLocation Loc, AliasSet::AccessLattice E);
392 AliasSet *mergeAliasSetsForPointer(const Value *Ptr, LocationSize Size,
393 const AAMDNodes &AAInfo,
394 bool &MustAliasAll);
395
396 /// Merge all alias sets into a single set that is considered to alias any
397 /// pointer.
398 AliasSet &mergeAllAliasSets();
399
400 AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
401};
402
404 AST.print(OS);
405 return OS;
406}
407
408class AliasSetsPrinterPass : public PassInfoMixin<AliasSetsPrinterPass> {
409 raw_ostream &OS;
410
411public:
414};
415
416} // end namespace llvm
417
418#endif // LLVM_ANALYSIS_ALIASSETTRACKER_H
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
uint64_t Size
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file provides utility analysis objects describing memory locations.
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
const ilist< AliasSet > & getAliasSets() const
Return the alias sets that are active.
BatchAAResults & getAliasAnalysis() const
Return the underlying alias analysis object used by this tracker.
AliasSet & getAliasSetFor(const MemoryLocation &MemLoc)
Return the alias set which contains the specified memory location.
void addUnknown(Instruction *I)
AliasSetTracker(BatchAAResults &AA)
Create an empty collection of AliasSets, and use the specified alias analysis object to disambiguate ...
const_iterator end() const
const_iterator begin() const
void print(raw_ostream &OS) const
void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo)
These methods are used to add different types of instructions to the alias sets.
Define an iterator for alias sets... this is just a forward iterator.
value_type * operator->() const
iterator(PointerRec *CN=nullptr)
std::forward_iterator_tag iterator_category
AAMDNodes getAAInfo() const
Value * getPointer() const
value_type & operator*() const
bool operator==(const iterator &x) const
LocationSize getSize() const
std::ptrdiff_t difference_type
bool operator!=(const iterator &x) const
iterator begin() const
void mergeSetIn(AliasSet &AS, AliasSetTracker &AST, BatchAAResults &BatchAA)
Merge the specified alias set into this alias set.
void print(raw_ostream &OS) const
AliasSet(const AliasSet &)=delete
iterator end() const
bool isMayAlias() const
bool isForwardingAliasSet() const
Return true if this alias set should be ignored as part of the AliasSetTracker object.
bool empty() const
AliasSet & operator=(const AliasSet &)=delete
ModRefInfo aliasesUnknownInst(const Instruction *Inst, BatchAAResults &AA) const
AliasResult aliasesPointer(const Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo, BatchAAResults &AA) const
If the specified pointer "may" (or must) alias one of the members in the set return the appropriate A...
bool isMustAlias() const
friend class AliasSetTracker
bool isMod() const
bool isRef() const
Accessors...
void dump() const
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
This class represents any memset intrinsic.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
An instruction for reading from memory.
Definition: Instructions.h:177
static constexpr LocationSize mapEmpty()
Representation for a specific memory location.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
An instruction for storing to memory.
Definition: Instructions.h:301
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
LLVM Value Representation.
Definition: Value.h:74
Iterator for intrusive lists based on ilist_node.
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
Definition: ilist.h:328
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This file defines classes to implement an intrusive doubly linked list class (i.e.
This file defines the ilist_node class template, which is a convenient base class for creating classe...
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: ModRef.h:27
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:651
AAMDNodes intersect(const AAMDNodes &Other) const
Given two sets of AAMDNodes that apply to the same pointer, give the best AAMDNodes that are compatib...
Definition: Metadata.h:694
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:51
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371