Coverage Report

Created: 2018-11-16 02:38

/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
//                     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
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
2.64M
    bool isSizeSet() const { return Size != LocationSize::mapEmpty(); }
61
62
  public:
63
    PointerRec(Value *V)
64
2.63M
      : Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {}
65
66
18.2M
    Value *getValue() const { return Val; }
67
68
6.81M
    PointerRec *getNext() const { return NextInList; }
69
4.64M
    bool hasAliasSet() const { return AS != nullptr; }
70
71
2.77M
    PointerRec** setPrevInList(PointerRec **PIL) {
72
2.77M
      PrevInList = PIL;
73
2.77M
      return &NextInList;
74
2.77M
    }
75
76
4.64M
    bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) {
77
4.64M
      bool SizeChanged = false;
78
4.64M
      if (NewSize != Size) {
79
2.64M
        LocationSize OldSize = Size;
80
2.64M
        Size = isSizeSet() ? 
Size.unionWith(NewSize)13.1k
:
NewSize2.63M
;
81
2.64M
        SizeChanged = OldSize != Size;
82
2.64M
      }
83
4.64M
84
4.64M
      if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
85
2.63M
        // We don't have a AAInfo yet. Set it to NewAAInfo.
86
2.63M
        AAInfo = NewAAInfo;
87
2.01M
      else {
88
2.01M
        AAMDNodes Intersection(AAInfo.intersect(NewAAInfo));
89
2.01M
        if (!Intersection) {
90
239k
          // NewAAInfo conflicts with AAInfo.
91
239k
          AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey();
92
239k
          return SizeChanged;
93
239k
        }
94
1.77M
        AAInfo = Intersection;
95
1.77M
      }
96
4.64M
      
return SizeChanged4.40M
;
97
4.64M
    }
98
99
17.0M
    LocationSize getSize() const {
100
17.0M
      assert(isSizeSet() && "Getting an unset size!");
101
17.0M
      return Size;
102
17.0M
    }
103
104
    /// Return the AAInfo, or null if there is no information or conflicting
105
    /// information.
106
17.0M
    AAMDNodes getAAInfo() const {
107
17.0M
      // If we have missing or conflicting AAInfo, return null.
108
17.0M
      if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() ||
109
17.0M
          AAInfo == DenseMapInfo<AAMDNodes>::getTombstoneKey())
110
207k
        return AAMDNodes();
111
16.8M
      return AAInfo;
112
16.8M
    }
113
114
1.92M
    AliasSet *getAliasSet(AliasSetTracker &AST) {
115
1.92M
      assert(AS && "No AliasSet yet!");
116
1.92M
      if (AS->Forward) {
117
73.3k
        AliasSet *OldAS = AS;
118
73.3k
        AS = OldAS->getForwardedTarget(AST);
119
73.3k
        AS->addRef();
120
73.3k
        OldAS->dropRef(AST);
121
73.3k
      }
122
1.92M
      return AS;
123
1.92M
    }
124
125
2.63M
    void setAliasSet(AliasSet *as) {
126
2.63M
      assert(!AS && "Already have an alias set!");
127
2.63M
      AS = as;
128
2.63M
    }
129
130
2.63M
    void eraseFromList() {
131
2.63M
      if (NextInList) 
NextInList->PrevInList = PrevInList1.48M
;
132
2.63M
      *PrevInList = NextInList;
133
2.63M
      if (AS->PtrListEnd == &NextInList) {
134
1.11M
        AS->PtrListEnd = PrevInList;
135
1.11M
        assert(*AS->PtrListEnd == nullptr && "List not terminated right!");
136
1.11M
      }
137
2.63M
      delete this;
138
2.63M
    }
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
3.10M
  void addRef() { ++RefCount; }
189
190
137k
  void dropRef(AliasSetTracker &AST) {
191
137k
    assert(RefCount >= 1 && "Invalid reference count detected!");
192
137k
    if (--RefCount == 0)
193
60.8k
      removeFromTracker(AST);
194
137k
  }
195
196
1.24M
  Instruction *getUnknownInst(unsigned i) const {
197
1.24M
    assert(i < UnknownInsts.size());
198
1.24M
    return cast_or_null<Instruction>(UnknownInsts[i]);
199
1.24M
  }
200
201
public:
202
  AliasSet(const AliasSet &) = delete;
203
  AliasSet &operator=(const AliasSet &) = delete;
204
205
  /// Accessors...
206
885k
  bool isRef() const { return Access & RefAccess; }
207
1.55M
  bool isMod() const { return Access & ModAccess; }
208
3.66M
  bool isMustAlias() const { return Alias == SetMustAlias; }
209
1
  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
1.06M
  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
3.41M
  iterator begin() const { return iterator(PtrList); }
222
2.81M
  iterator end()   const { return iterator(); }
223
270
  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
492k
  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
6.22M
    explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {}
243
244
9.35M
    bool operator==(const iterator& x) const {
245
9.35M
      return CurNode == x.CurNode;
246
9.35M
    }
