LLVM 19.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 memory locations 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 <vector>
31
32namespace llvm {
33
34class AliasResult;
35class AliasSetTracker;
36class AnyMemSetInst;
37class AnyMemTransferInst;
38class BasicBlock;
39class BatchAAResults;
40class LoadInst;
41enum class ModRefInfo : uint8_t;
42class raw_ostream;
43class StoreInst;
44class VAArgInst;
45class Value;
46
47class AliasSet : public ilist_node<AliasSet> {
48 friend class AliasSetTracker;
49
50 // Forwarding pointer.
51 AliasSet *Forward = nullptr;
52
53 /// Memory locations in this alias set.
55
56 /// All instructions without a specific address in this alias set.
57 std::vector<AssertingVH<Instruction>> UnknownInsts;
58
59 /// Number of nodes pointing to this AliasSet plus the number of AliasSets
60 /// forwarding to it.
61 unsigned RefCount : 27;
62
63 // Signifies that this set should be considered to alias any pointer.
64 // Use when the tracker holding this set is saturated.
65 unsigned AliasAny : 1;
66
67 /// The kinds of access this alias set models.
68 ///
69 /// We keep track of whether this alias set merely refers to the locations of
70 /// memory (and not any particular access), whether it modifies or references
71 /// the memory, or whether it does both. The lattice goes from "NoAccess" to
72 /// either RefAccess or ModAccess, then to ModRefAccess as necessary.
73 enum AccessLattice {
74 NoAccess = 0,
75 RefAccess = 1,
76 ModAccess = 2,
77 ModRefAccess = RefAccess | ModAccess
78 };
79 unsigned Access : 2;
80
81 /// The kind of alias relationship between pointers of the set.
82 ///
83 /// These represent conservatively correct alias results between any members
84 /// of the set. We represent these independently of the values of alias
85 /// results in order to pack it into a single bit. Lattice goes from
86 /// MustAlias to MayAlias.
87 enum AliasLattice {
88 SetMustAlias = 0, SetMayAlias = 1
89 };
90 unsigned Alias : 1;
91
92 void addRef() { ++RefCount; }
93
94 void dropRef(AliasSetTracker &AST) {
95 assert(RefCount >= 1 && "Invalid reference count detected!");
96 if (--RefCount == 0)
97 removeFromTracker(AST);
98 }
99
100public:
101 AliasSet(const AliasSet &) = delete;
102 AliasSet &operator=(const AliasSet &) = delete;
103
104 /// Accessors...
105 bool isRef() const { return Access & RefAccess; }
106 bool isMod() const { return Access & ModAccess; }
107 bool isMustAlias() const { return Alias == SetMustAlias; }
108 bool isMayAlias() const { return Alias == SetMayAlias; }
109
110 /// Return true if this alias set should be ignored as part of the
111 /// AliasSetTracker object.
112 bool isForwardingAliasSet() const { return Forward; }
113
114 /// Merge the specified alias set into this alias set.
115 void mergeSetIn(AliasSet &AS, AliasSetTracker &AST, BatchAAResults &BatchAA);
116
117 // Alias Set iteration - Allow access to all of the memory locations which are
118 // part of this alias set.
120 iterator begin() const { return MemoryLocs.begin(); }
121 iterator end() const { return MemoryLocs.end(); }
122
123 unsigned size() const { return MemoryLocs.size(); }
124
125 /// Retrieve the pointer values for the memory locations in this alias set.
126 /// The order matches that of the memory locations, but duplicate pointer
127 /// values are omitted.
130
131 void print(raw_ostream &OS) const;
132 void dump() const;
133
134private:
135 // Can only be created by AliasSetTracker.
136 AliasSet()
137 : RefCount(0), AliasAny(false), Access(NoAccess), Alias(SetMustAlias) {}
138
139 void removeFromTracker(AliasSetTracker &AST);
140
141 void addMemoryLocation(AliasSetTracker &AST, const MemoryLocation &MemLoc,
142 bool KnownMustAlias = false);
143 void addUnknownInst(Instruction *I, BatchAAResults &AA);
144
145public:
146 /// If the specified memory location "may" (or must) alias one of the members
147 /// in the set return the appropriate AliasResult. Otherwise return NoAlias.
149 BatchAAResults &AA) const;
150
152 BatchAAResults &AA) const;
153};
154
156 AS.print(OS);
157 return OS;
158}
159
161 BatchAAResults &AA;
162 ilist<AliasSet> AliasSets;
163
165
166 // Map from pointer values to the alias set holding one or more memory
167 // locations with that pointer value.
168 PointerMapType PointerMap;
169
170public:
171 /// Create an empty collection of AliasSets, and use the specified alias
172 /// analysis object to disambiguate load and store addresses.
173 explicit AliasSetTracker(BatchAAResults &AA) : AA(AA) {}
175
176 /// These methods are used to add different types of instructions to the alias
177 /// sets. Adding a new instruction can result in one of three actions
178 /// happening:
179 ///
180 /// 1. If the instruction doesn't alias any other sets, create a new set.
181 /// 2. If the instruction aliases exactly one set, add it to the set
182 /// 3. If the instruction aliases multiple sets, merge the sets, and add
183 /// the instruction to the result.
184 ///
185 void add(const MemoryLocation &Loc);
186 void add(LoadInst *LI);
187 void add(StoreInst *SI);
188 void add(VAArgInst *VAAI);
189 void add(AnyMemSetInst *MSI);
190 void add(AnyMemTransferInst *MTI);
191 void add(Instruction *I); // Dispatch to one of the other add methods...
192 void add(BasicBlock &BB); // Add all instructions in basic block
193 void add(const AliasSetTracker &AST); // Add alias relations from another AST
194 void addUnknown(Instruction *I);
195
196 void clear();
197
198 /// Return the alias sets that are active.
199 const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
200
201 /// Return the alias set which contains the specified memory location. If
202 /// the memory location aliases two or more existing alias sets, will have
203 /// the effect of merging those alias sets before the single resulting alias
204 /// set is returned.
205 AliasSet &getAliasSetFor(const MemoryLocation &MemLoc);
206
207 /// Return the underlying alias analysis object used by this tracker.
208 BatchAAResults &getAliasAnalysis() const { return AA; }
209
212
213 const_iterator begin() const { return AliasSets.begin(); }
214 const_iterator end() const { return AliasSets.end(); }
215
216 iterator begin() { return AliasSets.begin(); }
217 iterator end() { return AliasSets.end(); }
218
219 void print(raw_ostream &OS) const;
220 void dump() const;
221
222private:
223 friend class AliasSet;
224
225 // The total number of memory locations contained in all alias sets.
226 unsigned TotalAliasSetSize = 0;
227
228 // A non-null value signifies this AST is saturated. A saturated AST lumps
229 // all elements into a single "May" set.
230 AliasSet *AliasAnyAS = nullptr;
231
232 void removeAliasSet(AliasSet *AS);
233
234 // Update an alias set field to point to its real destination. If the field is
235 // pointing to a set that has been merged with another set and is forwarding,
236 // the field is updated to point to the set obtained by following the
237 // forwarding links. The Forward fields of intermediate alias sets are
238 // collapsed as well, and alias set reference counts are updated to reflect
239 // the new situation.
240 void collapseForwardingIn(AliasSet *&AS) {
241 if (AS->Forward) {
242 collapseForwardingIn(AS->Forward);
243 // Swap out AS for AS->Forward, while updating reference counts.
244 AliasSet *NewAS = AS->Forward;
245 NewAS->addRef();
246 AS->dropRef(*this);
247 AS = NewAS;
248 }
249 }
250
251 AliasSet &addMemoryLocation(MemoryLocation Loc, AliasSet::AccessLattice E);
252 AliasSet *mergeAliasSetsForMemoryLocation(const MemoryLocation &MemLoc,
253 AliasSet *PtrAS,
254 bool &MustAliasAll);
255
256 /// Merge all alias sets into a single set that is considered to alias
257 /// any memory location or instruction.
258 AliasSet &mergeAllAliasSets();
259
260 AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
261};
262
264 AST.print(OS);
265 return OS;
266}
267
268class AliasSetsPrinterPass : public PassInfoMixin<AliasSetsPrinterPass> {
269 raw_ostream &OS;
270
271public:
274 static bool isRequired() { return true; }
275};
276
277} // end namespace llvm
278
279#endif // LLVM_ANALYSIS_ALIASSETTRACKER_H
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
#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
This file defines the SmallVector class.
The possible results of an alias query.
Definition: AliasAnalysis.h:81
ilist< AliasSet >::iterator iterator
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
ilist< AliasSet >::const_iterator const_iterator
const_iterator begin() const
void print(raw_ostream &OS) const
void add(const MemoryLocation &Loc)
These methods are used to add different types of instructions to the alias sets.
unsigned size() 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.
AliasSet & operator=(const AliasSet &)=delete
ModRefInfo aliasesUnknownInst(const Instruction *Inst, BatchAAResults &AA) const
bool isMustAlias() const
AliasResult aliasesMemoryLocation(const MemoryLocation &MemLoc, BatchAAResults &AA) const
If the specified memory location "may" (or must) alias one of the members in the set return the appro...
friend class AliasSetTracker
SmallVectorImpl< MemoryLocation >::const_iterator iterator
bool isMod() const
bool isRef() const
Accessors...
PointerVector getPointers() const
void dump() const
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
This class represents any memset intrinsic.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
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:185
Representation for a specific memory location.
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
size_t size() const
Definition: SmallVector.h:91
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:591
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:318
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
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:293
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:74