Coverage Report

Created: 2018-07-12 09:57

/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.51M
      : Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {}
61
62
17.2M
    Value *getValue() const { return Val; }
63
64
6.25M
    PointerRec *getNext() const { return NextInList; }
65
4.31M
    bool hasAliasSet() const { return AS != nullptr; }
66
67
2.63M
    PointerRec** setPrevInList(PointerRec **PIL) {
68
2.63M
      PrevInList = PIL;
69
2.63M
      return &NextInList;
70
2.63M
    }
71
72
4.31M
    bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) {
73
4.31M
      bool SizeChanged = false;
74
4.31M
      if (NewSize > Size) {
75
2.51M
        Size = NewSize;
76
2.51M
        SizeChanged = true;
77
2.51M
      }
78
4.31M
79
4.31M
      if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
80
2.51M
        // We don't have a AAInfo yet. Set it to NewAAInfo.
81
2.51M
        AAInfo = NewAAInfo;
82
1.80M
      else {
83
1.80M
        AAMDNodes Intersection(AAInfo.intersect(NewAAInfo));
84
1.80M
        if (!Intersection) {
85
226k
          // NewAAInfo conflicts with AAInfo.
86
226k
          AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey();
87
226k
          return SizeChanged;
88
226k
        }
89
1.58M
        AAInfo = Intersection;
90
1.58M
      }
91
4.31M
      
return SizeChanged4.09M
;
92
4.31M
    }
93
94
16.3M
    LocationSize getSize() const { return Size; }
95
96
    /// Return the AAInfo, or null if there is no information or conflicting
97
    /// information.
98
16.3M
    AAMDNodes getAAInfo() const {
99
16.3M
      // If we have missing or conflicting AAInfo, return null.
100
16.3M
      if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() ||
101
16.3M
          AAInfo == DenseMapInfo<AAMDNodes>::getTombstoneKey())
102
163k
        return AAMDNodes();
103
16.2M
      return AAInfo;
104
16.2M
    }
105
106
1.70M
    AliasSet *getAliasSet(AliasSetTracker &AST) {
107
1.70M
      assert(AS && "No AliasSet yet!");
108
1.70M
      if (AS->Forward) {
109
79.7k
        AliasSet *OldAS = AS;
110
79.7k
        AS = OldAS->getForwardedTarget(AST);
111
79.7k
        AS->addRef();
112
79.7k
        OldAS->dropRef(AST);
113
79.7k
      }
114
1.70M
      return AS;
115
1.70M
    }
116
117
2.51M
    void setAliasSet(AliasSet *as) {
118
2.51M
      assert(!AS && "Already have an alias set!");
119
2.51M
      AS = as;
120
2.51M
    }
121
122
2.51M
    void eraseFromList() {
123
2.51M
      if (NextInList) 
NextInList->PrevInList = PrevInList1.40M
;
124
2.51M
      *PrevInList = NextInList;
125
2.51M
      if (AS->PtrListEnd == &NextInList) {
126
1.07M
        AS->PtrListEnd = PrevInList;
127
1.07M
        assert(*AS->PtrListEnd == nullptr && "List not terminated right!");
128
1.07M
      }
129
2.51M
      delete this;
130
2.51M
    }
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
  /// True if this alias set contains volatile loads or stores.
179
  unsigned Volatile : 1;
180
181
  unsigned SetSize = 0;
182
183
2.99M
  void addRef() { ++RefCount; }
184
185
157k
  void dropRef(AliasSetTracker &AST) {
186
157k
    assert(RefCount >= 1 && "Invalid reference count detected!");
187
157k
    if (--RefCount == 0)
188
67.9k
      removeFromTracker(AST);
189
157k
  }
190
191
2.02M
  Instruction *getUnknownInst(unsigned i) const {
192
2.02M
    assert(i < UnknownInsts.size());
193
2.02M
    return cast_or_null<Instruction>(UnknownInsts[i]);
194
2.02M
  }
195
196
public:
197
  AliasSet(const AliasSet &) = delete;
198
  AliasSet &operator=(const AliasSet &) = delete;
199
200
  /// Accessors...
201
  bool isRef() const { return Access & RefAccess; }
202
1.49M
  bool isMod() const { return Access & ModAccess; }
203
3.24M
  bool isMustAlias() const { return Alias == SetMustAlias; }
204
1
  bool isMayAlias()  const { return Alias == SetMayAlias; }
205
206
  /// Return true if this alias set contains volatile loads or stores.
207
557k
  bool isVolatile() const { return Volatile; }
208
209
  /// Return true if this alias set should be ignored as part of the
210
  /// AliasSetTracker object.
211
1.02M
  bool isForwardingAliasSet() const { return Forward; }
212
213
  /// Merge the specified alias set into this alias set.
214
  void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);
215
216
  // Alias Set iteration - Allow access to all of the pointers which are part of
217
  // this alias set.
218
  class iterator;
219
2.52M
  iterator begin() const { return iterator(PtrList); }