247
9.35M
    bool operator!=(const iterator& x) const { return !operator==(x); }
248
249
1.03M
    value_type &operator*() const {
250
1.03M
      assert(CurNode && "Dereferencing AliasSet.end()!");
251
1.03M
      return *CurNode;
252
1.03M
    }
253
603k
    value_type *operator->() const { return &operator*(); }
254
255
7.59M
    Value *getPointer() const { return CurNode->getValue(); }
256
7.59M
    LocationSize getSize() const { return CurNode->getSize(); }
257
7.59M
    AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); }
258
259
6.81M
    iterator& operator++() {                // Preincrement
260
6.81M
      assert(CurNode && "Advancing past AliasSet.end()!");
261
6.81M
      CurNode = CurNode->getNext();
262
6.81M
      return *this;
263
6.81M
    }
264
0
    iterator operator++(int) { // Postincrement
265
0
      iterator tmp = *this; ++*this; return tmp;
266
0
    }
267
  };
268
269
private:
270
  // Can only be created by AliasSetTracker.
271
  AliasSet()
272
      : PtrListEnd(&PtrList), RefCount(0),  AliasAny(false), Access(NoAccess),
273
1.00M
        Alias(SetMustAlias) {}
274
275
10.3M
  PointerRec *getSomePointer() const {
276
10.3M
    return PtrList;
277
10.3M
  }
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
2.07M
  AliasSet *getForwardedTarget(AliasSetTracker &AST) {
283
2.07M
    if (!Forward) 
return this2.00M
;
284
74.3k
285
74.3k
    AliasSet *Dest = Forward->getForwardedTarget(AST);
286
74.3k
    if (Dest != Forward) {
287
1.02k
      Dest->addRef();
288
1.02k
      Forward->dropRef(AST);
289
1.02k
      Forward = Dest;
290
1.02k
    }
291
74.3k
    return Dest;
292
74.3k
  }
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
0
inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
321
0
  AS.print(OS);
322
0
  return OS;
323
0
}
324
325
class AliasSetTracker {
326
  /// A CallbackVH to arrange for AliasSetTracker to be notified whenever a
327
  /// Value is deleted.
328
0
  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
573k
  explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
356
573k
  ~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 the underlying alias analysis object used by this tracker.
393
244k
  AliasAnalysis &getAliasAnalysis() const { return AA; }
394
395
  /// This method is used to remove a pointer value from the AliasSetTracker
396
  /// entirely. It should be used when an instruction is deleted from the
397
  /// program to update the AST. If you don't use this, you would have dangling
398
  /// pointers to deleted instructions.
399
  void deleteValue(Value *PtrVal);
400
401
  /// This method should be used whenever a preexisting value in the program is
402
  /// copied or cloned, introducing a new value.  Note that it is ok for clients
403
  /// that use this method to introduce the same value multiple times: if the
404
  /// tracker already knows about a value, it will ignore the request.
405
  void copyValue(Value *From, Value *To);
406
407
  using iterator = ilist<AliasSet>::iterator;
408
  using const_iterator = ilist<AliasSet>::const_iterator;
409
410
70.5k
  const_iterator begin() const { return AliasSets.begin(); }
411
70.5k
  const_iterator end()   const { return AliasSets.end(); }
412
413
4.31M
  iterator begin() { return AliasSets.begin(); }
414
4.31M
  iterator end()   { return AliasSets.end(); }
415
416
  void print(raw_ostream &OS) const;
417
  void dump() const;
418
419
private:
420
  friend class AliasSet;
421
422
  // The total number of pointers contained in all "may" alias sets.
423
  unsigned TotalMayAliasSetSize = 0;
424
425
  // A non-null value signifies this AST is saturated. A saturated AST lumps
426
  // all pointers into a single "May" set.
427
  AliasSet *AliasAnyAS = nullptr;
428
429
  void removeAliasSet(AliasSet *AS);
430
431
  /// Just like operator[] on the map, except that it creates an entry for the
432
  /// pointer if it doesn't already exist.
433
4.64M
  AliasSet::PointerRec &getEntryFor(Value *V) {
434
4.64M
    AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
435
4.64M
    if (!Entry)
436
2.63M
      Entry = new AliasSet::PointerRec(V);
437
4.64M
    return *Entry;
438
4.64M
  }
439
440
  AliasSet &addPointer(MemoryLocation Loc, AliasSet::AccessLattice E);
441
  AliasSet *mergeAliasSetsForPointer(const Value *Ptr, LocationSize Size,
442
                                     const AAMDNodes &AAInfo);
443
444
  /// Merge all alias sets into a single set that is considered to alias any
445
  /// pointer.
446
  AliasSet &mergeAllAliasSets();
447
448
  AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
449
};
450
451
0
inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {
452
0
  AST.print(OS);
453
0
  return OS;
454
0
}
455
456
} // end namespace llvm
457
458
#endif // LLVM_ANALYSIS_ALIASSETTRACKER_H