/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/AliasSetTracker.h
Line | Count | Source (jump to first uncovered line) |
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 | | //===----------------------------------------------------------------------===// |
15 | | |
16 | | #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H |
17 | | #define LLVM_ANALYSIS_ALIASSETTRACKER_H |
18 | | |
19 | | #include "llvm/ADT/DenseMap.h" |
20 | | #include "llvm/ADT/DenseMapInfo.h" |
21 | | #include "llvm/ADT/ilist.h" |
22 | | #include "llvm/ADT/ilist_node.h" |
23 | | #include "llvm/Analysis/AliasAnalysis.h" |
24 | | #include "llvm/IR/Instruction.h" |
25 | | #include "llvm/IR/Metadata.h" |
26 | | #include "llvm/IR/ValueHandle.h" |
27 | | #include "llvm/Support/Casting.h" |
28 | | #include <cassert> |
29 | | #include <cstddef> |
30 | | #include <cstdint> |
31 | | #include <iterator> |
32 | | #include <vector> |
33 | | |
34 | | namespace llvm { |
35 | | |
36 | | class AliasSetTracker; |
37 | | class BasicBlock; |
38 | | class LoadInst; |
39 | | class Loop; |
40 | | class MemorySSA; |
41 | | class AnyMemSetInst; |
42 | | class AnyMemTransferInst; |
43 | | class raw_ostream; |
44 | | class StoreInst; |
45 | | class VAArgInst; |
46 | | class Value; |
47 | | |
48 | | class AliasSet : public ilist_node<AliasSet> { |
49 | | friend class AliasSetTracker; |
50 | | |
51 | | class PointerRec { |
52 | | Value *Val; // The pointer this record corresponds to. |
53 | | PointerRec **PrevInList = nullptr; |
54 | | PointerRec *NextInList = nullptr; |
55 | | AliasSet *AS = nullptr; |
56 | | LocationSize Size = LocationSize::mapEmpty(); |
57 | | AAMDNodes AAInfo; |
58 | | |
59 | | // Whether the size for this record has been set at all. This makes no |
60 | | // guarantees about the size being known. |
61 | 2.67M | bool isSizeSet() const { return Size != LocationSize::mapEmpty(); } |
62 | | |
63 | | public: |
64 | | PointerRec(Value *V) |
65 | 2.65M | : Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {} |
66 | | |
67 | 18.4M | Value *getValue() const { return Val; } |
68 | | |
69 | 6.96M | PointerRec *getNext() const { return NextInList; } |
70 | 4.67M | bool hasAliasSet() const { return AS != nullptr; } |
71 | | |
72 | 2.79M | PointerRec** setPrevInList(PointerRec **PIL) { |
73 | 2.79M | PrevInList = PIL; |
74 | 2.79M | return &NextInList; |
75 | 2.79M | } |
76 | | |
77 | 4.68M | bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) { |
78 | 4.68M | bool SizeChanged = false; |
79 | 4.68M | if (NewSize != Size) { |
80 | 2.67M | LocationSize OldSize = Size; |
81 | 2.67M | Size = isSizeSet() ? Size.unionWith(NewSize)14.4k : NewSize2.65M ; |
82 | 2.67M | SizeChanged = OldSize != Size; |
83 | 2.67M | } |
84 | 4.68M | |
85 | 4.68M | if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey()) |
86 | 2.65M | // We don't have a AAInfo yet. Set it to NewAAInfo. |
87 | 2.65M | AAInfo = NewAAInfo; |
88 | 2.02M | else { |
89 | 2.02M | AAMDNodes Intersection(AAInfo.intersect(NewAAInfo)); |
90 | 2.02M | if (!Intersection) { |
91 | 244k | // NewAAInfo conflicts with AAInfo. |
92 | 244k | AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey(); |
93 | 244k | return SizeChanged; |
94 | 244k | } |
95 | 1.78M | AAInfo = Intersection; |
96 | 1.78M | } |
97 | 4.68M | return SizeChanged4.43M ; |
98 | 4.68M | } |
99 | | |
100 | 17.2M | LocationSize getSize() const { |
101 | 17.2M | assert(isSizeSet() && "Getting an unset size!"); |
102 | 17.2M | return Size; |
103 | 17.2M | } |
104 | | |
105 | | /// Return the AAInfo, or null if there is no information or conflicting |
106 | | /// information. |
107 | 17.2M | AAMDNodes getAAInfo() const { |
108 | 17.2M | // If we have missing or conflicting AAInfo, return null. |
109 | 17.2M | if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() || |
110 | 17.2M | AAInfo == DenseMapInfo<AAMDNodes>::getTombstoneKey()) |
111 | 210k | return AAMDNodes(); |
112 | 16.9M | return AAInfo; |
113 | 16.9M | } |
114 | | |
115 | 1.93M | AliasSet *getAliasSet(AliasSetTracker &AST) { |
116 | 1.93M | assert(AS && "No AliasSet yet!"); |
117 | 1.93M | if (AS->Forward) { |
118 | 73.2k | AliasSet *OldAS = AS; |
119 | 73.2k | AS = OldAS->getForwardedTarget(AST); |
120 | 73.2k | AS->addRef(); |
121 | 73.2k | OldAS->dropRef(AST); |
122 | 73.2k | } |
123 | 1.93M | return AS; |
124 | 1.93M | } |
125 | | |
126 | 2.65M | void setAliasSet(AliasSet *as) { |
127 | 2.65M | assert(!AS && "Already have an alias set!"); |
128 | 2.65M | AS = as; |
129 | 2.65M | } |
130 | | |
131 | 2.65M | void eraseFromList() { |
132 | 2.65M | if (NextInList) NextInList->PrevInList = PrevInList1.50M ; |
133 | 2.65M | *PrevInList = NextInList; |
134 | 2.65M | if (AS->PtrListEnd == &NextInList) { |
135 | 1.12M | AS->PtrListEnd = PrevInList; |
136 | 1.12M | assert(*AS->PtrListEnd == nullptr && "List not terminated right!"); |
137 | 1.12M | } |
138 | 2.65M | delete this; |
139 | 2.65M | } |
140 | | }; |
141 | | |
142 | | // Doubly linked list of nodes. |
143 | | PointerRec *PtrList = nullptr; |
144 | | PointerRec **PtrListEnd; |
145 | | // Forwarding pointer. |
146 | | AliasSet *Forward = nullptr; |
147 | | |
148 | | /// All instructions without a specific address in this alias set. |
149 | | /// In rare cases this vector can have a null'ed out WeakVH |
150 | | /// instances (can happen if some other loop pass deletes an |
151 | | /// instruction in this list). |
152 | | std::vector<WeakVH> UnknownInsts; |
153 | | |
154 | | /// Number of nodes pointing to this AliasSet plus the number of AliasSets |
155 | | /// forwarding to it. |
156 | | unsigned RefCount : 27; |
157 | | |
158 | | // Signifies that this set should be considered to alias any pointer. |
159 | | // Use when the tracker holding this set is saturated. |
160 | | unsigned AliasAny : 1; |
161 | | |
162 | | /// The kinds of access this alias set models. |
163 | | /// |
164 | | /// We keep track of whether this alias set merely refers to the locations of |
165 | | /// memory (and not any particular access), whether it modifies or references |
166 | | /// the memory, or whether it does both. The lattice goes from "NoAccess" to |
167 | | /// either RefAccess or ModAccess, then to ModRefAccess as necessary. |
168 | | enum AccessLattice { |
169 | | NoAccess = 0, |
170 | | RefAccess = 1, |
171 | | ModAccess = 2, |
172 | | ModRefAccess = RefAccess | ModAccess |
173 | | }; |
174 | | unsigned Access : 2; |
175 | | |
176 | | /// The kind of alias relationship between pointers of the set. |
177 | | /// |
178 | | /// These represent conservatively correct alias results between any members |
179 | | /// of the set. We represent these independently of the values of alias |
180 | | /// results in order to pack it into a single bit. Lattice goes from |
181 | | /// MustAlias to MayAlias. |
182 | | enum AliasLattice { |
183 | | SetMustAlias = 0, SetMayAlias = 1 |
184 | | }; |
185 | | unsigned Alias : 1; |
186 | | |
187 | | unsigned SetSize = 0; |
188 | | |
189 | 3.13M | void addRef() { ++RefCount; } |
190 | | |
191 | 136k | void dropRef(AliasSetTracker &AST) { |
192 | 136k | assert(RefCount >= 1 && "Invalid reference count detected!"); |
193 | 136k | if (--RefCount == 0) |
194 | 60.7k | removeFromTracker(AST); |
195 | 136k | } |
196 | | |
197 | 1.22M | Instruction *getUnknownInst(unsigned i) const { |
198 | 1.22M | assert(i < UnknownInsts.size()); |
199 | 1.22M | return cast_or_null<Instruction>(UnknownInsts[i]); |
200 | 1.22M | } |
201 | | |
202 | | public: |
203 | | AliasSet(const AliasSet &) = delete; |
204 | | AliasSet &operator=(const AliasSet &) = delete; |
205 | | |
206 | | /// Accessors... |
207 | 894k | bool isRef() const { return Access & RefAccess; } |
208 | 1.54M | bool isMod() const { return Access & ModAccess; } |
209 | 3.68M | bool isMustAlias() const { return Alias == SetMustAlias; } |
210 | 1 | bool isMayAlias() const { return Alias == SetMayAlias; } |
211 | | |
212 | | /// Return true if this alias set should be ignored as part of the |
213 | | /// AliasSetTracker object. |
214 | 1.06M | bool isForwardingAliasSet() const { return Forward; } |
215 | | |
216 | | /// Merge the specified alias set into this alias set. |
217 | | void mergeSetIn(AliasSet &AS, AliasSetTracker &AST); |
218 | | |
219 | | // Alias Set iteration - Allow access to all of the pointers which are part of |
220 | | // this alias set. |
221 | | class iterator; |
222 | 3.44M | iterator begin() const { return iterator(PtrList); } |
223 | 2.83M | iterator end() const { return iterator(); } |
224 | 270 | bool empty() const { return PtrList == nullptr; } |
225 | | |
226 | | // Unfortunately, ilist::size() is linear, so we have to add code to keep |
227 | | // track of the list's exact size. |
228 | 497k | unsigned size() { return SetSize; } |
229 | | |
230 | | /// If this alias set is known to contain a single instruction and *only* a |
231 | | /// single unique instruction, return it. Otherwise, return nullptr. |
232 | | Instruction* getUniqueInstruction(); |
233 | | |
234 | | void print(raw_ostream &OS) const; |
235 | | void dump() const; |
236 | | |
237 | | /// Define an iterator for alias sets... this is just a forward iterator. |
238 | | class iterator : public std::iterator<std::forward_iterator_tag, |
239 | | PointerRec, ptrdiff_t> { |
240 | | PointerRec *CurNode; |
241 | | |
242 | | public: |
243 | 6.27M | explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {} |
244 | | |
245 | 9.52M | bool operator==(const iterator& x) const { |
246 | 9.52M | return CurNode == x.CurNode; |
247 | 9.52M | } |
248 | 9.52M | bool operator!=(const iterator& x) const { return !operator==(x); } |
249 | | |
250 | 1.04M | value_type &operator*() const { |
251 | 1.04M | assert(CurNode && "Dereferencing AliasSet.end()!"); |
252 | 1.04M | return *CurNode; |
253 | 1.04M | } |
254 | 606k | value_type *operator->() const { return &operator*(); } |
255 | | |
256 | 7.74M | Value *getPointer() const { return CurNode->getValue(); } |
257 | 7.74M | LocationSize getSize() const { return CurNode->getSize(); } |
258 | 7.74M | AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); } |
259 | | |
260 | 6.96M | iterator& operator++() { // Preincrement |
261 | 6.96M | assert(CurNode && "Advancing past AliasSet.end()!"); |
262 | 6.96M | CurNode = CurNode->getNext(); |
263 | 6.96M | return *this; |
264 | 6.96M | } |
265 | 0 | iterator operator++(int) { // Postincrement |
266 | 0 | iterator tmp = *this; ++*this; return tmp; |
267 | 0 | } |
268 | | }; |
269 | | |
270 | | private: |
271 | | // Can only be created by AliasSetTracker. |
272 | | AliasSet() |
273 | | : PtrListEnd(&PtrList), RefCount(0), AliasAny(false), Access(NoAccess), |
274 | 1.00M | Alias(SetMustAlias) {} |
275 | | |
276 | 10.3M | PointerRec *getSomePointer() const { |
277 | 10.3M | return PtrList; |
278 | 10.3M | } |
279 | | |
280 | | /// Return the real alias set this represents. If this has been merged with |
281 | | /// another set and is forwarding, return the ultimate destination set. This |
282 | | /// also implements the union-find collapsing as well. |
283 | 2.08M | AliasSet *getForwardedTarget(AliasSetTracker &AST) { |
284 | 2.08M | if (!Forward) return this2.01M ; |
285 | 74.2k | |
286 | 74.2k | AliasSet *Dest = Forward->getForwardedTarget(AST); |
287 | 74.2k | if (Dest != Forward) { |
288 | 1.06k | Dest->addRef(); |
289 | 1.06k | Forward->dropRef(AST); |
290 | 1.06k | Forward = Dest; |
291 | 1.06k | } |
292 | 74.2k | return Dest; |
293 | 74.2k | } |
294 | | |
295 | | void removeFromTracker(AliasSetTracker &AST); |
296 | | |
297 | | void addPointer(AliasSetTracker &AST, PointerRec &Entry, LocationSize Size, |
298 | | const AAMDNodes &AAInfo, bool KnownMustAlias = false, |
299 | | bool SkipSizeUpdate = false); |
300 | | void addUnknownInst(Instruction *I, AliasAnalysis &AA); |
301 | | |
302 | 0 | void removeUnknownInst(AliasSetTracker &AST, Instruction *I) { |
303 | 0 | bool WasEmpty = UnknownInsts.empty(); |
304 | 0 | for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i) |
305 | 0 | if (UnknownInsts[i] == I) { |
306 | 0 | UnknownInsts[i] = UnknownInsts.back(); |
307 | 0 | UnknownInsts.pop_back(); |
308 | 0 | --i; --e; // Revisit the moved entry. |
309 | 0 | } |
310 | 0 | if (!WasEmpty && UnknownInsts.empty()) |
311 | 0 | dropRef(AST); |
312 | 0 | } |
313 | | |
314 | | public: |
315 | | /// If the specified pointer "may" (or must) alias one of the members in the |
316 | | /// set return the appropriate AliasResult. Otherwise return NoAlias. |
317 | | AliasResult aliasesPointer(const Value *Ptr, LocationSize Size, |
318 | | const AAMDNodes &AAInfo, AliasAnalysis &AA) const; |
319 | | bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const; |
320 | | }; |
321 | | |
322 | 0 | inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) { |
323 | 0 | AS.print(OS); |
324 | 0 | return OS; |
325 | 0 | } |
326 | | |
327 | | class AliasSetTracker { |
328 | | /// A CallbackVH to arrange for AliasSetTracker to be notified whenever a |
329 | | /// Value is deleted. |
330 | | class ASTCallbackVH final : public CallbackVH { |
331 | | AliasSetTracker *AST; |
332 | | |
333 | | void deleted() override; |
334 | | void allUsesReplacedWith(Value *) override; |
335 | | |
336 | | public: |
337 | | ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr); |
338 | | |
339 | | ASTCallbackVH &operator=(Value *V); |
340 | | }; |
341 | | /// Traits to tell DenseMap that tell us how to compare and hash the value |
342 | | /// handle. |
343 | | struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {}; |
344 | | |
345 | | AliasAnalysis &AA; |
346 | | MemorySSA *MSSA; |
347 | | Loop *L; |
348 | | ilist<AliasSet> AliasSets; |
349 | | |
350 | | using PointerMapType = DenseMap<ASTCallbackVH, AliasSet::PointerRec *, |
351 | | ASTCallbackVHDenseMapInfo>; |
352 | | |
353 | | // Map from pointers to their node |
354 | | PointerMapType PointerMap; |
355 | | |
356 | | public: |
357 | | /// Create an empty collection of AliasSets, and use the specified alias |
358 | | /// analysis object to disambiguate load and store addresses. |
359 | 573k | explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {} |
360 | | explicit AliasSetTracker(AliasAnalysis &aa, MemorySSA *mssa, Loop *l) |
361 | 156 | : AA(aa), MSSA(mssa), L(l) {} |
362 | 573k | ~AliasSetTracker() { clear(); } |
363 | | |
364 | | /// These methods are used to add different types of instructions to the alias |
365 | | /// sets. Adding a new instruction can result in one of three actions |
366 | | /// happening: |
367 | | /// |
368 | | /// 1. If the instruction doesn't alias any other sets, create a new set. |
369 | | /// 2. If the instruction aliases exactly one set, add it to the set |
370 | | /// 3. If the instruction aliases multiple sets, merge the sets, and add |
371 | | /// the instruction to the result. |
372 | | /// |
373 | | /// These methods return true if inserting the instruction resulted in the |
374 | | /// addition of a new alias set (i.e., the pointer did not alias anything). |
375 | | /// |
376 | | void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo); // Add a loc |
377 | | void add(LoadInst *LI); |
378 | | void add(StoreInst *SI); |
379 | | void add(VAArgInst *VAAI); |
380 | | void add(AnyMemSetInst *MSI); |
381 | | void add(AnyMemTransferInst *MTI); |
382 | | void add(Instruction *I); // Dispatch to one of the other add methods... |
383 | | void add(BasicBlock &BB); // Add all instructions in basic block |
384 | | void add(const AliasSetTracker &AST); // Add alias relations from another AST |
385 | | void addUnknown(Instruction *I); |
386 | | void addAllInstructionsInLoopUsingMSSA(); |
387 | | |
388 | | void clear(); |
389 | | |
390 | | /// Return the alias sets that are active. |
391 | | const ilist<AliasSet> &getAliasSets() const { return AliasSets; } |
392 | | |
393 | | /// Return the alias set which contains the specified memory location. If |
394 | | /// the memory location aliases two or more existing alias sets, will have |
395 | | /// the effect of merging those alias sets before the single resulting alias |
396 | | /// set is returned. |
397 | | AliasSet &getAliasSetFor(const MemoryLocation &MemLoc); |
398 | | |
399 | | /// Return the underlying alias analysis object used by this tracker. |
400 | 238k | AliasAnalysis &getAliasAnalysis() const { return AA; } |
401 | | |
402 | | /// This method is used to remove a pointer value from the AliasSetTracker |
403 | | /// entirely. It should be used when an instruction is deleted from the |
404 | | /// program to update the AST. If you don't use this, you would have dangling |
405 | | /// pointers to deleted instructions. |
406 | | void deleteValue(Value *PtrVal); |
407 | | |
408 | | /// This method should be used whenever a preexisting value in the program is |
409 | | /// copied or cloned, introducing a new value. Note that it is ok for clients |
410 | | /// that use this method to introduce the same value multiple times: if the |
411 | | /// tracker already knows about a value, it will ignore the request. |
412 | | void copyValue(Value *From, Value *To); |
413 | | |
414 | | using iterator = ilist<AliasSet>::iterator; |
415 | | using const_iterator = ilist<AliasSet>::const_iterator; |
416 | | |
417 | 68.5k | const_iterator begin() const { return AliasSets.begin(); } |
418 | 68.5k | const_iterator end() const { return AliasSets.end(); } |
419 | | |
420 | 4.30M | iterator begin() { return AliasSets.begin(); } |
421 | 4.30M | iterator end() { return AliasSets.end(); } |
422 | | |
423 | | void print(raw_ostream &OS) const; |
424 | | void dump() const; |
425 | | |
426 | | private: |
427 | | friend class AliasSet; |
428 | | |
429 | | // The total number of pointers contained in all "may" alias sets. |
430 | | unsigned TotalMayAliasSetSize = 0; |
431 | | |
432 | | // A non-null value signifies this AST is saturated. A saturated AST lumps |
433 | | // all pointers into a single "May" set. |
434 | | AliasSet *AliasAnyAS = nullptr; |
435 | | |
436 | | void removeAliasSet(AliasSet *AS); |
437 | | |
438 | | /// Just like operator[] on the map, except that it creates an entry for the |
439 | | /// pointer if it doesn't already exist. |
440 | 4.67M | AliasSet::PointerRec &getEntryFor(Value *V) { |
441 | 4.67M | AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)]; |
442 | 4.67M | if (!Entry) |
443 | 2.65M | Entry = new AliasSet::PointerRec(V); |
444 | 4.67M | return *Entry; |
445 | 4.67M | } |
446 | | |
447 | | AliasSet &addPointer(MemoryLocation Loc, AliasSet::AccessLattice E); |
448 | | AliasSet *mergeAliasSetsForPointer(const Value *Ptr, LocationSize Size, |
449 | | const AAMDNodes &AAInfo, |
450 | | bool &MustAliasAll); |
451 | | |
452 | | /// Merge all alias sets into a single set that is considered to alias any |
453 | | /// pointer. |
454 | | AliasSet &mergeAllAliasSets(); |
455 | | |
456 | | AliasSet *findAliasSetForUnknownInst(Instruction *Inst); |
457 | | }; |
458 | | |
459 | 0 | inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) { |
460 | 0 | AST.print(OS); |
461 | 0 | return OS; |
462 | 0 | } |
463 | | |
464 | | } // end namespace llvm |
465 | | |
466 | | #endif // LLVM_ANALYSIS_ALIASSETTRACKER_H |