220
2.20M
  iterator end()   const { return iterator(); }
221
58
  bool empty() const { return PtrList == nullptr; }
222
223
  // Unfortunately, ilist::size() is linear, so we have to add code to keep
224
  // track of the list's exact size.
225
462k
  unsigned size() { return SetSize; }
226
227
  void print(raw_ostream &OS) const;
228
  void dump() const;
229
230
  /// Define an iterator for alias sets... this is just a forward iterator.
231
  class iterator : public std::iterator<std::forward_iterator_tag,
232
                                        PointerRec, ptrdiff_t> {
233
    PointerRec *CurNode;
234
235
  public:
236
4.73M
    explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {}
237
238
8.45M
    bool operator==(const iterator& x) const {
239
8.45M
      return CurNode == x.CurNode;
240
8.45M
    }
241
8.45M
    bool operator!=(const iterator& x) const { return !operator==(x); }
242
243
732k
    value_type &operator*() const {
244
732k
      assert(CurNode && "Dereferencing AliasSet.end()!");
245
732k
      return *CurNode;
246
732k
    }
247
321k
    value_type *operator->() const { return &operator*(); }
248
249
7.21M
    Value *getPointer() const { return CurNode->getValue(); }
250
7.21M
    LocationSize getSize() const { return CurNode->getSize(); }
251
7.21M
    AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); }
252
253
6.25M
    iterator& operator++() {                // Preincrement
254
6.25M
      assert(CurNode && "Advancing past AliasSet.end()!");
255
6.25M
      CurNode = CurNode->getNext();
256
6.25M
      return *this;
257
6.25M
    }
258
0
    iterator operator++(int) { // Postincrement
259
0
      iterator tmp = *this; ++*this; return tmp;
260
0
    }
261
  };
262
263
private:
264
  // Can only be created by AliasSetTracker.
265
  AliasSet()
266
      : PtrListEnd(&PtrList), RefCount(0),  AliasAny(false), Access(NoAccess),
267
979k
        Alias(SetMustAlias), Volatile(false) {}
268
269
10.0M
  PointerRec *getSomePointer() const {
270
10.0M
    return PtrList;
271
10.0M
  }
272
273
  /// Return the real alias set this represents. If this has been merged with
274
  /// another set and is forwarding, return the ultimate destination set. This
275
  /// also implements the union-find collapsing as well.
276
1.86M
  AliasSet *getForwardedTarget(AliasSetTracker &AST) {
277
1.86M
    if (!Forward) 
return this1.78M
;
278
80.8k
279
80.8k
    AliasSet *Dest = Forward->getForwardedTarget(AST);
280
80.8k
    if (Dest != Forward) {
281
1.13k
      Dest->addRef();
282
1.13k
      Forward->dropRef(AST);
283
1.13k
      Forward = Dest;
284
1.13k
    }
285
80.8k
    return Dest;
286
80.8k
  }
287
288
  void removeFromTracker(AliasSetTracker &AST);
289
290
  void addPointer(AliasSetTracker &AST, PointerRec &Entry, LocationSize Size,
291
                  const AAMDNodes &AAInfo, bool KnownMustAlias = false);
292
  void addUnknownInst(Instruction *I, AliasAnalysis &AA);
293
294
  void removeUnknownInst(AliasSetTracker &AST, Instruction *I) {
295
    bool WasEmpty = UnknownInsts.empty();
296
    for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
297
      if (UnknownInsts[i] == I) {
298
        UnknownInsts[i] = UnknownInsts.back();
299
        UnknownInsts.pop_back();
300
        --i; --e;  // Revisit the moved entry.
301
      }
302
    if (!WasEmpty && UnknownInsts.empty())
303
      dropRef(AST);
304
  }
305
306
10.5k
  void setVolatile() { Volatile = true; }
307
308
public:
309
  /// Return true if the specified pointer "may" (or must) alias one of the
310
  /// members in the set.
311
  bool aliasesPointer(const Value *Ptr, LocationSize Size,
312
                      const AAMDNodes &AAInfo, AliasAnalysis &AA) const;
313
  bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const;
314
};
315
316
0
inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
317
0
  AS.print(OS);
318
0
  return OS;
319
0
}
320
321
class AliasSetTracker {
322
  /// A CallbackVH to arrange for AliasSetTracker to be notified whenever a
323
  /// Value is deleted.
324
0
  class ASTCallbackVH final : public CallbackVH {
325
    AliasSetTracker *AST;
326
327
    void deleted() override;
328
    void allUsesReplacedWith(Value *) override;
329
330
  public:
331
    ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr);
332
333
    ASTCallbackVH &operator=(Value *V);
334
  };
335
  /// Traits to tell DenseMap that tell us how to compare and hash the value
336
  /// handle.
337
  struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {};
338
339
  AliasAnalysis &AA;
340
  ilist<AliasSet> AliasSets;
341
342
  using PointerMapType = DenseMap<ASTCallbackVH, AliasSet::PointerRec *,
