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