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" |
22 | #include "llvm/ADT/SmallVector.h" |
23 | #include "llvm/ADT/ilist.h" |
24 | #include "llvm/ADT/ilist_node.h" |
25 | #include "llvm/Analysis/MemoryLocation.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 | |
32 | namespace llvm { |
33 | |
34 | class AliasResult; |
35 | class AliasSetTracker; |
36 | class AnyMemSetInst; |
37 | class AnyMemTransferInst; |
38 | class BasicBlock; |
39 | class BatchAAResults; |
40 | class LoadInst; |
41 | enum class ModRefInfo : uint8_t; |
42 | class raw_ostream; |
43 | class StoreInst; |
44 | class VAArgInst; |
45 | class Value; |
46 | |
47 | class 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. |
54 | SmallVector<MemoryLocation, 0> MemoryLocs; |
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 | |
100 | public: |
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. |
119 | using iterator = SmallVectorImpl<MemoryLocation>::const_iterator; |
120 | iterator begin() const { return MemoryLocs.begin(); } |
121 | iterator end() const { return MemoryLocs.end(); } |
122 | |
123 | unsigned size() { 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. |
128 | using PointerVector = SmallVector<const Value *, 8>; |
129 | PointerVector getPointers() const; |
130 | |
131 | void print(raw_ostream &OS) const; |
132 | void dump() const; |
133 | |
134 | private: |
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 | |
145 | public: |
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. |
148 | AliasResult aliasesMemoryLocation(const MemoryLocation &MemLoc, |
149 | BatchAAResults &AA) const; |
150 | |
151 | ModRefInfo aliasesUnknownInst(const Instruction *Inst, |
152 | BatchAAResults &AA) const; |
153 | }; |
154 | |
155 | inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) { |
156 | AS.print(OS); |
157 | return OS; |
158 | } |
159 | |
160 | class AliasSetTracker { |
161 | BatchAAResults &AA; |
162 | ilist<AliasSet> AliasSets; |
163 | |
164 | using PointerMapType = DenseMap<AssertingVH<const Value>, AliasSet *>; |
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 | |
170 | public: |
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) {} |
174 | ~AliasSetTracker() { clear(); } |
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 | |
210 | using iterator = ilist<AliasSet>::iterator; |
211 | using const_iterator = ilist<AliasSet>::const_iterator; |
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 | |
222 | private: |
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&: AS->Forward); |
243 | // Swap out AS for AS->Forward, while updating reference counts. |
244 | AliasSet *NewAS = AS->Forward; |
245 | NewAS->addRef(); |
246 | AS->dropRef(AST&: *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 | |
263 | inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) { |
264 | AST.print(OS); |
265 | return OS; |
266 | } |
267 | |
268 | class AliasSetsPrinterPass : public PassInfoMixin<AliasSetsPrinterPass> { |
269 | raw_ostream &OS; |
270 | |
271 | public: |
272 | explicit AliasSetsPrinterPass(raw_ostream &OS); |
273 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
274 | static bool isRequired() { return true; } |
275 | }; |
276 | |
277 | } // end namespace llvm |
278 | |
279 | #endif // LLVM_ANALYSIS_ALIASSETTRACKER_H |
280 | |