343
                                  ASTCallbackVHDenseMapInfo>;
344
345
  // Map from pointers to their node
346
  PointerMapType PointerMap;
347
348
public:
349
  /// Create an empty collection of AliasSets, and use the specified alias
350
  /// analysis object to disambiguate load and store addresses.
351
561k
  explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
352
561k
  ~AliasSetTracker() { clear(); }
353
354
  /// These methods are used to add different types of instructions to the alias
355
  /// sets. Adding a new instruction can result in one of three actions
356
  /// happening:
357
  ///
358
  ///   1. If the instruction doesn't alias any other sets, create a new set.
359
  ///   2. If the instruction aliases exactly one set, add it to the set
360
  ///   3. If the instruction aliases multiple sets, merge the sets, and add
361
  ///      the instruction to the result.
362
  ///
363
  /// These methods return true if inserting the instruction resulted in the
364
  /// addition of a new alias set (i.e., the pointer did not alias anything).
365
  ///
366
  void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo); // Add a loc
367
  void add(LoadInst *LI);
368
  void add(StoreInst *SI);
369
  void add(VAArgInst *VAAI);
370
  void add(AnyMemSetInst *MSI);
371
  void add(AnyMemTransferInst *MTI);
372
  void add(Instruction *I);       // Dispatch to one of the other add methods...
373
  void add(BasicBlock &BB);       // Add all instructions in basic block
374
  void add(const AliasSetTracker &AST); // Add alias relations from another AST
375
  void addUnknown(Instruction *I);
376
377
  void clear();
378
379
  /// Return the alias sets that are active.
380
  const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
381
382
  /// Return the alias set that the specified pointer lives in. If the New
383
  /// argument is non-null, this method sets the value to true if a new alias
384
  /// set is created to contain the pointer (because the pointer didn't alias
385
  /// anything).
386
  AliasSet &getAliasSetForPointer(Value *P, LocationSize Size,
387
                                  const AAMDNodes &AAInfo);
388
389
  /// Return the alias set containing the location specified if one exists,
390
  /// otherwise return null.
391
  AliasSet *getAliasSetForPointerIfExists(const Value *P, LocationSize Size,
392
                                          const AAMDNodes &AAInfo) {
393
    return mergeAliasSetsForPointer(P, Size, AAInfo);
394
  }
395
396
  /// Return true if the specified instruction "may" (or must) alias one of the
397
  /// members in any of the sets.
398
  bool containsUnknown(const Instruction *I) const;
399
400
  /// Return the underlying alias analysis object used by this tracker.
401
226k
  AliasAnalysis &getAliasAnalysis() const { return AA; }
402
403
  /// This method is used to remove a pointer value from the AliasSetTracker
404
  /// entirely. It should be used when an instruction is deleted from the
405
  /// program to update the AST. If you don't use this, you would have dangling
406
  /// pointers to deleted instructions.
407
  void deleteValue(Value *PtrVal);
408
409
  /// This method should be used whenever a preexisting value in the program is
410
  /// copied or cloned, introducing a new value.  Note that it is ok for clients
411
  /// that use this method to introduce the same value multiple times: if the
412
  /// tracker already knows about a value, it will ignore the request.
413
  void copyValue(Value *From, Value *To);
414
415
  using iterator = ilist<AliasSet>::iterator;
416
  using const_iterator = ilist<AliasSet>::const_iterator;
417
418
69.3k
  const_iterator begin() const { return AliasSets.begin(); }
419
69.3k
  const_iterator end()   const { return AliasSets.end(); }
420
421
4.62M
  iterator begin() { return AliasSets.begin(); }
422
4.62M
  iterator end()   { return AliasSets.end(); }
423
424
  void print(raw_ostream &OS) const;
425
  void dump() const;
426
427
private:
428
  friend class AliasSet;
429
430
  // The total number of pointers contained in all "may" alias sets.
431
  unsigned TotalMayAliasSetSize = 0;
432
433
  // A non-null value signifies this AST is saturated. A saturated AST lumps
434
  // all pointers into a single "May" set.
435
  AliasSet *AliasAnyAS = nullptr;
436
437
  void removeAliasSet(AliasSet *AS);
438
439
  /// Just like operator[] on the map, except that it creates an entry for the
440
  /// pointer if it doesn't already exist.
441
4.31M
  AliasSet::PointerRec &getEntryFor(Value *V) {
442
4.31M
    AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
443
4.31M
    if (!Entry)
444
2.51M
      Entry = new AliasSet::PointerRec(V);
445
4.31M
    return *Entry;
446
4.31M
  }
447
448
  AliasSet &addPointer(Value *P, LocationSize Size, const AAMDNodes &AAInfo,
449
                       AliasSet::AccessLattice E);
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
0
inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {
461
0
  AST.print(OS);
462
0
  return OS;
463
0
}
464
465
} // end namespace llvm
466
467
#endif // LLVM_ANALYSIS_ALIASSETTRACKER_H