Coverage Report

Created: 2018-09-19 08:35

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